Shahzad Bhatti Welcome to my ramblings and rants!

June 18, 2026

Applying Formal Verification to Guard AI-Generated Code

Filed under: Agentic AI — admin @ 4:16 pm

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/post condition maps on functions
  • Ada/SPARK: formal proof obligations on subprograms
  • Java/C++: assert statements (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:

ApproachWhat it guaranteesEffortTools
Unit testsSpecific inputs passLowJUnit, Go testing
BDD/GherkinNamed scenarios passLow–MediumCucumber, Godog
Property-based testingRandom inputs satisfy propertiesMediumgopter, QuickCheck, Hypothesis
Fuzz testingMutated inputs don’t crashMediumgo-fuzz, AFL, libFuzzer
Contract testingAPI boundaries respectedMediumPact, api-mock-service
Static analysisType safety, null checksLowgo vet, Rust compiler
Design by ContractPre/post/invariants checked at runtimeMediumEiffel, Clojure pre/post, assertions
Model checkingAll reachable states are safeHighTLA+, SPIN, Alloy
Deductive verificationMathematical proof of correctnessHighDafny, Lean, Coq
AI-assisted proof generationLoop invariants, lemmas, and annotations generated by LLMs,Low–Mediumdafny-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:

  1. Control flow analysis: what execution paths can the code take?
  2. Invariant discovery: what conditions hold regardless of which path it takes?
  3. 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:

  1. Programming language: loops, classes, generics, standard data structures
  2. Proof assistant: write lemmas and Dafny proves them automatically
  3. Program verifier: attach requires/ensures to 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 decreases clauses from BFS/iteration patterns the LLM recognizes

The feedback loop in practice:

  1. Human writes ValidStore capturing tenant isolation
  2. AI generates the AddPrincipal method in Go
  3. Dafny verifies the spec — or produces a counterexample
  4. If counterexample: human understands the bug (usually a missed invariant direction), refines the spec
  5. AI regenerates from the refined spec
  6. 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 verificationSkip it
Authorization and access controlUI rendering logic
Cryptographic protocolsCRUD boilerplate
Distributed consensusSimple data transformations
Financial calculationsUser-facing text content
Schema migration validatorsLogging and metrics
Safety-critical state machinesConfiguration 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 ValidXxx predicates 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:

LayerOwnerActivity
SpecificationHuman engineerDefines invariants, contracts, correctness properties
Code generationAI (LLM)Produces candidate implementations fast
VerificationFormal tools (Dafny, TLA+, Z3)Proves or refutes correctness mathematically
TestingProperty-based + fuzzCatches translation bugs between spec and implementation
ReviewHuman engineerReviews 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

  1. AWS: An Unexpected Discovery – Automated Reasoning Often Makes Systems More Efficient
  2. CACM: Systems Correctness Practices at Amazon Web Services
  3. CACM: AI for Software Engineering – From Probable to Provable
  4. Dafny: Teaching Program Verification at Amazon
  5. Galois: Automated Lean Proofs for Every Type
  6. Jane Street: Formal Methods
  7. Brooker: What’s Easy, What’s Hard for AI Agents
  8. Mager: The Valley of Calm
  9. Mager: The New Calculus of AI-Based Coding
  10. AI Writes Code, You Own the Design
  11. Beyond Vibe Coding – TLA+ with Claude
  12. Contract Testing for REST APIs
  13. TLA+ for the LLM Era
  14. Use Prolog to Improve LLM Reasoning
  15. Google OR-Tools CP-SAT for Scheduling
  16. you-got-skills: SDLC Skills for AI-Assisted Development
  17. ProVerB: Program Verification Book
  18. Loughridge et al. “DafnyBench: A Benchmark for Formal Software Verification.”

No Comments

No comments yet.

RSS feed for comments on this post. TrackBack URL

Sorry, the comment form is closed at this time.

Powered by WordPress