Auditing Through the API: Statistical Inference of Authorization Policies from Black-Box Observations

Abstract

Authorization bugs are among the most prevalent and dangerous classes of API vulnerabilities. A web service consists of a back-end, an API that mediates client interaction through HTTP endpoints, and an authorization policy that each endpoint invokes to decide whether to permit a request. Two bodies of work address these bugs from opposite sides: policy analysis tools verify whether intended policies hold, but cannot explain application behavior; black-box API security tools probe live APIs and find real bugs, but are coarse-grained and cannot attribute findings to a specific policy rules. In reality, the API acts as a lossy channel from authorization semantics to external observations, filtered through unobservable implementation choices. To our knowledge, no prior work has formalized this channel structure. Auditing whether an API enforces its intended policy requires resolving two unknowns: which endpoints check which rules (τ), and which response body fields reveal the system state those rules depend on (σ). The two are circularly dependent—estimating either requires the other—and the joint space is exponentially large. The key insight is that mutations, which change authorization relationships, produce evidence about both unknowns at once; and crucially, σ converges rapidly from this evidence, after which τ inference decomposes per-endpoint. What appears to demand joint search over an exponential space reduces to a fast sequential procedure. We formalize this in a Bayesian framework, prove convergence is guaranteed, and characterize which rules are structurally hard to audit from the outside. We evaluate the algorithm across ten scenarios spanning the full difficulty spectrum. The results confirm our theoretical predictions. On the cases with principal-level authorization conditions, it produces correct per-rule verdicts at ≥ 95% confidence and detects planted bugs with 100% precision and recall, with a 4× margin separating bugs from noise. Removing response body information often makes the inference problem impossible on ownership- and sharing-based scenarios, confirming that co-variation between response field changes and access pattern changes is essential. With resource-level conditions, all mutation strategies converge to the same structural ceiling; the theory predicts which action pairs will be unresolvable with high certainty before any probes are sent. Our framework characterizes not just what the algorithm can verify, but what any black-box auditor can know about an API’s authorization behavior.