Systematic Testing of Concurrent Software

Software-based systems are omnipresent and, therefore, have to work reliably. Efficient testing techniques become crucial tools to build reliable systems. In particular, test automaton plays an important role and research on automated testing techniques for sequential software made great progress in recent years. However, modern processor architectures require a shift from sequential to concurrent software. This complicates the development of reliable software. For example, programmers have to consider complex synchronization between processes and threads. Testing of concurrent software is incredibly challenging since all possible interleavings of operations from different threads and processes have to be considered to ensure that no important corner case is missed and, without adequate approaches, this causes a combinatorial explosion that renders systematic testing infeasible. Industrial testing tools, like Microsofts SAGE, show that systematic testing can be applied even to large sequential programs, but such a proof of scalability is still missing for concurrent programs. The first part of this project will contribute a study of design principles for scalable systematic testing techniques for complex concurrent software and will demonstrate that systematic testing can scale to concurrent software of practical relevance. Recently, the applicant co-developed con2colic testing, a new systematic testing approach for concurrent software that shows promising performance results. However, many open research questions have to be solved to achieve the same practical impact that systematic software testing for sequential software currently has on industry. The second part of this project is concerned with program repair after testing has found an error. Manual program repair is laborious and complex and, especially for concurrent software, regularly leads to the introduction of new errors during program repair. Therefore, like testing, program repair should be automated as much as possible. However, in general, program repair can become intractable even for very small problem instances and, therefore, efficient domain- specific solutions have to be found. This project will focus on the repair of algorithmic aspects of programs that repeatedly invoke domain-specific decision procedures during a computation, e.g., programs that involve geometric computations and repeatedly decide whether a line intersects with a plane. Such contradictions can occur, for example, if the implementation of the decision procedure is prone to imprecisions due to rounding errors in numerical computations or temporal variability in concurrent computations.