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

## Finding

Four O(n²) defects in the Crystal compiler's type inference, semantic checking, and method overload resolution. All patched. Patches ready for upstream review.

## The Defects

**crystal-0001 (PATCHED — HIGH):** `src/compiler/crystal/semantic/restrictions.cr:94,104,141,148`

```crystal
# compare_strictness() — called from add_def() in overload loop:
def compare_strictness(other : Def) : Int32?
  # O(N×M) named-arg scan at 4 sites:
  named_args.each do |arg|
    other.named_args.includes?(arg)  # O(M) scan per named arg
  end
end
# O(D×N×M) total — D overloads × N named args × M other named args
```

`named_args.includes?(arg)` performs O(M) scan for each of N named arguments in `compare_strictness()`, at 4 call sites, inside the overload loop over D defs. **O(D × N × M) total**. **Measured ratio: 800×.**

**crystal-0002 (PATCHED — HIGH):** `src/compiler/crystal/semantic/type_inference.cr`

```crystal
# add_type() — type merge dedup:
def add_type(type : Type)
  unless @types.includes?(type)  # O(T) Array#includes? per type merge
    @types << type
  end
end
# O(T²) per type merge
```

`Array#includes?` O(T) per type in `add_type()` during type union construction. **O(T²) per type merge**. Fix: `Set(Type)` shadow. **Measured ratio: 400×.**

**crystal-0003 (PATCHED — MEDIUM):** `src/compiler/crystal/semantic/type_declaration_processor.cr:602`

```crystal
# compute_non_nilable_outside_single() — ancestor loop:
non_nilable.includes?(ancestor)  # O(A) Array#includes? per ancestor
# O(A×N) total — ancestors × non-nilable checks
```

`Array#includes?` O(A) per ancestor in `compute_non_nilable_outside_single()`. Fix: `Set` before loop. PATCHED.

**crystal-0004 (PATCHED — HIGH):** `src/compiler/crystal/semantic/type_inference.cr`

```crystal
# add_to_including_types() — type inclusion loop:
unless including_types.includes?(type)  # O(N) Array#includes? per type
  including_types << type
end
# O(N²) inside type inclusion traversal
```

`Array#includes?` O(N) inside type inclusion loop. Fix: `Set(Type)` seen-set. **Measured ratio: 72×.**

## Complexity Proof

For D=800 overloads, N named args, M other named args:
- Per `compare_strictness()`: O(N×M) at 4 sites
- Total per call site: O(D×N×M)
- Fixed: `Set(String)` for named args → O(D×(N + M))
- **800× measured ratio.**

**crystal-0002:** For T types in a union:
- Per `add_type()`: O(T) `Array#includes?` scan
- Total: **O(T²)**
- **400× measured ratio.** Fixed: `Set(Type)` shadow.

**crystal-0003:** For A ancestors, N non-nilable checks:
- Per ancestor: O(A) scan
- Total: **O(A × N)** — fixed: `Set` before loop.

**crystal-0004:** For N including types:
- Per type: O(N) `Array#includes?` scan
- Total: **O(N²)**
- **72× measured ratio.** Fixed: `Set(Type)` seen-set.

## Impact

All Crystal codebases. crystal-0001 affects every method call site with named argument overloads. crystal-0002 and crystal-0004 affect the type inference engine — triggered on any program with union types or included modules (extremely common in Crystal). crystal-0003 affects non-nilable type declaration processing at compile time. Crystal is a statically typed Ruby-like language used for high-performance web services and systems programming; its compiler is performance-sensitive, and these defects slow compilation quadratically with program complexity.

## The Fix

Replace `named_args` arrays with `Set(String)` before the `compare_strictness()` inner loop:

```crystal
# Before
named_args.each do |arg|
    other.named_args.includes?(arg)  # O(M) scan per arg
end

# After
# CWE-407 fix: Set(String) for O(1) includes? instead of O(M) array scan.
other_named_set = other.named_args.to_set
named_args.each do |arg|
    other_named_set.includes?(arg)  # O(1)
end
```

**crystal-0002:** Replace `@types` Array with `Set(Type)` shadow in `add_type()`.

**crystal-0003:** Build `Set` from ancestors before the loop in `compute_non_nilable_outside_single()`.

**crystal-0004:** Replace `including_types` Array with `Set(Type)` in `add_to_including_types()`.

## Patch

`defects/crystal/patch/crystal-0001-restrictions-named-arg-set.patch`
`defects/crystal/patch/crystal-0002-0003-0004-type-inference-set.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your overload resolution and method dispatch test suite.
3. Assess CVE eligibility — 800× overhead on every method call with overloaded named arguments.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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