Model Checking Multithreaded C Code with Twist Anna Zaks and Rajeev Joshi Turn 2008 10 August, Los Angeles, USA.


75 views
Uploaded on:
Category: Medical / Health
Description
Model Checking Multithreaded C Code with Twist Anna Zaks and Rajeev Joshi Turn 2008 10 August, Los Angeles, USA. The Objective: Check Multithreaded C Code. /* Peterson's calculation (adjusted from Wikipedia) ‏ */static int sh_f0, sh_f1, sh_last; void * run_thread0 () {
Transcripts
Slide 1

Model Checking Multithreaded C Code with SPIN Anna Zaks & Rajeev Joshi SPIN 2008 10 August, Los Angeles, USA

Slide 2

Checking Multithreaded C Code The Goal: Check Multithreaded C Code/* Peterson\'s calculation (adjusted from Wikipedia) ‏ */static int sh_f0, sh_f1, sh_last; void * run_thread0 () { struct pa_desc d; d.f0 = &sh_f0; d.f1 = &sh_f1; d.last = 1; for (;;) { *(d.f0)=1; sh_last=d.last ; while (*(d.f1)==1 && (last==d.last)) { ;/* occupied hold up */}/* discriminating segment */d.f0=0; } … bool turn, flag[2]; dynamic proctype run_thread0 () { once more: flag[0] = 1; turn = 1; (flag[1] == 0 || turn == 0) - >/* occupied hold up *//* basic area */flag[0] = 0; goto once more; } ... express plan as a PROMELA model Limitations need to re-try manual interpretation at whatever point usage changes the nonappearance of blunders in the configuration does not ensure that the usage (the executable) is without lapse

Slide 3

Checking Multithreaded C Code Model-Driven Verification Embed C code inside PROMELA - C code is executed by SPIN amid pursuit static int sh_f0, sh_f1, sh_last; void * run_thread0 () { struct pa_desc d; d.f0 = &sh_f0; d.f1 = &sh_f1; d.last = 1; for (;;) { *(d.f0)=1; sh_last=d.last ; while (*(d.f1)==1 && (last==d.last)) { ;/* occupied hold up */}/* discriminating area */d.f0=0; } … c_decl { extern void * run_thread0 (void *); extern void * run_thread1 (void *); } ; ... dynamic proctype principle() { init() ; do :: choose(thread0) - > c_code { run_thread0 (); } :: choose(thread1) - > c_code { run_thread1 (); } ... od } Main disadvantage: Not helpful for confirmation of multithreaded C projects Need to investigate the interleavings inside of the capacity Ref: Model-Driven Software Verification , G.J.Holzmann & R.Joshi, SPIN 2004

Slide 4

Checking Multithreaded C Code Our Solution – Introducing pancam Build pancam mediator that can be inserted inside of a current model checker pancam acquires all SPIN improvements and future upgrades: bit-state confirmation hash pressure multi-center checking pancam does not depend on any customization of SPIN

Slide 5

Checking Multithreaded C Code The LLVM Compiler Infrastructure pancam translates enhanced LLVM bytecode (a wrote bytecode dialect) gets blunders that show themselves strictly when the streamlining stage/* Peterson\'s calculation (adjusted from Wikipedia) ‏ */static unpredictable int sh_f0, sh_f1, sh_last; void * run_thread0 () { struct pa_desc d; d.f0 = &sh_f0; d.f1 = &sh_f1; d.last = 1; for (;;) { *(d.f0)=1; sh_last=d.last ; while (*(d.f1)==1 && (sh_last==d.last)) { ;/* occupied hold up */}/* discriminating area */d.f0=0; } Ref: LLVM compiler (began from University of Illinois Urbana-Champaign), http://llvm.org

Slide 6

Checking Multithreaded C Code The pancam Checker Spin (pan.c) take_step (thread_id, granularity, &state) pancam SPIN arranges the state space look - chooses which string to execute next - stores went to states in the hash - restores to the past stride amid DFS backtracking pancam registers the move by code elucidation -can execute any number of directions of a particular string -can check predicates anytime &state

Slide 7

Checking Multithreaded C Code Spin M odel for pancam dynamic proctype fundamental() { c_code { pancam_init(“petersons.bc”); init_thread(0, “ run_thread0” ); init_thread(1, “ run_thread1” ); }; do :: c_expr { is_enabled(0) } - > c_code { take_step(0); } :: c_expr { is_enabled(1) } - > c_code { take_step(1); } od }

Slide 8

Checking Multithreaded C Code Program State cs[N] empowered worldwide state framework load FREE program stack c_track “cs” “N” “Matched”; dynamic proctype principle() { c_code { pancam_init(“petersons.bc”); init_thread(0, “ run_thread0” ); init_thread(1, “ run_thread1” ); }; do :: c_expr { is_enabled(0) } - > c_code { take_step(0); } :: c_expr { is_enabled(1) } - > c_code { take_step(1); } od }

Slide 9

Checking Multithreaded C Code Addressing State Space Explosion Three Strategies bolster client characterized reflection capacities use setting limited checking do on-the-fly fractional request decrease

Slide 10

Checking Multithreaded C Code User Defined Abstractions empowered worldwide state framework pile FREE program stack client characterized C oncrete State cs[N] Abstract State as[K] as is populated through the client characterized capacity compute_abst(void *as) cs is put away on Spin’s stack, which is utilized for DFS backtracking as is utilized for state hashing c_track “cs” “N” “UnMatched”; c_track “as” “K” “Matched”;

Slide 11

Checking Multithreaded C Code Context-Bounded Checking Enforce upper bound on number of permitted preemptive connection changes a change from p to q is preemptive given p is empowered investigate state space thoroughly with progressively bigger limits functions admirably by and by - most simultaneousness bugs can be activated with a little number of switches Ref: Iterative connection jumping for deliberate testing of multithreaded projects, M. Musuvathi, S. Qadeer, POPL 2007

Slide 12

Checking Multithreaded C Code pancam Implementation of Context B ounding Implemented as a discretionary expansion obliges no alteration to Spin

Slide 13

Checking Multithreaded C Code Experimental Results: Context B ounding peterson.c without deliberation

Slide 14

Checking Multithreaded C Code On-the-fly Partial-request R eduction take_step (th_id, s) Spin pancam “transitions” have no structure : c_code { take_step (th_id, s); } Spin’s conventional fractional request lessening doesn’t apply regardless of the fact that we changed Spin, registering freedom connection is too hard Shift the weight to pancam by expanding the granularity of a “pancam step” concealing pointless states from Spin s’

Slide 15

Checking Multithreaded C Code On-the-fly Partial-request R eduction take_step (th_id, s) Spin pancam “transitions” have no structure : c_code { take_step (th_id, s); } Spin’s customary halfway request diminishment doesn’t apply regardless of the fact that we adjusted Spin, processing autonomy connection is too hard Shift the weight to pancam by expanding the granularity of a “pancam step” concealing superfluous states from Spin Example execute a string until it gets to a worldwide variable or the mutual store Can we improve? s’

Slide 16

Checking Multithreaded C Code Superstep Reduction: Key Ideas S  2 Unlike traditional POR, which considers subsets of empowered moves from state s, we consider subsets of empowered limited ways from s  1

Slide 17

Checking Multithreaded C Code Superstep Reduction: Key Ideas S  2 Unlike established POR, which considers subsets of empowered moves from state s, we consider subsets of empowered limited ways from s Each chose way is supplanted with a solitary superstep move  1

Slide 18

Checking Multithreaded C Code Superstep Reduction: Key Ideas S  2 Unlike established POR, which considers subsets of empowered moves from state s, we consider subsets of empowered limited ways from s Each chose way is supplanted with a solitary superstep move The contentions (conditions) are figured progressively  1

Slide 19

Checking Multithreaded C Code Superstep Requirments Compute superstep  i for each empowered string i a superstep is limited and nonempty just the last move in a superstep may struggle with moves in different supersteps just the last move of a superstep can be noticeable From these, we can demonstrate that superstep diminishment is sound and complete for checking any LTL property without whenever administrator Can be seen as an augmentation of the Cartesian incomplete request decrease to LTL Ref: Cartesian halfway request lessening, G. Gueta, C. Flanagan, E. Yahav, M. Sagiv, SPIN 2007

Slide 20

Checking Multithreaded C Code Efficient DFS Implementation DFS is key for liveness bolster Precomputing the supersteps prompts run time overhead Supersteps are registered on-the-fly utilizing a plan that keeps up accounting data crosswise over Spin backtracking steps no alteration to SPIN is obliged

Slide 21

Checking Multithreaded C Code Experimental Results: Superstep R eduction robots.c benchmark

Slide 22

Checking Multithreaded C Code Other Related Work Modex instrument extricates PROMELA models from C executions A down to earth technique for confirming occasion driven programming, G. Holzmann, M. Smith, SE1999 Java Pathfinder coordinates model checking with the virtual machine Model checking projects, W. Visser, K. Havelund, G. Imp, S. Park, F. Lerda, ASE 2003 VeriSoft [God97] and Inspect [YCGK07] instruments are state-less model checkers for C Model checking for programming dialects utilizing VeriSoft , P. Godefroid, POPL 1997 Dynamic fractional request lessening for model checking programming , C. Flanagan, P. Godefroid, POPL 2005 CHESS model checker for simultaneous C code checks for livelocks Fair stateless model checking , M. Musuvathi, S. Qadeer, PLDI 2008 CMC express state model checking obliges manual interpretation from C A sober minded way to deal with model checking genuine code , M. Musuvathi, et al., OSDI 2002 In CodeSur

Recommended
View more...