Repository navigation
Code executor: catastrophic O(n^2) regex backtracking in extract_code_and_truncate_content hangs on large delimiter-free responses #5992
Description
Version: google-adk 1.28.0 (the regex is unchanged on the 2.x line as well)
What happens
When an LlmAgent has a code_executor, _CodeExecutionResponseProcessor runs CodeExecutionUtils.extract_code_and_truncate_content on every model response. The regex (in google/adk/code_executors/code_execution_utils.py):
pattern = re.compile(
rf'(?P<prefix>.*?)({leading_delimiter_pattern})(?P<code>.*?)({trailing_delimiter_pattern})(?P<suffix>.*?)$'.encode(),
re.DOTALL,
)
pattern_match = pattern.search(response_text.encode())is run via search() on the full joined response text. When the text contains no leading delimiter (e.g. a large structured/JSON response returned by a before_model_callback short-circuit, which still flows through the response post-processors), every start position rescans the whole string looking for the delimiter → O(n²). On a few-hundred-KB response this stalls for tens of minutes — effectively a hang, and no per-turn timeout catches it because it is a synchronous CPU/regex call inside the worker thread.
Reproduce
- Attach any
BaseCodeExecutor(e.g.UnsafeLocalCodeExecutor) to anLlmAgent. - Have the model (or a
before_model_callback) emit a single text part of ~300KB that contains no```python/```tool_codefence (e.g. a large Plotly figure JSON). - The post-processor hangs in
pattern.searchwhile extracting code.
Suggested fix
Before compiling/searching, short-circuit when no leading delimiter substring is present — the regex can only return None in that case, so this is behavior-preserving and makes the no-match path O(n):
text_parts = [p for p in content.parts if p.text]
if text_parts:
response_text = '\n'.join(p.text for p in text_parts)
if not any(d[0] in response_text for d in code_block_delimiters):
return None # no opening delimiter -> no code block(The default delimiters '```tool_code\n' and '```python\n' are literal substrings, so a plain in check is sufficient.)
Activity
surajksharma07 commentedon Jun 8, 2026
/adk-issue-analyze
adk-bot commentedon Jun 8, 2026
I will begin by reading the instructions for the$O(N^2)$ backtracking patterns may occur elsewhere.# GitHub Issue #5992 Analysis: Code executor: catastrophic O(n^2) regex backtracking in extract_code_and_truncate_content hangs on large delimiter-free responses
adk-issue-analyzeskill, as it directly corresponds to the/adk-issue-analyzecommand you issued. This will guide us in performing a structured analysis of issue #5992.I will fetch the details of GitHub issue #5992 using thefetch_github_issuetool.I will search forcode_execution_utils.pyin the workspace to locate the file described in the issue.I will read the contents ofsrc/google/adk/code_executors/code_execution_utils.pywhere the regex backtracking issue is reported to occur.I will run aghcommand to search for any pull requests ingoogle/adk-pythonthat reference this issue (5992).I see there are two open PRs related to this issue: PR #6002 and PR #6012. I will fetch the details of both PRs using thefetch_github_prtool. Let's inspect PR #6002 first.I will fetch the details of the other pull request, #6012, to see if it is a duplicate, a revision, or has an alternative approach.I will run a cleangh pr diffcommand to view the code changes implemented in PR #6012. This will let me verify how the developer chose to fix the bug.I will view thetest_code_execution.pyfile to see the testing context and check where this test fits.I will perform a search for regex usage in other execution files to see if similarExecutive Summary
LlmAgentutilizes acode_executor, the response processor runs the utility method extract_code_and_truncate_content on every response. This function searches the text using a regular expression with multiple greedy/lazy wildcards (.*?). If a large input (such as 100KB+ JSON/data payloads) contains no opening delimiter, the regex engine falls into catastrophicDetailed Analysis
1. Root Cause Analysis ("What is broken?")
leading_delimiter_patternis not matched):0. The lazy dot-star(?P<prefix>.*?)tries to expand but the engine has to match the delimiter. It fails.1, scans to the end, fails again.2,3, ..., up to2. Existing Pull Requests ("Is there a linked PR that fixes this issue?")
Noneimmediately, completely bypassing the regex engine.test_code_execution.pytracking mocks ofre.compile. It makes sure thatre.compileis never called if a payload is delimiter-free, preventing subsequent regressions.3. Recommendation
Turn Summary
I have successfully retrieved isttue #5992 and identified the root cause of the regular expression backtracking within extract_code_and_truncate_content. After checking all related PRs on Github, I confirmed that PR #6012 resolves this elegantly with robust regression testing. It is ready for approval and merging. No manual changes are required under this read-only workflow.
surajksharma07 commentedon Jun 9, 2026
@RexLeee this is a real backtracking trap: re.search() with a lazy .*? prefix tries every partition of a no-delimiter string, and on 300 KB that's effectively unbounded CPU time.
A quick local patch worth trying: right after response_text = '\n'.join(...) in extract_code_and_truncate_content, insert if not any(d[0] in response_text for d in code_block_delimiters): return before the re.compile call.
Could you verify this resolves the hang on your payload — and also confirm normal code-block extraction still works correctly on a fenced response?
Once you're happy it holds up, it'd be great to have that confirmed before the linked PR lands!
RexLeee commentedon Jun 9, 2026
Thanks @surajksharma07 — confirmed on both counts. ✅
I'd already been running exactly this guard in production since hitting the issue, so I can speak to it directly:
1. Resolves the hang. The one-liner you suggested
is the same condition I shipped. On a ~500 KB delimiter-free payload (a large Plotly chart JSON emitted via our agent's direct-output path)
extract_code_and_truncate_contentstalled the whole turn for ~36 minutes; with the fast-path substring check it returnsNonein well under a second. It runs on the exact sameresponse_textthe regex would scan, so for the delimiter-free case it's behaviorally identical to the old path (which could only ever returnNonethere) — just O(n) instead of O(n²).2. Normal extraction still works. Fenced responses (
```python … ```,```tool_code … ```) still extract correctly — I have a regression test asserting both the delimiter-free fast-return and that a normal fenced block is still parsed unchanged.One implementation note in case it's useful: I deliver it as a monkeypatch over the whole method (we vendor ADK and want it trivially removable once this lands), so mine adds an extra guard to skip the short-circuit when a part carries
executable_code. PR #6012 doesn't need that because it places the check after theexecutable_codeearly-return — which is the cleaner spot for the in-tree fix.+1 to merge #6012 as-is. Thanks for picking this up!
surajksharma07 commentedon Jun 9, 2026
That production number — 36 minutes on a 500 KB Plotly JSON — is exactly the kind of data that makes the severity undeniable, so thanks for sharing that directly.
Your note on positioning is worth calling out: PR #6012 placing the guard after the executable_code early-return is the cleaner design precisely because it avoids the extra conditional your monkeypatch needs — the check only runs on text-based responses, which is all it ever needs to protect.
Everything is confirmed at this point — the hang is reproducible, the fix is behaviour-preserving, regression-tested, and scoped correctly in #6012.
Marking this confirmed and flagging #6012 for reviewer attention — appreciate the thorough follow-up, @RexLeee!
Team is looking more into it.
Thanks!
GWeale commentedon Jun 17, 2026
Fixed on main via #6118 (commit 910e1c1): the O(n^2) backtracking regex in extract_code_and_truncate_content was replaced with a linear scan, so the ReDoS hang on large delimiter-free responses is gone. Thanks for the careful writeup. Closing as fixed.