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

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

The Price of Auditing a Firewall: Query Complexity of Black-Box Verification for Listed-Rule and Tree-Rule Policies

Thawatchai Chomsiri, Suwichai Phunsa
Journal of Cybersecurity and Privacy
Network Packet Processing and Optimization
article

The Price of Auditing a Firewall: Query Complexity of Black-Box Verification for Listed-Rule and Tree-Rule Policies

Thawatchai Chomsiri, Suwichai Phunsa
article en

Abstract

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.

Journal of Cybersecurity and PrivacyVol. 6(6)
Mahasarakham University
Network Packet Processing and Optimization
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon