✓ Human-authored analysis; AI used for formatting and proofreading.
"Can this principal read that bucket?"
Five documents get a vote: the identity policy attached to the principal, the trust policy on every role it can assume, the Service Control Policy on the account, the permission boundary if one exists, and the bucket policy on the resource. Six, if a VPC endpoint policy sits on the network path. Read each one in isolation and each one is unremarkable. Your scanner reads each one in isolation. That is the whole problem: the finding that matters is not in any of the five documents. It lives in their composition and composition, in AWS, is recursive.
Two claims from earlier pieces set this up. First: AWS configuration is first-order logic. Every policy statement is a quantified predicate over requests and engineers misread it procedurally, as a sequence of grants. Second: control planes act locally; each service evaluates its own slice, and no layer reasons across subsystems. Put those together and you get the gap this article closes. Even if you modeled every policy perfectly, one document at a time, you still could not answer the question above. The obstruction is expressiveness.
The question a scanner cannot state
Role assumption is an edge:
canAssume(dev-role, ci-role). Edges chain. A assumes B, B assumes C, C holds the permission. The effective identity of a principal is everything reachable from it. The reflexive-transitive closure of canAssume. Transitive closure has a famous property: Aho and Ullman proved in 1979 that no relational-algebra query or first-order query can compute it. Twenty years later, SQL:1999 conceded the point and bolted on WITH RECURSIVE.
A scanner is a SELECT statement. A privilege-escalation chain is a WITH RECURSIVE.
This is why a tool architected as per-resource checks with read a configuration object, apply a predicate, emit pass or fail can accumulate ten thousand checks without once stating the reachability question. The formalism the checks are written in cannot contain the question. And it sharpens the first-order-logic claim from the earlier piece: a single policy is first-order; effective access is first-order plus a fixpoint. The engineers were already misreading the logic. The tools cannot even hold it.
Datalog in ninety seconds
Datalog is Horn-clause logic with no function symbols, evaluated to a least fixpoint over a finite set of facts. Three consequences fall out of that restriction: every program terminates, evaluation is polynomial in the size of the data, and recursion, the one thing first-order queries lack is native.
// facts, extracted from the observation snapshot .decl principal(p: symbol) .decl canAssume(p: symbol, r: symbol) // effective identity: reflexive-transitive closure .decl actsAs(p: symbol, r: symbol) actsAs(P, P) :- principal(P). actsAs(P, R) :- actsAs(P, Q), canAssume(Q, R). Two rules. Every chain, at every depth, for every principal in the estate, simultaneously. There is no loop to bound, maximum depth to pick or worklist to manage. The engine computes the closure and hands you the relation.
Harrison, Ruzzo, and Ullman proved in 1976 that the general safety question: "can this subject ever acquire this right?" is undecidable for unrestricted protection systems. Lipton and Snyder showed a year later that constraining the rewrite rules (the take-grant model) makes the same question decidable in linear time. Datalog's function-free restriction is that trade made executable: give up the ability to construct unbounded new terms, and safety becomes not just decidable but cheap.
Notice also the inversion of authorship. Procedural code enumerates instances: check this pattern, then that one. A Datalog rule defines a property, and the engine enumerates every instance for you, including the ones no incident report has taught you to look for. You state what must not exist; the engine returns either emptiness or every counterexample, each with its derivation attached. That is "don't trust the author, check the invariant," compiled.
Deny is negation and negation is where procedural engines drift
AWS's documented evaluation semantics are unambiguous: an explicit deny overrides any allow; SCPs intersect with everything below them; permission boundaries intersect again; cross-account access requires an allow on both the identity side and the resource side. The important phrase is allowed unless denied with logical negation.
Procedural engines handle deny-override as a special case bolted onto an allow loop, and special cases drift as coverage grows. In Datalog it is a negated atom:
.decl denied(p: symbol, a: symbol, r: symbol) denied(P, A, R) :- actsAs(P, Q), denyStmt(Q, A, R). .decl permitted(p: symbol, a: symbol, r: symbol) permitted(P, A, R) :- actsAs(P, Q), allowStmt(Q, A, R), inAccount(Q, Acct), scpPermits(Acct, A), !denied(P, A, R). Simplified shipped encoding also carries permission boundaries, session policies, and the same-account OR / cross-account AND semantics between identity and resource policies.
Datalog imposes one soundness condition on negation: it must be stratified. The denied relation has to be fully computed before any rule consults !denied. That requirement happens to be the exact shape of AWS's own documented order. The deny layer closes before the allow layer reads it. When the solver's correctness condition and the vendor's semantics coincide, you are not simulating the cloud's logic. You are expressing it.
Cross-coupling is one more atom in the body
In "It Worked Yesterday" I argued that the failures which survive review live in cross-coupling. IAM composed with network, network composed with data classification. Because each control plane is individually sound and nobody owns the join. In a procedural architecture, every pairing is an integration project: a new module, new plumbing, O(k²) seams for k domains. In Datalog, a pairing is a conjunction:
.decl finding(p: symbol, r: symbol) finding(P, R) :- permitted(P, "s3:GetObject", R), netPath(P, R), sensitive(R), !trusted(P). One added atom netPath and the IAM closure is joined with the network closure. This is the edges-not-nodes thesis made operational. Risk lives in interactions between settings, and a language whose only verb is the join is a language whose native subject is interaction.
Grading falls out as well. A derivation with every edge present is exploitable now; a derivation missing one edge is one act of drift away. Stave's exploitable / one-away / reachable classification is a query over path structure.
Why Soufflé
Datalog is a language; Soufflé is the engine that made it industrial. Built at Oracle Labs a decade ago to synthesize program analyzers, it compiles rules to parallel C++ with semi-naive evaluation, automatic index selection rather than interpreting them. Its home turf is program analysis: the DOOP points-to framework for Java, GrammaTech's DDISASM binary lifter, the Gigahorse Ethereum decompiler. Points-to analysis as our problem wearing different clothes. What can this pointer reach through arbitrary chains of indirection is structurally what can this principal reach through arbitrary chains of assumption.
Those workloads run to billions of tuples. An AWS estate, even one carrying a hundred thousand policy statements produces a fact base that is small by Soufflé's standards, and the full fixpoint computes in seconds on commodity hardware. Seconds matter: that is CI-gate budget. Mechanical verification only changes behavior if it fits inside the pipeline where the behavior lives.
Prior art already voted
Batfish expressed router control-plane semantics as Datalog rules in 2015. Microsoft built Network-Optimized Datalog into Z3 to check reachability beliefs about Azure's network. AWS split the problem where this article splits it: Zelkova compiles a single policy to SMT and asks what that one document means, while Tiros, the engine behind VPC Reachability Analyzer, specified network semantics against three solver backends: MonoSAT, Vampire, and Soufflé. SMT for the semantics of one artifact. Datalog for the closure over many.
Stave keeps both lanes, and adds a check on the checkers. The same observation snapshot exports as SMT-LIB for Z3 and cvc5 and as Datalog relations for Soufflé, and trap-triplet differential tests run the engines against each other. Zero disagreements to date. "Don't trust the author" applies to engine authors too.
What Datalog cannot do and where that work goes
Datalog joins finite relations. It does not do string algebra or arithmetic, and IAM is full of both: ARN wildcards, aws:SourceIp CIDR containment, aws:PrincipalOrgID comparisons. Two placements exist for that work. Resolve it at fact extraction. Stave's collectors expand a wildcard against the resource inventory and emit concrete edges, so the model gets bigger while the logic stays pure. Or route it to SMT, where strings and bitvectors have real decision procedures. Multi-engine verification means choosing per-condition. It is a routing decision.
The proof is over the observation snapshot. Model fidelity is the collectors' burden; point-in-time is the snapshot's nature; drift between snapshots is its own problem and its own article. Dijkstra's line of testing shows the presence of bugs, never their absence applies verbatim to scanning: a list of findings tells you what was caught. A fixpoint over a complete fact base is different in kind. It is an absence proof, relative to the model. The relativity is the boundary of the claim, and why verification lives or dies in collector completeness.
The division of labor
Stave owns everything that touches the world: the collectors, the observation snapshot as a reproducible artifact, the normalization of AWS JSON into typed facts, the control catalog, findings with provenance, and the bridge that turns Soufflé derivations back into evaluations you can gate a pipeline on. Soufflé owns one thing: the fixpoint. Facts and a property go in; the closure and its counterexamples come out. Neither is useful alone.
Against Bishop Fox's IAM Vulnerable lab, the reachability engine finds 30 of 30 documented privilege-escalation paths. Every one of those thirty is a chain. They are not visible as a fact about a single resource.
"Is port 22 open?" is a fact that is answered by lookup, blind to composition, aging as fast as the incident corpus that motivated it. "Does any path exist from an untrusted principal to a sensitive resource, through any composition of assumption, permission, and network?" is a property that is answered by closure, covering configurations no postmortem has named yet. The property is always smaller than the enumeration: two rules for reachability, against thousands of lines that hand-walk the same graph. And the two rules are the version you can read, dispute, and check.
The rules are in the repo. Don't trust the author. Run the closure.
Stave is an open-source Risk Reasoner: AWS security findings from configuration snapshots you already have without credentials. It finds the compound attack paths that single-resource scanners miss. The Soufflé reachability engine described here ships in the repo: stave.
