[ICSE 2022] Controlled Concurrency Testing via Periodical Scheduling

(PERIOD is a controlled concurrency testing tool, where a scheduler explores the space of possible interleavings of a concurrent program looking for bugs)

Search-Based Concurrency Interleavings Exploration

MIT License

This is a testing framework for concurency programs.


The following pages show the technique report:

The following pages show the implementation details of key techniques:


The repository contains three folders: tool, test and evaluation.

Tool

We provide here a snapshot of ConFuzz. For simplicity, we provide shell script for the whole installation. Here, We recommend installing and running the tool under a Docker container. If you really want to install the tool in your developer environment, please see INSTALL.md

Requirements

  • Operating System: Ubuntu 18.04 LTS (This is very important, as our implementation requires higher kernel version)
  • 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).

Clone the Repository

$ git clone https://github.com/wcventure/ConcurrencyFuzzer.git ConFuzz --depth=1
$ cd ConFuzz

Build and Run the Docker Image

Firstly, system core dumps must be disabled as with AFL (you can skip this step sometimes. Keep going).

$ echo core|sudo tee /proc/sys/kernel/core_pattern
$ echo performance|sudo tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor

Run the following command to automatically build the docker image and configure the environment.

# build docker image
$ sudo docker build -t confuzzer --no-cache ./

# run docker image
$ sudo docker run --privileged -it confuzzer /bin/bash

If you want to build local souce, please read the instruction in Dockerfile.

Test

Before you use UAFL fuzzer, we suggest that you first use those simple examples provided by us to confirm whether the tool can work normally. In the following, we use the examples in the test folder to explain how to use the tool.

Test with AddressSanitizer

AddressSanitizer (aka ASan) is a memory error detector for C/C++. DBDS can be performed with AddressSanitizer.

AddressSanitizer requires to add -fsanitize=address into CFLAGS or CXXFLAGS, we provide a llvm wapper. Take df.c, which contains a simple double-free, as an example.

Before you start, you will have to have clang and llvm ready; use pip3 to have the numpy module install. In addition, please download and install the C++ Boost library; therefore you can compile and get the dbds-clang-fast instrumentation tool under the tool/staticAnalysis/DBDS-INSTRU directory.

# setup the environment variables in the root directory of the tool
$ source tool/init_env.sh

# compile the program and get bit code
$ cd $ROOT_DIR/test/doubleFree/
$ ./cleanDIR.sh
$ clang -g -emit-llvm -c ./df.c -o df.bc

# perform static analysis
$ $ROOT_DIR/tool/staticAnalysis/staticAnalysis.sh df

# complie the instrumented program with ASAN
$ export Con_PATH=$ROOT_DIR/test/doubleFree/ConConfig.df
$ $ROOT_DIR/tool/staticAnalysis/DBDS-INSTRU/dbds-clang-fast -g -fsanitize=address -c ./df.c -o df.o
$ clang++ ./df.o $ROOT_DIR/tool/staticAnalysis/DBDS-INSTRU/DBDSFunction.o -g -o df -lpthread -fsanitize=address -ldl

# perform DBDS
$ $ROOT_DIR/tool/DBDS/run_PDS.py ./df

Reproduce the Interleaving under a Certain Interleaving

After exectue run_PDS.py, it first perform dry run. Then we need to press Enter to continue. Finally, the results should look like following.

Start Testing!
test 0001: [0, 0, 1, 1]
test 0002: [0, 1, 0, 1]
        [Error Found]: NO.1 double-free
        The interleavings saved in out_df_1/Errors/000001
test 0003: [0, 1, 1, 0]
        [Error Found]: NO.2 double-free
        The interleavings saved in out_df_1/Errors/000002
test 0004: [1, 0, 0, 1]
        [Error Found]: NO.3 double-free
        The interleavings saved in out_df_1/Errors/000003
test 0005: [1, 0, 1, 0]
        [Error Found]: NO.4 double-free
        The interleavings saved in out_df_1/Errors/000004
test 0006: [1, 1, 0, 0]
End Testing!


Total Error Interleavings: 4
Total Timeouts Interleavings: 0
2 status found:
         [0, -6]
0 results found:
--------------------------------------------------
        Last New Find           Total
Round   0                       6
Time    00:00:00.00000          00:00:01.76925

From the result, we have found three interleavings that can lead to errors. The interleaving is saved in the folder out_df_*. If you want to reproduce a certain interleaving that saved in the folder out_df_*, you can perfrom the following command.

$ROOT_DIR/tool/DBDS/run_PDS.py -r out_df_1/Errors/000001 ./df

This command will execute the target program with interleaving [0, 0, 1, 1]. Actually, it can trigger a double-free bug.

=================================================================
==67534==ERROR: AddressSanitizer: attempting double-free on 0x602000000010 in thread T2:
    #0 0x4936fd  (/ConFuzz/test/doubleFree/df+0x4936fd)
    #1 0x4c5aa1  (/ConFuzz/test/doubleFree/df+0x4c5aa1)
    #2 0x7f586093e6b9  (/lib/x86_64-linux-gnu/libpthread.so.0+0x76b9)
    #3 0x7f585f9c74dc  (/lib/x86_64-linux-gnu/libc.so.6+0x1074dc)

0x602000000010 is located 0 bytes inside of 7-byte region [0x602000000010,0x602000000017)
freed by thread T1 here:
    #0 0x4936fd  (/ConFuzz/test/doubleFree/df+0x4936fd)
    #1 0x4c5a01  (/ConFuzz/test/doubleFree/df+0x4c5a01)

previously allocated by thread T0 here:
    #0 0x49397d  (/ConFuzz/test/doubleFree/df+0x49397d)
    #1 0x4c5baf  (/ConFuzz/test/doubleFree/df+0x4c5baf)
    #2 0x7f585f8e083f  (/lib/x86_64-linux-gnu/libc.so.6+0x2083f)

Thread T2 created by T0 here:
    #0 0x47e10a  (/ConFuzz/test/doubleFree/df+0x47e10a)
    #1 0x4c5c39  (/ConFuzz/test/doubleFree/df+0x4c5c39)
    #2 0x7f585f8e083f  (/lib/x86_64-linux-gnu/libc.so.6+0x2083f)
NULL 1

Thread T1 created by T0 here:
    #0 0x47e10a  (/ConFuzz/test/doubleFree/df+0x47e10a)
    #1 0x4c5c16  (/ConFuzz/test/doubleFree/df+0x4c5c16)
    #2 0x7f585f8e083f  (/lib/x86_64-linux-gnu/libc.so.6+0x2083f)

SUMMARY: AddressSanitizer: double-free (/ConFuzz/test/doubleFree/df+0x4936fd)
==67534==ABORTING

Test without AddressSanitizer

Before you use the tool, we suggest that you first use a simple example (increase_double.c) provided by us to determine whether the tool can work normally.

Please try to perform following command:

# setup the environment variables in the root directory of the tool
$ source tool/init_env.sh

# compile the program and get bit code
$ cd $ROOT_DIR/test/increase_double
$ ./cleanDIR.sh
$ clang++ -g -emit-llvm -c ./increase_double.cpp -o increase_double.bc

# perform static analysis
$ $ROOT_DIR/tool/staticAnalysis/staticAnalysis.sh increase_double

# complie the instrumented program
$ export Con_PATH=$ROOT_DIR/test/increase_double/ConConfig.increase_double
$ $ROOT_DIR/tool/staticAnalysis/DBDS-INSTRU/dbds-clang-fast++ -g ./increase_double.cpp -o increase_double

# perform PDS
$ $ROOT_DIR/tool/DBDS/run_PDS.py ./increase_double

Then you will see that we find all ten different results.

Test with ThreadSanitizer

ThreadSanitizer (aka TSan) is a fast data race detector for C/C++ and Go. DBDS can be performed with ThreadSanitizer.

ThreadSanitizer requires to add -fsanitize=thread -fPIE -pie into CFLAGS or CXXFLAGS, we provide a llvm wapper. Take increase_double.c, which contains a simple double-free, as an example.

# setup the environment variables in the root directory of the tool
$ source tool/init_env.sh

# compile the program and get bit code
$ cd $ROOT_DIR/test/increase_double
$ ./cleanDIR.sh
$ clang++ -g -emit-llvm -c ./increase_double.cpp -o increase_double.bc

# perform static analysis
$ $ROOT_DIR/tool/staticAnalysis/staticAnalysis.sh increase_double

# complie the instrumented program with ASAN
$ export Con_PATH=$ROOT_DIR/test/increase_double/ConConfig.increase_double
$ $ROOT_DIR/tool/staticAnalysis/DBDS-INSTRU/dbds-clang-fast++ -g -fsanitize=thread -fPIE -pie ./increase_double.cpp -o increase_double

# perform DBDS
$ $ROOT_DIR/tool/DBDS/run_PDS.py ./increase_double

Evaluation

The folder evaluation contains all our evaluation subjects. After having the tool installed, you can run the script to build and instrument the subjects. After instrument the subjects you can run the script to perform testing on the subjects.

ConVul-CVE-Benchmarks

The benchmarks for paper "Detecting Concurrency Memory Corruption Vulnerabilities, ESEC/FSE 2019." are available in this repository. It contains a set of concurrency vulnerabilities, including: UAF (Use After Free), NPD (Null Pointer Dereference), and DF (Double Free).

In evaluation/ConVul-CVE-Benchmarks folder, You can run the script ./build_all.sh to automatically compile the programs in this benchmark:

# setup the environment variables in the root directory of the tool
$ source tool/init_env.sh

# complie all ConVul-CVE-Benchmarks programs 
$ cd $ROOT_DIR/evaluation/ConVul-CVE-Benchmarks
$ ./build_all.sh

For the test command for each CVE, refers to:

Result: the Table shows the results of the all tools on 10 concurrency vulnerabilities. Our tool successfully detected all 10 vulnerabilites.

CVE ID Category Program Our Tool ConVul FT HEL TSAN UFO UFONPD
CVE-2009-3547 NDP Linux-2.6.32-rc6 -
CVE-2011-2183 NDP Linux-2.6.39-3 -
CVE-2013-1792 NDP Linux-2.8.3 -
CVE-2015-7550 NDP Linux-4.3.4 -
CVE-2016-1972 UAF Firefox-45.0 -
CVE-2016-1973 UAF Firefox-45.0 -
CVE-2016-7911 NDP Linux-4.6.6 -
CVE-2016-9806 DF Linux-4.6.3 - -
CVE-2017-6346 UAF(DF) Linux-4.9.13 -
CVE-2017-15265 UAF Linux-4.13.8 -
Total 10 9 1 1 2 1 2

Remark: In some CVE programs, DBDS also identified other types of bugs.

  • CVE-2016-1972 program contains both UAF and NDP bug.
  • CVE-2016-1973 program contains both UAF and NDP bug.
  • CVE-2017-6346 program contains UAF, DF and NDP bug.

Links

Website: https://sites.google.com/view/ConcurrencyFuzzer

GitHub: https://github.com/wcventure/ConcurrencyFuzzer

Owner
Cheng Wen
I am a Ph.D. student at Shenzhen University. My research interest is in the area of Cyber Security(SEC), Programming Language(PL), and Software Engineering(SE).
Cheng Wen
Similar Resources

The final project for the Udacity C++ Nanodegree Concurrency course

The final project for the Udacity C++ Nanodegree Concurrency course

CPPND: Program a Concurrent Traffic Simulation This is the project for the fourth course in the Udacity C++ Nanodegree Program: Concurrency. Throughou

Oct 15, 2021

Material para clase y entregas para la materia "Sistemas Operativos", impartida por Gunnar Wolf, en la Facultad de Ingeniería, UNAM, semestre 2022-1

sistop-2022-1 • Sistemas Operativos ¡Bienvenido! Este repositorio es el espacio de entrega de proyectos para la clase impartida por Gunnar Wolf de Sis

Jan 31, 2022

© 2022 Twitter Early Career Engineering Coding Challenge

© 2022 Twitter Early Career Engineering Coding Challenge

2022 Twitter Early Career Engineering Coding Challenge This is a timed test. Please make sure you are not interrupted during the test, as the timer ca

Oct 24, 2022

Esercizi del corso di Laboratorio di Calcolo 1 (A.A. 2021/2022)

LabCalc1 Esercizi del corso di Laboratorio di Calcolo 1 (A.A. 2021/2022) In questa repository sono presenti tutti gli esercizi proposti dal prof. Cris

Jan 3, 2022

Bypass it, you won't be Banned when playing cheats 2022

CFX-Bypass What's the purpose of this? Program blocks the outbounding and inbounding calls from adhesive so they won't get to check your hwid from the

Jan 3, 2023

CS202 (2022 Winter) Project: Interacting with "emulated" hardware accelerators

CS202 (2022 Winter) Project: Interacting with "emulated" hardware accelerators Overview Hardware accelerators that implement specialized circuits for

Nov 19, 2022

This repo contains demo exploits for CVE-2022-0185. There are two versions here.

CVE-2022-0185 This repo contains demo exploits for CVE-2022-0185. There are two versions here. The non-kctf version (fuse version) specifically target

Dec 24, 2022

It's a simple and free x86_64 architecture operating system created by one person, GoofOS started since 2022

This project is while developing... GoofOS GoofOS is a text operating system for x86 computers. About This is a 32 bit x86_64 graphical operating syst

May 1, 2022

A demonstration PoC for CVE-2022-21877 (storage spaces controller memory leak)

A demonstration PoC for CVE-2022-21877 (storage spaces controller memory leak)

POC CVE-2022-21877 This repository contains a POC for the CVE-2022-21877, found by Quang Linh, working at STAR Labs. This is an information leak found

Mar 8, 2022
Comments
  • Segmentation fault during the instrumentation with 'Combine redundant instructions'

    Segmentation fault during the instrumentation with 'Combine redundant instructions'

    Hi, there.

    There is a segmentation fault raised when instrumenting the result from SVF.

    I notice that there is a modification in your code already tackling this issue. Is there any further modification for this problem?https://github.com/wcventure/PERIOD/blob/7636dc7cd8c97ea2fb7c13d6d068efc3872b9d03/tool/staticAnalysis/DBDS-INSTRU/llvm-mode/dbds-llvm-pass.so.cc#L407

  • Static analysis error when handling FFmpeg

    Static analysis error when handling FFmpeg

    Hi, there.

    Period is an inspiring work. Unfortunately, when we are running the experiment for FFmpeg, we find there is error in the static analysis framework.

    To reproduce this error, run:

    $ROOT_DIR/tool/staticAnalysis.sh ffmpeg
    

    Here is the error message:

    opt: prototype/PERIOD/clang+llvm/include/llvm/Support/Casting.h:105: static bool llvm::isa_impl_cl<llvm::Instruction, const llvm::Value *>::doit(const From *) [To = llvm::Instruction, From = const llvm::Value *]: Assertion `Val && "isa<> used on a null pointer"' failed.
    Stack dump:
    0.	Program arguments: opt -load prototype/PERIOD/tool/staticAnalysis/LLVM-PASS/SensitiveOperationsPass/libSensitiveOperationsPass.so -so ./ffmpeg.bc -o /dev/null 
    1.	Running pass 'SensitiveOperations Instrumentation' on module './ffmpeg.bc'.
     #0 0x0000000001f11504 PrintStackTraceSignalHandler(void*) (prototype/PERIOD/clang+llvm/bin/opt+0x1f11504)
     #1 0x0000000001f0f2ee llvm::sys::RunSignalHandlers() (prototype/PERIOD/clang+llvm/bin/opt+0x1f0f2ee)
     #2 0x0000000001f118f5 SignalHandler(int) (prototype/PERIOD/clang+llvm/bin/opt+0x1f118f5)
     #3 0x00007f6df0cc1420 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x14420)
     #4 0x00007f6df077200b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4300b)
     #5 0x00007f6df0751859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22859)
     #6 0x00007f6df0751729 (/lib/x86_64-linux-gnu/libc.so.6+0x22729)
     #7 0x00007f6df0762fd6 (/lib/x86_64-linux-gnu/libc.so.6+0x33fd6)
     #8 0x00007f6df0722ee0 void std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_construct<char const*>(char const*, char const*, std::forward_iterator_tag) /usr/lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/basic_string.tcc:212:4
     #9 0x00007f6df0722ee0 void std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_construct_aux<char const*>(char const*, char const*, std::__false_type) /usr/lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/basic_string.h:251:11
    #10 0x00007f6df0722ee0 void std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_construct<char const*>(char const*, char const*) /usr/lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/basic_string.h:270:4
    #11 0x00007f6df0722ee0 std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&) /usr/lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/basic_string.h:531:9
    #12 0x00007f6df0722ee0 (anonymous namespace)::SensitiveOperations::runOnModule(llvm::Module&) prototype/PERIOD/tool/staticAnalysis/LLVM-PASS/SensitiveOperationsPass/SensitiveOperationsPass.cpp:580:52
    #13 0x00000000019528f8 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/prototype/PERIOD/clang+llvm/bin/opt+0x19528f8)
    #14 0x000000000074d9c8 main (/prototype/PERIOD/clang+llvm/bin/opt+0x74d9c8)
    #15 0x00007f6df0753083 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24083)
    #16 0x000000000073a1da _start (prototype/PERIOD/clang+llvm/bin/opt+0x73a1da)
    prototype/PERIOD/tool/staticAnalysis/staticAnalysis.sh: line 47: 823029 Aborted                 opt -load $ROOT_DIR/tool/staticAnalysis/LLVM-PASS/SensitiveOperationsPass/libSensitiveOperationsPass.so -so ./$NAME.bc -o /dev/null > so.$NAME
    

    Here is the binary for analysis:

    ffmpeg.zip

A simple tool using PC mouse via USART to control MCU and LCD/OLED (with LVGL library), if your screen cannot be controlled by touch.
A simple tool using PC mouse via USART to control MCU and LCD/OLED (with LVGL library), if your screen cannot be controlled by touch.

LVGL_USB_Mouse A simple tool using PC mouse via USART to control MCU and LCD/OLED (with LVGL library), if your screen cannot be controlled by touch. 如

May 5, 2022
Operating system project - implementing scheduling algorithms and some system calls for XV6 OS

About XV6 xv6 is a modern reimplementation of Sixth Edition Unix in ANSI C for multiprocessor x86 and RISC-V systems.

Dec 22, 2022
Voltage Controlled Digital Core Multimode Oscillator using Mozzi library on Arduino

Arduino-VDCO Voltage Controlled Digital Core Multimode Oscillator using Mozzi library on Arduino Its a digital Oscillator/Voice for the Eurorack Stand

Dec 12, 2022
This is a simple sketch that can be controlled from the TEST_ARMACOM.vr mission

ARMA_LED This is a simple Arduino sketch that can be controlled from the TEST_ARMACOM.vr mission in ARMA 3 With this sketch, a connected Arduino's bui

Oct 27, 2021
arduino controlled led matrix pullover

Animated Xmas pullover With this project we will make an animated pullover for the Christmas season. Controlled by a 32x8 LED matrix and a wemos D1 mi

Nov 5, 2021
2.4 GHz LORA based telemetry and radio link for remote controlled vehicles

mLRS This is the mLRS project. The goal is an open source 2.4 GHz LORA-based high-performance long-range radio link, which provides fully transparent

Jan 4, 2023
Iot-Surveillance-Car - This is a IOT Based Surveillance Car which can be controlled, tracked globally as well as its data can be accessed globally

Iot-Surveillance-Car - This is a IOT Based Surveillance Car which can be controlled, tracked globally as well as its data can be accessed globally. The camera on the front of the car can also be monitored globally. It can go anywhere where sim connection is available. 5th Sem Mini project

Dec 3, 2022
ESP32-Skid-Steer - Bruder Catepillar Skid Steer model converted to RC, controlled by an ESP32 with 2 analog joysticks and a receiver that is an ESP32 on the model.
ESP32-Skid-Steer - Bruder Catepillar Skid Steer model converted to RC, controlled by an ESP32 with 2 analog joysticks and a receiver that is an ESP32 on the model.

ESP32-Skid-Steer Bruder Catepillar Skid Steer model converted to RC, controlled by an ESP32 with 2 analog joysticks and a receiver that is an ESP32 on

Oct 27, 2022
A small scheduler for scheduling jobs

A small scheduler for scheduling jobs

Jan 28, 2022
Arduino-controlled bed that helps in reducing rate of disease infection by detecting whether a person accessed the safe space of a subject who is infected
Arduino-controlled bed that helps in reducing rate of disease infection by detecting whether a person accessed the safe space of a subject who is infected

Infection Control Bed BACKGROUND Spread of COVID-19 occurs via airborne parricels and droplets. People who are infected with COVID an release particle

Mar 17, 2022