32 lines
1.2 KiB
Markdown
32 lines
1.2 KiB
Markdown
# 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.
|
||
|
||
```c
|
||
// 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.
|