2013 · 46 citations · 12 references
ComputingComputer ScienceAlgorithmsFormal MethodsProgramming LanguagesConcurrency AnalysisConcurrency VerificationConcurrent ProgrammingConcurrent System VerificationControl-flow AnalysisStatic AnalysisConcurrent Program VerificationControl Dependence AnalysisDependence AnalysisModel Checking For ConcurrencyPartial-order ReductionProgram Dependence AnalysisState Space ExplosionVerification Of Concurrent Programs
Lazy abstraction with interpolants, also known as the Impact algorithm, is en vogue as a state-of-the-art software model-checking technique for sequential programs. However, a direct extension of the Impact algorithm to concurrent programs is bound to be inefficient as it has to explore all thread interleavings, which leads to control-state explosion. To this end, we present a new algorithm that combines a new, symbolic form of partial-order reduction with Impact. Our algorithm carries out the dependence analysis on-the-fly while constructing the abstraction and is thus able to deal precisely with dynamic dependencies arising from accesses to tables or pointers - a setting where classical static partial-order reduction techniques struggle. We have implemented the algorithm in a prototype tool that analyses concurrent C program with POSIX threads and evaluated it on a number of benchmark programs. To our knowledge, this is the first application of an Impact-like algorithm to concurrent programs.
12
An axiomatic proof technique for parallel programs I
Susan Owicki, David Gries · Acta Informatica · 1976 · 1K citations
Dynamic partial-order reduction for model checking software
Cormac Flanagan, Patrice Godefroid · 2005 · 641 citations · Full text
An interpolating theorem prover
Kenneth L. McMillan · Theoretical Computer Science · 2005 · 272 citations
Predicate Abstraction of ANSI-C Programs Using SAT
Edmund M. Clarke, Daniel Kroening, Natasha Sharygina et al. · Formal Methods in System Design · 2004 · 190 citations · Full text