2005 · 73 citations · 17 references
ComputingComputer EngineeringComputer ScienceAlgorithmsProgramming LanguagesSystems ProgrammingConcurrency AnalysisRace Condition VulnerabilitiesStatic AnalysisStatic Code AnalysisType CheckingType SystemsAtomicityAtomicity ViolationsData Race AnalysisRace Condition AnalysisRace Condition DetectionStatic Race DetectionStatic Type CheckingType Inference
Concurrent programs are notorious for containing errors that are difficult to reproduce and diagnose. Two common kinds of concurrency errors are data races and atomicity violations (informally, atomicity means that executing methods concurrently is equivalent to executing them serially). Several static and dynamic (run-time) analysis techniques exist to detect potential races and atomicity violations. Run-time checking may miss errors in unexecuted code and incurs significant run-time overhead. On the other hand, run-time checking generally produces fewer false alarms than static analysis; this is a significant practical advantage, since diagnosing all of the warnings from static analysis of large codebases may be prohibitively expensive. This paper explores the use of static analysis to significantly decrease the overhead of run-time checking. Our approach is based on a type system for analyzing data races and atomicity. A type discovery algorithm is used to obtain types for as much of the program as possible (complete type inference for this type system is NP-hard, and parts of the program might be untypable). Warnings from the typechecker are used to identify parts of the program from which run-time checking can safely be omitted. The approach is completely automatic, scalable to very large programs, and significantly reduces the overhead of run-time checking for data races and atomicity violations. 1.
17
Constructing Induction Rules for Deductive Synthesis Proofs
Alan Bundy, Lucas Dixon, Jeremy Gow et al. · Electronic Notes in Theoretical Computer Science · 2006 · 2.8K citations · Full text
Stefan Savage, Michael T. Burrows, Greg Nelson et al. · ACM Transactions on Computer Systems · 1997 · 1.6K citations · Full text
Dawson Engler, Ken Ashcraft · ACM SIGOPS Operating Systems Review · 2003 · 664 citations
Ownership types for safe programming
Chandrasekhar Boyapati, Robert Lee, Martin Rinard · 2002 · 571 citations
Richard J. Lipton · Communications of the ACM · 1975 · 459 citations · Full text