79 lines
3.5 KiB
Markdown
79 lines
3.5 KiB
Markdown
# 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*
|