Driving Concolic Testing to achieve higher MC/DC through source code transformations

Abstract

Test coverage criteria, including logical coverage, such as Modified Condition / Decision Coverage (MC/DC) have been increasingly used in safety-critical or mission-critical domains, complementing the more popularly used structural coverage criteria such as branch coverage. However, existing automated test-generation approaches such as concolic test generation often target at branch coverage for test generation and selection. Therefore, they do not support testing against logical coverage. Existing test-generation approaches fail to strategically choose input values to achieve high or complete logical coverages. To
address these issues, we propose some source code pre-processing (program transformation) techniques to generate test inputs that achieve logical coverage for the program under test. In Particular, we use code instrumentation to assist an existing test-generation approach(Concolic Testing) that targets, at achieving logical coverage such as MC/DC.

We present code transformation techniques that enable concolic testing execution to achieve increased MC/DC percentage. The transformation techniques introduce several new branches in the program under test. However, we do not modify any existing code of the program. We only insert nested conditional statements with empty branches in the program. These new branches contain constraints that need to be satisfied to achieve an increase in MC/DC. We then supply the transformed program to the concolic tester for dynamic symbolic testing. The generation of input values for the transformed program achieves an increase in MC/DC for the program under test. We have proposed our first code transformation technique named Program Code Transformer (PCT). We use Boolean logic simplification techniques that help generate equivalent simple conditional statements. The equivalent simple conditions for a predicate are inserted in the program under test with empty branches before the particular predicate. We use Boolean algebra properties to solve the Boolean expressions to frame into the Sum of Product (SOP) form. Then, the Boolean expression may become complex. To address this issue, we have applied Quine-McCluskey(QM) technique. After using PCT, MC/DC percentage is still low and insufficient. Hence, it requires some more test input values to achieve an increase in MC/DC percentage. Therefore,we propose another transformer named Exclusive-NOR Code Transformer (EX-NCT). We use Boolean derivative method to generate additional conditional statements for the complex Boolean expressions in the program. These additional conditions contain constraints which show the independent effect of component conditions on the evaluation of a complex condition. The additional conditional statements are inserted in the program under test with empty branches before the particular predicate. We have fused PCT and Ex-NCT to get some more test data, and observed that it really works. We have named this third type of code transformer as Double Refined Code Transformer (DRCT), due to its double transformation nature. We have set up a client-server mesh-topology of the computer systems and executed distributed concolic testing to generate more number of useful test cases. Since, now-a-days many programs are written in object-oriented programming languages, so we have extended our proposed techniques to handle object-oriented language such as Java. We have also extended our proposed techniques to handle multithreaded Java programs.

During experimentation using concolic testers, we found that there are some test inputs with large integer values. We have replaced those values with “0”(Zero) a neutral value and created new test inputs. Then, we observed significant increase in MC/DC percentage. Subsequently, we propose a technique to minimize the number of test cases and another technique to prioritize the test cases.

We have developed some tools to measure MC/DC percentage of the program under test.From the experimental results, it is observed that we have achieved higher MC/DC than that of the existing methods/approaches.