技術者ブログ

はじめに

SQLインジェクションがあるにもかかわらず、レスポンスボディの内容やステータスコードに変化がない、いわゆる「完全なブラインド」の状態でも、sleep系の関数等を使うことによってデータが盗まれる可能性があります。この攻撃はTime-Based SQL Injectionと呼ばれており、sleep系の関数を使うことから「実際に攻撃者にとって有用な情報を盗み出すには時間がかかる」というのが定説のようです。

しかし実はTime-Based SQL Injectionを高速に実行し、いわゆる「普通の」ブラインドな状態(DBのエラーメッセージは読めないが、ステータスコードの変化等でSQLがエラーになったかどうかを判別できる状態)と同じ速さでデータを取得することが可能です。本エントリではこの手法(眠らないTime-Based SQL Injection)についての説明を行います。

はじめに

JavaのHashMapには特定のbinに要素が集中すること(例えばHashDoS攻撃)によるパフォーマンスの劣化を避ける工夫がされています。このメカニズムはJava7とJava8で大きく変わりました。今回はこの点について詳しく見ていきます。

Java8でHashMapがどう変わったか?

以前こちらのエントリで書いたように、Java7ではHashMapにおいて激しいハッシュの衝突が起こると、ハッシュ計算のロジックそのものが変更されるという機能が実装されていました。これによってオブジェクトに対するハッシュ値自体が変わってくるため衝突は完全に回避され、その後の性能はHashMap本来の高速なものとして保たれます。この機能はデフォルトでは無効で、jdk.map.althashing.thresholdオプションで有効にする形となっていました。

Java8では上記機能は完全に廃止されました。代わりに、HashMap内部のbinにおいて格納される要素の数が増えてきたら、bin内での検索をLinked ListではなくBalanced Treeで行うよう切り替わるようになりました(参照:Oracleのドキュメント/OPENJDKの該当JEP)。この切り替えは自動で行われ、デフォルトで有効になっています。

閾値は8です。つまりあるbinにおいてLinkedListの長さが8になるとリストから木への変更が行われます。ソースコード中ではTREEIFY_THRESHOLDとして定義されています。

Java7では明示的にオプションを指定しないとHashDoS攻撃に対して脆弱でしたが、Java8からはデフォルトでHashDoS攻撃対策がされていると言ってよいでしょう。

閾値の8はどんな値なのか?

閾値である8というのはどの程度のレベルの値なのでしょうか。つまり、リストから木への変更は結構頻繁に発生するものなのか、あるいは殆ど発生しないものなのか、どちらに近いのでしょうか。

HashMapでは1つのbinに多くの要素が格納されてしまう状態を避けるため、自動的に内部のテーブル(binの集合)が要素の数に合わせてどんどん大きくなっていきます。しかしある程度は「1つのbinに複数の要素が格納される状態」が発生します。これは自然な状態です。

閾値の8というのは「ある１つのbinに割り当てられる要素が8個もある状態」を意味します。この規模の要素の混雑は、HashDoS攻撃のようなケースを除いて、自然に発生する可能性はあるのでしょうか。

これを確かめるため、ランダムに生成した長さ80のStringインスタンスをkeyとし、10万要素ほどputしたHashMapで確認してみました。テーブル中の全binについて要素の最大数を調べてみたところ、数回のテストにおいて、ほとんどの場合、5〜6という値になりました。つまり、8は「普通のアプリケーションであれば、ごく稀には発生するかもしれない...」という絶妙な閾値になっていることが確認できました。

ちなみに要素が1つも入っていないbinの割合は全binのうち6〜7割で、要素が1つ以上入っているbinにおける要素の数の平均値は約1.2でした。

この辺についてはソースコードの上の方にコメントで(ポアソン分布に従う等）説明が書いてあるので、興味がある人はぜひ読んでみてください。

はじめに

Scutumの開発ではJavaを使っていますが、以前HashMapの使い方を致命的に間違えてしまい、ひどいことになった経験が2度あります。今回はその内容について簡単に紹介します。

1. 消える要素

Mapに入れたはずの要素がその後忽然と姿を消した事象です。要点のみの再現コードは以下になります。

Map db = new HashMap();
Map key = new HashMap();

key.put( "aaa", "bbb" );
db.put( key, "ccc" );
System.out.println( db.get( key ) ); //ccc

key.put( "ddd", "eee" );
System.out.println( db.get( key ) ); //null

putした後、一度もremove()をコールしていないので、db.get(key)にはcccが返ってきてほしい心境だったのですが、最後の行ではnullが返ってきます(実行環境によっては、もしかしたらcccが返ってくるかもしれません)。

原因はputの後にkeyを変更してしまい、それによってkeyのハッシュ値が変わってしまっていることです。

キーとして使っているオブジェクトのハッシュ値が変わってしまうと、HashMap内部のテーブルにおいてハッシュ値の変更前とは別のbinに問い合わせを行う確率が高くなります。この場合には当然、要素が見つからないことになります。

ということで、「ハッシュ値が変わっていく可能性のあるオブジェクトはHashMapのキーに使ってはいけないし、同じくHashSetに入れてはいけない」ということです。コンピュータ・サイエンスでハッシュ検索を学んでいる人には「そりゃそうなるよね...」と思われる事例です。

状態が変化していくようなオブジェクトはハッシュ値が変わっていく可能性が高いので、そのようなオブジェクトは要注意です。