Firewalls and Packet Filtering

A firewall is a system, typically inline on the network path, that inspects traffic and decides — allow, deny, or transform — according to an access-control policy. The policy is expressed as an ordered list of rules, each rule matching on some tuple of packet attributes (source/destination IP, port, protocol, interface, TCP flags) and specifying an action. The firewall's job reduces to a well-defined decision procedure: given a packet, find the applicable rule and apply its action. Firewalls are classified by what information they use to decide. A stateless packet filter examines each packet in isolation — it has no memory of prior packets. A stateful filter additionally maintains a connection table: an entry per active flow (keyed by the 5-tuple: source IP, destination IP, source port, destination port, protocol) recording enough TCP or UDP state to recognize that an incoming packet is part of an already-approved conversation. An application gateway (proxy firewall) terminates the connection itself, speaks the application protocol on both sides, and can therefore filter on content — not just headers. These three sit on a stateless → stateful → application-aware spectrum, each layer adding semantic understanding at the cost of per-packet processing time and state that must be stored, aged, and defended against exhaustion. A DMZ (demilitarized zone) is not a filtering technique but a topology pattern: a network segment reachable from the internet, hosting only the services that must be public (web, mail relay, DNS), isolated by firewalls from both the internet and the internal LAN. The DMZ turns "one perimeter" into "two perimeters with an airlock in between," so that compromising the public web server does not automatically grant access to payroll and HR systems. This is Network Security Threats and Attack Models's defense-in-depth principle made concrete in network topology.

Stateless filtering. The firewall holds an ordered rule table. For each packet, it extracts the 5-tuple (and sometimes TCP flags, ICMP type, or interface) and scans the table top to bottom, applying the first matching rule — this is the standard semantics used by classic packet filters (e.g., traditional Cisco ACLs, early `ipfw`). If no rule matches, a default policy applies (commonly default-deny). ``` function STATELESS_FILTER(packet, rules[1..n], default_action): for i = 1 to n: if MATCHES(rules[i].pattern, packet): return rules[i].action # ALLOW or DENY return default_action # fallback, usually DENY function MATCHES(pattern, packet): return (pattern.src_ip covers packet.src_ip) and (pattern.dst_ip covers packet.dst_ip) and (pattern.proto == packet.proto or pattern.proto == ANY) and (pattern.src_port in pattern.src_port_range) and (pattern.dst_port in pattern.dst_port_range) and (pattern.flags subsetOf packet.flags or pattern.flags == ANY) ``` This is a linear scan: `O(n)` per packet for `n` rules in the naive case, though production firewalls compile rules into decision trees, tries, or bitmap-based classifiers (e.g., grid-of-tries, TCAM hardware in routers) to get closer to `O(log n)` or `O(1)`.

Stateful filtering. The firewall augments the above with a connection table `T`, keyed by a normalized 5-tuple, storing the TCP state (`SYN_SENT`, `ESTABLISHED`, `FIN_WAIT`, …) or a simple "seen" flag for UDP/ICMP pseudo-connections. Rules are still consulted, but only for the packet that initiates a new connection; subsequent packets belonging to a known connection are fast-pathed. ``` function STATEFUL_FILTER(packet, rules[1..n], T, default_action): key = NORMALIZE_5TUPLE(packet) # canonical direction-independent key if key in T: entry = T[key] if VALID_TRANSITION(entry.state, packet.flags): entry.state = NEXT_STATE(entry.state, packet.flags) entry.last_seen = NOW() if entry.state == CLOSED: remove T[key] return ALLOW else: return DENY # e.g. unexpected flag sequence

# No existing connection: consult static rules as for a NEW connection decision = STATELESS_FILTER(packet, rules, default_action) if decision == ALLOW and packet.is_connection_start(): # e.g. TCP SYN T[key] = new_entry(state = SYN_SENT, last_seen = NOW()) return decision

# Periodic housekeeping (runs independently) function REAP_STALE_ENTRIES(T, timeout): for key, entry in T: if NOW() - entry.last_seen > timeout: remove T[key] ``` The crucial property: a rule permitting outbound traffic to port 443 automatically and dynamically permits the matching inbound reply, without a static rule opening high ports inbound forever. This closes the "leave a permanent hole for return traffic" weakness of pure stateless filters.

Application gateways (proxies). Here the firewall is an endpoint, not a relay. The client connects to the proxy; the proxy, after inspecting/authenticating, opens its own connection to the real server and relays application-layer content, rewriting or blocking as policy dictates. ``` function APP_GATEWAY_HANDLE(client_conn, policy): request = PARSE_APPLICATION_PROTOCOL(client_conn) # e.g. full HTTP request if not policy.allows(request.method, request.url, request.headers, request.body): client_conn.send_error(403) return server_conn = OPEN_CONNECTION(request.destination) server_conn.send(request) response = server_conn.receive() if not policy.allows_response(response): client_conn.send_error(502) return client_conn.send(response) ``` Because the gateway fully parses the protocol, it can enforce rules a header filter cannot express — "no HTTP PUT," "strip this cookie," "block SQL keywords in query strings," "only allow FTP `RETR`, never `STOR`."

DMZ enforcement. Architecturally, two firewalls (or one device with three interfaces) create three zones: internet, DMZ, internal LAN. Policy is asymmetric and directional:

• internet → DMZ: allow only the specific service ports the public servers expose.
• DMZ → internal: default-deny, with narrow exceptions (e.g., web server may query one internal database port, nothing else).
• internal → internet: typically permissive outbound, filtered by proxy/gateway.
• internet → internal: default-deny, always.

This asymmetry is the point: even a fully compromised DMZ host has almost no rule granting it further reach.

Stateless filter complexity. With a naive linear scan, matching costs `Θ(n)` per packet for a table of `n` rules — every rule must potentially be examined until the first match (worst case: the match is the last rule, or there is no match at all and the default fires). Production systems compile the rule set once, at update time, into a classifier structure — a decision tree keyed on prefix bits (used in longest-prefix / grid-of-tries schemes) or a set of parallel bitmaps intersected per field — bringing per-packet lookup to `O(w)` where `w` is address width (effectively `O(1)` for fixed 32/128-bit fields), at the cost of `O(n log n)` or worse preprocessing time and `O(n)` to `O(n²)` space depending on the scheme. Hardware firewalls exploit TCAM (ternary content-addressable memory) to get true `O(1)` parallel matching in silicon, at higher unit cost and power draw.

Stateful filter complexity. Per-packet cost is `O(1)` expected time for the hash-table lookup into the connection table `T`, plus the `O(n)` (or accelerated) rule-table lookup only on the first packet of each new connection. Space is `Θ(c)` for `c` concurrent connections — this is the resource an attacker targets in a connection-table exhaustion attack (a variant of SYN flooding): each half-open connection consumes an entry until timeout, so an attacker can force `c` toward the table's capacity and cause legitimate new connections to be dropped. The `REAP_STALE_ENTRIES` timeout is a direct mitigation, trading state longevity (correctness of long-idle connections) against memory pressure.

Correctness argument for stateless filters — first-match semantics. Define the policy as a function `P: Packet → {ALLOW, DENY}`. The rule table is a finite ordered sequence `(pattern_i, action_i)`. The algorithm computes: ``` P(pkt) = action_k, where k = min{ i : MATCHES(pattern_i, pkt) } ``` and `default_action` if no such `i` exists. This is well-defined (the `min` exists over a finite nonempty-or-empty index set) and deterministic — the same packet always yields the same decision, an essential property for auditability. The subtlety, and the main source of real-world bugs, is that rule order is part of the specification: swapping two rules can change `P` for packets matched by both, because `MATCHES` is not required to be mutually exclusive across rules. A firewall administrator who reasons about rules as an unordered set of "policy statements" is reasoning about a different, wrong semantics; the correctness of a configuration must be checked against the ordered evaluation, e.g., by rule-anomaly analysis (detecting shadowing: rule `j > i` that can never fire because an earlier broader rule `i` already matches every packet `j` would match).

Correctness argument for the stateful transition system. Model each TCP connection as a finite-state automaton with states `{CLOSED, SYN_SENT, SYN_RCVD, ESTABLISHED, FIN_WAIT, CLOSED}` (mirroring the real TCP state machine). `VALID_TRANSITION` accepts a flag sequence only if it corresponds to an edge in this automaton (e.g., `ESTABLISHED --FIN--> FIN_WAIT` is valid; `CLOSED --ACK-only, no prior SYN-->` is invalid). This gives the firewall a soundness guarantee: any packet accepted for an existing connection corresponds to a state reachable by the standard TCP handshake protocol, so an attacker cannot inject a packet claiming membership in a connection without first observing or forging a consistent transcript of prior flags — this is exactly what defeats naive ACK-only spoofing attempts that a stateless filter (which sees only "TCP, port 443, ACK set" and blindly allows it because "acks are replies") would let through.

Tradeoffs, honestly stated.

• Stateless filters: fastest, simplest, easiest to reason about and audit; but blind to connection context, forcing either overly permissive static rules (open all high ports for replies) or broken functionality.
• Stateful filters: close that gap, but introduce a memory-bounded resource (the connection table) that becomes an attack surface, and add latency/complexity for protocols using dynamic ports (FTP active mode, SIP) requiring application-layer gateway helpers ("ALGs") bolted onto the stateful engine.
• Application gateways: strongest semantic guarantee, can enforce content policy no header-based device can express; but every protocol needs its own parser (maintenance burden, and a parsing bug becomes a security bug), and they add a full round-trip's worth of latency plus a scalability bottleneck since the proxy terminates every connection.
• DMZ topology: contains a compromise, but only if the DMZ→internal rules are genuinely minimal; a single overly broad rule ("DMZ can reach any internal port for troubleshooting") silently voids the entire architectural guarantee — this is not a mechanism failure but a policy-authoring failure, and it is the single most common real-world DMZ mistake.

Consider a small business firewall protecting a web server at `10.0.1.10` (mapped via NAT to public IP `198.51.100.4`) and an internal LAN `10.0.2.0/24`. Rule table (evaluated top to bottom, default deny):

Now trace four packets:

Packet A — external client `203.0.113.9:51000 → 198.51.100.4:443`, flag `SYN`. Scan: rule 1 matches (`dst=198.51.100.4`, `port=443`, `SYN` set) → ALLOW. A new connection entry is created: key `(203.0.113.9:51000, 198.51.100.4:443, TCP)`, state `SYN_SENT`.

Packet B — the server's SYN-ACK reply, `198.51.100.4:443 → 203.0.113.9:51000`, flags `SYN,ACK`. Normalized key matches the table entry from A. `VALID_TRANSITION(SYN_SENT, SYN|ACK)` holds (this is the expected second handshake step) → state advances to `SYN_RCVD` → ALLOW, without consulting the static rule table at all — notice this packet's direction is technically "outbound reply" but the stateful engine recognizes it as part of an already-approved flow.

Packet C — an attacker at `203.0.113.9` sends a bare `ACK` (no prior SYN observed by this firewall, e.g., a scan or an attempted ACK-flood) to `198.51.100.4:22` (SSH, no rule permits inbound SSH at all). No table entry exists for this 5-tuple. Falls through to static rules: none of rules 1–5 match (rule 1/2 require SYN and match only ports 443/80; port 22 matches nothing) → falls to default DENY. Note this packet is rejected twice over: no connection state, and no static rule — defense in depth even within one firewall.

Packet D — a packet claiming to be part of the connection from Packet A, `203.0.113.9:51000 → 198.51.100.4:443`, but with flags `ACK` only, arriving before Packet B ever occurred in the trace order (i.e., attacker races the handshake). `VALID_TRANSITION(SYN_SENT, ACK-only)` — is a bare ACK a valid follow-up to `SYN_SENT` state, with no `SYN,ACK` from the server yet observed? In a correctly implemented state machine, no — the automaton requires seeing the `SYN,ACK` transition first. Result: DENY, and depending on policy, the half-open entry may be flagged or purged. This is exactly the class of forgery a stateless filter (which only checks "TCP port 443, has ACK bit, not first fragment → looks like a legitimate reply") would have let through. The trace demonstrates the core lesson: identical header fields (Packets B and D both have plausible-looking flag combinations for "a reply") receive different decisions because the stateful engine consults history, not just the current packet — precisely the capability a stateless filter lacks by construction.

The packet filter concept grew directly out of early router access-control lists and the recognition, in the late 1980s, that perimeter enforcement needed a first-class abstraction rather than ad hoc router tweaks. Bell Labs researchers formalized the idea of a dedicated filtering gateway and coined much of the vocabulary — "screening router," "application gateway," "bastion host" — still used today. The stateful inspection model, patented and commercialized in the early 1990s, was the key conceptual leap: recognizing that tracking connection state, not just header fields, was necessary to reason about legitimate reply traffic without permanently opening inbound ports.

Firewalls sit in nearly every network boundary in production systems today. Cloud providers expose security groups and network ACLs (Amazon AWS, Google Cloud, Azure) that are, respectively, stateful and stateless packet filters attached to virtual machine instances and subnets — the exact mechanisms described above, reimplemented as software-defined policy objects. Enterprise perimeter firewalls (Cisco ASA, Palo Alto, Fortinet) combine stateful inspection with deep packet inspection and identity awareness, forming "next-generation firewalls." Web application firewalls (WAFs) are application-gateway descendants specialized for HTTP, parsing requests to block SQL injection and cross-site scripting patterns that no header filter could see. Home routers implement simplified stateful NAT/firewall combinations by default, silently protecting billions of consumer devices. DMZ design remains the standard blueprint for any organization exposing public services — web tiers, mail relays, VPN concentrators — while shielding databases and internal tooling. The same chokepoint principle underlies how organizations later layer Virtual Private Networks to extend a trusted perimeter over an untrusted network, and it forms the first line of defense examined in DDoS Attacks and Mitigation, where the connection-table and rate-limiting mechanisms discussed here become the target of volumetric and state-exhaustion attacks at internet scale.

Ask the tutor: How would you design a stateful firewall's connection-table eviction policy to resist exhaustion attacks while still supporting long-lived legitimate connections?