[PR #105] [MERGED] fix(bridge): bound regex search work #1835

New issue

Closed

opened 2026-10-16 21:11:37 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-16 21:11:37 +00:00

Owner

📋 Pull Request Information

Original PR: https://github.com/morluto/rea/pull/105
Author: @N0zoM1z0
Created: 7/13/2026
Status: ✅ Merged
Merged: 7/13/2026
Merged by: @morluto

Base: main ← Head: fix/bounded-hopper-regex-search

📝 Commits (1)

65682ee fix(bridge): bound regex search work

📊 Changes

7 files changed (+615 additions, -12 deletions)

View changed files

📝 bridge/hopper_bridge.py (+131 -9)
📝 scripts/verify-package.mjs (+3 -1)
➕ scripts/verify-packed-bridge.mjs (+40 -0)
📝 src/contracts/toolContracts.ts (+2 -2)
➕ tests/bridgeRegex.test.ts (+372 -0)
📝 tests/bridgeTruthfulness.test.ts (+5 -0)
➕ tests/fixtures/bridgeRegexProbe.py (+62 -0)

📄 Description

Summary

Harden Hopper-backed procedure and string regex searches against bounded-but-catastrophic Python regular expressions.

replace the previous structural blacklist with a conservative AST work model;
cap static backtracking paths at 10,000;
cap each regex candidate at 4,096 characters;
cap cumulative regex work across the full search inventory at 1,000,000 units;
normalize Python parser overflow into a stable invalid_request response;
document the exact limits in the public search_procedures and search_strings tool descriptions;
preserve exhaustive literal matching and the existing deterministic pagination behavior.

This is an independent regex-boundedness contribution toward #29. It does not claim to close the broader issue.

Root cause

The existing validator rejected lookarounds, backreferences, nested repetitions, and unbounded repetitions, but it treated every permitted bounded repetition as safe. Patterns such as:

(a|aa){1,35}b

were therefore accepted even though Python's backtracking engine can explore an exponential number of paths. Candidate length and inventory size could multiply that cost while the bridge handled the request synchronously.

Very large repetition counts could also make sre_parse raise OverflowError; that escaped the validation boundary as bridge_exception instead of a stable caller error.

Implementation

The bridge now derives two conservative values from the parsed regex AST:

the number of possible backtracking paths, including branch products, adjacent optional atoms, and bounded repetition alternatives;
the maximum matching steps along a path, including fixed and variable repeat counts.

The matcher combines those values with each candidate length and consumes a per-search work budget before calling re.search. This bounds both a single expensive candidate and cost accumulated while scanning an inventory. Unsupported AST operations fail closed.

Boundary behavior is intentional:

Boundary	Behavior
Pattern length	Existing 1-256 character contract remains unchanged
Bounded repetition	Up to 1,000 repetitions
Static backtracking paths	Up to 10,000 paths
Regex candidate length	Up to 4,096 characters
Cumulative regex work	Up to 1,000,000 units per search request

Regex safety failures are projected as invalid_request with stable messages. Literal mode does not use Python regex and continues matching the complete value even when returned text must be truncated.

Test coverage

A new executable probe loads the real bridge/hopper_bridge.py without opening a Hopper socket. The focused suite covers:

useful bounded regexes and case-insensitive matching;
deterministic regex pagination;
lookarounds and backreferences;
nested, unbounded, and excessive repetitions;
invalid syntax and repetition-count parser overflow;
exact maximum bounded-repeat and work-budget acceptance;
near-budget acceptance and over-budget rejection;
ambiguous bounded repetition and adjacent optional-atom path explosion;
cumulative work across multiple inventory entries;
exact 4,096-character candidate acceptance and oversized rejection;
exact 256-character pattern acceptance and oversized rejection;
literal matching of values longer than the returned-value limit;
stable invalid_request diagnostic projection.

Package verification now extracts the generated npm tarball and executes the same catastrophic-pattern probe against the packed production bridge. This prevents the fake launcher used by other package smoke tests from masking a missing bridge hardening change.

Verification

npm run check - 58 test files and 375 tests passed; typecheck, oxlint, Prettier, build, and coverage run passed
npm run knip - passed
npm run jscpd - passed; no new duplicate block introduced
npm run scan:todos - passed
npm run verify:package - passed with 68 MCP tools and boundedRegexBridge: true
pre-commit lint-staged, Prettier, oxlint, and typecheck - passed

Real Hopper verification was not run because this environment does not provide a Hopper executable and two target binaries. The tests execute the production bridge source and packed bridge directly, but they do not replace the repository's real-Hopper workflow.

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/morluto/rea/pull/105 **Author:** [@N0zoM1z0](https://github.com/N0zoM1z0) **Created:** 7/13/2026 **Status:** ✅ Merged **Merged:** 7/13/2026 **Merged by:** [@morluto](https://github.com/morluto) **Base:** `main` ← **Head:** `fix/bounded-hopper-regex-search` --- ### 📝 Commits (1) - [`65682ee`](https://github.com/morluto/rea/commit/65682ee65c9f899875be5a785c0ec688bc4eda14) fix(bridge): bound regex search work ### 📊 Changes **7 files changed** (+615 additions, -12 deletions) <details> <summary>View changed files</summary> 📝 `bridge/hopper_bridge.py` (+131 -9) 📝 `scripts/verify-package.mjs` (+3 -1) ➕ `scripts/verify-packed-bridge.mjs` (+40 -0) 📝 `src/contracts/toolContracts.ts` (+2 -2) ➕ `tests/bridgeRegex.test.ts` (+372 -0) 📝 `tests/bridgeTruthfulness.test.ts` (+5 -0) ➕ `tests/fixtures/bridgeRegexProbe.py` (+62 -0) </details> ### 📄 Description ## Summary Harden Hopper-backed procedure and string regex searches against bounded-but-catastrophic Python regular expressions. - replace the previous structural blacklist with a conservative AST work model; - cap static backtracking paths at 10,000; - cap each regex candidate at 4,096 characters; - cap cumulative regex work across the full search inventory at 1,000,000 units; - normalize Python parser overflow into a stable `invalid_request` response; - document the exact limits in the public `search_procedures` and `search_strings` tool descriptions; - preserve exhaustive literal matching and the existing deterministic pagination behavior. This is an independent regex-boundedness contribution toward #29. It does not claim to close the broader issue. ## Root cause The existing validator rejected lookarounds, backreferences, nested repetitions, and unbounded repetitions, but it treated every permitted bounded repetition as safe. Patterns such as: ```text (a|aa){1,35}b ``` were therefore accepted even though Python's backtracking engine can explore an exponential number of paths. Candidate length and inventory size could multiply that cost while the bridge handled the request synchronously. Very large repetition counts could also make `sre_parse` raise `OverflowError`; that escaped the validation boundary as `bridge_exception` instead of a stable caller error. ## Implementation The bridge now derives two conservative values from the parsed regex AST: - the number of possible backtracking paths, including branch products, adjacent optional atoms, and bounded repetition alternatives; - the maximum matching steps along a path, including fixed and variable repeat counts. The matcher combines those values with each candidate length and consumes a per-search work budget before calling `re.search`. This bounds both a single expensive candidate and cost accumulated while scanning an inventory. Unsupported AST operations fail closed. Boundary behavior is intentional: | Boundary | Behavior | | --- | --- | | Pattern length | Existing 1-256 character contract remains unchanged | | Bounded repetition | Up to 1,000 repetitions | | Static backtracking paths | Up to 10,000 paths | | Regex candidate length | Up to 4,096 characters | | Cumulative regex work | Up to 1,000,000 units per search request | Regex safety failures are projected as `invalid_request` with stable messages. Literal mode does not use Python regex and continues matching the complete value even when returned text must be truncated. ## Test coverage A new executable probe loads the real `bridge/hopper_bridge.py` without opening a Hopper socket. The focused suite covers: - useful bounded regexes and case-insensitive matching; - deterministic regex pagination; - lookarounds and backreferences; - nested, unbounded, and excessive repetitions; - invalid syntax and repetition-count parser overflow; - exact maximum bounded-repeat and work-budget acceptance; - near-budget acceptance and over-budget rejection; - ambiguous bounded repetition and adjacent optional-atom path explosion; - cumulative work across multiple inventory entries; - exact 4,096-character candidate acceptance and oversized rejection; - exact 256-character pattern acceptance and oversized rejection; - literal matching of values longer than the returned-value limit; - stable `invalid_request` diagnostic projection. Package verification now extracts the generated npm tarball and executes the same catastrophic-pattern probe against the packed production bridge. This prevents the fake launcher used by other package smoke tests from masking a missing bridge hardening change. ## Verification - `npm run check` - 58 test files and 375 tests passed; typecheck, oxlint, Prettier, build, and coverage run passed - `npm run knip` - passed - `npm run jscpd` - passed; no new duplicate block introduced - `npm run scan:todos` - passed - `npm run verify:package` - passed with 68 MCP tools and `boundedRegexBridge: true` - pre-commit `lint-staged`, Prettier, oxlint, and typecheck - passed Real Hopper verification was not run because this environment does not provide a Hopper executable and two target binaries. The tests execute the production bridge source and packed bridge directly, but they do not replace the repository's real-Hopper workflow. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

bsakaguchi

2026-10-16 21:11:37 +00:00