Research On Static Deadlock Detection Based On Source-Code Analysis

With information technology developing, the complexity and scale of the software extends continuously. The faults of software are being the most important factor that causes the computer system to be out of control. The quality of software became a hot research field in the computer science. The internet makes people's life more convenient; on the other hand, the threat to the computer system is increasing. Therefore, the security is a new higher standard for the software.Deadlock is one of the most typical problems in the concurrent programs, and makes the programs unsafe. Because a deadlock may prevent an entire program from working, or cause a system breakdown, it is a serious problem. How to improve software quality and find an efficient method for deadlock detection has been a hard problem, which is in a great need of solutions.Supported by the National High-tech Research and Development Program ("863" Program) "Software fault models and the fault oriented software testing system" and "Software secure fault models and testing technology based on software secure fault models", this thesis focuses on several static analysis technologies involved in defect pattern checking. It mainly discusses static deadlock detection based on source code analysis. The main contributions are as follows:(1)This thesis deliberates the production and conditions of the deadlock. Based on the characters of the concurrent program in Java, general deadlock defect patterns for the concurrent programs are proposed.(2)Based on several static analysis technologies involved in defect pattern checking, a static deadlock detection algorithm for Java is presented. This algorithm can detect deadlocks both in two threads and more than two threads. In our algorithm, we use a reachable analysis to find all the threads that can start in the program, the concurrent features of the threads are collected and used to catch the potential deadlocks. In order to improve the accuracy of the algorithm, we used the gatelock analysis, escape analysis and may-happen parallel analysis to find and delete the impossible deadlock, then update the potential deadlock set.(3)Based on the software defect detecting tool-DTS (Defect Testing System), we design and implement the algorithm that is presented in this thesis. Our deadlock detection sub-system contains five parts:concurrent feature analysis block, alias analysis block, reachable analysis block, gatelock analysis block, escape and parallel analysis block. Also, we have applied it to a suite of multi-threaded Java programs comprising over 225KLOC. We can find the deadlock that we discussed in the thesis efficiently.