2015 · 57 citations · 40 references
ComputingComputer ScienceComputer SystemsAlgorithmsFormal MethodsProgramming LanguagesConcurrency AnalysisConcurrent ProgrammingConstraint SatisfactionConstraint SolvingControl-flow AnalysisSymbolic ExecutionBounded Model CheckingConcurrency Bug DebuggingConcurrency Bug DetectionConcurrency BugsExecution Trace AnalysisModel Checking For ConcurrencySymbolic AnalysisThread Interleaving Analysis
Programmers often have to spend a significant amount of time in- specting the software code and execution traces to identify the cause of a bug. For a multithreaded program, debugging is even more challenging due to the subtle interactions between threads and the often astronomical number of interleavings. In this work, we pro- pose a logical constraint based symbolic analysis method to aid in the diagnosis of concurrency bugs and to recommend repairs. Both diagnosis and repair are formulated as constraint solving prob- lems. Our method, by leveraging the power of satisfiability (SAT) solvers and a bounded model checker, performs a semantic analy- sis of the sequential computation as well as thread interactions. The constraint based analysis is designed for handling critical software with small to medium code size, but complex concurrency control, such as device drivers, implementations of synchronization proto- cols, and concurrent data structures. We have implemented our new method in a software tool and demonstrated its effectiveness in di- agnosing bugs in multithreaded C programs.
40
The control of discrete event systems
Peter J. Ramadge, W.M. Wonham · Proceedings of the IEEE · 1989 · 2.9K citations
On the synthesis of a reactive module
Amir Pnueli, Roni Rosner · 1989 · 1.4K citations · Full text
Shan Lu, Soyeon Park, Eunsoo Seo et al. · 2008 · 892 citations