Effective Heuristic-based Test Generation Techniques for Concurrent Software

With the increasing dependency on software systems, we require them to be reliable and correct. Software testing is the predominant approach in industry for finding software errors. There has been a great advance in testing sequential programs throughout the past decades. Several techniques have been introduced with the aim of automatically generating input values such that the executions of the program with those inputs provide meaningful coverage guarantees for the program. Today, multi-threaded (concurrent) programs are becoming pervasive in the era of multiprocessor systems. The behaviour of a concurrent program depends not only on the input values but also on the way the executions of threads are interleaved. Testing concurrent programs is notoriously hard because often there are exponentially large number of interleavings of executions of threads that has to be explored. In this thesis, we propose an array of heuristicbased testing techniques for concurrent programs to prioritize a subset of interleavings and test as many of them as possible. To that end, we develop: (A) a sound and scalable technique that based on the events of an observed execution, predicts runs that might contain null-pointer dereferences. This technique explores the interleaving space (based on the observed execution) while keeping the input values fixed and can be adapted to predict other types of bugs. (B) a test generation technique that uses a set of program executions as a program under-approximation to explore both input and interleaving spaces. This technique generates tests that increase branch coverage in concurrent programs based their approximation models. (C) a new heuristic, called bounded-interference, for input/interleaving exploration. It is defined based on the notion of data-flow between threads and is parameterized by the number of interferences among threads. Testing techniques that employ this heuristic are able to provide coverage guarantees for concurrent programs (modulo interference bound). (D) a testing technique which adapts the sequential concolic testing to concurrent programs by incorporating the bounded-interference heuristic into it. The technique provides branch coverage guarantees for concurrent programs. Based on the above techniques, we have developed tools and used them to successfully find bugs in several traditional concurrency benchmarks.Ph