Programming Model Checking with SLAM

Presentation Transcript

Programming Model Checking with SLAM Thomas Ball Testing, Verification and Measurement Sriram K. Rajamani Software Productivity Tools Microsoft Research http://research.microsoft.com/hammer/

People behind SLAM Summer assistants Sagar Chaki, Todd Millstein, Rupak Majumdar (2000) Satyaki Das, Wes Weimer, Robby (2001) Jakob Lichtenberg, Mayur Naik (2002) Visitors Giorgio Delzanno, Andreas Podelski, Stefan Schwoon Windows Partners Byron Cook, Vladimir Levin, Abdullah Ustuner

Outline Part I: Overview (30 min) diagram of SLAM process showing (Static Driver Verifier) lessons adapted Part II: Basic SLAM (60 minutes) establishments fundamental calculations (no pointers) Part III: Advanced Topics (30 min) pointers + methods imprecision in associating and mod examination

Part I: Overview of SLAM

What is SLAM? Hammer is a product demonstrate checking venture at Microsoft Research Goal: Check C programs (framework programming) against wellbeing properties utilizing model checking Application area: gadget drivers Starting to be utilized inside Windows Working on making this into an item

Read for comprehension Drive testing instruments Precise API Usage Rules (SLIC) New API rules Defects Software Model Checking 100% way scope Rules Static Driver Verifier Development Testing Source Code

SLAM – Software Model Checking SLAM advancements boolean projects: another model for programming model creation (c2bp) show checking (bebop) display refinement (newton) SLAM toolbox based on MSR program investigation foundation

SLIC Finite state dialect for expressing rules screens conduct of C code transient security properties (security automata) commonplace C linguistic structure Suitable for communicating control-commanded properties e.g. appropriate arrangement of occasions can encode information values inside state

Locking Rule in SLIC state { enum {Locked,Unlocked} s = Unlocked; } KeAcquireSpinLock .passage { if (s==Locked) prematurely end ; else s = Locked; } KeReleaseSpinLock .section { if (s==Unlocked) prematurely end ; else s = Unlocked; } State Machine for Locking Rel Acq Unlocked Locked Rel Acq Error

The SLAM Process boolean program c2bp prog. P prog. P' slic bebop SLIC manage predicates way newton

Example Does this code comply with the locking guideline? do { KeAcquireSpinLock(); nPacketsOld = nPackets; if(request){ request = ask for >Next; KeReleaseSpinLock(); nPackets++; } while ( nPackets != nPacketsOld ); KeReleaseSpinLock();

Example Model checking boolean program (bebop) do { KeAcquireSpinLock(); if(*){ KeReleaseSpinLock(); } while (*); KeReleaseSpinLock(); U L U L U L U E

Example Is blunder way practical in C program? (newton) do { KeAcquireSpinLock(); nPacketsOld = nPackets; if(request){ request = ask for >Next; KeReleaseSpinLock(); nPackets++; } while ( nPackets != nPacketsOld ); KeReleaseSpinLock(); U L U L U L U E

Example Add new predicate to boolean program (c2bp) b : (nPacketsOld == nPackets) do { KeAcquireSpinLock(); nPacketsOld = nPackets; b = genuine; if(request){ request = ask for >Next; KeReleaseSpinLock(); nPackets++; b = b ? false : *; } while ( nPackets != nPacketsOld ); !b KeReleaseSpinLock(); U L U L U L U E

Example Model checking refined boolean program (bebop) b : (nPacketsOld == nPackets) do { KeAcquireSpinLock(); b = genuine; if(*){ KeReleaseSpinLock(); b = b ? false : *; } while ( !b ); KeReleaseSpinLock(); U L b L b L b U !b L U b L U b U E

Example Model checking refined boolean program (bebop) b : (nPacketsOld == nPackets) do { KeAcquireSpinLock(); b = genuine; if(*){ KeReleaseSpinLock(); b = b ? false : *; } while ( !b ); KeReleaseSpinLock(); U L b L b L b U !b L U b L b U

Observations about SLAM Automatic disclosure of invariants driven by property and a limited arrangement of (false) execution ways predicates are not invariants, but rather perceptions reflection + show checking figures inductive invariants (boolean mixes of perceptions) A half breed dynamic/static examination newton executes way through C code typically c2bp+bebop investigate all ways through deliberation another type of program cutting system code and information not significant to property are dropped non-determinism permits cuts to have more practices

Part I: Demo Static Driver Verifier comes about

Part I: Lessons Learned

SLAM Boolean program demonstrate has substantiated itself Successful for area of gadget drivers control-overwhelmed security properties couple of boolean factors expected to do evidence or discover genuine counterexamples Counterexample-driven refinement ends practically speaking inadequacy of hypothesis prover not an issue

What is hard? Abstracting from a dialect with pointers (C) to one without pointers (boolean projects) All symptoms should be demonstrated by duplicating (as in dataflow) Open environment issue

What remained settled? Boolean program display Basic apparatus stream Repercussions: newton needs to duplicate between extensions c2bp needs to model reactions by esteem result limited profundity accuracy on the stack is all boolean projects can do

What changed? Interface amongst newton and c2bp We now utilize predicates for accomplishing more things refine nom de plume accuracy by means of associating predicates newton determines pointer associating imprecision in c2bp

Scaling SLAM Largest driver we have prepared has ~60K lines of code Largest deliberations we have investigated have a few hundred boolean factors Routinely get comes about after 20-30 emphasess Out of 672 runs we do day by day, 607 end inside 20 minutes

Scale and SLAM segments Out of 67 runs that time out, devices that take longest time: bebop: 50, c2bp: 10, newton: 5, compel: 2 C2bp: quick predicate reflection (fastF) and incremental predicate reflection (oblige) re-use crosswise over cycles Newton: most concerning issues are because of extension duplicating Bebop: greatest issue is no re-use crosswise over emphasess arrangement in progress

SLAM Status 2000-2001 establishments, calculations, prototyping papers in CAV, PLDI, POPL, SPIN, TACAS March 2002 Bill Gates audit May 2002 Windows resolved to contract two individuals with model checking foundation to bolster Static Driver Verifier (SLAM+driver rules) July 2002 running SLAM on 100+ drivers, 20+ properties September 3, 2002 made introductory arrival of SDV to Windows (loved ones) April 1, 2003 made wide arrival of SDV to Windows (any inward driver engineer)

Part II: Basic SLAM

C-Types  ::= void | bool | int | ref  Expressions e ::= c | x | e 1 operation e 2 | &x | *x LExpression l ::= x | *x Declaration d ::=  x 1 ,x 2 ,… ,x n Statements s ::= skip | goto L 1 ,L 2 … L n | L: s | assume( e ) | l = e | l = f ( e 1 , e 2 ,… , e n ) | return x | s 1 ; s 2 ;… ; s n Procedures p ::=  f ( x 1 :  1 ,x 2 :  2 ,… ,x n :  n ) Program g ::= d 1 d 2 … d n p 1 p 2 … p n

C- - Types  ::= void | bool | int Expressions e ::= c | x | e 1 operation e 2 LExpression l ::= x Declaration d ::=  x 1 ,x 2 ,… ,x n Statements s ::= skip | goto L 1 ,L 2 … L n | L: s | assume( e ) | l = e | f ( e 1 , e 2 ,… , e n ) | return | s 1 ; s 2 ;… ; s n Procedures p ::= f ( x 1 :  1 ,x 2 :  2 ,… ,x n :  n ) Program g ::= d 1 d 2 … d n p 1 p 2 … p n

BP Types  ::= void | bool Expressions e ::= c | x | e 1 operation e 2 LExpression l ::= x Declaration d ::=  x 1 ,x 2 ,… ,x n Statements s ::= skip | goto L 1 ,L 2 … L n | L: s | assume( e ) | l = e | f ( e 1 , e 2 ,… , e n ) | return | s 1 ; s 2 ;… ; s n Procedures p ::= f ( x 1 :  1 ,x 2 :  2 ,… ,x n :  n ) Program g ::= d 1 d 2 … d n p 1 p 2 … p n

Syntactic sugar goto L1, L2; L1: accept( e ); S1 ; goto L3; L2: expect(! e ); S2 ; goto L3; L3: S3; if ( e ) { S1 ; } else { S2 ; } S3;

Example, in C void cmp (int a , int b) { if (a == b) g = 0; else g = 1; } int g; main(int x, int y){ cmp(x, y); if (!g) { if (x != y) assert(0); }

Example, in C- - int g; main(int x, int y){ cmp(x, y); assume(!g); assume(x != y) assert(0); } void cmp(int a , int b) { goto L1, L2; L1: assume(a==b); g = 0; return; L2: assume(a!=b); g = 1; return; }

The SLAM Process boolean program c2bp prog. P prog. P' slic bebop SLIC govern predicates way newton

c2bp: Predicate Abstraction for C Programs Given P : a C program F = { e 1 ,...,e n } every e i an unadulterated boolean expression every e i speaks to set of states for which e i is genuine Produce a boolean program B( P , F ) same control-stream structure as P boolean vars { b 1 ,...,b n } to coordinate { e 1 ,...,e n } properties valid for B(P,F) are valid for P

Assumptions Given P : a C program F = { e 1 ,...,e n } every e i an immaculate boolean expression every e i