This paper presents Basset, a tool for systematic testing of JVM-based actor programs. The actor programming model offers a promising approach for developing reliable concurrent and distributed systems. Since the actor model is based on message passing and disallows shared state, it avoids some of the problems inherent in shared-memory programming, e.g., low-level dataraces involving access to shared data. However, actor programs can still have bugs that result from incorrect orders of messages among actors or processing of messages by individual actors. To systematically test an actor program, it is necessary to explore different message delivery schedules that might occur during execution. Basset facilitates such exploration and provides a generic platform that can support actor systems that compile to Java bytecode. Our current implementation of Basset supports testing of programs developed using the ActorFoundry library and the Scala programming language.

Java PathFinder (JPF) is a popular model checker for Java programs. JPF was used to generate object graphs as test inputs for object-oriented programs. Specifically, JPF was used as an implementation engine for the Korat algorithm. Korat takes two inputs---a Java predicate that encodes properties of desired object graphs and a bound on the size of the graph---and generates all graphs (within the given bound) that satisfy the encoded properties. Korat uses a systematic search to explore the bounded state space of object graphs. Korat search was originally implemented in JPF using a simple instrumentation of the Java predicate. However, JPF is a general-purpose model checker and such direct implementation results in an unnecessarily slow search. We present our results on speeding up Korat search in JPF. The experiments on ten data structure subjects show that our modifications of JPF reduce the search time by over an order of magnitude.

The actor programming model offers a promising model for developing reliable parallel and distributed code. Actors provide flexibility and scalability: local execution may be interleaved, and distributed nodes may operate asynchronously. The resulting nondeterminism is captured by nondeterministic processing of messages. To automate testing, researchers have developed several tools tailored to specific actor systems. As actor languages and libraries continue to evolve, such tools have to be reimplemented. Because many actor systems are compiled to Java bytecode, we have developed Basset, a general framework for testing actor systems compiled to Java bytecode. We illustrate Basset by instantiating it for the Scala programming language and for the ActorFoundry library for Java. Our implementation builds on Java PathFinder, a widely used model checker for Java. Experiments show that Basset can effectively explore executions of actor programs; e.g., it discovered a previously unknown bug in a Scala application.

Java PathFinder (JPF) is an explicit-state model checker for Java programs. JPF implements a backtrackable Java Virtual Machine (JVM) that provides non-deterministic choices and control over thread scheduling. JPF is itself implemented in Java and runs on top of a host JVM. JPF represents the JVM state of the program being checked and performs three main operations on this state representation: bytecode execution, state backtracking, and state comparison. This paper summarizes four extensions that we have developed to the JPF state representation and operations. One extension provides a new functionality to JPF, and three extensions improve performance of JPF in various scenarios. Some of our code has already been included in publicly available JPF.

We present a novel technique that speeds up state-space exploration (SSE) for evolving programs with dynamically allocated data. SSE is the essence of explicit-state model checking and an increasingly popular method for automating test generation. Traditional, non-incremental SSE takes one version of a program and systematically explores the states reachable during the program's executions to find property violations. Incremental SSE considers several versions that arise during program evolution: reusing the results of SSE for one version can speed up SSE for the next version, since state spaces of consecutive program versions can have significant similarities. We have implemented our technique in two model checkers: Java PathFinder and the J-Sim state-space explorer. The experimental results on 24 program evolutions and exploration changes show that for non-initial runs our technique speeds up SSE in 22 cases from 6.43% to 68.62% (with median of 42.29%) and slows down SSE in only two cases for -4.71% and -4.81%.

We present Delta execution, a technique that speeds up state-space exploration of object-oriented programs. State-space exploration is the essence of model checking and an increasingly popular approach for automating test generation. A key issue in exploration of object-oriented programs is handling the program state, in particular the heap. We exploit the fact that many execution paths in state-space exploration partially overlap. Delta execution simultaneously operates on several states/heaps and shares the common parts across the executions, separately executing only the "deltas" where the executions differ. We implemented Delta execution in two model checkers: JPF, a popular general-purpose model checker for Java programs, and BOX, a specialized model checker that we developed for efficient exploration of sequential Java programs. The results for bounded-exhaustive exploration of ten basic subject programs and one larger case study show that Delta execution reduces exploration time from 1.06x to 126.80x (with median 5.60x) in JPF and from 0.58x to 4.16x (with median 2.23x) in BOX. The results for a non-exhaustive exploration in JPF show that Delta execution reduces exploration time from 0.92x to 6.28x (with median 4.52x).

State-space exploration is the essence of model checking and an increasingly popular approach for automating test generation. A key issue in exploration of object-oriented programs is handling the program state, in particular the heap. Previous research has focused on standard program execution that operates on one state/heap. We present Delta Execution, a technique that simultaneously operates on several states/heaps. It exploits the fact that many execution paths in state-space exploration partially overlap and speeds up the exploration by sharing the common parts across the executions and separately executing only the "deltas" where the executions differ.