Pryde: A Modular Generalizable Workflow for Uncovering Evasion Attacks Against Stateful Firewall Deployments

Pryde: A Modular Generalizable Workflow for Uncovering Evasion Attacks Against Stateful Firewall Deployments

Speakers: Soo-jin Moon, Milind Srivastava, Yves Bieri, Ruben Martins, Vyas Sekar

Conference: IEEE S&P

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

Overview

In the realm of network security, stateful firewall deployments are a cornerstone, designed to protect internal networks from external threats by enforcing strict access policies. However, as presented by Milind Srivastava and his co-authors in their IEEE S&P talk, these critical defenses are susceptible to evasion attacks stemming from subtle, often overlooked bugs within their complex packet processing logic. The talk introduces Pryde, a novel, black-box framework engineered to systematically discover these elusive evasion attacks, providing a much-needed capability for both network operators and firewall vendors.

The significance of Pryde lies in its ability to operate without access to the firewall's internal code or configuration rules, a common scenario in real-world deployments. It addresses the formidable challenges posed by the vast diversity of commercial firewalls and internal host operating systems, as well as the intricate interactions within complex network topologies that might include insider threats. By demonstrating successful evasion against multiple commercial firewalls, Pryde underscores a critical gap in current security testing methodologies and offers a proactive solution to fortify network perimeters against sophisticated adversaries.

Pryde’s innovative approach combines a deployment-aware perspective with a modular and model-guided workflow. Instead of treating the firewall in isolation, it considers the entire network context, including potential insider threats and victim host behaviors. This allows for the generation of highly targeted and effective evasion attacks, revealing vulnerabilities that traditional testing methods often miss. The research not only exposes significant security flaws but also provides a robust framework for continuous security validation in an ever-evolving threat landscape.

Background

▶ Watch: Introduction to evasion attacks against firewalls (0:00)

The premise for Pryde stems from a fundamental challenge in network security: while firewalls are ubiquitous and essential for protecting internal networks, their complex internal logic can harbor subtle vulnerabilities that attackers can exploit to bypass their defenses. A common deployment scenario involves a firewall separating a Local Area Network (LAN) from a Wide Area Network (WAN), with rules configured to block external access to internal hosts. For instance, a typical rule might allow only TCP connections initiated from the internal network to the external network, dropping all other inbound connections.

However, even with seemingly robust rules, an attacker on the external network, possessing no knowledge of the firewall's code or specific rule set (a black-box access scenario), can craft specific TCP packets that exploit subtle bugs in the firewall's stateful packet processing. This can lead to an evasion attack, where malicious data successfully reaches a protected internal host. The talk illustrated this with a concrete example: a critical victim server, potentially running an older, vulnerable operating system, is expected to be protected by the firewall. An insider threat, such as a low-security IoT device compromised by a Mirai-like attack, exists within the internal network. While segregated by VLANs from the victim, this insider can spoof packets as the victim, sending them towards the firewall. This complex interplay of attacker capabilities, network topology, and victim characteristics presents a fertile ground for evasion.

Several factors make finding these evasion attacks exceptionally challenging:

1. Black-box access: Attackers and, often, security researchers lack access to the firewall's proprietary code or internal configuration, necessitating external testing methods.
2. Firewall diversity: The market offers a vast array of firewalls, each with unique implementations of TCP/IP stack logic and state management, meaning an attack effective against one firewall may fail against another.
3. Host diversity: Internal networks host a variety of operating systems (e.g., older Ubuntu, CentOS, Tiny Linux) and networking stacks, each responding differently to various packet sequences, further complicating attack generation.
4. Deployment complexity: The interaction between the firewall, diverse internal hosts, and potential insider threats (e.g., spoofing capabilities) creates a large attack surface that traditional tools struggle to model.

Prior work has attempted to address aspects of network security but falls short in this specific domain:

• Firewall rule testing focuses on validating configured rules, often requiring white-box access and failing to test the firewall's actual packet processing behavior.
• Censorship circumvention techniques are primarily designed to bypass content filters, not the strict, default-drop semantics of stateful firewalls.
• Code analysis tools require white-box access, which is impractical for proprietary firewalls.
• Protocol fuzzing typically assumes simple client-server models and lacks the generalizability needed to account for complex deployments involving multiple hosts and insider threats.
• Automata learning approaches often fail to model firewall responses to non-TCP compliant packets, which are precisely the kind of packets used in evasion attacks.

Pryde was developed to overcome these limitations, offering a comprehensive and systematic solution for uncovering these critical vulnerabilities.

Key Findings

▶ Watch: Key challenges in discovering evasion attacks (2:50)

Pryde's research yielded several critical findings that highlight the pervasive nature of evasion attacks and the unique challenges in identifying them:

1. Systematic Discovery of Evasion Attacks: Pryde successfully identified evasion attacks against all four popular commercial firewalls evaluated, including one open-source and three closed-source appliances. This demonstrated its effectiveness in real-world scenarios, where traditional methods had proven ineffective. The attacks allowed malicious data to reach a victim server and, in many cases, even enabled the victim's TCP ACK response to be forwarded back to the attacker, providing crucial feedback on attack success.

1. Lack of Attack Generalizability: A significant finding was that successful attacks against one firewall rarely generalized to others. This was observed for both concrete PCAP attacks (less than 10% generalizability) and even symbolic attacks (only a small percentage generalized). This underscores the fact that evasion attacks are highly specific to a firewall's unique implementation details and internal logic, reinforcing the need for tailored, firewall-specific testing frameworks like Pryde.

1. Discovery of Idiosyncratic Firewall Behavior: In the process of finding attacks, Pryde uncovered unique and often surprising idiosyncratic firewall behaviors:

• Proactive RST spoofing: Firewall 1 was observed proactively spoofing reset (RST) packets and sending them to hosts, which likely contributed to Pryde finding fewer successful attacks against it. This aggressive behavior effectively thwarts certain attack sequences.
• Permissive ACK handling: Firewall 3 exhibited a highly permissive behavior, allowing an ACK packet in any direction without any preceding SYN packet. This unexpected leniency significantly increased the number of successful attacks found against it.
• Persistent TCP state after RST: A common theme across multiple firewalls was that even after a RST packet was sent, the TCP connection state was not fully torn down, allowing subsequent packets to pass through. This bug is a critical enabler for many evasion techniques.

1. Vulnerability Disclosure and Vendor Response: The disclosure process revealed varied responses from vendors:

• Firewall 1's vendor requested testing against a newer version, which showed more aggressive RST spoofing, thwarting some attacks.
• Firewall 2's vendor acknowledged the initial report but did not follow up.
• Firewall 3's vendor enabled a default setting for strict TCP session handling, which successfully mitigated some of the discovered attacks. This highlights the importance of proper configuration.
• Firewall 4's vendor also requested testing against a newer version, against which Pryde still found successful attacks.

These findings collectively emphasize the complexity of stateful firewall deployments and the critical need for systematic, black-box testing to uncover subtle yet exploitable vulnerabilities. Pryde demonstrates that relying solely on default configurations or generic security practices is insufficient to guard against sophisticated evasion attacks.

Technical Deep Dive

▶ Watch: Pryde's deployment-aware and modular approach (5:20)

Pryde's power lies in its modular, deployment-aware, and model-guided workflow, designed to overcome the challenges of black-box access and system diversity. The overall process takes a black-box firewall appliance as input and, through a series of stages, generates concrete, executable evasion attacks.

The workflow begins with the operator specifying the network configuration (IPs, subnets), a detailed deployment model (e.g., an insider in VLAN 2 can spoof victim IPs), an attacker goal (defined by an SMT constraint and a success criterion), and an optional victim model (e.g., older Ubuntu netcat server) to prune the search space.

The core of Pryde consists of three main modules:

1. Firewall Model Inference

This module is responsible for inferring a model of the black-box firewall's behavior.

• Input: A black-box firewall appliance and a defined input alphabet. The input alphabet describes the set of TCP packets that can be sent to the firewall (e.g., a SYN packet from internal to external, an ACK packet from external to internal).
• Output: An ensemble of firewall models, each represented as a Finite State Machine (FSM).
• Key Insight: Naively reasoning about all possible adversarial TCP attacks leads to scalability issues. Pryde addresses this by considering different input alphabets, each encoding a specific type of evasion capability. This allows Pryde to infer an ensemble of more manageable FSMs, rather than a single, overly complex one.
• Methodology: Each FSM models state transitions based on incoming packets and describes the firewall's output (e.g., forwarding a packet to its destination host or dropping it). This black-box inference process systematically probes the firewall with various packet sequences and observes its responses to build a behavioral model.

2. Symbolic Attack Generator

Once the firewall models are inferred, this module generates abstract representations of potential evasion attacks.

• Input: The ensemble of firewall models, facts about the network deployment, the victim model, and the operator-specified attacker goal.
• Output: A set of symbolic attacks. Each symbolic attack is a high-level representation of a sequence of TCP packets, specifying only essential details like data presence, TCP flags (SYN, ACK, RST, FIN), and the sender/receiver. It does not yet include concrete sequence or acknowledgment numbers.
• Key Insight: Generating symbolic attacks can produce many semantically equivalent sequences. To avoid redundant exploration, Pryde adds a constraint to the SMT solver that ensures only semantically distinct symbolic attacks are generated.
• Methodology: All inputs (firewall models, deployment facts, victim model, attacker goal) are converted into SMT constraints. These constraints are then fed into an SMT solver, which identifies sequences of packets that satisfy the attacker's goal while adhering to the inferred firewall and deployment behaviors. The SMT solver effectively explores the vast state space to find potential evasion paths.

3. Concrete Attack Generator

The symbolic attacks, being abstract, cannot be directly played out on a network. This module translates them into executable packet captures.

• Input: The set of semantically distinct symbolic attacks.
• Output: Concrete PCAPs (packet capture files) that can be replayed on the network. Each PCAP contains a sequence of packets with fully specified sequence and acknowledgment numbers.
• Challenge: Setting sequence and acknowledgment numbers correctly is crucial for TCP communication, but exploring the entire space of possible numbers is computationally prohibitive. Conversely, being too strict in dependence limits the exploration of evasion opportunities.
• Key Insight: Pryde maintains a loose dependence between the sequence and acknowledgment numbers of different packets. This allows for a broader exploration of the sequence/ACK space while still generating valid TCP flows.
• Methodology:

1. A dependency graph is created where each node represents a symbolic packet, and an arrow denotes a dependency of one packet's sequence/ACK number on another's.
2. This graph is then pruned to a spanning tree.
3. A set of heuristic strategies is applied to assign concrete sequence and acknowledgment numbers:

• TCP compliance strategy: Aims to maintain strict TCP compliance in assigning numbers, useful for baseline attacks.
• Random strategy: Assigns sequence and ACK numbers randomly, exploring non-compliant or unexpected behaviors.
• Delta step strategy: Assigns numbers based on the previous packet's numbers plus a small, fixed delta (e.g., +1, +2, +10), which can exploit off-by-one errors or specific windowing logic.

At the culmination of this workflow, Pryde produces a set of concrete PCAP files that can be directly played out on a network to test for successful evasion against the defined attack success criteria. This systematic and multi-stage process enables Pryde to uncover subtle vulnerabilities that evade traditional detection methods.

Demo / Proof of Concept

▶ Watch: Overview of the Pryde workflow modules (6:45)

The talk effectively demonstrated Pryde's capabilities by walking through a concrete evasion attack found against an anonymized commercial firewall (referred to as "firewall 2"), protecting a victim host running an older version of Ubuntu. The attack scenario involved a sophisticated interplay between an external attacker and an internal insider threat.

The attack sequence unfolded as follows:

1. Insider Initiates Spoofed SYN: The attack begins with an insider, located in the internal network (VLAN 2), sending a spoofed SYN packet towards the firewall. This packet uses the victim's IP address as its source, effectively punching an initial hole in the firewall's defenses by manipulating its state table.
2. Attacker Sends SYN: With the firewall's state now manipulated, the external attacker sends a SYN packet directly towards the victim. The firewall, due to the previous spoofed packet, incorrectly allows this SYN to pass through.
3. Victim Responds with SYN/ACK: The victim host, receiving the SYN, responds with a SYN/ACK packet, acknowledging the connection attempt.
4. Attacker Sends Confusing SYN/ACK: To further confuse the firewall and potentially disrupt its state machine, the attacker then sends another SYN/ACK packet back to the victim.
5. Victim Responds with RST: The victim, receiving an unexpected SYN/ACK in its current state, responds with a RST (reset) packet, attempting to tear down the connection.
6. Evasion of Malicious Data: Crucially, at this point, one would expect the firewall to have fully torn down the TCP connection state and block any further packets between the attacker and victim. However, Pryde discovered that the attacker was still able to send malicious TCP data through the firewall to the victim.
7. Victim Acknowledges Malicious Data: The victim host, despite the preceding RST, received and acknowledged this malicious data with an ACK packet, confirming the successful evasion.

This sequence exemplifies a successful evasion attack, where the firewall, despite its configured rules and the presence of a RST packet, failed to prevent the delivery of malicious content.

In its evaluation, Pryde was tested against four popular commercial firewalls (one open-source, three closed-source) using 10 distinct input alphabets to generate firewall models. These models were then used to generate attacks against four diverse victim servers: a CentOS host running a Telnet server, a Tiny Linux host with an HTTP server, and two older versions of Ubuntu running Netcat servers. Pryde successfully found attacks against all four commercial firewalls, whereas prior art and state-of-the-art solutions were ineffective. Even when the success criteria were made stricter, requiring the victim's TCP ACK to be forwarded back to the attacker (providing crucial feedback), Pryde still found successful attacks against three of the four firewalls. This comprehensive demonstration underscores Pryde's robustness and its ability to uncover deep-seated vulnerabilities across a range of real-world firewall implementations.

Defensive Implications

▶ Watch: How an operator uses Pryde in practice (8:00)

The findings presented by Pryde have profound defensive implications for both firewall vendors and network operators. The demonstrated ability to systematically uncover evasion attacks against commercial firewalls necessitates a re-evaluation of current security practices and testing methodologies.

For firewall vendors, Pryde offers a powerful, black-box testing framework that can be integrated into their development and quality assurance pipelines. Vendors should:

• Proactive Vulnerability Testing: Utilize Pryde to proactively test new firewall versions and patches before deployment. This ensures that existing evasion vulnerabilities are mitigated and that no new ones are inadvertently introduced.
• Post-Patch Validation: After applying security patches, Pryde can be used to validate their effectiveness, ensuring that the underlying idiosyncratic firewall behaviors exploited by evasion attacks have truly been addressed.
• Enhance TCP Session Handling: The discovery that some firewalls fail to fully tear down TCP state after a RST packet, or allow ACKs without preceding SYNs, points to fundamental flaws in TCP state machine implementation. Vendors should prioritize hardening their TCP session handling logic to strictly adhere to protocol specifications, especially in edge cases and error conditions. The example of Firewall 3 enabling a default setting for "strict TCP session handling" highlights a concrete step that can be taken.

For network operators, Pryde provides a means to assess the actual security posture of their deployed firewalls in their specific network environments:

• Deployment-Specific Testing: Given that attacks are highly firewall-specific and depend on the overall deployment context, operators should use tools like Pryde to test their firewalls with their unique network configurations, victim hosts (including older OS versions), and potential insider threat scenarios. Relying on generic security certifications or vendor assurances alone is insufficient.
• Layered Defense: The fact that firewalls can be evaded means they should not be the sole line of defense. Operators must implement a layered defense strategy, including updated operating systems on internal hosts, endpoint detection and response (EDR) solutions, intrusion detection/prevention systems (IDS/IPS) behind the firewall, and network segmentation.
• Monitor for Anomalous Traffic: Security monitoring should look for unusual packet sequences, especially those that appear after a connection reset (RST) or involve unexpected ACK or SYN/ACK packets. These could be indicators of an ongoing evasion attempt.
• Regular Software Updates: While firewalls can have subtle bugs, ensuring all internal hosts run current, patched operating systems significantly reduces the attack surface, even if an evasion attack bypasses the firewall. The victim host in the demo running an "older version of Ubuntu" highlights this risk.

In essence, Pryde shifts the paradigm from simply configuring firewall rules to rigorously testing the firewall's actual behavior in the face of sophisticated, non-compliant traffic. It empowers defenders to move from a reactive stance to a proactive one, systematically identifying and mitigating vulnerabilities before they can be exploited by adversaries.

Key Takeaways

• Firewall security can be evaded by subtle bugs: Despite their critical role, stateful firewall deployments are susceptible to evasion attacks stemming from minute flaws in their packet processing logic, which are challenging to discover due to black-box access limitations.
• Pryde offers a novel, systematic approach: The framework introduces a deployment-aware, modular, and model-guided workflow to systematically uncover these complex evasion attacks against diverse commercial firewalls and network configurations.
• Pryde successfully identifies real-world vulnerabilities: The tool successfully found unique evasion attacks against all four commercial firewalls tested, demonstrating its effectiveness where prior solutions failed, and even under strict success criteria.
• Attacks are highly firewall-specific: A critical finding is that successful attacks against one firewall rarely generalize to others, emphasizing the need for tailored, firewall-specific testing rather than relying on generic attack patterns.
• Idiosyncratic firewall behaviors are common: Pryde revealed surprising behaviors such as proactive RST spoofing, permissive ACK handling, and the failure to fully tear down TCP state after a RST, which are key enablers for evasion.
• Proactive testing is essential for vendors and operators: Both firewall vendors and network operators can leverage Pryde to proactively test firewall implementations, validate patches, harden TCP session handling, and build more resilient network defenses against sophisticated evasion techniques.

About the Speaker(s)

The research behind Pryde was presented by Milind Srivastava from Carnegie Mellon University. He is credited as the primary presenter of this detailed technical work. The comprehensive nature of Pryde's development and evaluation also involved a team of distinguished co-authors: Soo-jin Moon, Yves Bieri, Ruben Martins, and Vyas Sekar. Their collective expertise contributed to the design and implementation of this novel framework for uncovering evasion attacks against stateful firewalls.