Semantic Analyses to Detect and Localize Software Regression Errors

Abstract

Software maintenance takes up the major cost of a software project. When changes are made on software, extensive testing and debugging activities are performed to preserve software quality. Most of the existing testing and debugging techniques only focus on the current software version while ignoring previous program versions. However, we observe that previous software versions can be exploited to benefit these techniques in the following ways: (i) previous software versions serve as the reference for the current version with respect to unchanged software behavior, and (ii) previous analysis results can be reused given that they are not affected by software changes. We also observe that the recent advance in dynamic symbolic execution provides the adequate machinery for building semantic analysis techniques. Built upon these observations, we present several techniques for maintaining software quality in software evolution.

This thesis consists of the following five parts. First, we develop a test-suite augmentation technique based on code changes. We generate a test-input that has different outputs in the previous and current programs. The generated test-input can be helpful for comprehending program changes as well as testing the changed functionality of the program. Guided by program control structure and program changes, our technique was shown to be efficient in generating change-exposing test cases. Second, we present DARWIN, a debugging technique for evolving programs. When a bug is found through testing, we use DARWIN to locate the root cause of the bug. While using path condition to extract program semantics, our debugging technique could be more accurate than syntactic based approaches. Moreover, our DARWIN technique is also applicable to two entirely different implementations of the same specification. Third, we present a path partitioning technique that improves the state-of-the-art in dynamic symbolic execution. Program paths with the same input-output relationship are grouped in the same partition that is captured by relevant-slice condition. By improving dynamic symbolic execution, our debugging technique DARWIN achieves better efficiency and more accurate results. Fourth, we present the notion of change contracts, a contract language to document user intention of changes. Program requirement plays the most critical role in any testing and debugging activities. Unfortunately, a large volume of code does not come with any formal requirements, leaving program contract checking with full requirement unrealistic. Assuming that previous program versions are thoroughly tested, our proposed changed contract allows the users to only specify the changed program behavior. We have confirmed the usability of change contract via a user study with real-world program changes. Finally, we present a technique to localize program failure causes due to evolving execution environments.

As evidenced by comprehensive user studies and experiments on real-life programs, our proposed approaches ease various tasks in maintaining software quality, thereby helping to produce quality software in the face of never-ending software evolution.