russell@unturf.com a629bd0bbf no-stone-unturned wave: 8 new defects, 15 CLEAN confirmations; count 621→629

New defects (all PASS):
- exim-0001: same_hosts() MX-segment O(H²) → AVL set O(H log H), 10.5x at H=20
- minecraft-0001: DependencySorter.isCyclic no visited set O(E^D) → O(E), 342,000x at D=24
- minecraft-0002: PistonStructureResolver toPush ArrayList O(N²) → HashSet O(N)
- minecraft-0003: RedstoneWireEvaluator Deque.contains O(N²) → HashSet O(N)
- minecraft-0004: MoveThroughVillageGoal visited List O(N²) → HashSet O(N)
- mpich-0001: group_lpid_to_rank O(N²) → HashMap O(N), 313x at N=1000
- ompi-0001: group_overlap process-name scan O(N×M) → HashMap O(N+M), 2048x
- pcl-0001: RegionGrowing::getSegmentFromPoint O(C×S) → point_labels[] O(1), 50000x

CLEAN confirmed: esbuild, express, koa, ktor, lucene, mpich-recvq, ompi-startup,
  prosody, roda, rust/rustc-wave2, signal-server, solana, wiredtiger, wireguard-tools,
  linux-kernel (pointer to linux/)

2026-03-29 16:11:50 -04:00

3.8 KiB

Raw Permalink Blame History

Prosody CWE-407 Scan — CLEAN

Date: 2026-03-29 Target: Prosody XMPP server (~/git/prosody/) Language: Lua Version: main branch (depth-1 clone)

Scan Scope

Area	Files Checked
Core	`core/stanza_router.lua`, `core/moduleapi.lua`, `core/modulemanager.lua`, `core/portmanager.lua`, `core/sessionmanager.lua`, `core/hostmanager.lua`, `core/rostermanager.lua`, `core/certmanager.lua`, `core/storagemanager.lua`
Utilities	`util/events.lua`, `util/jsonschema.lua`, `util/x509.lua`, `util/datamanager.lua`
Plugins	`plugins/mod_authz_internal.lua`, `plugins/mod_roster.lua`, `plugins/mod_pep.lua`, `plugins/mod_pep_simple.lua`, `plugins/mod_http.lua`, `plugins/mod_s2s.lua`, `plugins/mod_bosh.lua`, `plugins/mod_saslauth.lua`, `plugins/mod_groups.lua`
Net	`net/websocket.lua`, `net/dns.lua`, `net/portmanager.lua`

Methodology

Searched for linear membership patterns in Lua: for k,v in pairs(t) do if v == x and table.remove() inside loops over the same list (O(N) shift per iteration = O(N²) total). Cross-referenced with Prosody's set utility to confirm hash-backed vs. array-backed membership checks.

Key Pattern: `set` module

Prosody's util/set.lua provides a hash-backed set type. Calls like set:contains(x) (x in set._items) are O(1). The codebase makes pervasive use of this throughout hot paths:

plugins/mod_authz_internal.lua: set.new(...) for role/permission dedup
plugins/mod_http.lua: app_headers:contains(header) — app_headers is a set
plugins/mod_pep.lua: nodes:contains(node), allowed_groups:contains(group) — both sets
plugins/mod_s2s.lua: cert_errors = set.new(), chain_errors = set.new()
plugins/mod_saslauth.lua: channel_bindings = set.new(), available_mechanisms = set.new()

Findings

Location	Pattern	Collection	Verdict
`util/events.lua:77–89`	`for i=1,#h do h[i](event_data)`	Pre-sorted array, no membership check	O(N) dispatch, expected
`core/moduleapi.lua:419–425`	`for i = #t,1,-1 do if t[i] == value then t_remove(...); return`	Removes first match then exits — O(N) scan, single remove	O(N), not O(N²)
`core/portmanager.lua:190–194`	`for i, service in ipairs(...) do ... table.remove(list, i)`	Removes first match then continues, list bounded to port services (small)	Not hot path
`plugins/mod_http.lua:210`	`if not app_headers:contains(header)` inside `for header, enable in pairs(cors.headers)`	`app_headers` is a `set` (hash-backed)	O(1) lookup
`plugins/mod_pep.lua:196`	`if nodes:contains(node)` inside `for recipient, nodes in pairs(...)`	`nodes` is a `set`	O(1) lookup
`util/jsonschema.lua:100–106`	`for _, v in ipairs(schema["enum"]) do if v == data`	Single validation call, not nested	O(E) isolated
`util/events.lua:137–139`	`for i = #w, 1, -1 do if w[i] == wrapper then t_remove(w, i)`	Wrapper removal — rare admin/config op, wrappers list tiny	Not hot path

Notable Non-Defects

core/moduleapi.lua:419 api:remove_item: Iterates the items list backward and calls t_remove(self.items[key], i) on first match, then return. The early return means it is O(N) not O(N²). No defect.
net/websocket.lua:196: Iterates a small protocol list (typically 1-3 elements) once to build a lookup table. Not nested.
util/events.lua fire_event: The hot dispatch path iterates a pre-sorted array of handlers. No membership checks inside the loop.

Result

CLEAN — no CWE-407 defects confirmed in Prosody.

The codebase makes consistent use of Prosody's hash-backed set module for membership checks in loops. The few cases of array iteration with equality checks (remove_item, wrapper removal) are on small collections in non-hot administrative paths.

3.8 KiB Raw Permalink Blame History Unescape Escape