Toward the Static Detection of Deadlock in Java Software
Abstract
Concurrency is the source of many real-world software reliability and security problems. Concurrency defects are difficult to detect because they defy conventional software testing techniques due to their non-local and non-deterministic nature. We focus on one important aspect of this problem: static detection of the possibility of deadlock - a situation in which two or more processes are prevented from continuing while each waits for resources to be freed by the continuation of the other. This thesis proposes a flow-insensitive interprocedural static analysis that detects the possibility that a program can deadlock at runtime. Our analysis proceeds in two steps. The first extracts the "real" call graph decorated with acquired locks from the target program. The second analysis this decorated graph to report how a possible deadlock may occur at runtime. We demonstrate our analysis via a prototype implementation that detects deadlock conditions within two small Java programs. The two principle limitations of our analysis are on the target program: (1) we need its "real" call graph and (2) its overall size is limited. Construction of the "real" call graph requires perfect aliasing information. The program's size our technique is able to analyze is roughly 35 kSLOC.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 23, 2006
- Accession Number
- ADA450020
Entities
People
- Jose E. Fadul
Organizations
- Air Force Institute of Technology