Skip to main content
Open Source

CS-MAST

A deterministic hashing scheme for general-tree ASTs in SAST scanners, enabling reliable subtree fingerprinting and constant-time node lookup via Merkle-style signatures.
Project image

CS-MAST (Context-Stratified Merkelized Abstract Syntax Tree) is a novel data structure that integrates Merkle-style hashing into general-tree ASTs for use in Static Application Security Testing (SAST) scanners and JavaScript fingerprinting pipelines.

This work was published as a whitepaper while at Rochester Institute of Technology, and the implementation is used in JS Recon for AST-level code pattern matching.

Problem

Applying Merkle Tree hashing to ASTs in SAST scanners surfaces two structural problems:

  • Structural incompatibility: Merkle Trees are defined over binary trees, but ASTs are general trees where nodes may have an arbitrary number of children.
  • Hash collisions: Prior work (e.g. the Unbundle-Rewrite-Rebundle framework) encountered collisions between AST nodes that were structurally identical but semantically distinct — same tree structure, different source code.

Solution

CS-MAST introduces CS-MAST-S (CS-MAST Signature), a deterministic, parameterized hashing scheme inspired by the PHC String Format. Each node's hash is cryptographically bound to its language, parser, and configurable element categories, eliminating collisions while remaining extensible to new code formats.

The signature encodes:

  • Hashing algorithm (hash)
  • Source language (lang) and version (lver)
  • AST parser (prsr)
  • Node inclusion settings (sinc, scat) — controls which node elements contribute to the hash

Key features

  • Extends general-tree ASTs with Merkle-style signatures at every node
  • Deterministic: same code + same config always produces the same signature
  • Constant-time subtree lookup via a hashmap keyed on CS-MAST-S signatures
  • Configurable element categories (lit, id, op, decl, loop, cond, name, val, op_name) for tuning fingerprint granularity
  • Cross-file support: independent per-file CS-MASTs can be combined into a single codebase-level signature
  • Compatible with standard AST library functions (traversal, extraction) — only mutation operations are restricted

How it works

CS-MAST traverses the AST in post-order (bottom-up), so child hashes are computed before parents. At each node, the CS-MAST-S hash is calculated from the node type, its semantic properties (name, value, operator), and the hashes of its children — weighted by the active scat configuration. The resulting signature string follows the format:

$hash=sha256,lang=js,lver=es6,prsr=-babel/parser$<hex-digest>

This enables reliable fingerprinting of AST subtrees and constant-time dictionary lookup in SAST pipelines such as JS Recon.

More info

Please visit the CS-MAST docs site for full specification and usage details.