Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav07_lecture_3_skeleton [2007/03/20 14:58] vkuncak |
sav07_lecture_3_skeleton [2007/03/20 21:13] vkuncak |
||
---|---|---|---|
Line 2: | Line 2: | ||
===== Converting programs (with simple values) to formulas ===== | ===== Converting programs (with simple values) to formulas ===== | ||
- | |||
Line 10: | Line 9: | ||
* represent programs using guarded command language, e.g. desugaring of 'if' into non-deterministic choice and assume | * represent programs using guarded command language, e.g. desugaring of 'if' into non-deterministic choice and assume | ||
* give meaning to guarded command language statements as relations | * give meaning to guarded command language statements as relations | ||
- | * we can represent relations using set comprehensions; if our program c has two state components, we can represent its meaning R( c ) as | + | * we can represent relations using set comprehensions; if our program c has two state components, we can represent its meaning R( c ) as $\{((x_0,y_0),(x,y)) \mid F \}$, where F is some formula that has x,y,x_0,y_0 as free variables. |
- | <latex> | + | |
- | \{((x_0,y_0),(x,y)) \mid F \} | + | |
- | </latex> | + | |
- | where F is some formula that has x,y,x_0,y_0 as free variables. | + | |
* this is what I mean by ''simple values'': later we will talk about modeling pointers and arrays, but we will still use this as a starting point. | * this is what I mean by ''simple values'': later we will talk about modeling pointers and arrays, but we will still use this as a starting point. | ||
Line 22: | Line 17: | ||
* efficient | * efficient | ||
* create formulas that we can effectively prove later | * create formulas that we can effectively prove later | ||
+ | |||
What exactly do we prove about the formula R( c ) ? | What exactly do we prove about the formula R( c ) ? | ||
- | We prove that this formula is **valid** | + | We prove that this formula is **valid**: |
R( c ) -> error=false | R( c ) -> error=false | ||
Line 71: | Line 67: | ||
when c is a basic command. | when c is a basic command. | ||
+ | |||
+ | |||
Line 92: | Line 90: | ||
We can apply these rules to reduce the size of formulas. | We can apply these rules to reduce the size of formulas. | ||
- | ==== Papers ==== | + | ==== Abstraction ==== |
+ | |||
+ | * for proving properties | ||
+ | * for finding errors | ||
+ | |||
+ | ==== Symbolic execution ==== | ||
+ | |||
+ | Symbolic execution converts programs into formulas by going forward. It is therefore somewhat analogous to the way an [[interpreter]] for the language would work. It is based on the notion of strongest postcondition. | ||
+ | |||
+ | |||
+ | ==== Weakest preconditions ==== | ||
+ | |||
+ | While symbolic execution computes formula by going forward along the program syntax tree, weakest precondition computes formula by going backward. | ||
+ | |||
+ | ===== Proving quantifier-free linear arithmetic formulas ===== | ||
+ | |||
+ | ===== Papers ===== | ||
* Verification condition generation in Spec#: http://research.microsoft.com/~leino/papers/krml157.pdf | * Verification condition generation in Spec#: http://research.microsoft.com/~leino/papers/krml157.pdf | ||
Line 100: | Line 114: | ||
* Presburger Arithmetic (PA) bounds: {{papadimitriou81complexityintegerprogramming.pdf}} | * Presburger Arithmetic (PA) bounds: {{papadimitriou81complexityintegerprogramming.pdf}} | ||
* Specializing PA bounds: http://www.lmcs-online.org/ojs/viewarticle.php?id=43&layout=abstract | * Specializing PA bounds: http://www.lmcs-online.org/ojs/viewarticle.php?id=43&layout=abstract | ||
+ | |||
+ | |||
+ | |||