Heuristics for concolic software testing

Software testing is an essential part of the software development process. Concolic testing is an automated unit test generation technique which is a result of decades of study on making the automated testing scalable. However, bottlenecks such as constraint solving still prevents concolic testers to be used in large projects. The constraint solving bottleneck occurs due to the large number of branches on the execution paths of a Unit Under Test (UUT). In this thesis, we design a novel constraint solving strategy called Incremental Partial Path Constraints (IPPC) on top of a standard concolic tester. Our strategy makes more but smaller queries to the constraint solver, i.e. ignores some path conditions. We implement IPPC on top of a known concolic testing framework, CREST. We show that it is possible to reach the same branch coverage as the standard concolic tester while decreasing the burden on the constraint solver. We support our claims by testing several C programs using different strategies. Experimental results show that our modification improves runtime performance of the standard concolic tester in half of the experiments and results in more than 5x speedup when the UUT has many infeasible paths. Ultimately, IPPC eliminates the need for solving large constraints while automatically generating unit tests.