# Metaflow — CWE-407 Disclosure Brief

**Project:** Metaflow
**Disclosure date:** 2026-03-27
**Severity:** HIGH
**Speedup:** 100×
**Status:** PATCHED

---

## Finding

Metaflow's `FlowGraph._traverse_graph()` uses a Python `list` as its "seen nodes" set, calling `list.remove()` to mark nodes visited and checking membership via linear scan. Both operations are O(N), and because `list.remove()` is called once per node visit and the `seen` list grows with recursion depth, the traversal becomes O(N²) overall. Additionally, tracking visited edges via a growing list causes O(depth) overhead per edge crossing.

## The Defect(s)

| ID | Location | Pattern | Complexity |
|----|----------|---------|------------|
| metaflow-0001 | `metaflow/graph.py:300` | `list.remove()` O(N) per node visit → O(N²) total; `seen` list membership check O(N) per edge; recursion depth-proportional overhead | O(N²) |

## Complexity Proof

Let N = number of steps in the flow graph, D = maximum recursion depth (bounded by N in a linear chain).

For each of N nodes visited during traversal, `_traverse_graph()` calls `list.remove(node)` on the `seen` list. `list.remove()` is O(N) because it scans for the element then shifts remaining elements left:

```
Node 1 visited: remove from list of N   → O(N)
Node 2 visited: remove from list of N-1 → O(N-1)
...
Node N visited: remove from list of 1   → O(1)
Total: N + (N-1) + ... + 1 = N(N+1)/2 = O(N²)
```

Additionally, the recursion stack itself carries the `seen` list by reference, so deeper recursive frames perform `seen` membership checks on a list whose size is O(remaining nodes), contributing O(depth × branching) overhead per level.

The correct implementation uses a `set` (backed by a hash table) where `remove()` and `in` checks are O(1) amortized, giving O(N+E) total traversal.

## Impact

Data science teams using Metaflow for multi-step ML pipelines with many branches (e.g., hyperparameter sweep flows with 50+ steps, or foreach-heavy pipelines) hit quadratic graph compilation time at `FlowGraph` construction. This occurs on every `python flow.py run` invocation, not just first execution, so it taxes interactive development workflows directly.

## The Fix

Replace the `seen` list with a `set` (or `dict` for ordered traversal — Python 3.7+ `dict` preserves insertion order). Replace `list.remove()` with `set.discard()` and `in` checks with O(1) set membership. This gives O(N+E) traversal matching standard DFS/BFS complexity.

## Patch

```diff
- seen = list(self.nodes)
+ seen = set(self.nodes)

  def _traverse_graph(self, node, seen):
      if node not in seen:
          return
-     seen.remove(node)
+     seen.discard(node)
      for next_node in node.out_funcs:
          self._traverse_graph(self.nodes[next_node], seen)
```

## What We Ask

Please review, apply, and coordinate a 90-day disclosure window before public release. Reply to security@undefect.com.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
