Concutest
From Wikipedia, the free encyclopedia
Concutest is a specialized unit testing framework for the Java programming language. Created by Mathias Ricken while at the JavaPLT (Java Programming Languages Team) at Rice University, Concutest provides a set of unit testing-like features for the analysis of multithreaded programs.
Contents |
[edit] Unit Testing
Traditional unit testing is covered in greater detail by the article on unit testing; however the basic premise is to verify the goodness of a program by analyzing specific attributes of an execution of a program. Specifically, the unit tests of some program will execute a function then verify that its result is correct. For example, one might unit test the mathematical function "f(x,y) = 3x+2y" by verifying that "f(0,0) == 0", "f(1,1) == 5", and others.
[edit] Difficulty of Thread Scheduling
One of the aspects that makes modern multithreaded programming so difficult is the fact that thread schedules are nondeterministic. Specifically, there are many possible schedules of execution, and modern operating systems do not selectively pick between them except according to very vague heuristics (such as thread priority). For example, consider a multithreaded processes:
Initial conditions: I = 1 J = 2
Thread A: 1 - Increment I 2 - Increment J
Thread B: 1 - Multiply J by 2 2 - Multiply I by 0
The results of this system depend upon the order in which the threads' steps are scheduled. One example schedule is this (which corresponds to Thread A running to completion followed by Thread B):
Increment I Increment J Multiply J by 2 Multiply I by 0
Final conditions: I = 0 J = 6
However, this is another legitimate schedule:
Multiply J by 2 Multiply I by 0 Increment I Increment J
Final conditions: I = 1 J = 5
There is a problem with our program, because various scheduling of its threads produce different results (we want the program to produce the same results no matter what). It is often difficult to determine that a program has such a problem (known as a race condition) because many schedules, although valid, would not occur during most normal conditions. Certain thread schedules only occur during exceptional conditions, including conditions not specifically known to the software developer (due to the immense complexity of software), and thus cannot be tested or accounted for directly.
[edit] Concurrent Unit Testing
Concutest provides a solution to this difficulty through concurrent unit testing. Concutest analyzes a candidate program to determine its sequence points; effectively, it divides a program up into a series of discrete steps, such as those provided for illustration above, and then analyzes all possible control flows.
Concutest, after determining a correct division of a program's steps, analyzes the control flow to determine if the results of the program are the same no matter which schedule is selected. Since in production code, any valid schedule may be executed by the operating system, a valid program must achieve the same result regardless of schedule. Therefore, if multiple runs of a program under different Concutest schedules produce different results, the program has flawed concurrent behavior.
Effectively, this analysis of control flow is a type of unit test; before a program is considered valid and ready for release, software developers run their software through a series of unit tests to ensure its correctness. With Concutest, one of the test steps against which a program is validated is that multiple, various possible thread executions achieve the same result. As part of a comprehensive testing package, Concutest helps to ensure that programs are valid.
Concutest cannot detect all problems that arise from the nondeterminism of concurrency; only those that arise from disparate scheduling can be detected by Concutest. Furthermore, the division of the program into blocks separated by sequence points assumes that the program is free of race conditions. Therefore, it is necessary that race condition detection, e.g. using a lockset algorithm, is used along with Concutest. Concutest is not a replacement for traditional unit testing, and it is advised that other testing be used in the context of Concutest to ensure that the unit tests themselves pass even under disparate thread schedules.
[edit] Mechanism
Concutest divides programs according to their sequence points. In the Java platform, sequence points are defined as any point at which a thread interacts with a synchronization object. For example, acquiring a mutex or releasing it would each be sequence point operations. Incrementing an integer would not be a sequence point because it is not involved in defined, protected operations.
Concutest requires that all modifiable resources in the program are protected by synchronization primitives. Concutest cannot determine certain kinds of race conditions: it can only determine whether multiple various schedules of the program result in different behaviors; it cannot determine whether multiple threads have a race condition in their accessing of a single object unless those differences show up due to the schedulings that Concutest checks.
[edit] Funding
It is partially funded by the National Science Foundation and the Texas Advanced Technology Program.
