Graph Evolution

Graph Evolution

Builds Trailmark code graphs at two source snapshots and computes a structural diff. Surfaces security-relevant changes that text-level diffs miss: new attack paths, complexity shifts, blast radius growth, taint propagation changes, and privilege boundary modifications.

When to Use

• Comparing two git refs to understand what structurally changed
• Auditing a range of commits for security-relevant evolution
• Detecting new attack paths created by code changes
• Finding functions whose blast radius or complexity grew silently
• Identifying taint propagation changes across refactors
• Pre-release structural comparison (tag-to-tag or branch-to-branch)

When NOT to Use

• Line-level code review (use differential-review for text-diff analysis)
• Single-snapshot analysis (use the trailmark skill directly)
• Diagram generation from a single snapshot (use the diagramming-code skill)
• Mutation testing triage (use the genotoxic skill)

Rationalizations to Reject

---

Prerequisites

trailmark must be installed. If uv run trailmark fails, run:

uv pip install trailmark

DO NOT fall back to "manual comparison" or reading source files as a substitute for running trailmark. The tool must be installed and used programmatically. If installation fails, report the error.

---

Quick Start

# Compare two git refs (e.g., tags, branches, commits)
# 1. Build graphs at each snapshot
# 2. Run pre-analysis on both
# 3. Compute structural diff
# 4. Generate report

# Step-by-step: see Workflow below

---

Decision Tree

├─ Need to understand what each metric means?
│  └─ Read: references/evolution-metrics.md
│
├─ Need the report output format?
│  └─ Read: references/report-format.md
│
├─ Already have two graph JSON exports?
│  └─ Jump to Phase 3 (run native diff + graph_diff.py)
│
└─ Starting from two git refs?
   └─ Start at Phase 1

---

Workflow

Graph Evolution Progress:
- [ ] Phase 1: Create snapshots (git worktrees)
- [ ] Phase 2: Build graphs + pre-analysis on both snapshots
- [ ] Phase 3: Compute structural diff
- [ ] Phase 4: Interpret diff and generate report
- [ ] Phase 5: Clean up worktrees

Phase 1: Create Snapshots

Use git worktrees to get clean copies of each ref without disturbing the working tree.

# Create temp directories for worktrees
BEFORE_DIR=$(mktemp -d)
AFTER_DIR=$(mktemp -d)

# Create worktrees (run from repo root)
git worktree add "$BEFORE_DIR" {before_ref}
git worktree add "$AFTER_DIR" {after_ref}

If comparing two directories instead of git refs, skip this phase and use the directory paths directly in Phase 2.

Phase 2: Build Graphs and Run Pre-Analysis

Build Trailmark graphs for both snapshots and run pre-analysis on each. Pre-analysis computes blast radius, taint propagation, privilege boundaries, and entrypoint enumeration.

from trailmark.query.api import QueryEngine

def build_and_export(target_dir, output_path, language="auto"):
    """Build graph, run pre-analysis, export JSON."""
    engine = QueryEngine.from_directory(target_dir, language=language)
    engine.preanalysis()
    json_str = engine.to_json()
    with open(output_path, "w") as f:
        f.write(json_str)
    return engine.summary()

import tempfile, os
work_dir = tempfile.mkdtemp(prefix="trailmark_evolution_")
before_json = os.path.join(work_dir, "before_graph.json")
after_json = os.path.join(work_dir, "after_graph.json")

before_summary = build_and_export(
    "{before_dir}", before_json
)
after_summary = build_and_export(
    "{after_dir}", after_json
)

Verify both graphs built successfully by checking the summary output. If either fails, rerun with an explicit language or comma-separated list instead of auto.

Phase 3: Compute Structural Diff

Run both:

1. Trailmark's native structural diff for nodes, edges, and entrypoints 2. The plugin's graph_diff.py helper for subgraph membership changes

Using the same work_dir from Phase 2:

trailmark diff --json "{before_dir}" "{after_dir}" > "{work_dir}/trailmark_diff.json" || \
  uv run trailmark diff --json "{before_dir}" "{after_dir}" > "{work_dir}/trailmark_diff.json"

uv run {baseDir}/scripts/graph_diff.py \
    --before "{before_json}" \
    --after "{after_json}" > "{work_dir}/subgraph_diff.json"

If either diff command fails or writes an empty JSON file, stop and report the error instead of continuing to Phase 4.

The native Trailmark diff contains:

The subgraph diff contains:

Phase 4: Interpret Diff and Generate Report

Read both diff JSON files and generate a security-focused markdown report. See references/report-format.md for the full template.

Interpretation priorities (highest to lowest):

1. New tainted paths — nodes entering the tainted subgraph, especially if they also appear in added edges targeting sensitive functions 2. Privilege boundary changes — new or removed trust transitions from the native entrypoint/edge diff plus the subgraph diff 3. Attack surface growth — new entrypoints, especially untrusted_external, from trailmark_diff.json 4. Blast radius increases — nodes entering high_blast_radius 5. Complexity spikes — CC increases > 3 on tainted or entrypoint-reachable nodes 6. Structural additions — new nodes and edges (review needed) 7. Structural removals — verify removed security functions were replaced

Cross-reference structural changes with git diff {before_ref}..{after_ref} to add source-level context to findings.

Severity classification:

For detailed metric definitions, see references/evolution-metrics.md.

Phase 5: Clean Up

Remove git worktrees after the report is written:

git worktree remove "{before_dir}"
git worktree remove "{after_dir}"

---

Diff Reference

trailmark diff --json BEFORE AFTER
uv run {baseDir}/scripts/graph_diff.py [OPTIONS]

Use trailmark diff for:

• Node/edge changes
• Added/removed/modified entrypoints
• Human-readable structural diff reports

Use graph_diff.py for:

• Subgraph membership changes derived from engine.preanalysis()
• tainted, high_blast_radius, privilege_boundary, and related sets

graph_diff.py input format: Trailmark JSON exports from engine.to_json(). graph_diff.py output: JSON structural diff for nodes, edges, and subgraphs.

---

Quality Checklist

Before delivering the report:

• [ ] Both graphs built successfully (check summaries)
• [ ] Pre-analysis ran on both snapshots
• [ ] Native Trailmark diff computed and non-empty (trailmark_diff.json)
• [ ] Subgraph diff computed and non-empty (subgraph_diff.json)
• [ ] All subgraph changes interpreted (tainted, blast radius, etc.)
• [ ] Critical findings include evidence (node IDs, edge diffs)
• [ ] Severity levels assigned to all findings
• [ ] Source-level context added via git diff cross-reference
• [ ] Worktrees cleaned up (or temp dirs removed)
• [ ] Report written to GRAPH_EVOLUTION_*.md

---

Integration

trailmark skill: Phase 2 uses the trailmark API for graph building and pre-analysis. All trailmark query patterns work on either snapshot's engine.

differential-review skill: Use graph-evolution for structural analysis, differential-review for line-level code review. The two are complementary — graph-evolution finds attack paths that text diffs miss, while differential-review provides git blame context and micro-adversarial analysis.

genotoxic skill: If graph-evolution reveals new high-CC tainted nodes, feed them to genotoxic for mutation testing triage.

diagramming-code skill: Generate before/after diagrams to visualize structural changes. Use call-graph or data-flow diagrams focused on changed nodes.

---

Supporting Documentation

• [references/evolution-metrics.md](references/evolution-metrics.md) —

What each structural metric means and why it matters for security

• [references/report-format.md](references/report-format.md) —

Report template, severity classification, and example findings

Evolution Metrics Reference

This document explains each structural metric the graph-evolution skill tracks and why it matters for security analysis.

Contents

• Node changes (added, removed, modified)
• Edge changes (added, removed)
• Complexity evolution
• Attack surface changes
• Blast radius shifts
• Taint propagation changes
• Privilege boundary changes

---

Node Changes

Added Nodes

New functions, methods, classes, or modules introduced between snapshots.

Security relevance:

• New code has no review history and may lack test coverage
• New public functions expand the attack surface
• New classes may introduce state management complexity

Triage: Cross-reference added nodes against the after graph's entrypoints subgraph. Added nodes that are entrypoint-reachable get highest review priority.

Removed Nodes

Functions, methods, or classes deleted between snapshots.

Security relevance:

• Removed validation functions may indicate weakened security controls
• Removed error handlers can expose unhandled edge cases
• Dead code removal is generally positive (reduces attack surface)

Triage: Check if removed nodes had privilege_boundary or taint_propagation annotations. If so, verify the security function was replaced, not just deleted.

Modified Nodes

Nodes present in both snapshots whose properties changed. Tracked properties:

---

Edge Changes

Added Edges

New call relationships between functions.

Security relevance:

• New calls from untrusted entrypoints to sensitive functions create

attack paths that did not previously exist

• New inherits or implements edges can change polymorphic dispatch
• Cross-module calls may violate existing trust boundaries

Triage: For each added calls edge, check if source is in the tainted subgraph and target handles sensitive operations.

Removed Edges

Call relationships that no longer exist.

Security relevance:

• Removed validation calls may mean input is no longer checked
• Removed authorization calls can create privilege escalation
• Usually benign during refactoring, but verify removed edges

between security-relevant nodes

---

Complexity Evolution

Tracks per-node cyclomatic complexity changes between snapshots.

Thresholds:

Aggregate signals:

• Mean CC increase across all modified nodes indicates codebase is

growing more complex

• Functions that crossed the CC > 10 threshold are new fuzzing

candidates (per the genotoxic skill's criteria)

---

Attack Surface Changes

Derived from the entrypoints subgraph.

New entrypoints: Nodes that appear in the after entrypoints but not before. Each new entrypoint is a new way external input reaches the system.

Removed entrypoints: Nodes that were entrypoints in before but not after. Usually positive (reduced surface), but verify the functionality wasn't just moved.

Trust level changes: Compare entrypoint trust levels between snapshots. A function changing from trusted_internal to untrusted_external is a significant security event.

---

Blast Radius Shifts

Derived from the high_blast_radius subgraph (nodes with 10+ downstream dependents).

New high-blast nodes: Nodes that entered high_blast_radius in after. These now affect many downstream functions — bugs here have wide impact.

Reduced blast radius: Nodes that left high_blast_radius. Usually positive (decoupling), but verify the downstream functions weren't orphaned.

---

Taint Propagation Changes

Derived from the tainted subgraph (nodes reachable from untrusted entrypoints).

Newly tainted: Nodes that entered tainted in after. These can now be reached by untrusted input and must validate their inputs.

De-tainted: Nodes that left tainted. Usually means a trust boundary was added or an entrypoint was removed.

Critical combination: Nodes that are both newly tainted AND had their CC increase. These are the highest-priority review targets.

---

Privilege Boundary Changes

Derived from the privilege_boundary subgraph (edges where trust levels change).

New boundary crossings: Functions that appeared on a privilege boundary. These are points where trust transitions happen — common vulnerability locations.

Removed boundaries: Privilege boundaries that disappeared. Could mean trust was flattened (potentially unsafe) or that the boundary moved (needs verification).

Report Format Reference

Output format for graph-evolution reports. The report is a markdown file summarizing structural changes between two code graph snapshots.

Contents

• Report filename convention
• Section-by-section template
• Severity classification
• Example snippets

---

Filename Convention

GRAPH_EVOLUTION_<project>_<before-ref>_<after-ref>.md

Example: GRAPH_EVOLUTION_myapp_v1.2.0_v1.3.0.md

---

Report Template

# Graph Evolution Report

**Project:** {project_name}
**Before:** {before_ref} ({before_date})
**After:** {after_ref} ({after_date})
**Language:** {language}

## Summary

| Metric | Before | After | Delta |
|--------|--------|-------|-------|
| Total nodes | N | N | +/-N |
| Functions | N | N | +/-N |
| Classes | N | N | +/-N |
| Call edges | N | N | +/-N |
| Entrypoints | N | N | +/-N |

## Critical Structural Changes

Changes with direct security implications. Each finding includes
the structural evidence and affected nodes.

### [SEVERITY] Finding title

**What changed:** Description of the structural change
**Evidence:** Node IDs, edge diffs, subgraph membership
**Security impact:** Why this matters
**Recommendation:** What to review or test

## Attack Surface Evolution

### New Entrypoints
| Node | Kind | Trust Level | File |
|------|------|------------|------|

### Removed Entrypoints
| Node | Kind | Trust Level | File |
|------|------|------------|------|

## Complexity Evolution

### Increased Complexity (CC delta > 0)
| Node | Before CC | After CC | Delta | File |
|------|-----------|----------|-------|------|

### Decreased Complexity (CC delta < 0)
| Node | Before CC | After CC | Delta | File |
|------|-----------|----------|-------|------|

## Taint Propagation Changes

### Newly Tainted Nodes
| Node | Kind | Tainted Via | File |
|------|------|-------------|------|

### De-Tainted Nodes
| Node | Kind | File |
|------|------|------|

## Blast Radius Shifts

### Nodes Entering high_blast_radius
| Node | Kind | Downstream Count | File |
|------|------|-----------------|------|

### Nodes Leaving high_blast_radius
| Node | Kind | File |
|------|------|------|

## Privilege Boundary Changes

### New Boundary Crossings
| Node | Trust Transition | File |
|------|-----------------|------|

### Removed Boundary Crossings
| Node | Trust Transition | File |
|------|-----------------|------|

## New Code (Added Nodes)
| Node | Kind | CC | File |
|------|------|----|------|

## Removed Code (Deleted Nodes)
| Node | Kind | CC | File |
|------|------|----|------|

## New Call Relationships (Added Edges)
| Source | Target | Kind |
|--------|--------|------|

## Removed Call Relationships (Deleted Edges)
| Source | Target | Kind |
|--------|--------|------|

## Methodology

- **Tool:** Trailmark graph-evolution
- **Before snapshot:** {before_ref}
- **After snapshot:** {after_ref}
- **Pre-analysis:** blast radius, taint, privilege boundaries,
  entrypoints
- **Limitations:** {honest scope disclosure}

---

Severity Classification

Classify structural findings by security impact:

---

Example: Critical Finding

### [CRITICAL] New untrusted path to database query

**What changed:** Function `parse_user_input` (added) calls
`execute_query` (existing, tainted). This edge did not exist in the
before snapshot.

**Evidence:**
- Added edge: `parse_user_input` → `execute_query` (calls, certain)
- `execute_query` is in `high_blast_radius` (47 downstream nodes)
- `parse_user_input` is in `tainted` subgraph
- `parse_user_input` CC = 12 (above fuzzing threshold)

**Security impact:** Untrusted external input can now reach database
query execution through a complex, high-blast-radius path.

**Recommendation:**
1. Verify input validation on `parse_user_input`
2. Add parameterized query usage in `execute_query`
3. Write fuzz harness targeting `parse_user_input`