Incomplete fix of Issue #206 makes use-after-free still possible about lrzip

[pete4abw]

$ lrzip -t POC.lrz
Decompressing...
Inconsistent length after decompression. Got 0 bytes, expected 205600%  
Inconsistent length after decompression. Got 0 bytes, expected 2056     6:100%  
Inconsistent length after decompression. Got 0 bytes, expected 2056
Inconsistent length after decompression. Got 0 bytes, expected 2056
89932%  196952.00 /    219.00 
Average DeCompression Speed:  0.000MB/s
MD5 CHECK FAILED.
Stored:fc98427843f47beb2510386d42d7fb64
Output file:0428bb8c2dcc7f1abc10f714729caf4c
Fatal error - exiting

[bugbot97]

Hello @pete4abw, thank you for the quick reaction! I want to mention that this is a continuation of #206 (a concurrent UAF), so to stably reproduce the issue we need to follow the same procedure as in #206, that is:

1. Inject delays (e.g., sleep(1)) to two locations in the program (one in clear_rulist() - the free site, and another in zpaq_decompress_buf() - the use site, the details can be seen in #206 ) to make the vulnerable thread interleaving more likely to happen. Note that such delay injection simply intends to reproduce this concurrent UAF issue more stably - without this injection, the bug can still be triggered but maybe in an unstable way (e.g., once in every ten runs - there is randomness in thread schedule and interleaving as we know).

2. Compile the program and uncompress the POC with multiple threads (since this is a concurrent UAF), as done in #206:

./autogen.sh
CC=gcc CXX=g++ CFLAGS="-g -O0 -fsanitize=address" CXXFLAGS="-g -O0 -fsanitize=address" ./configure --enable-static-bin
make
./lrzip -t -p2 POC.lrz

Another potential obstacle is that you might see "fatal exit" due to "MD5 CHECK FAILED" (as also shown in your above log):

MD5 CHECK FAILED.
Stored:fc98427843f47beb2510386d42d7fb64
Output file:0428bb8c2dcc7f1abc10f714729caf4c
Fatal error - exiting

This "fatal exit" happens at this line, resulting in a program termination before runzip_fd() can return and clear_rulist() can be executed. But this error can be bypassed in the following ways;

Method 1. The "Stored" MD5 value is at the end of the input archive (i.e., POC.lrz), to avoid the MD5 check failure we can just replace the stored MD5 value to the "correct" value (Output file:0428bb8c2dcc7f1abc10f714729caf4c as shown above), this can be done with a hex editor like "xxd".

Actually I have already replaced the MD5 value when preparing POC.lrz, based on the Output file hash I observed on my machine (e.g., Stored:fc98427843f47beb2510386d42d7fb64), but I guess there may be some dynamics in the uncompression process, so that in your experiment the output file of POC.lrz uncompression is different than I had, resulting in a different MD5 value.

Method 2. Though I haven't tested it, I envision that we might also be able to turn off the MD5 check (e.g., NO_MD5 at this line), which is controlled by some flags in the "control" structure.

Method 3. Alternatively, I also observed that fatal_return() in lrzip will only terminate the program (e.g., exit()) when control->library_mode is not set (see this line), otherwise it will simply return "-1" without terminating. If there are scenarios that library_mode is set (I guess when lrzip is used as an embedded library of another host program), all fatal_return() will become "return -1" and then runzip_fd() will return and trigger the clear_rulist().

Following the above procedures (I used Method 1 to avoid MD5 failure), I can reliably reproduce the concurrency UAF bug locally. After viewing your comments, I have also tried to re-run the same procedure on a different machine with the same POC.lrz (w/o even modifying the MD5 value), and triggered the UAF again. I attached the detailed command log below:

bugbot97@matrix:/data/lrzip$ ./lrzip -t -vvv -p2 POC.lrz
Threading is ENABLED. Number of CPUs detected: 2
Detected 67501146112 bytes ram
Compression level 7
Nice Value: 19
Show Progress
Max Verbose
Test file integrity
Temporary Directory set as: ./
Created temporary outfile ./lrzipout.0x3nRr
Detected lrzip version 0.6 file.
MD5 being used for integrity testing.
Decompressing...
Reading chunk_bytes at 24
Expected size: 219
Chunk byte width: 2
Reading eof flag at 25
EOF: 1
Reading expected chunksize at 26
Chunk size: 53248
Reading stream 0 header at 29
Reading stream 1 header at 36
Reading ucomp header at 43
Fill_buffer stream 0 c_len 26 u_len 65493 last_head 60
Starting thread 0 to decompress 26 bytes from stream 0
Thread 0 decompressed 65493 bytes from stream 0
Taking decompressed data from thread 0
Reading ucomp header at 43
Fill_buffer stream 1 c_len 26 u_len 65493 last_head 60
Starting thread 1 to decompress 26 bytes from stream 1
Reading ucomp header at 89
Thread 1 decompressed 65493 bytes from stream 1
Fill_buffer stream 1 c_len 2056 u_len 2056 last_head 2032
Starting thread 2 to decompress 2056 bytes from stream 1
Reading ucomp header at 2061
Fill_buffer stream 1 c_len 2056 u_len 2056 last_head 2056
Starting thread 3 to decompress 2056 bytes from stream 1
Taking decompressed data from thread 1
Closing stream at 4123, want to seek to 4234

Average DeCompression Speed:  0.000MB/s
MD5: fc98427843f47beb2510386d42d7fb64
=================================================================
==1516389==ERROR: AddressSanitizer: heap-use-after-free on address 0x6100000000a8 at pc 0x555555596332 bp 0x7ffff33fdd60 sp 0x7ffff33fdd50
(this part is the same ASAN report as I attached before)

IMHO the root cause of the issue seems quite clear from the code audit as described previously, I'm happy to provide more details and try my best to help fix the issue if you think it's necessary (I personally think we'd better fix the race condition to avoid this whole class of concurrency UAF issues). Thank you for your help!

[pete4abw]

@bugbot97 . If you spent as much time solving bugs instead of creating artificial ones, your efforts would be appreciated. You are injecting a bug into the program and causing it to abend. The program fails as it should when compiled and executed without mods. If you examine the verbose output, lrzip and lrzip-next both complain that data cannot be decompressed in parallel. I don't see the problem, and certainly would not entertain spending any time on one that is artificial.

Reading expected chunksize at 26
Chunk size: 53,248
Reading stream 0 header at 29
Reading stream 1 header at 36
Reading ucomp header at 43
Fill_buffer stream 0 c_len 26 u_len 65,493 last_head 60
Starting thread 0 to decompress 26 bytes from stream 0
Thread 0 decompressed 65,493 bytes from stream 0
Taking decompressed data from thread 0
Reading ucomp header at 43
Fill_buffer stream 1 c_len 26 u_len 65,493 last_head 60
Starting thread 1 to decompress 26 bytes from stream 1
Reading ucomp header at 89
Fill_buffer stream 1 c_len 2,056 u_len 2,056 last_head 2,032
Starting thread 2 to decompress 2,056 bytes from stream 1
Thread 1 decompressed 65,493 bytes from stream 1
Reading ucomp header at 2,061
Fill_buffer stream 1 c_len 2,056 u_len 2,056 last_head 2,056
Starting thread 3 to decompress 2,056 bytes from stream 1
Reading ucomp header at 2,085
Fill_buffer stream 1 c_len 2,056 u_len 2,056 last_head 2,072
Inconsistent length after decompression. Got 0 bytes, expected 2,056
Unable to decompress in parallel, waiting for previous thread to complete before trying again
Starting thread 4 to decompress 2,056 bytes from stream 1
Reading ucomp header at 2,101
Fill_buffer stream 1 c_len 2,056 u_len 2,056 last_head 0
Starting thread 5 to decompress 2,056 bytes from stream 1
Taking decompressed data from thread 1
Inconsistent length after decompression. Got 0 bytes, expected 2,056
Unable to decompress in parallel, waiting for previous thread to complete before trying again
Inconsistent length after decompression. Got 0 bytes, expected 2,056
Unable to decompress in parallel, waiting for previous thread to complete before trying again
Inconsistent length after decompression. Got 0 bytes, expected 2,056
Unable to decompress in parallel, waiting for previous thread to complete before trying again

Closing stream at 4,163, want to seek to 8,360
Average DeCompression Speed: 0.000MB/s
MD5 CHECK FAILED.
Stored: fc98427843f47beb2510386d42d7fb64
Decompressed hash: 0428bb8c2dcc7f1abc10f714729caf4c
Corrupt Decompression.
Fatal error - exiting

[bugbot97]

Hello @pete4abw , I want to stress again that I have not "artificially" injected any bugs during the whole process. As explained before, the injected delays (i.e., sleep(1)) merely intend to help reproduce the bug more efficiently, and delay injection is an extremely widely used approach to detect concurrency bugs. Please consider the fact that during its execution, one thread could be preempted at any time and paused for an uncertain amount of time, creating many different possible thread interleavings - some of which could trigger bugs (e.g., even we do not inject any delays, the thread could be preempted and paused for 1s before the said two locations - it's just that this may not happen every time, for example in your above run).

The delay injection is just a method to reliably reproduce a specific bug-triggering thread interleaving (otherwise we may need to try many times to hit a specific thread interleaving to trigger a bug). In other words, given the popularity of lrzip, there are so many users using it on different machines every day, it's almost for sure that they will encounter all different kinds of thread interleaving, including those ones that can trigger the UAF bug as mentioned before. Yes, in your above experiment the UAF is not triggered (because the execution happens to not hit the required thread interleaving, which is also why there are error messages like "Unable to decompress in parallel"), but it doesn't mean that other executions of lrzip will not trigger the bug by running into a different thread interleaving. Shouldn't a widely-used utility like lrzip be error-proof for all possible thread interleaving that users may encounter?

I'm also trying to solving bugs, but before solving any bugs, the first step is to understand the bugs and confirm with you, right? I spent much time in understanding the nature of these issues, which is unfortunately accused by you of "creating artificial bugs". But I still think that the bug is there, harmful thread interleavings are not fundamentally prevented by design in lrzip, and the UAF (or other concurrency issues) will eventually happen. I also tried to propose a potential fix in the first post (e.g., introduce pthread_join() in clear_rulist()), but as mentioned, before being able to solve bugs, the bug itself is questioned.