{"repro_id":"REPRO-2026-00361","version":6,"title":"PostgreSQL fuzzystrmatch integer wraparound: levenshtein()/levenshtein_less_equal() overflow leads to OOB writes to effectively-arbitrary addresses (potential RCE)","repro_type":"security","status":"published","severity":"high","description":"Integer wraparound in PostgreSQL contrib/fuzzystrmatch Levenshtein distance functions. Large caller-supplied insertion/deletion/substitution costs cause signed int32 overflow; in levenshtein_less_equal() the overflowed window arithmetic drives out-of-bounds writes (advisory: 'writes effectively-arbitrary addresses'), enabling memory corruption and potential arbitrary code execution as the OS user running the PostgreSQL backend.","root_cause":"# CVE-2026-15742 — Root Cause Analysis\n\n## Summary\n\nPostgreSQL's `src/backend/utils/adt/levenshtein.c` computes Levenshtein distances\nwith 32-bit `int` arithmetic. The contrib/fuzzystrmatch SQL functions\n`levenshtein()` and `levenshtein_less_equal()` accept caller-supplied signed\nint32 insertion/deletion/substitution costs, so a low-privilege authenticated SQL\nuser can force signed-integer wraparound. In `varstr_levenshtein_less_equal()`\nthe wraparound corrupts the bounded-window arithmetic\n(`slack_d = max_d - min_theo_d; stop_column = best_column + slack_d/(ins_c+del_c) + 1`),\nproducing a negative `stop_column`. The row loop then executes\n`prev[stop_column] = max_d + 1` — a 4-byte out-of-bounds write at an\nattacker-tunable offset from the heap-allocated row buffer, with an\nattacker-chosen 32-bit value. This is reachable with\n`CREATE EXTENSION fuzzystrmatch` (not enabled by default) by any role holding\nthe default PUBLIC execute grant.\n\n## Impact\n\n- Package/component: PostgreSQL, contrib/fuzzystrmatch (`levenshtein`, `levenshtein_less_equal`; core code in `src/backend/utils/adt/levenshtein.c`).\n- Affected versions: < 18.6, < 17.11, < 16.15, < 15.19, < 14.24. Reproduced on the official `postgres:17.10` release image.\n- 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.\n\n## Impact Parity\n\n- Disclosed/claimed maximum impact: code execution (\"writes effectively-arbitrary addresses\", potential RCE).\n- Reproduced impact this run: memory corruption / OOB write, with three evidence-backed primitives on the **non-sanitized release build**:\n  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).\n  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`.\n  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.\n  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.\n  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`.\n  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).\n  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.\n- 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:\n  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`).\n  2. Blind ~1.8GB held-cursor heap spray (phase-calibrated fake AllocBlock/glibc-chunk pattern; phase is a build constant).\n  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).\n  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...).\n  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.\n  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).\n\n## Root Cause\n\n`varstr_levenshtein_less_equal()` (levenshtein.c, vulnerable parent\n`37b8f3b0e05e85d4338f04c71caa156ba21d5015`) uses 32-bit `int` throughout:\n`min_theo_d = net_inserts * ins_c`, `slack_d = max_d - min_theo_d`, and\n`stop_column = best_column + slack_d/(ins_c+del_c) + 1` all wrap. With crafted\ncosts (e.g. `ins_c=1073741824, del_c=-1073741823, n-m=2`), `min_theo_d` wraps to\n`INT_MIN`, `slack_d` wraps hugely negative, and `stop_column` becomes\n`-2147483647`. The row-loop guard `if (stop_column < m)` only excludes values\n`>= m`; negative values pass and `prev[stop_column] = max_d + 1` writes out of\nbounds. The same wraparound silently corrupts `levenshtein()` results\n(`SELECT levenshtein('GUMBO','GAMBOL',2e9,2e9,2e9)` → −1474836480 instead of an\nerror). Fix commit `e88eb4e766381070f42e5b84e583a1d0288983f7` (\"Avoid overflow in\nLevenshtein distance calculations\", shipped in 17.11/18.6) switches the\narithmetic to 64-bit and raises `ERROR: levenshtein distance out of range` when\nthe result does not fit int32 — all probe shapes are rejected cleanly on the\nfixed build.\n\nAn exact Python re-implementation of the vulnerable int32 semantics\n(`bundle/repro/lev_sim.py`) reproduces the derived `stop_column`/value for the\nknown trigger and was used to search `(m,n,ins,del,sub,max_d)` tuples for chosen\noffsets/values.\n\n## Reproduction Steps\n\n1. `bundle/repro/reproduction_steps.sh` (self-contained; prefers Docker, falls back to source build of `37b8f3b0...` vs `e88eb4e7...` into the project cache).\n2. 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\n   `SELECT levenshtein_less_equal('aaa','bbbbb',1073741824,-1073741823,-2147483647,0);`\n   twice per build (fresh container per attempt), plus two patch-state probes.\n3. 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).\n\n## Evidence\n\n- Base proof (2 vulnerable + 2 fixed, non-sanitized product path):\n  - `bundle/logs/vulnerable_attempt_{1,2}/psql.txt` — `server closed the connection unexpectedly` (psql rc=2)\n  - `bundle/logs/vulnerable_attempt_{1,2}/server.txt` — signal 11 + failing statement\n  - `bundle/logs/fixed_attempt_{1,2}/psql.txt` — trigger returns 1; `health_after.txt` — server healthy\n  - `bundle/logs/reproduction_steps.log` — full transcript; `bundle/repro/results.env` — counters\n  - `bundle/repro/runtime_manifest.json` — service/health/target flags, image digests, per-artifact SHA-256\n- Escalation evidence (release build):\n  - `bundle/logs/escalation_freeptr/scan_gen.txt` + `scan_stop*.psql.txt` — stop scan: crash only at −7/−8 (block->next)\n  - `bundle/logs/escalation_freeptr/e2.gdb3.txt` — `rbx = 0x41414141` at `AllocSetReset+137: mov 0x10(%rbx),%rbx`\n  - `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)\n  - `bundle/logs/escalation_freeptr/fixed_controls.txt` — fixed build rejects all shapes, zero crashes\n  - `bundle/logs/escalation_multibyte/e1.psql.txt` — multibyte adjacency probe: no in-call consumption, no cross-call persistence (documented negative)\n  - `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`\n  - `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`\n  - `bundle/logs/escalation_freeptr/e5_ctxdump.txt` — live AllocSetContext dump (methods at S+0x10 = 0x5b3e16228bf8, keeper at S+0xC8, prev data at S+0xF8)\n  - `bundle/logs/escalation_freeptr/e6d_rip.gdb.txt` — vtable hijack crash: `call *0x18(%rax)` with rax=0x5b3e40000000 (attacker V), table = 0x41s\n  - `bundle/logs/escalation_freeptr/e8_survive.txt` — vtable entry = real AllocSetReset: hijacked reset executes it, backend SURVIVED (control-flow selection contrast)\n  - `bundle/logs/escalation_freeptr/e9_leak_scan.txt` / `e10_leak_scan.txt` — tcache-entry readback: heap pointer material in fetched cursor rows\n  - `bundle/logs/escalation_freeptr/e11_oracle.txt` — exe-base oracle: correct AllocSetMethods low32 survives, wrong crashes\n- Environment: Docker on Linux x86_64, `randomize_va_space=2`, official release images (vulnerable `postgres@sha256:7958605b...3317`, fixed `postgres@sha256:f4c66b82...1232`).\n\n## RCE Evidence (stage 2 of reproduction_steps.sh)\n\n- `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.\n- `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).\n- `bundle/logs/rce/finale_{x,y}.psql.txt` — trigger queries returning normally while the hijacked vtable runs the payload.\n- `bundle/logs/rce/finale_fixed.psql.txt` — fixed 17.11 control: `ERROR: levenshtein distance out of range`, no markers, server healthy.\n- `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).\n- 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).\n\n## Recommendations / Next Steps\n\n- Upgrade to PostgreSQL 18.6 / 17.11 / 16.15 / 15.19 / 14.24 or later (fix commit `e88eb4e766381070f42e5b84e583a1d0288983f7`).\n- Where upgrade is pending: do not `CREATE EXTENSION fuzzystrmatch`, or revoke EXECUTE on `levenshtein*` functions from PUBLIC/untrusted roles.\n- The fix's 64-bit arithmetic + range ERROR is the correct approach; add regression tests with extreme costs (the patch does).\n\n## Additional Notes\n\n- 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.\n- fuzzystrmatch is not enabled by default; exploitation requires a role able to use the extension (default PUBLIC execute grant after CREATE EXTENSION).\n- gdb attribution runs used a second container with `SYS_PTRACE`; the primary proof path uses only stock images and psql.\n- 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).\n- 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.\n","cve_id":"CVE-2026-15742","cwe_id":"CWE-190","source_url":"https://www.postgresql.org/support/security/CVE-2026-15742","package":{"name":"postgres/postgres","ecosystem":"github","affected_versions":"<18.6, <17.11, <16.15, <15.19, <14.24"},"reproduced_at":"2026-09-24T17:04:43.540345+00:00","duration_secs":30468.0,"tool_calls":513,"handoffs":2,"total_cost_usd":60.099062,"agent_costs":{"claim_matcher":0.050491,"judge":1.341936,"learning_policy":0.023881,"repro":56.84025,"support":0.10701,"vuln_variant":1.735494},"cost_breakdown":{"claim_matcher":{"gpt-5.4-mini-2026-03-17":0.050491},"judge":{"gpt-5.6-sol":1.341936},"learning_policy":{"gpt-5.4-mini-2026-03-17":0.023881},"repro":{"accounts/fireworks/models/kimi-k3":56.84025},"support":{"accounts/fireworks/models/kimi-k3":0.10701},"vuln_variant":{"accounts/fireworks/models/kimi-k3":1.735494}},"vulnerable_version_variant_outcome":"unknown","fix_bypass_outcome":"unknown","variant_disclosure_state":"unknown","quality":{"confidence":"high","idempotent_verified":false,"community_verifications":0},"evidence":{"workflow":{"profile":"known_vulnerability","schema_version":2,"stages":["support","claim_contract","repro","judge","vuln_variant"]}},"environment":{"sandbox_image":"ghcr.io/n3mes1s/pruva-sandbox@sha256:8096b2518d6022e13d68f885c3b8ded6b4fe607098b1a1ccbfb99abc004d1dc1"},"published_at":"2026-09-24T17:04:45.251035+00:00","retracted":false,"artifacts":[{"path":"bundle/repro/rca_report.md","filename":"rca_report.md","size":16255,"category":"analysis"},{"path":"bundle/repro/reproduction_steps.sh","filename":"reproduction_steps.sh","size":33759,"category":"reproduction_script"},{"path":"bundle/logs/escalation_freeptr/e11_oracle.txt","filename":"e11_oracle.txt","size":294,"category":"other"},{"path":"bundle/logs/escalation_multibyte/e1.psql.txt","filename":"e1.psql.txt","size":653,"category":"other"},{"path":"bundle/logs/fixed_attempt_1/range_ref.txt","filename":"range_ref.txt","size":83,"category":"other"},{"path":"bundle/logs/fixed_attempt_1/server.txt","filename":"server.txt","size":3357,"category":"other"},{"path":"bundle/logs/fixed_attempt_2/range_ref.txt","filename":"range_ref.txt","size":83,"category":"other"},{"path":"bundle/logs/fixed_attempt_2/server.txt","filename":"server.txt","size":3357,"category":"other"},{"path":"bundle/logs/rce/finale_fixed.psql.txt","filename":"finale_fixed.psql.txt","size":344,"category":"other"},{"path":"bundle/logs/rce/leak_1.txt","filename":"leak_1.txt","size":13,"category":"other"},{"path":"bundle/logs/rce/leak_2.txt","filename":"leak_2.txt","size":13,"category":"other"},{"path":"bundle/logs/rce/leak_4.txt","filename":"leak_4.txt","size":13,"category":"other"},{"path":"bundle/logs/rce/leak_5.txt","filename":"leak_5.txt","size":13,"category":"other"},{"path":"bundle/logs/rce/leak_6.txt","filename":"leak_6.txt","size":13,"category":"other"},{"path":"bundle/logs/rce/leak_7.txt","filename":"leak_7.txt","size":13,"category":"other"},{"path":"bundle/logs/rce/leak_8.txt","filename":"leak_8.txt","size":13,"category":"other"},{"path":"bundle/logs/rce/maps_finale_x.txt","filename":"maps_finale_x.txt","size":20541,"category":"other"},{"path":"bundle/logs/rce/maps_finale_y.txt","filename":"maps_finale_y.txt","size":20541,"category":"other"},{"path":"bundle/logs/rce/randomize_va_space.txt","filename":"randomize_va_space.txt","size":2,"category":"other"},{"path":"bundle/logs/rce/readelf_fixed.txt","filename":"readelf_fixed.txt","size":926284,"category":"other"},{"path":"bundle/logs/rce/readelf_vuln.txt","filename":"readelf_vuln.txt","size":925451,"category":"other"},{"path":"bundle/logs/vulnerable_attempt_1/wraparound.txt","filename":"wraparound.txt","size":50,"category":"other"},{"path":"bundle/logs/vulnerable_attempt_2/psql.txt","filename":"psql.txt","size":167,"category":"other"},{"path":"bundle/logs/vulnerable_attempt_2/wraparound.txt","filename":"wraparound.txt","size":50,"category":"other"},{"path":"bundle/repro/runtime_manifest.json","filename":"runtime_manifest.json","size":5376,"category":"other"},{"path":"bundle/repro/validation_verdict.json","filename":"validation_verdict.json","size":1883,"category":"other"}]}