Bounded Model Checking — CBMC and Software Verification

In this tutorial, you'll learn about Bounded Model Checking. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Bounded Model Checking (BMC) verifies software by unrolling loops a finite number of times and converting the program into a SAT formula, enabling deep bug detection without explicit state enumeration.

Learning Path

flowchart LR
  A["Model Checking"] --> B["Bounded Model Checking
CBMC & SAT"]
  B --> C["Symbolic Execution"]
  B --> D["Industrial Formal Verification"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Model Checking basics, SAT solving, and C Programming fundamentals.

What Is Bounded Model Checking?

BMC converts a program with bounded loops into a SAT formula. If the formula is satisfiable, there exists an execution that reaches the error. The bound k limits loop iterations and recursion depth.

Step-by-Step: Loop Unwinding

Step 1: Write a Simple C Program

int find_max(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    assert(max >= arr[0]);
    return max;
}

Step 2: Unwind the Loop

For k=2 iterations, the loop body is duplicated:

def unwound_program(arr, n, k):
    max_val = arr[0]
    # Unrolled loop with bound k
    if k >= 1 and 1 < n:
        if arr[1] > max_val:
            max_val = arr[1]
    if k >= 2 and 2 < n:
        if arr[2] > max_val:
            max_val = arr[2]
    # Assertion
    return max_val >= arr[0]

# Test
arr = [5, 3, 7, 2]
print(f"Assertion holds (k=2): {unwound_program(arr, len(arr), 2)}")

Expected output:

Assertion holds (k=2): True

Step 3: Convert to SAT

Each program variable at each step becomes a fresh SAT variable:

from itertools import product

def program_to_sat(k):
    # Variables: arr0_i, max_i for each step i
    formulas = []
    # max_0 = arr0_0
    for i in range(k):
        # if arr_i > max_i then max_{i+1} = arr_i else max_{i+1} = max_i
        g = f"g_{i}"  # guard: arr_i > max_i
        formulas.append(f"({g} -> max_{i+1} = arr_{i})")
        formulas.append(f"(not {g} -> max_{i+1} = max_{i})")
    return " and ".join(formulas)

result = program_to_sat(3)
print(f"SAT encoding:\n{result}")

Expected output (truncated):

SAT encoding:
(g_0 -> max_1 = arr_0) and (not g_0 -> max_1 = max_0) and (g_1 -> max_2 = arr_1) and (not g_1 -> max_2 = max_1) and (g_2 -> max_3 = arr_2) and (not g_2 -> max_3 = max_2)

Step-by-Step: Using CBMC

Step 1: Install CBMC

sudo apt-get install cbmc

Step 2: Write a Verification Target

#include <assert.h>

int binary_search(int arr[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == key) return mid;
        if (arr[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    int arr[5] = {1, 3, 5, 7, 9};
    int result = binary_search(arr, 5, 5);
    assert(result == 2);
    return 0;
}

Step 3: Run CBMC

cbmc binary_search.c --function main --unwind 10 --bounds-check

Expected output:

** Results:
[main.assertion.1] assertion result == 2: SUCCESS
** 1 of 1 shown
** No failures, 1 successful verification

Common Errors

1. Insufficient Unwinding Bound

If the bound k is too small, the verification may miss bugs that occur only after more loop iterations. Increase k or use k-induction.

2. Ignoring Unwinding Assertions

CBMC adds assertions that loops do not exceed the bound. If these fail, increase --unwind.

3. Non-Determinism in Inputs

BMC needs nondeterministic inputs to explore all paths. Use CBMC's nondet_int() or assume() constructs.

4. Pointer Aliasing Complexity

BMC struggles with unrestricted pointer aliasing. Use CBMC's --pointer-check and restrict aliasing where possible.

5. Array Out-of-Bounds

BMC catches these with --bounds-check, but the formula size grows with array length. Use symbolic arrays when possible.

Practice Questions

Q1: What is the main limitation of BMC?

Completeness. BMC only checks up to bound k. Bugs requiring more than k iterations are missed unless k-induction is used.

Q2: How does CBMC handle malloc/free?

CBMC models dynamic allocation as bounded arrays. Use --malloc-may-fail to cover allocation failures.

Q3: What does --unwind do?

Sets the maximum number of times each loop is unwound. Larger values increase coverage but also formula size.

Q4: Can BMC prove correctness?

With k-induction and sufficient bound, BMC can prove correctness for properties with finite diameter. For many programs, a relatively small k suffices.

Q5: What is a CBMC unwinding assertion?

An assertion that the loop executed at most k times. If it fails, the bound was insufficient.

Challenge

Write a C function that computes the factorial of n using recursion. Use CBMC to verify that the result is always non-negative for n from 0 to 10. Set the recursion bound appropriately and handle the base case.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.