連想配列への攻撃
マップの実装には大きく分けて、ハッシュテーブルと平衡２分木の２つがあるらしい。ハッシュテーブルは java.util.Hashmap や Hashtable、２分木は、java.util.TreeMap や C++ の std::map などがある。２分木の方は大小比較という相対評価だが、ハッシュテーブルの方は、ハッシュ値による絶対評価である。
私はこの、ハッシュ値やハッシュテーブルをあまり信用していない。たかだか sizeof(int/uint) * 8 bit の情報しか返せないからだ。例えば、
struct S {
uint x;
}という構造体のtoHash()の実装は単純に
uint toHash() {
return x;
}としておきけば、a, b が S のとき、
a == b ならば、a.toHash() == b.toHash()
だし、
a != b ならば、a.toHash() != b.toHash()
である。
おまけに
a < b ならば、a.toHash() < b.toHash()
だが、これはハッシュコードの必要条件ではない。値の大小比較ではなく、値の識別に使うものだから。
だが、これが
struct S {
uint x;
uint y;
}となると、各メンバがどんな値をとっても上記の値識別条件を満たすハッシュコードを満たす、toHash() の実装は不可能となる。S の取り得る値は、(uint.max - uint.min + 1) ^ 2 通りあるが、ハッシュ値は (uint.max - uint.min + 1) の組み合わせしかないからだ。
実際には、uint.max に近い値を使うことはまれなため、ハッシュ値のバッティングがたまたま起こっていないだけだ。
というわけで、私はあまりハッシュ値やハッシュテーブルを信用をしていないが、我等がD言語の連想配列は２分木を使っているだろうか？
(見慣れないテンプレートが多いですが、D言語Wikiのレシピ集を参照してください。struct の static opCall() と配列リテラルは愛用してます。Mapの初期化は私です）
struct S {
int x;
int y;
static S opCall(int x, int y) {
S s;
s.x = x;
s.y = y;
return s;
}
char[] toString() {
return "{" ~ .toString(x) ~ "," ~ .toString(y) ~ "}";
}
int opEquals(S* o) {
dout.writeLine(_TEXT("お前は俺か？") ~
this.toString() ~ "?=" ~ o.toString());
return x == o.x && y == o.y;
}
int opCmp(S* o) {
dout.writeLine(_TEXT("値踏みしたる") ~
this.toString() ~ "?<" ~ o.toString());
return (x == o.x) ? y - o.y : x - o.x;
}
uint toHash() {
dout.writeLine(_TEXT("切り刻んだる") ~ toString());
uint hash = x;
dout.writeLine(_TEXT("少し切り刻んだ値 = ") ~ .toString(hash));
hash = hash * 9 + y;
dout.writeLine(_TEXT("全部切り刻んだ値 = ") ~ .toString(hash));
return hash;
}
}
void main() {
{
mixin Map!(S, int);
int[S] map = Map(
Entry(S(1, 2), 1),
Entry(S(10, 20), 2),
Entry(S(100, 200), 3),
Entry(S(0, 9), 4),
Entry(S(-1, 18), 5)
);
ToString!(typeof(map))(map).writefln();
writefln(map[S(1, 2)]);
writefln(map[S(10, 20)]);
writefln(map[S(100, 200)]);
writefln(map[S(0, 9)]);
writefln(map[S(-1, 18)]);
}
}内部メンバの型が signed なので、値がバッティングする toHash() を書くのは容易である。
で、結果。
切り刻んだる{1,2}
少し切り刻んだ値 = 1
全部切り刻んだ値 = 11
切り刻んだる{10,20}
少し切り刻んだ値 = 10
全部切り刻んだ値 = 110
切り刻んだる{100,200}
少し切り刻んだ値 = 100
全部切り刻んだ値 = 1100
切り刻んだる{0,9}
少し切り刻んだ値 = 0
全部切り刻んだ値 = 9
切り刻んだる{-1,18}
少し切り刻んだ値 = 4294967295
全部切り刻んだ値 = 9
値踏みしたる{-1,18}?<{0,9}
[({0,9}:4),({-1,18}:5),({1,2}:1),({10,20}:2),({100,200}:3)]
少し切り刻んだ値 = 1
全部切り刻んだ値 = 11
値踏みしたる{1,2}?<{1,2}
1
切り刻んだる{10,20}
少し切り刻んだ値 = 10
全部切り刻んだ値 = 110
値踏みしたる{10,20}?<{10,20}
2
切り刻んだる{100,200}
少し切り刻んだ値 = 100
全部切り刻んだ値 = 1100
値踏みしたる{100,200}?<{100,200}
3
切り刻んだる{0,9}
少し切り刻んだ値 = 0
全部切り刻んだ値 = 9
値踏みしたる{0,9}?<{0,9}
4
切り刻んだる{-1,18}
少し切り刻んだ値 = 4294967295
全部切り刻んだ値 = 9
値踏みしたる{-1,18}?<{0,9}
値踏みしたる{-1,18}?<{-1,18}
5う〜ん、連想配列に値を入れた時点で、toHash() が呼ばれてますね。{-1,18}と{0,9}の間で、ハッシュコードがバッティングしているけど、そんときゃちゃんと opCmpが呼ばれている。
というわけで、D言語の連想配列は、基本的にハッシュテーブルだが、ハッシュ値がぶつかったときは、大小比較をしているので、ハッシュコードが一意でなくても大丈夫ってこってすね。
でも、連想配列をキー参照するときに、toHashが呼ばれるのはいいとして、いちいちopCmpまで呼んじゃってるね。なんでだろ。
と、ここまでが前段。
ここからが本格的な攻撃。
基本型や構造体は値渡しだが、class のオブジェクトは参照渡しである。で、連想配列のkey や value として、class のオブジェクトを渡すと連想配列の中身を「外から」変更できる。これは連想配列だけではなく、配列やクラスでも同じだし、参照渡しが基本の Java や C# でも多分同じである。つまり「カプセル化は破壊されている」のだ。Java なんかカプセル化されていないクラスが当たり前である。だって Java プログラマーで
・コンストラクターの引数がクラスの場合、コピーコンストラクターで新しいインスタンスを作ってそれを内部に持つ
・getter で内部のデータを返すときは、clone()か、コピーコンストラクターで新しいインスタンスを作ってそれを返す
といった「防御的コピー」を律儀に行っている人見たことないもん。
いや私もだけどさ。
ちなみにコンストラクターの引数をコピーするのに clone() を使ってしまうと何のインスタンスが返ってくるか知れたもんじゃないので、自分が欲しい型のコピーコンストラクターを使うのがセオリーだそうです（Effective Java より）
さてカプセル化が破壊された連想配列に対する攻撃を行ってみよう。
class C {
int x;
int y;
this(int x, int y) {
this.x = x;
this.y = y;
}
override { // Object
char[] toString() {
return "{" ~ .toString(x) ~ "," ~ .toString(y) ~ "}";
}
int opEquals(Object o) {
if (rhs; cast(C)o) {
dout.writeLine(_TEXT("お前は俺か？") ~
this.toString() ~ "?=" ~ rhs.toString());
return x == rhs.x && y == rhs.y;
}
return 0;
}
int opCmp(Object o) {
if (rhs; cast(C)o) {
dout.writeLine(_TEXT("値踏みしたる") ~
this.toString() ~ "?<" ~ rhs.toString());
return (x == rhs.x) ? y - rhs.y : x - rhs.x;
}
throw new Exception("Bad Cast");
}
uint toHash() {
dout.writeLine(_TEXT("切り刻んだる") ~ toString());
uint hash = x;
dout.writeLine(_TEXT("少し切り刻んだ値 = ") ~ .toString(hash));
hash = hash * 9 + y;
dout.writeLine(_TEXT("全部切り刻んだ値 = ") ~ .toString(hash));
return hash;
}
}
}基本的に構造体と同じ。opEquals と opCmp の引数が違うのと、static opCall がコンストラクターになってるだけである。
opCmpの内容は自信がない。opEquals だと右辺の型が違ったとき「等しくない」という結果を返せるが、opCmp だと、大なりとも小なりとも等しいとも言うわけにいかず、例外を投げるしかないと思うが、もっと適切な例外はないのかな？
で、この人を
{
C[] arr = Array!(C)(
new C(1, 2),
new C(10, 20),
new C(100, 200),
new C(0, 9),
new C(-1, 18)
);
mixin Map!(C, int);
int[C] map = Map(
Entry(arr[0], 1),
Entry(arr[1], 2),
Entry(arr[2], 3),
Entry(arr[3], 4),
Entry(arr[4], 5)
);
ToString!(typeof(map))(map).writefln();
}こうしてあげる訳ですが、その結果は
切り刻んだる{1,2}
少し切り刻んだ値 = 1
全部切り刻んだ値 = 11
切り刻んだる{10,20}
少し切り刻んだ値 = 10
全部切り刻んだ値 = 110
切り刻んだる{100,200}
少し切り刻んだ値 = 100
全部切り刻んだ値 = 1100
切り刻んだる{0,9}
少し切り刻んだ値 = 0
全部切り刻んだ値 = 9
切り刻んだる{-1,18}
少し切り刻んだ値 = 4294967295
全部切り刻んだ値 = 9
値踏みしたる{-1,18}?<{0,9}
[({0,9}:4),({-1,18}:5),({1,2}:1),({10,20}:2),({100,200}:3)]こうなりました。ここまでは構造体と同じですな。ここまではよい。
で、いよいよ攻撃
arr[0].x = 1000;
arr[0].y = 10000;
ToString!(typeof(map))(map).writefln();
...
[({0,9}:4),({-1,18}:5),({1000,10000}:1),({10,20}:2),({100,200}:3)]あ〜あ、変わってら。{1,2}→{1000,10000}にしたわけだけど、順番はもとのまま。
toHash も opCmp もコールされていない。
待てよ？ 連想配列には rehash てプロパティがあるじゃないか。呼んでみよう。
ToString!(typeof(map.rehash))(map.rehash).writefln();
ToString!(typeof(map))(map).writefln();
...
値踏みしたる{-1,18}?<{0,9}
[({0,9}:4),({-1,18}:5),({1000,10000}:1),({10,20}:2),({100,200}:3)]
[({0,9}:4),({-1,18}:5),({1000,10000}:1),({10,20}:2),({100,200}:3)]１回だけ opCmp が呼ばれているけど、toHash は未コール。順番ももとのまま。
ちゃんとアクセスできるのかしら？
writefln(map[arr[0]]);
...
切り刻んだる{1000,10000}
少し切り刻んだ値 = 1000
全部切り刻んだ値 = 19000
Error: ArrayBoundsError hashmap(120)げ、だめだ。
同じ値の key を new してみよう。
writefln(map[new C(1000, 10000)]);
...
切り刻んだる{1000,10000}
少し切り刻んだ値 = 1000
全部切り刻んだ値 = 19000
Error: ArrayBoundsError hashmap(120)やっぱりだめだ。
待てよ？ key をいぢったときも、rehash したときも、toHash は呼ばれてないんだっけな。ということは、変更前のハッシュ値を持った key でアクセスすると？
え〜と、変更前の値は{1,2}か。
writefln(map[new C(1, 2)]);
...
切り刻んだる{1,2}
少し切り刻んだ値 = 1
全部切り刻んだ値 = 11
値踏みしたる{1,2}?<{1000,10000}
Error: ArrayBoundsError hashmap(120)お〜い、どーやってもアクセスできなくなったぞ。key によるアクセスができない連想配列って一体ナニよ。ただのシーケンシャルコンテナじゃねーか。
そーいや、連想配列には keys プロパティがあるけど、あれを使っても攻撃できるかな？
map.keys[1].x = 10000;
map.keys[1].y = 100000;
ToString!(typeof(map))(map).writefln();
writefln(arr[4]);
...
[({0,9}:4),({10000,100000}:5),({1000,10000}:1),({10,20}:2),({100,200}:3)]
{10000,100000}わははは、しっかり変わってら。しかも連想配列に入れる前の値までしっかり変わってる。
2/22 に連想配列の key や value の値をいぢくっても元の連想配列に変化なしって書いたばっかしなのにねぇ。
でも今回は私のせいじゃないぞ。参照恐るべき、だ。私は別にあっちを指してる参照をこっちを指すように書き換えたりはしてないぞ。key が指す参照「先」の値を変えただけだ。
しかし、現実問題として key でアクセスできなくなるのは困るなぁ。
結果は同じなので載せないが、
・変更後の値を new
・変更後の元の値(arr[4])
・変更前の値を new
いずれの key でもArrayBoundsErrorが発生しました。
Observerパターンよろしく key の値が（外部から）更新されたときに、連想配列がそれを検知して rehash、再配置を行うというのは無理でしょう。しかし明示的に rehash を呼んでも、toHash が呼ばれないというのは納得いかん。欠陥かもしれん。英語がパープーなので Mr. Bright に進言、なんてことはしませんが。
まぁ、よい子はこんなことするなということなんでしょうが、教訓としては
・連想配列の key は基本型、構造体などの値オブジェクトにしましょう
・もし class 型のオブジェクトを key に使うときは、setter や外部との共有参照を持たない不変オブジェクトにしましょう。
・もし万一可変オブジェクトを key に使った場合、連想配列の中身を変えるときは、remove 後、新たな key で挿入しましょう。決して key と参照を共有するオブジェトの値を変えてはいけません。
ってことですね。
長いことお疲れ様でした。
