XGrammar Infinite Recursion Vulnerability Leading to Denial-of-Service

A denial-of-service vulnerability has been identified in XGrammar, an open-source library for structured generation. Prior to version 0.1.21, the library's grammar processing could enter an infinite recursion, causing a segmentation fault. This issue arises from certain grammar rules that create recursive loops, which can be exploited by passing user-defined grammars to XGrammar. The vulnerability has been patched in version 0.1.21.

Impact

Exploitation of this vulnerability causes a segmentation fault, leading to a crash of the application using XGrammar.

Reproduction

The vulnerability can be reproduced by using the XGrammar library to compile a grammar that includes implicit left recursion or certain right recursion patterns. This can be done by creating a grammar rule that references itself in a way that creates a loop, such as 'root ::= rule1 | (rule1 rule1 rule1 rule3)+', and then compiling this grammar with the XGrammar compiler.

Remediation

Users can upgrade to XGrammar version 0.1.21 or later, where this vulnerability has been fixed.