Programming Model Checking with SLAM

Software model checking with slam l.jpg
1 / 98
0
0
1118 days ago, 486 views
PowerPoint PPT Presentation

Presentation Transcript

Slide 1

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

Slide 2

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

Slide 3

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

Slide 4

Part I: Overview of SLAM

Slide 5

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

Slide 6

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

Slide 7

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

Slide 8

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

Slide 9

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

Slide 10

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

Slide 11

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();

Slide 12

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

Slide 13

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

Slide 14

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

Slide 15

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

Slide 16

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

Slide 17

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

Slide 18

Part I: Demo Static Driver Verifier comes about

Slide 19

Part I: Lessons Learned

Slide 20

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

Slide 21

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

Slide 22

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

Slide 23

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

Slide 24

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

Slide 25

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

Slide 26

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)

Slide 27

Part II: Basic SLAM

Slide 28

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

Slide 29

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

Slide 30

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

Slide 31

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;

Slide 32

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); }

Slide 33

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; }

Slide 34

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

Slide 35

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

Slide 36

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

SPONSORS