Computer Science – Logic in Computer Science
Scientific paper
2009-04-30
LMCS 5 (2:12) 2009
Computer Science
Logic in Computer Science
30 pages, LMCS
Scientific paper
10.2168/LMCS-5(2:12)2009
This paper shows how to harness existing theorem provers for first-order logic to automatically verify safety properties of imperative programs that perform dynamic storage allocation and destructive updating of pointer-valued structure fields. One of the main obstacles is specifying and proving the (absence) of reachability properties among dynamically allocated cells. The main technical contributions are methods for simulating reachability in a conservative way using first-order formulas--the formulas describe a superset of the set of program states that would be specified if one had a precise way to express reachability. These methods are employed for semi-automatic program verification (i.e., using programmer-supplied loop invariants) on programs such as mark-and-sweep garbage collection and destructive reversal of a singly linked list. (The mark-and-sweep example has been previously reported as being beyond the capabilities of ESC/Java.)
Immerman Neil
Lev-Ami Tal
Reps Thomas
Sagiv Mooly
Srivastava Siddharth
No associations
LandOfFree
Simulating reachability using first-order logic with applications to verification of linked data structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Simulating reachability using first-order logic with applications to verification of linked data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulating reachability using first-order logic with applications to verification of linked data structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-443967