graph-evolution

Graph Evolution

2 つのソーススナップショットで Trailmark コードグラフを構築し、構造差分を計算します。テキストレベルの差分では見落とされる、セキュリティに関わる変更を明らかにします。新たな攻撃経路、複雑さの変化、影響範囲の拡大、汚染伝播の変更、権限境界の変更などが含まれます。

使用する場面

• 2 つの git ref を比較して、構造的に何が変わったかを把握する
• セキュリティに関わる進化を確認するため、コミット範囲を監査する
• コード変更によって生じた新たな攻撃経路を検出する
• 影響範囲や複雑さが気付かないうちに増大した関数を見つける
• リファクタリングによる汚染伝播の変更を特定する
• リリース前に構造を比較する（タグ間またはブランチ間）

使用しない場面

• 行単位のコードレビュー（テキスト差分の分析には differential-review を使用してください）
• 単一スナップショットの分析（trailmark スキルを直接使用してください）
• 単一スナップショットからの図の生成（diagramming-code スキルを使用してください）
• ミューテーションテストのトリアージ（genotoxic スキルを使用してください）

避けるべき合理化

合理化	それが誤りである理由	必須の対応
「構造差分だけあればよいので、事前分析は省略する」	事前分析をしないと、汚染の変化、影響範囲の拡大、権限境界の変化を見落とします	両方のスナップショットで engine.preanalysis() を実行する
「テキスト差分で変更点は把握できる」	テキスト差分では、新たな攻撃経路、推移的な複雑さの変化、サブグラフの所属変更を見落とします	テキスト差分を補完するために構造差分を使用する
「追加されたノードだけが重要だ」	セキュリティ機能の削除や権限境界の移動も、同じように危険です	追加だけでなく、削除と変更も確認する
「重大度の低い構造変更は無視してよい」	INFO レベルの変更（デッドコードの削除など）が、セキュリティチェックの削除を覆い隠している場合があります	すべての変更を分類し、置き換えられた機能がないか削除箇所を確認する
「比較には一方のスナップショットのグラフだけで十分だ」	単一スナップショットの分析では進化を検出できません。変更前と変更後の両方が必要です	常に両方のグラフを構築してエクスポートする
「ツールがインストールされていないので、手動で比較する」	手動の比較では、グラフ分析で検出できるものを見落とします	まず trailmark をインストールする
「差分が空だったので、構造的な変更は何もない」	trailmark diff は --language の既定値を python とし、対象がそれ以外の言語でも空の配列を返して終了コード 0 で終了します。そのため、差分が空の場合、コードに変更がないのか、言語の指定が誤っていたのかを判別できません	--language を明示して再実行してから、変更がないと結論付ける

---

前提条件

trailmark がインストールされている必要があります。uv run trailmark が失敗した場合は、次を実行してください。

uv tool install trailmark
# Python snippets: uv run --with trailmark python -   (a tool env is not importable)

trailmark の実行の代わりに「手動で比較」したり、ソースファイルを読んだりすることは絶対に避けてください。ツールをインストールし、プログラムから使用する必要があります。インストールに失敗した場合は、エラーを報告してください。

---

クイックスタート

# 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

---

判断ツリー

├─ 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

---

ワークフロー

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

フェーズ 1：スナップショットを作成する

git worktree を使用し、作業ツリーに影響を与えずに各 ref のクリーンなコピーを取得します。

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

git ref ではなく 2 つのディレクトリを比較する場合は、このフェーズを省略し、フェーズ 2 でディレクトリのパスを直接使用してください。

フェーズ 2：グラフを構築して事前分析を実行する

両方のスナップショットで Trailmark グラフを構築し、それぞれで事前分析を実行します。事前分析では、影響範囲、汚染伝播、権限境界、エントリーポイントの列挙を計算します。

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
)

概要の出力を確認し、両方のグラフが正常に構築されたことを確かめてください。いずれかが失敗した場合は、auto ではなく、言語を明示するか、カンマ区切りのリストを指定して再実行してください。

フェーズ 3：構造差分の計算

次の両方を実行します。

1. ノード、エッジ、エントリーポイントに対する Trailmark のネイティブ構造差分
2. サブグラフのメンバーシップ変更に対するプラグインの graph_diff.py ヘルパー

フェーズ 2 と同じ work_dir を使用し、フェーズ 2 のビルド時に指定したものと同じ --language 値を渡します。trailmark diff では、このフラグのデフォルト値は python です。そのため、別のターゲットでは、デフォルト値のまま実行すると終了コード 0 が返され、不一致を報告する代わりに空の配列が書き込まれます。

trailmark diff --json --language auto "{before_dir}" "{after_dir}" > "{work_dir}/trailmark_diff.json" || \
  uv run trailmark diff --json --language auto "{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"

フェーズ 2 で auto ではなく明示的な言語、またはカンマ区切りのリストを指定した場合は、ここでも同じ値を使用します。

いずれかの差分コマンドが失敗するか、空の JSON ファイルを書き込んだ場合は、処理を停止し、フェーズ 4 に進まずにエラーを報告します。

nodes、edges、entrypoints の配列がすべて空の trailmark_diff.json は、構造上の変更がなかったか、両方のスナップショットが（ほぼ）空のグラフとして解析されたことを意味します。どちらに該当するかは、フェーズ 2 のグラフ概要で判断します。いずれかのスナップショットのノード数が 0、またはターゲットとして不自然に少ない場合は、解析でコードを検出できていません。言語を明示的に指定（rust、solidity、python,rust）して、再実行してください。両方のスナップショットでノード数が正常で、差分が空の場合は、構造が実際に安定しています。

Trailmark のネイティブ差分には次の情報が含まれます。

キー	内容
summary_delta	ノード／エッジ／エントリーポイント数の変更
nodes.added	新しい関数、クラス、メソッド
nodes.removed	削除された関数、クラス、メソッド
nodes.modified	CC、パラメーター、行の範囲が変更された関数
edges.added	新しい呼び出し／継承／インポート関係
edges.removed	削除された関係
entrypoints	追加、削除、変更されたエントリーポイント

サブグラフ差分には次の情報が含まれます。

キー	内容
subgraphs	サブグラフごとのメンバーシップ変更（tainted、high_blast_radius など）

フェーズ 4：差分を解釈してレポートを生成

両方の差分 JSON ファイルを読み込み、セキュリティに焦点を当てた Markdown レポートを生成します。 完全なテンプレートについては、references/report-format.md を参照してください。

解釈の優先順位（高い順）：

1. 新しい tainted パス — tainted サブグラフに入るノード。特に、機密性の高い関数を対象とする追加エッジにも含まれる場合
2. 権限境界の変更 — ネイティブのエントリーポイント／エッジ差分とサブグラフ差分から確認できる、新たな信頼遷移または削除された信頼遷移
3. 攻撃対象領域の拡大 — 新しいエントリーポイント。特に trailmark_diff.json の untrusted_external
4. 影響範囲の拡大 — high_blast_radius に入るノード
5. 複雑さの急増 — tainted ノードまたはエントリーポイントから到達可能なノードで CC が 3 を超えて増加
6. 構造上の追加 — 新しいノードとエッジ（レビューが必要）
7. 構造上の削除 — 削除されたセキュリティ関数が置き換えられたことを確認

構造上の変更を git diff {before_ref}..{after_ref} と照合し、検出事項にソースレベルの背景情報を加えます。

重大度の分類：

重大度	構造上のシグナル
CRITICAL	機密性の高い関数への新しい tainted パス、認証境界の削除
HIGH	新しいエントリーポイントと大きな影響範囲、tainted ノードでの CC の大幅な増加
MEDIUM	信頼境界をまたぐ新しいエッジ、CC の中程度の増加
LOW	エントリーポイントから到達できないノードの追加
INFO	デッドコードの削除、複雑さの低下

指標の詳しい定義については、references/evolution-metrics.md を参照してください。

フェーズ 5：クリーンアップ

レポートの作成後に git worktree を削除します。

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

---

差分リファレンス

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

trailmark diff --language のデフォルトは python です。ほかの言語の対象に対しても、このデフォルトでは終了コード 0 で終了し、nodes、edges、entrypoints の各配列が空の整形式 JSON を出力します。そのため、必ずフラグを指定してください。auto は対象の下にあるサポート対象の言語をすべて検出してマージし、単一の名前（rust、solidity）またはカンマ区切りのリスト（python,rust）を指定すると、明示的な言語セットに固定されます。解析可能なものがスナップショットに何も含まれていない場合、auto は No supported languages detected under <path> を出力して明示的に失敗します。これは期待どおりの動作です。まず言語を確認してください。空の差分を何も変更されていない証拠と見なせるのは、その後です。

以下には trailmark diff を使用します。

• ノード／エッジの変更
• エントリーポイントの追加／削除／変更
• 人が読みやすい構造差分レポート

以下には graph_diff.py を使用します。

• engine.preanalysis() から導出されるサブグラフのメンバーシップ変更
• tainted、high_blast_radius、privilege_boundary および関連するセット

引数	デフォルト	説明
--before	必須	「変更前」のグラフ JSON のパス
--after	必須	「変更後」のグラフ JSON のパス
--indent	2	JSON 出力のインデント

graph_diff.py の入力形式：engine.to_json() による Trailmark JSON エクスポート。 graph_diff.py の出力：ノード、エッジ、サブグラフの JSON 構造差分。

---

品質チェックリスト

レポートを提出する前に、次を確認してください。

• 両方のグラフが正常に構築された（サマリーを確認）
• 両方のスナップショットで事前分析が実行された
• Trailmark のネイティブ差分が計算された（trailmark_diff.json）。空の場合は、両方のスナップショットの Phase 2 のノード数がゼロではないことを確認する。空であれば、安定していることを意味する
• サブグラフ差分が計算され、空ではない（subgraph_diff.json）
• すべてのサブグラフの変更を解釈した（tainted、爆発半径など）
• 重大な検出結果に証拠が含まれている（ノード ID、エッジ差分）
• すべての検出結果に重大度レベルが割り当てられている
• git diff の相互参照により、ソースレベルのコンテキストが追加されている
• ワークツリーがクリーンアップされている（または一時ディレクトリが削除されている）
• レポートが GRAPH_EVOLUTION_*.md に書き込まれている

---

統合

trailmark スキル： Phase 2 では、グラフの構築と事前分析に trailmark API を使用します。 すべての trailmark クエリパターンは、どちらのスナップショットのエンジンでも使用できます。

differential-review スキル： 構造分析には graph-evolution を、行単位のコードレビューには differential-review を使用します。この 2 つは相互補完的です。graph-evolution はテキスト差分では見逃される攻撃経路を検出し、differential-review は git blame のコンテキストと詳細な敵対的分析を提供します。

trailmark-review-gate スキル： ブランチ、プルリクエスト、修正コミット、またはリリース差分について PASS/WARN/FAIL/UNKNOWN の構造レビュー一式が必要な場合は、graph-evolution の後に trailmark-review-gate を使用します。このゲートは graph-evolution の出力に決定論的なレビュー規則を適用しますが、人によるレビューに取って代わるものではありません。

genotoxic スキル： graph-evolution によって、新たに高 CC の tainted ノードが明らかになった場合は、それらを genotoxic に渡してミューテーションテストのトリアージを行います。

diagramming-code スキル： 変更前と変更後の図を生成して、構造の変更を可視化します。 変更されたノードに焦点を当てた call-graph または data-flow の図を使用します。

---

関連ドキュメント

• references/evolution-metrics.md — 各構造メトリクスの意味と、セキュリティ上重要である理由
• references/report-format.md — レポートのテンプレート、重大度の分類、検出結果の例