SEGV / uncaught exception in get_nns_by_item() via crafted index (untrusted node indices never bounds-checked — matches the existing "TODO: handle OOB" comment)

[3nesdeniz]

Summary

AnnoyIndex::_get_all_nns() (the internal traversal used by get_nns_by_item() /
get_nns_by_vector()) uses node index values read raw from the loaded index file —
specifically the heuristically-detected roots from load(), and each node's own
children[0]/children[1] fields — to index into the mmap'd node array via _get(i), which
does unbounded pointer arithmetic (_nodes + _s*i, no check against _n_nodes). This
directly matches the // TODO: handle OOB comment already present in get_nns_by_item().

I found two distinct crashes from this same root cause while fuzzing a crafted/mutated index
file, both triggered during a normal get_nns_by_item() query (not just at load time):

1. SEGV (wild pointer dereference) in _get_all_nns (annoylib.h ~1470) when a
   corrupted children[] value points far outside the mapped region.
2. Uncaught std::length_error (process abort) in the same function's
   nns.insert(nns.end(), dst, &dst[nd->n_descendants]) when a node's n_descendants field
   is corrupted to an implausibly large value.

Both are reachable simply by loading a tampered/crafted .ann index file and then querying it
normally — a realistic scenario if index files are ever shared, downloaded, or produced by an
untrusted pipeline (common in embedding-search / RAG setups).

Fix

Every place a node index that ultimately comes from the file (roots, children[0]/children[1],
and the values inserted into nns in the n_descendants <= _K branch) is used to call _get()
needs a bounds check against _n_nodes. Note n_descendants is signed (S), so the existing
n_descendants <= _K check alone is not enough -- a corrupted negative value passes it and
flips the subsequent pointer arithmetic (&dst[negative] lands before dst). Full patch
attached (fix-annoy-oob-segv.patch); the key pieces:

if (i < 0 || (size_t)i >= _n_nodes) { q.pop(); continue; }
Node* nd = _get(i);
...
if (nd->n_descendants == 1 && i < _n_items) {
    nns.push_back(i);
} else if (nd->n_descendants >= 0 && nd->n_descendants <= _K) {   // >= 0 is required
    const S* dst = nd->children;
    for (S* p2 = const_cast<S*>(dst); p2 != &dst[nd->n_descendants]; ++p2) {
        S v2 = *p2;
        if (v2 >= 0 && (size_t)v2 < _n_nodes) nns.push_back(v2);
    }
} else {
    S c1 = static_cast<S>(nd->children[1]);
    S c0 = static_cast<S>(nd->children[0]);
    if (c1 >= 0 && (size_t)c1 < _n_nodes) q.push(...);
    if (c0 >= 0 && (size_t)c0 < _n_nodes) q.push(...);
}

I found this fix required three iterations -- fuzzing caught two follow-up crashes in my own
first two attempts, including the signed-n_descendants subtlety above, which is why I'm
flagging it explicitly in case a partial fix looks tempting. All three known crash inputs
(two distinct SEGVs + the length_error DoS) are clean against the final version, and a
legitimately built-and-saved index (30 items) still returns identical get_nns_by_item
results after loading with the patched code — no regression. Happy to open a PR with this fix.