# Ruby MRI (CRuby) — CWE-407 Disclosure Brief

**Project:** Ruby MRI (CRuby)
**Disclosure date:** 2026-03-27
**Severity:** HIGH
**Speedup:** varies with N×M
**Status:** PATCHED

---

## Finding

Ruby MRI's bytecode compiler resolves named keyword argument bindings with an O(N×M) algorithm: for each of N call-site keyword arguments, it performs a linear scan over the M parameter names defined in the method signature. This appears in `compile.c` and executes at compile time for every call site that uses named kwargs. Methods with many keyword parameters called from many sites accumulate quadratic work during script compilation.

## The Defect(s)

| ID | Location | Pattern | Complexity |
|----|----------|---------|------------|
| ruby-0001 | `compile.c` | kwarg named parameter binding scans M param names for each of N call-site kwargs | O(N×M) per call site |

## Complexity Proof

Let N = number of keyword arguments at a call site, M = number of keyword parameters in the method definition.

For each of the N kwargs at the call site, the compiler scans the method's param list linearly to find the matching index:

```
For arg_1: scan up to M params → up to M comparisons
For arg_2: scan up to M params → up to M comparisons
...
For arg_N: scan up to M params → up to M comparisons
Total: N × M comparisons per call site
```

If the same method with M kwargs is called from K call sites, total work is K × N × M. For a method with M = 50 keyword params called from K = 200 sites each passing N = 40 kwargs, that is 400,000 string comparisons just for kwarg binding — versus 200 × 40 = 8,000 hash lookups with a pre-built `HashMap<name, index>`.

Pre-building a hash map of `{param_name => param_index}` once per method definition reduces each per-call-site lookup to O(1), making binding O(N) per call site and O(K×N) total.

## Impact

Any Ruby application or gem with methods that define and use many keyword arguments is affected at compile time. DSL-heavy frameworks (Rails, RSpec, Sorbet-annotated code), configuration builders, and test suites with large parameterized helpers see this most acutely. The cost is paid every time the Ruby runtime compiles the source file — on every process start, every `require`, and in every `eval`.

## The Fix

Pre-build a `HashMap<name, index>` (or equivalent C hash structure) for each method's keyword parameter list once during method compilation. At each call site, look up each kwarg name in O(1) instead of scanning the param array.

## Patch

```diff
- /* For each kwarg at call site, scan param list for matching name */
- for (int i = 0; i < argc; i++) {
-     VALUE kw_name = call_kwargs[i];
-     for (int j = 0; j < param_count; j++) {
-         if (rb_str_equal(kw_name, param_names[j])) {
-             binding[i] = j;
-             break;
-         }
-     }
- }
+ /* Build param name -> index map once per method, reuse at every call site */
+ st_table *kw_index = st_init_strtable();
+ for (int j = 0; j < param_count; j++) {
+     st_insert(kw_index, (st_data_t)RSTRING_PTR(param_names[j]), (st_data_t)j);
+ }
+ for (int i = 0; i < argc; i++) {
+     st_data_t idx;
+     if (st_lookup(kw_index, (st_data_t)RSTRING_PTR(call_kwargs[i]), &idx)) {
+         binding[i] = (int)idx;
+     }
+ }
```

## 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*