CLAP: Recording Local Executions to Reproduce Concurrency Failures

CLAP is a new technique to reproduce concurrency bugs. At runtime, it only logs thread local execution paths. Then, offline, it computes memory dependencies that accord with the logged execution and are able to reproduce the observed bug. The second step works by combining constraints from the thread paths and constraints based on a memory model, and computing an execution with a constraint solver. 

CLAP has four major advantages. First, logging purely local execution of each thread is substantially cheaper than logging memory interactions, which enables CLAP to be efficient compared to previous approaches. Second, our logging does not require any synchronization and hence with no added memory barriers or fences; this minimizes perturbation and missed bugs due to extra synchronizations foreclosing certain racy behaviors. Third, since it uses no synchronization, we extend CLAP to work on a range of relaxed memory models, such as TSO and PSO, in addition to sequential consistency. Fourth, CLAP can compute a much simpler execution than the original one, that reveals the bug with minimal thread context switches. To mitigate the scalability issues, we have also developed an approach to parallelize constraint solving, which theoretically scales our technique to programs with arbitrary execution length.

Contents:


People

Please contact Jeff if you have any question about CLAP.


Document

Please read our PLDI 2013 paper describing the details of CLAP.


Download (for Mac OSX)


Example

This section shows how to use CLAP.

Sample Program klee.h race.c raceKLEE.c:

#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <klee.h>

int x;
int * ptr;
pthread_t child, child2, child3, child4;

void setup() {
}
void teardown() {
}
void * routine1(void * arg) {
    ptr = NULL;
}
void * routine2(void * arg) {
    x = 4;
    ptr = &x;
}
void * routine3(void * arg) {
    x = 5;
    ptr = &x;
}
void * routine4(void * arg) {
    x = 3;
    ptr = &x;    
}
int main(int argc, char *argv[]) {

    setup();
    x = 0;
    ptr = &x;
    pthread_create(&child, NULL, routine1, NULL);
    pthread_create(&child2, NULL, routine2, NULL);
    pthread_create(&child3, NULL, routine3, NULL);
    pthread_create(&child4, NULL, routine4, NULL);

    pthread_join(child, NULL);
    pthread_join(child2, NULL);
    pthread_join(child3, NULL);
    pthread_join(child4, NULL);

    if(*ptr==1)
        printf("X is %d\n", 1);
    else if(*ptr==2)
        printf("X is %d\n", 2);
    else if(*ptr==3)
        printf("X is %d\n", 3);
    else if(*ptr==4)
        printf("X is %d\n", 4);
    else
        printf("X is %d\n", *ptr);

    teardown();
}

The simple program may produce different outputs on different runs, depending on the order of the write accesses to x among the four children threads (which is non-deterministic). The program may even crash with segmentation fault if the first child thread executes last (which sets "ptr" to NULL). However, this crash is difficult to reproduce once it happens. 

We next show how CLAP reproduces the crash:

  1. Runtime logging: ./runlog race
    2. A control-flow log "bbiid" and a synchronization log "synciid" will be generated: 
    cat bbiid

0 12 0 1 14 16 17 21 2 3 22
1 4 5
2 6 7
3 8 9
4 10 11  

    cat synciid

0 fork 1
0 fork 2
0 fork 3
0 fork 4
0 join 1
0 join 2
0 join 3
0 join 4
  2. Symbolic execution: ./runclapse race
    Run our symbolic execution engine (a modification of KLEE) to collect thread path constraints. A symbolic trace file will be generated in klee-last/trace:
    3. W-x_140662515500592-0
$0$
S-fork-0
S-fork-0
S-fork-0
S-fork-0
S-join-0
S-join-0
S-join-0
S-join-0
R-x_140662515500592-0-1
W-x_140662515500592-3
$5$
W-x_140662515500592-2
$4$
W-x_140662515500592-4
$3$
R-x_140662515500592-0-2
R-x_140662515500592-0-3
T0:(Eq false
    (Eq 1
        (ReadLSB w32 0 x_140662515500592-0-1)))
T0:(Eq false
    (Eq 2
        (ReadLSB w32 0 x_140662515500592-0-2)))
T0:(Eq 3
    (ReadLSB w32 0 x_140662515500592-0-3))
  3. Constraint construction and solving: ./clap klee-last/trace
    If the solver is able to find a solution, a bug-reproducing schedule will be generated:
    4. Array 0:	S-0-0[0]
Array 1:	W-x_140238781745600-0-1[1]
Array 2:	S-0-1[2]
Array 3:	S-0-2[3]
Array 4:	S-0-3[6]
Array 5:	S-0-4[7]
Array 6:	S-0-5[15]
Array 7:	S-0-6[16]
Array 8:	S-0-7[17]
Array 9:	S-0-8[18]
Array 10:	R-x_140238781745600-0-1[19]
Array 11:	R-x_140238781745600-0-2[20]
Array 12:	R-x_140238781745600-0-3[21]
Array 13:	S-0-N[22]
Array 14:	S-2-0[4]
Array 15:	W-x_140238781745600-2-1[5]
Array 16:	S-2-N[14]
Array 17:	S-3-0[8]
Array 18:	W-x_140238781745600-3-1[9]
Array 19:	S-3-N[13]
Array 20:	S-4-0[10]
Array 21:	W-x_140238781745600-4-1[11]
Array 22:	S-4-N[12]
Array 23:	x_140238781745600-0-1[3]
Array 24:	x_140238781745600-0-2[3]
Array 25:	x_140238781745600-0-3[3]

    The number in the square brackets represents the order of the corresponding operation in the schedule. 
The schedule above is: t0-t0-t0-t0-t2-t2-t2-t0-t3-t3-t0-t3-t0-t0-t4-t0-t4-t4-t0-t0-t0-t0

The above steps illustrate the usage of each component of CLAP. For more convenient use, we can run them all together:

./runall race


Steps to Build CLAP:

  1. Follow KLEE website to build:
  2. Build CLAP symbolic execution engine (based on KLEE):