Polyinstantiationの誘惑(1) - KaiGaiの俺メモ

ここ最近、SE-PostgreSQLにどうやってPolyinstantiationの機能を実装しようかと調べ物をしている。
参考にしているのは、Googleで引っ掛けてきた NCSC Technical Report - 005 というヤツ。まだ読んでる途中だけど。
NCSC TECHNICAL REPORT - 005 Vol 1/5 Lib No.S-243,039
NCSC TECHNICAL REPORT - 005 Vol 2/5 Lib No.S-243,039
NCSC TECHNICAL REPORT - 005 Vol 3/5 Lib No.S-243,039
NCSC TECHNICAL REPORT - 005 Vol 4/5 Lib No.S-243,039
NCSC TECHNICAL REPORT - 005 Vol 5/5 Lib No.S-243,039

Polyinstantiation と言うのは Multi-Level Database の中核機能で、その意図は繰り返し攻撃によって本来は読み出せないはずの情報を推測できてしまうという問題への対処。
例えば、以下のようなテーブルを考える。主キーは id とする。

|   security   | id |  name  | price |
+--------------+----+--------+-------+
| Unclassified |  1 | 'water'|  110  |
| Unclassified |  2 | 'coke' |  120  |
| Secret       |  3 | 'beer' |  200  |
| Unclassified |  4 | 'juice'|  150  |
+--------------+----+--------+-------+

この時、行レベルのアクセス制御によって、Classifiedレベルの人は id=3 の Secret のタプルが読み出せない。しかし、主キーは重複する値を許さないと言う制約があるために、手当たり次第に insert を試みることによって id=3 のタプルを挿入できないことに気がつく。そのため、これが隠れチャネルとして作用するということになる。

Polyinstantiation テーブルでは、主キーの定義が一部変更され、『同一の機密レベルで重複する値を許さない』となる。つまり、機密レベルが異なっていれば、主キーが同一の値を持てるということになる。
例えば以下のように、id=2のタプルが複数存在できる。

|   security   | id |  name  | price |
+--------------+----+--------+-------+
| Unclassified |  1 | 'water'|  110  |
| Unclassified |  2 | 'coke' |  120  |
| Secret       |  2 | 'pepsi'|  120  |
| Secret       |  3 | 'beer' |  200  |
| Unclassified |  4 | 'juice'|  150  |
+--------------+----+--------+-------+

これを Secret レベルのユーザが参照すると以下のような結果を得ることができる。

|   security   | id |  name  | price |
+--------------+----+--------+-------+
| Unclassified |  1 | 'water'|  110  |
| Secret       |  2 | 'pepsi'|  120  |
| Secret       |  3 | 'beer' |  200  |
| Unclassified |  4 | 'juice'|  150  |
+--------------+----+--------+-------+

一方、Unclassidiedレベルのユーザが参照すると、以下のような結果となる。Secretタプルがフィルタリングされ、以下の結果を得る。

|   security   | id |  name  | price |
+--------------+----+--------+-------+
| Unclassified |  1 | 'water'|  110  |
| Unclassified |  2 | 'coke' |  120  |
| Unclassified |  4 | 'juice'|  150  |
+--------------+----+--------+-------+

ここでのポイントは、同じid=2という主キーを持つ複数のタプルの中で、ユーザが参照可能な最も機密レベルの高いものが返却されるという点。単なるフィルタリングであれば、Secretユーザには'coke'と'pepsi'の両方が見えるということになる。

さらに混乱に拍車をかけるのがデータを更新する場合。
ここでの制約は、機密レベルの高いユーザの書き込みを機密レベルの低いユーザが探知できてはいけないというもの。

例えば、以下のテーブルでid=4の'juice'を'tea'に更新する場合、

|   security   | id |  name  | price |
+--------------+----+--------+-------+
| Unclassified |  1 | 'water'|  110  |
| Unclassified |  2 | 'coke' |  120  |
| Secret       |  3 | 'beer' |  200  |
| Unclassified |  4 | 'juice'|  150  |
+--------------+----+--------+-------+

次のSQL文を用いて更新を行う。
UPDATE drink SET name = 'tea', price = 130 WHERE id = 4;
しかし、Secretユーザがこの操作を行った場合、更新後のPolyinstantiationテーブルは以下のようになっており、更新操作のはずが挿入操作になっている。
（ちなみに、MLSポリシーでは書き込み操作の際に機密レベルが等価である事を求めるので、この更新操作は成功しない）

|   security   | id |  name  | price |
+--------------+----+--------+-------+
| Unclassified |  1 | 'water'|  110  |
| Unclassified |  2 | 'coke' |  120  |
| Secret       |  3 | 'beer' |  200  |
| Unclassified |  4 | 'juice'|  150  |
| Secret       |  4 | 'tea'  |  130  |
+--------------+----+--------+-------+

これによって、機密レベルの高い人の操作が、機密レベルの低い人に知られることは無くなる。

というのが、理論モデルの話であるわけだ。これを実装レベルで検討すると、色々と摩訶不思議な現象にぶち当たることになる…。
(続く)