Date of Award
3-2006
Document Type
Thesis
Degree Name
Master of Science
Department
Department of Electrical and Computer Engineering
First Advisor
Robert P. Graham, Jr., PhD
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.
AFIT Designator
AFIT-GE-ENG-06-19
DTIC Accession Number
ADA450020
Recommended Citation
Fadul, Jose E., "Toward the Static Detection of Deadlock in Java Software" (2006). Theses and Dissertations. 3482.
https://scholar.afit.edu/etd/3482