Tools and Benchmarks

Just download the image file (period.tar) and follow the installation instructions below:

period.tar

We executed our experiments on a Linux cluster, with Ubuntu 18.04 LTS, an x86_64 architecture, and LLVM 10.0. We recommend using 64-bit Linux machines with Docker installation:

• OS: Ubuntu 18.04 LTS (Requires kernel version >= 4.x due to our periodical scheduling.)

• Run the following command to install Docker (Docker version higher than 18.09.7):
  $ sudo apt-get install docker.io
  (If you have any questions on docker, you can see Docker's Documentation).

Open a terminal window, change to the directory that containing the downloaded period.tar.

Execute the following command to automatically import the image file.

$ sudo docker import period.tar period:v1

Run the docker image

$ sudo docker run --privileged -it period:v1 /bin/bash

Then you will enter the configured virtual environment of PERIOD.

The folder of PERIOD is located in the directory /workdir/PERIOD.

We briefly introduce each folder under /workdir/PERIOD:

• clang+llvm: Pre-Built Binaries of LLVM 10.0. These binaries include Clang, LLD, compiler-rt, various LLVM tools, etc.

• documents: Some description documents and old files. Omit this directory.

• tools: Root directory for PERIOD tool and scripts.

  • DBDS: The code about our proposed periodical scheduling method that can systematically explore the thread interleaving.

  • staticanalysis: The scripts of static analysis, which aim to find key points that used to be scheduled during testing. It also contains the codes about instrumentation.

  • SVF: Third-party libraries project SVF, which provides interprocedural dependence analysis for LLVM-based languages. SVF is able to perform pointer alias analysis, memory SSA form construction, value-flow tracking for program variables.

  • wllvm: Third-party libraries project WLLVM, which provides tools for building whole-program (or whole-library) LLVM bitcode files from an unmodified C or C++ source package.

• test: Some simple examples that are easy to understand. These examples could also be used to check the installation.

• evaluation: Root for benchmark directories. The ConVul-CVE-Benchmarks correspond to the 10 programs used in Table. 1 in our paper. Other folders contain the 36 programs used in Table. 2 in our paper. We provide scripts for each program for easy installation.

  • CB: Test cases for real applications.

  • CS: Small test cases and some small programs.

  • Chess: Test cases for several versions of a work-stealing queue.

  • ConVul-CVE-Benchmarks: 10 programs correspond to a real-world CVE.

  • Inspect_benchmarks: Small test cases and some small programs.

  • RADBench: Tests cases for real applications.

  • SafeStack: Test case for lock-free stack and a debugging library test case.

  • Splash2: Parallel workloads.

You can use one of the programs in the test folder to check whether PERIOD works normally.

Enter the working directory:

$ cd /workdir/PERIOD/test/work

Use the following script to build the program:

$ ./cleanDIR.sh

$ ./build.sh

Perform systematic controlled concurrency testing based on periodical scheduling:

$ $ROOT_DIR/tool/DBDS/run_PDS.py -y -d 3 -l ./work

If PERIOD works normally, you can see the following outputs, which indicate that PERIOD reports 2 bugs in this program (i.e., memory leaks and double free):

Start Testing!

Targeting bugs that bug depth = 1 . Iterate for 2 periods

test 0001: [[0, 0, 0, 0], [1, 1, 1, 1]]

test 0002: [[1, 1, 1, 1], [0, 0, 0, 0]]

Targeting bugs that bug depth = 2 . Iterate for 3 periods

test 0003: [[0], [1, 1, 1, 1], [0, 0, 0]]

[Error Found]: NO.1 memory leaks

The interleavings saved in out_work_1/Errors/000001_0000003_memory-leaks

test 0004: [[0, 0], [1, 1, 1, 1], [0, 0]]

test 0005: [[0, 0, 0], [1, 1, 1, 1], [0]]

test 0006: [[1], [0, 0, 0, 0], [1, 1, 1]]

[Error Found]: NO.2 memory leaks

The interleavings saved in out_work_1/Errors/000002_0000006_memory-leaks

test 0007: [[1, 1], [0, 0, 0, 0], [1, 1]]

test 0008: [[1, 1, 1], [0, 0, 0, 0], [1]]

Targeting bugs that bug depth = 3 . Iterate for 4 periods

test 0009: [[0], [1], [0, 0, 0], [1, 1, 1]]

[Error Found]: NO.3 memory leaks

The interleavings saved in out_work_1/Errors/000003_0000009_memory-leaks

test 0010: [[0], [1, 1], [0, 0, 0], [1, 1]]

[Error Found]: NO.4 double-free

The interleavings saved in out_work_1/Errors/000004_0000010_double-free

test 0011: [[0], [1, 1, 1], [0, 0, 0], [1]]

[Error Found]: NO.5 double-free

The interleavings saved in out_work_1/Errors/000005_0000011_double-free

test 0012: [[0, 0], [1], [0, 0], [1, 1, 1]]

[Error Found]: NO.6 memory leaks

The interleavings saved in out_work_1/Errors/000006_0000012_memory-leaks

test 0013: [[0, 0], [1, 1], [0, 0], [1, 1]]

test 0014: [[0, 0], [1, 1, 1], [0, 0], [1]]

test 0015: [[0, 0, 0], [1], [0], [1, 1, 1]]

[Error Found]: NO.7 memory leaks

The interleavings saved in out_work_1/Errors/000007_0000015_memory-leaks

test 0016: [[0, 0, 0], [1, 1], [0], [1, 1]]

test 0017: [[0, 0, 0], [1, 1, 1], [0], [1]]

test 0018: [[1], [0], [1, 1, 1], [0, 0, 0]]

[Error Found]: NO.8 memory leaks

The interleavings saved in out_work_1/Errors/000008_0000018_memory-leaks

test 0019: [[1, 1], [0], [1, 1], [0, 0, 0]]

[Error Found]: NO.9 memory leaks

The interleavings saved in out_work_1/Errors/000009_0000019_memory-leaks

test 0020: [[1, 1, 1], [0], [1], [0, 0, 0]]

[Error Found]: NO.10 memory leaks

The interleavings saved in out_work_1/Errors/000010_0000020_memory-leaks

test 0021: [[1], [0, 0], [1, 1, 1], [0, 0]]

[Error Found]: NO.11 memory leaks

The interleavings saved in out_work_1/Errors/000011_0000021_memory-leaks

test 0022: [[1, 1], [0, 0], [1, 1], [0, 0]]

test 0023: [[1, 1, 1], [0, 0], [1], [0, 0]]

test 0024: [[1], [0, 0, 0], [1, 1, 1], [0]]

[Error Found]: NO.12 memory leaks

The interleavings saved in out_work_1/Errors/000012_0000024_memory-leaks

test 0025: [[1, 1], [0, 0, 0], [1, 1], [0]]

test 0026: [[1, 1, 1], [0, 0, 0], [1], [0]]

End Testing!

Total Error Interleavings: 12

Total Timeouts Interleavings: 0

2 status found:

[0, -6]

0 results found:

--------------------------------------------------

Last New Find Total

Round 0 26

Time 00:00:00.00000 00:00:02.08057

After the testing terminates, you can find the folder out_work_1, which saves the buggy schedule that could deterministically reproduce the bugs.

Use the command like the following to reproduce the memory leaks:

$ $ROOT_DIR/tool/DBDS/run_PDS.py -r out_work_1/Errors/000001_0000003_memory-leaks -l ./work

And you will see the memory leaks reported by ASAN:

=================================================================

==2666==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 10 byte(s) in 1 object(s) allocated from:

#0 0x49445d (/workdir/PERIOD/test/work/work+0x49445d)

#1 0x4c64fd (/workdir/PERIOD/test/work/work+0x4c64fd)

SUMMARY: AddressSanitizer: 10 byte(s) leaked in 1 allocation(s).

Or use the command like the following to reproduce the double-free:

$ $ROOT_DIR/tool/DBDS/run_PDS.py -r out_work_1/Errors/000004_0000010_double-free ./work

And you will see the double-free reported by ASAN:

=================================================================

==2773==ERROR: AddressSanitizer: attempting double-free on 0x602000001010 in thread T2:

#0 0x4941dd (/workdir/PERIOD/test/work/work+0x4941dd)

#1 0x4c6564 (/workdir/PERIOD/test/work/work+0x4c6564)

#2 0x7f8c3f7716da (/lib/x86_64-linux-gnu/libpthread.so.0+0x76da)

#3 0x7f8c3e74f71e (/lib/x86_64-linux-gnu/libc.so.6+0x12171e)

0x602000001010 is located 0 bytes inside of 10-byte region [0x602000001010,0x60200000101a)

freed by thread T1 here:

#0 0x4941dd (/workdir/PERIOD/test/work/work+0x4941dd)

#1 0x4c6564 (/workdir/PERIOD/test/work/work+0x4c6564)

previously allocated by thread T2 here:

#0 0x49445d (/workdir/PERIOD/test/work/work+0x49445d)

#1 0x4c64fd (/workdir/PERIOD/test/work/work+0x4c64fd)

Thread T2 created by T0 here:

#0 0x47f20a (/workdir/PERIOD/test/work/work+0x47f20a)

#1 0x4c66b0 (/workdir/PERIOD/test/work/work+0x4c66b0)

#2 0x7f8c3e64fbf6 (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)

Thread T1 created by T0 here:

#0 0x47f20a (/workdir/PERIOD/test/work/work+0x47f20a)

#1 0x4c668d (/workdir/PERIOD/test/work/work+0x4c668d)

#2 0x7f8c3e64fbf6 (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)

SUMMARY: AddressSanitizer: double-free (/workdir/PERIOD/test/work/work+0x4941dd)

==2773==ABORTING

If the above steps can be executed normally, it means that your installation has been successful！

The fold evaluation contains all our evaluation subjects. After having PERIOD installed, you can run the scripts ./build.sh to automatically build the benchmark program with PERIOD instrumentation. Then run the script $ROOT_DIR/tool/DBDS/run_PDS.py to perform systematic controlled concurrency testing based on periodical scheduling, with the command $ROOT_DIR/tool/DBDS/run_PDS.py -d <periods limits> -t <timeout> <program under test> <args>. We take the CVE-2016-7911 in ConVul-CVE-Benchmark as an example here.

Build Benchmark Program

$ cd /workdir/PERIOD/evaluation/ConVul-CVE-Benchmarks/CVE-2016-7911

$ ./cleanDIR.sh

$ ./build.sh

Expose Bugs with PERIOD

$ $ROOT_DIR/tool/DBDS/run_PDS.py -d 3 ./2016-7911

Deterministically Reproduce the Bug

$ROOT_DIR/tool/DBDS/run_PDS.py -r out_2016-7911_1/Errors/000001_0000003_SEGV ./2016-7911

(More detailed usage will be updated later. We illustrate it with an example here)

Previously, we recommend using the script ./build we provided to build the benchmark programs. Here, we introduce how to use PERIOD for general programs. We use an example to quickly show you how to use PERIOD to test a concurrent program. Consider the following multithreaded program (the code can be found in /workdir/PERIOD/test/work).

01 #include <stdio.h>

02 #include <stdlib.h>

03 #include <pthread.h>

04

05 char *g;

06

07 void *Work(void *args) {

08

09 g = (char*)malloc(10); printf("%p\n",g);

10 if (g != NULL) {

11 free(g);

12 }

13 g = NULL;

14 }

15

16 int main(int argc, char **argv) {

17 pthread_t id1, id2;

18 pthread_create(&id2, NULL, Work, NULL);

19 pthread_create(&id1, NULL, Work, NULL);

20 pthread_join(id1, NULL);

21 pthread_join(id2, NULL);

22 printf("finished\n");

23 return 0;

24 }

This program creates two threads. Each thread will write the shared variable g. In the beginning, both threads try to allocate a section of memory and write the address that points to allocated memory to variable g. Then if g != NULL, the memory pointed by g will be released. Finally, set g = NULL.

Obviously, this program has a double-free and memory leak bug on the shared variable g. If the g = (char*)malloc(10); in one thread execute following close at the g = (char*)malloc(10); in another thread, a memory leak on g would happen. A double-free can occur if g in both threads become alias, and the free(g); statement in one thread executes following close at the free(g); in another thread, a double-free would happen. We want to see whether PERIOD can quickly find these two bugs and expose the buggy interleaving.

For using PERIOD, you need to perform the following step:

1. Compile the program on LLVM platform and get its bitcode.

2. Perform our static analysis scripts to analyze key points for further scheduling.

3. Import the information of key points to the environment variable Con_PATH and perform instrumentation on the .bc file.

4. Expose the bug through PERIOD's systematic testing.

5. Reproduce the buggy interleavings if found the bugs.

Compile the program on LLVM platform and get its bitcode, according to the following rules.

• Preferably use static linking

• Preferably use -g when compiling

• Preferably use -fno-omit-frame-pointer when compiling, but not required

For example:

$ cd $ROOT_DIR/test/work

$ ./cleanDIR.sh

$ clang -g -O0 -fno-omit-frame-pointer -emit-llvm -c ./work.c -o work.bc -lpthread

or use wllvm to get the bitcode.

$ wllvm -g -O0 -fno-omit-frame-pointer ./work.c -o work -lpthread

$ extract-bc ./work

(If you have any questions on WLLVM, you can see WLLVM's Documentation).

Perform our static analysis scripts to analyze key points for further scheduling.

Then use the script staticAnalysis.sh to perform the static analysis base on SVF. This will analyze key points for further scheduling (key points are the statements/expressions accessing shared memory locations or containing synchronization primitives):

$ROOT_DIR/tool/staticAnalysis/staticAnalysis.sh work

Then you can see the information of key points in the file ConConfig.work.

work.c:10

work.c:11

work.c:13

work.c:9

Import the information of key points to the environment variable Con_PATH, and use the wapper $ROOT_DIR/tool/staticAnalysis/DBDS-INSTRU/dbds-clang-fast++ to perform instrumentation on the .bc file (here can also add AddressSanitizer instrumentation).

export Con_PATH=$ROOT_DIR/test/work/ConConfig.work

$ROOT_DIR/tool/staticAnalysis/DBDS-INSTRU/dbds-clang-fast++ -g -O0 -fno-omit-frame-pointer -fsanitize=address ./work.bc -o work

Expose the bug through PERIOD's systematic testing.

execute the script $ROOT_DIR/tool/DBDS/run_PDS.py for PERIOD's CCT:

$ $ROOT_DIR/tool/DBDS/run_PDS.py -d 3 -l ./work

Reproduce the buggy interleavings if found the bugs.

As described above, use the command like the following to reproduce the memory leaks:

$ $ROOT_DIR/tool/DBDS/run_PDS.py -r out_work_1/Errors/000001_0000003_memory-leaks -l ./work

As described above, use the command like the following to reproduce the double-free:

$ $ROOT_DIR/tool/DBDS/run_PDS.py -r out_work_1/Errors/000004_0000010_double-free ./work

We have included all the benchmark programs used in our paper into an uploaded docker image, with our scripts for easy configuration.

The original dataset could be download from

- STCBench: https://github.com/mc-imperial/sctbench

- CVE benchmark: https://github.com/mryancai/ConVul

We used existing implementations of compared tools when available. Here are their websites to obtain the tool.

- Maple: https://github.com/jieyu/maple.

- IPB, IDB, DFS, PCT, Random are optimized and implemented in https://github.com/mc-imperial/sctbench.

- ConVul can be download on https://sites.google.com/site/detectconvul/.

- UFO can be download on https://github.com/parasol-aser/UFO.

- Data Race detector: TSAN, FastTrack, Helgrind+.