BLAST

BLAST-A Model Checker for C: 

BLAST-A Model Checker for C Developed by Thomas A. Henzinger (EPFL) Rupak Majumdar (UC Los Angeles) Ranjit Jhala (UC San Diego) Dirk Beyer (Simon Fraser University) Presented by Sowmya Venkateswaran

BLAST Installation: 

BLAST Installation Currently version 2.0 src files available. http://mtc.epfl.ch/software-tools/blast/ Installation Download Simplify theorem prover http://www.cs.virginia.edu/~weimer/615/hw.html Either build from src files or use Linux binaries. A “working” example configuration for compiling Blast 2.0 is OCaml 3.08.3 and gcc (GCC) 3.4.4 20050721 (Red Hat 3.4.4-2).

Features: 

Features “On the Fly” Abstraction Automatic abstraction Smarter predicate discovery Verify safety properties, assertion violations Finding reachable program locations Detecting dead code Reuse saved abstractions

Problems: 

Problems Installing and making it work Predicate discovery not good enough. Checking concurrent programs Eclipse plugin Checking recursive functions

BLAST working: 

BLAST working Build an abstract model using predicate abstraction. Check for reachability of a specified label using the abstract model. If no path to ERR node-system safe. If path is feasible, output error trace. Else use infeasibility of path to refine abstract model.

BLAST working: 

BLAST working CIL Infrastructure C Program Property spec.opt Instrumented C file with error label Lazy Abstraction CFA Forward Search Phase ART Error node unreachable; program safe Backward counterexample analysis Refine Add Predicates

Problem: Abstraction is expensive: 

Problem: Abstraction is expensive # of abstract states=2# of predicates Solution 1: Only abstract reachable states Solution 2: Don’t refine any error free states Advantages: State space only refined as much as required. Reuse previously defined error free states.

Lazy Abstraction: 

Lazy Abstraction Integrate the following Abstraction Verification Counterexample-driven refinement Find pivot state. Construct, verify and refine abstract model “on the fly” from pivot state on. Forward Search Phase and Backward Counterexample analysis. Stop when either real counterexample found or system found safe

Locking example: 

Locking example

Control Flow Automaton: 

Control Flow Automaton Local and global variables of C program Vertices: control locations of a function. Labeled directed edges Basic block of instructions. Assume predicate for branch condition. Formally, CFA is a tuple <Q,q0,X,Ops,→> Q- finite set of control locations q0-initial control location X- set of variables Ops- set of operations on X (lval=exp or [p]) →∈(Q x Ops x Q)

Control Flow Automaton: 

Control Flow Automaton

Forward Search Phase: 

Forward Search Phase Abstract reachability tree in dfs order. Constructed from CFA. Vertices in CFA are nodes in ART. Labels of nodes are reachable regions. Reachable region obtained from parent’s reachable region and instructions on the edge between them. Finite set of predicates per node. Reachable region is a boolean combination of set of predicates

Forward Search for locking example: 

Forward Search for locking example 1 LOCK=0 2 [T] LOCK=0 lock() old=new 3 LOCK=1 4 [T] LOCK=1 5 unlock() new++ LOCK=0 [new=old] 6 LOCK=0 unlock() ERR LOCK=0 Is this a valid counterexample??

Weakest Precondition: 

Weakest Precondition WP(P,Op) –weakest formula P` s.t. if P` is T before Op, then P is T after Op Assign x=e P P [e / x ] new+1=old new=new + 1 new=old

Weakest Precondition: 

Weakest Precondition WP(P,Op) –weakest formula P` s.t. if P` is T before Op, then P is T after Op Assume [C] P C ^ P new = old [ new=old ] new=old

Backward Counterexample Analysis: 

Backward Counterexample Analysis For each tree node, find a bad region. Bad region of ERR node=T Other nodes=WP of bad region of child w.r.t instructions on edge between the 2. Start from ERR node Pivot node - First node in the tree where Bad region ∩ Reachable region=φ Refine abstraction from pivot node onwards

Counter example analysis for locking program: 

Counter example analysis for locking program 1 LOCK=0 2 [T] LOCK=0 lock() old=new 3 LOCK=1 4 [T] LOCK=1 5 unlock() new++ LOCK=0 [new=old] 6 LOCK=0 unlock() ERR LOCK=0 {LOCK=0} { LOCK=0 & new=old } { LOCK=1 & new+1=old } { LOCK=1 & new+1=old } { LOCK=0 & new+1=new } {T}

Searching with new predicatenew=old: 

Searching with new predicate new=old 1 LOCK=0 2 [T] LOCK=0 3 LOCK=1 & new=old 4 5 LOCK=0& !new=old 2 6 5 2 6 [T] [T] [new!=old] LOCK=1 & new=old LOCK=1 & new=old [new=old] RET unlock() LOCK=0 & new=old False False LOCK=0 Program Safe!!

Finding Predicates: 

Finding Predicates Problem: How many predicates to find? # of predicates grows with program size 2n abstract states!! p1 p2 pn Solution: Use predicates only where needed 2n abstract states

Counter example Traces: 

Counter example Traces 1:x=ctr; 2:ctr=ctr+1; 3:y=ctr; 4: if (x=i-1) { 5: if (y!=i){ ERROR; }} 1: x=ctr; 2: ctr=ctr+1; 3: y=ctr; 4: assume (x=i-1) 5: assume (y!=i) Theorem: Trace formula is satisfiable iff trace is feasible. Counter example trace Sample program 1:x1=ctr0 2:ctr1=ctr0+1 3:y1=ctr1 4:x1=i0-1 5:y1!=i0 Trace Formula φ Trace formula is a conjunction of constraints, one per instruction in the trace.

Steps in Refine Stage: 

Steps in Refine Stage Counter example trace Trace formula Proof of Unsatisfiability Theorem Prover Interpolate Predicate Map

Finding what predicates are needed: 

Finding what predicates are needed 1: x=ctr; 2: ctr=ctr+1; 3: y=ctr; 4: assume (x=i-1) 5: assume (y!=i) 1:x1=ctr0 2:ctr1=ctr0+1 3:y1=ctr1 4:x1=i0-1 5:y1!=i0 What predicate is needed for trace to become infeasible Trace Trace Formula Given an infeasible trace t, find a set of predicates P, such that t is abstractly infeasible w.r.t P.

Slide23: 

Partition φ into φ- (trace prefix) and φ+ (trace suffix) Find an interpolant Ψ s.t φ- implies Ψ Ψ ^ φ+ is unsatisfiable. The variables of Ψ are common to both φ- and φ+ Use interpolant to construct predicate map. Finding what predicates are needed

Interpolant = Predicate: 

Interpolant = Predicate 1:x1=ctr0 2:ctr1=ctr0+1 3:y1=ctr1 4:x1=i0-1 5:y1!=i0 Trace Formula φ- φ+ Interpolate φ Predicate at 4: y=x+1 Predicate is ..implied by Trace formula prefix ..on common variables ..makes Trace Formula suffix unfeasible x1 y1 y1 x1

Finding predicate map: 

Finding predicate map Partition at each point Interpolate at each partition Construct predicate map pci  Interpolant from partition i Trace Trace Formula 1: x=ctr; 2: ctr=ctr+1; 3: y=ctr; 4: assume (x=i-1) 5: assume (y!=i) 1:x1=ctr0 2:ctr1=ctr0+1 3:y1=ctr1 4:x1=i0-1 5:y1!=i0 φ- φ+ Interpolate x1=ctr0 Predicate Map 2: x1=ctr0

Slide26: 

Partition at each point Interpolate at each partition Construct predicate map pci  Interpolant from partition i Trace Trace Formula 1: x=ctr; 2: ctr=ctr+1; 3: y=ctr; 4: assume (x=i-1) 5: assume (y!=i) 1:x1=ctr0 2:ctr1=ctr0+1 3:y1=ctr1 4:x1=i0-1 5:y1!=i0 φ- φ+ Interpolate x1=ctr1-1 Predicate Map 2: x1=ctr0 3: x1=ctr1-1 Finding predicate map

Finding predicate map: 

Finding predicate map Partition at each point Interpolate at each partition Construct predicate map pci  Interpolant from partition i Trace Trace Formula 1: x=ctr; 2: ctr=ctr+1; 3: y=ctr; 4: assume (x=i-1) 5: assume (y!=i) 1:x1=ctr0 2:ctr1=ctr0+1 3:y1=ctr1 4:x1=i0-1 5:y1!=i0 φ- φ+ Interpolate y1=x1+1 Predicate Map 2: x1=ctr0 3: x1=ctr1-1 4: y1=x1+1

Finding predicate map: 

Finding predicate map Partition at each point Interpolate at each partition Construct predicate map pci  Interpolant from partition i Trace Trace Formula 1: x=ctr; 2: ctr=ctr+1; 3: y=ctr; 4: assume (x=i-1) 5: assume (y!=i) 1:x1=ctr0 2:ctr1=ctr0+1 3:y1=ctr1 4:x1=i0-1 5:y1!=i0 φ- φ+ Interpolate y1=i0 Predicate Map 2: x1=ctr0 3: x1=ctr1-1 4: y1=x1+1 5: y1=i0

BLAST Specification language: 

BLAST Specification language Include directives Global variables Shadowed types Events Pattern Guard Action/Repair Before/After

References: 

References “Abstractions from Proofs”-Thomas .H et al. “The Blast query language for software verification”- Dirk Beyer et al. “Lazy Abstraction”-Gregoire Sutre et al.