2005 · 111 citations · 28 references
ComputingComputer ScienceAlgorithmsFormal MethodsProgramming LanguagesAbstract InterpretationAbstract Syntax TreesControl-flow AnalysisData-flow AnalysisDeductive VerificationStatic AnalysisAbstract SemanticsAbstractionHeap AllocationHeap AnalysisHeap ModelingHeap OrganizationRuntime Semantics
The goal of this work is to develop compile-time algorithms for automatically verifying properties of imperative programs that manipulate dynamically allocated storage. The paper presents an analysis method that uses a characterization of a procedure's behavior in which parts of the heap not relevant to the procedure are ignored. The paper has two main parts: The first part introduces a non-standard concrete semantics, LSL, in which called procedures are only passed parts of the heap. In this semantics, objects are treated specially when they separate the "local heap" that can be mutated by a procedure from the rest of the heap, which---from the viewpoint of that procedure---is non-accessible and immutable. The second part concerns abstract interpretation of LSL and develops a new static-analysis algorithm using canonical abstraction.
28
Patrick Cousot, Radhia Cousot · 1977 · 6.2K citations
A relational model of data for large shared data banks
E. F. Codd · Communications of the ACM · 1970 · 5.2K citations · Full text
Separation logic: a logic for shared mutable data structures
John Reynolds · 2003 · 2.2K citations
Systematic design of program analysis frameworks
Patrick Cousot, Radhia Cousot · 1979 · 1.6K citations · Full text
Proof of correctness of data representations
C. A. R. Hoare · Acta Informatica · 1972 · 967 citations