Research On Key Technologies Of Improving The Accuracy Of Static Defect Detecting

Software code defects are the main cause of the problem of software failures and vulnerabilities. Software defect detection methodology can be divided into dynamic and static techniques. Static techniques need not execute the software, which find defects by static analysis techniques. From the perspective of computability theory, static analysis is a computationally undecidable problem. Improving detection accuracy is the core issue of static defect detection, which includes two aspects: to reduce false positives and reduce false negative. A large number of false positives will make people lose confidence in the analysis tool. False negative will cause the program to have the illusion of a higher quality.This paper is sponsored by the National High-Tech Research and Development Plan of China under Grant2009AA012404,2007AA010302and2006AA01Z184. Its core work is to improve the accuracy of static defect detection from the perspective of the abstract domain design, path-sensitive analysis and context-sensitive analysis. Paper’s main contributions include:(1) How to better approximate and calculate the values of variables is the key to improve the accuracy of static analysis. Based on abstract interpretation, this paper proposes an abstract representation and computation method to get the variable values, which considers the relationship between variables. Firstly, in order to accurately represent the union of two separate intervals, it extends the classical single-interval abstract domain to the interval set abstract domain; secondly, in order to deal with the relationship between variables introduced by the assignment, the abstract domain of symbolic expressions is proposed, which can be combined with other abstract methods and improves their abstract accuracy. Finally, this paper proposes a uniform algorithm to calculate the abstract value of the variable, which does not depend on the specific abstract domain.(2) The defect detection based on finite state machine can be turned into a traditional data flow problem. There are three typical solution of data flow problem: IDEAL solution, MOP solution, MFP solution. Traditional iterative approaches to seek MFP solution are flow-sensitive but path-insensitive. This paper presents a new path-sensitive algorithm for static defect detecting running in polynomial time. In this method, property state conditions are represented by abstract domain of variables, and infeasible paths can be identified when some variable’s abstract value range is empty. This method avoids the combination explosion of full path analysis by merging the conditions of identical property state at join points in the CFG (control flow graph). Practical test results show that this method can reduce false positive.(3) As to the defect detection based on finite state machine, the interprocedural analysis has its own characteristics: it only concerns about whether the state of the defect state machine instances is changed. This paper presents a global defect detection method based on function summary: Firstly, it defines the function summary for defect detection, which includes precondition information collection, side effect information collection and feature information collection. Function summary can be considered as the abstract of actual function semantics. Precondition information collection generation can be dealed with as a reverse data flow problems, the generation of side effect information collection and feature information collection can be dealed with as two forward data flow problems. Secondly, in order to achieve context-sensitive analysis, this paper introduces the concept of summary conditions. Summary conditions are represented by the abstract values of variables, which define the context conditions to apply the function summary. Finally, based on function summary, a global iterative detect detection algorithm is proposed. Experiments show that proposed method can reduce false positives and false negatives.To sum up, in this dissertation, several key problems of improving the accuracy of static defect detecting have been studied and some contributions have been achieved. These key tehnologies have been implemented in a software defect detecting tool-DTS (Defect Testing System). Experients show that they have a bright future for industry applications.