Detecting Infeasible Paths Based On Program Slicing And Symbolic Execution

The detection of infeasible paths is particularly significant, it is one of the quality guarantees of computer program. During the process of software testing, if the selected test data is for those statements which are in unreachable paths, then the data will not actually be tested, which will cause a lot of waste. The current detection methods of infeasible paths can be divided into two categories, namely static detection and dynamic detection method, each of them has some problems.Although static detection methods may have the less consumption of time and space resources, they are likely to cause false positives and omissions. Dynamic detection methods may cause much more consumption of time and space resources, as well as they may cause state explosion problems with complex paths.This paper presents an infeasible path detection method based on program slicing and symbolic execution. In this method, we take advanced programming language code as input,transfer it into the form of LLVM intermediate representation, then do the calculation of its static program slicing and get the results. Then we take the LLVM IR for symbolic execution, to find all feasible different inputs, and do the calculation of its dynamic program slicing according to the inputs. Comparing the results of static program slicing with the union of all the results of dynamic program slicing to find the differences which are the infeasible paths. This method can ease the exist problems of false positives and omission to a certain extent.In addition, in order to deal with the problem of time and space resource consumption, this paper also proposes a method to reduce the size of the program slicing in a certain degree. After static program slicing, we can use constraint solving to find infeasible paths due to the contradictions of multiple branches conditions in the code according to the control flow graph.Therefore the examination of the dynamic program slicing can reduce resource consumption to some extent, improve the efficiency of detection, and ease the existing some problems of dynamic detection methods.