Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
sav07_lecture_13_skeleton [2007/05/02 10:19] vkuncak |
sav07_lecture_13_skeleton [2007/05/02 15:18] vkuncak |
||
|---|---|---|---|
| Line 7: | Line 7: | ||
| * model checking (finite state or pushdown system) | * model checking (finite state or pushdown system) | ||
| * 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 26: | Line 34: | ||
| * caching of calls to theorem prover | * caching of calls to theorem prover | ||
| Further approximations: | Further approximations: | ||
| - | * bounding cube length | + | * bounding cube length to 3 |
| * distributing approximation through logical operations | * distributing approximation through logical operations | ||
| - | Bounding cube length. | ||
| - | |||
| - | ==== Model checking ==== | ||
| - | |||
| - | Finite state space for now. | ||
| - | |||
| - | Bounded model checking for finite diameter systems. | ||
| - | |||
| - | BDDs. | ||
| - | |||
| - | ==== Counterexample-driven refinement ==== | ||
| - | |||
| - | Heuristic refinement | ||
| - | * expressions in branches | ||
| - | * adding weakest preconditions | ||
| - | * Craig's interpolation | ||