Research On An Uniformed Control-flow Based Software Testing Coverage Criteria And Symbolic Execution Guidance

Software testing is an important way to guarantee software quality, which is wide-1y used in industry. However, since exhaustive testing is heavily consuming, in real world, one key problem of software testing is to measure the testing adequacy. On this basis, various control-flow based software testing criteria are proposed, which measure the occurrence of different control-flow events to capture the program behavior and measure the testing adequacy. Traditional control-flow based software testing cover-age criteria, such as statement coverage, branch coverage, is easily to understand and implement, which makes them the most practical and widely used. Nonetheless, since a statement or branch contains few context information, such coverage criteria are too shallow to capture and show the behavior of a program; to the contrary, path coverage criterion can capture the program behavior with small granularity, which can provide a more comprehensive way to understand the execution state of a program, however, since the path explosion problem make it high consuming and hard to achieve, it can not be widespread applied. In that case, more than form differences amount existing various control-flow based coverage criteria, there is also a huge gap of complexity and cost between branch coverage and path coverage. The lack of uniformed, continu-ous coverage spectra makes the industry hard to judge and control testing consumption with small granularity. In the other hand, after selecting a coverage criterion, another key problem of software testing is how to generate test cases effectively. Symbolic execution technique can systematically explore and traverse the execution path space of the program to generate test cases, since the execution path space is usually huge or even infinite, people need effective methods and techniques for guiding the procedure of symbolic execution to improve the efficiency of test case generation and reduce the cost.In this paper, we launch the researches based on establishing a uniformed control-flow based software testing coverage criterion and applying it for symbolic execution guidance. The main contribution addresses the following aspects:1. We propose a uniformed control-flow based coverage criterion-Length-n Sub-path Coverage Criterion(LSC(n)). LSC(n) measures the covering situation of Length-n Subpath, a consecutive sub-sequence from a complete path with n branches in the control flow, to flexibly capture a continuous program spectra from branch coverage to path coverae. It provide a great support for industry to judge and control the testing consumption with continuous small granularity.2. Based on LSC(n), we propose a search strategy to steer symbolic execution to less travelled parts of the program. In this strategy, based on the explored part-s of the program, we choose the execution state corresponding to the Length-n Subpath with the fewest frequency to continue the exploration. The strategy is implemented in the state-of-art symbolic execution engine KLEE, experiment re-sults show that compared to traditional strategy, this strategy can guide symbolic execution to cover the program faster and locate more defects.3. Based on LSC(n), we propose a search strategy to guide symbolic execution to user-defined important parts of the program. For the scenario that the tester need to focus on testing or inspection some important part of the program, this strat-egy integrate the frequency of explored parts and the covering situation for the important part of each Length-n Subpath, calculate a weight for each Length-n Subpath, and select the execution state corresponding to the Length-n Subpath with highest weight to continue the exploration. Based on this method, we im-plement the strategy in the symbolic execution engine KLEE, experiment result show that this strategy can explore the important part with higher priority and generate corresponding test cases.4. Based on LSC(n), we propose a search strategy to direct symbolic execution to specific target(s) of the program. Compared to conduct a general or part explo-ration for the program, direct symbolic execution to cover specific statement(s) can reduce the search space efficiently. This strategy analyzes the target state-ment(s), calculates all possible Length-n Subpaths which cover the target(s) in control flow graph, and prunes those execution states corresponding to irrelevan-t Length-n Subpaths to guide symbolic execution focus on the execution paths covering the target statement(s). Based on this strategy, we take the static anal-ysis warning as an instance of specific target(s), implement a tool for automat-ic buffer overflow warning inspection and bug repair. Experiments shows this method can increase the efficiency of search and validate the correctness of the defect warning.