Differences

This shows you the differences between two versions of the page.

--- sav07_lecture_13_skeleton [2007/05/02 09:59]
vkuncak
+++ sav07_lecture_13_skeleton [2007/05/02 15:19]
vkuncak
@@ Line 7: / Line 7: @@
   * model checking (finite state or pushdown system)
   * counterexample-driven refinement
+Today: 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:
@@ Line 17: / Line 25: @@
   * best transformer in abstract domain
-Computation using wp.  Boolean programs.  Bounding cube length.
+Examples.
-==== Model checking ====
-Finite state space for now.
-BDDs.
-Bounded model checking for finite diameter systems.
+Computation using wp.  Weakest predicate abstraction of a given formula.  Boolean programs.
-==== Counterexample-driven refinement ====
+Precision-preserving optimizations:
+  * cubes in increasing order
+  * do not update variables if command cannot change them
+  * cone of influence to reduce the number of predicates to consider
+  * syntactic construction of predicates
+  * caching of calls to theorem prover
+Approximations:
+  * bounding cube length to 3
+  * distributing approximation through logical operations
-Heuristic refinement
-  * expressions in branches
-  * adding weakest preconditions
-  * Craig's interpolation