russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
142 lines
5.2 KiB
ReStructuredText
142 lines
5.2 KiB
ReStructuredText
PostgreSQL — CWE-407 Analysis
|
||
==============================
|
||
|
||
.. contents:: :local:
|
||
|
||
Overview
|
||
--------
|
||
|
||
PostgreSQL's query planner is a cost-based optimizer that performs join ordering,
|
||
equivalence class reasoning, target list construction, and join elimination. The
|
||
planner is implemented in C and uses PostgreSQL's own ``List`` type (a singly-linked
|
||
list of ``void *`` cells) with O(n) membership functions: ``list_member()``,
|
||
``list_member_ptr()``, ``list_member_int()``, ``list_member_oid()``, and
|
||
``list_member_xid()``.
|
||
|
||
**Status: 5 confirmed defects — all unpatched**
|
||
|
||
The scanner used pg-specific patterns (``list_member*`` membership tests, ``foreach``
|
||
loop macro) rather than generic C patterns. 58 candidates were identified; 5 confirmed
|
||
as true CWE-407 defects in hot planner paths. PostgreSQL developers independently
|
||
acknowledged the O(n²) risk in ``execExpr.c:626`` (patched locally with bitmapset)
|
||
— confirming the pattern is real and known to the project.
|
||
|
||
Confirmed Defects
|
||
-----------------
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
:widths: 15 35 20 15 15
|
||
|
||
* - ID
|
||
- File:Line
|
||
- Pattern
|
||
- Complexity
|
||
- Severity
|
||
* - postgresql-0001
|
||
- ``optimizer/util/tlist.c:812``
|
||
- ``tlist_member`` in sort/group labeling foreach
|
||
- O(sort_keys × width)
|
||
- HIGH
|
||
* - postgresql-0002
|
||
- ``optimizer/prep/preptlist.c:180,206,316``
|
||
- ``tlist_member`` in MERGE/UPDATE target dedup (3 loops)
|
||
- O(W² × C²) for MERGE
|
||
- HIGH
|
||
* - postgresql-0003
|
||
- ``optimizer/path/equivclass.c:1041``
|
||
- ``list_member`` in equivalence class var matching
|
||
- O(M × E) per class
|
||
- HIGH
|
||
* - postgresql-0004
|
||
- ``optimizer/util/analyzejoins.c:1914``
|
||
- ``list_member`` in join elimination expr merge
|
||
- O(E²) per eliminated join
|
||
- HIGH
|
||
* - postgresql-0005
|
||
- ``nodes/list.c:1077-1478``
|
||
- ``list_union``, ``list_intersect``, ``list_difference``
|
||
- O(|a| × |b|) per call
|
||
- MEDIUM
|
||
|
||
Developer Acknowledgment
|
||
------------------------
|
||
|
||
A PostgreSQL developer commented in ``execExpr.c:626``::
|
||
|
||
/* Using list_member_int() tests, but that risks O(N^2) behavior with many columns */
|
||
|
||
That site was subsequently patched with ``bitmapset``. The five sites above were not
|
||
caught in the same pass — confirming they are unaddressed.
|
||
|
||
Threat Model
|
||
------------
|
||
|
||
All five defects are triggered at **planning time** — before execution begins. For
|
||
OLTP queries the planner is amortized over many executions via plan caching. For
|
||
ad-hoc analytical queries, uncached plans are regenerated on every execution.
|
||
|
||
Worst-case scenarios:
|
||
|
||
- **MERGE with many WHEN clauses** (postgresql-0002): PostgreSQL 15+ feature, upsert-heavy
|
||
workloads. W=50 WHEN clauses × C=20 columns → O(W²×C²) ≈ 10⁶ membership tests per plan.
|
||
- **Star schema with many equivalence members** (postgresql-0003): analytical databases
|
||
with wide dimension tables. K equivalence classes × M=20 members × E=20 exprvars → O(K×400).
|
||
- **Views with many columns + self-join** (postgresql-0004): joins against wide views
|
||
trigger join elimination on every query. E=50 projected columns → 2,500 list_member calls.
|
||
|
||
Fix Pattern
|
||
-----------
|
||
|
||
All five defects follow the same fix pattern:
|
||
|
||
1. Before the ``foreach`` loop, build an O(1) membership structure:
|
||
|
||
- For Var nodes: ``Bitmapset *`` keyed on ``varattno`` (already used by PG)
|
||
- For expression pointer identity: pointer-identity hash set (palloc'd)
|
||
- For int/oid/xid variants: ``Bitmapset *`` or integer hash set
|
||
|
||
2. Replace ``list_member*(list, item)`` in the loop body with O(1) set lookup.
|
||
|
||
3. Free the temporary structure after the loop (palloc memory is freed with context).
|
||
|
||
PostgreSQL already has ``bitmapset.h`` and ``HTAB`` (hash table) as first-class
|
||
utilities — no new dependencies required.
|
||
|
||
False Positives Triaged
|
||
-----------------------
|
||
|
||
53 of 58 scanner candidates were false positives:
|
||
|
||
- **``execExpr.c:626``** — already patched by PG developers with bitmapset (O(1) check)
|
||
- **``nodeHashjoin.c``**, **``nodeNestloop.c``** — list traversal is the join execution
|
||
itself, not a membership test inside traversal
|
||
- **``ruleutils.c``**, **``deparse.c``** — display/deparse code, cold path
|
||
- **``pg_dump``** — dump utility, not query planner, not performance-critical
|
||
- Remaining 48 candidates — bounded input (typically < 10 elements) or genuinely cold paths
|
||
|
||
Scan Details
|
||
------------
|
||
|
||
Scanner: ``tools/scans/postgresql.sh``
|
||
|
||
Strategy: Lead with ``list_member*`` call sites, confirm ``foreach`` loop context
|
||
within ±20 lines. Inverted from generic C scanner because PG uses its own list API
|
||
(``foreach``/``lfirst``) rather than ``std::find`` or ``.count()``.
|
||
|
||
Directories scanned:
|
||
|
||
- ``src/backend/optimizer`` — query planner
|
||
- ``src/backend/nodes`` — node utilities including ``list.c``
|
||
- ``src/backend/rewrite`` — rule rewriter
|
||
- ``src/backend/executor`` — execution engine
|
||
- ``src/backend/parser`` — SQL parser
|
||
- ``src/backend/planner`` — (alias for optimizer in older PG layouts)
|
||
|
||
References
|
||
----------
|
||
|
||
* Tickets: postgresql-0001 through postgresql-0005
|
||
* Scanner: ``tools/scans/postgresql.sh``
|
||
* Developer acknowledgment: ``execExpr.c:626`` comment (bitmapset fix)
|
||
* PostgreSQL List API: ``src/include/nodes/pg_list.h``
|