[ICSE 2022] Controlled Concurrency Testing via Periodical Scheduling

Overview

(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

Releases(v1.0)
  • v1.0(Jan 26, 2022)

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
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. 如

k_ying 5 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.

Amirhossein Rajabpour 20 May 19, 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

null 40 Jun 30, 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

Erik 1 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

null 1 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

null 40 Jul 27, 2022
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

Rahul Vijan 3 Jun 29, 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

null 5 Feb 4, 2022
A small scheduler for scheduling jobs

A small scheduler for scheduling jobs

Naira 2 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

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

Amir Hesham Ibrahim 3 Mar 17, 2022
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

Franz 2 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

UNAM Engineering 5 Jan 31, 2022
© 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

Ricky Chuang 7 Jun 17, 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

Lorenzo 7 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

Sarnax 35 Jul 30, 2022
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

Hung-Wei Tseng 4 Mar 21, 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

Crusaders of Rust CTF Team 328 Jul 19, 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

null 3 May 1, 2022
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

null 4 Mar 8, 2022