Repository navigation
Description
Describe the bug
The datalog_parser fuzzer discovered a crash in the datalog parser when processing deeply nested malformed query inputs with invalid syntax and UTF-8 sequences. The parser lacks recursion depth protection, leading to stack overflow or panic on adversarial input.
To reproduce
The crash can be reproduced using the failing input:
cargo fuzz run datalog_parser fuzz/artifacts/datalog_parser/crash-2c32fd065e9691a58aa9d205fe19d5d7bf9ca02aOr minimize the test case:
cargo +nightly fuzz tmin datalog_parser fuzz/artifacts/datalog_parser/crash-2c32fd065e9691a58aa9d205fe19d5d7bf9ca02aMinimal input
The crashing input (in hex):
28,71,75,65,72,79,20,91,58,118,97,108,105,100,45,97,116,34,65,92,92,92,92,58,102,105,224,174,183,224,174,183,224,174,183,40,40,40,40,40,40,45,224,174,183,224,174,183,224,174,183,40,44,40,40,40,40,40,40,45,224,174,183,224,174,183,224,174,183,40,40,45,224,174,183,224,174,183,224,174,183,40,40,101,32,58,110,97,109,32,101,63,110,93,44,40,40,40,40,40,40,40,40,40,40,40,111,110,92,92,92,39,0,0,0,92,92,92,92,33,92,41,0,0,0,92,92,92,92,92,92,92,34,34,63,49,120,116,51,118,118,53,58,104,101,32,63,95,93,41,109,101,41,10
Expected behaviour
The datalog parser should either:
- Gracefully reject invalid inputs with a clear parse error, or
- Handle deeply nested structures without crashing or panicking
Actual behaviour
The parser crashes with a deadly signal (exit status 77), causing libFuzzer to terminate.
Root cause analysis
The parser (src/query/datalog/parser.rs) lacks recursion depth limits. When the fuzzer generates malformed input with excessive nesting (multiple levels of unbalanced parentheses and brackets), the recursive parser descends without bounds:
Parser::parse_value()→ recursively calls itself for nested structuresParser::parse_list()andParser::parse_vector()→ callparse_value()in a loop- No depth tracking means deeply nested input causes stack exhaustion → panic or segfault
Suggested fix
Add recursion depth tracking to Parser::parse_value() and enforce a reasonable maximum depth limit (e.g., 100 levels). This prevents stack exhaustion on adversarial input while still supporting legitimate deeply-nested queries (rare in practice).
Key changes:
- Add
depth: usizefield toParserstruct - Increment depth on entry to
parse_value(), decrement on exit - Return a parse error if depth exceeds
MAX_RECURSION_DEPTH(e.g., 100) - Apply the same check to
parse_list(),parse_vector(), andparse_map()
Estimated impact:
- ✅ Prevents denial-of-service via unbounded recursion
- ✅ Maintains backward compatibility (legitimate queries are not deeply nested)
- ✅ Clear error message for rejected inputs
- ✅ Minimal performance overhead (one comparison per recursion level)
Additional context
Fuzzer metadata:
- Base unit:
977b85e0812ce7b8d64de0664bba405a8eace6be - Crash artifact:
/home/runner/work/minigraf/minigraf/fuzz/artifacts/datalog_parser/crash-2c32fd065e9691a58aa9d205fe19d5d7bf9ca02a - Exit status: 77 (deadly signal)
- Mutation sequence:
MS: 3 ChangeByte-ChangeByte-CrossOver-
This is a distinct failure
Activity
fix(datalog): bound parser recursion depth to prevent stack overflow (#…