KLab
KLablog デリシャスなワクワクでいっぱい

Technology 技術への挑戦

Technologyブログ一覧

map データ構造の列挙順序と脆弱性について調べてみた

こんにちは、最近シェーダーをよく書いているバックエンドアークテクチャGの小林です。

先日業務内で map データ構造の罠にはまってしまった事例が観測されたため、改めて振り返ってみることにしました。

発端

Go で、以下のようなコードで map の等値性を判定している箇所がありました。

package main

import (
    "fmt"
)

func main() {
    m1 := map[string]string{"foo": "hoge", "bar": "fuga", "baz": "piyo"}
    m2 := map[string]string{"foo": "hoge", "bar": "fuga", "baz": "piyo"}
    
    for i := 0; i < 10; i++ {
        fmt.Printf("%t\n", isEquivalentMap(m1, m2))
    }
}

func isEquivalentMap(lhs, rhs map[string]string) bool {
    return mapToString(lhs) == mapToString(rhs)
}

func mapToString(m map[string]string) string {
    buf := make([]byte, 0, 8192)
    for k, v := range m {
        elm := fmt.Sprintf("(%s,%s)", k, v)
        buf = append(buf, elm...)
    }
    return string(buf)
}

しかし、結果としてこのコードは結果として想定どおりに動作せず、不具合の原因になってしまいました。 この原因についてより深く知るために map の内部構造や実装について調査しましたので共有します。

map におけるデータの挿入・検索方法

一般的に map と呼ばれるデータ構造1においてキーに対応する値を発見するアルゴリズムはいくつか存在しますが、 大きく分けてハッシュ関数を使うものと木構造を使うものに分けられます。

ハッシュ関数を使う方法

ハッシュ関数を用いてキーに対応するハッシュ値を計算し、それを配列などに格納します。 平均計算量(厳密にはならし計算量)は挿入・削除・探索ともに O(1) です。

ハッシュ値を計算した際、違うキー同士でハッシュ値が衝突してしまうことがあります。 その際の処理としてはさらに次の 2 つに大別されます。

  • closed hash
    • 後続のハッシュ値用のエントリの場所に格納する
    • ハッシュ値が #42 で衝突した場合、 array[42], array[43], array[44]... で最初に空いている部分に登録する
    • #43 などは array[44] 以降で登録される
  • open hash
    • ハッシュ値用のエントリがさらにリストになっている
    • ハッシュ値が #42 で衝突した場合、 array[42][0], array[42][1], array[42][2]... で最初に空いている部分に登録する
    • いわゆる jagged array のような形態をとる

SwissTables など、現代のプロセッサに合わせてより最適化された アルゴリズムもありますが、ここで重要なのは 「ハッシュ値が衝突したキーの間の探索はあくまで線形探索」 ということです。

多くのスクリプト言語の map や、明示的に順序が保証されていない場合の map はこのタイプです (C++ の std::unordered_map なんかもそう)。

木構造を使う方法

キーの順序によって決定される木構造を使って管理する方法です。具体的には赤黒木や B 木のようなバランス木が使われることが多いです。 平均計算量は挿入・削除・探索ともに O(log(n)) ですが、最悪計算量も同じく O(log(n)) です。 また、衝突のようなことは原理的に起きないほか、この方法だと内容を列挙した際に常にキーの順序で取り出すことができます。

.NET ならば SortedDictionary 、C++ では std::map 、Rust では BTreeMap などが該当します。

ハッシュ関数方式の脆弱性

さて、ハッシュ関数を使う方法のところで「『平均計算量は』挿入・削除・探索ともに O(1)」と説明しました。 逆に、最悪計算量は O(n) となってしまうのがこの方法の欠点でもあります。

では、全てハッシュ値が衝突するようなキーで構成された map を作ったとしたら？

その時、ハッシュ関数は一切意味を為さなくなります。常に配列を線形探索してキーで比較するのと同じ状態になってしまうのです。 これを巨大な map で実行すればするほど、どんどんパフォーマンスは悪化します。

特に POST パラメーター等から map を構築する際は、構築が O(n^2) のオーダーとなってしまい、探索も列挙も全て線形になります。 このような攻撃を HashDoS 攻撃といいます。2011 年ごろにこの脆弱性が発表され、多くの言語が影響を受けていました。 類似の脆弱性自体は 1990 年 代から知られていたようで、 Perl や Ruby ではすでにいくらかの修正が施されていましたが、 本格的に対策がとられはじめたのは上記発表があってからのようです。

対策方法としては、「ハッシュ値が外部から予測できないハッシュ関数を使う」というものが主流です。 入力となる文字列と別に乱数の鍵を使ってハッシュ値を計算することで、その乱数を知らない攻撃者にはハッシュ値が衝突する複数の入力を 用意することができなくなります。

このようなハッシュ関数として代表的なものに SipHash があります。 これは暗号学的に安全かつ短いメッセージ(e.g. キーにする文字列)に対しても高速という特長があり、 SHA などを使うよりも 効率よく、かつ安全にハッシュ値を生成することができるものです。現在では様々な言語やアプリケーションでハッシュ値の生成に 使われているようです。

列挙順序の保証

ところで、 map のキーや値、あるいはそのペアを列挙したときの順序はどうなるのでしょうか？ 答えは 「実装による」 です。

例えば Rust の HashMap では、以下のようなコードを実行すると生成するごとに同じキーでも違う順序で列挙されることがわかります。

use std::collections::HashMap;

fn main() {
    for i in 1..=10 {
        println!("Iteration #{}", i);
        
        let mut hashmap: HashMap<i32, i32> = HashMap::new();
        for i in 0..10 {
            hashmap.insert(i, 10 - i);
        }
        for pair in hashmap {
            print!("{:?} ", pair);
        }

        println!();
    }
}

また、 Go では同じ map に対しても列挙ごとに違う順序になります。

package main

import (
    "fmt"
)

func main() {
    m := map[string]string{
        "foo": "hoge",
        "bar": "fuga",
        "baz": "piyo",
        "a": "あ",
        "b": "い",
        "c": "う",
        "one": "eins",
        "two": "zwei",
        "three": "drei",
    }

    for i := 0; i < 10; i++ {
        for k, v := range m {
            fmt.Printf("(%s, %s) ", k, v)
        }
        fmt.Printf("\n")
    }
}

冒頭のコードがうまく動かない原因がわかりましたね。毎回違う順序で列挙されていたので、構成される文字列も毎回違うものになってしまっていたのです。 Go で map の内容が一致しているかを正しく検査する方法として、 reflect.DeepEqual を使う方法や、 1.12 以降 map の print 順序がソートされることを利用して `fmt.Sprintf` で文字列化して比較する方法などがあります。 もちろん、手動で全てのキーをソートしてからキー順に比較することもできます。

一方で、ハッシュ関数を使わない実装ではキーによる一意な順序を返すものが多いです。 また、 SipHash などによる内部的なハッシュ値とは関係なく、キーが挿入された順で列挙する実装もあります。 スクリプト言語の言語構造の map に多い傾向で、例えば Python では以下のコードは毎回同じ結果を返します。

d =  {
    'foo': 42,
    'bar': 'hoge',
    'baz': 'https://example.com',
}

# 常に foo, bar, baz の順で表示される
for k, v in d.items():
    print(k, v)

このように、言語や実装によって map の列挙順序は異なったものとなっています。 言語仕様などで明確に順序が保証されている場面以外では、順序に依存したコードを書かないようにしましょう。

まとめ

  • map にはハッシュ関数を使うものと木構造を使うものがある。
    • ハッシュ関数を使うものは、平均的には定数時間で挿入・削除・検索ができる。
    • 木構造を使うものは、各操作が対数時間のことが多い。
  • map の列挙順序は常に同じとは限らない。
    • 様々な理由でランダム性が付与されていることがある。
    • 言語やライブラリによっては挿入した順序が保持されるものもある。

基本的なデータ構造と侮るなかれ、意外なところで罠を踏まないように気を付けていきたいですね。

この記事を書くにあたって、アドバイスをくださった皆さんにこの場を借りてお礼申し上げます。

付録: 言語・実装ごとの違い

主要な言語の標準ライブラリ・言語構造の map について、どのような特性のものがあるのかをまとめました。 以下では map についてのみ記述しますが、特筆のない限りは対応する set 構造についても同じものとなっています。

参考

  1. 言語によって map・dictionary・hash・table など様々な呼称がありますが、この記事では map に統一します。↩︎

このブログについて

KLabのゲーム開発・運用で培われた技術や挑戦とそのノウハウを発信します。

記事検索

おすすめ

合わせて読みたい

このブログについて

KLabのゲーム開発・運用で培われた技術や挑戦とそのノウハウを発信します。

記事検索