LARA

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Next revision Both sides next revision
sav07_lecture_3_skeleton [2007/03/20 14:54]
vkuncak
sav07_lecture_3_skeleton [2007/03/20 18:06]
vkuncak
Line 2: Line 2:
  
 ===== Converting programs (with simple values) to formulas ===== ===== Converting programs (with simple values) to formulas =====
 +
 +
  
  
Line 12: Line 14:
 <​latex>​ <​latex>​
 \{((x_0,​y_0),​(x,​y)) \mid F \} \{((x_0,​y_0),​(x,​y)) \mid F \}
-</​latex> ​     +</​latex>​ 
 where F is some formula that has x,y,x_0,y_0 as free variables. where F is some formula that has x,y,x_0,y_0 as free variables.
  
Line 20: Line 23:
   * correct   * correct
   * efficient   * efficient
-  * create formulas that we can prove later+  * create formulas that we can effectively ​prove later 
 + 
 +What exactly do we prove about the formula R( c ) ? 
 + 
 +We prove that this formula is **valid** 
 + 
 +  R( c ) -> error=false
  
  
Line 64: Line 73:
  
 when c is a basic command. when c is a basic command.
 +
 +
  
  
Line 85: Line 96:
 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