Research · v1.0.0

Labyrinth: A Grammar-Composable Rule Language for Static Application Security Testing

Lars Shakya Buch-Jepsen

v1.0.0Latest stable release: 2026-11-21

Labyrinth: A Grammar-Composable Rule Language for Static Application Security Testing

1. Introduction

Static application security testing (SAST) tools face a fundamental tension: the more precise their analysis, the more they tend to bind rule authors to a fixed set of supported languages and a tool-specific query dialect. Labyrinth takes the opposite starting point. It is a rule language and engine built on the Minotaur grammar platform, in which a security rule is a small YAML document whose pattern bodies are ordinary syntax snippets written in the rule’s target grammar — whatever that grammar is. Rules are compiled ahead of analysis into native C# delegates and executed as a fixed-point taint traversal directly on the CognitiveGraph, with no serialization and no interpretation.

Labyrinth follows the Semgrep paradigm of snippet-based rules [1]: a rule author writes what the vulnerable code looks like, plus metavariables that capture and unify nodes, an ellipsis operator that absorbs irrelevant detail, and — for cases a pattern alone cannot express — a dynamically compiled boolean condition as an escape hatch. Unlike Semgrep, however, the language set is not fixed: metavariable and ellipsis tokens are injected into each target grammar through a per-language overlay, so every grammar in the corpus becomes a rule target. This makes Labyrinth a grammar-composable SAST rule language: the same rule schema, matching semantics and reporting pipeline apply uniformly across 36 language grammars, from C# and Java to COBOL and classic ASP.

1.1 Contributions

This work contributes:

  1. A rule language design with two analysis modes (search and taint) whose pattern bodies are snippets in the target grammar rather than a fixed language, specified by a small EBNF grammar.
  2. An overlay composition mechanism that injects metavariable and ellipsis tokens into arbitrary target grammars in the StepLexer/StepParser pipeline, decoupling the rule language from any particular language inventory.
  3. Ahead-of-analysis compilation of patterns to expression-tree delegates with delegate caching, so rule evaluation is native code over the in-memory graph.
  4. A fixed-point taint engine with rule-wide metavariable unification, sanitizer pruning, propagator transfer and interprocedural flow via host-provided edges.
  5. A CI-ready reporting pipeline: console output, SARIF 2.1.0 for GitHub code scanning [2], grep-convention exit codes, and location-sensitive baselines so pipelines only break on new findings.

Information-flow and taint analysis. The security motivation for tracking untrusted data from entry points to sensitive sinks goes back to Denning’s lattice model of secure information flow [3]. Dynamic taint tracking demonstrated the practical value of source-to-sink paths for exploit detection [4], and FlowDroid established precision standards for static context- and flow-sensitive taint analysis on realistic codebases [5]. Labyrinth’s taint mode adopts the same conceptual model — sources, sinks, sanitizers and explicit propagators — but expresses it in a rule language rather than an analysis program.

Graph-based and pattern-based SAST. CodeQL exposes code as a relational database and rules as queries over it [6], and code property graphs combine syntax and data flow into a single queryable representation [7]. At the other end of the spectrum, Coccinelle popularized semantic patches: incomplete code patterns with metavariables matched over C source [8], and Semgrep brought the same idea to a broad language inventory with a focus on rule readability [1]. Labyrinth sits deliberately in the Semgrep lineage: rules are snippet-based and readable by security researchers, but the engine additionally performs fixed-point taint traversal with metavariable unification over a graph, without requiring the rule author to write graph queries.

Data-flow frameworks. The taint engine’s worklist-to-equilibrium execution follows the classical monotone-framework model of global program optimization [9].

3. The Labyrinth Rule Language

3.1 Rule schema

Rules live in YAML files under a rule pack directory, as a rules: list. Two analysis kinds exist: search rules match a single pattern, and taint rules track data flow from sources to sinks:

rules:
  - id: custom-grammar-injection
    severity: ERROR
    message: "Untrusted data flows into a critical execution sink."
    type: taint
    sources:
      - pattern: "ReceiveData($DATA)"
    sinks:
      - pattern: "ExecuteAction(..., $DATA, ...)"
    sanitizers:
      - pattern: "VerifyIntegrity($DATA)"
    propagators:
      - pattern: "$TARGET = FormatString($SRC)"
        from: $SRC
        to: $TARGET

Severity is one of ERROR, WARNING or INFO and drives the SARIF level of the resulting finding. Search rules carry a single pattern; taint rules carry sources and sinks, with optional sanitizers that prune taint state and propagators that transfer taint between metavariables via explicit from/to bindings.

3.2 Metavariables and ellipsis

A pattern is a snippet of the target grammar’s syntax, parsed by the StepLexer/StepParser pipeline under two augmentations:

  • Metavariables. $NAME matches any single node and captures it. The unification scope is the whole rule: the same metavariable must bind the very same node everywhere it occurs. A $DATA bound at a source therefore only matches a sink consuming that exact node — the rule language, not the rule author, enforces path-sensitive consistency.
  • Ellipsis. ... matches any sequence of sibling nodes (zero or more), e.g. ExecuteAction(..., $DATA, ...).

Node type conventions give patterns uniform vocabulary across languages: FunctionCall (name = callee, arguments = arguments) and Assignment (argument 0 = left-hand side, argument 1 = assigned expression).

3.3 Dynamic LINQ conditions

Every pattern entry accepts an optional condition: — a string C# boolean expression in System.Linq.Dynamic.Core syntax [10] evaluated against the matched node:

- id: advanced-size-check
  type: search
  pattern: "AllocateMemory($SIZE)"
  condition: "node.Arguments[0].Value > 1024"

Conditions are parsed once at rule load time and appended to the pattern’s expression tree before compilation; malformed conditions fail fast with a rule error naming the rule, so an invalid pack never reaches analysis.

3.4 Grammar and overlay composition

The Labyrinth rule format itself is specified by a small EBNF grammar that validates rule structure — id uniqueness and format, severity and type validity, mandatory source/sink presence for taint rules, metavariable consistency, and propagator bindings referencing metavariables defined in their own pattern.

Crucially, pattern bodies are carried by this grammar only as opaque quoted strings. They are parsed as snippets of the rule’s target grammar, composed with a per-target Labyrinth.extension overlay that injects the metavariable and ellipsis tokens into that grammar’s lexer/parser definition. This inversion — the rule language defines no language constructs of its own beyond the YAML skeleton — is what makes Labyrinth grammar-composable: adding a rule-targetable language requires only a grammar plus an overlay, and every language grammar in the corpus ships one (36 grammars at the time of writing, including C#, Java, Python, Rust, TypeScript, Go, COBOL 2023, classic ASP and WebAssembly 2.0).

4. Engine Architecture

The engine is organized in five layers, all shipped:

Layer Scope
1 — Rule schema & pattern parsing Semgrep-style YAML schema; metavariable/ellipsis tokens; target-grammar pattern parsing via StepLexer/StepParser with overlay composition
2 — Expression-tree compilation Pattern mini-ASTs compiled to native delegates (Func<ILabyrinthMatchNode, LabyrinthMatchContext, bool>) with delegate caching
3 — Taint traversal engine Fixed-point worklist over the data-flow graph: source identification, propagation, sanitizer pruning, propagator transfer, sink confirmation with full source-to-sink paths, pooled metavariable bindings, interprocedural flow via host-provided edges
4 — Dynamic LINQ conditions condition: parsed at initialization, appended to the pattern expression tree before compilation; fail-fast rule errors
5 — Reporting & CI/CD Console output, SARIF for GitHub code scanning, exit codes, baselines, rule-pack loading

Three design points deserve emphasis.

Zero serialization. The taint engine consumes compiled matchers plus an ILabyrinthDataFlowGraph materialized by the host directly from the CognitiveGraph. Analysis runs on the in-memory graph; there is no intermediate representation to serialize or deserialize.

Fixed point without iteration bounds. Per node, the engine tracks one taint state per taint origin (source node); a state change — a new origin or a new metavariable binding — re-enqueues the node, and the worklist drains to equilibrium. Loops and mutual recursion terminate without a caller-side iteration bound, following the classical monotone-framework argument [9].

Allocation discipline. Metavariable bindings travel along each taint path in a value-type struct with pooled backing arrays; paths are stored as linked steps (O(nodes) memory) and materialized only when a finding is reported, with the shortest path winning per (source, sink) pair. The hot loop allocates only path steps and pooled binding arrays; a 20,002-node chain traversal completes with bounded allocations in the engine’s large-graph regression test.

5. Reporting and CI Integration

Console. A console reporter writes one block per finding — severity, rule id, sink location, message, and the full indented source-to-sink path — and returns the process exit code directly.

SARIF. A dependency-free SARIF 2.1.0 writer [2] emits one result per finding: severity mapped to error/warning/note, the sink location as the result location, tool driver rule metadata, and the full data-flow path as a codeFlow threadFlow — ready for GitHub code scanning upload.

Exit codes. The engine follows the grep/CodeQL convention: 0 for a clean run, 1 for findings, 2 for configuration errors (invalid rules, baseline or graph errors).

Baselines. A baseline stores a stable SHA-256 fingerprint per accepted finding (rule id, severity, and source/sink identity including location). Suppressed findings do not affect the exit code, so a pipeline only breaks on new findings. Fingerprints are deliberately location-sensitive: editing code around an accepted finding moves it and makes it reportable again, forcing re-review.

6. Implementation Status

All five layers of the engine are implemented and tested in the Minotaur repository, including pattern parser, expression compiler, taint engine, Dynamic LINQ condition, reporting and grammar-pipeline test suites. The rule grammar and the 36 per-language extension overlays live in the Minotaur-Grammars corpus alongside the language grammars they extend. A rule author guide documents the schema, patterns, conditions, loading, reporting and baseline workflow.

A quantitative comparison against Semgrep [1] or CodeQL [6] on public vulnerability corpora has not yet been performed and is left as future work; no such numbers are claimed here.

7. Discussion and Future Work

The grammar already specifies a set of coverage-completion constructs that broaden authoring ergonomics: metadata blocks, language and path filters (include/exclude globs), fix suggestions, pattern-either, pattern-inside and pattern-not variants, and focus-metavariable selection. Aligning the engine’s coverage with the full grammar surface is the main line of ongoing work. Beyond that, two directions stand out: an empirical evaluation of rule expressiveness and analysis cost against established SAST rule languages, and a study of baseline workflows in real CI pipelines, where the location-sensitive fingerprinting trades report stability for forced re-review.

8. Conclusion

Labyrinth demonstrates that a SAST rule language need not choose between rule readability and language breadth. By making pattern bodies snippets of the target grammar and injecting the rule language’s only two tokens — metavariables and ellipsis — through per-language overlays, the same rule schema, compiled matching semantics and taint traversal apply uniformly across a growing grammar corpus. Rules stay small enough for security researchers to write and review; the engine still performs fixed-point taint analysis with rule-wide metavariable unification directly on the host graph; and findings flow into standard CI and code-scanning infrastructure.

[1]
Semgrep, Inc., “Semgrep documentation.” [Online]. Available: https://semgrep.dev/docs/
[2]
OASIS, “Static analysis results interchange format (SARIF) version 2.1.0.” OASIS Standard, 2021. Available: http://docs.oasis-open.org/sarif/sarif/v2.1.0/sarif-v2.1.0.html
[3]
D. E. R. Denning, “A lattice model of secure information flow,” Communications of the ACM, vol. 19, no. 5, pp. 236–243, 1976.
[4]
J. Newsome and D. Song, “Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software,” in Proceedings of the 12th network and distributed system security symposium (NDSS), 2005.
[5]
S. Arzt et al., “FlowDroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps,” in Proceedings of the 35th ACM SIGPLAN conference on programming language design and implementation (PLDI), 2014, pp. 299–315.
[6]
GitHub, Inc., “CodeQL documentation.” [Online]. Available: https://codeql.github.com/docs/
[7]
F. Yamaguchi, N. Golde, D. Arp, and K. Rieck, “Modeling and discovering vulnerabilities with code property graphs,” in Proceedings of the 2014 IEEE symposium on security and privacy (s&p), 2014, pp. 790–804.
[8]
Coccinelle Team, “Coccinelle: Program matching and transformation for c.” [Online]. Available: https://coccinelle.lip6.fr/
[9]
G. A. Kildall, “A unified approach to global program optimization,” in Proceedings of the 1st ACM SIGACT-SIGPLAN symposium on principles of programming languages (POPL), 1973, pp. 194–206.
[10]
zzzprojects, “System.Linq.Dynamic.Core.” [Online]. Available: https://github.com/zzzprojects/System.Linq.Dynamic.Core/