Testing and Debugging Event-based Software through OS-level Replay

Abstract

Testing and debugging are essential but most complex activities of the software development process, and consume 50-75% of the total software development cost. Event-based software, an increasingly prevalent class of software, poses some additional challenges for testing and debugging. First, they require generating a large number of concrete test-cases to verify all the possible combinations of events in the software. The execution of such large number of test cases involves significant manual effort and/or special hardware support. Second, the events in such systems are triggered non-deterministically, for example, due to unpredictable I/O timing and user actions. This non-determinism can lead to some severe failures in the production systems which cannot be reproduced when given identical test inputs under identical conditions. Without the ability to reproduce, debugging such failures becomes an inefficient and time-consuming process of trial and error. This dissertation addresses the above-mentioned problems by combining the state-of-the-art testing and debugging techniques with an Operating System level record and replay mechanism (OS-level replay). The idea of an OS-level replay system is based on the observation that the events happening in a user process can be fully identified, captured and reproduced at the operating system level with instruction-accurate fidelity. The low-level events captured regarding a high-level event in the program can be used to generate concrete test cases. In addition, the OS-level replay mechanism helps in automatically emulating any desired sequence of low-level events without requiring special hardware support and human intervention. This ability can be used to enable the automated execution of concrete test cases. Since the events captured during original program execution can be fed to the program during the subsequent executions, it is also possible to reconstruct the entire sequence of events that caused a non-deterministic failure in the original run. From this vantage point, a developer can replay a non-deterministic failure of a program and find its root-cause effectively using cyclic debugging methods. Relying on the aforementioned ideas, this dissertation introduces: 1. A model-based replay testing framework, which automatically generates abstract test cases by applying n-switch coverage on a finite state machine (FSM) model of the software. The use of OS-level replay is then introduced to transform abstract test cases into concrete test cases and execute them in an automated manner. 2. A method for debugging non- deterministic failures, which employs the OS-level replay system to reproduce a non-deterministic failure and allows cyclic analysis during replay to find out the sources of failure. Owing to the fact that event-based programs are also vulnerable to concurrency bugs which are especially challenging to diagnose, a replay analysis method is presented to find out the root cause of these bugs. This method combines static analysis, dynamic tracing during replay, and delta debugging to pinpoint the failure-inducing memory access patterns that led to a concurrency bug failure. To demonstrate the practical usefulness of the model-based replay testing framework, a prototype of an OS-level replay system is implemented in Android to test an important class of event-based software; GUI applications. The experimental results show that the suggested approach is beneficial in providing support for automated testing and is able to expose operation errors, transfer errors and extra state errors that are typical to an application modeled as FSM. For the second part of this dissertation which involves debugging non-deterministic failures in event-based programs, we extended the OS-level replay mechanism to a full-fledged operating system, i.e., Linux. The record and replay system was implemented for an ARMv7 uniprocessor-based system. It incurs low overhead during recording, i.e., under 15% for applications such as text-editors, web-browsers, and network benchmarks. Hence, such a system can be used in an always-on mode during testing or production runs to catch non-deterministic and rarely occurring bugs. We present several debug case studies from real-world applications, where we effectively used the proposed replay-based system to reproduce and diagnose concurrency bugs, i.e., single-variable data races and atomicity violations found in event-based programs. This dissertation has made original contributions to the Software Engineering scholarly body of knowledge in terms of a substantial literature review of existing software testing and debugging techniques used for event-based software, and record and replay systems. In addition, the methodologies and results presented in the thesis provide a foundation for further research into replay-based testing and debugging which can help to meet the ultimate goal of producing trusted and reliable software.