✓ Human-authored analysis; AI used for formatting and proofreading.
Your cloud security scanner tells you a finding exists. An SMT solver tells you why or proves the finding is impossible. This is a checklist vs a mathematical guarantee.
SMT-LIB is the international standard language for communicating with SMT (Satisfiability Modulo Theories) solvers. Z3, cvc5, or Yices are solvers that verify Intel processor designs and NASA flight software. SMT-LIB is a way to talk to them.
This article explains SMT-LIB, why it matters for cloud security, and how an open-source tool called Stave uses it to detect compound misconfigurations that no checklist scanner can find.
What is SMT-LIB
SMT-LIB provides three things:
A standard syntax. Based on S-expressions (Lisp-style parenthesized notation). Every SMT solver in the world reads the same format. Write once, verify with any solver.
Mathematical theories. Standardized ways to reason about strings (ARN matching, wildcard expansion), integers (port ranges, CIDR arithmetic), booleans (policy allow/deny), and arrays (permission sets). These theories make SMT solvers more powerful than simple SAT solvers. They understand the meaning of the data, not just true/false flags.
A logic hierarchy. You choose how expressive your logic needs to be. Quantifier-free boolean logic is fast but limited. Full first-order logic with strings and arithmetic is slower but can express questions like "does there exist any principal that can reach any resource containing PHI through any chain of role assumptions?"
Why Cloud Security Needs This
Every cloud security scanner on the market checks components one at a time:
- Is this bucket public?
- Is MFA enabled?
- Is this role overpermissioned?
Attackers don't check components. They check compositions. The Capital One breach exploited five configurations that each passed every individual check. The vulnerability was the interaction between them. A Cognito identity pool granting anonymous AWS credentials to a role that had S3 access to a bucket containing 100 million customer records.
No individual check catches this. The question to answer is: "Can an unauthenticated internet user reach confidential data through a chain of services?" That's a satisfiability question that SMT solvers are designed to answer.
Example: The Compound Chain
Here's SMT-LIB query when checking a cross-service attack chain. This is the query structure that runs against real AWS configuration snapshots.
First, Stave exports configuration facts as SMT-LIB assertions:
(set-logic ALL) ;; --- Asset declarations --- (declare-fun allows_unauthenticated (String String) Bool) (declare-fun maps_unauth_to (String String) Bool) (declare-fun has_action (String String) Bool) (declare-fun has_resource (String String) Bool) (declare-fun has_tag (String String) Bool) ;; --- Facts from the configuration snapshot --- (assert (allows_unauthenticated "arn:aws:cognito-identity:us-east-1:111122223333:identitypool/abc" "true")) (assert (maps_unauth_to "arn:aws:cognito-identity:us-east-1:111122223333:identitypool/abc" "arn:aws:iam::111122223333:role/AppUnauthRole")) (assert (has_action "arn:aws:iam::111122223333:role/AppUnauthRole" "s3:GetObject")) (assert (has_resource "arn:aws:iam::111122223333:role/AppUnauthRole" "arn:aws:s3:::sensitive-data/*")) (assert (has_tag "arn:aws:s3:::sensitive-data" "data_classification:confidential")) ;; --- Closed-world axioms (if a fact isn't asserted, it's false) --- (assert (forall ((x String) (y String)) (=> (allows_unauthenticated x y) (and (= x "arn:aws:cognito-identity:us-east-1:111122223333:identitypool/abc") (= y "true"))))) ;; (similar axioms for each predicate — omitted for brevity) These are facts only about the configuration. No rules or queries. Stave's job ends here.
Now, a separate query file asks the question:
;; Query: Can an anonymous user reach confidential data? (declare-const pool String) (declare-const role String) (declare-const action String) (declare-const resource String) ;; The pool allows unauthenticated access (assert (allows_unauthenticated pool "true")) ;; The pool maps to a role (assert (maps_unauth_to pool role)) ;; The role has an S3 action (assert (has_action role action)) ;; The role can access a resource (assert (has_resource role resource)) ;; The resource contains confidential data (assert (has_tag resource "data_classification:confidential")) (check-sat) (get-model) Run this through Z3:
$ cat facts.smt2 query.smt2 | z3 -in sat ( (pool "arn:aws:cognito-identity:us-east-1:111122223333:identitypool/abc") (role "arn:aws:iam::111122223333:role/AppUnauthRole") (action "s3:GetObject") (resource "arn:aws:s3:::sensitive-data/*") ) sat means the attack path exists. Z3 didn't just say yes. It named the specific pool, role, action, and resource that constitute the path. This is a constructive proof: the witness is the exploit.
Run the same file through cvc5 and Yices:
$ cat facts.smt2 query.smt2 | cvc5 --lang smt2 --finite-model-find sat $ cat facts.smt2 query.smt2 | yices-smt2 sat Three solvers from three independent institutions (Microsoft Research, Stanford/Iowa, SRI International) agree. This is a mathematical certainty.
Now apply the remediation. Set allow_unauthenticated_identities = false and re-export the facts. The allows_unauthenticated assertion disappears from the SMT-LIB file. The closed-world axiom forces it to false for all inputs. Run the same query:
$ cat remediated-facts.smt2 query.smt2 | z3 -in unsat unsat means the attack path is impossible. Not "we didn't find it." Impossible. Proven. The chain is broken at step one because no identity pool allows unauthenticated access.
Why This Matters: Facts vs. Rules
The critical architectural decision: Stave exports facts. External programs own rules.
The SMT-LIB file from stave export-sir --format smt2 contains only assertions that shows what the configuration looks like. The query file contains the question that you want to check. They're separate files. This means:
- You can write new queries without changing Stave
- You can run the same facts through different solvers
- You can share facts with your team while each person asks different questions
- The facts are reusable across any SMT-LIB-compatible tool
This is why Stave uses (set-logic ALL) instead of a restricted logic. It keeps the facts general enough for any query, and lets the solver determine the most efficient strategy.
The Modulo Theories Power
Standard SAT solvers understand only true and false. SMT solvers understand mathematical structures that model real-world concepts:
Theory of Strings: Does arn:aws:s3:::company-frontend-* match arn:aws:s3:::company-frontend-prod? Z3's string theory handles wildcard expansion, prefix matching, and ARN comparison natively. The Bybit breach pattern, a wildcard resource grant on production S3 buckets is a string satisfiability question.
Theory of Integers: Is port 8443 inside the range 8000–9000? Is a security group's ingress CIDR a subset of the VPC's CIDR? These are integer arithmetic questions that boolean SAT can't express.
Theory of Arrays: Does a role's effective permission set (after Allow minus Deny minus Permissions Boundary) include s3:PutObject? Array theory models sets of permissions.
Each theory adds reasoning power that's relevant to cloud configuration. The solver combines them automatically. A single query can use strings (ARN matching), integers (port ranges), and booleans (policy effects) together.
Solver Interchangeability
Because SMT-LIB is a standard, Stave doesn't depend on any single solver:
| Solver | Developer | Strength |
|---|---|---|
| Z3 | Microsoft Research | Fast general-purpose solving, strong quantifier handling |
| cvc5 | Stanford / Iowa | Powerful string theory, finite model finding |
| Yices | SRI International | Efficient for large quantified formulas |
The same .smt2 file works with all three. In practice, Z3 handles most cloud security queries sub-second. cvc5 cross-verifies. Yices provides a third independent confirmation. When all three agree, the answer is as certain as mathematics allows.
When they disagree, it is the most valuable signal. It means either the encoding has a bug (fix the encoder) or one solver found a corner case the others missed (investigate the query). In practice, disagreements have revealed encoding issues that would have been silent with a single solver.
How This Fits Into the Larger Pipeline
SMT-LIB is one of two export formats Stave produces. The other is JSONL (subject/predicate/object triples). Together they feed nine reasoning engines:
AWS snapshots → Stave normalization → stave export-sir --format jsonl → Soufflé, Clingo, Prolog, PySAT, Risk, TLA+, Game Theory → stave export-sir --format smt2 → Z3, cvc5, Yices Each engine answers a different kind of question from the same facts:
| Engine | Question | Format consumed |
|---|---|---|
| Z3/cvc5/Yices | Can this unsafe state exist? | SMT-LIB |
| Soufflé | How many paths are reachable? | JSONL |
| Clingo | What violations exist? | JSONL |
| Prolog | Why is this path reachable? | JSONL |
| PySAT | Which control combos are unsafe? | JSONL |
| Risk model | How likely is exploitation? | JSONL |
| TLA+ | How far from unsafe after fix? | JSONL |
| Game theory | What does the attack cost? | JSONL |
SMT-LIB handles the questions where you need mathematical proof: "can this state exist?" and "is this configuration safe?" JSONL handles everything else such as enumeration, counting, explanation and quantification.
This proof is valid within the scope of exported SIR facts; the Fact Export reference names which property domains the SIR currently covers.
The Business Impact
When a CISO asks "are we safe?" a checklist scanner says "you have 3 critical findings." An SMT solver says "there exists no assignment of principals, actions, and resources that violates your security invariants are proven by three independent solvers."
When an auditor asks "how do you know this control is effective?" you don't show them a screenshot. You show them the SMT-LIB assertion and the unsat result. It's a transparent, declarative record of the security logic that is readable, reproducible, and mathematically sound.
When a developer asks "will this change break security?" you run the proposed configuration through the same queries. If Z3 still returns unsat, the change is safe. If it flips to sat, the change created an attack path and the witness names exactly which path.
This is the shift from "finding bugs" to "proving safety." SMT-LIB is the language that makes the proof portable, verifiable, and solver-independent.
How this relates to existing compliance mods
The "finding bugs" vs "proving safety" distinction maps the two tool layers. Framework-coverage mods like turbot/steampipe-mod-aws-compliance are excellent finders of per-resource bugs. 540+ controls across CIS / PCI / HIPAA / NIST will report every public bucket, every missing-MFA user, every unrotated key the frameworks name. That's the auditor-grade bug-finding layer, and the mod's framework-breadth makes it useful for that job. SMT-LIB export turns Stave's compositional catalog into proofs over the same snapshot facts, unsat over the chain conditions means no assignment of principals + resources violates the invariant the chain encodes. Bug-finding for per-resource verdicts; proof-by-solver for compositional verdicts; both run against the same snapshot in the same pipeline. Comparison: aws-compliance-mod.
Stave is an open-source static analysis tool for cloud infrastructure. It evaluates configurations via CEL predicates and exports facts in JSONL and SMT-LIB for consumption by external reasoning engines. All analysis runs on air-gapped snapshots without cloud credentials. github.com/sufield/stave
