32 lines
979 B
Markdown
32 lines
979 B
Markdown
# hurd-0006 — CWE-407: idvec_merge_ids — O(N×k) deduplication scan
|
||
|
||
**Severity:** MEDIUM
|
||
**File:** `libshouldbeinlibc/idvec.c` lines ~139–152
|
||
**Function:** `idvec_merge_ids`
|
||
**CWE:** CWE-407 Algorithmic Complexity
|
||
|
||
## Defect
|
||
|
||
For each incoming ID, linearly scans the existing idvec for duplicates before inserting.
|
||
|
||
```c
|
||
while (num-- > 0 && !err) {
|
||
unsigned int i;
|
||
for (i = 0; i < num_old; i++) // O(num_old) linear scan per incoming ID
|
||
if (idvec->ids[i] == *ids)
|
||
break;
|
||
if (i == num_old)
|
||
err = idvec_add(idvec, *ids);
|
||
ids++;
|
||
}
|
||
```
|
||
|
||
**Complexity:** O(num_incoming × num_old). Merging two idvecs of size k: O(k²).
|
||
|
||
## Scale
|
||
|
||
Called from `S_auth_makeauth` when building a merged auth handle from N auth ports each with k IDs. Total merge cost: O(nauths × k²). Compounds hurd-0001.
|
||
|
||
## Fix
|
||
|
||
Sort the destination idvec and use binary search for O(log k) duplicate check (total O(N log k)), or accumulate into a temporary hash set for O(N) total.
|