The debug-only invariant checker and the benchmark helper both use a for loop that computes str.size() - 1 without first checking that the string is non-empty. For an empty key this underflows size_t, and assigning the result to a signed int is implementation-defined; on platforms where the conversion does not yield -1, the subsequent str[index] is an out-of-bounds read.
Locations
ConflictSet.cpp line 5681: std::string strinc(std::string_view str, bool &ok)
Bench.cpp line 40: ConflictSet::ReadRange prefixRange(Arena &arena, TrivialSpan key)
When str.size() == 0, str.size() - 1 wraps to SIZE_MAX. Converting SIZE_MAX (a 64-bit unsigned value in this build) to int is implementation-defined, and the following str[index] is only safe if that conversion happens to produce -1.
Concrete code path that triggers it
strinc() is called from checkMaxVersion() (ConflictSet.cpp line 5834) with key = getSearchPath(root). For the root node of the radix tree, getSearchPath() returns the empty string, so every debug/fuzz run that calls checkCorrectness() exercises strinc("", ok).
Reproduction
Build a Debug fuzz target and run any corpus input; the path is hit immediately inside checkCorrectness:
A small standalone demonstration of the pattern is:
#include<string_view>boolstrinc(std::string_viewstr){intindex;for(index=str.size()-1;index>=0;index--);returnindex>=0;}intmain(){returnstrinc("");// UB: size_t underflow + signed conversion
}
Expected vs actual
Expected: The helper handles the empty string gracefully (returns ok = false) without invoking implementation-defined or undefined behavior.
Actual: The function performs str.size() - 1 on an empty string, causing an unsigned underflow and an implementation-defined signed conversion before any bounds check.
Impact
strinc() is used only by the debug invariant checker (checkMaxVersion / checkCorrectness), so release builds are not directly affected. However, fuzz tests and debug CI runs rely on this path to validate tree correctness, and the implementation-defined behavior makes those checks non-portable and potentially unreliable across compilers or sanitizer configurations.
prefixRange() is used by benchConflictSet() in Bench.cpp. Passing an empty key (intentionally or via a future benchmark variant) would hit the same UB and could crash the benchmark or read out of bounds.
Suggested fix
Guard the loop so it only runs when the string is non-empty, e.g. for strinc:
The same guard should be applied to prefixRange().
The debug-only invariant checker and the benchmark helper both use a `for` loop that computes `str.size() - 1` without first checking that the string is non-empty. For an empty key this underflows `size_t`, and assigning the result to a signed `int` is implementation-defined; on platforms where the conversion does not yield `-1`, the subsequent `str[index]` is an out-of-bounds read.
## Locations
- `ConflictSet.cpp` line 5681: `std::string strinc(std::string_view str, bool &ok)`
- `Bench.cpp` line 40: `ConflictSet::ReadRange prefixRange(Arena &arena, TrivialSpan key)`
Both functions contain:
```cpp
int index;
for (index = str.size() - 1; index >= 0; index--)
if ((uint8_t &)(str[index]) != 255)
break;
```
When `str.size() == 0`, `str.size() - 1` wraps to `SIZE_MAX`. Converting `SIZE_MAX` (a 64-bit unsigned value in this build) to `int` is implementation-defined, and the following `str[index]` is only safe if that conversion happens to produce `-1`.
## Concrete code path that triggers it
`strinc()` is called from `checkMaxVersion()` (ConflictSet.cpp line 5834) with `key = getSearchPath(root)`. For the root node of the radix tree, `getSearchPath()` returns the empty string, so every debug/fuzz run that calls `checkCorrectness()` exercises `strinc("", ok)`.
## Reproduction
Build a Debug fuzz target and run any corpus input; the path is hit immediately inside `checkCorrectness`:
```bash
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --target fuzz_driver
./build/fuzz_driver corpus/<any-file>
```
A small standalone demonstration of the pattern is:
```cpp
#include <string_view>
bool strinc(std::string_view str) {
int index;
for (index = str.size() - 1; index >= 0; index--)
;
return index >= 0;
}
int main() {
return strinc(""); // UB: size_t underflow + signed conversion
}
```
## Expected vs actual
- **Expected:** The helper handles the empty string gracefully (returns `ok = false`) without invoking implementation-defined or undefined behavior.
- **Actual:** The function performs `str.size() - 1` on an empty string, causing an unsigned underflow and an implementation-defined signed conversion before any bounds check.
## Impact
- `strinc()` is used only by the debug invariant checker (`checkMaxVersion` / `checkCorrectness`), so release builds are not directly affected. However, fuzz tests and debug CI runs rely on this path to validate tree correctness, and the implementation-defined behavior makes those checks non-portable and potentially unreliable across compilers or sanitizer configurations.
- `prefixRange()` is used by `benchConflictSet()` in `Bench.cpp`. Passing an empty key (intentionally or via a future benchmark variant) would hit the same UB and could crash the benchmark or read out of bounds.
## Suggested fix
Guard the loop so it only runs when the string is non-empty, e.g. for `strinc`:
```cpp
std::string strinc(std::string_view str, bool &ok) {
int index = static_cast<int>(str.size()) - 1;
for (; index >= 0; index--)
if (static_cast<uint8_t>(str[index]) != 255)
break;
if (index < 0) {
ok = false;
return {};
}
ok = true;
auto r = std::string(str.substr(0, index + 1));
static_cast<uint8_t &>(r[r.size() - 1])++;
return r;
}
```
The same guard should be applied to `prefixRange()`.
weaselbot
was assigned by andrew2026-06-29 17:04:11 +00:00
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
The debug-only invariant checker and the benchmark helper both use a
forloop that computesstr.size() - 1without first checking that the string is non-empty. For an empty key this underflowssize_t, and assigning the result to a signedintis implementation-defined; on platforms where the conversion does not yield-1, the subsequentstr[index]is an out-of-bounds read.Locations
ConflictSet.cppline 5681:std::string strinc(std::string_view str, bool &ok)Bench.cppline 40:ConflictSet::ReadRange prefixRange(Arena &arena, TrivialSpan key)Both functions contain:
When
str.size() == 0,str.size() - 1wraps toSIZE_MAX. ConvertingSIZE_MAX(a 64-bit unsigned value in this build) tointis implementation-defined, and the followingstr[index]is only safe if that conversion happens to produce-1.Concrete code path that triggers it
strinc()is called fromcheckMaxVersion()(ConflictSet.cpp line 5834) withkey = getSearchPath(root). For the root node of the radix tree,getSearchPath()returns the empty string, so every debug/fuzz run that callscheckCorrectness()exercisesstrinc("", ok).Reproduction
Build a Debug fuzz target and run any corpus input; the path is hit immediately inside
checkCorrectness:A small standalone demonstration of the pattern is:
Expected vs actual
ok = false) without invoking implementation-defined or undefined behavior.str.size() - 1on an empty string, causing an unsigned underflow and an implementation-defined signed conversion before any bounds check.Impact
strinc()is used only by the debug invariant checker (checkMaxVersion/checkCorrectness), so release builds are not directly affected. However, fuzz tests and debug CI runs rely on this path to validate tree correctness, and the implementation-defined behavior makes those checks non-portable and potentially unreliable across compilers or sanitizer configurations.prefixRange()is used bybenchConflictSet()inBench.cpp. Passing an empty key (intentionally or via a future benchmark variant) would hit the same UB and could crash the benchmark or read out of bounds.Suggested fix
Guard the loop so it only runs when the string is non-empty, e.g. for
strinc:The same guard should be applied to
prefixRange().