Using dynamic analysis to improve model checking

Details Using dynamic analysis to improve model checking Using dynamic analysis to improve model checking

2011-06-14

2011-06-14

Puente, Emerson C (Department: 2196)

Data processing: software development, installation, and managem

Software program development tool

Testing or debugging

C717S126000, C717S130000, C703S022000

Reexamination Certificate

active

07962901

ABSTRACT:
Model checking has been used to verify program behavior. However, exploration of the model is often impractical for many general purpose programs due to the complexity of an exploding state space. Instead, a program is instrumented with code that records pointer dereference information. The instrumented program is executed thereby recording pointer dereference frequency information. Then, a model of the program is explored using the pointer dereference frequency information to direct state space exploration of the model.

REFERENCES:
patent: 4862373 (1989-08-01), Meng et al.
patent: 5220667 (1993-06-01), Ichieda
patent: 5333311 (1994-07-01), Whipple, II
patent: 5713008 (1998-01-01), Falkner
patent: 5740443 (1998-04-01), Carini
patent: 5774685 (1998-06-01), Dubey
patent: 5815720 (1998-09-01), Buzbee
patent: 5909578 (1999-06-01), Buzbee
patent: 5925100 (1999-07-01), Drewry et al.
patent: 5940618 (1999-08-01), Blandy et al.
patent: 5950003 (1999-09-01), Kaneshiro et al.
patent: 5950007 (1999-09-01), Nishiyama et al.
patent: 5953524 (1999-09-01), Meng et al.
patent: 5960198 (1999-09-01), Roediger et al.
patent: 6026234 (2000-02-01), Hanson et al.
patent: 6073232 (2000-06-01), Kroeker et al.
patent: 6079032 (2000-06-01), Peri
patent: 6145121 (2000-11-01), Levy et al.
patent: 6148437 (2000-11-01), Shah et al.
patent: 6189036 (2001-02-01), Kao
patent: 6216219 (2001-04-01), Cai et al.
patent: 6233678 (2001-05-01), Bala
patent: 6311260 (2001-10-01), Stone et al.
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6330556 (2001-12-01), Chilimbi et al.
patent: 6360361 (2002-03-01), Larus et al.
patent: 6370684 (2002-04-01), De Pauw et al.
patent: 6381735 (2002-04-01), Hunt
patent: 6404455 (2002-06-01), Ito et al.
patent: 6446257 (2002-09-01), Pradhan et al.
patent: 6560693 (2003-05-01), Puzak et al.
patent: 6560773 (2003-05-01), Alexander et al.
patent: 6571318 (2003-05-01), Sander et al.
patent: 6598141 (2003-07-01), Dussud et al.
patent: 6628835 (2003-09-01), Brill et al.
patent: 6651243 (2003-11-01), Berry et al.
patent: 6658652 (2003-12-01), Alexander et al.
patent: 6675374 (2004-01-01), Pieper et al.
patent: 6704860 (2004-03-01), Moore
patent: 6738968 (2004-05-01), Bosworth et al.
patent: 6848029 (2005-01-01), Coldewey
patent: 6886167 (2005-04-01), Breslau et al.
patent: 6904590 (2005-06-01), Ball et al.
patent: 6951015 (2005-09-01), Thompson
patent: 6957422 (2005-10-01), Hunt
patent: 7032217 (2006-04-01), Wu
patent: 7058936 (2006-06-01), Chilimbi et al.
patent: 7140008 (2006-11-01), Chilimbi et al.
patent: 7159038 (2007-01-01), Rychlicki
patent: 7181730 (2007-02-01), Pitsianis et al.
patent: 7293260 (2007-11-01), Dmitriev
patent: 7296180 (2007-11-01), Waterhouse et al.
patent: 7343598 (2008-03-01), Chilimbi et al.
patent: 7401324 (2008-07-01), Dmitriev
patent: 7506317 (2009-03-01), Liang et al.
patent: 7587709 (2009-09-01), Chilimbi et al.
patent: 7607119 (2009-10-01), Perelman et al.
patent: 7770153 (2010-08-01), Chilimbi et al.
patent: 2002/0133639 (2002-09-01), Breslau et al.
patent: 2002/0144245 (2002-10-01), Lueh
patent: 2002/0178401 (2002-11-01), Ball et al.
patent: 2003/0145314 (2003-07-01), Nguyen et al.
patent: 2003/0182654 (2003-09-01), Dmitriev
patent: 2003/0204840 (2003-10-01), Wu
patent: 2004/0015897 (2004-01-01), Thompson et al.
patent: 2004/0015930 (2004-01-01), Wu
patent: 2004/0025145 (2004-02-01), Dawson
patent: 2004/0078381 (2004-04-01), Blandy et al.
patent: 2004/0088699 (2004-05-01), Suresh
patent: 2004/0103401 (2004-05-01), Chilimbi et al.
patent: 2004/0103408 (2004-05-01), Chilimbi et al.
patent: 2004/0111444 (2004-06-01), Garthwaite
patent: 2004/0133556 (2004-07-01), Wolczko et al.
patent: 2004/0181782 (2004-09-01), Findeisen
patent: 2004/0215880 (2004-10-01), Chiimbi et al.
patent: 2004/0216091 (2004-10-01), Groeschel
patent: 2005/0086648 (2005-04-01), Andrews et al.
patent: 2005/0091645 (2005-04-01), Chilimbi et al.
patent: 2005/0149904 (2005-07-01), Ball et al.
patent: 2005/0182603 (2005-08-01), Freitas et al.
patent: 2005/0235257 (2005-10-01), Ball et al.
patent: 2005/0246696 (2005-11-01), Alexander et al.
patent: 2006/0070040 (2006-03-01), Chilimbi et al.
patent: 2006/0155791 (2006-07-01), Tene et al.
patent: 2006/0242636 (2006-10-01), Chilimbi et al.
patent: 2006/0265438 (2006-11-01), Shankar et al.
patent: 2006/0265694 (2006-11-01), Chilimbi et al.
patent: 2007/0083856 (2007-04-01), Chilimbi et al.
patent: 2007/0169000 (2007-07-01), Havin et al.
patent: 2008/0005208 (2008-01-01), Vaswani et al.
Dynamic Points-To Sets: A Comparison with Static Analyses and Potential Applications in Program Understanding and Optimization Markus Mock, Manuvir Das, Craig Chambers, and Susan J. Eggers Microsoft Research Technical Report MSR-TR-2001-38 Published: Mar. 2001.
Automatic predicate abstraction of C programs Thomas Ball, Rupak Majumdar, Todd Millstein, Sriram K. Rajamani ACM SIGPLAN Notices, vol. 36 , Issue 5 (May 2001) pp. 203-213.
Dynamic Analysis from the Bottom Up Markus Mock Workshop on Dynamic Analysis, pp. 13-16 May 9, 2003.
Hints to Accelerate Symbolic Traversal Kavita Ravi and Fabio Somenzi Charme'99, LNCS 1703, pp. 250-266 Year of Publication: 1999.
Two-Level Tree Structure for Fast Pointer Lookup Hans-J. Boehm Archived via Wayback Machine Dec. 2, 2002, retrieved Sep. 13, 2010 http://web.archive.org/web/20021202232247/http://www.hpl.hp.com/personal/Hans—Boehm/gc/tree.html.
Distributed Program Sampling Ben Liblit, Alex Aiken, Alice X. Zheng Year of Publication: 2003.
An Empirical Study on the Granularity of Pointer Analysis in C Programs Tong Chen, Jin Lin, Wei-Chung Hsu and Pen-Chung Yew Languages and Compilers for Parallel Computing, 15th Workshop Year of Publication: 2002.
Program Slicing with Dynamic Points-To Sets Markus Mock, Darren C. Atkinson, Craig Chambers, and Susan J. Eggers IEEE Transactions on Software Engineering, vol. 31, No. 8, pp. 657-678 Aug. 2005.
Using Runtime Analysis to Guide Model Checking of Java Programs Klaus Havelund Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification pp. 245-264 Year of Publication: 2000.
Model Checking Programs Willem Visser, Klaus Havelund, Guillaume Brat, Seungjoon Park, Flavio Lerda Automated Software Engineering, 10, pp. 203-232 Year of publication: 2003.
Predicate Abstraction of ANSI-C Programs Using SAT Edmund Clarke, Daniel Kroening, Natasha Sharygina, Karen Yorav Formal Methods in System Design, 25, pp. 105-127 Year of publication: 2004.
Symbolic Guided Search for CTL Model Checking Roderick Bloem, Kavita Ravi, Fabio Somenzi 37th Design Automation Conference Year of publication: 2000.
Liblit et al., “Distributed Program Sampling,” Department of Electrical Engineering and Computer Science, University of California, Berkely, 10 pages.
Ball and Rajamani, “Generating abstract explanations of spurious counterexamples in C programs,” Technical Report MSR-TR-2002-09, 13 pages, Jan. 22, 2002.
Ball and Rajamani, “The SLAM project: Debugging system software via static analysis,” 3 pages.
Ball and Rajamani, “Boolean programs: A model and process for software analysis,” Technical Report MSR-TR-2000-14, 29 pages, Feb. 29, 2000 (updated Mar. 28, 2000).
Ball and Millstein, “Plymorphic Predicate Abstraction,” Technical Report MSR-TR-200110, 22 pages, Jun. 17, 2002.
Ball et al., “SLAM and static driver verifier: Technology transfer of formal methods inside Microsoft,” Technical Report MSR-TR-2004-08, 20 pages, Jan. 28, 2004.
Microsoft, “Static driver verifier—Finding driver bugs at compile-time,” <http://www.microsoft.com/whdc/devtools/tools/sdv.mspx>, 2 pages (accessed Apr. 1, 2006).
“Dynamic Binary Analysis and Instrumentation,” by Nicholas Nethercote, Nov. 2004 Ph.D. Dissertation. University of Cambridge.
“Precise Interprecedural Dataflow Analysis via Graph Reachability,” by T. Reps, S. Horwitz, M. Sagiv, pp. 49-61, Conference Record of POPL'95: 22ndACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1

Affiliated with

Also associated with

Rating

Using dynamic analysis to improve model checking does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Using dynamic analysis to improve model checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using dynamic analysis to improve model checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2713985