How automated reasoning with Dafny and TLA+ reduces review burden, catches subtle bugs, and gives you a principled way to resist the pressure to ship without thinking
The Problem Keeps Getting Worse
Over the past year I’ve written about agentic coding from several angles such as how to keep design ownership with engineers, how to use TLA+ for executable specifications, how to apply property-based and fuzz testing for microservices, and how to structure the entire delivery process through SDLC skills that force AI to operate within human-defined constraints. Each of those things helps but none of them fully solves the core problem.
The core problem: AI-generated code is probabilistic, and at scale, probability catches up with you. Based on Brooks’ Mythical Man-Month breakdown, coding itself is roughly 14% of the software delivery process. Agentic AI has largely solved that 14%. It writes clean, well-formatted, plausible code faster than any human. But plausible is not the same as correct. And when you generate 10× more code, the other 86% of your pipeline like design, specification, review, testing, deployment doesn’t automatically scale with it. I keep watching three failure modes play out:
- Hallucinations scale with complexity. An AI writing a 50-line function gets it right most of the time. An AI building a major feature in a large codebases with dozens of modules operators more probabilistically. It produces shallow modules instead of deep ones, duplicates logic, and makes locally correct decisions that violate global invariants. The code looks fine at the file level but the system breaks at the integration level.
- Review becomes the bottleneck. When one engineer’s code output multiplies by 10×, review bandwidth doesn’t scale with it. I’ve watched teams respond in two ways: slow everything down to match review capacity, or cut the review process to maintain throughput. Amazon learned what cutting review does to production reliability. It’s not a lesson you want to repeat.
- AI-generated code is harder to review than messy code. This is the counterintuitive one. Bertrand Meyer’s article AI for Software Engineering: From Probable to Provable names it precisely: clean, well-structured AI code creates a psychological safety bias. You stop reading as carefully. The concurrency bug in elegant code is harder to spot than the same bug in obviously messy code.
The Pressure to Abandon Quality
I have observed the organizational pressure to treat 10× code output as “just faster developers” and to cut the review, specification, and verification processes accordingly. I’ve seen executive pressure to eliminate code review entirely, to lay off senior engineers who “just do reviews,” to skip integration testing because “the AI tested it.”
This is exactly backwards. When code output increases 10×, the need for rigorous verification increases proportionally not decreases. Joe Mager’s Monte Carlo simulation of agentic coding pipelines quantifies that at a defect rate of 1-in-40 commits with a 12-hour pipeline, you get 0.7% deployment success, essentially deadlock. He calls the safe zone the “valley of calm”: the region where defect rate × pipeline duration stays well below 1.
Formal verification is the tool that keeps you in the valley. It doesn’t slow the generative side down and the AI still generates code fast. It gates the output mathematically, so you catch invariant violations before they reach production rather than after. The practical solution is a triple-engine pipeline: a generative engine (the LLM) that produces implementations fast, a verification engine (Dafny/TLA+/Z3) that proves correctness mathematically, an AI assisted specification engine where LLMs write the loop invariants, lemma stubs, and preconditions that feed the verifier. Human engineers own the intent and specification: what invariants matter, what correctness means in the problem domain. AI assists on all three layers. This post shows how to build that pipeline using a real RBAC system as the example. The companion repository is at github.com/bhatti/automated-reasoning.
From Logic AI to LLMs and Back
Modern LLMs work by predicting the next token, i.e., statistical, probabilistic, pattern-matching at scale. But AI didn’t start here. The dominant AI paradigm from the 1970s through the 1990s was symbolic and logical: knowledge representation, inference engines, expert systems, formal reasoning. We went from logic to probability and now we need both.
timeline
title AI Paradigms and Verification Approaches
section Logic Era (1970s–1990s)
1972 : Prolog — logic programming and knowledge representation
1979 : Boyer-Moore theorem prover
1986 : Eiffel introduces Design by Contract
1987 : TLA created by Leslie Lamport
section Hybrid Era (2000s–2010s)
1999 : Z3 SMT solver (Microsoft Research)
2005 : Alloy model finder
2009 : Dafny created (Microsoft Research)
2014 : TLA+ used at AWS for S3 and DynamoDB
section LLM Era (2020s)
2022 : ChatGPT and Copilot — probabilistic code generation goes mainstream
2024 : Agentic coding — 10× code throughput becomes normal
2025 : Spec-driven development movement emerges
2026 : Formal verification as AI guardrail
Understanding this history matters for a practical reason: the tools from the logic era didn’t disappear when LLMs arrived. They got faster, more automated, and better integrated into real development workflows. The question today isn’t “logic or probability?”, it’s “how do we combine them?”
Prolog and Logic Programming
Prolog (1972) represents knowledge as facts and rules, then uses unification and backtracking to answer queries. For authorization policy, you write the what, not the how:
has_role(alice, viewer).
has_role(bob, editor).
role_inherits(editor, viewer).
role_grants(viewer, read, docs).
role_grants(editor, write, docs).
can_access(User, Action, Resource) :-
has_role(User, Role),
role_grants(Role, Action, Resource).
can_access(User, Action, Resource) :-
has_role(User, Role),
role_inherits(Role, Parent),
role_grants(Parent, Action, Resource).
?- can_access(bob, read, docs).
% Yes — bob is editor, editor inherits viewer, viewer grants read:docs.
Design by Contract: Eiffel (1986)
Bertrand Meyer’s Eiffel language introduced Design by Contract (DbC): every method carries a formal contract such as preconditions, postconditions, class invariants that the runtime checks. I’ve been a fan of this approach for a long time, because it encodes intent alongside code rather than hoping a test suite happens to cover the right cases. DbC influenced:
- Clojure:
pre/postcondition maps on functions - Ada/SPARK: formal proof obligations on subprograms
- Java/C++:
assertstatements (though almost nobody enables them in production, which defeats the point) - Go: convention-based precondition checks that panic or return errors
- Dafny: compile-time verification of contracts
The key DbC insight that gets lost in most production codebases: assertions should always be enabled in production. They’re not test-time scaffolding. They’re executable specifications that catch invariant violations the moment they occur, including input combinations no test ever anticipated.
The Verification Spectrum
Here’s how I think about the tools available, from informal to formally proven:
| Approach | What it guarantees | Effort | Tools |
|---|---|---|---|
| Unit tests | Specific inputs pass | Low | JUnit, Go testing |
| BDD/Gherkin | Named scenarios pass | Low–Medium | Cucumber, Godog |
| Property-based testing | Random inputs satisfy properties | Medium | gopter, QuickCheck, Hypothesis |
| Fuzz testing | Mutated inputs don’t crash | Medium | go-fuzz, AFL, libFuzzer |
| Contract testing | API boundaries respected | Medium | Pact, api-mock-service |
| Static analysis | Type safety, null checks | Low | go vet, Rust compiler |
| Design by Contract | Pre/post/invariants checked at runtime | Medium | Eiffel, Clojure pre/post, assertions |
| Model checking | All reachable states are safe | High | TLA+, SPIN, Alloy |
| Deductive verification | Mathematical proof of correctness | High | Dafny, Lean, Coq |
| AI-assisted proof generation | Loop invariants, lemmas, and annotations generated by LLMs, | Low–Medium | dafny-annotator, LLM + Dafny |
The progression is from probabilistic to provable. The top rows test specific cases and find bugs. The bottom rows prove properties over all possible inputs and make entire classes of bugs impossible. AI-generated code needs both sides of this spectrum. Tests give you practical coverage fast. Proofs give you guarantees that no test suite can match. But here’s the catch I keep running into: when tests are also generated by AI, they may test the wrong thing as they optimize for passing, not for correctness. Formal specifications are the antidote. They state what correct is, mathematically, so even wrongly generated tests get caught when they conflict with the spec.
Automated Reasoning: The Technical Foundation
Before diving into code, let me explain what automated reasoning means. Automated reasoning means using software to answer mathematical questions about other software, without running it. Three activities matter here:
- Control flow analysis: what execution paths can the code take?
- Invariant discovery: what conditions hold regardless of which path it takes?
- Property verification: given a specification, does the code satisfy it for all inputs?
The critical distinction from testing: testing checks that specific inputs produce expected outputs. Automated reasoning proves that a property holds for every input the program could ever receive.
SAT: Boolean Satisfiability
The foundation is SAT (Boolean Satisfiability): given a formula with boolean variables, can you assign true/false values to satisfy all constraints simultaneously?
Example: (A v B) ^ (¬A v C) ^ (¬B v ¬C) SAT solver: A=true, B=false, C=true
SAT is NP-complete in theory but practically fast with modern CDCL (Conflict-Driven Clause Learning) solvers. Industrial solvers handle millions of variables routinely.
SMT: Satisfiability Modulo Theories
SMT extends SAT with theories and first-class reasoning about integers, real numbers, arrays, bitvectors, and strings. Where SAT works with booleans, SMT works with the kinds of values programs actually use:
(assert (= (+ x y) 10)) (assert (> x 3)) (assert (> y 3)) (check-sat) --> sat; x=4, y=6
AWS runs SMT at extraordinary scale. Their Zelkova system runs a billion SMT queries per day to analyze IAM access policies. Zelkova encodes IAM policies as logical formulas and feeds them to Z3 and CVC4. The FMCAD 2018 paper describes how policies translate to first-order logic with string theories and how incremental SMT solving makes this practical at scale.
Constraint Logic Programming (CLP)
CLP extends logic programming with constraint domains. Rather than enumerating solutions by hand, you declare variables, domains, and constraints, and the solver searches:
from ortools.sat.python import cp_model model = cp_model.CpModel() x = model.new_int_var(0, 10, 'x') y = model.new_int_var(0, 10, 'y') model.add(x + y == 10) model.add(x > 3) model.add(y > 3) solver = cp_model.CpSolver() solver.solve(model) # finds x=4, y=6
Google’s CP-SAT scheduler uses this approach and outperforms integer programming for VM migration scheduling because interval variables natively model time-continuous constraints.
The Formal Verification Landscape

Where to apply each:
- Distributed systems with concurrency: TLA+ (exhaustive state space exploration)
- Algorithm correctness and data structure invariants: Dafny (deductive proof)
- Access policy analysis: SMT (Zelkova, Cedar, Z3 directly)
- Memory safety: Rust’s type system, Verus, or Dafny ghost state
One finding from AWS’s work that surprises most people: formal verification often makes systems faster, not just safer. Their IAM authorization engine got a 50% performance improvement after verification as the process of proving correctness forced developers to eliminate redundant computation and latent bugs that happened to be performance bottlenecks. The S3 index subsystem moved from quarterly to monthly releases after applying automated reasoning. This directly addresses the organizational pushback: verification doesn’t slow you down.
Spec-Driven Development: The Movement Behind the Tools
The insight that specifications instead of code should drive AI development has gained serious traction. Projects like OpenSpec and Spec-Kit formalize this workflow. My own you-got-skills SDLC skills set encodes it: structured workflows for PRD refinement, TRD review, architecture, work breakdown, implementation, and formal QA where AI operates within human-defined constraints rather than inventing its own.
The spec-driven philosophy is: make invalid implementations unrepresentable. You can do this through types (Rust, Haskell), contracts (Eiffel, Dafny), or formal models (TLA+). When your specification is precise enough, AI hallucinations become immediately visible as verification failures rather than subtle production bugs. The verifier catches them instead of the reviewer or the on-call engineer at 2am. Formal verification shifts the time from debugging production incidents to writing specifications that make the rest of the process faster and more predictable.
TLA+ for Concurrency
I covered TLA+ extensively in my earlier post about an year go. I’ll show a targeted example specific to RBAC: the concurrent policy update problem.
The scenario: two admins simultaneously assign roles to the same principal. Without coordination, a check-then-act race violates Separation of Duty (SoD):
Admin A: check(submitter) --> no conflict --> intend to assign Admin B: check(approver) --> no conflict --> intend to assign Admin A: assign(submitter) OK Admin B: assign(approver) <-- SoD violated: both roles now held
The TLA+ spec models an optimistic-locking protocol and asks TLC to exhaustively check that SoD is never violated:
(* Safety: SoD never violated *)
SoDOK ==
~(\E r1, r2 \in assigned : r1 # r2 /\ <<r1,r2>> \in Conflicts)
(* Liveness: every pending assignment eventually completes *)
Liveness ==
\A a \in Admins :
[](phase[a] = "checking" => <>(phase[a] \in {"done", "idle"}))
With 2 admins and 3 roles ({Submitter, Approver, Viewer}), TLC explores 1,046 distinct states and finds no violations:
Model checking completed. No error has been found. 2349 states generated, 1046 distinct states found, 0 states left on queue.
Full spec is in tla/RBACPolicyChange.tla in the companion repo. Run it with:
java -jar ~/tla2tools.jar -config tla/RBACPolicyChange.cfg tla/RBACPolicyChange.tla
For the rest of this post I focus on Dafny, since I already covered TLA+ in depth and Dafny is where I spend most of my verification time now.
Dafny: Practical Deductive Verification
Dafny is a verification-aware programming language from Microsoft Research. It sits in the practical sweet spot: more powerful than static analyzers, far less manual effort than Coq or Lean. Dafny uses Z3 under the hood and verifies many programs automatically without manual proof steps. Importantly for this post, Dafny compiles to Go so you write your specifications in Dafny, your implementations in Go, and the type system and contracts carry through naturally.
The Amazon Dafny curriculum describes three roles Dafny plays simultaneously:
- Programming language: loops, classes, generics, standard data structures
- Proof assistant: write lemmas and Dafny proves them automatically
- Program verifier: attach
requires/ensuresto methods and Dafny proves they hold for all possible inputs
Design by Contract in Dafny
method Divide(a: int, b: int) returns (result: int)
requires b != 0 // precondition: caller must ensure this
ensures result * b == a // postcondition: callee guarantees this
{
return a / b;
}
If you call Divide(10, 0), Dafny rejects it at compile time not at runtime. That’s the shift from “testing catches bugs” to “bugs can’t be expressed.”
The Example: An RBAC System
I chose RBAC because it’s rich enough to demonstrate real verification value without being contrived. The companion project is a simplified version of my saas_rbac project. The domain model has six entities:

Why RBAC? It exhibits four bug classes that AI-generated code routinely gets wrong and each maps cleanly to a formal property:
- Type safety: dangling references, e.g., a principal in org A assigned a role that references a resource in org B
- Structural safety: role hierarchy must be a DAG, e.g., cycles cause infinite loops during claim resolution
- Security safety: policy evaluation must be sound (no phantom permissions) and complete (no missed permissions)
- Conflict safety: Separation of Duty must hold after every role assignment, including the symmetric direction AI almost always misses
Each of these is a property I state once in Dafny and prove once rather than hoping a test suite happens to exercise the right edge cases.
Step 1: Types and the System-Wide Invariant (rbac_types.dfy)
The first thing I write isn’t any method, it’s the ValidStore predicate: the system-wide invariant that every operation must preserve. Writing it out forces you to articulate what “correct state” actually means before writing a single line of logic.
predicate ValidStore(s: RBACStore) {
// No dangling principal references
&& (forall id :: id in s.principals ==>
s.principals[id].orgId in s.orgs)
// Tenant isolation: role parents must be in same org
&& (forall rid :: rid in s.roles ==>
(forall pid :: pid in SeqToSet(s.roles[rid].parentIds) ==>
s.roles[pid].orgId == s.roles[rid].orgId))
// Claim resources must exist in the store
&& (forall rid :: rid in s.roles ==>
(forall c :: c in s.roles[rid].claims ==>
c.resourceId in s.resources))
// ... (8 more invariants)
}
A lemma proves the empty store satisfies it and Dafny verifies this automatically with no manual proof steps:
lemma EmptyStoreIsValid()
ensures ValidStore(EmptyStore())
{}
The value here isn’t the lemma but it’s the discipline the predicate imposes. When you have to state every invariant precisely before writing code, the class of bugs you can introduce narrows dramatically. Every subsequent method carries requires ValidStore(s) and ensures ValidStore(result) and Dafny enforces this chain automatically.
Step 2: Policy Evaluation (rbac_policy.dfy)
The two most critical properties of any authorization system:
SOUNDNESS: If Evaluate returns Allow, a valid claim chain EXISTS.
No phantom permissions. No false positives.
COMPLETENESS: If a valid claim chain exists, Evaluate returns Allow.
No missed permissions. No false negatives.
I write the ground-truth specification as a pure, non-executable predicate, then verify that the executable method matches it exactly:
// The specification — states what "correct" means mathematically
predicate PolicySpec(req: Request, store: RBACStore, ctx: EvalContext) {
var principal := store.principals[req.principalId];
exists c :: c in PrincipalClaims(principal, store.roles) &&
ClaimGrants(c, req.action, req.resourceId, ctx)
}
// The implementation — Dafny proves it matches PolicySpec for all inputs
method Evaluate(req: Request, store: RBACStore, ctx: EvalContext)
returns (decision: Decision)
requires ValidStore(store)
requires req.principalId in store.principals
requires store.principals[req.principalId].orgId == req.orgId
ensures decision == Allow ==> PolicySpec(req, store, ctx) // SOUNDNESS
ensures decision == Deny ==> !PolicySpec(req, store, ctx) // COMPLETENESS
Dafny verifies the loop implementation with a loop invariant that tracks “no match found in claims[0..i]”:
while i < |claimSeq|
invariant decision == Deny ==>
forall j :: 0 <= j < i ==>
!ClaimGrants(claimSeq[j], req.action, req.resourceId, ctx)
decreases |claimSeq| - i
{
if ClaimGrants(claimSeq[i], req.action, req.resourceId, ctx) {
decision := Allow;
return;
}
i := i + 1;
}
The decreases clause proves termination and Dafny guarantees no infinite loops, for any input. When AI generates the implementation, if it introduces a subtle loop condition bug, Dafny catches it immediately rather than at a production incident. A bonus lemma proves monotonicity and adding claims can never turn an Allow into a Deny:
lemma MoreClaimsMonotonic(req, store1, store2, ctx) requires store1 has subset of claims of store2 ensures PolicySpec(req, store1, ctx) ==> PolicySpec(req, store2, ctx)
Step 3: Role Hierarchy with No Cycles (rbac_role_hierarchy.dfy)

AddParent proves that cycles can never be introduced, regardless of what sequence of operations an API caller attempts:
method AddParent(child: RoleId, parent: RoleId, roles: map<RoleId, Role>)
returns (result: map<RoleId, Role>, ok: bool)
requires NoCycles(roles)
ensures ok ==> NoCycles(result) // DAG invariant always preserved
ensures !ok ==> result == roles // rejection leaves the store unchanged
{
var wouldCycle := child in Ancestors(parent, roles, |roles|);
if wouldCycle { return roles, false; }
// safe to add the parent edge
}
Ancestors computes the full ancestor set with bounded recursion, e.g., fuel of |roles| is sufficient for any valid DAG. This is a property that’s easy to state but extremely hard to test exhaustively: you’d have to enumerate all possible role graph topologies. Dafny proves it once, for all possible graphs.
Step 4: Separation of Duty (rbac_separation_of_duty.dfy)
SoD says certain role pairs must never be co-assigned and you can’t be both the invoice submitter and the invoice approver. The subtle bug AI code routinely misses is the symmetric case: checking (existing, new) but not (new, existing). This is exactly the kind of off-by-one semantic error that looks correct on inspection and only surfaces in edge-case inputs.
predicate SoDSatisfied(assignedRoles: set<RoleId>, conflicts: ConflictSet) {
forall a, b ::
a in assignedRoles && b in assignedRoles && a != b ==>
(a, b) !in conflicts
}
method AssignRole(principal, newRole, conflicts)
requires SoDSatisfied(SeqToSet(principal.roleIds), conflicts)
ensures ok ==> SoDSatisfied(SeqToSet(updated.roleIds), conflicts)
ensures !ok ==> exists existing ::
existing in SeqToSet(principal.roleIds) &&
(existing, newRole) in conflicts // proof witness for why it was rejected
Here’s what Dafny outputs when an AI generates the broken version that only checks one direction:
rbac_separation_of_duty.dfy(42,4): Error: a postcondition could not be proved
ensures ok ==> SoDSatisfied(SeqToSet(updated.roleIds), conflicts)
Counterexample:
principal.roleIds = ["approver"]
newRole = "submitter"
conflicts = {("submitter", "approver")} ? (new, existing) direction missed
That counterexample shows exactly which input violates the contract, with a concrete example. Without Dafny, catching this requires either a carefully targeted test case or it shows up in production when someone discovers SoD can be bypassed by using conflict pairs in reverse order.
Step 5: Constraint Monotonicity (rbac_constraints.dfy)
Constraints make RBAC dynamic like time windows, geo fences, usage quotas. The key properties to prove are:
// Adding constraints can only reduce access, never increase it
lemma AddingConstraintReducesAccess(base, extra, ctx)
ensures AllConstraintsHold(base + [extra], ctx) ==>
AllConstraintsHold(base, ctx)
// Empty constraint list always passes (vacuous truth — no constraints = no restrictions)
lemma EmptyConstraintsAlwaysHold(ctx)
ensures AllConstraintsHold([], ctx)
{}
// Higher usage makes quota constraints harder to satisfy
lemma HigherUsageHarder(limit, usage1, usage2, ctx)
requires usage1 <= usage2
ensures ConstraintHolds(MaxUsage(limit), ctx[usage:=usage2]) ==>
ConstraintHolds(MaxUsage(limit), ctx[usage:=usage1])
These seem obvious. They are exactly the properties that break when AI generates constraint evaluation with subtle off-by-one errors or a flipped inequality direction (>= instead of >). Proving them once means you catch the implementation error in the Go translation from a failed test instead of production from an access control bypass.
The Go Implementation: Verified by Construction
The Go implementation translates the Dafny specifications directly. Every design decision traces back to a proved property.
Types Mirror Dafny Datatypes
// go/pkg/types/types.go
type Claim struct {
ID ClaimID
Action string
ResourceID ResID
Constraints []Constraint // empty = always passes (vacuous truth, proved by EmptyConstraintsAlwaysHold)
}
// NewTimeWindow enforces the Dafny precondition ValidConstraint at construction time
func NewTimeWindow(start, end int) (Constraint, error) {
if start >= end || end > 24 {
return Constraint{}, fmt.Errorf("invalid time window: start < end <= 24 required")
}
return Constraint{Kind: TimeWindowKind, StartHour: start, EndHour: end}, nil
}
// NewGeoFence — Dafny requires |regions| > 0
func NewGeoFence(regions []string) (Constraint, error) {
if len(regions) == 0 {
return Constraint{}, fmt.Errorf("geo fence requires at least one region")
}
return Constraint{Kind: GeoFenceKind, Regions: regions}, nil
}
// NewMaxUsage — Dafny requires limit > 0
func NewMaxUsage(limit int) (Constraint, error) {
if limit <= 0 {
return Constraint{}, fmt.Errorf("max usage limit must be positive")
}
return Constraint{Kind: MaxUsageKind, MaxCount: limit}, nil
}
Constraint Evaluation Maps Directly to Dafny
// go/pkg/constraints/constraints.go
// Holds mirrors Dafny's ConstraintHolds predicate exactly.
// Every case corresponds to a branch in the Dafny match expression.
func Holds(c types.Constraint, ctx types.EvalContext) bool {
switch c.Kind {
case types.TimeWindowKind:
// Dafny: ctx.currentHour >= c.startHour && ctx.currentHour < c.endHour
return ctx.CurrentHour >= c.StartHour && ctx.CurrentHour < c.EndHour
case types.GeoFenceKind:
// Dafny: ctx.currentRegion in c.allowedRegions
for _, r := range c.Regions {
if r == ctx.CurrentRegion {
return true
}
}
return false
case types.MaxUsageKind:
// Dafny: ctx.currentUsage < c.maxCount
return ctx.CurrentUsage < c.MaxCount
default:
return false
}
}
// AllHold evaluates a conjunction of constraints.
// Dafny proved: AllConstraintsHold([], ctx) == true (EmptyConstraintsAlwaysHold)
// Dafny proved: AllConstraintsHold(base + [extra], ctx) ==> AllConstraintsHold(base, ctx)
func AllHold(cs []types.Constraint, ctx types.EvalContext) bool {
for _, c := range cs {
if !Holds(c, ctx) {
return false
}
}
return true
}
Role Hierarchy: BFS with Proven Cycle Detection
// go/pkg/hierarchy/hierarchy.go
// HasCycle returns true if adding parent to child would create a cycle.
// Mirrors Dafny: child in Ancestors(parent, roles, |roles|)
func (r *Resolver) HasCycle(child, parent types.RoleID) bool {
visited := map[types.RoleID]bool{}
queue := []types.RoleID{parent}
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
if current == child {
return true
}
if visited[current] {
continue
}
visited[current] = true
if role, ok := r.roles[current]; ok {
queue = append(queue, role.ParentIDs...)
}
}
return false
}
// AddParent adds a parent role with cycle guard.
// Mirrors Dafny: requires NoCycles, ensures NoCycles preserved or store unchanged.
func (r *Resolver) AddParent(child, parent types.RoleID) error {
if r.HasCycle(child, parent) {
return fmt.Errorf("adding parent %s to %s would create a cycle", parent, child)
}
role := r.roles[child]
role.ParentIDs = append(role.ParentIDs, parent)
r.roles[child] = role
return nil
}
// TransitiveClaims collects all claims reachable through the role hierarchy.
// BFS bounded by number of roles — same as Dafny's fuel parameter.
func TransitiveClaims(roleID types.RoleID, roles map[types.RoleID]types.Role) []types.Claim {
var claims []types.Claim
visited := map[types.RoleID]bool{}
queue := []types.RoleID{roleID}
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
if visited[current] {
continue
}
visited[current] = true
role, ok := roles[current]
if !ok {
continue
}
claims = append(claims, role.Claims...)
queue = append(queue, role.ParentIDs...)
}
return claims
}
Store: Invariant Enforcement at Every Write
// go/pkg/store/store.go
// AssignRole mirrors Dafny AssignRole:
// requires SoDSatisfied(current roles, conflicts)
// ensures SoDSatisfied(updated roles, conflicts) OR rejection with witness
func (s *Store) AssignRole(principalID types.PrinID, roleID types.RoleID) error {
s.mu.Lock()
defer s.mu.Unlock()
principal, ok := s.principals[principalID]
if !ok {
return fmt.Errorf("principal %s not found", principalID)
}
role, ok := s.roles[roleID]
if !ok {
return fmt.Errorf("role %s not found", roleID)
}
// Tenant isolation — from Dafny ValidStore predicate
if role.OrgID != principal.OrgID {
return fmt.Errorf("tenant isolation: role org %s != principal org %s",
role.OrgID, principal.OrgID)
}
// SoD conflict check — checks BOTH directions, per Dafny SoDSatisfied predicate
for _, existingRoleID := range principal.RoleIDs {
if s.hasConflict(existingRoleID, roleID) {
return fmt.Errorf("separation of duty: role %q conflicts with existing role %q",
roleID, existingRoleID)
}
}
// Safe to assign — SoD preserved (Dafny ensures clause holds)
principal.RoleIDs = append(principal.RoleIDs, roleID)
s.principals[principalID] = principal
return nil
}
Policy Engine Encodes the Soundness/Completeness Contract
// go/pkg/policy/policy.go
// Evaluate decides Allow or Deny for a request.
// Preconditions from Dafny requires clauses: request fields valid, principal exists, tenant matches.
// Postconditions from Dafny ensures clauses: Allow iff valid claim chain exists.
func (e *Engine) Evaluate(req types.Request, ctx types.EvalContext) (types.Decision, error) {
if err := req.Validate(); err != nil {
return types.Deny, fmt.Errorf("invalid request: %w", err)
}
principal, ok := e.store.GetPrincipal(req.PrincipalID)
if !ok {
return types.Deny, nil // deny-by-default — proved by DenyByDefault lemma
}
if principal.OrgID != req.OrgID {
return types.Deny, fmt.Errorf("tenant isolation violated")
}
// Walk transitive claims — same BFS algorithm as Dafny Evaluate method
claims := hierarchy.PrincipalClaims(principal, e.store.AllRoles())
for _, c := range claims {
if constraints.ClaimGrants(c, req.Action, req.ResourceID, ctx) {
return types.Allow, nil
}
}
return types.Deny, nil
}
Property-Based Tests: The Bridge from Provable to Probable
Each Dafny lemma gets a matching gopter property-based test. Dafny proves for all possible inputs; gopter fires hundreds of random inputs and catches bugs in the Go translation where the Dafny spec is correct but the Go implementation diverges.
// go/pkg/policy/policy_test.go
// Mirrors: DenyByDefault lemma in rbac_invariants.dfy
func TestProp_NoRolesAlwaysDenied(t *testing.T) {
props := gopter.NewProperties(gopter.DefaultTestParameters())
props.Property("principal with no roles is always denied", prop.ForAll(
func(action, resource string) bool {
s := store.New()
_ = s.AddOrg(types.Organization{ID: "org", Name: "org"})
_ = s.AddResource(types.Resource{ID: resource, Name: resource, Kind: "api"})
_ = s.AddPrincipal(types.Principal{ID: "p", OrgID: "org", Name: "P"})
engine := policy.New(s)
req := types.Request{OrgID: "org", PrincipalID: "p",
Action: action, ResourceID: resource}
decision, _ := engine.Evaluate(req, types.EvalContext{CurrentHour: 12})
return decision == types.Deny
},
gen.AlphaString(), gen.AlphaString(),
))
props.TestingRun(t, gopter.NewFormatedReporter(false, 80, os.Stdout))
}
// Mirrors: AddingConstraintReducesAccess lemma in rbac_constraints.dfy
func TestProp_ConstraintMonotonicity(t *testing.T) {
props := gopter.NewProperties(gopter.DefaultTestParameters())
props.Property("subset of constraints passing implies prefix passes", prop.ForAll(
func(hour int, region string, usage int) bool {
ctx := types.EvalContext{
CurrentHour: abs(hour) % 24,
CurrentRegion: region,
CurrentUsage: abs(usage) % 100,
}
tw, _ := types.NewTimeWindow(9, 17)
base := []types.Constraint{tw}
geo, _ := types.NewGeoFence([]string{"us-east-1"})
extended := append(base, geo)
// If the extended (stricter) set passes, the base set MUST also pass
if constraints.AllHold(extended, ctx) {
return constraints.AllHold(base, ctx)
}
return true
},
gen.Int(), gen.AnyString(), gen.Int(),
))
props.TestingRun(t, gopter.NewFormatedReporter(false, 80, os.Stdout))
}
// Mirrors: HigherUsageHarder lemma in rbac_constraints.dfy
func TestProp_QuotaMonotonicity(t *testing.T) {
props := gopter.NewProperties(gopter.DefaultTestParameters())
props.Property("higher usage never turns Deny into Allow for quota", prop.ForAll(
func(limit int, lo int, delta int) bool {
limit = abs(limit)%100 + 1
lo = abs(lo) % 200
hi := lo + abs(delta)%100 // hi >= lo guaranteed
quota, _ := types.NewMaxUsage(limit)
ctxLo := types.EvalContext{CurrentUsage: lo}
ctxHi := types.EvalContext{CurrentUsage: hi}
// If quota passes at HIGHER usage, it MUST pass at lower usage
if constraints.Holds(quota, ctxHi) {
return constraints.Holds(quota, ctxLo)
}
return true
},
gen.Int(), gen.Int(), gen.Int(),
))
props.TestingRun(t, gopter.NewFormatedReporter(false, 80, os.Stdout))
}
// Mirrors: OwnClaimsIncluded lemma in rbac_role_hierarchy.dfy
func TestProp_OwnClaimsAlwaysIncluded(t *testing.T) {
props := gopter.NewProperties(gopter.DefaultTestParameters())
props.Property("role's own claims always appear in transitive claims", prop.ForAll(
func(claimCount int) bool {
claimCount = abs(claimCount)%5 + 1
var claims []types.Claim
for i := 0; i < claimCount; i++ {
claims = append(claims, types.Claim{
ID: types.ClaimID(fmt.Sprintf("c%d", i)),
Action: fmt.Sprintf("action%d", i),
ResourceID: "res1",
})
}
roles := map[types.RoleID]types.Role{
"role1": {ID: "role1", OrgID: "org1", Claims: claims},
}
transitive := hierarchy.TransitiveClaims("role1", roles)
for _, c := range claims {
found := false
for _, tc := range transitive {
if tc.ID == c.ID {
found = true
break
}
}
if !found {
return false
}
}
return true
},
gen.Int(),
))
props.TestingRun(t, gopter.NewFormatedReporter(false, 80, os.Stdout))
}
Running the full suite:
+ empty constraint list always passes: OK, passed 200 tests. + hour in [start,end) passes, hour outside fails: OK, passed 500 tests. + subset of constraints passing implies prefix passes: OK, passed 300 tests. + higher usage never turns Deny into Allow for quota: OK, passed 300 tests. + role's own claims always appear in transitive claims: OK, passed 200 tests. + adding a parent never reduces transitive claims: OK, passed 200 tests. + unknown principal is always denied: OK, passed 200 tests. + principal with no roles is always denied: OK, passed 200 tests. PASS — 2300+ property-based test cases executed.
Each line corresponds to a Dafny lemma. The property tests don’t replace the proofs, they catch bugs in the Go translation that the Dafny verifier can’t see.
Adding a Feature the Verified Way
Let me walk through adding a RateLimit constraint from scratch. This is the exact workflow for extending a formally verified system, and it shows why the upfront cost is much lower than it looks.
Step 1: Add the datatype in Dafny
datatype ConstraintKind =
| TimeWindow(startHour: nat, endHour: nat)
| GeoFence(allowedRegions: seq<string>)
| MaxUsage(maxCount: nat)
| RateLimit(requestsPerMinute: nat) // NEW
predicate ValidConstraint(c: ConstraintKind) {
match c
case TimeWindow(s, e) => 0 <= s < e <= 24
case GeoFence(regions) => |regions| > 0
case MaxUsage(max) => max > 0
case RateLimit(rpm) => rpm > 0 // must be positive
}
Step 2: Define evaluation semantics
predicate ConstraintHolds(c: ConstraintKind, ctx: EvalContext) {
match c
case TimeWindow(s, e) => s <= ctx.currentHour < e
case GeoFence(regions) => ctx.currentRegion in regions
case MaxUsage(max) => ctx.currentUsage < max
case RateLimit(rpm) => ctx.currentRequestRate < rpm // NEW
}
Step 3: Write and prove a monotonicity lemma
// Lower rate limit is harder to satisfy — proved automatically
lemma LowerRateLimitHarder(rpm1: nat, rpm2: nat, ctx: EvalContext)
requires rpm1 <= rpm2
requires rpm1 > 0 && rpm2 > 0
ensures ConstraintHolds(RateLimit(rpm1), ctx) ==>
ConstraintHolds(RateLimit(rpm2), ctx)
{
// Dafny proves this in under a second: if rate < rpm1 <= rpm2 then rate < rpm2
}
Step 4: Verify
$ dafny verify dafny/rbac_constraints.dfy Dafny program verifier finished with 12 verified, 0 errors
Step 5: Implement in Go
func NewRateLimit(rpm int) (Constraint, error) {
if rpm <= 0 {
return Constraint{}, fmt.Errorf("rate limit must be positive")
}
return Constraint{Kind: RateLimitKind, MaxCount: rpm}, nil
}
// Add to Holds() in constraints.go:
case types.RateLimitKind:
return ctx.CurrentRequestRate < c.MaxCount
Step 6: Write the matching property test
func TestProp_LowerRateLimitHarder(t *testing.T) {
props := gopter.NewProperties(gopter.DefaultTestParameters())
props.Property("lower rate limit is harder to satisfy", prop.ForAll(
func(rpm1, rpm2, rate int) bool {
rpm1 = abs(rpm1)%100 + 1
rpm2 = rpm1 + abs(rpm2)%100 // rpm2 >= rpm1 guaranteed
ctx := types.EvalContext{CurrentRequestRate: abs(rate) % 200}
c1, _ := types.NewRateLimit(rpm1)
c2, _ := types.NewRateLimit(rpm2)
if constraints.Holds(c1, ctx) {
return constraints.Holds(c2, ctx)
}
return true
},
gen.Int(), gen.Int(), gen.Int(),
))
props.TestingRun(t, gopter.NewFormatedReporter(false, 80, os.Stdout))
}
That full loop from datatype –> predicate –> lemma –> verify –> implement –> test takes maybe 20 minutes for a new constraint type. The result ships with a mathematical proof that the Go implementation matches the specification.
The Complete Pipeline
The workflow in the companion repo ties everything together:

Running the full pipeline:
# Step 1: Verify formal specs
$ make verify-dafny
[DAFNY] Verifying rbac_types.dfy... ? PASS
[DAFNY] Verifying rbac_policy.dfy... ? PASS
[DAFNY] Verifying rbac_role_hierarchy.dfy... ? PASS
[DAFNY] Verifying rbac_separation_of_duty.dfy... ? PASS
[DAFNY] Verifying rbac_constraints.dfy... ? PASS
[DAFNY] Verifying rbac_invariants.dfy... ? PASS
All 6 Dafny files verified successfully.
# Step 2: Model check concurrent protocol
$ make check-tla
[TLA+] Model checking RBACPolicyChange...
Model checking completed. No error has been found.
2349 states generated, 1046 distinct states found.
# Step 3: Run property-based tests
$ make test
+ empty constraint list always passes: OK, passed 200 tests.
+ time window boundary conditions: OK, passed 500 tests.
+ constraint monotonicity: OK, passed 300 tests.
+ quota monotonicity: OK, passed 300 tests.
+ own claims in transitive closure: OK, passed 200 tests.
+ adding parent never removes claims: OK, passed 200 tests.
+ unknown principal always denied: OK, passed 200 tests.
+ no roles always denied: OK, passed 200 tests.
PASS — 2300+ property-based test cases executed.
# Step 4: Smoke-test the API
$ make run &
Server starting on :9090...
# alice can read docs (viewer role, time window 9-17, currently hour 10)
$ curl -s localhost:9090/evaluate -d '{
"org_id":"acme", "principal_id":"alice",
"action":"read", "resource_id":"docs",
"hour":10, "region":"us-east-1", "usage":0
}' | jq .decision
"Allow"
# alice denied at 10pm — time constraint blocks access outside 9-17
$ curl -s localhost:9090/evaluate -d '{
"org_id":"acme", "principal_id":"alice",
"action":"read", "resource_id":"reports",
"hour":22, "region":"us-east-1", "usage":0
}' | jq .decision
"Deny"
# bob can write docs from US (editor role + geo constraint us-east-1)
$ curl -s localhost:9090/evaluate -d '{
"org_id":"acme", "principal_id":"bob",
"action":"write", "resource_id":"docs",
"hour":12, "region":"us-east-1", "usage":0
}' | jq .decision
"Allow"
# bob denied from EU — geo constraint blocks non-US regions
$ curl -s localhost:9090/evaluate -d '{
"org_id":"acme", "principal_id":"bob",
"action":"write", "resource_id":"docs",
"hour":12, "region":"eu-west-1", "usage":0
}' | jq .decision
"Deny"
# SoD blocks carol (finance role) from also being submitter
$ curl -s localhost:9090/principals/carol/roles -d '{"role_id":"submitter"}'
{"error":"separation of duty: role \"submitter\" conflicts with existing role \"finance\""}
Who Writes the Specs? The Human-AI Division
This is the question I get asked most. Here’s how I answer it.

Humans must own:
- What the invariants are, e.g., SoD, tenant isolation, deny-by-default, referential integrity
- What the formal properties mean in the problem domain
- Reviewing counterexamples from the verifier and refining specs accordingly
- Architecture decisions: which tool for which problem, which 20% of the codebase to verify
AI can assist:
- Dafny syntax, e.g.,LLMs generate valid Dafny from English property descriptions, as the TLA+ for the LLM era article demonstrates for TLA+
- Boilerplate Go translated from Dafny type definitions
- Test scaffolding for gopter properties
- Translating Dafny lemmas into property test outlines
- Generating loop invariants and
decreasesclauses from BFS/iteration patterns the LLM recognizes
The feedback loop in practice:
- Human writes
ValidStorecapturing tenant isolation - AI generates the
AddPrincipalmethod in Go - Dafny verifies the spec — or produces a counterexample
- If counterexample: human understands the bug (usually a missed invariant direction), refines the spec
- AI regenerates from the refined spec
- Repeat until proof succeeds
Marc Brooker’s analysis of what AI agents find easy versus hard makes the point precisely: agents succeed on tasks with good automated feedback and struggle on tasks without it. Formal verification is that feedback as it is mathematical, precise, and automatable. It turns the review loop into a tight iteration between human specifier and verifier, rather than a bottleneck where an engineer reads 1,000 lines of plausible AI code hoping to spot a subtle invariant violation. This directly counters the “cut review to go faster” argument: you don’t cut review instead you replace line-by-line code review with specification review, which is faster, higher leverage, and catches the bugs that matter.
When to Apply Formal Verification
Not every line of code needs formal verification. Here’s how I decide where to apply it:
| Apply formal verification | Skip it |
|---|---|
| Authorization and access control | UI rendering logic |
| Cryptographic protocols | CRUD boilerplate |
| Distributed consensus | Simple data transformations |
| Financial calculations | User-facing text content |
| Schema migration validators | Logging and metrics |
| Safety-critical state machines | Configuration defaults |
The pattern: apply where bugs are expensive like security, correctness, data integrity and where the specification can be stated mathematically. For the critical 20% of a codebase where correctness failures are severe, formal verification pays for itself on the first prevented production incident. For the other 80%, tests and code review are the right tools. This targeting also addresses the organizational pressure argument directly. You don’t need to formally verify everything, which would be impractical. You verify the parts where the cost of being wrong is highest. That’s a defensible, scoped investment that produces measurable risk reduction.
Getting Started with Dafny: Three Steps
- Step 1: Start with types. Write
ValidXxxpredicates before writing any methods. This forces you to articulate what “correct state” means before writing code that’s supposed to produce it. The predicates are small, incremental, and require no theorem-proving expertise. AI can bootstrap this step. LLMs are now quite capable at generating Dafny precondition/postcondition stubs from English property descriptions. See dafny-annotator: AI-Assisted Verification of Dafny Programs. - Step 2: Add contracts to one critical method. Pick the authorization check. Add
requires/ensures. Let Dafny fail. Understand why. Add lemmas. The first proof is the hardest; subsequent ones follow the same pattern. - Step 3: Mirror each lemma with a property test. This catches translation bugs in the Go implementation and keeps spec and code in sync as the system evolves.
// Dafny lemma — proved by the verifier
lemma EmptyConstraintsAlwaysHold(ctx: EvalContext)
ensures AllConstraintsHold([], ctx)
{}
// Matching gopter property — catches Go translation bugs
props.Property("empty constraint list always passes", prop.ForAll(
func(hour int, region string) bool {
ctx := types.EvalContext{CurrentHour: hour % 24, CurrentRegion: region}
return constraints.AllHold(nil, ctx)
},
gen.Int(), gen.AnyString(),
))
Conclusion: You Can’t Outsource Thinking
The AI era has come full circle. In the 1980s, AI meant logic like Prolog, expert systems, formal inference. The 2020s flipped to probabilistic: statistical token prediction that generates plausible code at extraordinary speed. But plausible was never the goal. Correct is the goal. And correctness was always logic’s domain.
The Bertrand Meyer’s article From Probable to Provable captures the shift precisely: the engineering role moves from writing code to writing specifications. From debugging via console.log to managing verification pipelines. From reviewing AI-generated code line by line to reviewing the specs the verifier checks against.
The division of labor looks like this:
| Layer | Owner | Activity |
|---|---|---|
| Specification | Human engineer | Defines invariants, contracts, correctness properties |
| Code generation | AI (LLM) | Produces candidate implementations fast |
| Verification | Formal tools (Dafny, TLA+, Z3) | Proves or refutes correctness mathematically |
| Testing | Property-based + fuzz | Catches translation bugs between spec and implementation |
| Review | Human engineer | Reviews counterexamples, refines specifications |
This is the answer to the organizational pressure to skip review, reduce verification, and just ship. The pressure comes from observing 10× code output and concluding that verification overhead is blocking throughput. The data says the opposite: organizations that remove verification to increase throughput move from the valley of calm to the plateau of misery. They ship more code with lower reliability. The pipeline stalls.
Formal verification, applied selectively to the critical 20% of your codebase, keeps the defect rate low enough that the rest of the pipeline flows. It shifts human effort from reading AI-generated code line by line to writing the specifications that make wrong implementations immediately visible. That’s a higher-leverage use of engineering time and a better argument to make to management than “we need more review bandwidth.”
The tools are practical today:
- Dafny verifies all 6 RBAC specification files in under 30 seconds on a laptop
- TLC model-checks the concurrent update protocol in under a second
- gopter runs 2,300+ property tests in under a second
- Total upfront overhead: roughly 20% more time spent writing specs rather than debugging production
Mager’s valley of calm stays wide when your defect rate stays low. Formal verification is the most effective tool I’ve found for keeping it there.
Everything in this post runs from the companion repository: github.com/bhatti/automated-reasoning.
References
- AWS: An Unexpected Discovery – Automated Reasoning Often Makes Systems More Efficient
- CACM: Systems Correctness Practices at Amazon Web Services
- CACM: AI for Software Engineering – From Probable to Provable
- Dafny: Teaching Program Verification at Amazon
- Galois: Automated Lean Proofs for Every Type
- Jane Street: Formal Methods
- Brooker: What’s Easy, What’s Hard for AI Agents
- Mager: The Valley of Calm
- Mager: The New Calculus of AI-Based Coding
- AI Writes Code, You Own the Design
- Beyond Vibe Coding – TLA+ with Claude
- Contract Testing for REST APIs
- TLA+ for the LLM Era
- Use Prolog to Improve LLM Reasoning
- Google OR-Tools CP-SAT for Scheduling
- you-got-skills: SDLC Skills for AI-Assisted Development
- ProVerB: Program Verification Book
- Loughridge et al. “DafnyBench: A Benchmark for Formal Software Verification.”