Improved regression testing of multithreaded programs

The advent of multicore processors has necessitated the use of parallelism to extract greater software performance. Shared-memory multithreaded programming is currently the dominant parallel programming paradigm. However, multithreaded programs are difficult to get right and are often afflicted by bugs like data races, deadlocks, and atomicity violations which may be triggered only by a specific set of schedules. Multithreaded programs are also difficult to test. Since the behavior of multithreaded programs can depend on the schedule, developers need to express and enforce schedules in multithreaded tests. However, there exists no reliable, modular, efficient, and intuitive methodology for expressing and enforcing schedules in multithreaded tests. Traditionally, developers enforce schedules with time delays, e.g., using Thread.sleep in Java. Unfortunately, this sleep-based approach can produce false positives or negatives, and can result in unnecessarily long testing time. This dissertation presents a novel framework, called IMUnit, for expressing and enforcing schedules reliably and efficiently in multithreaded tests. IMUnit includes a new language for specifying schedules as constraints on events encountered during test execution and a tool for automatically enforcing the specified schedules during test execution. This dissertation also introduces a tool that helps developers migrate their legacy, sleep-based tests into event-based IMUnit tests. The tool uses new techniques for inferring events and schedules from the executions of sleep-based tests. The inference techniques have high precision and recall, of over 75%, and compared to sleep-based tests, IMUnit reduces testing time on average 3.39x. We also describe our experience in migrating over 200 sleep-based tests. Since each multithreaded test can have different results for different schedules, it needs to be explored for multiple schedules (ideally all possible schedules) to ensure the property being tested. Exploration is expensive, especially in the context of regression testing where tests need to be re-explored when programs evolve. Most recent research on testing multithreaded code focuses on improving the exploration for one code version. While there have been promising results, most techniques are slow and do not exploit the fact that code evolves. To improve the exploration of multithreaded tests in the regression testing context, this dissertation proposes a technique, called CAPP, that leverages knowledge about code evolution to prioritize the exploration of multithreaded tests. We evaluated CAPP on the detection of 15 faults in multithreaded Java programs, including large open-source programs, and found that the technique can significantly reduce the exploration required to detect regression faults in multithreaded code compared to the state-of-the-art exploration techniques that do not prioritize exploration based on code evolution