CrossCheck: Input Validation for WAN Control Systems

The paper presents CrossCheck, a shadow validation system for Wide Area Network SDN controllers that effectively detects invalid inputs to prevent network outages while maintaining a zero false positive rate even under conditions of noisy or corrupted telemetry data.

The Gist

Imagine a massive, global internet highway system run by a super-intelligent traffic control center (the SDN Controller). This center decides the best routes for every car (data packet) to ensure no traffic jams occur.

However, this control center is only as smart as the information it receives. If the traffic cameras are broken, or if the report on how many cars are entering the highway is wrong, the control center will make bad decisions, causing massive gridlock (network outages).

CrossCheck is a new "safety inspector" system designed to catch these bad reports before they cause a crash.

Here is how it works, explained through simple analogies:

1. The Problem: The "Blind" Traffic Cop

In the real world, the traffic control center relies on two main things:

• The Demand Report: A list saying, "We expect 1,000 cars to go from City A to City B."
• The Map: A list of which roads are open and how wide they are.

The Issue: Sometimes, the software that writes these reports has bugs.

• Example: A bug might tell the controller, "There are 10,000 cars coming!" when there are actually only 1,000. The controller, trying to be helpful, might try to route all 10,000 cars onto a road that only fits 1,000. Result: A massive traffic jam (outage).

Traditionally, operators tried to catch these errors with "sanity checks" (like asking, "Is the number negative?"). But these checks are like a bouncer at a club who only checks for ID. They can't tell if the person is lying about their age. They miss subtle lies that still look "legal."

2. The Solution: CrossCheck (The "Reality Check")

CrossCheck acts as a shadow inspector. It sits next to the traffic control center, watching everything, but it doesn't actually drive the cars. It just watches and whispers, "Hey, that report looks fake!"

It uses a clever trick based on conservation of flow (a fancy way of saying: what goes in must come out).

The Analogy: The Water Pipe Network

Imagine a network of water pipes connecting different cities.

• The Controller's Report: Says, "We are pumping 100 gallons of water into Pipe A."
• The Reality (Router Signals): The pipes have sensors at both ends.
  • Sensor at the start says: "100 gallons left."
  • Sensor at the end says: "100 gallons arrived."

CrossCheck's Job:
It compares the Report (100 gallons) against the Sensors (Start and End).

• Scenario A (Noise): Maybe the sensor at the end is glitchy and says "98 gallons." CrossCheck knows sensors sometimes glitch. It looks at other pipes connected to that city. If 99 other pipes say "100 gallons," CrossCheck realizes, "Okay, that one sensor is just having a bad day. I'll ignore it."
• Scenario B (The Bug): The report says "100 gallons," but every single sensor along the path says "50 gallons." CrossCheck sees a massive mismatch. It realizes the Report is the liar, not the sensors. It sounds the alarm: "STOP! The input is wrong!"

3. How It Handles "Noisy" Data

Real-world data is messy. Sensors can be slow, or they might miss a few packets.

• The "Gossip" Method: CrossCheck doesn't just look at one pipe. It uses a "gossip" strategy. It asks the neighbors: "Hey, if I send 100 gallons here, where did it go?"
• If a few sensors are broken, the majority of the other sensors will "vote" for the correct number. CrossCheck takes a majority vote to figure out the truth.
• The Magic: Because the "lie" (the bad input) affects the entire network path, it creates a pattern of errors that looks very different from a single broken sensor. CrossCheck can spot this pattern instantly.

4. Why It's a Game Changer

The authors tested CrossCheck on a real, massive Google network for four weeks.

• The Result: It caught one real mistake where the data was doubled (a bug that would have caused a huge outage).
• The Safety: It had zero false alarms. It never yelled "Fire!" when there was just a candle. This is crucial because if a system cries wolf too often, operators stop listening.

Summary

Think of CrossCheck as a lie detector test for network data.

• Old systems asked: "Does this number look impossible?" (e.g., Is it negative?)
• CrossCheck asks: "Does this number match what the rest of the world is actually seeing?"

By constantly cross-referencing the "story" the controller is told with the "physical reality" of the network, CrossCheck ensures that the traffic cop never makes a decision based on a lie, keeping the internet running smoothly.

Technical Summary

Here is a detailed technical summary of the paper "CrossCheck: Input Validation for WAN Control Systems."

1. Problem Statement

The paper addresses a critical vulnerability in Wide Area Network (WAN) operations: incorrect inputs to Software-Defined Networking (SDN) controllers.

• Root Cause: Analysis of major outages at a large cloud provider (2019–2024) revealed that over one-third were caused by incorrect inputs (e.g., inaccurate traffic demand matrices or topology views) rather than controller logic errors. These errors stem from bugs in the complex control infrastructure, faulty router telemetry, or external data aggregation issues.
• Limitations of Current Solutions: Existing validation methods rely on static sanity checks (e.g., checking for impossible values). These are insufficient because incorrect inputs are often syntactically valid but inconsistent with the actual network state. Furthermore, static heuristics generate high false positive rates during legitimate network anomalies (e.g., disasters), leading to alert fatigue.
• The Challenge: Building a system that detects input errors in real-time with a near-zero False Positive Rate (FPR) is difficult because:
  1. Real-world telemetry is inherently noisy.
  2. The "ground truth" signals (router counters) used for validation can themselves be buggy.
  3. The system must operate at the timescale of SDN decisions (minutes) without introducing significant latency.

2. Methodology: CrossCheck System

CrossCheck is a shadow validation system that decouples from the production SDN control plane. It continuously validates controller inputs against the current network state derived from low-level router signals.

A. System Architecture

The system operates in three stages:

1. Collection: Streams raw router signals (link status, byte counters, forwarding entries) and controller inputs (demand matrices, topology) into a dedicated, isolated backend database.
2. Repair: Constructs a reliable, network-wide view of the current state by detecting and correcting faulty router signals using network invariants.
3. Validation: Compares the controller's inputs against the "repaired" state to classify inputs as correct or incorrect.

B. Key Technical Components

1. Collected Signals:
CrossCheck utilizes three types of signals, chosen for their independence from controller inputs:

• Link Status Indicators: Physical and link-layer status (e.g., BFD heartbeats) from both ends of a link.
• Link Counters: Hardware byte counters (transmit/receive) from router interfaces.
• Forwarding Entries: Routing tables used to reconstruct traffic paths and estimate demand-induced load.

2. Network Invariants & Repair Algorithm:
The core innovation is leveraging flow conservation to distinguish between local noise (buggy routers) and global errors (bad inputs). CrossCheck enforces four invariants:

• Link Invariants: Both ends of a link must agree on status; transmit counters must equal receive counters ($l_{out} = l_{in}$).
• Router Invariants: Total incoming traffic must equal total outgoing traffic at a router.
• Path Invariants: Traffic demand estimated via forwarding tables must match observed link loads.

The Repair Process (Voting Mechanism):
To handle noisy or buggy signals, CrossCheck employs a multi-round voting algorithm:

• It generates multiple "votes" for the load on a specific link from different sources (e.g., $l_{out}$, $l_{in}$, $l_{demand}$, and estimates derived from neighbor routers via flow conservation).
• It runs multiple random voting rounds to explore combinations, aggregating votes that fall within a noise threshold ($N=5\%$).
• It uses a gossip-like iterative approach: It finalizes the link with the highest confidence score, fixes its value, and re-runs the process. This allows correct values to propagate and override local pockets of correlated bugs.

3. Validation Logic:

• Demand Validation: Checks if the demand-induced load ($l_{demand}$) matches the repaired link load ($l_{final}$).
  • Differentiation: A buggy demand causes widespread inconsistencies across many links (global pattern), whereas noisy telemetry causes localized inconsistencies (confined to adjacent links).
  • Decision: If the fraction of links satisfying the path invariant exceeds a calibrated cutoff ($\Gamma$), the input is accepted.
• Topology Validation: Uses a simple majority vote across five independent signals (physical status, link status, and whether $l_{final} > 0$) to determine link up/down status.

3. Key Contributions

1. Decoupled Shadow Architecture: A system design that validates inputs in real-time without risking the production control plane, ensuring isolation from shared failure modes.
2. Invariant-Based Repair: A novel algorithm that reconstructs the "true" network state by exploiting flow conservation, enabling the system to tolerate up to 30% corrupted telemetry data.
3. Asymmetry Exploitation: The ability to distinguish between local sensor noise and global input errors based on the spatial distribution of invariant violations.
4. Scalability: Theoretical and empirical proof that validation accuracy improves exponentially with network size, as larger networks provide more redundant signals to corroborate the truth.

4. Results

The authors evaluated CrossCheck via a 4-week shadow deployment in a production WAN (WAN A) and extensive simulations.

• Production Deployment:

  • False Positive Rate (FPR): 0% over 4 weeks. It did not trigger false alarms despite real-world noise.
  • True Positive Rate (TPR): Successfully detected the single incident of invalid input that occurred during the deployment (a bug that doubled traffic demand estimates).
  • Performance: Runtime was under 10 seconds per validation cycle (mostly spent on the repair algorithm), well within the minute-scale decision window of SDN controllers.

• Simulation Results:

  • Demand Perturbation: Detected 100% of demand perturbations $\ge 5\%$. Even 2–3% perturbations were detected with 74% accuracy.
  • Telemetry Resilience: Maintained 0% FPR even when 30% of router counters were zeroed or corrupted.
  • Correlated Failures: Remained robust against correlated bugs (e.g., a router reporting all interfaces as down) up to 25% of telemetry corruption.
  • Topology Validation: Successfully repaired incorrect link states even when >25% of routers were buggy.

5. Significance

• Outage Prevention: CrossCheck addresses the leading cause of major WAN outages (incorrect inputs) which current static checks fail to catch.
• Operational Safety: By achieving a near-zero FPR, it builds operator trust, making automated alerting feasible without causing "alert fatigue."
• Generalizability: While focused on SDN Traffic Engineering, the methodology (validating high-level inputs against low-level ground truth via invariants) is applicable to other control systems, including non-SDN networks, building climate control, and power management.
• Paradigm Shift: Moves network validation from static, pre-deployment checks to dynamic, runtime verification based on physical network laws (conservation of flow).

In conclusion, CrossCheck demonstrates that it is possible to build a highly reliable, automated system that detects subtle input errors in massive, complex networks by leveraging the inherent redundancy and physical constraints of the network itself.