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

hurd-0004 — CWE-407: check_owner → check_uid — O(nuids²) double UID scan

Severity: LOW-MEDIUM Files: proc/info.c lines ~47–67, proc/mgt.c lines ~84–92 Functions: check_owner, check_uid CWE: CWE-407 Algorithmic Complexity

Defect

check_owner(proc1, proc2) verifies proc1 holds every UID proc2 holds. Outer loop over proc2's UIDs, inner check_uid() linearly scans proc1's UIDs.

// check_owner — proc/info.c ~65
for (size_t i = 0; i < proc2->p_id->i_nuids; i++)
  if (!check_uid(proc1, proc2->p_id->i_uids[i]))   // O(k) linear scan
    return 0;

// check_uid — proc/mgt.c ~88
for (i = 0; i < p->p_id->i_nuids; i++)
  if (p->p_id->i_uids[i] == uid || p->p_id->i_uids[i] == 0)
    return 1;

Complexity: O(nuids_proc2 × nuids_proc1). With N = total UIDs per process, O(N²).

Scale

N is small in practice (≤64 UIDs), but called on every proc_pid2task, proc_pid2proc, proc_proc2task — every kill(), waitpid(), ptrace(), and task port request.

Fix

Sort proc1's UID array once and use binary search for O(log N) lookup per check, giving O(N log N) total. Or maintain a small bitset for O(1) lookup when UID range is bounded.