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

## Finding

One O(n³) defect in Puppet's dependency cycle error reporter. Patched. Patch ready for upstream review. The defect is on the error-reporting path — activated when Puppet detects a dependency cycle in a catalog.

## The Defect

**puppet-0001 (PATCHED — LOW):** `graph/simple_graph.rb:199`

```ruby
# In paths_in_cycle() — called when a dependency cycle is detected:
def paths_in_cycle(cycle, max_paths)
    paths = []
    # ...
    while not_exhausted
        path = grow_current_path()
        if frame[1].member?(path)   # Array.member?() — O(|cycle|) per call
            # ...
        end
        frame[1] << path            # growing Array
    end
    paths
end
```

`frame[1]` is a growing Array. `frame[1].member?(path)` is a linear scan over the accumulated paths. Called inside the cycle enumeration loop, which itself iterates over the cycle. Total: **O(|cycle|³)** — cubic on the error-reporting path.

## Complexity Proof

For a cycle of length C:
- Outer loop: C steps
- Inner growth loop: C steps
- `member?()` scan: O(C) per call
- Total: **O(C³)**

At C=100 (100-resource dependency cycle): defective=~500,000 comparisons, fixed=100 (Set shadow). **~5,000× op reduction** for large cycles.

Note: this is on the error path, not the hot path. It fires only when Puppet detects a dependency cycle in a catalog — an error condition. However, in development environments where catalog errors are frequent (iterative resource development, refactoring large Puppet manifests), this path may run many times per session. Large catalogs with complex dependency graphs that accidentally create cycles will hit worst case.

## Impact

Puppet is a widely-deployed configuration management system, used particularly in enterprise environments and those with existing Puppet infrastructure (many organizations have 10+ years of Puppet manifests). It is used by system administrators to manage large numbers of servers.

While puppet-0001 is on the error path, Puppet is commonly used in development workflows where catalog compilation errors are frequent. Large Puppet manifests with hundreds of resources and complex `before`/`require`/`notify`/`subscribe` chains are common in enterprise deployments. A misconfigured relationship causing a cycle in a 100+ resource catalog produces a particularly slow error report.

## The Fix

Replace `frame[1]` Array with a Set for membership testing:

```ruby
# Before
frame[1] << path
if frame[1].member?(path)   # O(|cycle|) Array scan

# After
# CWE-407 fix: Set for O(1) member? instead of O(|cycle|) Array scan.
frame[1][:set].add(path)
frame[1][:list] << path
if frame[1][:set].member?(path)   # O(1) Set lookup
```

Or more simply, use a parallel `Set` alongside the Array:

```ruby
paths_set = Set.new
while not_exhausted
    path = grow_current_path()
    if paths_set.member?(path)  # O(1)
        # ...
    end
    paths_set.add(path)
    paths << path
end
```

## Patch

Fix available: `defects/puppet/patch/puppet-0001-paths-in-cycle-set.patch`

Single-method change in `graph/simple_graph.rb`.

Unit test: cubic growth confirmed on error path; Set replacement eliminates the inner scan.

## What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub issue reference (puppetlabs/puppet).
2. Assess severity — puppet-0001 is on the error path (LOW severity) but produces cubic slowdown for large dependency cycles during development.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Puppet team in the public disclosure. Preferred acknowledgment format welcome.

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