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

## Finding

Two O(n²) defects in Terraform's directed acyclic graph (DAG) validation and edge transformer. Both patched. Patches ready for upstream review. The defects fire on every `terraform plan` and `terraform apply` invocation.

## The Defects

**terraform-0001 (PATCHED — HIGH):** `internal/dag/tarjan.go:96`

```go
// In Tarjan SCC — called from AcyclicGraph.Validate() on every plan/apply:
func inStack(s *[]Vertex, v Vertex) bool {
    for _, n := range *s {
        if n == v {
            return true
        }
    }
    return false
}
```

`inStack` performs an O(V) slice scan per call. Called for every edge in the SCC traversal. Total: **O(V × E)** instead of O(E).

**terraform-0002 (PATCHED — MEDIUM):** `internal/dag/graph.go:79`

```go
// In EdgesTo() — called inside CBDEdgeTransformer vertex loop:
func (g *Graph) EdgesTo(v Vertex) Set {
    var s Set
    for _, e := range g.edges {  // O(E) — iterates all edges per call
        if hashcode(e.Target()) == hashcode(v) {
            s.Add(e)
        }
    }
    return s
}
// Called inside O(V) vertex loop → O(V × E) total
```

`g.edges` is a flat slice. `EdgesTo()` iterates all E edges for each of V vertices. The existing `upEdges` index (maintained for other purposes) is not used here.

## Complexity Proof

**terraform-0001:** For V vertices and E edges in the resource dependency graph:
- `inStack()`: O(V) scan per SCC edge traversal
- Called for every edge: O(E) times
- Total: **O(V × E)**

At V=100 vertices (100-resource Terraform module): defective ~triangular count, fixed O(V) with `onStack map[Vertex]bool`. **100× op reduction confirmed. Exact triangular count verified by unit test.**

**terraform-0002:** For V vertices and E edges:
- `EdgesTo()`: O(E) scan per call
- Called V times in transformer: **O(V × E)**

At V=100, E=500: defective=50,000 comparisons per transform, fixed=500 (upEdges index lookup). **100× op reduction.**

## Impact

Terraform is the dominant infrastructure-as-code tool — used by virtually every cloud engineering team to provision AWS, GCP, Azure, and other cloud resources. `terraform plan` and `terraform apply` are run dozens to hundreds of times daily in active development and CI/CD pipelines.

terraform-0001 fires on every invocation: `AcyclicGraph.Validate()` runs Tarjan SCC to detect cycles in the resource dependency graph on every `plan` and `apply`. Large Terraform configurations — monorepos with hundreds of resources, complex module hierarchies — maximize V and hit worst case on every run.

terraform-0002 fires in `CBDEdgeTransformer` — the create-before-destroy edge transformer that handles lifecycle rules for resource replacement. It runs on every `apply` that involves resource replacement.

## The Fix

**terraform-0001:** Replace `inStack` slice scan with `map[Vertex]bool`:

```go
// Before
func inStack(s *[]Vertex, v Vertex) bool {
    for _, n := range *s {
        if n == v { return true }
    }
    return false
}

// After
// CWE-407 fix: map[Vertex]bool for O(1) lookup instead of O(V) slice scan.
onStack := make(map[Vertex]bool)
// In SCC traversal:
if onStack[v] { ... }   // O(1)
onStack[v] = true       // O(1)
onStack[v] = false      // O(1)
```

**terraform-0002:** Use the existing `upEdges` index:

```go
// Before
func (g *Graph) EdgesTo(v Vertex) Set {
    for _, e := range g.edges { ... }  // O(E) scan

// After
// CWE-407 fix: use existing upEdges index for O(1) lookup instead of O(E) scan.
func (g *Graph) EdgesTo(v Vertex) Set {
    return g.upEdges[hashcode(v)]  // O(1) map lookup
}
```

## Patch

Fix available: `defects/terraform/patch/terraform-0001-0002-dag-onstack-map.patch`

Two-location patch across `internal/dag/tarjan.go` and `internal/dag/graph.go`.

Unit test: **100× speedup at V=100, exact triangular count verified**. terraform-0001 growth confirmed: defective 3.99× per doubling (quadratic), fixed 2.00× per doubling (linear).

## What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitHub Security Advisory or issue reference (hashicorp/terraform).
2. Assess severity — terraform-0001 fires on every `terraform plan` and `apply`; large infrastructure configs with 100+ resources hit worst case on every CI run.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the HashiCorp/Terraform team in the public disclosure. Preferred acknowledgment format welcome.

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