Concurrent data structures are often tested under stress to detect bugs that can only be exposed by some rare interleavings of instructions. A typical stress test for a concurrent data structure creates a number of threads that repeatedly invoke methods of the target data structure. After a failure is detected by a stress test, developers need to localize the fault causing the failure. However, the execution trace of a failed stress test may be very long, making it time-consuming to replay the failure and localize the fault. In this paper, we present an approach to minimizing stress tests for concurrent data structures. Our approach is to create a smaller test that still produces the same failure by removing some of the threads and/or method invocations in the original stress test. We apply delta debugging to identify the threads and method invocations that are essential for causing the failure. Other threads and method invocations are removed to create a smaller stress test. To increase the chance of triggering the original failure during the execution of the new stress test, we force the new execution to replay the original failed execution trace when possible, and try to guide the execution back to the failed trace when the execution diverges. We describe a tool called TestMinimizer and report the results of an empirical study in which TestMinimizer was applied to 16 real-life concurrent data structures. The results of our evaluation showed that TestMinimizer can effectively and efficiently minimize the stress tests for these concurrent data structures.

In server applications, threads are created to handle incoming requests. Since threads consume significant resources including CPU cycles and memory, it is important to control the number of threads that are created. In this paper, we introduce a lightweight, static approach to detecting unbounded thread- instantiation loops that may exist in a server application. The key observation of our approach is that threads are objects of special significance and the decision logic for thread instantiation is typically not complex. Our approach checks loops against some bounded thread-instantiation patterns. A loop is considered bounded if a pattern match is found. Otherwise, it is considered unbounded. Our approach is heuristic by nature. That is, it does not guarantee to detect all the unbounded loops and may report unbounded loops that are actually bounded. To evaluate the effectiveness of our approach, we report an Eclipse plugin called ThreadBoundChecker which implements our approach and an experiment on 24 real-life Java server applications. The results of our evaluation show that our approach can effectively detect unbounded thread-instantiation loops in these applications. In particular, 12 unbounded thread-instantiation loops detected by our approach are confirmed by the original developers.

Abstract Reachability testing is an approach to verifying concurrent programs. During reachability testing, every partially ordered synchronization sequence of a program with a given input is exercised exactly once. In this paper, we present the design and implementation of a distributed reachability testing algorithm for a cluster of workstations. This algorithm allows different test sequences to be exercised concurrently by different workstations without any synchronization, and without any duplication of sequences among workstations. Dynamic load balancing is performed using a work‐stealing scheme. A novel aspect of this scheme is that work‐stealing requests progress in rounds. This round‐based structure identifies overloaded workstations to target for work stealing. Empirical studies show good speedup for four benchmark Java programs and one Lotos specification. Copyright © 2010 John Wiley & Sons, Ltd.

Abstract One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, calledt‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy calledt‐way testing. We present an algorithm that implementst‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate thatt‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.

A Java monitor is a Java class that defines one or more synchronized methods. Unlike a regular object, a Java monitor object is intended to be accessed by multiple threads simultaneously. Thus, testing a Java monitor can be significantly different from testing a regular class. In this paper, we propose a state exploration-based approach to testing a Java monitor. A novel aspect of our approach is that during exploration, threads are introduced on-the-fly, and as needed, to simulate race conditions that can occur when multiple threads try to access a monitor object at the same time. Furthermore, each transition is defined in a way such that the behavior of the threads along each path can be precisely characterized and controlled. We describe a prototype tool called MonitorExplorer and report three case studies that are designed to provide an initial evaluation of our approach

One approach to testing concurrent programs, called reachability testing, generates synchronization sequences automatically and on-the-fly, without constructing any static models. In this paper, we present a general execution model for concurrent programs that allows reachability testing to be applied to several commonly used synchronization constructs. We also present a new method for performing reachability testing. This new method guarantees that every partially ordered synchronization sequence will be exercised exactly once without having to save any sequences that have already been exercised. We describe a prototype reachability testing tool called RichTest and report some empirical results, including a comparison between RichTest and a partial order reduction-based tool called VeriSoft. RichTest performed significantly better for the programs in our study

One approach to testing concurrent programs, called reachability testing, generates test sequences automatically, and on-the-fly, without constructing any static models. To ensure that every partially-ordered synchronization sequence of a program with a given input is exercised exactly once, existing reachability testing algorithms need to save and search through the history of synchronization sequences that have already been exercised, which is impractical for many applications. In this paper, we present a new reachability testing algorithm which does not save any synchronization sequences but still guarantees that every partially-ordered sequence will be exercised exactly once. We describe a reachability testing tool called RichTest and report some empirical results, including a comparison between RichTest and a partial order reduction based tool called VeriSoft. RichTest performed significantly better for the programs in our study.

Concurrent programming is becoming more important in modern software development. However, concurrent programs exhibit non-deterministic behavior, which makes them difficult to test. We describe how to apply reachability testing to semaphore-based multithreaded programs, i.e., programs that use semaphores to synchronize operations on shared data. A novel aspect of reachability testing is that it derives test sequences on-the-fly, avoiding the construction of any static models. Also, our reachability testing algorithms deal with partial orders directly, avoiding the test sequence explosion problem that occurs when independent events are interleaved. We describe a prototype tool called RichTest and report some preliminary results.

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force deterministic program executions according to paths selected from the graph. However, using a reachability graph for test path selection introduces a state explosion problem. To overcome this problem, a reduced graph can be generated using incremental reachability analysis, which consists of repeatedly generating a reachability graph for a subset of LTSs, reducing this graph, and using the reduced graph in place of the original LTSs. Unfortunately, existing incremental reachability analysis techniques generate reduced graphs with insufficient information for deterministic testing. We present an incremental approach to testing concurrent programs. Incremental testing consists of incremental reachability analysis for test path selection and deterministic testing for test execution. We define a new type of reachability graph for incremental analysis, called an annotated labeled transition system (ALTS). An ALTS is an LTS annotated with information necessary for deterministic testing. We propose practical coverage criteria for selecting tests paths from an ALTS and present an ALTS reduction algorithm. The results of several case studies are reported.

This paper describes the results of an investigation into a set of metrics for object-oriented design, called the MOOD metrics. The merits of each of the six MOOD metrics is discussed from a measurement theory viewpoint, taking into account the recognized object-oriented features which they were intended to measure: encapsulation, inheritance, coupling, and polymorphism. Empirical data, collected from three different application domains, is then analyzed using the MOOD metrics, to support this theoretical validation. Results show that (with appropriate changes to remove existing problematic discontinuities) the metrics could be used to provide an overall assessment of a software system, which may be helpful to managers of software development projects. However, further empirical studies are needed before these results can be generalized.

An abstract program is a formal specification that describes the valid behavior of a distributed program without describing particular implementation mechanisms that achieve this behavior. Valid behavior can be modeled as the possible sequences of events that may be observed of a conforming concrete implementation of the abstract program. In this paper, we address the problem of how to select event sequences from an abstract program to test its concrete implementation. Sequencing constraints make explicit certain types of required properties that are expressed only implicitly by an abstract program. The sequencing constraints derived from an abstract program can be used to guide the selection of event sequences during testing. We describe a constraint notation called CSPE and show how to achieve coverage and detect violations of abstract CSPE constraints. Abstract constraints address the problem of how to compare two programs written at different levels of abstraction. Results of an empirical study of CSPE-based testing are reported.

This paper introduces the use of sequencing constraints for specifying, testing, and debugging concurrent programs. An execution of a concurrent program P nondeterministically exercises a sequence of synchronization events, called a synchronization sequence (or SYN-sequence). Sequencing constraints (or constraints) specify restrictions on the allowed SYN-sequences of P. Constraints for P are derived from a formal or informal specification of P and do not have to be complete. The SYN-sequences collected during nondeterministic testing of P can be used to measure coverage and detect violations of P's constraints. Also, SYN-sequences can be generated according to P's constraints and used for deterministic testing of P. This paper shows in detail how to accomplish coverage and detect violations of constraints written in CSPE (Constraints on Succeeding and Preceding Events) by nondeterministic and deterministic testing.

Mutation-based software testing is a powerful technique for testing software systems. It requires executing many slightly different versions of the same program to evaluate the quality of the test cases used to test the program. Mutation-based testing has been applied to sequential software; however, problems are encountered when it is applied to concurrent programs. These problems are a product of the nondeterminism inherent in the executions of concurrent programs. In this paper, we describe a general approach to testing and debugging concurrent programs, called deterministic execution testing and debugging. We then describe a combination of deterministic execution testing and mutation-based testing, called deterministic execution mutation testing (DEMT), and illustrate the DEMT approach with an example.>

A static analysis method is introduced for detecting synchronization errors. This method is to derive constraints on the feasible synchronization sequences of a concurrent program (or program module) P according to P's syntactic and semantic information. These constraints, called feasibility constraints for P, can be compared with constraints in the specification of P to detect specification-dependent errors and can be analyzed to detect specification-independent errors such as deadlock. Feasibility constraints for P can be used to improve the accuracy of existing methods for deriving approximations of the set of feasible SYN-sequences of P.>

A language-based approach to deterministic execution debugging of concurrent Ada programs is presented. The approach is to define synchronization (SYN)-sequences of a concurrent Ada program in terms of Ada language constructs and to replay such SYN-sequences without the need for system-dependent debugging tools. It is shown how to define a SYN-sequence of a concurrent Ada program in order to provide sufficient information for deterministic execution. It is also shown how to transform a concurrent Ada program P so that the SYN-sequences of previous executions of P can be replayed. This transformation adds an Ada task to P that controls program execution by synchronizing with the original tasks in P. A brief description is given of the implementation of tools supporting deterministic execution debugging of concurrent Ada programs.>

The authors show how to accomplish deterministic execution debugging of a concurrent Ada program according to a given synchronization (SYN) sequence. They first define the format of a SYN sequence of a concurrent Ada program in order to provide sufficient information for deterministic execution. They show how to transform a concurrent Ada program P into a slightly different Ada program P' so that any execution of P' with (X,S) as input, where S is the SYN sequence of a previous execution of P with input X, definitely repeats S. Tools for transforming concurrent Ada programs for deterministic execution debugging are described.>