A family of cost-effective test coverage strategies for multithreaded programs and Web services

Abstract

Web services demand rapid revisions, which may introduce faults, and its multithreaded software components often incur concurrency bugs, such as data races, which can be hard to detect. Nonetheless, testing of above-kind software systems must be conducted comprehensively within each short revision turnaround time. In this thesis, I examine and formulate new cost-effective strategies to address the identified new challenges. The first contribution is the first work that formulates a family of meta-level strategies to test multithreaded programs. A widely applied assumption of many existing studies on testing against concurrency bugs is that the same piece of object code that produces these execution traces has been given to them. I have developed a new family of strategies that systematically, randomly, or historically select different pieces of object codes generated by setting different compiler optimization options when compiling the source code of a multithreaded program. I have validated these strategies through a large-scale experiment on real-world programs with data race bugs. The results have shown that our family of strategies can significantly enhance the cost-effectiveness of existing dynamic techniques in detecting data races. I have also shown an architecture to implement the strategies of the above as a cloud-based service called SDA-Cloud. To the best of our knowledge, it is the first work to design dynamic data race detection as a cloud-based service. The second contribution is the first work to study the effectiveness of test case prioritization in adverse effectiveness scenarios in service regression testing. Existing studies evaluate the effectiveness of test case prioritization techniques and design factors only in average scenarios. I study to what extent the effectiveness measure in the average scenarios can be extrapolated to the adverse scenarios through a large-scale empirical study. The result shows that a noticeable portion of techniques show inconsistent effectiveness results with respect to random ordering between the average scenarios and the adverse scenarios on the same subject. At the test suite level, all studied techniques show the inconsistent effectiveness, even though there is a strong linear correlation between the effectiveness in the two types of scenarios for the same technique on the same test suite. The two ends of the effectiveness spectrum of each technique exhibit a distinguishing behavior from the factor’s perspective. The effect of the level change of the design factor is being more consistent with that in the average scenarios when going through the least effective end to the most effective end. To the best of our knowledge, it is the first work to study the test case prioritization effective in adverse scenarios. In summary, this thesis makes three main contributions: the first work to systematically explore the dimension of compile optimization options for concurrency bug detection, the first work to study the effectiveness of regression testing techniques in adverse effectiveness scenarios and its relation to the average scenarios, and the first architecture model for dynamic data race detection as a cloud-based service.

Date of Award	15 Jul 2015
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wing Kwong CHAN (Supervisor) & Y.T. Yu (Supervisor)