Memory safety in C for pg_sift

The column engine and the BM25 readers decode bytes from disk. Every byte read goes through a length-carrying type (SiftSpan, src/core/span.h), arithmetic on stored sizes is checked, the compiler inserts what it can, and tools find the rest.

Threat model

Input Example Layers that catch it
Corrupt or malicious segment bytes (disk fault, hostile restore) a length, count, offset or code that points outside its buffer Span (at the read), sift_blob_check / sift.verify (structure, offline), fuzzers (before release), trap UBSan and FORTIFY (at run time, abort instead of exploit)
Hostile sizes (OOM) n = 16M rows in a 40-byte header, allocation before validation Span-first order (validate, then allocate), MaxAllocSize, per-open decompression budget
Concurrent modification a page changes between two reads of one header copy the header once into a local, then parse the copy; buffer locks (not a C-language issue)
Own bugs off-by-one in a SIMD tail, use after free in a memory context ASan/UBSan CI, fuzzers, Valgrind, PG debug build, static analysis

An attacker who can write a data file already owns the server (PostgreSQL trusts its data directory); the goal is that corruption becomes an ERROR (ERRCODE_DATA_CORRUPTED), never a wild read or write. The layers complement each other: Span checks what the code asks, ASan sees heap and stack but not an overrun inside one palloc chunk, trap UBSan sees array bounds of known size and pointer wrap, fuzzers find the unexpected.

Ranking (safety gain / cost; cost is instructions by cpu_gate, below; “pkg” is shipped in packages)

# Measure Gain Cost Where
1 SiftSpan for every stored offset/length; validate before allocate closes the P1/P2 class of the audits ~0 on parse paths, to be measured per converted decoder src/core/span.h, phase 2
2 Fuzz every decoder, corpus from tests, differential vs scalar 8 findings, 3 high CI minutes test/fuzz, scripts/fuzz.sh
3 SIFT_HARDEN=pkg: stack protector strong, stack clash, CET/branch protection, strict-flex-arrays=3, FORTIFY_SOURCE=3, relro/now stack smash, libc misuse, ROP 0.0 to +0.3% pkg
4 -ftrivial-auto-var-init=zero (SIFT_HARDEN=init) uninitialized stack and padding leaks +0.1 to +1.9% CI hardened; pkg optional
5 Trap UBSan bounds,shift,nonnull,returns-nonnull,vla-bound flexible/array overruns, bad shifts +1 to +5% (bounds), +2 to +4% (shift set) CI hardened
6 object-size trap pointer-to-object overruns +3 to +8% CI hardened
7 pointer-overflow trap (SIFT_POINTER_OVERFLOW=1) pointer wrap +9 to +36% separate opt-in, off in 1
8 Static analysis (scripts/static.sh) shallow bugs, widening multiplies none at run time CI static, non-blocking
9 Structural verifier (sift.verify) sharing the Span code offline detection none at run time phase 2
10 CBMC on Span and the chunk header parser; clang -fbounds-safety proof for small code; compiler-enforced bounds CBMC not used; bounds-safety blocked later
11 debug_discard_caches = 1 on a server with assertions (tests cache_discard, verify_relcache) a pointer into the relcache’s cached state (rd_amcache) kept across a lock or a catalog read: the entry is reloaded at every such point and the freed state is overwritten. Found the crash of , of sift.col_verify and of the cost estimate of a scan; each dies in seconds on a few rows cache_discard 48 s (0.5 s without the setting, about 30 ms per row), verify_relcache 2 s; 0 at run time the PostgreSQL 19 job of CI (a build with assertions) and the assert lane

Measured overhead

bench/steps/cpu_gate.sh: user-mode instructions per operation (8 rounds, 20k rows, 95% intervals under 1%), build with and without; wall time was not used (loaded host). BM25 cells: bulk, merge and the query classes count, rank, and, or, phrase. Column-scan cells: 5 pushdown queries (bench/cpu-query.sh, 100 queries, 5 rounds). Single checks ran on top of init.

Flag set BM25 cells Column scan Verdict
pkg 0.0 to +0.3% (bulk +0.3) 1.000 to 1.002 pkg: on
init +0.1 to +1.9% (merge +1.9, bulk +1.1) +0.1 to +0.4% CI; packages optional
1 as measured, with pointer-overflow +13 to +45% (bulk +45, merge +38) +14.5% to +62% (ts_group +62, filter_count +40) 1 now omits it: lower, not re-measured
bounds alone +1.0 to +4.8% not run off by default
shift,nonnull,returns-nonnull,vla-bound +0 to +3.7% not run off by default
object-size +2.7 to +8.1% not run off by default
pointer-overflow +9 to +36% (bulk +36, merge +27) not run opt-in only
ASan+UBSan (SANITIZE=1) not gated not gated CI sanitize flavor

Flags above 1% on hot loops are off by default and on in the hardened flavor (pointer-overflow only on request). signed-integer-overflow is not trapped (-fwrapv defines it). The Span is not measured yet (no decoder uses it); phase 2 measures each converted decoder with the same cells. Reproduce: bench/steps/cpu_gate.sh --env LABEL=SIFT_HARDEN=1.

What each knob is

SIFT_HARDEN=pkg|init|1 (scripts/harden.mk, included by the Makefile) probes every flag with the host compiler and drops unknown ones. SIFT_UBSAN_SET="bounds shift" (or comma list) picks the trap checks and SIFT_POINTER_OVERFLOW=1 adds the pointer-wrap trap; scripts/pgtest.sh passes them. pkg also adds -Wvla -Walloca -Warray-bounds=2 -Wstringop-overflow=4 -Wformat=2 -Wundef. -Wconversion (474 hits) and -Wsign-conversion (1306) are too noisy to enable; -Wnull-dereference (36) and -Wclobbered (2, see the findings) merit a one-time read.

scripts/check-memory.sh (lint, with a selftest; check-memory: allow <why> on a site) flags what a grep can decide: rd_amcache outside the files that own an accessor of it, and an inclusive for loop over a 64-bit counter (it never ends when the bound is the largest value, the key loop of the point directory).

CI (scripts/ci.sh): hardened (scripts/hardened.sh: private copy built with SIFT_HARDEN=1, 16 decoder regress tests), static, span-test (sqlite/tests/span_test.c, ASan/UBSan, SIMD=none), fuzz (scripts/fuzz.sh). Opt-in lanes on a PostgreSQL built from source (make pg-assert, make pg-valgrind, PG_ASSERT_MAJOR=17 for the 17 branch; scripts/pg-assert.sh pins 18.6 and 17.11 with cassert, debug, -DRANDOMIZE_ALLOCATED_MEMORY, -DCATCACHE_FORCE_RELEASE (every syscache lookup builds a fresh entry and frees it at release, so a HeapTuple kept past its ReleaseSysCache is garbage; found F-MCX-1), plus -DUSE_VALGRIND for the valgrind prefix; cached in $SIFT_PG_CACHE, default ~/.cache/sift/pg): - SIFT_CI_JOBS=assert scripts/ci.sh quick (scripts/assert.sh): 13 regression tests and 2 quick-tier TAP tests; fails on a TRAP or a memory-context warning in any server log; passes on 18.6 and 17.11. The server of the lane is built with --enable-injection-points (scripts/pg-assert.sh --inject, the prefix <version>-assert-inject), so a shell TAP test can stop a backend at a named point of the code without a sleep: maint_lock_order stops a maintenance worker before and after it locks the table of its index and runs DROP TABLE beside it (no deadlock, no error, the index gone is not an error). Ownership asserts of the testing build: every slot of an executor state’s table is in the query memory context (checked at ExecutorEnd, self-test slot_owner: a table slot made in a node’s context is the crash of a cold backend), and a worker holds the table before the index it opens (sift_try_open_index: lock order of the statements, Assert on CheckRelationOidLockedByMe). - SIFT_CI_JOBS=valgrind (scripts/valgrind.sh): 4 tests under memcheck with the server’s valgrind.supp and --error-exitcode, bounded by SIFT_VALGRIND_TIMEOUT; a host whose glibc has no debug symbols runs it in a pinned Debian bookworm container (see the script header); skips when neither works. - Weekly and non-blocking on GitHub: .github/workflows/assert.yml. The quick tier of ci.yml has one assertions entry (“PostgreSQL 18 (assertions)”, the 30 installcheck-agg_* regress tests of the planner paths: cte, cost, scope, lateral, subplan, placeholder; the whole installcheck-agg* set takes 61 minutes there): planner asserts (a foreach_node cast of the wrong node type, found on PostgreSQL 19 first) exist only in a --enable-cassert build, which the distribution packages of 17 and 18 lack.

Tools (gcc 16.2, clang 23.1)

Used: clang-tidy, scan-build, gcc -fanalyzer, libFuzzer, MSan and UBSan-minimal runtimes, valgrind 3.25, perf. Not used: cppcheck (scripts/static.sh skips it when absent), CBMC, ESBMC, Frama-C, CodeQL, AFL++. - clang -fbounds-safety (__counted_by, __sized_by, __indexable): clang 23 only has -Xclang -fexperimental-bounds-safety, no <ptrcheck.h>, and a one-function probe did not build; Apple’s clang ships it. Not usable on the Debian/RPM/AUR toolchains. - counted_by on flexible array members: gcc 15+ and clang 18+; with -fsanitize=bounds the access traps (verified with gcc 16). Applies to 5 sites only (src/core/page.h x3, src/bm25/parallel.h, src/col/batch.c); the pgsql-hackers thread “Add counted_by attribute” is the PostgreSQL-side attempt (it found write-order problems under bounds checking). Low value: decoders mostly walk byte buffers. - PostgreSQL aids: --enable-cassert implies MEMORY_CONTEXT_CHECKING and CLOBBER_FREED_MEMORY (they catch palloc overruns ASan cannot); the assert and valgrind lanes above use them. amcheck is the model for sift.verify. - MSan: only for the standalone fuzz targets, with every dependency instrumented (zstd/lz4/libpgcommon are not: DEFS= COLZ=, false positives in libc wrappers). - MTE (arm64) and CHERI: hardware tag/capability checks; no toolchain in the distro targets. - Rust: not recommended now. pgrx would replace the C ABI of the access methods and the portable core shared with SQLite and MariaDB; possible later for a standalone decoder crate behind a C ABI and cbindgen, with the Span semantics as its contract.

Packages (Debian/RPM/AUR) use SIFT_HARDEN=pkg (FORTIFY needs -O2; aarch64 gets -mbranch-protection instead of CET); init and above stay off.

Coverity Scan

.github/workflows/coverity.yml (weekly and on demand) builds under cov-build and uploads to scan.coverity.com; without the secrets it does nothing and passes. Setup: (1) sign in at https://scan.coverity.com with the GitHub account and add the public repository as a project (C/C++; project name owner/repo, or set the repository variable COVERITY_SCAN_PROJECT); (2) copy the project token from Project Settings; (3) add the Actions secrets COVERITY_SCAN_TOKEN (that token) and COVERITY_SCAN_EMAIL (the email of the account that owns the project); (4) run the workflow once from the Actions tab (workflow_dispatch needs the workflow on the default branch); (5) triage the defects at scan.coverity.com. Coverity limits builds per day.

Phase 2: conversion list (31 entries)

P1 out-of-bounds from stored data, P2 unbounded loop or allocation, P3 correct hand-written checks to move onto Span, P4 hygiene. Each item: raw offset arithmetic becomes sift_span_sub/array/take/read_*, validate before allocate, raise DATA_CORRUPTED.

Id File:function Gap and replacement
P1-1 bm25/bitmap.c:sift_cur_blob, gr_seek, ls_seek, ef_hdr, ef_decode, ls_at query path decodes unchecked blobs (F-BM25-2/¾, fixed by explicit checks in 2.0.2, 463951f; the Span conversion is open): cursor over a Span, per-group sub-span, lazy check_grouped rules
P1-2 bm25/bitmap.c:sift_chunk_pagemask/offsets/count (called by bm25/segment.c:load_sb) no length argument; pass sift_span_sub(rec,8,h[1]), require w in {1,2,4,8..64}, pg<256
P1-3 bm25/segment.c:load_sb; bm25/walk.c:walk_docs; bm25/liveness.c:live_sb_bits ndocs from mask popcounts never compared with the header; keys[] overflow
P1-4 col/scan_unit.c:unit_group, col/scan_read.c:sift_col_read; col/batch.c:sift_cunit_decode uint32 group-count sum wraps, expand_parents writes far past parent: uint64 sum, reject outside [0,n], total equals child n
P1-5 col/ctest.c:chunk_lut, cc_lut done (F-COL-1): tables of at most 16 bits cover the width, wider codes pass max32(codes) < sbits
P1-6 col/scan_read.c:read_positions (STR), sift_col_read_lane (CODE lane) done: max32(codes) <= dict->n once per chunk read, before agg/agg.c indexes map[code] or the LUT
P1-7 table/wbuf.c:sift_tbl_delta_page, link_delta_page disk npages copied into a 1024 array
P1-8 table/wbuf.c:sift_tbl_page_rec and callers (scan, seg, vacuum) slot offsets unchecked, VACUUM writes there: return a record Span
P1-9 table/wbuf.c:sift_tbl_rec_tuple rec->len unchecked vs page, t_len; overflow chain without hop limit
P2-1 bm25/posting.c:post_attach, sift_post_group_tf, list_tf_pos nnib/df/ng/esc length raw (F-BM25-5, fixed by explicit checks in 3.0.0, 7f59d1a; the Span conversion is open): carve sidecar Spans at attach
P2-2 bm25/posting.c:post_open; bm25/dict.c:sift_dict_open; bm25/segment.c:docmap, load_sb; bm25/walk.c:walk_docs allocation before validation (up to 32 GB)
P2-3 bm25/rank.c:score_block offsets not ANDed with present: knorm reads past the row
P2-4 bm25/segment.c:sift_seg_open; bm25/dict.c:sift_dict_open; col/seg/seg.c:sift_cseg_open u64 off+len can wrap; section ends not checked against the stream. The pre-aggregate sums and cubes of col/seg/seg.c are compared without a wrapping sum; every read is bounded by sift_sr_get
P2-5 core/live.c:sift_live_clear page index and write unchecked (Assert only)
P2-6 core/tomb.c:sift_tomb_sync nent unchecked; next chain can cycle
P2-7 col/codec_parse.c:sift_cc_open, parse_node row count compared after the whole tree is built: pass expected n in. Done: sift_cc_open_rows
P2-8 col/codec_parse.c:parse_node WRAP decompression total not capped: per-open byte budget
P2-9 col/codec_blob.c:sift_cc_decode_strs total allocated before the lengths are summed. Done for the count and the raw form (sift_cc_decode_strs takes the expected n); total of a compressed list stays bounded by 231 and the allocation limit
P2-10 col/seg/seg.c:sift_cseg_unit, sift_cseg_unit_head unit buffer lacks SIFT_COL_PAD; unpack reads 31 bytes past
P2-11 col/enc.c:sift_cchunk_zone, col/ctest.c:chunk_scalar palloc((n+8)*8) with header n up to 228
P3-1 col/codec_parse.c:parse_node, parse_child, sift_cc_open, col/codec_blob.c:sift_cc_decode_bits hand-written need() checks: move to take/sub/read_u32le
P3-2 col/chunk.c:sift_cchunk_parse, col/unit.c:unit_parse, col/dict/dict.c:sift_cdict_parse, col/schema.c:sift_cschema_parse nulls/ovf/nbytes set before the check; plain memcpy
P3-3 col/seg/seg.c:sift_cseg_open, sift_cseg_dict, zone_arrays manual arithmetic; one 7-byte over-read at 429/441
P3-4 col/compress.c:sift_colz_decompress (int) truncation of clen/rawlen: reject above INT_MAX
P3-5 core/reader.c:sift_sr_get, sr_bytes, sift_sr_init correct; return a SiftSpan so callers inherit the bound
P3-6 bm25/dict.c:block_begin, block_next, find_block correct; pos_len points into the shared buffer: take/read_varint
P3-7 bm25/pos.c:pos_next, pos_window, pos_ckpt; bm25/posting.c:BLOB_NG/BLOB_KEYS; bm25/segment.c:docmap; core/store.c:check_dir; bm25/wbuf.c:rec_at correct; macros become sift_span_u32le_at, rest for uniformity
P3-8 real range checks: nd_get DICT, unit_emit, sift_cc_decode_bits, sparse_valid plain bound or max32, not Span
P4-1 core/varint.h:sift_get_varint (bm25/bitmap.c 86,470,504,608,909) unbounded, safe only by 64 pad bytes (F-BM25-1): no caller of the unbounded sift_get_varint was left since 2.0.2 (463951f, 0ddff29), and the function is deleted; Span read_varint for the bounded ones
P4-2 core/varint.h:sift_get_varint64_n, bm25/pos.c:get_v32, sift_post_positions last-byte overflow bits dropped, want*=2 wraps above 2 GB: reject
P4-3 col/unit.c:sift_cunit_chunk; col/seg/seg.c:sift_cseg_unit_fill; col/scan/scan.c 584, 621, 871 XX000 to DATA_CORRUPTED (F-COL-2: done for sift_cunit_chunk); off+len Assert only; scattered c.n checks into sift_cunit_chunk

Also: extend sift.verify (src/bm25/segment_sql.c) to run the same Span parsers and the P1-3 popcount check, cross-check DICTIDX against the dictionary blocks. Not audited: bm25/docdir.c, core/lane.c, rest of bm25/wbuf.c, bm25/cscan.c, sift_cscan consumers.

Decisions

Decided: assert and valgrind lanes, Coverity Scan, pointer-overflow out of 1, and the fix of F-BM25-2/3 and F-COL-1 (reachable from a corrupt page on the query path) ahead of the full conversion (done: F-BM25-2/3 in 2.0.2, F-COL-1 in 3.0.0). Open: 1. Accept up to 1% instructions on column-scan and BM25 cells per converted decoder?

Sources

clang bounds-safety https://clang.llvm.org/docs/BoundsSafety.html, UBSan https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html, libFuzzer https://llvm.org/docs/LibFuzzer.html, gcc counted_by https://gcc.gnu.org/onlinedocs/gcc/Common-Attributes.html, FORTIFY_SOURCE=3 https://developers.redhat.com/articles/2022/09/17/gccs-new-fortification-level, OpenSSF flags https://best.openssf.org/Compiler-Hardening-Guides/Compiler-Options-Hardening-Guide-for-C-and-C++.html, counted_by https://opensource.googleblog.com/2024/07/bounds-checking-flexible-array-members.html, amcheck https://www.postgresql.org/docs/current/amcheck.html, Valgrind https://wiki.postgresql.org/wiki/Valgrind, CBMC https://www.cprover.org/cbmc/, Frama-C WP https://frama-c.com/fc-plugins/wp.html, Coverity Scan https://scan.coverity.com/, MTE https://developer.arm.com/documentation/108035/, CHERI https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/, pgrx https://github.com/pgcentralfoundation/pgrx.