key: cord-0047687-1m682dze
authors: Schemmel, Daniel; Büning, Julian; Rodríguez, César; Laprell, David; Wehrle, Klaus
title: Symbolic Partial-Order Execution for Testing Multi-Threaded Programs
date: 2020-06-13
journal: Computer Aided Verification
DOI: 10.1007/978-3-030-53288-8_18
sha: ae6ae0c44bb88c938f5b0f19a49996e5ac4ea6e4
doc_id: 47687
cord_uid: 1m682dze

We describe a technique for systematic testing of multi-threaded programs. We combine Quasi-Optimal Partial-Order Reduction, a state-of-the-art technique that tackles path explosion due to interleaving non-determinism, with symbolic execution to handle data non-determinism. Our technique iteratively and exhaustively finds all executions of the program. It represents program executions using partial orders and finds the next execution using an underlying unfolding semantics. We avoid the exploration of redundant program traces using cutoff events. We implemented our technique as an extension of KLEE and evaluated it on a set of large multi-threaded C programs. Our experiments found several previously undiscovered bugs and undefined behaviors in memcached and GNU sort, showing that the new method is capable of finding bugs in industrial-size benchmarks.

Advances in formal testing and the increased availability of affordable concurrency have spawned two opposing trends: While it has become possible to analyze increasingly complex sequential programs in new and powerful ways, many projects are now embracing parallel processing to fully exploit modern hardware, thus raising the bar for practically useful formal testing. In order to make formal testing accessible to software developers working on parallel programs, two main problems need to be solved. Firstly, a significant portion of the API in concurrency libraries such as libpthread must be supported. Secondly, the analysis must be accessible to non-experts in formal verification. Currently, this niche is mostly occupied by manual and fuzz testing, oftentimes combined with dynamic concurrency checkers such as ThreadSanitizer [45] or Helgrind [2] .

Data non-determinism in sequential and concurrent programs, and scheduling non-determinism are two major sources of path explosion in program analysis. Symbolic execution [10, 11, 22, 29, 38] is a technique to reason about input data in sequential programs. It is capable of dealing with real-world programs. Partial-Order Reductions (PORs) [5, 19, 20, 41] are a large family of techniques to explore a reduced number of thread interleavings without missing any relevant behavior.

In this paper we propose a technique that combines symbolic execution and a Quasi-Optimal POR [35] . In essence, our approach (1) runs the program using a symbolic executor, (2) builds a partial order representing the occurrence of POSIX threading synchronization primitives (library functions pthread *) seen during that execution, (3) adds the partial order to an underlying tree-like, unfolding [32, 41] data structure, (4) computes the first events of the next partial orders to explore, and (5) selects a new partial order to explore and starts again. We use cutoff events [32] to prune the exploration of different traces that reach the same state, thus natively dealing with non-terminating executions.

We implemented our technique as an extension of KLEE. During the evaluation of this prototype we found nine bugs (that we attribute to four root causes) in the production version of memcached. All of these bugs have since been confirmed by the memcached maintainers and are fixed as of version 1.5.21. Our tool handles a significant portion of the POSIX threading API [4] , including barriers, mutexes and condition variables without being significantly harder to use than common fuzz testing tools.

The main challenge that our approach needs to address is that of scalability in the face of an enormous state space. We tackle this challenge by detecting whenever any two Mazurkiewicz traces reach the same program state to only further explore one of them. Additionally, we exploit the fact that data races on non-atomic variables cause undefined behavior in C [25, § 5.1.2.4 /35] , which means that any unsynchronized memory access is, strictly speaking, a bug. By adding a data race detection algorithm, we can thereby restrict thread scheduling decisions to synchronization primitives, such as operations on mutexes and condition variables, which significantly reduces the state space.

This work has three core contributions, the combination of which enables the analysis of real-world multi-threaded programs (see also Sect. 6 for related work):

1. A partial-order reduction algorithm capable of handling real-world POSIX programs that use an arbitrary amount of threads, mutexes and condition variables. Our algorithm continues analysis in the face of deadlocks. 2. A cutoff algorithm that recognizes whenever two Mazurkiewicz traces reach the same program state, as identified by its actual memory contents. This significantly prunes the search space and even enables the partial-order reduction to deal with non-terminating executions. 3 . An implementation that finds real-world bugs.

We also present an extended, more in-depth version of this paper [42] .

The technique proposed in this paper can be described as a process of 5 conceptual steps, each of which we describe in a section below: A program (a) with its 5 partial-order runs (b-f), its unfolding (g) and the 5 steps used by our algorithm to visit the unfolding (h-l).

Consider the program shown in Fig. 1a . Assume that all variables are initially set to zero. The statement a = in() initializes variable a non-deterministically. A run of the program is a sequence of actions, i.e., pairs i, s where i ∈ N identifies a thread that executes a statement s. For instance, the sequence σ 1 := 1, a=in() , 1, c=3 , 2, b=c , 2, a<0 , 2, puts("n")

is a run of Fig. 1a . This run represents all program paths where both statements of thread 1 run before the statements of thread 2, and where the statement a = in() initializes variable a to a negative number. In our notion of run, concurrency is represented explicitly (via thread identifiers) and data non-determinism is represented symbolically (via constraints on program variables). To keep things simple the example only has atomic integers (implicitly guarded by locks) instead of POSIX synchronization primitives.

Many POR techniques use a notion called independence [20] to avoid exploring concurrent interleavings that lead to the same state. An independence relation associates pairs of actions that commute (running them in either order results in the same state). For illustration purposes, in Fig. 1 let us consider two actions as dependent iff either both of them belong to the same thread or one of them writes into a variable which is read/written by the other. Furthermore, two actions will be independent iff they are not dependent. A sequential run of the program can be viewed as a partial order when we take into account the independence of actions. These partial orders are known as dependency graphs in Mazurkiewicz trace theory [31] and as partial-order runs in this paper. Figures 1b to 1f show all the partial-order runs of Fig. 1a . The partial-order run associated to the run σ 1 above is Fig. 1c . For σ 2 := 2, b=c , 2, a>=0 , 1, a=in() , 2, puts("y") , 1, c=3 , we get the partial order shown in Fig. 1f. 

An unfolding [16, 32, 37] is a tree-like structure that uses partial orders to represent concurrent executions and conflict relations to represent thread interference and data non-determinism. We can define unfolding semantics for programs in two conceptual steps: (1) identify isomorphic events that occur in different partial-order runs; (2) bind the partial orders together using a conflict relation.

Two events are isomorphic when they are structurally equivalent, i.e., they have the same label (run the same action) and their causal (i.e., happens-before) predecessors are (transitively) isomorphic. The number within every event in Figs. 1b to 1f identifies isomorphic events.

Isomorphic events from different partial orders can be merged together using a conflict relation for the un-merged parts of those partial orders. To understand why conflict is necessary, consider the set of events C := {1, 2}. It obviously represents part of a partial-order run (Fig. 1c , for instance). Similarly, events C := {1, 8, 9} represent (part of) a run. However, their union C ∪ C does not represent any run, because (1) it does not describe what happens-before relation exists between the dependent actions of events 2 and 8, and (2) it executes the statement c=3 twice. Unfoldings fix this problem by introducing a conflict relation between events. Conflicts are to unfoldings what branches are to trees. If we declare that events 2 and 8 are in conflict, then any conflict-free (and causally-closed) subset of C ∪ C is exactly one of the original partial orders. This lets us merge the common parts of multiple partial orders without losing track of the original partial orders. Figure 1g represents the unfolding of the program (after merging all 5 partialorder runs). Conflicts between events are represented by dashed red lines. Each original partial order can be retrieved by taking a (⊆-maximal) set of events which is conflict-free (no two events in conflict are in the set) and causally closed (if you take some event, then also take all its causal predecessors).

For instance, the partial order in Fig. 1d can be retrieved by resolving the conflicts between events 1 vs. 14, 2 vs. 8, 10 vs. 12 in favor of, resp., 1, 8, 10. Resolving in favor of 1 means that events 14 to 17 cannot be selected, because they causally succeed 14. Similarly, resolving in favor of 8 and 10 means that only events 9 and 11 remain eligible, which hold no conflicts among them-all other events are causal successors of either 2 or 12.

Since the unfolding represents all runs of the program via a set of compactlymerged, prefix-sharing partial orders, enumerating all the behaviors of the program reduces to exploring all partial-order runs represented in its unfolding. Our algorithm iteratively enumerates all ⊆-maximal partial-order runs.

In simplified terms, it proceeds as follows. Initially we explore the black events shown in Fig. 1h , therefore exploring the run shown in Fig. 1b . We discover the next partial order by computing the so-called conflicting extensions of the current partial order. These are, intuitively, events in conflict with some event in our current partial order but such that all its causal predecessors are in our current partial order. In Fig. 1h these are shown in circles, events 8 and 6.

We now find the next partial order by (1) selecting a conflicting extension, say event 6, (2) removing all events in conflict with the selected extension and their causal successors, in this case events 4 and 5, and (3) expanding the partial order until it becomes maximal, thus exploring the partial order Fig. 1c , shown as the black events of Fig. 1i . Next we select event 8 (removing 2 and its causal successors) and explore the partial order Fig. 1d , shown as the black events of Fig. 1j . Note that this reveals two new conflicting extensions that were hidden until now, events 12 and 14 (hidden because 8 is a causal predecessor of them, but was not in our partial order). Selecting either of the two extensions makes the algorithm explore the last two partial orders.

When the program has non-terminating runs, its unfolding will contain infinite partial orders and the algorithm above will not finish. To analyze nonterminating programs we use cutoff events [32] . In short, certain events do not need to be explored because they reach the same state as another event that has been already explored using a shorter (partial-order) run. Our algorithm prunes the unfolding at these cutoff events, thus handling terminating and nonterminating programs that repeatedly reach the same state.

This section formally describes the approach presented in this paper.

Let P := T, L, C represent a (possibly non-terminating) multi-threaded POSIX C program, where T is the set of statements, L is the set of POSIX mutexes used in the program, and C is the set of condition variables. This is a deliberately simplified presentation of our program syntax, see [42] for full details. We represent the behavior of each statement in P by an action, i.e., a pair i, b in A ⊆ N × B, where i ≥ 1 identifies the thread executing the statement and b is the effect of the statement. We consider the following effects:

Below we informally explain the intent of an effect and how actions of different effects interleave with each other. In [42] we use actions and effects to define labeled transition system semantics to P . Below we also (informally) define an independence relation (see Sect. 2.2) between actions.

Actions. An action i, loc, t represents the execution of a local statement t from thread i, i.e., a statement which manipulates local variables. For instance, the actions labeling events 1 and 3 in Fig. 2b are local actions. Note that local actions do not interfere with actions of other threads. Consequently, they are only dependent on actions of the same thread.

Mutex Lock/Unlock. Actions i, acq, l and i, rel, l respectively represent that thread i locks or unlocks mutex l ∈ L. The semantics of these actions correspond to the so-called NORMAL mutexes in the POSIX standard [4] . Actions of acq, l or rel, l effect are only dependent on actions whose effect is an operation on the same mutex l (acq, rel, w 1 or w 2 , see below). For instance the action of event 4 (rel) in Fig. 2b depends on the action of event 6 (acq).

Wait on Condition Variables. The occurrence of a pthread cond wait(c, l) statement is represented by two separate actions of effect w 1 , c, l and w 2 , c, l . An action i, w 1 , c, l represents that thread i has atomically released the lock l and started waiting on condition variable c. An action i, w 2 , c, l indicates that thread i has been woken up by a signal or broadcast operation on c and that it successfully re-acquired mutex l. For instance the action 1, w 1 , c, m of event 10 in Fig. 2c represents that thread 1 has released mutex m and is waiting for c to be signaled. After the signal happens (event 12) the action 1, w 2 , c, m of event 14 represents that thread 1 wakes up and re-acquires mutex m. An action i, w 1 , c, l is dependent on any action whose effect operates on mutex l (acq, rel, w 1 or w 2 ) as well as signals directed to thread i ( sig, c, i , see below), lost signals ( sig, c, 0 , see below), and any broadcast ( bro, c, W for any W ⊆ N, see below). Similarly, an action i, w 2 , c, l is dependent on any action whose effect operates on lock l as well as signals and broadcasts directed to thread i (that is, either sig, c, i or bro, c, W when i ∈ W ).

Variables. An action i, sig, c, j , with j ≥ 0 indicates that thread i executed a pthread cond signal(c) statement. If j = 0 then no thread was waiting on condition variable c, and the signal had no effect, as per the POSIX semantics. We refer to these as lost signals. Example: events 7 and 17 in Fig. 2b and 2d are labeled by lost signals. In both cases thread 1 was not waiting on the condition variable when the signal happened. However, when j ≥ 1 the action represents that thread j wakes up by this signal. Whenever a signal wakes up a thread j ≥ 1, we can always find a (unique) w 1 action of thread j that happened before the signal and a unique w 2 action in thread j that happens after the signal. For instance, event 12 in Fig. 2c signals thread 1, which went sleeping in the w 1 event 10 and wakes up in the w 2 event 14. Similarly, an action i, bro, c, W , with W ⊆ N indicates that thread i executed a pthread cond broadcast(c) statement and any thread j such that j ∈ W was woken up. If W = ∅, then no thread was waiting on condition variable c (lost broadcast). Lost signals and broadcasts on c depend on any action of w 1 , c, · effect as well as any non-lost signal/broadcast on c. Non-lost signals and broadcasts on c that wake up thread j depend 1 on w 1 and w 2 actions of thread j as well as any signal/broadcast (lost or not) on the same condition variable.

A run of P is a sequence of actions in A * which respects the constraints stated above for actions. For instance, a run for the program shown in Fig. 2a is the sequence of actions which labels any topological order of the events shown in any partial order in Fig. 2b to 2e. The sequence below, 1, loc, x=in() , 2, loc, y=1 , 1, acq, m , 1, loc, x>=0 , 1, rel, m , 2, acq, m is a run of Fig. 2a . Naturally, if σ ∈ A * is a run, any prefix of σ is also a run. Runs explicitly represent concurrency, using thread identifiers, and symbolically represent data non-determinism, using constraints, as illustrated by the 1st and 4th actions of the run above. We let runs(P ) denote the set of all runs of P .

A concrete state of P is a tuple that represents, intuitively, the program counters of each thread, the values of all memory locations, the mutexes locked by each thread, and, for each condition variable, the set of threads waiting for it (see [42] for a formal definition). Since runs represent operations on symbolic data, they reach a symbolic state, which conceptually corresponds to a set of concrete states of P .

The state of a run σ, written state(σ), is the set of all concrete states of P that are reachable when the program executes the run σ. For instance, the run σ given above reaches a state consisting on all program states where y is 1, x is a non-negative number, thread 2 owns mutex m and its instruction pointer is at line 3, and thread 1 has finished. We let reach(P ) := σ∈runs(P ) state(σ) denote the set of all reachable states of P .

In the previous section, given an action a ∈ A we informally defined the set of actions which are dependent on a, therefore indirectly defining an independence relation. We now show that this relation is a valid independence [19, 41] . Intuitively, an independence relation is valid when every pair of actions it declares as independent can be executed in any order while still producing the same state.

Our independence relation is valid only for data-race-free programs. We say that P is data-race-free iff any two local actions a := i, loc, t and a := i , loc, t from different threads (i = i ) commute at every reachable state of P . See [42] for additional details. This ensures that local statements of different threads of P modify the memory without interfering each other. Proof. See [42] .

Our technique does not use data races as a source of thread interference for partial-order reduction. It will not explore two execution orders for the two statements that exhibit a data race. However, it can be used to detect and report data races found during the POR exploration, as we will see in Sect. 4.4.

A labeled partial-order (LPO) is a tuple X, <, h where X is a set of events, < ⊆ X × X is a causality (a.k.a., happens-before) relation, and h : X → A labels each event by an action in A.

A partial-order run of P is an LPO that represents a run of P without enforcing an order of execution on actions that are independent. All partialorder runs of Fig. 2a are shown in Fig. 2b to 2e.

Given a run σ of P , we obtain the corresponding partial-order run E σ := E, <, h by the following procedure: (1) initialize E σ to be the only totallyordered LPO that consists of |σ| events where the i-th event is labeled by the i-th action of σ; (2) for every two events e, e such that e < e , remove the pair e, e from < if h(e) is independent from h(e ); (3) restore transitivity in < (i.e., if e < e and e < e , then add e, e to <). The resulting LPO is a partial-order run of P .

Furthermore, the originating run σ is an interleaving of E σ . Given some LPO E := E, <, h , an interleaving of E is the sequence that labels any topological ordering of E. Formally, it is any sequence h(e 1 ), . . . , h(e n ) such that E = {e 1 , . . . , e n } and e i < e j =⇒ i < j. We let inter (E) denote the set of all interleavings of E. Given a partial-order run E of P , the interleavings inter (E) have two important properties: every interleaving in inter (E) is a run of P , and any two interleavings σ, σ ∈ inter (E) reach the same state state(σ) = state(σ ). 

We use unfoldings to give semantics to multi-threaded programs. Unfoldings are Prime Event Structures [37] , tree-like representations of system behavior that use partial orders to represent concurrent interaction. Figure 3a depicts an unfolding of the program in Fig. 2a . The nodes are events and solid arrows represent causal dependencies: events 1 and 4 must fire before 8 can fire. The dotted line represents conflicts: 2 and 5 are not in conflict and may occur in any order, but 2 and 16 are in conflict and cannot occur in the same (partial-order) run.

Formally, a Prime Event Structure [37] (PES) is a tuple E := E, <, #, h with a set of events E, a causality relation < ⊆ E × E, which is a strict partial order, a conflict relation # ⊆ E × E that is symmetric and irreflexive, and a labeling function h : E → A.

The causes of an event e := {e ∈ E : e < e} are the least set of events that must fire before e can fire. A configuration of E is a finite set C ⊆ E that is causally closed ( e ⊆ C for all e ∈ C), and conflict-free (¬(e # e ) for all e, e ∈ C). We let conf (E) denote the set of all configurations of E. For any e ∈ E, the local configuration of e is defined as [e] := e ∪{e}. In Fig. 3a , the set {1, 2} is a configuration, and in fact it is a local configuration, i.e., [2] = {1, 2}. The local configuration of event 6 is {1, 2, 3, 4, 5, 6}. Set {2, 5, 16} is not a configuration, because it is neither causally closed (1 is missing) nor conflict-free (2 # 16).

Given a program P , in this section we define a PES U P such that every configuration of U P is a partial-order run of P .

Let E 1 := E 1 , < 1 , h 1 , . . . , E n := E n , < n , h n be the collection of all the partial-order runs of P . The events of U P are the equivalence classes of the structural equality relation that we intuitively described in Sect. 2.3.

Two events are structurally equal iff their canonical name is the same. Given some event e ∈ E i in some partial-order run E i , the canonical name Figure 3a shows the unfolding produced by merging all 4 partial-order runs in Fig. 2b to 2e. Note that the configurations of U P are partial-order runs of P . Furthermore, the ⊆-maximal configurations are exactly the 4 originating partial orders. It is possible to prove that U P is a semantics of P . In [42] we show that (1) U P is uniquely defined, (2) any interleaving of any local configuration of U P is a run of P , (3) for any run σ of P there is a configuration C of U P such that σ ∈ inter (C).

Our technique analyzes P by iteratively constructing (all) partial-order runs of P . In every iteration we need to find the next partial order to explore. We use the so-called conflicting extensions of a configuration to detect how to start a new partial-order run that has not been explored before.

Given a configuration C of U P , an extension of C is any event e ∈ E \ C such that all the causal predecessors of e are in C. We denote the set of extensions of C as ex ( is not an extension of [6] because 18 is a causal predecessor of 19, but 18 ∈ [6] . A conflicting extension of C is an extension for which there is at least one e ∈ C such that e # e . The (local) configuration [6] from our previous example has two conflicting extensions, events 9 and 16. A conflicting extension is, intuitively, an incompatible addition to the configuration C, an event e that cannot be executed together with C (without removing e and its causal successors from C). We denote by cex (C) the set of all conflicting extensions of C, which coincides with the set of all extensions that are not enabled: cex (C) := ex (C) \ en(C). Our technique discovers new conflicting extension events by trying to revert the causal order of certain events in C. Owing to space limitations we only explain how the algorithm handles events of acq and w 2 effect ( [42] presents the remaining 4 procedures of the algorithm). Algorithm 1 shows the procedure that handles this case. It receives an event e of acq or w 2 effect (line 2). We build and return a set of conflicting extensions, stored in variable R. Events are added to R in line 14 and 17. Note that we define events using their canonical name. For instance, in line 14 we add a new event whose action is h(e) and whose causal history is P . Note that we only create events that execute action h(e). Conceptually speaking, the algorithm simply finds different causal histories (variables P and e ) within the set K = e to execute action h(e).

Procedure last-of(C, i) returns the only <-maximal event of thread i in C; last-notify(e, c, i) returns the only immediate <-predecessor e of e such that the effect of h(e ) is either sig, c, i or bro, c, S with i ∈ S; finally, procedure last-lock(C, l) returns the only <-maximal event that manipulates lock l in C (an event of effect acq, rel, w 1 or w 2 ), or ⊥ if no such event exists. See [42] for additional details. 

This section presents an algorithm that explores the state space of P by constructing all maximal configurations of U P . In essence, our procedure is an improved Quasi-Optimal POR algorithm [35] , where the unfolding is not explored using a DFS traversal, but a user-defined search order. This enables us to build upon the preexisting exploration heuristics ("searchers") in KLEE rather than having to follow a strict DFS exploration of the unfolding.

Our algorithm explores one configuration of U P at a time and organizes the exploration into a binary tree. Figure 3b shows the tree explored for the unfolding shown in Fig. 3a . A tree node is a tuple n := C, D, A, e that represents both the exploration of a configuration C of U P and a choice to execute, or not, event e ∈ en(C). Both D (for disabled ) and A (for add ) are sets of events.

The key insight of this tree is as follows. The subtree rooted at a given node n explores all configurations of U P that include C and exclude D, with the following constraint: n's left subtree explores all configurations including event e and n's right subtree explores all configuration excluding e. Set A is used to guide the algorithm when exploring the right subtree. For instance, in Fig. 3b the subtree rooted at node n := {1, 2}, ∅, ∅, 3 explores all maximal configurations that contain events 1 and 2 (namely, those shown in Fig. 2b and 2c) . The left subtree of n explores all configurations including {1, 2, 3} (Fig. 2b ) and the right subtree all of those including {1, 2} but excluding 3 (Fig. 2c) .

Algorithm 2 shows a simplified version of our algorithm. The complete version, in [42] , specifies additional details including how nodes are selected for exploration and how they are removed from the tree. The algorithm constructs and stores the exploration tree in the variable N , and the set of currently known events of U N in variable U . At the end of the exploration, U will store all events of U N and the leafs of the exploration tree in N will correspond to the maximal configurations of U N .

The tree is constructed using a fixed-point loop (line 4) that repeats the following steps as long as they modify the tree: select a node C, D, A, e in the tree (line 5), extend U with the conflicting extensions of C (line 6), check if the configuration is ⊆-maximal (line 7), in which case there is nothing left to do, then try to add a left (line 9) or right (line 12) child node.

The subtree rooted at the left child node will explore all configurations that include C ∪ {e} and exclude D (line 10); the right subtree will explore those including C and excluding D ∪ {e} (line 15), if any of them exists, which we detect by checking (line 14) if we found a so-called alternative [41] .

An alternative is a set of events which witnesses the existence of some maximal configuration in U P that extends C without including D ∪ {e}. Computing such witness is an NP-complete problem, so we use an approximation called k-partial alternatives [35] , which can be computed in P-time and works well in practice. Our procedure alt specifically computes 1-partial alternatives: it selects k = 1 event e from D ∩ en(C), searches for an event e in conflict with e (we have added all known candidates in line 6, using the algorithms of Sect. 3.6) that can extend C (i.e., such that C ∪ [e ] is a configuration), and returns it. When such an event e is found (line 33), some events in its local configuration [e ] become the A-component of the right child node (line 15), and the leftmost branch rooted at that node will re-execute those events (as they will be selected in line 20), guiding the search towards the witnessed maximal configuration. 

All interleavings of a given configuration always reach the same state, but interleavings of different configurations can also reach the same state. It is possible to exclude certain such redundant configurations from the exploration without making the algorithm incomplete, by using cutoff events [32] .

Intuitively, an event is a cutoff if we have already visited another event that reaches the same state with a shorter execution. Formally, in Algorithm 2, line 27 While cutoffs prevent the exploration of redundant configurations, the analysis is still complete: it is possible to prove that every state reachable via a configuration with cutoffs is also reachable via a configuration without cutoffs. Furthermore, cutoff events not only reduce the exploration of redundant configurations, but also force the algorithm to terminate for non-terminating programs that run on bounded memory.

For any reachable state s ∈ reach(P ), Algorithm 2 explores a configuration C such that for some C ⊆ C it holds that state(C ) = s. Furthermore, it terminates for any program P such that reach(P ) is finite.

A proof sketch is available in [42] . Naturally, since Algorithm 2 explores U P , and U P is an exact representation of all runs of P , then Algorithm 2 is also sound : any event constructed by the algorithm (added to set U ) is associated with a real run of P .

We implemented our approach on top of the symbolic execution engine KLEE [10] , which was previously restricted to sequential programs. KLEE already provides a minimal POSIX support library that we extended to translate calls to pthread functions to their respective actions, enabling us to test real-world multi-threaded C programs. We also extended already available functionality to make it threadsafe, e.g., by implementing a global file system lock that ensures that concurrent reads from the same file descriptor do not result in unsafe behavior. The source code of our prototype is available at https://github.com/por-se/por-se.

When a new alternative is explored, a symbolic execution state needs to be computed to match the new node in the POR tree. However, creating it from scratch requires too much time and keeping a symbolic execution state around for each node consumes significant amounts of memory. Instead of committing to either extreme, we store standby states at regular intervals along the exploration tree and, when necessary, replay the closest standby state. This way, significantly fewer states are kept in memory without letting the replaying of previously computed operations dominate the analysis either.

Schemmel et al. presented [43] an incremental hashing scheme to identify infinite loops during symbolic execution. The approach detects when the program under test can transition from any one state back to that same state. Their scheme computes fragments for small portions of the program state, which are then hashed individually, and combined into a compound hash by bitwise xor operations. This compound hash, called a fingerprint, uniquely (modulo hash collisions) identifies the whole state of the program under test. We adapt this scheme to provide hashes that identify the concurrent state of parallel programs.

To this end, we associate each configuration with a fingerprint that describes the whole state of the program at that point. For example, if the program state consists of two variables, x = 3 and y = 5, the fingerprint would be fp = hash ("x=3") ⊕ hash ("y=5"). When one fragment changes, e.g., from x = 3 to x = 4, the old fragment hash needs to be replaced with the new one. This operation can be performed as fp = fp ⊕ hash ("x=3") ⊕ hash ("x=4") as the duplicate fragments for x = 3 will cancel out. To quickly compute the fingerprint of a configuration, we annotate each event with an xor of all of these update operations that were done on its thread. Computing the fingerprint of a configuration now only requires xor-ing the values from its thread-maximal events, which will ensure that all changes done to each variable are accounted for, and cancel out one another so that only the fragment for the last value remains.

Any two local configurations that have the same fingerprint represent the same program state; each variable, program counter, etc., has the same value. Thus, it is not necessary to continue exploring both-we have found a potential cutoff point, which the POR algorithm will treat accordingly (Sect. 3.8).

KLEE usually uses the system allocator to determine the addresses of objects allocated by the program under test. But it also provides a (more) deterministic mode, in which addresses are consumed in sequence from a large pre-allocated array. Since our hash-based cutoff computation uses memory address as part of the computation, using execution replays from standby states (Sect. 4.1) requires that we have fully repeatable memory allocation.

We tackle this problem by decoupling the addresses returned by the emulated system allocator in the program under test from the system allocator of KLEE itself. A new allocator requires a large amount of virtual memory in which it will perform its allocations. This large virtual memory mapping is not actually used unless an external function call is performed, in which case the relevant objects are temporarily copied into the region from the symbolic execution state for which the external function call is to be performed. Afterwards, the pages are marked for reclamation by the OS. This way, allocations done by different symbolic execution states return the same address to the program under test.

While a deterministic allocator by itself would be enough for providing deterministic allocation to sequential programs, parallel programs also require an allocation pattern that is independent of which sequentialization of the same partial order is chosen. We achieve this property by providing independent allocators for each thread (based on the thread id, thus ensuring that the same virtual memory mapping is reused for each instance of the same semantic thread). When an object is deallocated on a different thread than it was allocated on, its address only becomes available for reuse once the allocating thread has reached a point in its execution where it is causally dependent on the deallocation. Additionally, the thread ids that are used by our implementation are hierarchically defined: A new thread t that is the i-th thread started by its parent thread p has the thread id t := (p, i), with the main thread being denoted as (1). This way, thread ids and the associated virtual memory mappings are independent of how the concurrent creation of multiple threads are sequentialized.

We have also included various optimizations that promote controlled reuse of addresses to increase the chance that a cutoff event (Sect. 4.2) is found, such as binning allocations by size, which reduces the chance that temporary allocations impact which addresses are returned for other allocations.

Our data race detection algorithm simply follows the happens-before relationships established by the POR. However, its implementation is complicated by the possibility of addresses becoming symbolic. Generally speaking, a symbolic address can potentially point to any and every byte in the whole address space, thus requiring frequent and large SMT queries to be solved.

To alleviate the quadratic blowup of possibly aliasing accesses, we exploit how KLEE performs memory accesses with symbolic addresses: The symbolic state is forked for every possible memory object that the access may refer to (and one additional time if the memory access may point to unallocated memory). Therefore, a symbolic memory access is already resolved to memory object granularity when it potentially participates in a data race. This drastically reduces the amount of possible data races without querying the SMT solver.

When a program wants to call a function that is neither provided by the program itself nor by the runtime, KLEE will attempt to perform an external function call by moving the function arguments from the symbolic state to its own address space and attempting to call the function itself. While this support for uninterpreted functions is helpful for getting some results for programs which are not fully supported by KLEE's POSIX runtime, it is also inherently incomplete and not sound in the general case. Our prototype includes this option as well.

To explore the efficacy of the presented approach, we performed a series of experiments including both synthetic benchmarks from the SV-COMP [9] benchmark suite and real-world programs, namely, Memcached [3] and GNU sort [1] . We compare against Yogar-CBMC [49] , which is the winner of the concurrency safety category of SV-COMP 2019 [9] , and stands in for the family of bounded model checkers. As such, Yogar-CBMC is predestined to fare well in the artificial SV-COMP benchmarks, while our approach may demonstrate its strength in dealing with more complicated programs. We ran the experiments on a cluster of multiple identical machines with dual Intel Xeon E5-2643 v4 CPUs and 256 GiB of RAM. We used a 4 h timeout and 200 GB maximum memory usage for real-world programs. We used a 15 min timeout and 15 GB maximum memory for individual SV-COMP benchmarks.

We ran our tool and Yogar-CBMC on the "pthread" and "pthread-driver-races" benchmark suites in their newest (2020) incarnation. As expected, Table 1 shows that Yogar-CBMC clearly outperforms our tool for this specific set of benchmarks. Not only does Yogar-CBMC not miscategorize even a single benchmark, it does so quickly and without using a lot of memory. Our tool, in contrast, takes significantly more time and memory to analyze the target benchmarks. In fact, several benchmarks do not complete within the 15 min time frame and therefore cannot give a verdict for those.

The "pthread-driver-races" benchmark suite contains one benchmark that is marked as a failure for our tool in Table 1 . For the relevant benchmark, a verdict of "target function unreachable" is expected, which we translate to mean "no data race occurs". However, the benchmark program constructs a pointer that may point to effectively any byte in memory, which, upon dereferencing it, leads to both, memory errors and data races (by virtue of the pointer also being able to touch another thread's stack). While we report this behavior for completeness sake, we attribute it to the adaptations made to fit the SV-COMP model to ours.

Preparation of Benchmark Suites. The SV-COMP benchmark suite does not only assume various kinds of special casing (e.g., functions whose name begins with VERIFIER atomic must be executed atomically), but also routinely violates the C standard by, for example, employing data races as a control flow mechanism [25, § 5.1.2.4 /35] . Partially, this is because the analysis target is a question of reachability of a certain part of the benchmark program, not its correctness. We therefore attempted to guess the intention of the individual benchmarks, making variables atomic or leaving the data race in when it is the aim of the benchmark.

Memcached [3] is an in-memory network object cache written in C. As it is a somewhat large project with a fairly significant state space, we were unable to analyze it completely, even though our prototype still found several bugs. Our attempts to run Yogar-CBMC did not succeed, as it reproducibly crashes.

Faults Detected. Our prototype found nine bugs in memcached 1.5.19, attributable to four different root causes, all of which where previously unknown. The first bug is a misuse of the pthread API, causing six mutexes and condition variables to be initialized twice, leading to undefined behavior. We reported 2 the issue, a fix is included in version 1.5.20. The second bug occurs during the initialization of memcached, where fields that will later be accessed in a threadsafe manner are sometimes accessed in a non-thread-safe manner, assuming that competing accesses are not yet possible. We reported 3 a mistake our tool found in the initialization order that invalidates the assumption that locking is not (yet) necessary on one field. A fix ships with memcached 1.5.21. For the third bug, memcached utilizes a maintenance thread to manage and resize its core hash table when necessary. Additionally, on another thread, a timer checks whether the maintenance thread should perform an expansion of the hash table. We found 4 a data race between these two threads on a field that stores whether the maintenance thread has started expanding. This is fixed in version 1.5.20. The fourth and final issue is a data race on the stats state storing execution statistics. We reported 5 this issue and a fix is included in version 1.5.21.

We run our prototype on five different versions of memcached, the three releases 1.5.19, 1.5.20 and 1.5.21 plus variants of the earlier releases (1.5.19+ and 1.5.20+) which include patches for the two bugs we found during program initialization. Those variants are included to show performance when not restricted by inescapable errors very early in the program execution. Table 2 shows clearly how the two initialization bugs may lead to very quick analyses-versions 1.5.19 and 1.5.20 are completely analyzed in 7 s each, while versions 1.5.19+, 1.5.20+ and 1.5.21 exhaust the memory budget of 200 GB. We have configured the experiment to stop the analysis once the memory limit is reached, although the analysis could continue in an incomplete manner by removing parts of the exploration frontier to free up memory. Even though the number of error paths in Table 2 differs between configurations, it is notable that each configuration can only reach exactly one of the bugs, as execution is arrested at that point. When not restricted to the program initialization, the analysis of memcached produces hundreds of thousands of events and retires hundreds of millions of instructions in less than 2 h. Our setup delivers a single symbolic packet to memcached followed by a concrete shutdown packet. As this packet can obviously only be processed once the server is ready to process input, we observe symbolic choices only after program startup is complete. (Since our prototype builds on KLEE, note that it assumes a single symbolic choice during startup, without generating an additional path.)

GNU sort uses threads for speeding up the sorting of very large workloads. We reduced the minimum size of input required to trigger concurrent sorting to four lines to enable the analysis tools to actually trigger concurrent behavior. Nevertheless, we were unable to avoid crashing Yogar-CBMC on this input.

During analysis of GNU sort 8.31, our prototype detected a data race, that we manually verified, but were unable to trigger in a harmful manner. Table 2 shows two variants of GNU sort, the baseline version with eager parallelization (8.31) and a version with added locking to prevent the data race (8.31+).

Surprisingly, version 8.31 finishes the exploration, as all paths either exit, encounter the data race and are terminated or are cut off. By fixing the data race in version 8.31+, we make it possible for the exploration to continue beyond this point, which results in a full 4 h run that retires a full billion instructions while encountering almost seven million unique events.

The body of work in systematic concurrency testing [5, 6, 19, 21, 23, 35, 41, 47, 50] is large. These approaches explore thread interleavings under a fixed program input. They prune the search space using context-bounding [34] , increasingly sophisticated PORs [5] [6] [7] 12, 19, 23, 35, 41] , or random testing [13, 50] . Our main difference with these techniques is that we handle input data.

Thread-modular abstract interpretation [18, 30, 33] and unfolding-based abstract interpretation [46] aim at proving safety rather than finding bugs. They use over-approximations to explore all behaviors, while we focus on testing and never produce false alarms. Sequentialization techniques [26, 36, 40 ] encode a multi-threaded program into a sequential one. While these encodings can be very effective for small programs [26] they grow quickly with large context bounds (5 or more, see [36] ). However, some of the bugs found by our technique (Sect. 5) require many context switches to be reached.

Bounded-model checking [8, 15, 28, 39, 49] for multi-threaded programs encode multiple program paths into a single logic formula, while our technique encodes a single path. Their main disadvantage is that for very large programs, even constructing the multi-path formula can be extremely challenging, often producing an upfront failure and no result. Conversely, while our approach faces path explosion, it is always able to test some program paths.

Techniques like [17, 27, 44] operate on a data structure conceptually very similar to our unfolding. They track read/write operations to every variable, which becomes a liability on very large executions. In contrast, we only use POSIX synchronization primitives and compactly represent memory accesses to detect data races. Furthermore, they do not exploit anything similar to cutoff events for additional trace pruning.

Interpolation [14, 48] and weakest preconditions [24] have been combined with POR and symbolic execution for property-guided analysis. These approaches are mostly complementary to PORs like our technique, as they eliminate a different class of redundant executions [24] .

This work builds on top of previous work [35, 41, 46] . The main contributions w.r.t. those are: (1) we use symbolic execution instead of concurrency testing [35, 41] or abstract interpretation [46] ; (2) we support condition variables, providing algorithms to compute conflicting extensions for them; and (3) here we use hashbased fingerprints to compute cutoff events, thus handling much more complex partial orders than the approach described in [46] .

Our approach combines POR and symbolic execution to analyze programs w.r.t. both input (data) and concurrency non-determinism. We model a significant portion of the pthread API, including try-lock operations and robust mutexes. We introduce two techniques to cope with state-space explosion in real-world programs. We compute cutoff events by using efficiently-computed fingerprints that uniquely identify the total state of the program. We restrict scheduling to synchronization points and report data races as errors. Our experiments found previously unknown bugs in real-world software projects (memcached, GNU sort).

Helgrind: A thread error detector

IEEE Standard for Information Technology-Portable Operating System Interface (POSIX(R)) Base Specifications, Issue 7. Standard IEEE Std 1003

Optimal dynamic partial order reduction

Stateless model checking for TSO and PSO

Optimal context-sensitive dynamic partial order reduction with observers

Partial orders for efficient bounded model checking of concurrent software

Automatic verification of C and Java programs: SV-COMP

KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs

Symbolic execution for software testing: three decades later

Data-centric dynamic partial order reduction

Testing multithreaded programs via thread speed control

A framework to synergize partial order reduction with state interpolation

Verifying multi-threaded software using SMT-based context-bounded model checking

An improvement of McMillan's unfolding algorithm

Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013

Causal dataflow analysis for concurrent programs

Dynamic partial-order reduction for model checking software

Partial-Order Methods for the Verification of Concurrent Systems

Model checking for programming languages using VeriSoft

Automated whitebox fuzz testing

Cartesian partial-order reduction

Assertion guided symbolic execution of multithreaded programs

International Organization for Standardization: Information technology -Programming languages -C

Bounded model checking of multi-threaded C programs via lazy sequentialization

Unfolding based automated testing of multithreaded programs

Monotonic partial order reduction: an optimal symbolic partial order reduction technique

Symbolic execution and program testing

Flow-sensitive composition of thread-modular abstract interpretation

Trace theory

Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits

Relational thread-modular static value analysis by abstract interpretation

Iterative context bounding for systematic testing of multithreaded programs

Quasi-optimal partial order reduction

Parallel bugfinding in concurrent programs via reduced interleaving instances

Petri nets, event structures and domains, Part I

Symbolic PathFinder: symbolic execution of Java bytecode

Concurrent program verification with invariant-guided underapproximation

KISS: keep it simple and sequential

Unfolding-based partial order reduction

Symbolic partialorder execution for testing multi-threaded programs

Symbolic liveness analysis of real-world software

A race-detection and flipping algorithm for automated testing of multi-threaded programs

ThreadSanitizer: data race detection in practice

Abstract interpretation with unfoldings

Concurrency testing using controlled schedulers: an empirical study

Verifying multi-threaded software with impact

YOGAR-CBMC: CBMC with scheduling constraint based abstraction refinement

Maple: a coverage-driven testing tool for multithreaded programs