interface:
  display_name: "Graph Evolution"
  short_description: "Compare code graphs for security-relevant structural changes"
  icon_small: "assets/trail-of-bits-mark.svg"
  icon_large: "assets/trail-of-bits-mark.svg"
  brand_color: "#D83A34"

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

| Property | What Changed | Security Concern |
|----------|-------------|-----------------|
| `cyclomatic_complexity` | Control flow complexity | Higher CC = more paths to test |
| `parameters` | Function signature | New params may accept untrusted input |
| `return_type` | Return type annotation | Type changes can break callers |
| `line_span` | Lines of code | Significant growth may indicate added logic |

---

## 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:**

| CC Delta | Significance |
|----------|-------------|
| +1 to +3 | Minor — likely a new branch or error check |
| +4 to +9 | Moderate — new logic paths need test coverage |
| +10 or more | Major — function is becoming difficult to reason about |
| Negative | Positive — simplification usually reduces bug surface |

**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

```markdown
# 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:

| Severity | Criteria |
|----------|----------|
| **CRITICAL** | New tainted path to sensitive function, removed auth boundary |
| **HIGH** | New entrypoint + high blast radius, CC increase > 10 on tainted node |
| **MEDIUM** | New call edges crossing trust boundaries, moderate CC increase |
| **LOW** | Added nodes without entrypoint reachability, cosmetic changes |
| **INFO** | Dead code removal, complexity reductions, positive changes |

---

## Example: Critical Finding

```markdown
### [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`
```

# /// script
# requires-python = ">=3.12"
# ///
"""Compute structural diff between two Trailmark graph JSON exports.

Compares nodes, edges, complexity, subgraph membership, and
pre-analysis results to surface security-relevant structural changes.
"""

from __future__ import annotations

import argparse
import json
import sys
from pathlib import Path
from typing import Any


def load_graph(path: str) -> dict[str, Any]:
    """Load and validate a Trailmark JSON export."""
    data = json.loads(Path(path).read_text())
    for key in ("nodes", "edges"):
        if key not in data:
            print(f"ERROR: Missing '{key}' in {path}", file=sys.stderr)
            sys.exit(1)
    return data


def diff_nodes(
    before: dict[str, Any],
    after: dict[str, Any],
) -> dict[str, Any]:
    """Compute added, removed, and modified nodes."""
    before_ids = set(before.keys())
    after_ids = set(after.keys())

    added = _summarize_nodes(after, after_ids - before_ids)
    removed = _summarize_nodes(before, before_ids - after_ids)
    modified = _find_modified(before, after, before_ids & after_ids)

    return {"added": added, "removed": removed, "modified": modified}


def _summarize_nodes(
    nodes: dict[str, Any],
    ids: set[str],
) -> list[dict[str, Any]]:
    """Extract summary dicts for a set of node IDs."""
    result = []
    for nid in sorted(ids):
        node = nodes[nid]
        result.append(
            {
                "id": nid,
                "name": node.get("name", ""),
                "kind": node.get("kind", ""),
                "file": _node_file(node),
                "cyclomatic_complexity": node.get("cyclomatic_complexity"),
            }
        )
    return result


def _node_file(node: dict[str, Any]) -> str:
    """Extract file path from a node's location."""
    loc = node.get("location", {})
    if isinstance(loc, dict):
        return loc.get("file_path", "")
    return ""


def _find_modified(
    before: dict[str, Any],
    after: dict[str, Any],
    shared_ids: set[str],
) -> list[dict[str, Any]]:
    """Find nodes present in both with changed properties."""
    modified = []
    for nid in sorted(shared_ids):
        b, a = before[nid], after[nid]
        changes = _compare_node_properties(b, a)
        if changes:
            modified.append({"id": nid, "changes": changes})
    return modified


def _compare_node_properties(
    before: dict[str, Any],
    after: dict[str, Any],
) -> dict[str, Any]:
    """Compare security-relevant properties of two node versions."""
    changes: dict[str, Any] = {}
    cc_b = before.get("cyclomatic_complexity")
    cc_a = after.get("cyclomatic_complexity")
    if cc_b != cc_a:
        changes["cyclomatic_complexity"] = {
            "before": cc_b,
            "after": cc_a,
        }

    params_b = _param_signature(before)
    params_a = _param_signature(after)
    if params_b != params_a:
        changes["parameters"] = {
            "before": params_b,
            "after": params_a,
        }

    ret_b = _return_type_str(before)
    ret_a = _return_type_str(after)
    if ret_b != ret_a:
        changes["return_type"] = {"before": ret_b, "after": ret_a}

    span_b = _line_span(before)
    span_a = _line_span(after)
    if span_b != span_a:
        changes["line_span"] = {"before": span_b, "after": span_a}

    return changes


def _param_signature(node: dict[str, Any]) -> list[str]:
    """Extract parameter names from a node."""
    params = node.get("parameters", ())
    if isinstance(params, (list, tuple)):
        return [p.get("name", "") if isinstance(p, dict) else str(p) for p in params]
    return []


def _return_type_str(node: dict[str, Any]) -> str | None:
    """Extract return type string from a node."""
    rt = node.get("return_type")
    if isinstance(rt, dict):
        return rt.get("name")
    return rt


def _line_span(node: dict[str, Any]) -> int:
    """Compute line count from a node's location."""
    loc = node.get("location", {})
    if isinstance(loc, dict):
        start = loc.get("start_line", 0)
        end = loc.get("end_line", 0)
        return max(0, end - start + 1)
    return 0


def diff_edges(
    before: list[dict[str, Any]],
    after: list[dict[str, Any]],
) -> dict[str, Any]:
    """Compute added and removed edges."""
    before_set = {_edge_key(e) for e in before}
    after_set = {_edge_key(e) for e in after}

    added = sorted(after_set - before_set)
    removed = sorted(before_set - after_set)

    return {
        "added": [_parse_edge_key(k) for k in added],
        "removed": [_parse_edge_key(k) for k in removed],
    }


def _edge_key(edge: dict[str, Any]) -> str:
    """Create a hashable key for an edge."""
    src = edge.get("source", edge.get("source_id", ""))
    tgt = edge.get("target", edge.get("target_id", ""))
    kind = edge.get("kind", "")
    return f"{src}|{tgt}|{kind}"


def _parse_edge_key(key: str) -> dict[str, str]:
    """Convert an edge key back to a dict."""
    source, target, kind = key.split("|", 2)
    return {"source": source, "target": target, "kind": kind}


def diff_subgraphs(
    before: dict[str, list[str]],
    after: dict[str, list[str]],
) -> dict[str, Any]:
    """Compute per-subgraph membership changes."""
    all_names = sorted(set(before.keys()) | set(after.keys()))
    changes: dict[str, Any] = {}

    for name in all_names:
        b_ids = set(before.get(name, []))
        a_ids = set(after.get(name, []))
        added = sorted(a_ids - b_ids)
        removed = sorted(b_ids - a_ids)
        if added or removed:
            changes[name] = {"added": added, "removed": removed}

    return changes


def compute_summary_delta(
    before: dict[str, Any],
    after: dict[str, Any],
) -> dict[str, Any]:
    """Compute deltas for summary statistics."""
    b_sum = before.get("summary", {})
    a_sum = after.get("summary", {})
    delta: dict[str, Any] = {}

    for key in ("total_nodes", "functions", "classes", "call_edges", "entrypoints"):
        b_val = b_sum.get(key, 0)
        a_val = a_sum.get(key, 0)
        if b_val != a_val:
            delta[key] = {
                "before": b_val,
                "after": a_val,
                "delta": a_val - b_val,
            }
    return delta


def compute_diff(
    before: dict[str, Any],
    after: dict[str, Any],
) -> dict[str, Any]:
    """Compute the full structural diff between two graphs."""
    return {
        "summary_delta": compute_summary_delta(before, after),
        "nodes": diff_nodes(
            before.get("nodes", {}),
            after.get("nodes", {}),
        ),
        "edges": diff_edges(
            before.get("edges", []),
            after.get("edges", []),
        ),
        "subgraphs": diff_subgraphs(
            before.get("subgraphs", {}),
            after.get("subgraphs", {}),
        ),
    }


def parse_args(argv: list[str] | None = None) -> argparse.Namespace:
    """Parse command-line arguments."""
    parser = argparse.ArgumentParser(
        description="Structural diff between Trailmark graphs",
    )
    parser.add_argument(
        "--before",
        required=True,
        help="Path to the 'before' graph JSON export",
    )
    parser.add_argument(
        "--after",
        required=True,
        help="Path to the 'after' graph JSON export",
    )
    parser.add_argument(
        "--indent",
        type=int,
        default=2,
        help="JSON output indentation (default: 2)",
    )
    return parser.parse_args(argv)


def main(argv: list[str] | None = None) -> None:
    """Entry point: load graphs, compute diff, print JSON."""
    args = parse_args(argv)
    before = load_graph(args.before)
    after = load_graph(args.after)
    diff = compute_diff(before, after)
    print(json.dumps(diff, indent=args.indent))


if __name__ == "__main__":
    main()