2013 · 36 citations · 15 references
ComputingComputer ScienceComputer SystemsAlgorithmsFormal MethodsTheory Of ComputationConcurrency VerificationConcurrent System VerificationDeductive VerificationModel CheckingProtocol VerificationConcurrent Program VerificationInvariant CheckingInvariant GenerationInvariant VerificationInvariantsModel Checking For ConcurrencySafety PropertiesVerification Of Concurrent Programs
Verification of safety properties of concurrent programs with an arbitrary numbers of processes is an old challenge. In particular, complex parameterized protocols like FLASH are still out of the scope of state-of-the-art model checkers. In this paper, we describe a new algorithm, called BRAB, that is able to automatically infer invariants strong enough to prove a protocol like FLASH. BRAB computes over-approximations of backward reachable states that are checked to be unreachable in a finite instance of the system. These approximations (candidate invariants) are then model checked together with the original safety properties. Completeness of the approach is ensured by a mechanism for backtracking on spurious traces introduced by too coarse approximations.
15
The Stanford FLASH multiprocessor
Jeffrey S. Kuskin, David Ofelt, Mark Heinrich et al. · International Symposium on Computer Architecture · 1994 · 670 citations
E. M. Clarke, David E. Long, Kenneth L. McMillan · 2003 · 471 citations
Reasoning about systems with many processes
Steven M. German, A. Prasad Sistla · Journal of the ACM · 1992 · 443 citations · Full text
The Stanford FLASH multiprocessor
Jeffrey S. Kuskin, David Ofelt, Mark Heinrich et al. · 2002 · 270 citations