# 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:

```python
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:
```python
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

```python
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`:
```python
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.
