advertisement

BLAST

50 %
50 %
advertisement
Information about BLAST
Entertainment

Published on January 16, 2008

Author: Reginaldo

Source: authorstream.com

advertisement

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 predicate new=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.

Add a comment

Related presentations

Related pages

BLAST (Basic Local Alignment Search Tool)

The Basic Local Alignment Search Tool (BLAST) finds regions of local similarity between sequences. The program compares nucleotide or protein sequences to ...
Read more

dict.cc | blast | Wörterbuch Englisch-Deutsch

Übersetzung für blast im Englisch-Deutsch-Wörterbuch dict.cc.
Read more

Blast – Wikipedia

Blast bezeichnet: eine junge, nicht endgültig differenzierte Zelle, siehe Blast (Biologie) eine britische Literaturzeitschrift, siehe Blast (Zeitschrift)
Read more

BLAST-Algorithmus – Wikipedia

BLAST (Abk. für engl. Basic Local Alignment Search Tool) ist der Überbegriff für eine Sammlung der weltweit am meisten genutzten Programme zur Analyse ...
Read more

Nucleotide BLAST: Search nucleotide databases using a ...

Enter coordinates for a subrange of the query sequence. The BLAST search will apply only to the residues in the range.
Read more

BLAST | Partyband, Showband & Band für Firmenfeier Bayern

Die 10-köpfige Eventband & Partyband BLAST bietet professionelle Livemusik für Firmenfeier, Betriebsfest oder Live-Event in Bayern & ganz Deutschland.
Read more

Blast - definition of blast by The Free Dictionary

blast (blăst) n. 1. a. A very strong gust of wind or air. b. The effect of such a gust. 2. A forcible stream of air, gas, or steam from an opening ...
Read more

dict.cc Wörterbuch :: blast :: Deutsch-Englisch-Übersetzung

Englisch-Deutsch-Übersetzung für blast im Online-Wörterbuch dict.cc (Deutschwörterbuch).
Read more

Richtig blasen | Petra

Überraschen Sie ihn. Wichtig ist, dass Sie Spaß an der Sache haben. Halbherziges Blasen möchte kein Mann gerne. Beginnen Sie langsam, bringen Sie ihren ...
Read more