The Price of Auditing a Firewall: Query Complexity of Black-Box Verification for Listed-Rule and Tree-Rule Policies
Firewalls are audited, reverse-engineered and tested by sending packets and observing whether they pass, yet the literature offers algorithms, not lower bounds. We formulate black-box firewall verification as a query-complexity problem in Angluin’s exact-learning framework, with oracles matched to what auditors and attackers observe: action-only queries, identity queries (hit counters or exact flow logs) and witness packets from captured traffic. We prove that the contents of shadowed rules are invisible to every black-box observer; that without side information even a single-rule policy on the IPv4 5-tuple needs 2104 − 1 probes; and that with one witness per rule and identity feedback, a Tree-Rule policy whose m leaves the identity oracle names is reconstructed with (m − 1)(logW + d) + 2m probes (m equals the minimal-tree size when the deployed tree is minimal), with the number d of header fields entering only additively, against the bound 2n · Σ logWj + n for a disjoint list of n rules. A fixed certificate of 3m − 2 packets is complete against structural misconfigurations, and N traffic samples bound the expected reconstruction error by m/(eN). Exact simulations and a real iptables testbed give results consistent with the bounds, and 16 production-derived rule sets show how policy structure drives the cost: for three host and container policies the tree needs 13–26 times fewer probes than the bound for a disjoint list of the same size, whereas cross-product policies inflate the tree by up to 83×, making overlapping rule lists the central open problem.
Authors
- Thawatchai Chomsiri (ORCID: https://orcid.org/0000-0001-5998-9376)
- Suwichai Phunsa (ORCID: https://orcid.org/0000-0003-1093-6999)
Publication Details
- Journal
- Journal of Cybersecurity and Privacy
- Published
- 2026-11-17
- DOI
- https://doi.org/10.3390/jcp6060207
- Primary Topic
- Network Packet Processing and Optimization
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Mahasarakham University