第2章: 理論的基盤 — アクセス行列・HRU問題・形式的安全性

アクセス行列モデル — Butler Lampson (1971)

アクセス制御の理論的基盤は、1971年にButler Lampsonが発表したアクセス行列モデル（Access Matrix Model）に遡ります。 これはコンピュータシステムの保護状態（Protection State）を数学的に形式化した最初のモデルです。

アクセス行列モデルは三つ組 (S, O, A) で定義されます。

• S（Subjects）: システム内の主体の集合（ユーザー、プロセス、ロールなど）
• O（Objects）: 保護対象の客体の集合（ファイル、プリンタ、データベーステーブルなど）
• A（Access Matrix）: 各セル A[s, o] が主体 s の客体 o に対する権利の集合

たとえば A[Alice, file1] = {read, write} であれば、AliceはFile1を読み書きできる、という意味になります。

アクセス行列の具体例

以下の表は、3人のユーザー（Alice、Bob、Carol）が3つのオブジェクト（file1、file2、printer）に持つ権利を示します。

この行列は直感的にわかりやすいものの、実際のシステムでは主体・客体の数が爆発的に増大します。 100万ユーザー × 10億オブジェクトの行列を保持することは不可能であり、多くのセルが「権利なし（空集合）」になる疎行列（sparse matrix）となります。 そのため、アクセス行列をそのまま実装するのは非現実的です。

ACL vs Capabilityリスト — 疎行列の実装戦略

疎なアクセス行列を実用的に実装するには2つのアプローチがあります。列方向（Object単位）で切り出すACL（アクセス制御リスト）と、行方向（Subject単位）で切り出すCapabilityリストです。

graph TB
  subgraph matrix[アクセス行列]
    direction TB
    M["A[s,o] = 権利集合"]
  end
  subgraph acl[列方向で切り出し]
    direction TB
    ACL1["file1: {Alice:rwo, Bob:r}"]
    ACL2["file2: {Bob:rwo, Carol:r}"]
  end
  subgraph cap[行方向で切り出し]
    direction TB
    C1["Alice: {file1:rwo, printer:print}"]
    C2["Bob: {file1:r, file2:rwo}"]
  end
  matrix -->|列方向| acl
  matrix -->|行方向| cap
  style matrix fill:#8b5cf6,stroke:#6d28d9,color:#fff
  style acl fill:#3b82f6,stroke:#1d4ed8,color:#fff
  style cap fill:#10b981,stroke:#059669,color:#fff

Confused Deputy問題

Confused Deputy（混乱した代理人）問題は1988年にNorm Hardyが指摘した脆弱性パターンです。 権限を持つプログラム（Deputy）が、権限を持たない第三者に悪用されるシナリオです。

具体例：コンパイラプログラムは課金ファイルへの書き込み権限を持っています。 悪意あるユーザーが「出力ファイル」の名前として課金ファイルのパスを指定すると、 コンパイラはその操作が正当な要求かどうかを区別できずに課金ファイルを上書きしてしまいます。

Take-Grantモデル — 決定可能な安全性分析

HRU問題（次節）の一般ケースが決定不能である中、Take-Grantモデル（Jones, Lipton, Snyder, 1976-77）は より制約されたモデルで線形時間の安全性決定を実現しました。

Take-Grantモデルでは、保護状態を有向グラフ G = (V, E) として表します。

• V = S ∪ O：頂点は主体（S）または客体（O）
• E：辺は権利ラベル付き。s →[r] o は「s は o に対して権利 r を持つ」

graph LR
  Alice([Alice]) -->|take, grant| file1[/file1/]
  Alice([Alice]) -->|grant| Bob([Bob])
  Bob([Bob]) -->|read| file1[/file1/]
  Bob([Bob]) -->|take| Carol([Carol])
  Carol([Carol]) -.->|read 取得可能?| file1[/file1/]
  style Alice fill:#8b5cf6,stroke:#6d28d9,color:#fff
  style Bob fill:#3b82f6,stroke:#1d4ed8,color:#fff
  style Carol fill:#10b981,stroke:#059669,color:#fff
  style file1 fill:#374151,stroke:#6b7280,color:#fff

Take-Grantモデルは4つのルールのみで保護状態の遷移を定義します。

Take-Grantモデルの最大の利点は、can-share プレディケートの決定可能性です。 「主体 x が権利 r を主体/客体 y に伝搬できるか？」という問いに対して、 グラフを単純に探索するアルゴリズムで O(|V| + |E|) の線形時間で答えられます。

HRU問題 — 安全性の決定不能性

Harrison、Ruzzo、Ullmanの3名が1976年に発表した論文は、アクセス制御理論における最も重要な結果の一つを示しました。 一般的なアクセス制御システムにおける安全性問題は決定不能（undecidable）だというものです。

安全性の形式的定義

HRUモデルはアクセス行列モデルを拡張し、6つのプリミティブ操作で保護状態の遷移を定義します。

これらのプリミティブ操作を組み合わせたコマンド（Command）は、条件（前提部）と操作のリストで構成されます。

Safety Problem：あるHRUシステムにおいて、初期保護状態 Q₀ から始めて任意のコマンド列を実行したとき、 「権利 r が当初 A[s, o] に存在しなかった A[s, o] に enter されることがあるか？」をrのリーク（leak of r）と呼ぶ。 このリークが発生しないとき、そのシステムは権利 r に関して安全（safe）と言う。

決定可能な特殊ケース

一般ケースは決定不能ですが、コマンドの表現力を制限すると決定可能になります。 最も重要な特殊ケースがモノオペレーショナルシステム（mono-operational system）です。

モノオペレーショナルシステムとは、各コマンドが1つのプリミティブ操作のみを持つシステムです。 HRUは1976年の論文でこの場合の安全性が多項式時間で決定可能であることを証明しました。

決定可能性の全体マップ

*ABACはポリシー言語によっては決定不能になり得る。XACMLは実装によって異なる。

理論モデルから実装へ

本章で見た理論モデルは、実際の認可システム設計に次のような指針を与えます。

1. ACL vs Capabilityの選択：監査・権限取り消し重視ならACL、委任・分散環境重視ならCapabilityベース。多くの現実システムはハイブリッド
2. 安全性分析の限界認識：汎用システムの安全性は自動証明できない。モデルを制約（RBAC等）して検証可能性を確保する
3. Take-Grantの実践的価値：「この権限は伝搬できるか？」という問いはグラフ探索で線形時間に答えられる。OPA等のポリシーエンジンも本質的にこの考え方を応用している

次章では、これらの理論を踏まえて構築された最初の実用的モデルであるDAC（任意アクセス制御）とMAC（強制アクセス制御）の設計思想と限界を詳しく見ていきます。