Symphony: Path Validation at Scale

Symphony: Path Validation at Scale

Speakers: Anxiao He

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=rJGR_G9ap2M

Overview

In this presentation at the NDSS Symposium, Anxiao He introduced "Symphony: Path Validation at Scale," a groundbreaking work addressing a fundamental security challenge in future Internet architectures. The talk centers on path validation, a critical mechanism designed to empower end-hosts to specify and verify the precise forwarding paths for their network traffic. Unlike the current Internet, where packet forwarding is largely opaque and uncontrolled, path validation promises significant advancements in flexibility, security, and privacy by requiring on-path routers to embed unforgeable cryptographic proofs into packet headers, testifying to strict adherence to the designated path.

The core dilemma in achieving robust path validation lies in balancing security with efficiency. To guarantee unforgeability against sophisticated active Dolev-Yao attackers, these cryptographic proofs must be sufficiently complex and lengthy, demanding substantial computational resources. This inherent complexity creates an efficiency bottleneck, severely limiting the scalability of existing solutions. State-of-the-art approaches often compromise by either validating only a subset of routers or embedding partial, and thus weaker, proofs. Symphony tackles this dilemma by proposing aggregate validation, a novel paradigm that processes packets in groups rather than individually. By aggregating a group of packets and using them as a single input for proof computation, Symphony amortizes the validation overhead across multiple packets, thereby achieving dramatically higher validation efficiency without sacrificing the strong security guarantees of full, hop-wise proof validation.

Background

▶ Watch: Introduction: Path validation challenge and Symphony's solution (0:00)

Path validation is conceptualized through two complementary functionalities: path enforcement and path verification. Path enforcement ensures that packets strictly adhere to the designated path specified in their headers. However, the presence of malicious or compromised routers necessitates path verification, which guarantees that packets have indeed followed the specified path by embedding unforgeable cryptographic proofs.

Symphony operates within a system model that assumes an Internet architecture augmented with lightweight enhancements. In this model, end-hosts can select their preferred forwarding paths, and on-path routers are responsible for enforcing and verifying compliance with these paths. Path authorization can be managed by either a centralized authority or distributed routers. The work adopts an inter-AS path model, abstracting each Autonomous System into a single node, consistent with much of the existing literature. Both routers and end-hosts require updates to their packet processing logic and protocol stacks, respectively, to handle the embedded path proofs and facilitate path requests.

The threat model for Symphony is robust, considering an active Dolev-Yao attacker. This attacker is capable of mis-forwarding packets and actively attempting to forge valid path proofs. This includes scenarios where malicious or hijacked routers might bypass specified routers, direct packets in incorrect orders, or try to make mis-forwarded packets pass validation through proof forgery. To counter such threats, Symphony defines two critical security requirements:

1. Proof Unforgeability: Path proofs must be computationally hard to forge, ensuring that any mis-forwarded packets are reliably detected and filtered.
2. Hop-wise Validation: Mis-forwarded packets should be detected and discarded as early as possible, ideally at each hop, to minimize security impacts and resource waste. This is formalized through predicates, ensuring that a router accepting a packet confirms its origin from a trusted source, traversal through honest routers in the correct order, and correct proof verification and updates.

Beyond security, two efficiency requirements are paramount:

1. Throughput: Quantifies the total bandwidth consumed for transmitting packets, including their path proofs.
2. Goodput: Measures the bandwidth consumed solely for transmitting actual packet payloads. High goodput is desirable, implying a high ratio of payload size to total packet length, which in turn means smaller proof sizes are beneficial.

Path validation has been an active area of research, with several prior solutions attempting to balance security and efficiency:

• ICING 39 was an early scheme that required every router to compute a proof for each downstream router. It used aggregate MACs to merge O(n²) proofs into O(n) fields (where 'n' is path length), but relied on computationally intensive pair-wise shared keys between end-hosts and routers.
• Origin and Path Trace (OPT) 33 aimed to reduce the number of proof fields requiring verification and update to O(1). It pre-computed verification fields at the source, which routers then verified. While improving efficiency, it still involved packet-wise proof computation.
• Probabilistic Path Validation (PPV) 48 adopted a different approach, probabilistically selecting a subset of on-path routers to mark packets, with proofs verified only at the destination. This was efficient but sacrificed hop-wise validation and relied on sufficient packet numbers to infer path behavior.
• OSV 9, 10 replaced traditional cryptographic computations with Hadamard matrix computations, offering faster calculation and better parallelizability. However, the simplicity of computation might compromise security and integrity guarantees.
• The state-of-the-art, EPIC 36, improved upon OPT by significantly shortening proof field lengths, embedding only the first few bytes (e.g., five bytes) of each verification field into packet headers. While this drastically reduced header overhead, it made proofs more vulnerable to brute-force attacks and necessitated additional security schemes, potentially weakening the core hop-wise validation principle.

Symphony critically identifies packet-wise validation as a fundamental efficiency bottleneck common to all these existing solutions. Instead of merely optimizing individual packet processing or compromising on hop-wise validation, Symphony introduces aggregate validation as a new paradigm. This allows for high efficiency by amortizing cryptographic overhead across groups of packets, without sacrificing the strong security guarantees of full, hop-wise proof validation.

Key Findings

▶ Watch: Background: Path enforcement, verification, and system model (2:00)

The research behind Symphony yielded several crucial findings and contributions that significantly advance the field of network security:

• Fundamental Efficiency Improvement: Aggregate validation fundamentally improves path validation efficiency by amortizing cryptographic overhead across packet groups. This paradigm shift addresses the inherent security-efficiency dilemma more effectively than prior packet-wise approaches.
• Superior Performance: Symphony achieves significantly faster packet processing and higher communication throughput compared to state-of-the-art packet-wise solutions like EPIC, all without compromising the stringent security requirements of path validation.
• Efficient Router-Queue Logic: The proposed SRAM-based router-queue logic is highly effective in efficiently handling packet grouping and reordering, which is critical for the practical implementation of aggregate validation in hardware routers.
• Resilience to Packet Loss: Symphony-PR (Packet Reaggregation) effectively mitigates the impact of high packet loss rates by enabling intermediate reaggregation, demonstrating robustness in disruptive network conditions.

The specific performance improvements demonstrated by Symphony are compelling:

• Construction Time Reduction: Symphony reduces the proof construction time at the source by 39.51% to 93.78% compared to EPIC, depending on path length and group size.
• Router Processing Speedup: Routers running Symphony achieve a processing speedup of 3.78x to 18.40x compared to EPIC.
• Communication Throughput Increase: Symphony increases communication throughput by 1.13x to 6.11x compared to EPIC, achieving up to 9.19 Gbps on a single-core machine for specific configurations.

Technical Deep Dive

▶ Watch: Security and efficiency requirements for path validation (3:15)

The core innovation of Symphony lies in its aggregate validation technique, which fundamentally redefines how path proofs are computed and verified. Instead of the traditional packet-wise approach, Symphony treats a group of packets as a single, logical input for the path validation protocol. A single, comprehensive proof is computed for the entire group, and this group proof is then intelligently distributed across the individual packets within that group. This amortization strategy offers several advantages:

1. Shorter Proofs per Packet: The effective proof size per packet is drastically reduced, improving goodput and alleviating MTU (Maximum Transmission Unit) limitations, which are common issues when embedding large cryptographic proofs.
2. Faster Validation per Packet: The intensive computational cost of generating, verifying, and updating proofs is performed once for the entire group. When amortized across 'm' packets, the per-packet computational overhead is significantly reduced.
3. Reduced Queuing Time: Processing packets in groups allows multiple packets to be fetched simultaneously from the queue, effectively eliminating the waiting time that would otherwise be interleaved between individual packet validations. This approach is feasible due to the high transmission rates in modern networks, where router queues are often populated with numerous packets, and path validation itself can increase queue lengths.

The Symphony protocol implements aggregate validation through a four-step packet processing logic on routers:

1. Fetch: The router initiates the process by fetching a group of packets from its input queue. This step is crucial and requires careful queue management to ensure that complete groups can be assembled.
2. Verify: The router takes the entire group of packets as a single input. It computes the expected path validation proofs for this group, extracts the carried proofs from all packets in the group, concatenates them, and then verifies the proof validity by comparing the computed proof with the concatenated one. An all-or-nothing principle is applied: if the proofs match, the entire group passes validation; otherwise, the entire group is discarded, simplifying design and ensuring strong security.
3. Update: If verification succeeds, the router updates the packet proofs by integrating its own credential into the group proof. Again, the router processes the entire group as a single input for this computation. The newly computed proof is then evenly distributed across all packets in the group, replacing the original proofs.
4. Transfer: Finally, the router places the group of verified packets, now carrying updated proofs, into the output queue for forwarding to the next hop.

To support this group-wise processing, Symphony necessitates specialized router-queue logics. Traditional FIFO queues are inadequate as packets from the same group might arrive out of order or be interleaved with packets from other groups. Symphony proposes an SRAM-based solution for hardware routers. This involves a small SRAM configured as a g x m grid, where g is the number of groups the queue can hold, and m is the number of packets per group. Each SRAM cell stores validation metadata. Packets fetched from the FIFO queue are placed into the SRAM, with a GroupTag mapping to a specific row and an OrderTag mapping to a column within that row. This hardware-assisted approach ensures that packets of the same group are collected and ordered correctly before validation, minimizing reordering overhead.

The Symphony header, placed between the IP and TCP headers, is central to the protocol. It contains seven fields:

1. SessionID (16 bytes): A 128-bit identifier negotiated by the source and destination, uniquely identifying a communication session and its designated path. It serves as an input for SymphonyProof computation to prevent rerouting attacks.
2. GroupTag (8 bits): Initializes at the source, uniquely identifies a group of packets within a session. Together with SessionID, it uniquely classifies packet groups, preventing inter-group mixing. Its 8-bit length balances collision avoidance with practical queue lengths.
3. OrderTag (8 bits): Initializes at the source, specifying the ordering index of a packet within its group (e.g., 0 to m-1). This is vital for preserving source-defined order for proof computation and addressing intra-group disordering. An 8-bit OrderTag supports up to 256 packets per group.
4. GroupSize (8 bits): Explicitly specifies the number of packets in a group, allowing routers and end-hosts to determine how many packets to collect and aiding in detecting incomplete groups due to packet loss.
5. Timestamp (4 bytes): Records the creation time of the packet group at the source, stored only in the first packet. It ensures packet freshness and helps prevent replay attacks, also fed into SymphonyProof computation.
6. DataHash (32 bytes): Supports group-wise integrity checks. It's calculated as H(GP), where GP is the concatenation of all packet payloads in a group. DataHash is then evenly distributed across packets and included in SymphonyProof, preventing malicious modification and offering higher goodput than packet-wise hashing.
7. SymphonyProof (variable size): The only cryptography-protected field, comprising two sub-fields:

• Update field (σ): Updated hop-by-hop by intermediate routers.
• Verification fields (Vi): Pre-computed by the source and fixed during transmission. Both σ and Vi are divided and distributed across packets in the group to amortize space overhead.

Packet aggregation is a key challenge, addressed by using SessionID and GroupTag for unique group identification and OrderTag for preserving order. To avoid GroupTag collisions, the protocol ensures that a reused GroupTag only reaches a router after all packets from the previous group with that tag have been processed, with Equation (1) providing constraints for GroupTag length.

Symphony's aggregate validation is detailed through four main functions:

1. Initialization: The source (Ro) and destination (Rn) exchange shared symmetric keys (Kn). The source also exchanges shared symmetric keys (Ki) with each on-path router (Ri). These keys, often established via Diffie-Hellman, are crucial for proof construction, verification, and updates.
2. Construction (Source): For a group of 'm' packets (Pi), the source sets SessionID, GroupTag, OrderTag, and GroupSize. The Timestamp is set for the first packet. The group payload (GP) is formed by concatenating all packet payloads, and DataHash is computed as H(GP) and distributed. An intermediate value h is computed as SessionID || DataHash || Timestamp. The initial update field σ0 is computed as MACK_K0(h). A series of verification fields Vi are then iteratively computed for each hop i from 1 to n (path length) as MACK_Ki(h || σi-1). Both σ0 and Vi are divided and distributed across all packet headers.
3. Verification (Router Ri): Upon receiving a complete group, the router reconstructs h and σ from the packets. It computes its expected verification field V' as MACK_Ki(h || σ). If V' matches the Vi carried in the group, verification succeeds. Otherwise, or if the group is incomplete, the entire group is dropped.
4. Update (Router Ri): If verification succeeds and Ri is not the destination, it updates the σ field. The new σ is computed as MACK_Ki(σ), then divided and distributed across all packet headers for the next hop.

The security analysis formally proves Symphony's adherence to proof unforgeability and hop-wise validation, and discusses its resistance to DDoS attacks.

• A. Proof Unforgeability: Symphony relies on Cipher Block Chaining MAC (CBC MAC), implemented with AES-128, ensuring negligible forging probability (approx. 2^-26 for 1000-byte packets). The cryptographic computation of σ and Vi involves SessionID, Timestamp, and DataHash, making brute-force attacks extremely unlikely (2^(-128(n+1)) for an n-hop path). Shared 128-bit symmetric keys further secure the system. Crucially, an attacker must forge proofs for an entire group of 'm' packets, not just one, introducing an O(m) complexity multiplier that significantly increases the difficulty of forgery.
• B. Hop-wise Validation:
• Packet Alteration (Theorem 2): Any modification to a packet in a group changes its DataHash, causing verification to fail and the group to be discarded.
• Packet Injection (Theorem 3): Injected packets will lack valid source signatures. Replayed valid groups are detected via expired Timestamps, which are signed into the proofs and unforgeable.
• Packet Deviation (Theorem 4): Rerouting to an off-path router causes a SessionID mismatch. Incorrect ordering on the specified path leads to incorrect credential integration, causing verification failure at subsequent hops.
• C. DDoS Resistance: While not a primary design goal, tampering with proof-related fields leads to packet discard, similar to integrity violations. The system can identify suspicious routers sending many invalid packets.

Symphony is more sensitive to packet loss than packet-wise solutions because the loss of a single packet necessitates retransmission of the entire group. To address this, Packet Reaggregation (Symphony-PR) is introduced. An intermediate router can act as a new source, re-initiating aggregation validation over the remaining verified packets of a group. Only lost or unverified packets are retransmitted and mixed into subsequent groups to regain efficiency. To protect against untrusted new sources, Symphony-PR introduces a signed binding δ = MACK_Kon(SessionID || P.payload) and an unforgeable field ε (nested encryption of δ) to track forwarding history.

Demo / Proof of Concept

▶ Watch: Related work and limitations of existing solutions (4:00)

The efficacy and performance of Symphony were rigorously demonstrated through a comprehensive implementation and evaluation, serving as its proof of concept. The system was implemented using the Data Plane Development Kit (DPDK) 28, a collection of libraries optimized for high-speed packet processing on Intel processors. To accelerate cryptographic computations, the implementation leveraged Intel AES-NI hardware instructions 41, showcasing a practical approach to achieving high performance.

The evaluation was conducted across two distinct setups:

1. Local Server: An Intel Xeon E5-2630 v3 (2.40 GHz) server, equipped with 8 cores, 16 GB of memory, and two Intel I350 Gigabit / X710 Ethernet NICs. One NIC was configured as a packet generator and bandwidth monitor, while the other performed the demanding path validation computations.
2. Multihop Testbed: A real-world deployed testbed utilizing rented servers from Alibaba Cloud 17. These servers featured 3.2 GHz Intel Xeon Platinum 8269CY processors (Cascade Lake) and a 10 Gbps elastic NIC. For this multihop environment, the evaluation primarily focused on single-core performance due to memory constraints.

Symphony's performance was benchmarked against the state-of-the-art EPIC 36 across various critical metrics:

• Proof Size and Goodput Ratio: Symphony significantly reduces proof size compared to ICING and OPT (O(n) complexity), achieving O(n/m) complexity. For an 8-hop path with a group size of 16 (m=16), Symphony's proof size was 30 bytes, compared to EPIC's 56 bytes (which uses partial proofs). With a 1,000-byte payload, Symphony maintained a high goodput ratio of 91.72% even for a 16-hop path with m=16, consistently outperforming OPT and ICING.
• Construction Time at Source: Symphony dramatically reduces the time taken by the source to generate proofs. For a 16-hop path, the construction time dropped from 9.11 μs (m=2) to 2.39 μs (m=8). Compared to EPIC, Symphony achieved a reduction in construction time ranging from 39.51% (m=2) to 93.78% (m=16).
• Reassembly and Reordering Time on Router: The reassembly time (collecting a complete group) was found to be very fast, increasing from 0.06 μs (m=2) to 0.29 μs (m=16). For hardware routers, the proposed SRAM-based logic resulted in minimal reordering time, approximating SRAM access time (e.g., 0.003 μs). Even in software, reordering time was a small fraction (1.57% to 20.68%) of total verification time.
• Processing Time on Router: This includes verification and update. Symphony's processing time remained relatively constant regardless of path length (due to only two MAC operations per hop) and decreased significantly with larger group sizes due to amortization. For a 16-hop path, it decreased from 0.73 μs (m=2) to 0.15 μs (m=16), representing a 4.87x speedup. Even the worst-case Symphony (m=2, 0.73 μs) was 3.78x faster than EPIC (2.76 μs) on a 16-hop path, and with m=16, Symphony was an impressive 18.40x faster than EPIC.
• Throughput and Goodput: Symphony consistently yielded higher throughput. For 1,000-byte payloads on a 16-hop path with m=16, Symphony achieved 6.11x higher throughput than EPIC, reaching up to 9.19 Gbps on a single-core machine for a 2-hop path. Goodput similarly saw a 6.56x increase over EPIC for the same configuration.
• Sensitivity to Mixed Packet Size: Symphony demonstrated robustness to heterogeneous traffic, with performance trends for throughput and goodput remaining similar to those with uniform packet sizes, as processing time primarily depends on header fields.
• Multi-core Acceleration: On the local server, Symphony effectively leveraged multi-core architectures. With 3-4 cores allocated, throughput reached the upper bound of the 10 Gbps link, showcasing its scalability. For a 4-hop path, 1,000-byte payloads, and m=8, throughput accelerated from 5.68 Gbps (one core) to 8.06 Gbps (two cores).
• Packet Loss and Reaggregation (Symphony-PR): While standard Symphony is more sensitive to packet loss (e.g., 7.73% throughput reduction at 1% loss with m=8), it still outperforms EPIC even at practical high loss rates (e.g., 10%). Symphony-PR further enhanced resilience, yielding 5.50x higher throughput than standard Symphony at a 45% packet loss rate, proving its effectiveness in highly disruptive environments and outperforming EPIC under severe loss.

These extensive evaluation results unequivocally demonstrate Symphony's superior performance and practical viability as a scalable and secure path validation solution for future Internet architectures.

Defensive Implications

▶ Watch: Symphony's core innovation: Aggregate validation paradigm (6:00)

Symphony's aggregate validation paradigm offers profound implications for network defenders, significantly enhancing the security posture against various network attacks and misconfigurations:

• Early Detection and Mitigation of Path Deviations: The core principle of hop-wise validation ensures that mis-forwarded packets—whether due to malicious rerouting, incorrect ordering, or packet alteration—are detected and discarded at the first dishonest hop. This drastically minimizes the window of attack, prevents resource waste on compromised paths, and limits the potential impact of an attack compared to solutions that only verify at the destination.
• Enhanced Data Integrity and Authenticity: The DataHash field, calculated over the concatenated payloads of an entire group and signed into the SymphonyProof, provides strong group-wise integrity. Any malicious modification to packet payloads within a group will immediately invalidate the DataHash, leading to detection and discard. This offers a higher level of payload integrity assurance than traditional network mechanisms.
• Robust Replay Attack Prevention: The inclusion of a Timestamp, signed into the SymphonyProof, effectively prevents replay attacks. Even if an attacker captures and retransmits a valid group of packets, the outdated timestamp will cause verification to fail, ensuring the freshness of traffic.
• Stronger Cryptographic Proofs: Unlike state-of-the-art solutions like EPIC that compromise security by embedding partial proofs (e.g., 5 bytes per hop), Symphony provides full, unforgeable cryptographic proofs based on CBC MAC with AES-128. This significantly raises the bar for attackers, making proof forgery computationally infeasible (probability of forging is negligible, e.g., 2^(-128(n+1))). The O(m) complexity for an attacker to forge an entire group's proof further strengthens this defense.
• Indirect DDoS Resistance: While not its primary design goal, Symphony inherently contributes to DDoS resistance by discarding malformed or tampered packets at the earliest possible stage. Packets with invalid proofs consume minimal processing resources before being dropped, preventing resource exhaustion attacks that rely on injecting high volumes of subtly altered packets. Furthermore, routers generating excessive invalid proofs can be identified as suspicious, aiding in incident response.
• Scalable Security Deployment: The ability of Symphony to amortize cryptographic overhead across packet groups allows for the deployment of strong path validation mechanisms at very high network speeds (demonstrated up to 9.19 Gbps on a single-core, and saturating 10 Gbps with multi-core acceleration). This makes robust path validation a practical reality for future high-speed Internet infrastructures, where traditional packet-wise approaches would be prohibitive.
• Resilience in Disruptive Environments: The Symphony-PR (Packet Reaggregation) mechanism provides crucial resilience in networks experiencing high packet loss rates. By allowing intermediate routers to re-aggregate and re-transmit only lost packets, Symphony-PR ensures that secure path validation can continue even under challenging network conditions, preventing complete service disruption and maintaining the security guarantees. The use of signed bindings and unforgeable fields in Symphony-PR protects against untrusted re-aggregation.

In essence, Symphony provides network defenders with a powerful, efficient, and scalable tool to enforce network path integrity, detect deviations early, and maintain high confidence in the authenticity and integrity of traffic flowing through their infrastructure, moving towards a more secure and trustworthy Internet.

Key Takeaways

• Aggregate Validation Paradigm: Symphony introduces a novel paradigm of aggregate validation, processing groups of packets as a single unit for cryptographic proof computation, which fundamentally improves efficiency by amortizing overhead.
• Superior Performance: Symphony significantly outperforms state-of-the-art packet-wise solutions like EPIC, achieving up to 18.40x faster router processing and 6.11x higher communication throughput while maintaining strong security.
• Uncompromised Security: The system upholds critical security guarantees, including proof unforgeability (using CBC MAC with AES-128) and hop-wise validation, effectively defending against active Dolev-Yao attackers and various packet manipulation attacks.
• Hardware-Optimized Design: Specialized SRAM-based router-queue logic is crucial for efficient packet aggregation and reordering in hardware routers, minimizing overhead and enabling high-speed processing.
• Resilience to Packet Loss: Symphony-PR (Packet Reaggregation) enhances the system's resilience to high packet loss rates by enabling intermediate reaggregation, allowing for continued secure forwarding even in disruptive network conditions.
• Practical Scalability: Implemented with DPDK and leveraging Intel AES-NI, Symphony demonstrates practical scalability, capable of saturating 10 Gbps links with multi-core acceleration, making it a viable solution for future high-speed Internet architectures.

About the Speaker(s)

Anxiao He is the speaker who presented the work "Symphony: Path Validation at Scale" at the NDSS Symposium. No further biographical details were provided in the transcript or metadata.