README.md

# Apache ORC C++ dictionary-length cumulative-overflow PoC

Tested against Apache ORC commit:

```text
af4cbf36b051c176f0d13ae5a7ac436ada8aeccf
```

## Summary

The C++ string-dictionary loader validates each decoded dictionary entry length
for negativity, but it adds the individually valid values into signed
`int64_t` prefix sums without checking overflow.

The 251-byte trigger contains three non-negative dictionary lengths:

```text
INT64_MAX, INT64_MAX, 2
```

Their mathematical sum is `2^64`. The prefix sums overflow signed `int64_t`,
the final dictionary blob size wraps to zero, and the row reader returns a
`StringVectorBatch` whose first row advertises length `INT64_MAX` over a
one-byte backing allocation. A consumer that reads the returned string data
causes a heap-buffer-overflow.

The valid 228-byte control contains the strings `a`, `bb`, `a`, `bb` and exits
normally.

## Reproduce

Build prerequisites are the same as Apache ORC C++. Then run:

```bash
ORC_SRC=/path/to/orc ./reproduce.sh
```

The script configures current ORC with AddressSanitizer and
UndefinedBehaviorSanitizer, builds the standalone reader harness, and runs both
fixtures.

Expected control:

```text
row=0 length=1
checksum=97
value=a
row=1 length=2
checksum=0
value=bb
...
rows=4
```

Expected trigger:

```text
row=0 length=9223372036854775807
DictionaryLoader.cc:79:22: runtime error: signed integer overflow
ColumnReader.cc:591:57: runtime error: signed integer overflow
ERROR: AddressSanitizer: heap-buffer-overflow
READ of size 1
0x... is located 0 bytes after 1-byte region
```

The harness limits downstream inspection to 1 MiB. It does not attempt to
materialize the advertised `INT64_MAX` bytes.

## Fixtures

```text
88477314865f2fdf594489fdd08a9996447a549245be27cddc303444d2cf5068  control-two-entry-dictionary.orc
0f3625588531b294bfebb5c9f19b3099dbc62815ce31487cf8c102f0de4f1034  trigger-wrapped-zero-offsets.orc
```

The generator embeds the Apache ORC 2.2.2 control and changes only:

- the dictionary LENGTH stream;
- that stream's serialized byte length;
- the stripe data length; and
- the dictionary entry count.

## Root cause

At `c++/src/DictionaryLoader.cc:73-80`, each raw entry passes the existing
negative-value check before the unchecked signed addition:

```cpp
if (lengthArray[i] < 0) {
  throw ParseError(...);
}
lengthArray[i] += lengthArray[i - 1];
```

At `c++/src/ColumnReader.cc:588-593`, the corrupted offsets are subtracted
again and exposed through `StringVectorBatch::length` and
`StringVectorBatch::data`.

## Prior-art distinction

ORC-312 / PR #224 fixed the case where one decoded dictionary length was
already negative before accumulation. This trigger uses three individually
non-negative lengths and overflows only during the prefix-sum addition after
that check.

ORC-2192 / PR #2673 covers direct-encoded strings, not dictionary prefix sums.

## Suggested fix

Before adding each entry, reject:

```cpp
lengthArray[i] >
    std::numeric_limits<int64_t>::max() - lengthArray[i - 1]
```

Also validate that every cumulative offset is monotonic, fits the backing
dictionary blob, and can be safely subtracted before exposing string lengths.