Destruction: An exact and adaptable verifier for frameworks programming

Havoc a precise and scalable verifier for systems software l.jpg
1 / 39
0
0
959 days ago, 539 views
PowerPoint PPT Presentation
Teammates. ResearchersJeremy Condit, Shuvendu LahiriInternsShaunak Chatterjee, Brian Hackett, Zvonimir Rakamaric, Ian Wehrman, Thomas Wies. Destruction. Secluded verifier for C programsVerifies every system separatelyRequires contracts: preconditions, postconditions, adjusts provisos, circle invariantsFeaturesAccurate pile modelExpressive annotation languageEfficient checking utilizing SMT solversPrecise

Presentation Transcript

Slide 1

Devastation: An exact and adaptable verifier for frameworks programming Shaz Qadeer Microsoft Research

Slide 2

Collaborators Researchers Jeremy Condit, Shuvendu Lahiri Interns Shaunak Chatterjee , Brian Hackett, Zvonimir Rakamaric , Ian Wehrman , Thomas Wies

Slide 3

HAVOC Modular verifier for C programs Verifies every methodology independently Requires contracts: preconditions, postconditions , adjusts provisions, circle invariants Features Accurate stack demonstrate Expressive comment dialect Efficient checking utilizing SMT solvers Precise and proficient thinking for circle free and sans call code

Slide 4

Annotated C program Visual C Front End Control stream diagram CtoBoogiePL Memory show Boogie program Boogie VCGenerator Verification condition Z3 SMT solver Verified Warning

Slide 5

Challenges for HAVOC Concise and exact articulation of non-associating and disjointness of store qualities Properties of unbounded accumulations Lists, Arrays, … Enable such thinking for low-level programming pointer number-crunching inside pointers settled structures and unions …

Slide 6

But will developers ever compose contracts? At times, they may security properties: a great many cradle comments in Windows code upkeep of basic legacy code: the Windows NT record framework Automatic comment derivation exact and effective checking of clarified projects is a critical initial step

Slide 7

Roadmap Novel elements of the determination dialect Dealing with low-level components of C Concluding comments

Slide 8

log_list.head log_list.tail next prev LinkNode information singe * channel_name file_name logtype struct _logentry [muh: Internet Relay Chat (IRC) bouncer]

Slide 9

LinkNode *iter = log_list.head; while (iter != invalid) { struct _logentry *entry = iter->data; free (passage >channel_name); free (section >file_name); free (section); section = NULL; iter = iter->next; } Ensure nonattendance of twofold free Data structure invariant Reachability predicate For each hub x in the rundown amongst log_list.head and invalid : x->data is an extraordinary pointer , and x->data->channel_name is an interesting pointer , and x->data->file_name is a one of a kind pointer . All inclusive measurement

Slide 10

Limitations of SMT solvers No support for exact prevailing upon reachability predicate Incompleteness in Floyd-Hoare proofs for straight line code Brittle support for quantifiers Complexity: NP-finish (ground)  undecidable Leads to capricious conduct of verifiers Proof circumstances, confirmation achievement rate Requires client inventiveness to specialty adages/invariants with quantifiers

Slide 11

Contribution Expressive and productive rationale for exact thinking about reachability , one of a kind pointers, and confined evaluation A choice method for the rationale worked over a SMT solver

Slide 12

Simple Java-like memory model Heap comprises of an arrangement of items ( obj ) Each field "f" is a variable guide f: obj  obj g: obj  int h: obj  bool The sort obj might be refined into a gathering of sorts

Slide 13

Reachability predicate: Btwn f next x y prev information Btwn next (x,y) Btwn prev (y,x)

Slide 14

Inverse of a capacity: f - 1 next x y prev information w information - 1 (w) = {x, y}

Slide 15

LinkNode *iter = log_list.head; while (iter != invalid) { struct _logentry *entry = iter->data; free (passage >channel_name); free (section >file_name); free (passage); section = NULL; iter = iter->next; } Data structure invariant For each hub x in the rundown amongst log_list.head and invalid : x->data is a one of a kind pointer , and … .  x  Btwn f (log_list.head, invalid) \ {null}. information - 1 (data(x)) = {x} … .

Slide 16

Expressive rationale Express properties of accumulations  x  Btwn (f( hd ), hd ). state(x) = LOCKED/cyclic Arithmetic thinking on information (e.g. sortedness )  x  Btwn f ( hd , invalid) \ {null}. y  Btwn f (x, invalid) \ {null}. d(x)  d(y)

Slide 17

Precise Need comments/reflections just at technique/circle limits Given the Floyd-Hoare triple X = {P} S {Q} P and Q are communicated in our rationale S is a circle free without call program We can develop an equation Y in our rationale Y is straight in the extent of X is substantial iff Y is legitimate

Slide 18

Efficient Decision issue is NP-finished Can't expect any better with propositional rationale! Holds the multifaceted nature of current SMT rationales Provide a choice method for the rationale on top of cutting edge Z3 SMT solver Leverages effective ground-hypothesis thinking (number-crunching, exhibits, uninterpreted capacities… )

Slide 19

Ground Logic t  Term ::= c | x | t 1 + t 2 | t 1 - t 2 | f(t) G  GFormula ::= t = t' | t < t' | t  Btwn f (t 1 , t 2 ) | G S  Set ::= f - 1 (t) | Btwn f (t 1 , t 2 ) F  Formula ::= G | F 1  F 2 |F 1  F 2 | x  S. F

Slide 20

Ground choice system Provide an arrangement of 10 revamp rules for Btwn f Sound, finish and ending E.g. Transitivity3 t 1  Btwn f (t 0 , t 2 ) t  Btwn f (t 0 , t 1 ) t  Btwn f (t 0 , t 2 ), t 1  Btwn f (t, t 2 )

Slide 21

t  Term ::= c | x | t 1 + t 2 | t 1 - t 2 | f(t) G  GFormula ::= t = t' | t < t' | t  Btwn f (t 1 , t 2 ) | G Logic Bounded measurement over translated sets S  Set ::= f - 1 (t) | Btwn f (t 1 , t 2 ) F  Formula ::= G | F 1  F 2 |F 1  F 2 | x  S. F

Slide 22

Lazy quantifier Instantiation govern t  S x  S. F F[t/x] Lazy instantiation Instantiate just when a term t has a place with the set S Substantially diminishes the quantity of terms to instantiate an evaluated reality Terminates if x  S. F is sort-confined sort(x) is not as much as sort(t[x]) for any term t[x] in F

Slide 23

Experience Compared with a before execution Unrestricted quantifiers, fragmented axiomatization of reachability , no f - 1 Small to medium estimated benchmarks Greatly enhanced the consistency of HAVOC Reduced runtimes (2X – 100X) Eliminate requirement for painstakingly made aphorisms and invariants Can deal with more current cases

Slide 24

Roadmap Novel elements of the detail dialect Dealing with low-level components of C Concluding comments

Slide 25

p struct list { list *next; list * prev ; }; struct record { int data1; list hub; int data2; }; q record data1 next prev data2 data1 next prev data2 q = CONTAINER(p , record, hub) = (record *) (( int *) p – ( int ) (&(((record *)0) node))) = (record *) (( int *) p – 1)

Slide 26

void init_all_records (list *p) { while (p != NULL) { init_record (p); p = p->next; } void init_record (list *p) { record *r = CONTAINER(p, record, hub); r->data2 = 42; } Type wellbeing requires nontrivial thinking the holder of each component in rundown has sort record* Use of memory model with field deliberation is unsound Field reflection is critical to all property checkers &a->data1 is not associated to &b->data2 init_all_records (p) protects the declaration a->data1 == 0

Slide 27

Unify sort checking and property checking Harness the force of limitation solvers to improve sort checking sort security regularly relies on upon program-particular invariants Harness the solid assurances gave by the sort invriant to upgrade property checking non-associating, field reflection

Slide 28

Mem:int  int Type:int  sort Mutable Immutable 102 101 Ptr ( Int ) Ptr (List) Ptr (Record) 100 Int List Record 99 int sort Type invariant: a:int. HasType ( Mem (a), Type(a))

Slide 29

void init_record (list *p) { record *r = CONTAINER(p, record, hub); r->data2 = 42; } struct list { list *next; list * prev ; }; struct record { int data1; list hub; int data2; }; requires a:int. HasType ( Mem (a), Type(a)) requires HasType (p, Ptr (List)) guarantees a:int. HasType ( Mem (a), Type(a)) void init_record ( int p) { var r:int; r := p-1; attest HasType (r, Ptr (Record)); Mem (r+3) := 42; state a:int. HasType ( Mem (a), Type(a)); }

Slide 30

struct list { list *next; list * prev ; }; HasType (v, Int )  genuine HasType (v, Ptr (t))  v = 0  (v > 0  Match(v, t)) struct record { int data1; list hub; int data2; }; Match(a, Int )  Type(a) = Int Match(a, Ptr (t))  Type(a) = Ptr (t) Match(a, List)  Match(a, Ptr (List))  Match(a+1, Ptr (List)) Match(a, Record)  Match(a, Int )  Match(a+1, List)  Match(a+3, Int )

Slide 31

void init_record (list *p) { record *r = CONTAINER(p, record, hub); r->data2 = 42; } struct list { list *next; list * prev ; }; struct record { int data1; list hub; int data2; }; requires HasType (p-1, Ptr (Record))  p - 1  0 requires a:int. HasType ( Mem (a), Type(a)) requires HasType (p, Ptr (List)) guarantees a:int. HasType ( Mem (a), Type(a)) void init_record ( int p) { var r:int; r := p-1; affirm HasType (r, Ptr (Record)); Mem (r+3) := 42; attest a:int. HasType ( Mem (a), Type(a)); }

Slide 32

struct list { list *next; list * prev ; }; HasType (v, Int )  genuine HasType (v, Data1)  genuine HasType (v, Data2)  genuine HasType (v, Ptr (t))  v = 0  (v > 0  Match(v, t)) struct record { int data1; list hub; int data2; }; Match(a, Int )  Type(a) = Int Match(a, Data1)  Type(a) = Data1 Match(a, Data2)  Type(a) = Data2 Match(a, Ptr (t))  Type(a) = Ptr (t) Match(a, List)  Match(a, Ptr (List))  Match(a+1, Ptr (Li

SPONSORS