UCLA

Detecting computational states of a program, where safety requirements have been violated, is the main task of a software tester. We focus on three critical safety requirements. First, finding maximum stack usage in event-based systems, in order to avoid stack overflow. Second and third, absence of data race and deadlock in parallel programs, respectively. We will present how particular states of computation, where the above mentioned requirement are violated, is reached.

Directed testing has shown considerable success in both academy and industry. However, applying directed testing's core form on programming paradigms, with a more complicated control flow is not nearly as successful as on sequential programs. The goal of this dissertation is to address how we can enhance directed testing to perform well with event-driven and parallel programs.

For event-driven software we present a new approach, termed event-based directed testing. Our approach combines aspects of random testing and directed testing to generate challenging event sequences, for testing event-driven software.

Our experiments show, we achieve significantly improved branch coverage and larger maximum stack sizes.

xi

For parallel programs, we also present a new dynamic technique to detect data races and deadlocks. Our technique combines previous work on concolic execution with a new constraint-based approach to drive an execution towards a concurrency bug candidate. Our technique has found almost twice as many real concurrency bugs as the four previous techniques combined.