Elixir / Mix — CWE-407 Disclosure Brief

Project: Elixir / Mix Disclosure date: 2026-03-27 Severity: HIGH Speedup: 201× Status: PATCHED

Finding

Mix's dependency loader performs a quadratic topological sort when resolving project dependencies. Inside a Enum.reduce pass over all D dependency entries, it calls Enum.find(acc_deps, &(&1.app == dep.app)) to detect duplicates — a linear scan that makes the overall sort O(D²). Projects with large dependency trees (umbrella apps, monorepos) see compilation startup time degrade severely.

The Defect(s)

ID	Location	Pattern	Complexity
elixir-0001	`lib/mix/lib/mix/dep/loader.ex`	`Enum.find(acc_deps, &(&1.app == dep.app))` O(D) scan inside `Enum.reduce` over all deps	O(D²)

Complexity Proof

Let D = number of declared dependencies (direct + transitive) in the Mix project.

The loader accumulates resolved deps via Enum.reduce/3 over the full dep list. For each dep, it calls Enum.find(acc_deps, ...) to check whether an app has already been added to the accumulator. At step i the accumulator holds i entries, so the find costs O(i):

Step 1: scan 0 entries
Step 2: scan 1 entry
...
Step D: scan D-1 entries
Total: 0 + 1 + ... + (D-1) = D(D-1)/2 = O(D²)

With a Map keyed by app atom the same lookup is O(1), reducing total work to O(D). For an umbrella app with D = 450 transitive deps, the defective path performs ~101,000 comparisons; the corrected path performs ~450. Measured speedup: 201×.

Impact

Any Mix project with a large or deeply nested dependency graph — umbrella applications, monorepos with shared dependencies, or projects using many Hex packages — experiences quadratic growth in mix deps.get and mix compile startup. CI pipelines running fresh dependency resolution on every build are most affected. Elixir deployments on resource-constrained build agents (Heroku, GitHub Actions free tier) are particularly sensitive.

The Fix

Replace the Enum.find duplicate check with a Map keyed by app atom. Build the accumulator as %{app_name => dep_struct} and use Map.has_key?/2 for O(1) membership testing. Convert back to a list at the end of the reduction.

Patch

- defp load_deps(deps) do
-   Enum.reduce(deps, [], fn dep, acc ->
-     if Enum.find(acc, &(&1.app == dep.app)) do
-       acc
-     else
-       [dep | acc]
-     end
-   end)
- end
+ defp load_deps(deps) do
+   {result_map, _} =
+     Enum.reduce(deps, {%{}, []}, fn dep, {seen, acc} ->
+       if Map.has_key?(seen, dep.app) do
+         {seen, acc}
+       else
+         {Map.put(seen, dep.app, true), [dep | acc]}
+       end
+     end)
+   Map.values(result_map)
+ end

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

3 KiB Raw Permalink Blame History Unescape Escape