# UNDF: UNDF-2026-000000608
# kylin-0002: AclPermissionUtil.transformAuthorities — O(A²) ArrayList dedup loop

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | kylin-0002 |
| Severity | MEDIUM |
| Ecosystem | Apache Kylin |
| Package | `org.apache.kylin.rest.util` |
| File | `src/core-metadata/src/main/java/org/apache/kylin/rest/util/AclPermissionUtil.java` |
| Lines | 65–73 |
| Complexity | O(A²) — ArrayList.contains called in O(A) loop to deduplicate authorities |
| Hot path | Called on every API request that resolves ACL permissions; invoked from multiple REST controllers |

## Defect

```java
// DEFECT: ret is an ArrayList<String>; ret.contains() is O(A) per call
// Called inside an O(A) loop → O(A²) total
public static List<String> transformAuthorities(
        Collection<? extends GrantedAuthority> authorities) {
    List<String> ret = Lists.newArrayList();
    for (GrantedAuthority auth : authorities) {
        if (!ret.contains(auth.getAuthority())) {   // O(A) linear scan
            ret.add(auth.getAuthority());
        }
    }
    return ret;
}
```

`A` = number of granted authorities for the authenticated user. In enterprise deployments with role-group hierarchies, a user can accumulate dozens to hundreds of authorities after group-role expansion.

## Fix

```java
// AFTER: use LinkedHashSet to dedup in O(1) per insert while preserving insertion order
public static List<String> transformAuthorities(
        Collection<? extends GrantedAuthority> authorities) {
    Set<String> seen = new LinkedHashSet<>();
    for (GrantedAuthority auth : authorities) {
        seen.add(auth.getAuthority());
    }
    return new ArrayList<>(seen);
}
```

## Speedup

| A (authorities per user) | Before (ops) | After (ops) | Speedup |
|--------------------------|--------------|-------------|---------|
| 20 | 400 | 20 | 20× |
| 100 | 10,000 | 100 | 100× |
| 500 | 250,000 | 500 | 500× |

## Notes

This pattern is a textbook dedup-via-list antipattern. The fix preserves the exact return type (`List<String>`) and insertion ordering while eliminating the O(A²) scan cost. `transformAuthorities` is called from `AclPermissionUtil.isGlobalAdmin`, `getCurrentUserGroups`, and several REST filter chains — each serving incoming HTTP requests.
