Skip to content

mohitmishra786/low-level-dev-skills / skills/runtimes/formal-verification

formal-verification

Verified

Formal verification skill for systems code in Rust and C. Use when proving absence of panics, overflow or out-of-bounds access, writing Kani proof harnesses or function contracts, bounded model checking C with CBMC, proving ACSL contracts with Frama-C WP, or choosing between model checking, deductive verification, fuzzing and Miri. Activates on queries about Kani, cargo kani, kani::any, CBMC, nondet, unwinding assertion, Frama-C, ACSL, WP, EVA, Verus, Creusot, ESBMC, or formal verification.

Formal Verification for Systems Code

Purpose

Guide agents through practical formal verification of Rust and C (checked with Kani 0.68, CBMC 6.6 and Frama-C 33.0): choosing a tool, writing harnesses and contracts, reading counterexamples, and fixing the common failures.

Triggers

  • "How do I prove this Rust function can't panic or overflow?"
  • "How do I write a Kani proof harness?"
  • "How do I model check C code with CBMC?"
  • "What does 'unwinding assertion' mean?"
  • "How do I prove an ACSL contract with Frama-C?"
  • "Should I use fuzzing, Miri or a model checker?"

Workflow

1. Choosing a tool

ToolLanguageTechniqueProves
KaniRustBounded model checking (CBMC backend)No panics, overflow, UB in unsafe; user assert!s; function contracts
CBMCC/C++Bounded model checkingBounds, pointer, overflow checks; user asserts, up to a loop bound
ESBMCC/C++Bounded model checking (SMT)Similar to CBMC
Frama-C WPCDeductive (ACSL contracts → provers)Full contracts for all inputs, loops via invariants
Frama-C EVACAbstract interpretationAbsence of runtime errors, sound but may raise false alarms
Verus, CreusotRustDeductiveFull functional correctness, needs specs and invariants
What do you need?
├── Find bugs fast, any input → fuzzing (skills/runtimes/fuzzing)
├── Check one execution for UB in unsafe Rust → Miri
├── Prove a property for ALL inputs, bounded loops → Kani (Rust) / CBMC (C)
├── Prove a C contract for all inputs, unbounded loops → Frama-C WP
└── Prove a whole C program free of runtime errors → Frama-C EVA

Bounded model checkers are exhaustive up to the loop bound you give them. Code with unbounded loops needs a bound plus an unwinding assertion, or contracts and invariants.

2. Kani: proof harnesses

cargo install --locked kani-verifier
cargo kani setup              # downloads the pinned toolchain and CBMC (needs rustup, curl)
cargo kani                    # run every #[kani::proof] in the crate
cargo kani --harness ring_fifo_order
// src/lib.rs
pub struct Ring<const N: usize> {
    head: usize,
    len: usize,
    buf: [u8; N],
}

impl<const N: usize> Ring<N> {
    pub fn new() -> Self { Ring { head: 0, len: 0, buf: [0; N] } }

    pub fn push(&mut self, v: u8) -> bool {
        if self.len == N { return false; }
        let tail = (self.head + self.len) % N;
        self.buf[tail] = v;
        self.len += 1;
        true
    }

    pub fn pop(&mut self) -> Option<u8> {
        if self.len == 0 { return None; }
        let v = self.buf[self.head];
        self.head = (self.head + 1) % N;
        self.len -= 1;
        Some(v)
    }
}

/// Midpoint with a classic overflow bug.
pub fn midpoint(a: u32, b: u32) -> u32 { (a + b) / 2 }

/// Fixed version.
pub fn midpoint_fixed(a: u32, b: u32) -> u32 { a / 2 + b / 2 + (a % 2 + b % 2) / 2 }

#[cfg(kani)]
mod proofs {
    use super::*;

    #[kani::proof]
    fn midpoint_no_overflow() {
        let a: u32 = kani::any();        // every possible u32
        let b: u32 = kani::any();
        let _ = midpoint(a, b);          // Kani reports the overflow
    }

    #[kani::proof]
    fn midpoint_fixed_correct() {
        let a: u32 = kani::any();
        let b: u32 = kani::any();
        let m = midpoint_fixed(a, b);
        assert!(m >= a.min(b) && m <= a.max(b));
        assert_eq!(m as u64, (a as u64 + b as u64) / 2);
    }

    #[kani::proof]
    #[kani::unwind(5)]                   // loops run at most 4 times
    fn ring_fifo_order() {
        let mut r: Ring<4> = Ring::new();
        let n: usize = kani::any();
        kani::assume(n <= 4);            // restrict the input space
        for i in 0..n { assert!(r.push(i as u8)); }
        for i in 0..n { assert_eq!(r.pop(), Some(i as u8)); }
        assert_eq!(r.pop(), None);
    }
}
# Cargo.toml: silence the unknown-cfg warning for `cfg(kani)`
[lints.rust]
unexpected_cfgs = { level = "warn", check-cfg = ['cfg(kani)'] }
Checking harness proofs::midpoint_no_overflow...
Failed Checks: attempt to add with overflow
VERIFICATION:- FAILED
...
Complete - 3 successfully verified harnesses, 1 failures, 4 total.

cargo kani -Z concrete-playback --harness midpoint_no_overflow --concrete-playback=print prints a #[test] that reproduces the failing inputs.

3. Kani: function contracts

Contracts let Kani check a function once and reuse its specification at call sites:

#[cfg_attr(kani, kani::requires(divisor != 0))]
#[cfg_attr(kani, kani::ensures(|r: &u32| *r <= dividend))]
pub fn safe_div(dividend: u32, divisor: u32) -> u32 { dividend / divisor }

#[cfg(kani)]
#[kani::proof_for_contract(safe_div)]
fn safe_div_contract() {
    let _ = safe_div(kani::any(), kani::any());   // inputs constrained by `requires`
}
# Contracts are unstable: without the flag the crate fails to compile
cargo kani -Z function-contracts
# error otherwise: Using the proof_for_contract attribute requires activating
#                  the unstable `function-contracts` feature

Callers' harnesses can then use #[kani::stub_verified(safe_div)] to replace the body with its contract (cargo kani -Z function-contracts -Z stubbing).

4. CBMC: bounded model checking C

/* ring.c — fixed-size ring buffer with an off-by-one bug in ring_push */
#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>

#define CAP 4

struct ring {
    uint8_t buf[CAP];
    size_t head, len;
};

bool ring_push(struct ring *r, uint8_t v)
{
    if (r->len > CAP)                 /* BUG: should be >= */
        return false;
    r->buf[(r->head + r->len) % CAP] = v;
    r->len++;
    return true;
}

bool ring_pop(struct ring *r, uint8_t *out)
{
    if (r->len == 0)
        return false;
    *out = r->buf[r->head];
    r->head = (r->head + 1) % CAP;
    r->len--;
    return true;
}
/* harness.c — CBMC proof harness: any sequence of up to 6 pushes/pops */
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>

#define CAP 4
struct ring { uint8_t buf[CAP]; size_t head, len; };
bool ring_push(struct ring *r, uint8_t v);
bool ring_pop(struct ring *r, uint8_t *out);

bool nondet_bool(void);        /* CBMC treats undefined nondet_* functions as "any value" */
uint8_t nondet_u8(void);

int main(void)
{
    struct ring r = { .head = 0, .len = 0 };
    for (int i = 0; i < 6; i++) {
        if (nondet_bool()) {
            ring_push(&r, nondet_u8());
        } else {
            uint8_t v;
            ring_pop(&r, &v);
        }
        assert(r.len <= CAP);          /* invariant */
        assert(r.head < CAP);
    }
    return 0;
}
cbmc harness.c ring.c \
    --bounds-check --pointer-check --signed-overflow-check --unsigned-overflow-check \
    --unwind 7 --unwinding-assertions
# [main.assertion.1] line 25 assertion r.len <= CAP: FAILURE
# VERIFICATION FAILED

# Counterexample: the sequence of states leading to the failure
cbmc harness.c ring.c --bounds-check --pointer-check --unwind 7 --unwinding-assertions --trace
#   r.len=5ul ...  Violated property: file harness.c function main line 25

# After fixing `>` to `>=`:  ** 0 of 75 failed  /  VERIFICATION SUCCESSFUL

--unwind N must exceed the iteration count of every loop. With --unwinding-assertions, a bound that is too small is reported (unwinding assertion loop 0: FAILURE) instead of silently skipping paths. For multi-file builds use goto-cc to produce a goto binary, then run cbmc on it.

5. Frama-C WP: deductive proof of ACSL contracts

/* abs.c — prove the contract, including absence of overflow */
#include <limits.h>

/*@ requires x > INT_MIN;
    assigns \nothing;
    ensures \result >= 0;
    ensures x >= 0 ==> \result == x;
    ensures x <  0 ==> \result == -x;
*/
int my_abs(int x)
{
    return x < 0 ? -x : x;
}

/*@ requires n >= 0 && \valid_read(a + (0 .. n-1));
    assigns \nothing;
    ensures \forall integer i; 0 <= i < n ==> \result >= a[i];
*/
int max_of(const int *a, int n)
{
    int m = INT_MIN;
    /*@ loop invariant 0 <= i <= n;
        loop invariant \forall integer j; 0 <= j < i ==> m >= a[j];
        loop assigns i, m;
        loop variant n - i;
    */
    for (int i = 0; i < n; i++)
        if (a[i] > m) m = a[i];
    return m;
}
# -wp-rte adds runtime-error goals (overflow, division by zero, invalid access)
frama-c -wp -wp-rte abs.c
# [wp] Proved goals:   22 / 22

# Without `requires x > INT_MIN`, the overflow goal cannot be proved:
# [wp] [Timeout] typed_my_abs_assert_rte_signed_overflow
# [wp] Proved goals:    2 / 3

Loops need loop invariant, loop assigns and a loop variant (termination). A goal that times out is either false or needs a stronger invariant; try -wp-timeout 30 before rewriting. Frama-C publishes framac/frama-c Docker images (amd64); distributions often lag behind.

6. Frama-C EVA: absence of runtime errors

EVA analyses a whole program from main. Use Frama_C_interval for nondeterministic inputs and ACSL assertions for properties:

#include "__fc_builtin.h"   /* Frama_C_interval */
/* ... same ring declarations as the CBMC harness ... */
int main(void)
{
    struct ring r = { .head = 0, .len = 0 };
    for (int i = 0; i < 6; i++) {
        if (Frama_C_interval(0, 1))
            ring_push(&r, (uint8_t)Frama_C_interval(0, 255));
        else { uint8_t v; ring_pop(&r, &v); }
        //@ assert r.len <= CAP;
        //@ assert r.head < CAP;
    }
    return 0;
}
frama-c -eva -eva-precision 3 harness_eva.c ring.c
# buggy ring:  [eva:alarm] harness_eva.c:24: Warning: assertion got status unknown.
# fixed ring:  100% of the logical properties reached have been proven.

Comments inside a //@ annotation are a parse error (unexpected block-comment opening).

7. Running proofs in CI

  • Keep harnesses small and focused; a harness per function or invariant parallelizes well.
  • Pin tool versions (cargo install kani-verifier --version ..., a Frama-C image tag).
  • Kani: cargo kani --output-format terse prints a compact summary; make the job fail when any harness fails.
  • CBMC: commit the exact command line with --unwind values next to the harness.
  • Use proofs alongside fuzzing: fuzzers cover unbounded behaviour, proofs cover all inputs within bounds.

8. Common problems

SymptomCauseFix
unwinding assertion loop N: FAILURE--unwind/#[kani::unwind] below the loop's iteration countRaise the bound, or constrain inputs with assume
Kani/CBMC runs for hoursState space too large (big arrays, deep loops, many nondet values)Smaller bounds, smaller types, stubs for heavy functions
proof_for_contract ... requires activating the unstable function-contracts featureContracts are unstable in Kanicargo kani -Z function-contracts
Kani check unsupported_constructCode Kani cannot model (some intrinsics, foreign calls)#[kani::stub(f, f_stub)] with -Z stubbing, or a contract
cargo kani setup fails downloadingNo curl, or CARGO_HOME without rustupInstall curl; keep the default rustup/cargo homes
WP goal TimeoutGoal is false, or invariant too weakCheck with a counterexample tool, strengthen invariants, raise -wp-timeout
EVA alarm on CBMC-style nondet_*()EVA has no spec for undefined functionsUse Frama_C_interval from __fc_builtin.h

Related skills

  • Use skills/runtimes/fuzzing for finding bugs with libFuzzer/AFL and cargo-fuzz
  • Use skills/rust/rust-sanitizers-miri for Miri and sanitizers on Rust code
  • Use skills/rust/rust-unsafe for the invariants Kani checks in unsafe code
  • Use skills/build-systems/static-analysis for clang-tidy, cppcheck and other analyzers
reverse-engineer-anythingmorluto/reaReverse engineer native, managed, Electron/JavaScript, packaged, firmware, and browser targets with REA, and build agent environments (AgentEnv bundles) of web applications from a live instance or a capture, and of Linux desktop apps with a task from a request. Use shipped-artifact or requested runtime evidence to explain features, compare versions, decompile code, or guide a reconstruction. Skip REA for ordinary source-repository architecture analysis.Stars: 471kUpdated Claude CodeCodexVerifiedInstall
diagnosing-superpowersobra/superpowersUse when a superpowers session went wrong and your human partner wants to know why — repeated work, ignored plans, stumbles, poor results, a skill that didn't fire, "it took too long", "why is it so expensive", "what is it doing" — or wants to build a bug report for the superpowers maintainers, for the current session or a past one identified by id or path, on any harness.Stars: 322kUpdated Claude CodeCodexVerifiedInstall
dispatching-parallel-agentsobra/superpowersUse when facing 2+ independent tasks that can be worked on without shared state or sequential dependenciesStars: 322kUpdated Claude CodeCodexVerifiedInstall
executing-plansobra/superpowersUse when executing an implementation plan in the current session as the implementer yourself — your human partner chose inline execution, or no subagent tool is availableStars: 322kUpdated Claude CodeCodexVerifiedInstall