java-topology/defects/wine-0004/TICKET.md

wine-0004 — CWE-407: Token Privilege Linear Scan O(count × P)

MOAD: 0001 — Sedimentary Defect (CWE-407) Severity: MEDIUM File: server/token.c Functions: token_find_privilege(), token_adjust_privileges(), token_check_privileges() Lines: 808-821, 823-853, 870-890

Summary

token_find_privilege() performs an O(P) linear scan through our linked list of token privileges to find a privilege by LUID. It is called inside for loops in both token_adjust_privileges() and token_check_privileges(), making those functions O(count × P) per invocation.

Defect Pattern

// token_find_privilege: O(P) linear scan
static struct privilege *token_find_privilege(struct token *token,
    struct luid luid, int enabled_only)
{
    struct privilege *privilege;
    LIST_FOR_EACH_ENTRY(privilege, &token->privileges, struct privilege, entry)
    {
        if (is_equal_luid(luid, privilege->luid))
            ...
    }
    return NULL;
}

// token_adjust_privileges: O(count) outer loop
for (i = 0; i < count; i++)
{
    struct privilege *privilege = token_find_privilege(token, privs[i].luid, FALSE);
    // ^^ O(P) each iteration → O(count * P) total
    ...
}

// token_check_privileges: same pattern
for (i = 0; i < count; i++)
{
    struct privilege *privilege = token_find_privilege(token, reqprivs[i].luid, TRUE);
    // ^^ O(P) each → O(count * P) total
}

Complexity

Windows allows up to 1023 privileges per AdjustTokenPrivileges call. A Wine token can hold ~21 standard privileges + dynamically allocated ones.

count	P	Ops (defect)	Ops (fixed)	Ratio
21	21	441	21	21x
100	100	10,000	100	100x
1023	1023	1,046,529	1,023	1023x

Fix

Replace our list-based privilege storage with an indexed structure:

Option A — flat array (simplest): All standard Windows privilege LUIDs have .low_part values 2-36 (SeCreateTokenPrivilege=2 through SeRelabelPrivilege=65). A fixed array of struct privilege * indexed by luid.low_part gives O(1) lookup for all standard privileges at the cost of ~70 pointers per token.

Option B — wine_rb_tree: Use Wine's existing red-black tree (include/wine/rbtree.h) keyed on the 64-bit LUID value. O(log P) lookup. Handles dynamic LUIDs from NtAllocateLocallyUniqueId.

Both options maintain the linked list for iteration in get_token_privileges.