java-topology/docs/tickets/hurd-0006.md

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.

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.