Research On Static Analysis And Related Defect Detection Of Sequential Storage Structure In C Program

Sequential storage structures such as array and dynamically allocated memory blocks in C programs are widely used in software programming.Defects such as out-of-bounds and memory leak caused by it can lead to a program running chaos or even crash.However,the complexity of its structure makes it difficult to use the traditional abstract memory model and data flow analysis methods to describe and analyze it accurately.Especially when access the sequential storage structure by pointers,most data flow analysis methods only pay attention to the points-to information of the pointer without considering the possible offset that may occur in the process.It makes low accuracy in the analysis of the sequential storage structure and high false positives or high false negatives in detecting related defects.Aiming at the existing problems,this paper aims to design the abstract memory model of the sequential storage structure of the C program,realizing precise analysis of it and related defects detection fully.This research mainly includes the abstract memory model design,data flow analysis,and memory leak detection.The specific work of this paper is shown as follows:(1)Design of abstract memory model Seq MM for sequential storage structure.Seq MM uses multiple serial regions to simulate allocated memory blocks for sequential storage structure during program execution.Its specific values are represented by intervals and interval computation,depicting the value or address of sequential storage structure and the relationship between variables or memory regions,including points-to relationships,hierarchical relationships,linear and logic relationships,and offset relationships.(2)Data flow analysis of sequential storage structure based on Seq MM.In this paper,the related operations of sequential storage structure,including migration operation,predicate operation,inter-procedural operation,are summarized first.Moreover,the Worklist algorithm is implemented based on Seq MM to calculate respectively state of each node in the control flow graph,which can calculate the possible value interval of the analysis object at each program point,realizing accurate analysis of procedures state of three operations.(3)Memory leak detection algorithm of C program.Based on the description of the state of each program point by Seq MM and data flow analysis,the abstract storage status of the continuous memory blocks from allocated points are tracked by this algorithm first,which can label various types of nodes in the control flow graph according to the different behavior.Then,a control flow graph will be established in this paper,capable of fully detecting memory leaks resulting from unreleased or partially freed allocated dynamically memory blocks.In conclusion,the abstract storage model,data flow analysis,and memory leak detection about sequential storage structure in the C program are studied in this paper.The above method has been implemented in the defect detection tool DTSC＿Seq MM.The experimental results show that the tool can effectively analyze the related operations of the sequential storage structure and detect the unreleased and partially released defects of the dynamically allocated memory.