`TreeLength()` on a multifurcating tree performs out-of-bounds heap writes and returns a score read from memory *before* the buffer — reachable with no error and no warning from `MaximizeParsimony()`'s DEFAULT output.

[ms609]

Severity: P1 · Area: 11 (Collapse), 6 (R<->C++ interface)

Location: R/tree_length.R:74-76 (the guard that exists) vs :325-330/:399 (the method that lacks it); root cause src/ts_tree.cpp:11-35; garbage read at src/ts_fitch.cpp:88-91

TreeState::init_from_edge derives n_tip = n_edge / 2 + 1, which is wrong for every non-binary tree. For a rooted tree with n tips and k internal nodes, n_edge = n + k - 1, so n_node_derived = 2 * floor(n_edge / 2) + 1 and both parities break, differently: (a) n_edge odd -> n_node_derived == n_edge, one short, so parent[c] = p writes 1 int past the end and pi = p - n_tip reaches n_internal, making left[pi]/right[pi] OOB writes; (b) n_edge even -> indices stay in bounds but parent[n_tip] = n_tip (:35) puts the root on a real tip (since n_tip_derived < n for every non-binary tree), so left[0] == right[0] == -1, build_postorder yields a 1-element postorder, and ts_fitch.cpp:88-91 forms &prelim[size_t(-1) * total_words + offset] = prelim.data() - total_words — the returned score is computed from memory before the buffer. Not a mis-resolved traversal on either path. Verified REAL and worse than filed (opus verifier, clean git archive build of HEAD 5ac9e280 with -D_GLIBCXX_ASSERTIONS injected via R_MAKEVARS_USER, so no src/Makevars.win entered the repo): stl_vector.h:1130: Assertion '__n < this->size()' failed on both parities, and an instrumented build attributes them exactly — *** OOB WRITE parent[13], parent.size()==13, *** OOB ACCESS left/right[6], size()==6 on (a,(b,((e,f),(g,h),(c,d)))); (n_edge = 13). Reachable on the documented happy path: collapse = TRUE is the default (R/MaximizeParsimony.R:1012) and returns multifurcating trees, so TreeLength(MaximizeParsimony(dat), dat) on a length-1 collapsed multiPhylo returned 12, 9, 12, 12, 12 across five identical calls (truth 12); a 12-taxon matrix gave 4, 3, 6, 0, 6 against a truth of 13. Independently corroborated by a second verifier that had not been told about this finding (it rediscovered the same guard asymmetry while checking T-401), on different data: Vinther2008 inapplicable = "missing", the 15 returned trees with Nnode 21 -> 40 40 40 22 40 40 22 22 40 22 40 40 40 22 40 where MakeTreeBinary(grp[[1]]) gives the true 78. Two traps for a fixer: an accidental partial guard means a heterogeneous edge-count set errors with "Trees have different numbers of edges", so this bites hardest on homogeneous or length-1 results; and res[[1]] errors cleanly while res[1] returns silent garbage. The exposure is not confined to TreeLength — same missing guard, same kernel entry, all reproduced or traced: CharacterLength() / FastCharacterLength() (R/tree_length.R:510, :536; .CheckTreeCharLen at :441-451 checks class/labels/rooted but not binary; returned 0 where truth is 2), TreeScore() (:570) and EdgeListScore() (:596) — and EdgeListScore is the default TreeScorer for TreeSearch()/Ratchet()/Jackknife() — plus the TreeLength.list HSJ (:367) and XFORM (:375-380) branches. Guarded or unreachable: MaximizeParsimony() start trees (MakeTreeBinary() + hard stop(), :1454-1465), ts_ls_fit/ts_ls_search (same bad derivation cloned at src/ts_rcpp.cpp:271-273 but R/LeastSquares.R:64 guards with ape::is.binary), Resample()/Jackknife()/Bootstrap()/SuccessiveApproximations() (never pass a user tree's edges to C++), ts_collapse_pool (only ever sees the search's own binary pool); 17 further init_from_edge exports are equally unguarded but have no R caller outside RcppExports.R. Fix at the root, not per-caller: a boundary check in init_from_edge (require n_edge == 2 * (n_tip - 1), or every internal node to have exactly two children) fixes all entry points at once — which is why this is one row rather than four. Relationship to GitHub issue ms609#259, stated precisely because it is easy to get backwards: ms609#259 is an OPEN low-priority enhancement asking to support polytomous scoring, and it asserts as background that "TreeLength.phylo() errors with tree must be binary" — i.e. it believes the API safely refuses. This finding is that the refusal was never implemented uniformly, so one entry point silently misbehaves instead of erroring. It is a bug inside today's contract, not the feature ms609#259 requests, and closing ms609#259 would not close it. Nearest existing row is T-372 (TreeLength() on a list under profile parsimony erroring "Not a matrix.") — same method family, different defect.

---

Migrated 2026-08-04 from dev/red-team/findings.md; pre-tracker ID T-400. References to T-400 in source comments, dev/red-team/log.md, commit messages and PR bodies mean this issue — see dev/red-team/migration-map.tsv. Cross-repo references use the fully-qualified form agent-issues/TreeSearch#<n>; a bare #n means this repo.

[ms609]

Claiming on branch feature/multifurc-oob, worktree worktrees/TreeSearch/wonderful-goodall-d625d2. Fixed together: the #24 comment audit covers the construction-time zeroing in init_from_edge, which #16 rewrites.

[ms609]

PR #50 opened against cpp-search.

ubuntu-arm64 full R CMD check is green (Status: OK, FAIL 0 | PASS 11754). The windows leg fails in dependency setup on the pre-existing MaxMin resolution error that also reddened cpp-search itself (run 30909722952); #45 fixes it. Awaiting: that merge, then a re-dispatch of agent-check.yml on feature/multifurc-oob, then human review of #50.

[ms609]

Independent corroboration from #17's chip (feature/xform-statespace), with a cheap local reproducer.

A regression test there called TreeLength() on a contracted (polytomous) tree under inapplicable = "xform" to demonstrate that doing so returns the wrong length. That call aborted ubuntu-arm64 with double free or corruption (out) — reproducibly, on three of three runs, while cpp-search was green on two of two. It was not caught locally because plain x86 builds only return the wrong number silently.

Under -D_GLIBCXX_ASSERTIONS the fault is precise and reproduces on Windows in seconds:

bits/stl_vector.h:1130: std::vector<_Tp, _Alloc>::reference
std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = long long unsigned int; ...]:
Assertion `__n < this->size()` failed.

Note _Tp = uint64_t and the non-const operator[] — an out-of-bounds write into the Fitch word vector, matching this issue's title. Build with the flag in PKG_CPPFLAGS (not PKG_CXXFLAGS, which ~/.R/Makevars.win zeroes), then score any polytomous tree.

Two things worth carrying into the fix:

1. tryCatch() is no defence. The test wrapped the call expecting T-400 to surface as a catchable R error; heap corruption is not catchable, so the guard did nothing. Any code that currently "handles" a multifurcating tree by catching an error is not protected today.
2. A boundary check in TreeState::init_from_edge should abort, not repair. The x86 behaviour — a plausible-looking wrong number — is the more dangerous of the two symptoms, so failing loudly is the right outcome.

The #17 chip does not depend on this being fixed: it makes MaximizeParsimony()'s own report block score the binary pool a contracted tree came from, so it never reaches the kernel with a polytomy. Its test no longer performs the unsafe call.