Heap Buffer Overflow in Preflate
andrew-epstein opened this issue · 10 comments
andrew-epstein commented
I'm not sure whether to report this bug here or against the preflate project, but I figure if you (@schnaader) aren't the right person to handle it, then @deus-libri will see it here regardless. The command-line invocation was:
precomp -intense ELS-Search-OBSOLETE.tar
I would provide the file I was trying to process, but it contains private code. It is a tar archive of a large git repository. I compiled with clang's address sanitizer and almost immediately upon starting to process a file, the process exits with the following error:
Compressing with LZMA, 8 threads, memory usage: 1320 MiB, block size: 24 MiB
0.00% lzma total/written/left: 0/0/0 MiB / =================================================================
==52362==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x61a000001153 at pc 0x0001004204fb bp 0x7fff5fa436b0 sp 0x7fff5fa436a8
READ of size 1 at 0x61a000001153 thread T0
#0 0x1004204fa in PreflateHashChainExt::updateHash(unsigned int) (precomp:x86_64+0x1002694fa)
#1 0x1003de2b7 in PreflateCompLevelEstimatorState::updateOrSkipHash(unsigned int) (precomp:x86_64+0x1002272b7)
#2 0x1003e0537 in PreflateCompLevelEstimatorState::checkDump(bool) (precomp:x86_64+0x100229537)
#3 0x1003e15f8 in estimatePreflateCompLevel(int, int, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&, bool) (precomp:x86_64+0x10022a5f8)
#4 0x100424944 in estimatePreflateParameters(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&) (precomp:x86_64+0x10026d944)
#5 0x1003e295b in PreflateDecoderTask::analyze() (precomp:x86_64+0x10022b95b)
#6 0x1003e606c in preflate_decode(OutputStream&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&, unsigned long long&, InputStream&, std::__1::function<void ()>, unsigned long, unsigned long) (precomp:x86_64+0x10022f06c)
#7 0x100523336 in try_recompression_deflate(__sFILE*) (precomp:x86_64+0x10036c336)
#8 0x10052740c in try_decompression_deflate_type(unsigned int&, unsigned int&, unsigned char, unsigned char const*, int, bool, char const*) (precomp:x86_64+0x10037040c)
#9 0x100527ff5 in try_decompression_zip(int) (precomp:x86_64+0x100370ff5)
#10 0x10050caa0 in compress_file(float, float) (precomp:x86_64+0x100355aa0)
#11 0x1005066c7 in main (precomp:x86_64+0x10034f6c7)
#12 0x7fff97ed45ac in start (libdyld.dylib:x86_64+0x35ac)
0x61a000001153 is located 0 bytes to the right of 1235-byte region [0x61a000000c80,0x61a000001153)
allocated by thread T0 here:
#0 0x1009040e2 in wrap__Znwm (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x680e2)
#1 0x1003f3a58 in std::__1::__libcpp_allocate(unsigned long, unsigned long) (precomp:x86_64+0x10023ca58)
#2 0x1003f62b9 in std::__1::allocator<unsigned char>::allocate(unsigned long, void const*) (precomp:x86_64+0x10023f2b9)
#3 0x1003f6010 in std::__1::allocator_traits<std::__1::allocator<unsigned char> >::allocate(std::__1::allocator<unsigned char>&, unsigned long) (precomp:x86_64+0x10023f010)
#4 0x1003f5bea in std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >::__vallocate(unsigned long) (precomp:x86_64+0x10023ebea)
#5 0x1003f5889 in std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >::vector(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) (precomp:x86_64+0x10023e889)
#6 0x1003e26bc in std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >::vector(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) (precomp:x86_64+0x10022b6bc)
#7 0x1003e24a6 in PreflateDecoderTask::PreflateDecoderTask(PreflateDecoderTask::Handler&, unsigned int, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> >&&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&&, unsigned long, bool, unsigned int) (precomp:x86_64+0x10022b4a6)
#8 0x1003e27d5 in PreflateDecoderTask::PreflateDecoderTask(PreflateDecoderTask::Handler&, unsigned int, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> >&&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&&, unsigned long, bool, unsigned int) (precomp:x86_64+0x10022b7d5)
#9 0x1003e6057 in preflate_decode(OutputStream&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&, unsigned long long&, InputStream&, std::__1::function<void ()>, unsigned long, unsigned long) (precomp:x86_64+0x10022f057)
#10 0x100523336 in try_recompression_deflate(__sFILE*) (precomp:x86_64+0x10036c336)
#11 0x10052740c in try_decompression_deflate_type(unsigned int&, unsigned int&, unsigned char, unsigned char const*, int, bool, char const*) (precomp:x86_64+0x10037040c)
#12 0x100527ff5 in try_decompression_zip(int) (precomp:x86_64+0x100370ff5)
#13 0x10050caa0 in compress_file(float, float) (precomp:x86_64+0x100355aa0)
#14 0x1005066c7 in main (precomp:x86_64+0x10034f6c7)
#15 0x7fff97ed45ac in start (libdyld.dylib:x86_64+0x35ac)
SUMMARY: AddressSanitizer: heap-buffer-overflow (precomp:x86_64+0x1002694fa) in PreflateHashChainExt::updateHash(unsigned int)
Shadow bytes around the buggy address:
0x1c34000001d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c34000001e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c34000001f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c3400000200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c3400000210: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x1c3400000220: 00 00 00 00 00 00 00 00 00 00[03]fa fa fa fa fa
0x1c3400000230: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c3400000240: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c3400000250: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c3400000260: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c3400000270: 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
==52362==ABORTING
Abort trap: 6
I am on OS X 10.11.6, and this is my version of clang:
clang version 8.0.0 (trunk 339561)
Target: x86_64-apple-darwin15.6.0
Thread model: posix
InstalledDir: /usr/local/bin
If I compile with the UndefinedBehavior sanitizer instead, the process also crashes, but not until later:
Compressing with LZMA, 8 threads, memory usage: 1320 MiB, block size: 24 MiB
0.00% lzma total/written/left: 0/0/0 MiB / /Users/epsteina/code/personal/precomp-cpp/contrib/preflate/preflate_decoder.cpp:147:88: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'
/Users/epsteina/code/personal/precomp-cpp/contrib/preflate/preflate_statistical_codec.cpp:96:37: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
/Users/epsteina/code/personal/precomp-cpp/contrib/preflate/preflate_statistical_codec.cpp:96:37: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
/Users/epsteina/code/personal/precomp-cpp/contrib/preflate/preflate_statistical_codec.cpp:96:37: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
/Users/epsteina/code/personal/precomp-cpp/contrib/preflate/preflate_statistical_codec.cpp:96:37: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
/Users/epsteina/code/personal/precomp-cpp/contrib/preflate/preflate_statistical_codec.cpp:96:37: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
0.15% lzma total/written/left: 24/15/9 MiB | /Users/epsteina/code/personal/precomp-cpp/contrib/packjpg/packjpg.cpp:3938:15: runtime error: shift exponent -1 is negative
/Users/epsteina/code/personal/precomp-cpp/contrib/packjpg/packjpg.cpp:3956:32: runtime error: shift exponent -1 is negative
0.60% lzma total/written/left: 94/65/29 MiB \ UndefinedBehaviorSanitizer:DEADLYSIGNAL
==95070==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address 0x00012e06f000 (pc 0x7fff9192df49 bp 0x7fff5aaba530 sp 0x7fff5aaba530 T149899120)
==95070==The signal is caused by a READ memory access.
#0 0x7fff9192df48 in _platform_memmove$VARIANT$Haswell (libsystem_platform.dylib:x86_64+0x4f48)
==95070==Register values:
rax = 0x000000012e02f020 rbx = 0x00000000000000ff rcx = 0x0000000000000020 rdx = 0x0000000000020800
rdi = 0x000000012e04f800 rsi = 0x000000012e06f000 rbp = 0x00007fff5aaba530 rsp = 0x00007fff5aaba530
r8 = 0x0000000000000001 r9 = 0x0000000000010301 r10 = 0x00000000000103fe r11 = 0xfffffffffffe0800
r12 = 0x0000000000000000 r13 = 0x0000000000000000 r14 = 0x0000000000000001 r15 = 0x0000000000000000
UndefinedBehaviorSanitizer can not provide additional info.
==95070==ABORTING
Abort trap: 6
I would be happy to provide additional details if they are required.
deus-libri commented
Hi Andrew,
the bug is definitely on my plate. My guess is, it is either some invalid or "unusual" deflate stream which isn't handled correctly, or my code has some undefined behaviour which clang tries to be clever about, while VS doesn't. Can you maybe bisect the tar file to find the offending deflate streams? Or try the switch -pfverify? It checks that a deflate stream can be recompressed successfully. If not, it dumps the offending deflate stream.
Without something to work with, fixing the issue might take a lot of time.
andrew-epstein commented
The error only seems to happen when using the -intense flag. I was able to reproduce the issue with a much smaller (and shareable) file, which was a tar archive of the precomp-cpp git repo itself. The output of both the sanitizers was much the same. If no sanitizer is enabled, the program exits with a segfault. Github won't let me upload a .tar file. I will try to reproduce the issue with a .zip or .gz file instead.
Running under valgrind indicates multiple invalid reads of size 1. I suspect an off by one error somewhere. I will dig into this a little more.
andrew-epstein commented
Okay, so I don't have a fix because I'm not sure exactly what the code is supposed to be doing, but I found (one of) the problem(s):
const unsigned char* b = _input.curChars();
unsigned pos = _input.pos();
if (pos - totalShift >= 0xfe08) {
reshift();
}
for (unsigned i = 0; i < l; ++i) {
updateRunningHash(b[2 + i]);
...
}This will attempt to read memory we don't own if 2 + i > _input.remaining().
deus-libri commented
Small correction: if 2 + i >= ...
The code is quite straightforward: it calculates a running hash whose value only depends on 3 continuous bytes each, and then updates a linked list for all entries with the same hash value. This is how classic zlib finds previous sequences that start with the same three bytes. (Minus the out-of-bounds access of course.)
Since the original goal of preflate was to perfectly model zlib generated deflate streams (as much as possible at least), I also had to reimplement the hash chains and other zlib quirks.
I guess the Windows (or VC CRT) memory allocator keeps the process memory nicely continuous, which is why I never encountered a page fault exception. I'm pretty sure that, for every stream, preflate was reading two bytes too much here.
For the moment, you can try
for (unsigned i = 2, n = std::min(2 + l, _input.remaining()); i < n; ++i) {
updateRunningHash(b[i]);
unsigned h = runningHash & hashMask;
unsigned p = (pos + i - 2) - totalShift;
chainDepth[p] = chainDepth[head[h]] + 1;
prev[p] = head[h];
head[h] = p;
}
andrew-epstein commented
This change allows my file to be compressed successfully if I don't enable any sanitizers. Address sanitizer still complains, however, as does valgrind. Here's the report from AddressSanitizer:
==19507==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x622000002c7d at pc 0x0001076f1057 bp 0x7fff587769c0 sp 0x7fff587769b8
READ of size 1 at 0x622000002c7d thread T0
#0 0x1076f1056 in PreflatePredictorState::prefixCompare(unsigned char const*, unsigned char const*, unsigned int, unsigned int) preflate_predictor_state.cpp:89
#1 0x1076f2c8b in PreflatePredictorState::match(unsigned int, unsigned int, unsigned int, bool, bool, unsigned int) preflate_predictor_state.cpp:169
#2 0x10776abdb in PreflateTokenPredictor::predictToken() preflate_token_predictor.cpp:74
#3 0x10776ddf2 in PreflateTokenPredictor::analyzeBlock(unsigned int, PreflateTokenBlock const&) preflate_token_predictor.cpp:200
#4 0x1076ae175 in PreflateDecoderTask::analyze() preflate_decoder.cpp:82
#5 0x1076b140c in preflate_decode(OutputStream&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&, unsigned long long&, InputStream&, std::__1::function<void ()>, unsigned long, unsigned long) preflate_decoder.cpp:225
#6 0x1077ee8d6 in try_recompression_deflate(__sFILE*) precomp.cpp:3119
#7 0x1077f29ac in try_decompression_deflate_type(unsigned int&, unsigned int&, unsigned char, unsigned char const*, int, bool, char const*) precomp.cpp:3480
#8 0x1077fbb1a in try_decompression_zlib(int) precomp.cpp:6977
#9 0x1077ddc09 in compress_file(float, float) precomp.cpp:4449
#10 0x1077d1c67 in main precomp.cpp:496
#11 0x7fff982805ac in start (libdyld.dylib:x86_64+0x35ac)
0x622000002c7d is located 0 bytes to the right of 4989-byte region [0x622000001900,0x622000002c7d)
allocated by thread T0 here:
#0 0x107d2d0e2 in wrap__Znwm (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x680e2)
#1 0x1076bedf8 in std::__1::__libcpp_allocate(unsigned long, unsigned long) new:252
#2 0x1076c1659 in std::__1::allocator<unsigned char>::allocate(unsigned long, void const*) memory:1799
#3 0x1076c13b0 in std::__1::allocator_traits<std::__1::allocator<unsigned char> >::allocate(std::__1::allocator<unsigned char>&, unsigned long) memory:1548
#4 0x1076c0f8a in std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >::__vallocate(unsigned long) vector:970
#5 0x1076c0c29 in std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >::vector(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) vector:1245
#6 0x1076ada5c in std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >::vector(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) vector:1238
#7 0x1076ad846 in PreflateDecoderTask::PreflateDecoderTask(PreflateDecoderTask::Handler&, unsigned int, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> >&&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&&, unsigned long, bool, unsigned int) preflate_decoder.cpp:70
#8 0x1076adb75 in PreflateDecoderTask::PreflateDecoderTask(PreflateDecoderTask::Handler&, unsigned int, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> >&&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&&, unsigned long, bool, unsigned int) preflate_decoder.cpp:73
#9 0x1076b13f7 in preflate_decode(OutputStream&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&, unsigned long long&, InputStream&, std::__1::function<void ()>, unsigned long, unsigned long) preflate_decoder.cpp:220
#10 0x1077ee8d6 in try_recompression_deflate(__sFILE*) precomp.cpp:3119
#11 0x1077f29ac in try_decompression_deflate_type(unsigned int&, unsigned int&, unsigned char, unsigned char const*, int, bool, char const*) precomp.cpp:3480
#12 0x1077fbb1a in try_decompression_zlib(int) precomp.cpp:6977
#13 0x1077ddc09 in compress_file(float, float) precomp.cpp:4449
#14 0x1077d1c67 in main precomp.cpp:496
I will update later with the report from Valgrind. Please note that I reformatted the code to make it easier for me to read, so the line numbers may not perfectly match up with your code. If this presents a problem, please let me know.
deus-libri commented
I'll work on a cleanup to get rid of this UB, but don't hold your breath.
andrew-epstein commented
Okay. Here's another one valgrind reports:
==45588== 5568 errors in context 19 of 20:
==45588== Invalid read of size 1
==45588== at 0x1009D0F49: _platform_memmove$VARIANT$Haswell (in /usr/lib/system/libsystem_platform.dylib)
==45588== by 0x10009BDA5: PreflateHashChainExt::reshift() (preflate_hash_chain.cpp:109)
==45588== by 0x10009BB36: PreflateHashChainExt::updateHash(unsigned int) (preflate_hash_chain.cpp:60)
==45588== by 0x10008311B: PreflateCompLevelEstimatorState::updateOrSkipHash(unsigned int) (preflate_complevel_estimator.cpp:72)
==45588== by 0x100083932: PreflateCompLevelEstimatorState::checkDump(bool) (preflate_complevel_estimator.cpp:170)
==45588== by 0x100083CB6: estimatePreflateCompLevel(int, int, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&, bool) (preflate_complevel_estimator.cpp:218)
==45588== by 0x10009C758: estimatePreflateParameters(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&) (preflate_parameter_estimator.cpp:74)
==45588== by 0x1000842C7: PreflateDecoderTask::analyze() (preflate_decoder.cpp:77)
==45588== by 0x1000856CA: preflate_decode(OutputStream&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&, unsigned long long&, InputStream&, std::__1::function<void ()>, unsigned long, unsigned long) (preflate_decoder.cpp:225)
==45588== by 0x1000F4DB4: try_recompression_deflate(__sFILE*) (precomp.cpp:3119)
==45588== by 0x1000F6949: try_decompression_deflate_type(unsigned int&, unsigned int&, unsigned char, unsigned char const*, int, bool, char const*) (precomp.cpp:3480)
==45588== by 0x1000FAADA: try_decompression_zlib(int) (precomp.cpp:6977)
==45588== Address 0x102961040 is 0 bytes after a block of size 262,144 alloc'd
==45588== at 0x1004B4681: malloc (in /usr/local/Cellar/valgrind/3.13.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==45588== by 0x1004F97DD: operator new(unsigned long) (in /usr/lib/libc++.1.dylib)
==45588== by 0x10009B873: PreflateHashChainExt::PreflateHashChainExt(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned char) (preflate_hash_chain.cpp:30)
==45588== by 0x10009B9E5: PreflateHashChainExt::PreflateHashChainExt(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned char) (preflate_hash_chain.cpp:24)
==45588== by 0x100082DBC: PreflateCompLevelEstimatorState::PreflateCompLevelEstimatorState(int, int, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&) (preflate_complevel_estimator.cpp:26)
==45588== by 0x100082FF8: PreflateCompLevelEstimatorState::PreflateCompLevelEstimatorState(int, int, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&) (preflate_complevel_estimator.cpp:33)
==45588== by 0x100083CA1: estimatePreflateCompLevel(int, int, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&, bool) (preflate_complevel_estimator.cpp:217)
==45588== by 0x10009C758: estimatePreflateParameters(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long, std::__1::vector<PreflateTokenBlock, std::__1::allocator<PreflateTokenBlock> > const&) (preflate_parameter_estimator.cpp:74)
==45588== by 0x1000842C7: PreflateDecoderTask::analyze() (preflate_decoder.cpp:77)
==45588== by 0x1000856CA: preflate_decode(OutputStream&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >&, unsigned long long&, InputStream&, std::__1::function<void ()>, unsigned long, unsigned long) (preflate_decoder.cpp:225)
==45588== by 0x1000F4DB4: try_recompression_deflate(__sFILE*) (precomp.cpp:3119)
==45588== by 0x1000F6949: try_decompression_deflate_type(unsigned int&, unsigned int&, unsigned char, unsigned char const*, int, bool, char const*) (precomp.cpp:3480)
Do you / @schnaader want this issue open or closed?
schnaader commented
I would keep it open for now. I recently got two files where crashes occured, this might be related to this UB, so I'll check and add it here or file another issue for them. After that, I'll close this issue.
schnaader commented
OK, the crash is not fixed by the workaround above, so I filed #89 for one of the crashes.
deus-libri commented
I've updated preflate to v0.3.5. It should solve this issue. At least when compiled by Windows clang++ with sanitizers enabled, it didn't find anything when I checked against my standard corpus of ~11000 deflate streams.