Overall Workflow

Static Instrumentation

The static analysis is based on LLVM. This can be divided into two phrases: the analysis part and the instrumentation part.

Static Analysis

This part reconstructs thread-aware ICFG and suspicious-interleaving-scope.

It firstly wraps the regular compilation procedure with gllvm to get the LLVM bitcode format of the binaries. The purpose is to feed the whole module of the target binaries in LLVM bitcode format to our static analyzer. Specially, both the bitcode of executable and the shared libraries are analyzed. These bitcode files are then analyzed by the static analyzer which is based on SVF project. Notably, SVF includes all the multithreading analyses we need such as may happen-in-parallel and lockset analysis. With these analyses, we generated two file: mtiscope.txt and forked_funcs.txt. "mtiscope.txt" includes the source code lines in the target program that is considered in "suspicious interleaving scope" (with the help of the debugging information): each of its lines is of the format "filename:lineno". "forked_funcs.txt" includes the functions that are called by the thread-forking APIs such as "pthread_create".

Instrumentation

This part does the actual instrumentation. Similar to AFL, we wrap the CC/CXX/CFLAGS/CXXFLAGS to build the instrumentation version. Here, both CFLAGS and CXXFLAGS accept another option "-muzz-conf llvm.toml" where llvm.toml contains content such as:

[ins]

proj_name = "mt-motivation"

[mt]

dir = "out"

Ps0 = 0.5

Pm0 = 0.33

llvm.toml is supposed to be the same directory as mtiscope.txt and forked_funcs.txt . And the CC/CXX wrapper handles this option with the help of -mllvm. dir specifies the output statistics directory and Ps0/Pm0 specify the upper bound probability of the instrumentation ratio for these lines outside or inside the suspicious interleaving scope. The instrumentation follows the following procedures:

• Coverage-oriented instrumentation is done based on mtiscope.txt; the selection of these deputy instructions follows "Coverage-instrumentation Algorithm" in Algorithm 2.
• Schedule-intervention instrumentation is done based on forked_funcs.txt. This is done by calling function rt_schedule_intervene which does the actual scheduling intervention by change the policy and the priority.
• Threading-context instrumentation is done on the call to the threading APIs. For pthread, this includes pthread_mutex_lock, pthread_mutex_unlock, pthread_join, pthread_cancel, etc. For OpenMP, this includes the function stubs matching the pattern such as omp_outlined*.

Dynamic Fuzzing

This is almost the same as AFL. The only difference is that we also need to manually set time slice (echo 10 > /proc/sys/kernel/sched_rr_timeslice_ms) as mentioned in this Q&A.

Before fuzzing, we export AFL_NO_AFFINITY=0 to disable the CPU affinity option and executes the fuzzers with -d option to force figdgety mode.

Concurrency-bug Revealing

We export CFLAGS="-fsanitize=thread -g", CXXFLAGS="-fsanitize=thread -g" and LDFLAGS="-fsanitize=thread -g" to rebuild the programs and replay with the generated seeds in the folder queue/.stat/var_behavior of the fuzzers' generated non-deterministic behavior seed directory.

Instrumentation Rationales

Low-level Instruction Representations

MUZZ works on the target program's binary level and its instrumentation is applied on LLVM intermediate representation (IR), which resembles the binary level assembly. On statement in the source code can be compiled into multiple LLVM IR instructions. For example, the two statements g_var += 1 and g_v ar ∗= 2 may be divided into 6 instructions:

// g_var += 1

a: v = load g_var

b: w = v + 1

c: store w, g_var

// g_var *= 2

d: x = load g_var

e: y = x * 2

f: store y, g_var

In the cases of two threads T1 and T2, there are actually many more interleavings than the three interleavings shown in the main paper.

T1:a→T1:b→T2:a→T2:b→T1:c→T2:c→T1:d→T2:d→T1:e→T2:e→T1:f→T2:f

T1:a→T2:a→T1:b→T2:b→T1:c→T2:c→T1:d→T2:d→T1:e→T2:e→T1:f→T2:f

T1:a→T2:a→T2:b→T1:b→T1:c→T2:c→T1:d→T2:d→T2:e→T1:e→T1:f→T2:f

T1:a→T2:a→T2:b→T1:b→T2:c→T1:c→T1:d→T2:d→T1:e→T2:e→T2:f→T1:f

...

This means that more different output results can be emitted after the executions of these instructions (corresponding to the two statements). In addition, due to the caching mechanism in modern CPUs, more results may occur which will affect the final value of g_var .

Memory Operation Instructions

In coverage-oriented instrumentation, M UZZ relies on the percentage of memory operation instructions in the residing basicblocks to determine the probability for assigning deputy instructions in suspicious-interleaving scope (Lm). We determine these instructions at the LLVM IR level. These operation instructions either read or write the memory.

1. load/store instructions: e.g., load (LoadInst), store (StoreInst), cmpxchg (AtomicCmpXchgInst), atomicrmw (AtomicRMWInst);
2. Intrinsic memory function calls: e.g., calls to llvm.memcpy.*, llvm.memmove.*, llvm.memset.*;
3. Standard C memory function calls: e.g., calls to strncpy, malloc, free.

Note that we deliberately ignore some memory-relevant instructions. For example, gep (GetElementPtr) is excluded since it basically calculates the offset while does not involves any memory read/write; alloc (AllocInst) in LLVM IR is excluded since it is a common allocation for stack variables; fence (FenceInst) is excluded since it is used to introduce happens-before edges between operations.

We plan to provide more systematic approach to distinguish these memory operation instructions; in particular, we would like to summarize more memory functions in addition to those in the standard C library.