Design And Implementation Of Program Slicing And Transformation In C Analysis Tool

Nowadays,with the rapid development of computer technology,software plays an important role in our daily life.The C programming language has been used widely for 40 years.It still has a strong advantage in the field of system software such as operating system,compiler and database.C is famous for high efficiency in low-level field.On the other hand,it brings much burden to programmers,who have to pay attention to common defects such as memory leak,null pointer and dangling pointer dereference,buffer overflow.At present,to improve the reliability and security of software,we can use program verification,dynamic test and static analysis.Program verification has not yet been done automatically.The accuracy and coverage rate of dynamic test is greatly affected by input set.In addition,the cost and risk in run-time is higher than others.The static analysis is a more precise and cheaper method.In the field of static analysis,symbolic execution is widely used for auto-generation of test cases.Its main idea is to symbolize values of the variables in the code and simulate to execute all possible paths.As the control structures become more and more complex,the number of states to be executed rise dramatically,which has a poor effect on scalability of static analysis tools.In this paper,two optimization methods are proposed to alleviate the state explosion problem in the different stages of symbolic execution.Program slicing for defects is used to preprocess the intermediate representation of testee.Firstly,we generate the slicing criterion of source programs according to defects that users concern about.Then we analyze the source code to generate Data Dependence Graph and Control Dependence Graph,which constitute Program Dependence Graph.Next,the program is sliced according to the slicing criterion so that the source code could be reduced.Finally,we use the program analyzer to analyze the sliced program.During the execution of symbolic executor,program transformation is used to transform control structures which have no side effect.When the static analysis tool performs a function,we analysis all the control structures in that function.If some control structure has no effect on the subsequent execution of the program,it will be simplified.In order not to affect the analysis precision,we extract all instructions which have potential flaw,which reduces the number of paths and improves the performance of analysis tool.Our research group has implemented a C program static analysis tool based on symbolic execution.By using the above two optimization methods,the performance of the static analysis tool has been improved effectively.