2009 · 276 citations · 39 references
ComputingComputer ScienceAlgorithmsData StructuresProgramming LanguagesAbstract InterpretationAutomated ReasoningData-flow AnalysisFrame-based RepresentationAbstract SemanticsHoare TriplesInterprocedural AnalysisSeparation Logic
This paper describes a compositional shape analysis, where each procedure is analyzed independently of its callers. The analysis uses an abstract domain based on a restricted fragment of separation logic, and assigns a collection of Hoare triples to each procedure; the triples provide an over-approximation of data structure usage. Compositionality brings its usual benefits -- increased potential to scale, ability to deal with unknown calling contexts, graceful way to deal with imprecision -- to shape analysis, for the first time.
39
Patrick Cousot, Radhia Cousot · 1977 · 6.2K citations
Collected Papers of Charles Sanders Peirce
Nature · 1935 · 4.6K citations · Full text
Humanities, Literature, Penology +1
Separation logic: a logic for shared mutable data structures
John Reynolds · 2003 · 2.2K citations
Precise interprocedural dataflow analysis via graph reachability
Thomas Reps, Susan Horwitz, Mooly Sagiv · 1995 · 1.2K citations
Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar et al. · 2002 · 1.2K citations