Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav07_lecture_13_skeleton [2007/05/02 10:20] vkuncak |
sav07_lecture_13_skeleton [2007/05/02 15:19] vkuncak |
||
---|---|---|---|
Line 8: | Line 8: | ||
* counterexample-driven refinement | * counterexample-driven refinement | ||
+ | Today: abstraction | ||
==== Abstraction ==== | ==== Abstraction ==== | ||
+ | |||
+ | Main readings: | ||
+ | * [[http://www-verimag.imag.fr/~graf/biblio.php?view=full#GrafSaidi97|Construction of abstract state graphs with PVS]] | ||
+ | * [[http://www.mpi-sb.mpg.de/~podelski/papers/cartesian.ps|Boolean and Cartesian Abstraction for Model Checking C Programs, Thomas Ball, Andreas Podelski, Sriram K. Rajamani. TACAS 2001: 268-283 (paper in .PS format)]] | ||
+ | * [[http://doi.acm.org/10.1145/378795.378846|Automatic Predicate Abstraction of C Programs, Thomas Ball, Rupak Majumdar, Todd D. Millstein, Sriram K. Rajamani. PLDI 2001: 203-213]] | ||
+ | |||
Design space of abstractions: | Design space of abstractions: | ||
Line 18: | Line 25: | ||
* best transformer in abstract domain | * best transformer in abstract domain | ||
- | Computation using wp. Boolean programs. | + | Examples. |
+ | |||
+ | Computation using wp. Weakest predicate abstraction of a given formula. Boolean programs. | ||
Precision-preserving optimizations: | Precision-preserving optimizations: | ||
Line 26: | Line 35: | ||
* syntactic construction of predicates | * syntactic construction of predicates | ||
* caching of calls to theorem prover | * caching of calls to theorem prover | ||
- | Further approximations: | + | Approximations: |
* bounding cube length to 3 | * bounding cube length to 3 | ||
* distributing approximation through logical operations | * distributing approximation through logical operations | ||
- | ==== Model checking ==== | ||
- | |||
- | Finite state space for now. | ||
- | |||
- | Bounded model checking for finite diameter systems. | ||
- | |||
- | BDDs: http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf | ||
- | |||
- | ==== Counterexample-driven refinement ==== | ||
- | |||
- | Heuristic refinement | ||
- | * expressions in branches | ||
- | * adding weakest preconditions | ||
- | * Craig's interpolation | ||