# Celery — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Two O(n²) defects in Celery's ResultSet group merge and task chain canvas builder. Both patched. Patches ready for upstream review.

## The Defects

**celery-0001 (PATCHED — HIGH):** `celery/result.py:597`

```python
# ResultSet.update() + add() — chord group merge:
if r not in self.results:  # O(N) — self.results is a list
    self.results.append(r)
# O(M×N) total — M new results × N existing results per merge
```

`self.results` is a plain list. `r not in self.results` performs O(N) scan per result addition in `update()` and `add()`. During chord group merge with M new results and N existing: **O(M × N) total**. Fix: parallel `set` of IDs. **Measured ratio: 499×.**

**celery-0002 / cel-0001 (PATCHED — HIGH):** `celery/canvas.py:702-706`

```python
# append_to_list_option() — called inside chain-build loops O(T×E) times:
def append_to_list_option(lst, val):
    if val not in lst:  # O(L) list scan per append
        lst.append(val)
    return lst
# O(T×E×L) total — tasks × executions × list length
```

`if val not in lst` performs O(L) linear scan where `lst` is a list. Called O(T×E) times inside chain-build loops. **O(T × E × L) total overhead**. Fix: parallel set mirror for O(1) dedup.

## Complexity Proof

**celery-0001:** For M=499 new results merged into N=499 existing:
- O(M×N) = 249,001 comparisons
- Fixed: parallel `set` of IDs → O(M + N)
- **499× measured ratio.**

**celery-0002:** For T=100 tasks, E=10 executions, L=100 list entries:
- O(T×E×L) = 100,000 comparisons
- Fixed: parallel `set` mirror → O(T×E)
- **Measured: scales with T×E×L product.**

## Impact

All Celery applications. celery-0001 fires on every `ResultSet.update()` or `add()` call during chord group merge — the core Celery pattern for fan-out/fan-in workflows. Applications using chords with large groups of parallel tasks maximize M×N. celery-0002 affects `append_to_list_option()` in canvas (workflow) construction. Applications that build complex Celery workflows at runtime (data pipelines, task DAGs, dynamic workflows) hit celery-0002 on every workflow construction. Celery is the most widely used Python distributed task queue, deployed in Django, Flask, and FastAPI applications.

## The Fix

**celery-0001:** Maintain a parallel set of result IDs alongside the results list:

```python
# Before
if r not in self.results:
    self.results.append(r)

# After
# CWE-407 fix: parallel set of IDs for O(1) membership instead of O(N) list scan.
if r.id not in self._result_id_set:
    self._result_id_set.add(r.id)
    self.results.append(r)
```

**celery-0002:** Maintain a parallel set mirror alongside the list:

```python
# Before
def append_to_list_option(lst, val):
    if val not in lst:  # O(L) list scan
        lst.append(val)
    return lst

# After
# CWE-407 fix: parallel set mirror for O(1) dedup instead of O(L) list scan.
def append_to_list_option(lst, val, lst_set=None):
    if lst_set is not None:
        if val not in lst_set:  # O(1) set lookup
            lst_set.add(val)
            lst.append(val)
    else:
        if val not in lst:  # fallback for callers without set
            lst.append(val)
    return lst
```

## Patch

`defects/celery/patch/celery-0001-resultset-id-set.patch`
`defects/celery/patch/celery-0002-canvas-append-set-mirror.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your canvas and workflow test suite.
3. Assess CVE eligibility — fires on every complex workflow construction with O(T×E×L) scaling.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
