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

4.1 KiB

Raw Permalink Blame History

Ktor CWE-407 Scan — CLEAN

Date: 2026-03-29 Target: Ktor framework (~/git/ktor/) Language: Kotlin Version: main branch (depth-1 clone)

Scan Scope

Area	Files Checked
Server core	`ktor-server/ktor-server-core/common/src/io/ktor/server/routing/` (RoutingResolveContext, RouteSelector, HostsRoutingBuilder, RoutingBuilder), `response/ResponseHeaders.kt`, `engine/BaseApplicationResponse.kt`
HTTP layer	`ktor-http/common/src/io/ktor/http/` (HttpHeaders, ContentTypes, HeaderValueWithParameters, HttpAuthHeader)
Plugins (server)	`ktor-server-content-negotiation` (RequestConverter, ResponseConverter), `ktor-server-cors` (CORS.kt, CORSUtils.kt, CORSConfig.kt), `ktor-server-auth` (Authentication, AuthenticationInterceptors)
Plugins (client)	`ktor-client-core/common/src/io/ktor/client/engine/HttpClientEngine.kt`, `ktor-client-plugins/ktor-client-auth/`
Utilities	`ktor-utils/common/src/io/ktor/util/StringValues.kt`, `ktor-utils/common/src/io/ktor/util/CaseInsensitiveSet.kt`
WebSockets	`ktor-shared/ktor-websockets/common/src/io/ktor/websocket/WebSocketExtension.kt`

Methodology

Searched for Kotlin List.contains(), Collection.contains(), .indexOf(), .indexOfFirst(), and .any { it == x } calls nested inside per-request loops. Verified the backing type of each collection at the declaration site.

Findings

Location	Pattern	Collection / Backing Type	Verdict
`HttpHeaders.kt:139`	`UnsafeHeadersArray.any { it.equals(header) }`	`Array<String>` of exactly 2 elements	O(2) = constant
`HttpClientEngine.kt:188–190`	`for (ext in requiredCapabilities) { supportedCapabilities.contains(ext) }`	`supportedCapabilities: Set<HttpClientEngineCapability<*>>`	O(1)
`CORS.kt:66–78`	`hostsNormalized` and `hostsWithWildcard` lookups per request	Both `HashSet<>`	O(1)
`CORSUtils.kt:104–105`	`requestHeaders.all { header in allHeadersSet }`	`allHeadersSet: Set<String>`	O(1) per lookup
`ContentTypes.kt:84–105`	`for (patternName in pattern.parameters) { parameter(patternName) }` — inner scan of `this.parameters`	`List<HeaderValueParam>`, Content-Type params bounded at 1-3 entries	O(P²) where P ≤ 3: effectively constant
`HttpAuthHeader.kt:318`	`parameters.indexOfFirst { it.name == name }`	Called once per challenge construction, not in per-request loop	O(P) isolated
`ResponseConverter.kt:53–55`	`acceptItems.flatMap { registrations.filter { it.contentType.match(contentType) } }`	O(A×R): A ≤ 5 Accept types, R ≤ 3 registrations	O(15) effectively constant
`StringValues.kt`	Key lookup via `listForKey(name)`	Hash table (open-addressing with `hashBuckets`/`hashNext`)	O(1)
`ResponseHeaders.kt:63`	`managedByEngineHeaders.contains(name)`	`Set<String>`	O(1)

Notable Non-Defects

HttpHeaders.isUnsafe(): UnsafeHeadersArray is a 2-element compile-time constant array. Even though it is scanned linearly, the bound is fixed at 2 and will never grow with request load.
ContentType.match() (ContentTypes.kt:84): Outer loop over pattern.parameters, inner parameter() scans this.parameters. Both are Content-Type parameter lists, bounded in practice to 2-3 entries (e.g., charset=utf-8, boundary=xxx).
ResponseConverter.kt:53–55: acceptItems.flatMap { registrations.filter { ... } } is O(A×R). Both A (Accept header items) and R (content negotiation registrations) are tiny in all real deployments. The subsequent .distinct() uses Kotlin's LinkedHashSet-backed dedup.

Result

CLEAN — no CWE-407 defects confirmed in Ktor.

The codebase uses hash-backed sets (Set<>, HashSet<>, CaseInsensitiveSet) for all membership checks in hot per-request paths. The few cases of linear list scan (isUnsafe, parameter(), withReplacedParameter) operate on collections bounded by a small protocol-defined constant.

CORSConfig.kt: CaseInsensitiveSet (Set impl) — O(1)
CallId.kt: dictionarySet: Set — O(1)

Scan date: 2026-03-29

4.1 KiB Raw Permalink Blame History Unescape Escape