The Design And Implementation Of Efficiency Optimization Of Static Analysis Tool

The purpose of the paper is to optimize the efficiency of a C program static analysis tool developed by the lab.In order to detect complex vulnerabilities,the tool uses a path-sensitive and context-sensitive analysis strategy.This strategy makes the number of paths grow nonlinearly with the growth of code size,resulting in low efficiency of analysis.The size of the code detected is far less than expected.Efficiency optimization is an extremely important and indispensable task.The path-sensitive feature is to traverse all possible paths.In this paper,the pre-traversing module is designed and implemented to prune the CFG.In order to implement the module,the paper first implements the traversal framework as depth-first traversal,and a new data record algorithm is designed and implemented to avoid the large amount of data backup and recovery at the branch nodes.Before the pre-traversal,all the defined functions are sorted topologically so that the called function is traversed earlier than the calling function.The pre-traversal first marks the single nodes in the flow graph based on common vulnerability scenarios and user configuration information,and then uses the iterative algorithm to propagate the state of the marked nodes to their forwards until the state of all nodes in the entire CFG no longer changes,then the iterative algorithm ends.After the iterative algorithm is finished,the paths that can reach the marked nodes are all marked,and the other paths will not be traversed.When checking for vulnerabilities,the pre-traversal of the tagged information and the contextual data information ultimately determine whether the marked paths should be traversed.The context-sensitive feature is to analyze every function that is called.After analyzing the CFG of the called function,return to the calling function to continue the analysis.The function call causes a sharp increase in the number of path.In order to reduce the function call,the paper changes the original embedded analysis method to the memory analysis method,that is,records the point information that has appeared to achieve the purpose of reuse.In order to reduce the number of patterns to be recorded and to increase the probability of reuse,the paper uses the extension name to abstract the point information to call pattern.For each function to use the same extension every time,use the pre-assignment policy to assign the extension.It will take the corresponding result as the result of the analysis if the pattern appeared before,no longer traverse the CFG of the function,or analyze the function and record the call mode and analysis result.In order to make the security analysis tool more flexible to deal with different characteristics and size of the detection code,the paper add a number of configuration items in the pre-traversal and cross-process pattern matching module.The users can configure these parameters according to the actual situation,so that tools more focus on analysis efficiency or analysis accuracy.The paper finally tests the effect of each module on efficiency.The result of the test show that the pre-traversal and cross-process pattern matching modules have a great effect on the efficiency improvement.Tool significantly improve the detection efficiency but still be able to maintain the original analysis accuracy.The efficiency optimization has achieved the desired effect.