Budget-Sensitive Testing and Analysis Strategies and Their Applications to Concurrent and Service-Based Systems

This dissertation, "Budget-sensitive Testing and Analysis Strategies and Their Applications to Concurrent and Service-based Systems" by Ke, Zhai, 翟可, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Software testing is the most widely practiced approach to assure the correctness of programs. Despite decades of research progress, software testing is still considered very resource-demanding and time-consuming. In the recent decade, the wide adoption of multithreaded programs and the service-based architecture has further aggravated the problem that we are facing. In this thesis, we study issues in software testing where resource constraints (such as time spent and memory space allocated) are important considerations, and we look for testing techniques that are significantly advanced in effectiveness and efficiency given limited quotas of resources, which we refer to as budget. Our main focus is on two types of systems: concurrent systems and service-based systems. The concurrent system is a class of computing system where programs are designed as collections of interacting and parallel computational processes. Unfortunately, concurrent programs are well known to be difficult to write and test: various concurrency bugs still exist in heavily-tested programs. To make it worse, detecting concurrency bugs is expensive, which is, for example, notorious for dynamic detection techniques that target high precision. This thesis proposes a dynamic sampling framework, CARISMA, to reduce the overhead dramatically while still largely preserving the bug detection capability. To achieve its goal, CARISMA intelligently allocates the limited budget on the computation resource through sampling. The core of CARISMA is a budget estimation and allocation framework whose correctness has been proven mathematically. Another source of cost comes from the nondeterministic nature of concurrent systems. A common practice to test concurrent system is through stress testing where a system is executed with a large number of test cases to achieve a high coverage of the execution space. Stress testing is inherently costly. To this end, it is critical that the bug detection for each execution is effective, which demands a powerful test oracle. This thesis proposes such a test oracle, OLIN, which reports anomalies in the concurrent executions of programs. OLIN finds concurrency bugs that are consistently missed by previous techniques and incurs low overhead. OLIN can achieve a higher effectiveness within given time and computational budgets. Service-based systems are composed of loosely coupled and unassociated units of functional units and are often highly concurrent and distributed. We have witnessed their prosperity in recent decades. Service-based systems are highly dynamic and regression testing techniques are applied to ensure their previously established functionality and correctness are not adversely affected by subsequent evolutions. However, regression testing is expensive and our thesis focuses on the prioritization of regression test cases to improve the effectiveness of testing within predefined constraints. This thesis proposes a family of prioritization metrics for regression testing of location-based services and presents a case study to evaluate their performance. In conclusion, this thesis makes the following contributions to software testing and analysis: (1) a dynamic sampling framework for concurrency bug detection, (2) a test oracle for concurrent testing, and (3) a family of test case prioritization techniques for service-based systems. These contributions s