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

## Finding

Two O(n²) defects in Ansible's role dependency resolution. Both patched. Patches ready for upstream review. Notably, the Ansible codebase contained a `TODO: re-examine dep loading` comment at one of the defect sites, acknowledging the problem.

## The Defects

**ansible-0001 (PATCHED — HIGH):** `playbook/role/__init__.py:529`

```python
# In Role.get_vars() — role dependency deduplication, per-role per-play:
seen = []
# ...
for dep in get_all_deps(role):
    if dep not in seen:   # O(D) — list scan per dep
        seen.append(dep)
    # ...
# TODO: re-examine dep loading
```

`seen` is a plain Python list. `dep not in seen` is O(D) per dependency check. With D transitive dependencies: **O(D²)** total. Fires per-role per-play during playbook compilation.

**ansible-0002 (PATCHED — MEDIUM):** `playbook/role/__init__.py:285`

```python
# In Role._load_role_data() — collection deduplication:
self.collections.extend(
    c for c in new_collections if c not in self.collections  # O(C) per item
)
```

`self.collections` is a list. `c not in self.collections` is O(C) per item in a growing list. **O(C²)** total over C collections.

## Complexity Proof

**ansible-0001:** For D transitive role dependencies:
- Per dep: O(D) `not in seen` list scan
- Total: **O(D²)**

At D=80 role dependencies: defective=3,160 comparisons, fixed=80. **30× op reduction** (unit test at D=80). Scales worse for deep dependency trees common in large Ansible roles with many transitive dependencies.

**ansible-0002:** For C collections added:
- Per collection: O(C) list scan
- Total: **O(C²)**

Fix: parallel `seen_ids = set()` using `id(dep)` (Role objects are unhashable directly).

## Impact

Ansible is the dominant configuration management and orchestration tool — used by system administrators, DevOps teams, and SREs worldwide for server provisioning, application deployment, and infrastructure automation.

ansible-0001 fires during playbook compilation — when Ansible resolves the transitive dependency graph of roles. Large Ansible role trees (enterprise playbooks with 20+ roles, each with multiple dependencies) maximize D and hit worst case on every playbook run. Ansible Tower/AWX users running scheduled playbooks on large fleets pay this overhead on every execution.

ansible-0002 fires during role data loading when Ansible collection namespaces are resolved. Organizations using Ansible Collections (the standard package format for Ansible content) with many installed collections hit this path.

## The Fix

**ansible-0001:** Replace `seen = []` with `seen_ids = set()` using object identity:

```python
# Before
seen = []
if dep not in seen:
    seen.append(dep)

# After
# CWE-407 fix: set of id(dep) for O(1) membership — Role is unhashable by value.
seen_ids = set()
if id(dep) not in seen_ids:
    seen_ids.add(id(dep))
    seen.append(dep)
```

Using `id(dep)` because `Role` objects are not hashable by value (mutable with complex equality). Object identity is the correct dedup key for dependency traversal.

**ansible-0002:** Parallel set for O(1) membership:

```python
# Before
self.collections.extend(
    c for c in new_collections if c not in self.collections
)

# After
# CWE-407 fix: shadow set for O(1) membership instead of O(C) list scan.
collections_set = set(self.collections)
for c in new_collections:
    if c not in collections_set:
        collections_set.add(c)
        self.collections.append(c)
```

## Patch

Fix available: `defects/ansible/patch/ansible-0001-0002-seen-set-id.patch`

Two-location patch in `playbook/role/__init__.py`.

Unit test: ansible-0001 **30× speedup at D=80**. ansible-0002: measured ratio confirming O(C²) → O(C).

## What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (ansible/ansible).
2. Assess severity — ansible-0001 fires on every playbook run for every role with transitive dependencies; the `TODO: re-examine dep loading` comment indicates this was a known issue.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Ansible team in the public disclosure. Preferred acknowledgment format welcome.

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