Research On Fully Null Pointer Dereference Defect Detection Technique

Research on trustworthy software is an important work in the field of software engineering, and it’s an efficient approach to produce trustworthy software by discovering and eliminating software defects during the development process or test phase. Defects of software code are the main cause of the problem of software faults and vulnerabilities, and static analysis is an effective way to detect these defects, but static analysis could not be both sound and complete, which might lead to false negatives and false positives. Some high trustworthy software needs to achieve zero false negatives of some types of defects, so it has the practical value for research on fully defects detection.Null pointer dereference is a kind of representative defects in software code, and it is also a hotspot of defect detection. Although there has been many researches on null pointer dereference detection up to now, it’s difficult to achieve fully null pointer dereference detection. Hence, this paper mainly researches on the key technologies for sound data flow analsis and fully null pointer dereference detection, and main contributions include:(1) Fully recognizing addressable expressions. This paper makes addressable expression as basic objects of static analysis of C programs, and introduces an approach to recognizing addressable expressions from abstract syntax tree. Firstly, this paper induces grammar patterns of C addressable expressions, and maps each kind of them to the node of abstract syntax tree; secondly, this paper introduces the corresponding naming rule, type inference rule and scope inducing rule of addressable expressions; finally, this paper introduces the approach to recognizing addressable expressions from abstract syntax tree.(2) Applying region-based symbolic three-valued logic (RSTVL) to describe the store state of memory object. RSTVL simulations memory chunk of a memory object by a region, expresses the value of a region applying a symbolic expression, and uses domain to express the value of each symbol in symbolic expressions, and translates operations about addressable expressions into operations on regions. As a sound abstract memory model, RSTVL can describe shape of data structures, store state of memory objects, and all kinds of relations of addressable expressions including point-to relations, hierarchical relations and logic relations.(3) Data flow analysis based on RSTVL. This paper introduces an approach to flow-sensitive, field-sensitive intra-procedural data flow analysis based on RSTVL, the analysis translates operations about addressable expressions into operations on regions, and analysis value data and address data together, so achieves data flow analysis, point-to analysis and shape analysis in a unified framework. This paper focuses on the analysis of migration operations about assignment statements, branch statements and loop statements, and proves the soundness of analysis about these three kinds of statements based on abstract interpretation theory, and further proves the soundness of our data flow analysis.(4) Inter-procedural data flow analysis based on symbolic function summary. This paper introduces an approach to field-sensitive, context-sensitive inter-procedural data flow analysis, based on the result of intra-procedural data flow analysis, this approach expresses the behaviour of a function applying symbolic function summary which is described by RSTVL; at the call site, this approach instantiate the symbolic function summary based on the calling context described by RSTVL, achieves fileld-sensitive, context-sensitive inter-procedural data flow analysis.(5) Fully null pointer dereference defects detection. Based on the results of fully recognizing addressable expressions, this paper recognizes referenced pointers from abstract syntax tree; in order to meet the need of null pointer dereferences defects detection, this paper introduces the concept of point-to attributes of pointers, and judgement rules of pointer dereference based on the point-to attribute. In order to detects inter-procedural null pointer dereference defects, for the referenced pointer which point-to attribute is unknown, this paper get related external pointers and add them into the null pointer dereference precondition of function summary, at the call site, based on the calling context describles by RSTVL, this paper induces detecting objects of null pointer dereference which mappes the pointers in precondition on function summary, and achieves inter-procedural null pointer dereference defects based on judgement rules of pointer dereference.To sum up, in this dissertation, several key problems of data flow analysis and null pointer dereference defect detection have been studied and some contributions have been achieved. These key technologies have been implemented in a software defect detecting tool DTSC_RSTVL, and a large number of test results show that DTSC_RSTVL can fully detects null pointer dereference defects of C programs.