Detected Bugs and Case Studies
We also apply PERIOD to a good number of widely-used real-world programs. With PERIOD, we have discovered 5 previously unknown concurrency bugs. These concurrency bugs were not previously reported and we informed the maintainers.
As listed below, our newly detected concurrency bugs include a use-after-free in lrzip, buffer-overflow in pbzip2, invalid-address-dereference in ctrace, etc.
Jump to bugs:
1. Use-after-free in lrzip v0.641
There would be concurrency use-after-free bugs between zpaq_decompress_buf() function and clear_rulist() function, in the master branch 465afe8.
Bug report: https://github.com/ckolivas/lrzip/issues/206
Brief Explanation
The related code simplified from stream.c and runzip.c are shown as follow:
// Thread T0 | // Thread T1
// in clear_rulist() in runzip.c | // in zpaq_decompress_buf() in steam.c
... | ...
struct runzip_node *node = control->ruhead; | if (unlikely(dlen != ucthread->u_len)) {
struct stream_info *sinfo = node->sinfo; | ret = -1;
| } else
dealloc(sinfo->ucthreads); | dealloc(c_buf);
dealloc(sinfo); | out:
| if (ret == -1) {
| dealloc(ucthread->s_buf);
| ucthread->s_buf = c_buf;
| }
Both thread T0 and thread T1 operate on a shared variable ucthread (i.e., T0 dealloc the a ucthread through dealloc(sinfo->ucthreads);, and T1 use the ucthread in all statements if (unlikely(dlen != ucthread->u_len)), dealloc(ucthread->s_buf);, and ucthread->s_buf = c_buf;).
However, a use-after-free can occur if the deallocation of ucthread before the use of ucthread.
For example, the following three thread interleaving can trigger three different UAFs:
*Interleaving (a)*
// Thread T0 | // Thread T1
|
... |
struct runzip_node *node = control->ruhead; |
struct stream_info *sinfo = node->sinfo; |
|
dealloc(sinfo->ucthreads); |
dealloc(sinfo); |
----------------------------------------------------------------------------------------------------
| ...
| if (unlikely(dlen != ucthread->u_len)) { // UAF here
| ret = -1;
| } else
| dealloc(c_buf);
| out:
| if (ret == -1) {
| dealloc(ucthread->s_buf);
| ucthread->s_buf = c_buf;
| }
*Interleaving (b)*
// Thread T0 | // Thread T1
|
| ...
| if (unlikely(dlen != ucthread->u_len)) {
| ret = -1;
| } else
| dealloc(c_buf);
| out:
| if (ret == -1) {
----------------------------------------------------------------------------------------------------
... |
struct runzip_node *node = control->ruhead; |
struct stream_info *sinfo = node->sinfo; |
|
dealloc(sinfo->ucthreads); |
dealloc(sinfo); |
----------------------------------------------------------------------------------------------------
| dealloc(ucthread->s_buf); // UAF occur here
| ucthread->s_buf = c_buf;
| }
*Interleaving (c)*
// Thread T0 | // Thread T1
|
| ...
| if (unlikely(dlen != ucthread->u_len)) {
| ret = -1;
| } else
| dealloc(c_buf);
| out:
| if (ret == -1) {
| dealloc(ucthread->s_buf);
----------------------------------------------------------------------------------------------------
... |
struct runzip_node *node = control->ruhead; |
struct stream_info *sinfo = node->sinfo; |
|
dealloc(sinfo->ucthreads); |
dealloc(sinfo); |
----------------------------------------------------------------------------------------------------
| ucthread->s_buf = c_buf; // UAF occur here
| }
Reproduce through delay injection
First, download the source code from the Git repo.
$ git clone https://github.com/ckolivas/lrzip.git
$ cd lrzip
$ git checkout 465afe8
To reproduce those use-after-free errors, we can insert two delays (e.g., sleep(1)) into the original source code.
For example, to reproduce interleaving (a) as mentioned earlier, you can insert a delay before dealloc(sinfo->ucthreads); statement in function in steam.c, and also a delay after, as shown as follows.
// In runzip.c, insert a delay after `dealloc(sinfo->ucthreads);`
static void clear_rulist(rzip_control *control)
{
while (control->ruhead) {
struct runzip_node *node = control->ruhead;
struct stream_info *sinfo = node->sinfo;
dealloc(sinfo->ucthreads);
sleep(1); // delay here !!!!!!!!!!
dealloc(node->pthreads);
dealloc(sinfo->s);
dealloc(sinfo);
control->ruhead = node->prev;
dealloc(node);
}
}
// In steam.c, insert a delay after `dealloc(sinfo->ucthreads);`
static int zpaq_decompress_buf(rzip_control *control __UNUSED__, struct uncomp_thread *ucthread, long thread)
{
...
zpaq_decompress(ucthread->s_buf, &dlen, c_buf, ucthread->c_len,
control->msgout, SHOW_PROGRESS ? true: false, thread);
sleep(1); // delay here !!!!!!!!!!
if (unlikely(dlen != ucthread->u_len)) {
print_err("Inconsistent length after decompression. Got %ld bytes, expected %lld\n", dlen, ucthread->u_len);
ret = -1;
} else
dealloc(c_buf);
...
}
compile the program:
$ CC=gcc CXX=g++ CFLAGS="-g -O0 -fsanitize=address" CXXFLAGS="-g -O0 -fsanitize=address" ./configure --enable-static-bin
$ make
Download the testcase (I upload the POC here, please unzip first).
Run with the testcase with the following command:
./lrzip -t -p2 POC
Then, you will see the use-after-free bug report. Here is the trace reported by ASAN:
=================================================================
==33325==ERROR: AddressSanitizer: heap-use-after-free on address 0x61d0000000e8 at pc 0x000000512b00 bp 0x7f9a30bfdb10 sp 0x7f9a30bfdb08
READ of size 8 at 0x61d0000000e8 thread T3
#0 0x512aff in zpaq_decompress_buf /workdir/lrzip/stream.c:449:6
#1 0x510381 in ucompthread /workdir/lrzip/stream.c:1554:11
#2 0x7f9a3541b6da in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x76da)
#3 0x7f9a3479771e in clone (/lib/x86_64-linux-gnu/libc.so.6+0x12171e)
0x61d0000000e8 is located 104 bytes inside of 2400-byte region [0x61d000000080,0x61d0000009e0)
freed by thread T0 here:
#0 0x494e1d in free /home/brian/src/final/llvm-project/compiler-rt/lib/asan/asan_malloc_linux.cpp:123:3
#1 0x4faa0d in clear_rulist /workdir/lrzip/runzip.c:255:3
#2 0x4f7ab2 in runzip_chunk /workdir/lrzip/runzip.c:384:2
#3 0x4f4aae in runzip_fd /workdir/lrzip/runzip.c:404:7
#4 0x4d84ce in decompress_file /workdir/lrzip/lrzip.c:845:6
#5 0x4cb98b in main /workdir/lrzip/main.c:706:4
#6 0x7f9a34697bf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
previously allocated by thread T0 here:
#0 0x495212 in calloc /home/brian/src/final/llvm-project/compiler-rt/lib/asan/asan_malloc_linux.cpp:154:3
#1 0x5003e1 in open_stream_in /workdir/lrzip/stream.c:1084:33
#2 0x4f6fa5 in runzip_chunk /workdir/lrzip/runzip.c:322:7
#3 0x4f4aae in runzip_fd /workdir/lrzip/runzip.c:404:7
#4 0x4d84ce in decompress_file /workdir/lrzip/lrzip.c:845:6
#5 0x4cb98b in main /workdir/lrzip/main.c:706:4
#6 0x7f9a34697bf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
Thread T3 created by T0 here:
#0 0x47fe4a in pthread_create /home/brian/src/final/llvm-project/compiler-rt/lib/asan/asan_interceptors.cpp:214:3
#1 0x4fbbd0 in create_pthread /workdir/lrzip/stream.c:125:6
#2 0x507033 in fill_buffer /workdir/lrzip/stream.c:1713:6
#3 0x504184 in read_stream /workdir/lrzip/stream.c:1800:8
#4 0x4f9c88 in unzip_literal /workdir/lrzip/runzip.c:162:16
#5 0x4f731c in runzip_chunk /workdir/lrzip/runzip.c:338:9
#6 0x4f4aae in runzip_fd /workdir/lrzip/runzip.c:404:7
#7 0x4d84ce in decompress_file /workdir/lrzip/lrzip.c:845:6
#8 0x4cb98b in main /workdir/lrzip/main.c:706:4
#9 0x7f9a34697bf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
SUMMARY: AddressSanitizer: heap-use-after-free /workdir/lrzip/stream.c:449:6 in zpaq_decompress_buf
Shadow bytes around the buggy address:
0x0c3a7fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c3a7fff8000: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c3a7fff8010: fd fd fd fd fd fd fd fd fd fd fd fd fd[fd]fd fd
0x0c3a7fff8020: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3a7fff8030: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3a7fff8040: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3a7fff8050: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3a7fff8060: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==33325==ABORTING
Execute snapshot
2. Buffer-overflow in pbzip2 v1.0.5
There would be concurrency buffer-overflow bug between fileWriter() function and producer() function in v1.0.5.
Brief Explanation
The related code simplified from pbzip2.cpp are shown as follow:
// Thread T0 | // Thread T1
// in producer() in pbzip2.cpp | // in fileWriter() in pbzip2.cpp
... | ...
... | while ((currBlock < NumBlocks) || (allDone == 0)) {
... | if (OutputBuffer[currBlock].bufSize < 1) {
... | pthread_mutex_unlock(OutMutex);
allDone = 1; | continue;
return 0; | } else
| pthread_mutex_unlock(OutMutex);
|
| currBlock++;
| }
Both thread T0 and thread T1 operate on a shared variable allDone (i.e., T0 sets allDone = 1, and T1 compares allDone in while ((currBlock < NumBlocks) || (allDone == 0))).
However, a buffer-overflow can occur if the statements inside while ((currBlock < NumBlocks) || (allDone == 0)) before the allDone be set to 1.
For example, the following thread interleaving can trigger buffer-overflow:
// Thread T0 | // Thread T1
// in producer() in pbzip2.cpp | // in fileWriter() in pbzip2.cpp
... | ...
| while ((currBlock < NumBlocks) || (allDone == 0)) {
| if (OutputBuffer[currBlock].bufSize < 1) {
| pthread_mutex_unlock(OutMutex);
| continue;
| } else
| pthread_mutex_unlock(OutMutex);
|
| currBlock++;
| }
| while ((currBlock < NumBlocks) || (allDone == 0)) {
| if (OutputBuffer[currBlock].bufSize < 1) {
| pthread_mutex_unlock(OutMutex);
| continue;
| } else
| pthread_mutex_unlock(OutMutex);
|
| currBlock++;
| }
| ...
| ...
| while ((currBlock < NumBlocks) || (allDone == 0)) {
| if (OutputBuffer[currBlock].bufSize < 1) { // BOF occur
| pthread_mutex_unlock(OutMutex);
| continue;
| } else
| pthread_mutex_unlock(OutMutex);
|
| currBlock++;
| }
--------------------------------------------------------------------------------------
allDone = 1; |
return 0; |
|
Reproduce through delay injection
Download the source code from https://launchpad.net/pbzip2/1.0/1.0.5/+download/pbzip2-1.0.5.tar.gz
To reproduce this concurrency buffer-overflow error, we can insert two delays (e.g., sleep(1)) into the original source code.
For example, to reproduce interleaving as mentioned earlier, you can insert a delay before allDone = 1; statement in function in pbzip2.cpp, and also a delay after, as shown as follows.
// In pbzip2.cpp, insert a delay after `allDone = 1;`
1299 int producer(int hInfile, int blockSize, queue *fifo)
1300 {
... ...
1411 sleep(2); // delay here !!!!!!!!!!
1412 allDone = 1;
1413 return 0;
1414 }
We also need to modify the code noThread = 1 to noThread = 0, to make any testcase trigger the multi-threaded mode.
2665 if (fileSize > 0)
2666 {
2667 // calculate the # of blocks of data
2668 numBlocks = (fileSize + blockSize - 1) / blockSize;
2669 // Do not use threads for small files where we only have 1 block to process
2670 // or if we only have 1 CPU
2671 if ((numBlocks == 1) || (numCPU == 1))
2672 noThreads = 0; // the original code is noThreads = 1
2673 else
2674 noThreads = 0;
26756 }
Edit the Makefile and add -g -Wno-narrowing -fsanitize=address into CFLAGS
# Make file for parallel BZIP2
SHELL = /bin/sh
# Compiler to use
CC = g++
CFLAGS = -O2 -g -Wno-narrowing -fsanitize=address
...
Then compile the program:
$ make
Download the testcase (just a simple .tar file, please unzip first).
Run with the testcase with the following command:
./pbzip2 -k -f -p3 ./test.tar
Then, you will see the buffer-overflow bug report. Here is the trace reported by ASAN:
=================================================================
==1943==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000068 at pc 0x56232eac264d bp 0x7f06d27fbe30 sp 0x7f06d27fbe20
READ of size 4 at 0x602000000068 thread T4
#0 0x56232eac264c in fileWriter(void*) /mnt/e/pbzip2-1.0.5/pbzip2.cpp:809
#1 0x7f06d78ec608 in start_thread /build/glibc-eX1tMB/glibc-2.31/nptl/pthread_create.c:477
#2 0x7f06d7604292 in __clone (/lib/x86_64-linux-gnu/libc.so.6+0x122292)
0x602000000068 is located 8 bytes to the right of 16-byte region [0x602000000050,0x602000000060)
allocated by thread T0 here:
#0 0x7f06d7a15947 in operator new(unsigned long) (/lib/x86_64-linux-gnu/libasan.so.5+0x10f947)
#1 0x56232eac88e6 in __gnu_cxx::new_allocator<outBuff>::allocate(unsigned long, void const*) /usr/include/c++/9/ext/new_allocator.h:114
#2 0x56232eac88e6 in std::allocator_traits<std::allocator<outBuff> >::allocate(std::allocator<outBuff>&, unsigned long) /usr/include/c++/9/bits/alloc_traits.h:444
#3 0x56232eac88e6 in std::_Vector_base<outBuff, std::allocator<outBuff> >::_M_allocate(unsigned long) /usr/include/c++/9/bits/stl_vector.h:343
#4 0x56232eac88e6 in std::vector<outBuff, std::allocator<outBuff> >::_M_default_append(unsigned long) /usr/include/c++/9/bits/vector.tcc:635
Thread T4 created by T0 here:
#0 0x7f06d7940805 in pthread_create (/lib/x86_64-linux-gnu/libasan.so.5+0x3a805)
#1 0x56232eac11da in main /mnt/e/pbzip2-1.0.5/pbzip2.cpp:2812
SUMMARY: AddressSanitizer: heap-buffer-overflow /mnt/e/pbzip2-1.0.5/pbzip2.cpp:809 in fileWriter(void*)
Shadow bytes around the buggy address:
0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa 00 04 fa fa 00 04 fa fa 00 00 fa[fa]fa fa
0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==1943==ABORTING
3. Invalid-address-dereference in CTrace v1.2
There exists an invalid-address-dereference bug in trc_add_thread() function and also trc_thread() function in CTrace v1.2.
Brief Explanation
The related code simplified from trc_add_thread() function in ctrace.c are shown as follow:
// ctrace.c
#define THRDMAX 307 /* keep this prime - used in hashing fn */
#define HASH(a) a % THRDMAX
static tthread_t *_thread[THRDMAX]; /* trace thread hash lookup table */
int trc_add_thread(cchar_t *tname, tid_t id)
{
uint_t i;
if(id == 0)
id = pthread_self();
...
i = HASH((int)id); // the i could be negative, due to the return value of pthread_self()
...
t->next = _thread[i]; // invalid-addres-dereference occur if the value of i is negative
_thread[i] = t;
}
The sub-thread access _thread[i] through the hash id of pthread_self(). However, when a large integer is cast to int it becomes negative and results in a wild pointer being dereferenced.
Another invalid-address-dereference could occur in trc_thread() function. The situation is similar to trc_add_thread() function, as mentioned above. Here, we will not describe it in detail.
Reproduce
Download the source code from http://ctrace.sourceforge.net/ctrace-1.2.tar.gz
To reproduce this Invalid-address-dereference, first compile the program with AddressSanitizer:
$ CC=clang CFLAGS="-g -O0 -fsanitize=address" make
Then compile the tests in test folder
$ cd test
$ CC=clang CFLAGS="-g -O0 -fsanitize=address" make
Run with the tests over and over again, as this bug only happens probabilistically without controlled scheduling:
./test
Then, you will see the SVGV bug report, demonstrating an invaild-address-dereference bug. Here is the trace reported by ASAN:
AddressSanitizer:DEADLYSIGNAL
=================================================================
==2256==ERROR: AddressSanitizer: SEGV on unknown address 0x0001801ac654 (pc 0x0000004c5786 bp 0x7ffceb17bef0 sp 0x7ffceb17be60 T0)
==2256==The signal is caused by a READ memory access.
#0 0x4c5786 in trc_add_thread /mnt/e/ctrace/src/ctrace.c:290:13
#1 0x4c3528 in main /mnt/e//ctrace/test/main.c:25:2
#2 0x7fb6f55210b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16
#3 0x41b3ad in _start (/mnt/e/ctrace/test/test+0x41b3ad)
AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /mnt/e/ctrace/src/ctrace.c:290:13 in trc_add_thread
==2256==ABORTING
Or you will see the global-buffer-overflow report, demonstrating an invaild-address-dereference bug. Here is the trace reported by ASAN:
=================================================================
==2258==ERROR: AddressSanitizer: global-buffer-overflow on address 0x000000da3728 at pc 0x0000004c5215 bp 0x7fff1abc9d10 sp 0x7fff1abc9d08
READ of size 8 at 0x000000da3728 thread T0
#0 0x4c5214 in trc_thread /mnt/e/FuzzingProject/ctrace/src/ctrace.c:224:8
#1 0x4c5549 in trc_add_thread /mnt/e/FuzzingProject/ctrace/src/ctrace.c:264:9
#2 0x4c3528 in main /mnt/e/FuzzingProject/ctrace/test/main.c:25:2
#3 0x7fa9b9bd00b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16
#4 0x41b3ad in _start (/mnt/e/FuzzingProject/ctrace/test/test+0x41b3ad)
0x000000da3728 is located 56 bytes to the left of global variable '_tlevel' defined in 'ctrace.c:20:17' (0xda3760) of size 4
0x000000da3728 is located 4 bytes to the right of global variable '_on' defined in 'ctrace.c:19:14' (0xda3720) of size 4
SUMMARY: AddressSanitizer: global-buffer-overflow /mnt/e/FuzzingProject/ctrace/src/ctrace.c:224:8 in trc_thread
Shadow bytes around the buggy address:
0x0000801ac690: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0000801ac6a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0000801ac6b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0000801ac6c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0000801ac6d0: 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
=>0x0000801ac6e0: f9 f9 f9 f9 04[f9]f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0000801ac6f0: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0000801ac700: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0000801ac710: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0000801ac720: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0000801ac730: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==2258==ABORTING
4. Race Condition in CTrace v1.2
There exists a data race on the shared variable tim in trc_trace() function, in CTrace v1.2.
Brief Explanation
The related code simplified from trc_trace() function in ctrace.c are shown as follow:
// T0 | T1
void trc_trace(){ | void trc_trace(){
... | ...
time_t tim; | time_t tim;
char buf[64]; | char buf[64];
... | ...
time(&tim); | time(&tim);
timeptr = localtime(&tim); | timeptr = localtime(&tim); // race here !!!!!
strftime(buf, 64, "%D-%T", timeptr); | strftime(buf, 64, "%D-%T", timeptr);
} | }
Both thread T0 and thread T1 call the trc_trace() function, without being protected by a lock. . After executing time(&tim); the variable tim in T0 and tim in T1 will become alias. The value of tim could be written concurrently by the timeptr = localtime(&tim); statement, which will pass to the variable buf, leading data race.
Reproduce
Download the source code from http://ctrace.sourceforge.net/ctrace-1.2.tar.gz
To reproduce this data race, first compile the program with ThreadSanitizer:
$ CC=clang CFLAGS="-g -O0 -fsanitize=thread" make
Then compile the tests in test folder
$ cd test
$ CC=clang CFLAGS="-g -O0 -fsanitize=thread" make
Run with the tests over and over again, as this bug only happens probabilistically without controlled scheduling:
./test
Then, you will see the data race report. Here is the trace reported by TSAN:
==================
WARNING: ThreadSanitizer: data race (pid=2373)
Write of size 8 at 0x7b0400000000 by thread T2:
#0 free /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:707:3 (test+0x423818)
#1 tzset_internal /build/glibc-eX1tMB/glibc-2.31/time/tzset.c:401:3 (libc.so.6+0xd51b1)
#2 trc_trace /mnt/e/FuzzingProject/ctrace/src/ctrace.c:787:12 (test+0x4b570e)
#3 thread2 /mnt/e/FuzzingProject/ctrace/test/main.c:79:2 (test+0x4b228c)
Previous write of size 8 at 0x7b0400000000 by main thread:
#0 malloc /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:651:5 (test+0x4231c4)
#1 strdup /build/glibc-eX1tMB/glibc-2.31/string/strdup.c:42:15 (libc.so.6+0xa250e)
#2 trc_trace /mnt/e/FuzzingProject/ctrace/src/ctrace.c:787:12 (test+0x4b570e)
#3 main /mnt/e/FuzzingProject/ctrace/test/main.c:42:2 (test+0x4b1c57)
Thread T2 (tid=2376, running) created by main thread at:
#0 pthread_create /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:962:3 (test+0x424a8b)
#1 main /mnt/e/FuzzingProject/ctrace/test/main.c:34:5 (test+0x4b1ba4)
SUMMARY: ThreadSanitizer: data race /build/glibc-eX1tMB/glibc-2.31/time/tzset.c:401:3 in tzset_internal
==================
==================
WARNING: ThreadSanitizer: data race (pid=2373)
Write of size 8 at 0x7f7c6a7f91c0 by thread T2:
#0 localtime /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/../sanitizer_common/sanitizer_common_interceptors.inc:1330:3 (test+0x431507)
#1 trc_trace /mnt/e/FuzzingProject/ctrace/src/ctrace.c:787:12 (test+0x4b570e)
#2 thread2 /mnt/e/FuzzingProject/ctrace/test/main.c:79:2 (test+0x4b228c)
Previous write of size 8 at 0x7f7c6a7f91c0 by main thread:
#0 localtime /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/../sanitizer_common/sanitizer_common_interceptors.inc:1330:3 (test+0x431507)
#1 trc_trace /mnt/e/FuzzingProject/ctrace/src/ctrace.c:787:12 (test+0x4b570e)
#2 main /mnt/e/FuzzingProject/ctrace/test/main.c:42:2 (test+0x4b1c57)
Location is global '??' at 0x7f7c6a608000 (libc.so.6+0x0000001f11c0)
Thread T2 (tid=2376, running) created by main thread at:
#0 pthread_create /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:962:3 (test+0x424a8b)
#1 main /mnt/e/FuzzingProject/ctrace/test/main.c:34:5 (test+0x4b1ba4)
SUMMARY: ThreadSanitizer: data race /mnt/e/FuzzingProject/ctrace/src/ctrace.c:787:12 in trc_trace
==================
5. Race Condition in Axel v2.17.10
There may exist a data race in the axel v2.17.10. Here is a brief explanation.
Brief Explanation
The sub-thread will call the setup_thread function to set up a connection. The function would write conn->last_transfer, and the access is protected by a lock pthread_mutex_lock(&conn->lock);. However, the main thread would read the value in the print_alternate_output_progress function without being protected by a lock, leading to a potential data race. The related code simplified from setup_thread() function in axel.c are shown as follow:
/* Thread used to set up a connection */
static void * setup_thread(void *c)
{
conn_t *conn = c;
int oldstate;
/* Allow this thread to be killed at any time. */
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, &oldstate);
pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, &oldstate);
pthread_mutex_lock(&conn->lock);
if (conn_setup(conn)) {
conn->last_transfer = axel_gettime(); // race here
if (conn_exec(conn)) {
conn->last_transfer = axel_gettime();
conn->enabled = true;
goto out;
}
}
// ...
}
The following is the function call by the main thread. It read the value from conn->last_transfer without protection by a lock. The value of conn->last_transfer could be written concurrently by sub-thread in setup_thread function, leading to a data race. The related code simplified from print_alternate_output_progress() function in text.c are shown as follow:
static void print_alternate_output_progress(axel_t *axel, char *progress, int width, off_t done, off_t total, double now)
{
//...
for (int i = 0; i < axel->conf->num_connections; i++) {
int offset = axel->conn[i].currentbyte * width / total;
if (axel->conn[i].currentbyte < axel->conn[i].lastbyte) {
if (now <= axel->conn[i].last_transfer + axel->conf->connection_timeout / 2) { // race here
progress[offset] = alt_id(i);
} else
progress[offset] = '#';
}
memset(progress + offset + 1, ' ',
max(0, axel->conn[i].lastbyte * width / total - offset - 1));
}
}
This data race could cause the real-time progress display to be inconsistent with the actual situation.
Reproduce
Download the axel source code from https://github.com/axel-download-accelerator/axel/releases/download/v2.17.10/axel-2.17.10.tar.gz.
Unzip the downloaded file, and compile the program with ThreadSanitizer.
$ tar xvf axel-2.17.10.tar.gz
$ cd axel-2.17.10
$ CC=clang CXX=clang++ CFLAGS="-g -O0 -fsanitize=thread" CXXFLAGS="-g -O0 -fsanitize=thread" ./configure
$ make
Run the program to download a file, for example:
./axel -n 4 -o test.pdf https://www.carolemieux.com/fairfuzz-ase18.pdf && rm test.pdf
Then, you will see the data race report. Here is the trace reported by TSAN:
==================
WARNING: ThreadSanitizer: data race (pid=8947)
Write of size 4 at 0x7bb000005204 by thread T2 (mutexes: write M2):
#0 setup_thread /workdir/axel-2.17.10/src/axel.c:835:24 (axel+0x4b6989)
Previous read of size 4 at 0x7bb000005204 by main thread:
#0 print_alternate_output_progress /workdir/axel-2.17.10/src/text.c:576:29 (axel+0x4c9108)
#1 print_alternate_output /workdir/axel-2.17.10/src/text.c:616:3 (axel+0x4c85da)
#2 main /workdir/axel-2.17.10/src/text.c:406:5 (axel+0x4c7be1)
Location is heap block of size 31608 at 0x7bb000000000 allocated by main thread:
#0 calloc /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:668:5 (axel+0x4237d0)
#1 axel_new /workdir/axel-2.17.10/src/axel.c:137:15 (axel+0x4b22f5)
#2 main /workdir/axel-2.17.10/src/text.c:312:10 (axel+0x4c71fb)
Mutex M2 (0x7bb000005228) created at:
#0 pthread_mutex_init /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:1220:3 (axel+0x42639d)
#1 axel_new /workdir/axel-2.17.10/src/axel.c:142:3 (axel+0x4b242f)
#2 main /workdir/axel-2.17.10/src/text.c:312:10 (axel+0x4c71fb)
Thread T2 (tid=8950, running) created by main thread at:
#0 pthread_create /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:962:3 (axel+0x424e1b)
#1 axel_start /workdir/axel-2.17.10/src/axel.c:472:8 (axel+0x4b6291)
#2 main /workdir/axel-2.17.10/src/text.c:380:2 (axel+0x4c7895)
SUMMARY: ThreadSanitizer: data race /workdir/axel-2.17.10/src/axel.c:835:24 in setup_thread
==================
==================
WARNING: ThreadSanitizer: data race (pid=8947)
Write of size 4 at 0x7bb000007b2c by thread T3 (mutexes: write M3):
#0 setup_thread /workdir/axel-2.17.10/src/axel.c:835:24 (axel+0x4b6989)
Previous read of size 4 at 0x7bb000007b2c by main thread:
#0 print_alternate_output_progress /workdir/axel-2.17.10/src/text.c:576:29 (axel+0x4c9108)
#1 print_alternate_output /workdir/axel-2.17.10/src/text.c:616:3 (axel+0x4c85da)
#2 main /workdir/axel-2.17.10/src/text.c:406:5 (axel+0x4c7be1)
Location is heap block of size 31608 at 0x7bb000000000 allocated by main thread:
#0 calloc /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:668:5 (axel+0x4237d0)
#1 axel_new /workdir/axel-2.17.10/src/axel.c:137:15 (axel+0x4b22f5)
#2 main /workdir/axel-2.17.10/src/text.c:312:10 (axel+0x4c71fb)
Mutex M3 (0x7bb000007b50) created at:
#0 pthread_mutex_init /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:1220:3 (axel+0x42639d)
#1 axel_new /workdir/axel-2.17.10/src/axel.c:142:3 (axel+0x4b242f)
#2 main /workdir/axel-2.17.10/src/text.c:312:10 (axel+0x4c71fb)
Thread T3 (tid=8951, running) created by main thread at:
#0 pthread_create /home/brian/src/final/llvm-project/compiler-rt/lib/tsan/rtl/tsan_interceptors_posix.cpp:962:3 (axel+0x424e1b)
#1 axel_start /workdir/axel-2.17.10/src/axel.c:472:8 (axel+0x4b6291)
#2 main /workdir/axel-2.17.10/src/text.c:380:2 (axel+0x4c7895)
SUMMARY: ThreadSanitizer: data race /workdir/axel-2.17.10/src/axel.c:835:24 in setup_thread
==================