In our days, it is hard to imagine big software products written without the use of multithreading. However, they not only use multithreading, but are also complicated by being distributed. On one hand, it gives performance advantages, but on the other hand, it becomes much more di cult to nd bugs and test such applications. When developing programs that use multithreading, we can nd the following types of errors: priority inversions, deadlock, livelock, ABA problem, and others. Such errors can lead to large nancial losses, for example, in the banking infrastructure, or losses of human lives in aircraft engineering, civil engineering, medical devices and other areas. Special tools such as Valgrind, Google TSAN and others are used to nd such bugs. Until recently, such tools were not able to fuzzing testing multithreaded applications, but now Google TSAN has a special module. The main limitation of the testing fuzzing module is that it is not able to handle waiting on nonatomic variables. The results presented in this paper allow us to carry fuzzing testing of threads and at the same time correctly handle the situation with waiting on variables that are not atomic, as well as examples on which the improved algorithm successfully copes with handling such waiting.
Fuzz testing or Fuzzing [
As for the fuzz testing of multithreaded applications, instead of trying out variants of the input arguments, the search goes through the combinations of thread execution sequences. And in this case there are di erent strategies for performing the search of execution sequences.
At the moment, fuzz testing is being implemented into the main
development branch of the ThreadSanitizer (TSAN) [
1. Comparison of existing solutions
RRD Lfouczkz-ifnrgee FuzzLinogckwith
uDsoeerscno'tderequire changes in - + +
sSyunpcphorrotnsiztahteiobnloaclkgionrgithms +/- -
+/tShurpepaodrtloscwalorsktoinraggwe ith - + +
Snounp-paotrotmsiwcovrakriinagblwesith - -
iImtdpoleems ennottatrieoqnuiorfe etahcehinbdloivckidinugalalgorithm - X
Here's a comparison of the various solutions that exist at the moment. The
comparison is made on 5 criteria:
1. Doesn't require changes in user code - this means that the user can
use the tool to phase out thread testing for the source code in the c++
language without making any changes to it. For example, Relacy Race
Detector (RRD) [
This work improves the fuzz testing module described in [
Let's start by describing the fuzz testing algorithm for threads based on waiting, with an example that causes previous approaches to fuzz testing to hang:
Example barrier 1 volatile std::byte barrier = 0; 2 void thread1() { 3 while (!barrier); 4 } 5
7 barrier = true; 8 //... 9 }
This example uses a simple barrier that suspends thread 1.
The code is fully valid up to the CPU memory model, as the minimum addressed memory unit is a byte.
The main assumption on which we base the developed algorithm is that errors in multithreaded applications appear only at synchronization points. Therefore, thread switching points are selected among operations: reading/writing into an atomic variable, capturing/releasing a mutex, waiting/noti cation on a conditional variable, and others.
Based on the above, we design the interface for thread scheduling fuzzing in the simplest form of a single SynchronizationPoint method.
To improve the thread scheduler fuzzing module, we now need to solve two problems: 1. Implement planning algorithms for the presented interface 2. Introduce the developed interface into the TSAN architecture Let's start with the second problem and describe how TSAN works:
The image above shows a simpli ed layout of the program's compilation in the C language. It embeds TSAN in the source code during the compilation phase. As a result, we get the source code with replaced functions to work with mutexes, conditional variables, instrumented reading and writing operations into variables, and other intercepted functions.
This approach allows to replace certain functionality transparently and to create algorithms based on it to nd errors in the code. From the user's point of view, it su ces to compile the source code with special compiler options, and algorithms for nding errors will work. A downside of this approach is that additional compilation time is required, and even with separate compilation the linking stage can take considerable amount of time. However, for well-structured programs this shortcoming is negligible.
Let's look at what the described architecture looks like from a code perspective. Suppose the user code gains ownership of the mutex:
2 //...
4 // application logic
In fact, this code is converted to the following:
2 // ...
4 // ...
The implementation of tsan mutex lock/unlock is taken care of by the developers of algorithms for nding errors. For SynchronizationPoint, for example, the use of tsan mutex lock will look like this:
Converted code 1 int tsan_mutex_lock(void* mutex) {
3 //...
5 //...
7 }
In example above we made two points of synchronisation: before taking the mutex and after it. This is how IScheduler is embedded into TSAN. We now progress to description of our algorithm for fuzz testing of multithreaded applications. This algorithm should allow to deal with cases of thread hangs such as described above. The states each thread in IScheduler can be in are: 1. UNKNOWN - the thread is in this state until it reaches the rst synchronization point. 2. RUNNING - marks the main execution thread. Only one thread in the program can have such this state at every moment in time. 3. WAIT - a thread in this state is waiting for its turn for execution. 4. OUT TIME - this state happens if a thread has exhausted its execution quant but has not reached the next SynchronizationPoint. One reason for this state can be the hanging of the thread on the waiting event, just as described in the example with the barrier. Here, the thread remains on execution, and there may be several threads in OUT TIME state. When these threads reach SynchronizationPoint, they go into WAIT.
Figure 2 shows the graph [
The example above describes a typical example of a thread wandering through such a graph. It is worth noting that WatchDog constantly monitors all the threads running in the system at some interval and can change these states for arbitrary threads.
The problem of thread hang-ups on a normal variable is solved by a state of OUT TIME, when physically several threads can be executed. This algorithm imposes restrictions on the data structures used in IScheduler: they must be thread-safe. But what we get is the bene ts of no hang-ups in these algorithms for di erent thread planning strategies; it works for any production-ready applications.
Let's look now at how to manage thread states. WatchDog is used to manage the OUT TIME states. The schema shows the application architecture:
The system has N threads, where N can increase or decrease. WatchDog selects execution threads through SynchronizationPoint, except for the OUT TIME state processing. A special WatchDog thread monitors all states and durations of threads' work. It sets OUT TIME state if the thread has been running longer than a de ned period of time. Depending on the choice of the length of this time period, we can balance the quality and time of work.
The pseudo-code for the SynchronizationPoint method implementation is: tsan mutex lock 1 int tsan_mutex_lock(void* mutex) {
3 //...
5 //...
7 }
In the example above, we do two synchronization points: before the mutex capture and after the capture. This is how IScheduler is introduced into TSAN.
Now let's go to the description of how to build a fuzzing algorithm for testing multithreaded applications, which would bypass the thread sagging cases described above.
Let's start by describing the states in which each thread can be inside IScheduler:
SynchronizationPoint pseudo-code
2 tid = GetTid(); 3 oldState = state[tid]; 4 state[tid] = WAIT; 5 if (oldState = RUNNING) { 6 7 8 9 nextTid = GetNextTid(); state[nextTid] = nextTid; } While (state[tid] == Wait) Yield();
The pseudo-code above sets the (initial) state for each thread to WAIT unless it was in OUT TIME state; and then the next thread is selected for execution, so there can only be one RUNNING thread on the execution. The rest of the work for OUT TIME state processing and preserving the invariant of just one RUNNING thread takes place in the WatchDog thread. 3
This work improved the module for fuzz testing of multithreaded applications in
Google TSAN. We added support for the correct processing of application
hangup on non-atomic variables. This result allows TSAN to test any multithreaded
algorithms. For example, if we want to improve the quality of lock-free algorithm
testing, such as the libcds [