Zstd: Out-of-bounds read in ZSTD_insertBtAndGetAllMatches()

[vnair81]

See below:

[terrelln]

I don't believe that this is possible. ll0 must be either 0 or 1, since it is a boolean parameter. Then before we access rep, we check repCode == ZSTD_REP_CODE, which can only happen when ll0 == 1, and is also the maximum possible value for repCode.

We could assert that ll0 <= 1 at the top of the function.

[Cyan4973]

I agree with @terrelln , ll0 is necessarily <= 1,
but that's a guarantee that the static analyzer seems unable to determine.

We could add an assert(),
which feels like a good idea anyway because it can act as an "active comment"
hence improves code clarity.

However, I'm unsure if this will be a good enough signal for the static analyzer.
It might simply elude it since assert() are disabled in release mode.
Ideally, I would like to reproduce this warning to see if the assert() can solve it.
I'm currently using 2 static analyzers (scan-build and cppcheck), and none of them trigger any warning on this code section.

[vnair81]

If ll0 is meant to be <=1, we can convert its type to bool. In this case we won't need an assert.

Or perhaps we can add the assert and convert repCode == ZSTD_REP_CODE to repCode >= ZSTD_REP_CODE.

[vnair81]

If we don't want to change ll0's type, we can also change:
U32 const lastR = ZSTD_REP_NUM + ll0;
to
U32 const lastR = ZSTD_REP_NUM + (ll0 ? 1 : 0);
making the intent (of an integer being treated as a binary) very clear.

[Cyan4973]

U32 const lastR = ZSTD_REP_NUM + (ll0 ? 1 : 0);

I tried this suggested variant. Unfortunately, the generated code is not binary identical, so it impacts the assembler generated.

I then measured a very small speed hit (~1%). Note that this is within error margin, so it might have been noise.

Anyway, if the intention is to ensure that ll0 is understood as a 0/1 value, I believe that an assert() and a comment are enough.

[cemeyer]

Anyway, if the intention is to ensure that ll0 is understood as a 0/1 value, I believe that an assert() and a comment are enough.

One advantage of the bool type is that it literally cannot hold values other than 0 or 1. No assertion is needed; it is defined by the C standard since 1999. This might help make the variable's semantics more clear to both developers and static analyzers.

(Edit: In C11, this is specified in §6.3.1.2, _Boolean type_: "When any scalar value is converted to _Bool, the result is 0 if the value compares equal to 0; otherwise, the result is 1.")

[Cyan4973]

One issue is that we try to keep the code mostly compatible with C90 (+ a few reasonable extensions, such as variadic macros, or long long type) for broader compatibility.

[cemeyer]

One possible C90 compromise might be something like:

#if !defined(__STDC_VERSION__) || __STDC_VERSION__ < 199901L
#define bool U32
#else
#include <stdbool.h>
#endif

[Cyan4973]

Right, we could define our own bool type,
I suspect I would rather lean towards using enum in this case,

but it feels overblown if the objective is just to solve this issue #1397.
Introducing a new type must be considered at code base level.

I feel no urge to push for the introduction of bool type within zstd currently,
though I note the suggestion, as it could happen in the future.

[cemeyer]

That is very reasonable, and I agree with the conclusion — this issue does not justify a change of that magnitude. I just happen to like C99+ and bool personally, so I try to advocate for it a little bit ;-). No worries.