README.md

# MLeap `bundle-ml` tree deserializers: uncontrolled recursion -> uncaught StackOverflowError (CWE-674 / CWE-400)

Target: `combust/mleap` (huntr.com MFF), specifically the Bundle.ML tree
serializer components in the `bundle-ml` module (component category:
"other serializer classes", not the previously-filed `ArraySerializer` OOM
finding).

## Affected code

- `bundle-ml/src/main/scala/ml/combust/bundle/tree/decision/TreeSerializer.scala`
  - `TreeSerializer.read(reader: FormatTreeReader): N` (lines ~112-122) —
    unbounded recursion, one stack frame per tree node, no depth/size limit.
  - `ProtoFormatTreeReader.read()` (lines ~67-76) — allocates
    `new Array[Byte](size)` from an attacker-controlled `readInt()` with no
    bound check against remaining stream length (secondary issue, same file).
- `bundle-ml/src/main/scala/ml/combust/bundle/tree/cluster/NodeSerializer.scala`
  - `NodeSerializer.read(reader: FormatNodeReader): N` (lines ~111-118) — the
    identical unbounded-recursion pattern, keyed off attacker-controlled
    `numChildren`, in the sibling clustering-tree (BisectingKMeans) reader.
    Confirms this is a systemic pattern, not a one-off.

Both are reached from real, exercised production call paths, e.g.:

```scala
// mleap-runtime/.../bundle/ops/classification/DecisionTreeClassifierOp.scala
override def load(model: Model)(implicit context: BundleContext[MleapContext]): DecisionTreeClassifierModel = {
  val rootNode = TreeSerializer[tree.Node](context.file("tree"), withImpurities = true).read().get
  ...
```

i.e. any application that loads an untrusted MLeap bundle (`.zip`) containing
a `DecisionTreeClassifier`/`DecisionTreeRegressor` (and, by the identical
pattern above, `BisectingKMeans`) component reaches this code.

## The bug

`read(reader)` recursively reads a pre-order-encoded binary tree with **no
depth limit and no node-count limit**:

```scala
def read(reader: FormatTreeReader): N = {
  val node = reader.read()
  if(node.n.isInternal) {
    ntc.internal(node.getInternal, read(reader), read(reader))   // <-- unbounded recursion
  } else if(node.n.isLeaf) {
    ntc.leaf(node.getLeaf, withImpurities)
  } else { throw new IllegalArgumentException("invalid tree") }
}
```

A degenerate/unbalanced tree (a long right-leaning chain of "internal" nodes)
recurses to a depth proportional to the number of nodes. With the JVM's
default 1 MB thread stack, a **~340 KB** crafted `tree.json` (~3,500 chained
nodes) is enough to blow the stack.

Worse: MLeap's own bundle-loading API is entirely built on
`scala.util.Try` / `scala.util.Using`, seemingly to convert load errors into
a handled `Failure(...)`. But `scala.util.control.NonFatal` (see
`NonFatal_bytecode.txt`) checks `instanceof VirtualMachineError` **first**
and treats it as fatal (not caught). `StackOverflowError extends
VirtualMachineError`. So the `StackOverflowError` is **not** converted into a
`Failure` anywhere in the chain — it propagates as an uncaught `Error` clean
through `TreeSerializer.read(): Try[N]`, `ModelSerializer.readWithModel()`,
`NodeSerializer.read()`, and `BundleSerializer.read(): Try[Bundle[_]]`,
crashing the thread that called the "safe", Try-typed bundle-load API.

This is confirmed empirically in `evidence_log.txt` item 2 and item 4 below
(not just theorized from the Scala docs).

## Real, unmodified-code proof

All four harnesses below are plain Scala programs compiled against the
**real, unmodified, published** `ml.combust.bundle:bundle-ml_2.13:0.24.0`
jar from Maven Central — the exact release that HEAD of
`https://github.com/combust/mleap` is tagged as (`v0.24.0`,
commit `027342cac5c96d6cb4f56046634a5f0487849a67`). No library source was
patched or stubbed; only a trivial `NodeWrapper[N]` type-class instance is
supplied (the same kind of glue MLeap's own `mleap-runtime` module supplies
via `MleapNodeWrapper`), because that is a public extension point the
library requires callers to implement.

- `TreeRecursionHarness.scala` — crafts a malicious tree payload and calls
  the real `ml.combust.bundle.tree.decision.TreeSerializer.read(reader)`
  directly.
- `TreeRecursionHarness2.scala` — same payload, but drives the real
  file-based, `Try`-returning public API `TreeSerializer.read(): Try[N]`
  (exactly what `DecisionTreeClassifierOp.load()` /
  `DecisionTreeRegressionOp.load()` call), to prove the crash escapes even
  through the "safe" API.
- `ClusterRecursionHarness.scala` — same technique against the sibling
  `ml.combust.bundle.tree.cluster.NodeSerializer` (BisectingKMeans).
- `TrySoeCheck.scala` — isolated, minimal proof that `scala.util.Try` does
  not catch `StackOverflowError` in this Scala version (2.13.16, the exact
  version `bundle-ml_2.13-0.24.0` is compiled against).

See `evidence_log.txt` for full run output (StackOverflowError stack traces
truncated for brevity; full traces were captured and inspected manually) and
`NonFatal_bytecode.txt` for the decompiled proof of the `NonFatal.apply`
fatal/non-fatal check ordering.

## Reproduce

```
# fetch bundle-ml_2.13-0.24.0.jar + its runtime deps from Maven Central
# (scala-library/-compiler/-reflect 2.13.16, protobuf-java 3.21.7,
#  scalapb-runtime_2.13 0.11.13, lenses_2.13 0.11.13, config 1.4.2,
#  scala-collection-compat_2.13 2.8.1, spray-json_2.13 1.3.6)
CP=$(ls jars/*.jar | tr '\n' ':')
java -cp "$CP" scala.tools.nsc.Main -d classes -classpath "$CP" \
    TreeRecursionHarness.scala TreeRecursionHarness2.scala \
    ClusterRecursionHarness.scala TrySoeCheck.scala
java -cp "${CP}classes" TreeRecursionHarness2 4000
```

## Impact

Denial of Service: a small (a few hundred KB), otherwise well-formed
MLeap bundle containing a degenerate decision-tree / random-forest /
GBT / BisectingKMeans component crashes the loading thread with an
uncaught `StackOverflowError` in any application that embeds MLeap to load
user-/client-supplied model bundles (e.g. mleap-serving, a custom scoring
service, a model-management pipeline). This directly defeats the
`Try`-based error-handling contract the library advertises for bundle
loading — callers who correctly `match` on `Success`/`Failure` still see
their thread die from an uncaught `Error` instead.

## Dedup check

Searched `combust/mleap` GitHub issues/PRs for `StackOverflow`,
`TreeSerializer`, `recursion`, `OOM`, `security`, `denial` — no existing
report of this recursion/stack-exhaustion issue. The only related prior
security fix found was PR #866 ("Fix - Add zip slip validation"), an
unrelated path-traversal fix in the bundle `.zip` extractor (already merged,
confirmed still fixed in current `FileUtil.scala`). This finding is distinct
from the already-filed `ArraySerializer` OOM report: different files, a
different bug class (uncontrolled recursion / stack exhaustion vs. unbounded
heap allocation), and a different vulnerable component
(`tree/decision/TreeSerializer.scala` + `tree/cluster/NodeSerializer.scala`
vs. `tensor/ArraySerializer.scala`).