Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Chomsiri et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: