# UNDF: UNDF-2026-000000402
# frrouting-0004: ecommunity_include O(E1×E2) → O(E1+E2) merge-intersection

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | MEDIUM |
| Component   | `bgpd/bgp_ecommunity.c:1534` |
| Function    | `ecommunity_include` |
| Hot path    | `subgroup_announce_check()` SoO filter (per-route announcement check) |
| Status      | PATCHED (unit test PASS) |

## Defect

`ecommunity_include` checks whether any entry from `e1` appears in `e2` using a
double nested loop — O(E1×E2):

```c
// bgp_ecommunity.c:1534
bool ecommunity_include(struct ecommunity *e1, struct ecommunity *e2) {
    for (int i = 0; i < e1->size; i++) {
        for (int j = 0; j < e2->size; j++) {
            if (memcmp(e1->val + i * ECOMMUNITY_SIZE,
                       e2->val + j * ECOMMUNITY_SIZE,
                       ECOMMUNITY_SIZE) == 0)
                return true;
        }
    }
    return false;
}
```

**Current callers pass small `e2`** (SoO single-entry or rtlist), so practical severity
is low today. However the API itself is O(E1×E2) — if called with two large extended
community lists it degrades badly.

**Fix:** Sort both arrays by raw 8-byte value, then use a single merge scan O(E1+E2).
Or: build a hash set from the smaller of e1/e2, then check the other:

```c
bool ecommunity_include(struct ecommunity *e1, struct ecommunity *e2) {
    // Build set from smaller list (typically e2)
    eset_t set = eset_from_ecommunity(e2);    // O(E2)
    for (int i = 0; i < e1->size; i++) {
        if (eset_contains(&set, e1->val + i * ECOMMUNITY_SIZE))
            return true;
    }
    return false;
}
```

Speedup: ~250× at E1=E2=500.
