# UNDF: UNDF-2026-000000307
# tf-aws-0001 — Terraform AWS Provider: CloudFormation StackSet org-ID filter O(S×O)

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — Linear Membership Test in Loop)
**File:** `internal/service/cloudformation/stack_set_instance.go`
**Function:** `findStackInstanceSummariesByFourPartKey`

## Defect

```go
// stack_set_instance.go:501-519
pages := cloudformation.NewListStackInstancesPaginator(conn, input)
for pages.HasMorePages() {                           // O(P) pages
    page, err := pages.NextPage(ctx)
    ...
    for _, v := range page.Summaries {               // O(S/P) summaries per page
        if slices.Contains(orgIDs, aws.ToString(v.OrganizationalUnitId)) {  // O(O)
            output = append(output, v)
        }
    }
}
```

`slices.Contains` performs a linear scan of `orgIDs` (a `[]string`) for every stack instance
summary returned by the AWS API.

In large AWS Organizations deployments:
- `orgIDs` can contain hundreds of OU IDs (user-supplied filter)
- Total stack instance summaries across all pages can be thousands

Total complexity: **O(S × O)** where S = total summaries, O = len(orgIDs).

At S=5000 stack instances, O=200 OU IDs → 1,000,000 string comparisons per Terraform plan/apply.
This is called during every `terraform plan` and `terraform apply` that touches
`aws_cloudformation_stack_set_instance` with an `deployment_targets` block.

## Fix

Pre-build a `map[string]bool` from `orgIDs` before the pagination loop:

```go
orgIDSet := make(map[string]bool, len(orgIDs))
for _, id := range orgIDs {
    orgIDSet[id] = true
}

pages := cloudformation.NewListStackInstancesPaginator(conn, input)
for pages.HasMorePages() {
    page, err := pages.NextPage(ctx)
    ...
    for _, v := range page.Summaries {
        if orgIDSet[aws.ToString(v.OrganizationalUnitId)] {   // O(1)
            output = append(output, v)
        }
    }
}
```

## Patch

```diff
--- a/internal/service/cloudformation/stack_set_instance.go
+++ b/internal/service/cloudformation/stack_set_instance.go
@@ -497,6 +497,12 @@ func findStackInstanceSummariesByFourPartKey(...) ([]awstypes.StackInstanceSumma
 	var output []awstypes.StackInstanceSummary

+	// CWE-407: pre-build an O(1) lookup set for orgIDs to avoid O(S×O)
+	// linear scan inside the pagination loop.
+	orgIDSet := make(map[string]bool, len(orgIDs))
+	for _, id := range orgIDs {
+		orgIDSet[id] = true
+	}
+
 	pages := cloudformation.NewListStackInstancesPaginator(conn, input)
 	for pages.HasMorePages() {
@@ -515,7 +521,7 @@ func findStackInstanceSummariesByFourPartKey(...) ([]awstypes.StackInstanceSumma
 		for _, v := range page.Summaries {
-			if slices.Contains(orgIDs, aws.ToString(v.OrganizationalUnitId)) {
+			if orgIDSet[aws.ToString(v.OrganizationalUnitId)] {
 				output = append(output, v)
 			}
 		}
```

## Complexity

| S (summaries) | O (org IDs) | Before (comparisons) | After |
|---------------|-------------|---------------------|-------|
| 500           | 50          | 25,000              | 500   |
| 5,000         | 200         | 1,000,000           | 5,000 |
| 50,000        | 500         | 25,000,000          | 50,000|

## Reproduction

See `defects/terraform/unit/TfAwsCloudFormationAlgorithm.java` — ratio ≥ 5x at S=2000, O=200 (46x at S=7000, O=500).
