Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav07_lecture_3_skeleton [2007/03/20 21:21] vkuncak |
sav07_lecture_3_skeleton [2007/03/21 09:25] vkuncak |
||
|---|---|---|---|
| Line 108: | Line 108: | ||
| 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. | 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. | ||
| + | |||
| Line 113: | Line 114: | ||
| While symbolic execution computes formula by going forward along the program syntax tree, weakest precondition computes formula by going backward. | While symbolic execution computes formula by going forward along the program syntax tree, weakest precondition computes formula by going backward. | ||
| + | |||
| + | ==== Inferring Loop Invariants ==== | ||
| + | |||
| + | Suppose we compute strongest postcondition in a program where we unroll loop k times. | ||
| + | * What does it denote? | ||
| + | * What is its relationship to loop invariant? | ||
| + | |||
| + | Weakening strategies | ||
| + | * maintain a conjunction | ||
| + | * drop conjuncts that do not remain true | ||
| + | |||
| + | Alternative: | ||
| + | * decide that you will only loop for formulas of restricted form, as in abstract interpretation and data flow analysis (next week) | ||
| ===== Proving quantifier-free linear arithmetic formulas ===== | ===== Proving quantifier-free linear arithmetic formulas ===== | ||