Skip to content

[BUG] Datalog parser crashes on deeply nested malformed query input #321

Closed

Description

@adityamukho

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-2c32fd065e9691a58aa9d205fe19d5d7bf9ca02a

Or minimize the test case:

cargo +nightly fuzz tmin datalog_parser fuzz/artifacts/datalog_parser/crash-2c32fd065e9691a58aa9d205fe19d5d7bf9ca02a

Minimal 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:

  1. Gracefully reject invalid inputs with a clear parse error, or
  2. 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 structures
  • Parser::parse_list() and Parser::parse_vector() → call parse_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:

  1. Add depth: usize field to Parser struct
  2. Increment depth on entry to parse_value(), decrement on exit
  3. Return a parse error if depth exceeds MAX_RECURSION_DEPTH (e.g., 100)
  4. Apply the same check to parse_list(), parse_vector(), and parse_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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions