Zstd: NULL + offset has undefined behavior

[QrczakMK]

In C adding an offset to a null pointer has undefined behavior (in C++ that would be valid only if the offset was 0).

zstd may perform such operations (with both zero and non-zero offsets), which breaks execution under UBSan.

Here are places that I could find by running some of our tests under UBSan (in 1.4.4):

diff --git a/google3/third_party/zstdlib/compress/zstd_compress.c b/google3/third_party/zstdlib/compress/zstd_compress.c
--- a/google3/third_party/zstdlib/compress/zstd_compress.c
+++ b/google3/third_party/zstdlib/compress/zstd_compress.c
@@ -1321,6 +1321,7 @@ ZSTD_reset_matchState(ZSTD_matchState_t*
     DEBUGLOG(4, "reset indices : %u", forceResetIndex == ZSTDirp_reset);
     if (forceResetIndex == ZSTDirp_reset) {
         memset(&ms->window, 0, sizeof(ms->window));
+        ms->window.base = "";
         ms->window.dictLimit = 1;    /* start from 1, so that 1st position is valid */
         ms->window.lowLimit = 1;     /* it ensures first and later CCtx usages compress the same */
         ms->window.nextSrc = ms->window.base + 1;   /* see issue #1241 */
@@ -3655,11 +3656,11 @@ static size_t ZSTD_compressStream_generi
                                           ZSTD_EndDirective const flushMode)
 {
     const char* const istart = (const char*)input->src;
-    const char* const iend = istart + input->size;
-    const char* ip = istart + input->pos;
+    const char* const iend = input->size ? istart + input->size : istart;
+    const char* ip = input->pos ? istart + input->pos : istart;
     char* const ostart = (char*)output->dst;
-    char* const oend = ostart + output->size;
-    char* op = ostart + output->pos;
+    char* const oend = output->size ? ostart + output->size : ostart;
+    char* op = output->pos ? ostart + output->pos : ostart;
     U32 someMoreWork = 1;

     /* check expectations */
@@ -3698,7 +3699,7 @@ static size_t ZSTD_compressStream_generi
                                         zcs->inBuff + zcs->inBuffPos, toLoad,
                                         ip, iend-ip);
                 zcs->inBuffPos += loaded;
-                ip += loaded;
+                if (loaded) ip += loaded;
                 if ( (flushMode == ZSTD_e_continue)
                   && (zcs->inBuffPos < zcs->inBuffTarget) ) {
                     /* not enough input to fill full block : stop here */
@@ -3758,7 +3759,7 @@ static size_t ZSTD_compressStream_generi
                             zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
                 DEBUGLOG(5, "toFlush: %u into %u ==> flushed: %u",
                             (unsigned)toFlush, (unsigned)(oend-op), (unsigned)flushed);
-                op += flushed;
+                if (flushed) op += flushed;
                 zcs->outBuffFlushedSize += flushed;
                 if (toFlush!=flushed) {
                     /* flush not fully completed, presumably because dst is too small */
diff --git a/google3/third_party/zstdlib/compress/zstd_double_fast.c b/google3/third_party/zstdlib/compress/zstd_double_fast.c
--- a/google3/third_party/zstdlib/compress/zstd_double_fast.c
+++ b/google3/third_party/zstdlib/compress/zstd_double_fast.c
@@ -96,7 +96,7 @@ size_t ZSTD_compressBlock_doubleFast_gen
                                      dictCParams->hashLog : hBitsL;
     const U32 dictHBitsS           = dictMode == ZSTD_dictMatchState ?
                                      dictCParams->chainLog : hBitsS;
-    const U32 dictAndPrefixLength  = (U32)(ip - prefixLowest + dictEnd - dictStart);
+    const U32 dictAndPrefixLength  = (U32)((ip - prefixLowest) + (dictEnd - dictStart));

     DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_generic");

diff --git a/google3/third_party/zstdlib/compress/zstd_lazy.c b/google3/third_party/zstdlib/compress/zstd_lazy.c
--- a/google3/third_party/zstdlib/compress/zstd_lazy.c
+++ b/google3/third_party/zstdlib/compress/zstd_lazy.c
@@ -660,7 +660,7 @@ ZSTD_compressBlock_lazy_generic(
     const U32 dictIndexDelta       = dictMode == ZSTD_dictMatchState ?
                                      prefixLowestIndex - (U32)(dictEnd - dictBase) :
                                      0;
-    const U32 dictAndPrefixLength = (U32)(ip - prefixLowest + dictEnd - dictLowest);
+    const U32 dictAndPrefixLength = (U32)((ip - prefixLowest) + (dictEnd - dictLowest));

     /* init */
     ip += (dictAndPrefixLength == 0);

Could you fix that please?

[Cyan4973]

Thanks for feedback @QrczakMK !
Another thing we may need is a test able to trigger the same warnings, so that we can act on the same signal, and avoid breaking things again in the future.
I'm surprised we did not see it already, as we are supposed to have an usan test up and running.
To be investigated ...

[terrelln]

I guess we never use NULL as an input for compression in our tests.

[QrczakMK]

There are 3 categories of issues in my patch:

• ZSTD_reset_matchState(): this unconditionally computes (const uint8_t*)NULL + 1. I am not sure whether my fix is the most appropriate though (and ms->window.base = "" likely needs a comment).
• ZSTD_compressStream_generic(): this indeed likely only manifests if the caller passed {NULL, 0, 0} as ZSTD_inBuffer or ZSTD_outBuffer. Arguably zstd does not have to support this, but it would be harmless to fix. In our case the caller is in C++ (where an empty range beginning at a null pointer is generally valid, and only some functions like std::memcpy() annoyingly do not support that), and a test compresses an empty input — this triggers ZSTD_compressStream2() with ZSTD_e_end, and the only input buffer available was an empty range at a null pointer. The calling code might work around that by an explicit check which ensures that a non-null pointer is passed.
• ZSTD_compressBlock_doubleFast_generic(), ZSTD_compressBlock_lazy_generic() — this is an obvious improvement because even without null pointers the original code may form a pointer out of range of an array, and only afterwards subtract an offset to bring it back to the valid range.

[terrelln]

I haven't been able to reproduce the UBSAN warnings with clang-9.0.0 and -fsanitize=undefined,pointer-overflow, when I added a test that passed ZSTD_inBuffer = { NULL, 0, 0 };, so it definitely triggered the code.

Do you know what compiler+options are used to trigger the UBSAN warning?

[QrczakMK]

It is a quite new clang check, since Oct 10: https://github.com/llvm/llvm-project/commit/536b0ee40ab97f2878dc124a321cf9108ee3d233

[terrelln]

Thanks @QrczakMK! Conveniently, I already have a clang development build on my machine, and I can reproduce these failures with it.

I'll add some extra tests, and fix all the warnings for now. Then once clang-10.0 is released we'll be able to test for regressions in our CI.

[terrelln]

I will fix all the NULL pointer arithmetic for this issue.

But, that does leave a bunch of pointer overflows like "pointer index expression with base 0xffffffffffe28161 overflowed to 0x000001283be0". Zstd relies on pointer overflow/underflow wrapping around. We could potentially cast to uintptr_t before the arithmetic, and cast back to a pointer after... But that would be a very invasive change, probably use a macro to manipulate base/dictBase instead of the addition we do currently.