トラバーサル完全ガイド：アルゴリズムの基礎からパストラバーサル攻撃の実例・検出・防御まで
エバープレイ編集部はじめに — 「トラバーサル」とは何か
IT分野で「トラバーサル（traversal）」という用語は大きく二つの文脈で使われます。一つはデータ構造やグラフ・ツリーを巡回（走査）するアルゴリズムとしての「トラバーサル」、もう一つはファイルパスの誤利用を突く「パストラバーサル（ディレクトリトラバーサル）」というセキュリティ上の脆弱性を指す「トラバーサル攻撃」です。本コラムでは両者を明確に区別し、基本概念から実装／攻撃例、検出・防御まで詳しく解説します。
トラバーサル（走査）の基本概念 — データ構造における役割
アルゴリズムとしてのトラバーサルは、ノード（頂点）とエッジ（辺）で構成されるグラフや、親子関係を持つツリー構造を「系統的に訪問する」操作を指します。代表的な用途は以下のとおりです。
- 探索（ある条件を満たすノードを探す）
- データの列挙（全ノードを1回ずつ処理する）
- 最短経路や連結成分の計算（BFSやDFSを基礎に発展）
- コンパイラでの構文木走査、XML/JSONのパースや検査
トラバーサルはアルゴリズムの設計と効率に直接関わり、適切な方法を選ばないと計算時間・メモリが爆発することがあります。
代表的なトラバーサルアルゴリズム
最も基本的なものは深さ優先探索（DFS: Depth-First Search）と幅優先探索（BFS: Breadth-First Search）です。ツリーではさらに前順（preorder）、中順（inorder）、後順（postorder）などの順序が重要になります。
- DFS：再帰または明示的スタックを使って「深く」探索する。メモリは最悪で木の高さ（/グラフの深さ）に比例。経路追跡が容易。
- BFS：キューを使い「層（レベル）ごと」に探索する。最短経路（エッジ数最小）を求める際に有用。メモリは探索幅に依存。
- トラバーサル順序（ツリー）：pre/in/postはそれぞれ「訪問→子」「左→親→右」「子→訪問」などの処理順を定義し、各種アルゴリズム（式の評価、木の複製）で使い分けられる。
複雑なグラフでは巡回時に「既訪問ノードの検出（サイクルの回避）」が必須です。未処理だと無限ループに陥る可能性があります。
実践での利用例・応用分野
- 検索エンジンやクローラ：ウェブページやドキュメントの横断的収集
- コンパイラ／インタプリタ：抽象構文木（AST）のトラバーサルによるコード解析・最適化
- ネットワーク解析：トポロジや到達可能性分析
- データベースやファイルシステム：階層構造の列挙、バックアップ、権限評価
- 機械学習やグラフデータ分析：ノード埋め込みや近傍探索
実装上の注意点と落とし穴
再帰的実装は短く直感的ですが、深さが非常に深いケースでスタックオーバーフローを招きます。反対に反復実装（スタックやキューを明示的に使う）ではメモリ管理の自由度が上がります。さらに、競合状態やTOCTOU（Time-Of-Check To Time-Of-Use）問題、シンボリックリンクの扱い、負の重みを持つグラフでの誤った仮定など、実務上の落とし穴が存在します。
パストラバーサル（ディレクトリトラバーサル） — セキュリティ文脈
ここからは「パストラバーサル（path traversal）」に焦点を当てます。ウェブアプリケーションやファイルサーバがユーザ入力を理由にファイルパスを組み立てる際、攻撃者が「..」（親ディレクトリ）やパス区切り文字を用いて、本来アクセスできないファイルへ到達してしまう脆弱性がパストラバーサルです。CWE-22として定義され、長年にわたり現場で多く検出されている攻撃手法です。
攻撃の具体例
典型的な脆弱なサーバ側コード（擬似）：
GET /download?file=report.pdf → サーバ側で "/var/www/files/" + file を返す
攻撃者はパラメータに "../../etc/passwd" を入れることで、"/var/www/files/../../etc/passwd" → 正規化後に "/etc/passwd" を参照可能になり、機密情報を取得できる可能性があります。URLエンコード（%2e%2e）、UTF-8/Unicode混入、相対パスやWindowsのバックスラッシュ「..\\」など多彩なエンコーディングで試みられます。
原因となる実装パターン
- ユーザ入力をそのままパス連結してファイルアクセスする（ホワイトリスト不在）
- 入力正規化（正規化・デコード）を怠る／誤って行う
- シンボリックリンク、リダイレクト、マウントポイントの扱いを考慮していない
- TOCTOUにより、チェック時と利用時でパスが変化する（競合状態）
検出・診断方法
- ダイナミックテスト（ペネトレーションテスト）：各種エンコードを用いたパラメータ送信で挙動を確認
- ファジング：ファイル名パラメータへパターンを大量投入して応答を観察
- 静的解析：ソースコード中のパス組み立て箇所、入力バリデーション不足を検出
- ログ分析：異常なパスや複数回のデコード要求、404/500の頻発を監視
実践的な防御策（ベストプラクティス）
以下は現場で推奨される対策です。複数併用することで安全性が高まります。
- ホワイトリスト方式で有効なファイル・拡張子・IDのみ許可する（最も確実）
- サニタイズではなく「正規化（canonicalization）」を行い、正規化後のパスが期待するベースディレクトリ内にあるか確認する（realpath / Path.GetFullPath / path.normalize 等）
- OSや言語が提供する安全なAPIを使用する（例：openat、O_NOFOLLOW フラグでシンボリックリンク追跡を制限）
- 最小権限原則：アプリケーション実行ユーザに不要なファイルの読み取り権限を与えない
- 隔離（サンドボックス、コンテナ、chroot等）と権限分離を組み合わせる。chrootは万能ではなく、設定ミスや権限昇格に注意
- 入力の許容範囲を厳しく定義し、受け付けない文字やパターンは即座に拒否する（例：パス区切り文字、エンコード類の混入を禁止）
- ファイル操作のチェックと利用は原子操作を心がけ、TOCTOUの影響を低減する
フレームワーク／言語別の留意点
- PHP：basename(), realpath() の使い方に注意。realpath は存在しないパスで false を返す点や、シンボリックリンクの扱いに留意。
- Node.js：path.normalize(), path.resolve() による正規化を行い、必ずアプリケーションが許容するベースディレクトリを参照しているか確認する。
- .NET：Path.GetFullPath() を利用して正規化し、想定ベースフォルダとStartsWith等で比較。ただしケースセンシティブ/インセンシティブの違いに注意。
- Java：java.nio.file.Paths.get(...).toRealPath() 等で正規化し、Files.isSameFile 等を活用して検証する。
高度な対策と運用面
防御はコードだけで完結しません。CI/CD パイプラインに静的解析を組み入れ、ライブラリ脆弱性のスキャンやセキュリティテストを自動化します。WAF（Web Application Firewall）は既知パターンに対する保険になりますが、エンコード多様化やゼロデイには万能ではないため、根本的なコード修正を優先します。監査ログ・アラートの整備により、異常なファイルアクセス試行を早期検出できる体制も重要です。
まとめ：トラバーサルを正しく理解して安全を保つ
「トラバーサル」は良い意味ではデータ構造やファイルシステムを効率的に巡回する重要なアルゴリズム概念であり、悪い意味ではパストラバーサルという形で重大な情報漏洩を招く脆弱性を指します。開発者はアルゴリズム設計の基本と、外部入力を扱う際のセキュリティ原則（最小権限、ホワイトリスト、正規化、ライブラリ利用）を理解し、実装と運用の両面から対策を講じる必要があります。
