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.
134 lines
5.1 KiB
ReStructuredText
134 lines
5.1 KiB
ReStructuredText
SQLite — CWE-407 Analysis
|
||
==========================
|
||
|
||
.. contents:: :local:
|
||
|
||
Overview
|
||
--------
|
||
|
||
SQLite is the most widely deployed database engine in the world, embedded in browsers,
|
||
mobile operating systems, and countless applications. Its query optimizer performs join
|
||
reordering, subquery flattening, and recursive CTE processing.
|
||
|
||
SQLite is implemented in C using array-backed list types (``ExprList``, ``SrcList``,
|
||
``IdList``) with O(n) membership functions: ``sqlite3ColumnIndex()`` (linear name scan
|
||
over table columns) and ``sqlite3IdListIndex()`` (linear name scan over an ``IdList``).
|
||
|
||
**Status: 2 confirmed defects — MEDIUM severity, all unpatched**
|
||
|
||
The main optimizer logic (``where.c``, the ``WhereLoop`` builder, join ordering) is clean:
|
||
it uses bitmask-backed ``Bitmask`` types for table and column tracking. The defects are
|
||
concentrated in DML support and join resolution paths.
|
||
|
||
Confirmed Defects
|
||
-----------------
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
:widths: 15 35 25 10 15
|
||
|
||
* - ID
|
||
- File:Line
|
||
- Pattern
|
||
- Complexity
|
||
- Severity
|
||
* - sqlite-0001
|
||
- ``src/trigger.c:792``
|
||
- ``sqlite3IdListIndex`` in ``checkColumnOverlap`` foreach SET cols
|
||
- O(|SET| × |trigger_cols|)
|
||
- MEDIUM
|
||
* - sqlite-0002
|
||
- ``src/select.c:575-617``
|
||
- ``sqlite3ColumnIndex`` × 2 in NATURAL JOIN / USING loop
|
||
- O(|USING| × |tables| × |cols|)
|
||
- MEDIUM
|
||
|
||
Defect Detail — sqlite-0001
|
||
----------------------------
|
||
|
||
``checkColumnOverlap()`` in ``trigger.c`` determines whether an UPDATE's SET clause
|
||
touches any column in a trigger's column-list condition::
|
||
|
||
for(e=0; e<pEList->nExpr; e++){
|
||
if( sqlite3IdListIndex(pIdList, pEList->a[e].zEName)>=0 ) return 1;
|
||
}
|
||
|
||
``sqlite3IdListIndex`` is a sequential string-comparison loop (O(|pIdList|)). The outer
|
||
``for`` loop is O(|pEList->nExpr|). Combined: O(|SET_cols| × |trigger_cols|).
|
||
|
||
This is called by ``triggersReallyExist()`` on **every INSERT, UPDATE, and DELETE**
|
||
to determine which triggers fire. For a table with W trigger-watched columns and an
|
||
UPDATE with S SET columns: O(S × W) string comparisons per DML statement.
|
||
|
||
**Fix:** Build a case-insensitive hash set over ``pIdList`` names before the loop;
|
||
O(1) per SET column. SQLite's ``Hash`` type (already used in the codebase) suffices.
|
||
|
||
Defect Detail — sqlite-0002
|
||
----------------------------
|
||
|
||
In ``addWhereTerm()`` / ``sqliteProcessJoin()`` for NATURAL JOIN and JOIN ... USING,
|
||
each USING column triggers::
|
||
|
||
iRightCol = sqlite3ColumnIndex(pRightTab, zName); /* O(right_cols) */
|
||
tableAndColumnIndex(pSrc, 0, i, zName, &iLeft, &iLeftCol, ...); /* O(tables × cols) */
|
||
|
||
Both calls are inside ``for(j=0; j<pList->nId; j++)`` over USING clause columns.
|
||
Combined: O(|USING_cols| × |tables| × |max_cols_per_table|).
|
||
|
||
For a NATURAL JOIN on two 50-column tables: O(50 × 2 × 50) = 5,000 string comparisons.
|
||
All comparisons use ``sqlite3StrICmp`` (case-insensitive string compare).
|
||
|
||
**Fix:** Pre-build a name → column-index hash map for each participating table before
|
||
the USING loop; O(1) lookup per column name.
|
||
|
||
False Positives Triaged
|
||
-----------------------
|
||
|
||
The scanner returned 7 candidates from ``WalkExprList`` cross-matching — all false
|
||
positives:
|
||
|
||
- ``alter.c:938`` — sequential ``WalkExprList`` then separate loop (not nested)
|
||
- ``alter.c:1475`` — trigger step walker, no membership test, pure traversal
|
||
- ``select.c:7496`` — outer join table-function arg walker, no membership test
|
||
- ``select.c:7520`` — ``sqlite3CopySortOrder``: two equal-length lists, positional copy
|
||
- ``walker.c:110,173`` — ``sqlite3WalkExprList`` implementation itself (inner loop body)
|
||
- ``window.c:901`` — ``exprListAppendList``: copy with duplication, no membership test
|
||
|
||
Additional low-severity sites NOT promoted to defects:
|
||
|
||
- ``insert.c:1086`` — ``sqlite3ColumnIndex`` in INSERT column mapping: O(|cols|²) for
|
||
INSERT with explicit column list, but bounded (schema width) and not hot.
|
||
- ``update.c:476`` — same pattern for UPDATE column mapping.
|
||
- ``build.c:1555`` — ``sqlite3ColumnIndex`` duplicate check in CREATE TABLE: O(N²)
|
||
over N columns, but DDL cold path.
|
||
|
||
Optimizer Core — CLEAN
|
||
-----------------------
|
||
|
||
SQLite's ``where.c`` (the core join optimizer) is clean:
|
||
|
||
- Table membership: ``Bitmask`` — one bit per table index, O(1) bitwise AND
|
||
- Column tracking: ``Bitmask`` — same mechanism
|
||
- ``WhereLoop`` selection: cost-based, no list membership
|
||
- ``WITH RECURSIVE`` cycle detection: ``sqlite3_exec`` row-level deduplication via
|
||
ephemeral table hash, not a list scan
|
||
|
||
The main optimizer avoids the defect pattern by design.
|
||
|
||
Scan Details
|
||
------------
|
||
|
||
Scanner: ``tools/scans/sqlite.sh``
|
||
|
||
Strategy: Lead with ``sqlite3ExprListFind``, ``sqlite3IdListIndex``, and
|
||
``for(i<->nExpr/nSrc/nId)`` patterns; confirm loop context within ±20 lines.
|
||
Follow-up targeted search for ``sqlite3ColumnIndex`` and ``sqlite3IdListIndex``
|
||
call sites with outer loop context.
|
||
|
||
References
|
||
----------
|
||
|
||
* Tickets: sqlite-0001, sqlite-0002
|
||
* Scanner: ``tools/scans/sqlite.sh``
|
||
* SQLite List API: ``src/sqliteInt.h`` — ``ExprList``, ``SrcList``, ``IdList``
|
||
* SQLite Hash API: ``src/hash.h``, ``src/hash.c``
|