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 17:23] vkuncak |
sav07_lecture_3_skeleton [2007/03/21 09:25] 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 89: | ||
| We can apply these rules to reduce the size of formulas. | We can apply these rules to reduce the size of formulas. | ||
| + | |||
| + | |||
| + | ==== Approximation ==== | ||
| + | |||
| + | If (F -> G) is value, we say that F is stronger than F and we say G is weaker than F. | ||
| + | |||
| + | When a formula would be too complicated, we can instead create a simpler approximate formula. To be sound, if our goal is to prove a property, we need to generate a *larger* relation, which corresponds to a weaker formula describing a relation, and a stronger verification condition. (If we were trying to identify counterexamples, we would do the opposite). | ||
| + | |||
| + | We can replace "assume F" with "assume F1" where F1 is weaker. Consequences: | ||
| + | * omtiting complex if conditionals (assuming both branches can happen - as in most type systems) | ||
| + | * replacing complex assignments with arbitrary change to variable: because x=t is havoc(x);assume(x=t) and we drop the assume | ||
| + | |||
| + | This idea is important in static analysis. | ||
| + | |||
| + | |||
| ==== Symbolic execution ==== | ==== 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. | 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 101: | 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 ===== | ||
| Line 112: | Line 138: | ||
| * 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 | ||
| + | |||
| + | |||
| + | |||