java-topology/defects/keystone/keystone-0001.md

keystone-0001 — CWE-407: O(n²) list comprehension in implied-role deduplication

Severity: MEDIUM File: keystone/api/users.py Line: 659 Status: PATCHED

Description

_create_application_credential() expands implied roles by iterating over roles and appending newly discovered implied roles. The list grows during iteration, and for each implied role it checks membership with a list comprehension:

for role in roles:                                           # O(n) — grows
    for implied_role in PROVIDERS.role_api.list_implied_roles(role['id']):
        imp_role_obj = PROVIDERS.role_api.get_role(...)
        if imp_role_obj['id'] not in [x['id'] for x in roles]:  # O(n) list comprehension
            roles.append(imp_role_obj)                           # list grows

Each check rebuilds a temporary list of role['id'] values and does a linear scan. With R roles and I implied roles each, cost is O(R × I × R) — cubic in the worst case if the role set is deeply implied.

Additionally line 666–668 does another O(R) scan:

token_roles = [r['id'] for r in token.roles]    # builds a list
for role in roles:
    if role['id'] not in token_roles:            # O(T) per role

Fix

seen_role_ids = {r['id'] for r in roles}  # build set first
for role in list(roles):  # iterate over snapshot so appends don't cause infinite loop
    for implied_role in PROVIDERS.role_api.list_implied_roles(role['id']):
        imp_role_obj = PROVIDERS.role_api.get_role(...)
        if imp_role_obj['id'] not in seen_role_ids:   # O(1)
            seen_role_ids.add(imp_role_obj['id'])
            roles.append(imp_role_obj)

For token_roles:

token_role_ids = {r['id'] for r in token.roles}   # O(1) lookup
for role in roles:
    if role['id'] not in token_role_ids:           # O(1)

Patch

See patch/keystone-0001.patch

Test

See unit/KeystoneImpliedRoleAlgorithm.java

Speedup

At R=50 roles with 10 implied each: ~50× fewer ID comparisons.