[H-3] Unbounded recursion in extglob pattern matching (DoS)

[chaliy]

Finding H-3: ExtGlob Exponential Blowup

Severity: HIGH
File: crates/bashkit/src/interpreter/mod.rs:3043-3092
Threat ID: TM-DOS-031 (new)

Description

The +(...) and *(...) extglob handlers recursively call glob_match_impl without any depth limit. For each split point in the string, the function recurses with a reconstructed pattern, creating O(n!) time complexity.

for split in 1..=value.len() {
    let prefix = &value[..split];
    let suffix = &value[split..];
    if self.glob_match_impl(prefix, alt, nocase) {
        let inner = alts.join("|");
        let re_pattern = format!("+({}){}", inner, rest);
        if self.glob_match_impl(suffix, &re_pattern, nocase) {
            return true;
        }
    }
}

Attack Vector

# Pattern +(a|aa) against a long string of 'a's causes exponential time
[[ "aaaaaaaaaaaaaaaaaaaaaaaaa" == +(a|aa) ]]

Recommended Fix

Add a depth parameter to glob_match_impl and match_extglob, bail when exceeded (e.g., depth > 20).

Write a failing test first per AGENTS.md.