Heisenbugs

Concurrent applications should execute correctly on every possible thread schedule in the underlying operating system. However, traditional testing methods detect few bugs, chiefly because of the Heisenbugs^[1] problem. A Heisenbug is an error that changes or disappears when an attempt is made to isolate and probe them via debugger, by adding some constructs such as synchronization requests or delay statements.

Non-repeatability

Another issue is caused due to the unpredictable behavior of the scheduler. Differences in system load influence scheduler behavior. This behavior cannot be changed manually. To counter this indeterminism, the program must be executed many times under various execution environments. Still, it is not guaranteed that a bug can be reproduced. Most of the time, the program runs correctly, and the bug is visible only when specific conditions are matched. As a result, non-repeatability of the concurrent programs is a major source of roadblock for detecting error. As an example, consider the following.

void thread1(void *t)
{
   mutex_lock(a);
   mutex_lock(b);
   // do some work
   .
   .
   .
   mutex_unlock(b);
   mutex_unlock(a);
}

void thread2(void *t)
{
   mutex_lock(b);
   mutex_lock(a);
   // do some work
   .
   .
   .
   mutex_unlock(a);
   mutex_unlock(b);
}

Clearly, this has a problem of causing deadlocks. Yet, it may cause deadlock in some runs of the program while in others, it may run successfully.

Probe effect

Probe effect is seen in parallel programs when delay-statements are inserted in parallel programs facing synchronization problems. This effect, like Heisenbugs, alters behavior changes that may obscure problems. Detecting the source of a probe effect is a great challenge in testing parallel applications.
The main difference between Probe effect and Heisenbugs is that Heisenbugs are seen when additional delay statements and/or synchronization requests are added to the concurrent application during testing, while probe effect is seen when the developer adds delay statements to concurrent applications with poor synchronization.

Deterministic scheduling / reproducible testing

The indeterminacy of scheduling has two sources.^[1]

1. Time slicing

Scheduler switches contexts at equal intervals of time. This interval depends on the speed of individual processors, memory-cache hierarchy state and system load. Even on the same processor, under the same load, the interval varies slightly due to minor variations in frequency of the system clock.

2. Page Faults

Scheduler suspends a program if a page fault occurs, letting other threads proceed while the system fetches the page. As the occurrence of page faults depends upon what other processes are running, the timing of a context switch becomes indeterminate.

To make concurrent programs repeatable, an external scheduler is used. The program under test is instrumented to add calls to this scheduler. Such calls are made at the beginning and end of each thread as well as before every synchronization request. This scheduler selectively blocks threads of execution by maintaining a semaphore associated with each thread, such that only one thread is ready for execution at any given time. Thus, it converts parallel non-deterministic application into a serial execution sequence in order to achieve repeatability. The number of scheduling decisions made by the serializing scheduler is given by –

(N * K / P)*{(N + P)!}

Where 

N = number of threads

K = potential context switch points

P = budget of pre-emptive context switches

Feedback-directed testing

To obtain more accurate results using deterministic scheduling, an alternate approach can be chosen. A few properly-placed pre-emptions in the concurrent program can detect bugs related to data-races.^[1] Bugs are found in clusters. The existence of one bug establishes a high probability of more bugs in the same region of code. Thus each pass of the testing process identifies sections of code with bugs. The next pass more thoroughly scrutinizes those sections by adding scheduler calls around them. Allowing the problematic locations to execute in a different order can reveal unexpected behavior.

Timing-related testing

This strategy ensures that the application is not prone to the Probe Effect. Sources of errors that cause the Probe Effect can range from task creation issues to synchronization and communication problems. Requirements of timing related tests:^[3]

• Delay duration must vary
• Delay points must cover appropriate program locations
• Delay statements must be inserted, removed or relocated to induce Probe Effect

The number of test cases per input data set is:

nC1 + nC1 + … + nC1 = 2n -1

Where n = total number of synchronization, process creation and communication calls.

This equation has exponential order. In order to reduce the number of test cases, either Deterministic Execution Method (DET) or Multiple Execution Technique (MET) is used. Various issues must be handled:

• Delayed execution

Addition of delays is a straightforward task. A typical sleep() statement can be used to insert delays.

• Deciding where to insert delays

Insertion locations are known as delay-points. As the objective of timing related test cases is to detect synchronization, communication and thread creation errors, delay statements are added just in front of these statements.

All Du-Path testing

This method applies the concept of define-use pair, in order to determine the paths to be tested.

Test calculations

Input is given to the system to generate a known result. This input-result pair can be obtained from previous empirical results and/or manual calculations.^[4] This is a system-level test that can be performed only when all relevant modules are integrated. Moreover, it only shows that bugs exist. It offers no detailed information regarding the number of bugs, their location or nature.

Symmetry tests

These tests are primarily used for scientific simulations. The output of the simulation often cannot be predicted. Since these simulations attempt to describe scientific laws, any symmetries in the theory must be honored by the simulation. Thus, by varying input conditions along the lines of symmetry and then comparing the obtained results with externally derived results, the existence of bugs can be detected.^[4]

Figure 1 : Data Distribution

In scientific computing most data lies in the central region of the simulation conditions. As a result, it is difficult to perform Boundary-value testing ^[2] with real time experimental data. Thus, center of simulation (for example, for data value of 10 in Figure 1) is shifted to one of the boundaries so as to test the boundary condition effectively.

Parallel implementation tests

Parallel implementation tests are usually used for applications that use distributed memory programming models such as message passing. These tests are often applied to programs that use regular grids of processors.^[4]

Microsoft CHESS

This tool eliminates non-determinacy using deterministic scheduling. It tracks schedule paths executed previously and guarantees that each time a new schedule path is executed.^[1]