gitnexus-taint-analysis

GitNexus による CFG とテイント解析

オプトインの --pdg プログラム解析サブシステムに関するエキスパート知識: 制御フロー グラフ、到達定義、および手続き内 + 手続き間テイントです。gitnexus/src/core/ingestion/cfg/** や gitnexus/src/core/ingestion/taint/** に触れる前、または検出結果を説明するときにこれを読んでください。

使用すべきとき

• 「テイントエンジンはどのように動作しますか / このフローが (報告され) ないのはなぜですか?」
• モデルにソース、シンク、またはサニタイザーを追加する。
• CFG / 到達定義 / テイント / サマリーのコードを拡張またはレビューする。
• explain MCP ツールの検出結果 (手続き内 vs 手続き間) を理解する。
• --pdg 出力の誤検出または検出漏れをデバッグする。

階層化された基盤 (ビルド順)

テイントはグラフの上で実行され、その横で実行されるのではありません。各層は --pdg の背後でオプトインであり、デフォルトの analyze 実行はバイト単位で同一です (ゴールデンパリティゲートは、ここでのすべての変更に対するハードフロアです)。

L1  CFG            per-function basic blocks + control-flow edges   (M1 #2081)
L2  REACHING_DEF   GEN/KILL def→use data dependence (pure solver)   (M2 #2082)
L3  Taint (intra)  source→sink over RD facts, minus sanitizers      (M3 #2083)
L4  Taint (inter)  per-function summaries composed over CALLS       (M4 #2084)

• ワーカーが構築し、メインスレッドが解決します。 パースワーカーは各関数の CFG を構築し、def/use + 呼び出しサイトのファクトを ParsedFile.cfgSideChannel に収集します (プレーンで structured-clone 安全なデータ — AST ノードは決して含みません)。メインスレッドが 純粋なソルバーを実行します。メインスレッドで再パースしては決してなりません (#1983 の OOM を再導入します)。
• フェーズ内エミット (KTD1)。 L1〜L4-harvest はすべてスコープ解決の pdg ウィンドウ (scope-resolution/pipeline/run.ts、input.pdg === true でゲート) の内部で実行されます。 なぜなら、ディスクベースの ParsedFile ストアはそのフェーズが終わるとクリアされるためです — 独立した post-mro フェーズは空のデータを読むことになります。関数間の不動点 (L4) は例外です: これはスコープ解決の後に独自に登録されたフェーズ (taintSummaries) で実行されます。 なぜなら、完全な呼び出しグラフが必要であり、ScopeResolutionOutput を介して スレッディングされた小さなプレーンなサマリーデータを消費するからです。
• 純粋ソルバー契約。 computeReachingDefs、computeTaintFlows、 harvestFunctionSummary、および solveInterprocTaint は純粋かつ決定論的です (グラフなし、I/Oなし、ロガーなし; ソート済み出力)。スナップショットテストと コンテンツ由来のエッジ ID はこれに依存しています。

手続き内テイント (L3)

マッチしたソースからマッチしたシンクへの RD ファクトに対する前方到達可能性であり、 サニタイザーによってキルされます。内面化する価値のある主要な設計ポイント:

• 出現タグ付きサイト。 引数ごとのフラットなバインディングセットでは exec(escape(x)) (安全) と exec(x) (検出) を区別できません; ハーベストはネストされた 呼び出し構造 (SiteRecord.parent/via-tags) を記録するため、サニタイザーの介在が 正確になります。
• 種類セットのサニタイザーモデル。 テイントは無効化された SinkKind のセットを運びます; シンクはその種類がセットに含まれていない限り発火します。したがって escape(req.body) は res.send (xss) を抑制しますが、db.query (sql) は依然として発火します — 種類を無視した キルは、抑制された生きたインジェクションになります (禁じられた FN の方向)。 path.basename(t) はパストラバーサルのみを無効化し、コマンドインジェクションは無効化しません。
• ステートメントレベルの検出同一性。 ブロックペアではありません (ブロックの混同は 異なる検出を落とします; exec(req.body, req.query) は 2 つの検出です)。
• TAINTED エッジ (BasicBlock→BasicBlock) として永続化されます; パスは 共有のバージョン付きコーデック (taint/path-codec.ts) を介して reason カラムに乗ります。

手続き間テイント (L4) — 関数型/サマリー方式

実運用のアプローチ (Sharir-Pnueli 1981、Meta の Pysa や Mariana Trench、FB Infer と同じ形) — 完全な IFDS タビュレーションではありません。各関数はコンパクトな サマリー に還元され、サマリーはすでに解決済みの CALLS グラフ上で合成されます。

サマリーの形 (taint/summary-model.ts、パラメータ全体の粒度):

エッジ	意味	対応するもの
param→return	パラメータが戻り値に流れる	TITO — 予約済み (床はすでにその再現率をカバーしており、精度パスは保留)
param→callee-arg	パラメータが呼び出しの引数 j に流れ込む (そのパスの無効化されたシンク種別を運ぶ)	呼び出し先への TITO
param→sink	パラメータがモデル化されたシンクに到達する	部分的/トリガーされたシンク
source→return	関数がソースを生成して返す	生成的 — 呼び出し元の callResults を介して 合成 される
source→callee-arg	生成されたソースが呼び出しに流れ込む	不動点 SEED
callResults	ユーザー関数呼び出しの結果が呼び出し元のシンク/戻り値/呼び出し先引数に流れる	呼び出し先の source→return と合成される

不動点 (taint/interproc-solver.ts): 単位は (関数, パラメータ, ソース) です。source→callee-arg からシードし、param→callee-arg を介して伝播し、テイントされたパラメータが param→sink に遭遇したときに所見を発火します。

• 単調性によるサイクル安全。 テイント集合は有限格子 (fn × param × source) 上で単調であるため、ワークリストは収束します — 再帰呼び出しは単にすでに訪問済みのエントリを再提案するだけです。SCC 縮約は処理順序を洗練させるだけであり、正当性/終了性はそれを必要としません。
• ソースで識別される状態 (基盤となる要素)。 状態は SOURCE によってもキー付けします。(fn, param) だけでキー付けするとマルチソースフローが崩壊します。ソース A によってテイントされたシンクパラメータが訪問済みとマークされ、ソース B からの後続のフローが発火前に破棄される — 繰り返し発生するマルチソースバグの類型です。(ビット M3、ビット M4 U9。)
• 名前ベースの呼び出し結合。 サマリーの呼び出し引数エッジを CALLS エッジに、呼び出しサイトの行ではなく CALLEE NAME でマッチします — 行ベースの整合性 (CFG は 1 始まり vs 参照サイト) は脆弱であり、呼び出し先の同一性は正確で、コンテキスト非感度はすべての呼び出しサイトで呼び出し先のパラメータを同一にテイントします。
• TAINT_PATH エッジ (Function→Function) として永続化され、reason 内の関数レベルのホップチェーンは同じコーデックを介し、信頼度は手続き内の 1.0 より低くなります。

コンテキスト非感度 はこの階層で受け入れられるトレードオフです。関数ごとに 1 つのサマリー、戻り値/呼び出しサイトのマージは受け入れられます (セキュリティ上は保守的)。マージによる一部の FP が予想されます。より大きな FN の源はモデル化されていない機能です (以下を参照)。

既知の偽陰性クラス (文書化済み、保留)

最大のものは クロージャ/コールバック (arr.forEach(() => sink(y))) です — コールバックへのテイントはライブラリごとのモデルなしでは破棄されます (CodeQL の JS ライブラリでも同様です)。また保留中なのは、フィールド/プロパティフロー (obj.x = taint; sink(obj.y))、フィールド感度のあるアクセスパス、ガード形式のサニタイザー、暗黙的/制御依存フロー、promise/async-await のスレッディング、そして テイントされた単純パラメータより前の分割代入/レストパラメータ です (サマリーのポートインデックスは束縛の順序であり、仮引数の位置ではありません — ワーカーの BindingEntry から仮引数インデックスをスレッディングする必要があります)。手続き間の結合もまたコンテキスト非感度です。1 つの呼び出し元が 2 つの異なる 同名の呼び出し先 を呼び出すとき、一方へのフローが両方に過剰帰属されます (サウンド — 過剰報告であり、フローの見逃しには決してなりません)。所見の不在は安全の証明ではありません。

GitNexus 固有の注意点

• Function↔CFG の結合。 FunctionCfg.functionStartLine は1始まりですが、Function／ Method ノードの startLine は0始まりです。startLine - 1 で結合してください。Function ノードには 列番号がないため、同じ行にある関数（{a:()=>x(), b:()=>y()}）は 曖昧になります。誤結合するのではなく、除外してください（summary driver は unresolved を カウントします）。
• リレーションシッププロパティのインデックスなし（S1）。 Kuzu はリレーションシップ プロパティにセカンダリインデックスを持たず、アンカーのない [:TAINTED*]／[:TAINT_PATH*] クエリは 処理が爆発的に増えます。そのため、TAINT_PATH は解析時に具体化され、アンカーを付けて保存されます。 実行時に走査されることはありません。explain はソースをアンカーにして、LIMIT で制限したうえで読み取ります。
• 検出手段は explain のみです。 TAINTED／TAINT_PATH は意図的に VALID_RELATION_TYPES（impact の許可リスト）および Web スキーマ（security.test.ts に固定）から 除外されています。explain は両方のレイヤーを列挙します （関数をまたぐ検出結果には interprocedural: true が付きます）。
• 共有コーデックは1つだけ。 出力経路と explain の両方が taint/path-codec.ts をインポートします。ワイヤ形式を手作業で実装したものを2つ作ると差異が生じます。 分岐させないでください。新しいメタデータは、書き込み側と読み取り側を同時にリリースする場合、 バージョン内で形式を拡張してください。
• キャッシュ互換性。 Worker の収集内容の変更は、PDG アーティファクトの識別情報を通じて自動的に無効化されます。 抽出のみの依存関係は PDG の所有境界内に維持し、通常の解析キーが安定していることを確認してください。 共有パーサーの変更はベース識別情報に含めます。永続化されたグラフ／設定の変更は、 RepoMeta.pdg のキー集合の不一致を通じて反映され、全体の書き戻しが行われます。 モデルの内容は taintModelVersion に反映されます。

ソース／シンク／サニタイザーの追加

汚染モデルは、3つのファイルに分かれた4つの SupportedLanguages ID を対象とします。 TypeScript と JavaScript は taint/typescript-model.ts、Python は taint/python-model.ts、Java は taint/java-model.ts を使用します。対象言語のモデルを編集してください。 typescript-model.ts にある明示的な registerBuiltinTaintModels の接続箇所で4言語すべてを登録します。 これはインポート時の副作用ではありません。

仕様はハッシュ化できるデータであり（関数は含みません）、サニタイザーの neutralizes には、 防御するシンクの種類を正確に列挙します。無条件にすべてを無効化する指定はしないでください。 フィクスチャを追加し、test/unit/taint/ で検出結果（または検出されないこと）をアサートしてください。 TypeScript と JavaScript では実際のソースを使うハーネス test/helpers/ts-cfg-harness.ts を使用します。 Python と Java のモデル一致は python-model-match.test.ts と java-model-match.test.ts でカバーされます。エンドツーエンドの検証は test/integration/cfg/ で行います。

--pdg を変更する際の検証チェックリスト

1. tsc clean (schema additions are exhaustiveness-checked; watch the
   api.ts getNodeQuery runtime read-path if a node label is added).
2. Targeted vitest by directory (test/unit/taint, test/unit/cfg,
   test/integration/cfg) — verify by ISOLATION, not full-suite exit
   (known load-flakes). `node scripts/build.js` before worker/integration runs.
3. Flag-off golden byte-identical (pipeline-graph-golden.test.ts).
4. bench/cfg/measure.mjs --check (no fingerprint drift / budget regression).
5. detect_changes() before commit; impact({direction:'upstream'}) before
   editing shared symbols (KnowledgeGraph, RepoMeta, RelationshipType, codec).

先行事例（設計上の詳しい検討事項向け）

Sharir & Pnueli 1981（関数型アプローチ）；Reps-Horwitz-Sagiv IFDS（POPL 1995）； FlowDroid／StubDroid（アクセスパスの要約）；Pysa & Mariana Trench（TITO／ 伝播、並列 SCC 固定点）；CodeQL Models-as-Data（コールバックポートを含む、最も豊富なポート記法）； Infer（コンテンツキーに基づく増分要約）。