アドレス空間配置のランダム化

この記事には独自研究が含まれているおそれがあります。 問題箇所を検証し出典を追加して、記事の改善にご協力ください。議論はノートを参照してください。（2008年10月）

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "アドレス空間配置のランダム化" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2008年10月)

アドレス空間配置のランダム化（英語: address space layout randomization, ASLR）とは、重要なデータ領域 の位置（通常、プロセスのアドレス空間における実行ファイルの基底とライブラリ、ヒープ、およびスタックの位置が含まれる）を無作為に配置するコンピュータセキュリティの技術である。

アドレス空間のランダム化は、攻撃者が標的のアドレスを予測することをより困難にすることによって、ある種のセキュリティ攻撃を妨害する。たとえば、return-to-libc攻撃で実行を試みる攻撃者は実行されるコードの位置を特定しなければならず、スタック上に注入されたシェルコードの実行を試みる他の攻撃者はまずスタックを見つけなければならない。どちらの場合も、関連するメモリアドレスは攻撃者から隠されている。攻撃者はこれらの値を推測しなくてはならず推測が失敗すると通常アプリケーションはクラッシュするため、回復は不可能である。

アドレス空間配置のランダム化はランダムに置かれた領域を攻撃者が探し出すことを困難にすることを狙ったものである。探索空間が増大すれば、その分セキュリティも向上する。したがって、アドレス空間のランダム化は無作為なオフセット内に存在するエントロピーが大きくなるほど効果的である。エントロピーを大きくするにはランダム化が行われる仮想記憶領域空間の量を増やすか、ランダム化を行う時間間隔を短縮する。時間間隔は通常は可能な限り小さくなるよう実装されるので、ほとんどのシステムは仮想記憶領域の量を増やさねばならない。

攻撃者はランダム化に対抗するために、攻撃を加えようとする全ての領域の位置の推測に成功しなければならない。攻撃用のコードや役に立つデータを乗せるためのスタックやヒープのようなデータ領域については、コードならばNOPスライドの使用、データならばコピーの繰り返しによって、攻撃可能な状態を増やすことができる。領域がランダム化された結果それらの状態のどれか1つになれば攻撃は成功する。一方、基本ライブラリやメイン実行ファイルのようなコード領域はその位置を正確に知る必要がある。しばしばこれらの領域は混合される。たとえばスタックフレームはスタック上に注入され、ライブラリはそこを戻り先にされる。

まず、以下の変数を宣言する:

${\displaystyle E_{s}={\mbox{entropy bits of stack top}}\,}$

${\displaystyle E_{m}={\mbox{entropy bits of mmap() base}}\,}$

${\displaystyle E_{x}={\mbox{entropy bits of main executable base}}\,}$

${\displaystyle E_{h}={\mbox{entropy bits of heap base}}\,}$

${\displaystyle A_{s}={\mbox{attacked bits per attempt of stack entropy}}\,}$

${\displaystyle A_{m}={\mbox{attacked bits per attempt of mmap() base entropy}}\,}$

${\displaystyle A_{x}={\mbox{attacked bits per attempt of main executable entropy}}\,}$

${\displaystyle A_{h}={\mbox{attacked bits per attempt of heap base entropy}}\,}$

${\displaystyle \alpha ={\mbox{attempts made}}\,}$

${\displaystyle N=E_{s}-A_{s}+E_{m}-A_{m}+E_{x}-A_{x}+E_{h}-A_{h}\,}$

攻撃者が成功する確率を計算するために、試行回数 ${\displaystyle \alpha }$ はシグネチャベースのIPS、法的規制、その他の要因によって中断されることなく実行されると仮定する。ブルートフォースの場合、デーモンを再起動することはできない。さらにどれだけ多くのビットが関係し、どれだけ多くのビットが1回あたりの試行で攻撃され、どれだけ多くのビット攻撃しなければならないビットが残るかも算出しなければならない。

以下の式は${\displaystyle N}$ビットのエントロピーに対する${\displaystyle \alpha \,}$回の試行が与えられたとき、攻撃が成功する確率を表す。

${\displaystyle g\left(\alpha \,\right)={\mbox{isolated guessing; address space is re-randomized after each attempt}}\,}$

${\displaystyle g\left(\alpha \,\right)=1-{\left(1-{2^{-N}}\right)^{\alpha }\,}:0\leq \,\alpha \,}$

${\displaystyle b\left(\alpha \,\right)={\mbox{systematic brute forcing on copies of the program with the same address space}}}$

${\displaystyle b\left(\alpha \,\right)={\frac {\alpha \,}{2^{N}}}:0\leq \,\alpha \,\leq \,{2^{N}}}$

多くのシステムで、${\displaystyle 2^{N}}$は数千から数百万の範囲になりうる。現代の^[update] 64ビットシステム上では、これらの数値は少なくとも数百万に達する。アドレスのランダム化に16ビットを使用する2004年時点の32ビットシステムについて、Shachamと共同研究者は以下のように述べている。「…16ビットのアドレスランダム化はブルートフォース攻撃により数分で破れる」^[1] この研究者の主張は攻撃者が同じアプリケーションに対していかなる遅延もなく複数回攻撃できる能力に依存していることに注意されたい。grsecurityに含まれているような、ASLRの適切な実装は、このようなブルートフォース攻撃を不可能にするいくつかの手法を提供している。ひとつの方法は、ある一定の時間内に設定された回数以上クラッシュした実行ファイルの実行を妨げることである。

一部のシステムはライブラリロード順序のランダム化を実装する。これはライブラリがロードされる順序をランダム化する、ASLRの一形態である。これにより供給されるエントロピーはほとんどない。必要なライブラリ1つごとに供給されるエントロピーのビット数の見積りを以下に示す。これは可変のライブラリサイズを考慮に入れていないため、実際に得られるエントロピーはもう少し大きくなる。攻撃者は通常1つのライブラリしか必要としないことに注意されたい。複数ライブラリの場合の計算式はより複雑になるがこれも以下に示す。攻撃者が1つのライブラリしか使用しない場合は、複雑な式を${\displaystyle l=1}$として単純化したものであることに注意。

${\displaystyle l={\mbox{number of libraries loaded}}}$

${\displaystyle \beta \,={\mbox{number of libraries used by the attacker}}}$

${\displaystyle E_{m}=\log _{2}\left(l\right):\beta \,=1,l\geq \,1}$

${\displaystyle E_{m}=\sum _{i=l}^{l-\left(\beta \,-1\right)}\log _{2}\left(i\right):\beta \,\geq \,1,l\geq \,1}$

これらの値は${\displaystyle l}$が大きな値でも、低くなる傾向にある。もっとも重要な点は、攻撃者は通常C標準ライブラリしか使えず、そのためしばしば${\displaystyle \beta \,=1}$と仮定できるということである。しかし、興味深いことにライブラリの数が少なくともここで数ビットのエントロピーが得られる。このようにライブラリロード順序のランダム化を仮想メモリ領域アドレスのランダム化と組み合わせることにより、数ビットの追加エントロピーを得られる可能性がある。これらの追加ビットはライブラリのみに適用され、他のmmap()セグメントなどには適用されないことに注意。

攻撃者は単純な情報漏洩から、攻撃1回あたりの複数ビットエントロピー攻撃（heap sprayingによる攻撃など）まで、いくつかの方法を使ってランダム化されたアドレス空間に現れるエントロピーを削減できる。これに対抗する手段はほとんどない。

書式文字列攻撃を使用したメモリレイアウトに関する情報の漏洩がありうる。printf()のような書式文字列関数は可変長引数リストを使用して作業を行う。書式指定子は引数リストがどのように見えるかを記述する。引数が渡される通常の方法のために、各種書式指定子はスタックフレームの先頭近くに移動する。最終的に、戻り先のポインタとスタックフレームポインタの抽出が可能であり、脆弱なライブラリのアドレスと既知のスタックフレームのアドレスが現れる。これにより攻撃者に対する障害としてのライブラリとスタックのランダム化の効果はまったくなくなる。

スタックやヒープのエントロピーを減らすこともできる。スタックは通常16バイトの倍数境界に配置されなければならないので、ランダム化の間隔もそれより小さくはできない。さらにヒープはページ（通常4096バイト）境界に配置されなければならない。攻撃を試みるとき、重複した攻撃をこれらの境界に合わせることが可能である。NOPスライドをシェルコードの注入に使うことができ、system()への戻りを試みるときは文字列 '/bin/sh' を任意個数のスラッシュの '////////bin/sh' に置き換えることができる。削減されるビット数は間隔${\displaystyle n}$の攻撃に対して、ちょうど${\displaystyle log_{2}\left(n\right)}$である。

このような減少はスタックやヒープのデータ量のために制限される。たとえば、スタックは通常8MB^[2]に制限され、それよりも伸びて使われることは、めったにない。これにより削減が可能なのは最大19ビットであるが、より保守的な見積もりでは4-16KB^[2]のスタックの詰め物に対しておよそ 8-10ビットである。一方ヒープはメモリアロケータの振る舞いに制限される。glibcの場合、128KBを超える割り当てはmmap()を使って作られ、攻撃者のビット削減を5ビットに制限する。これはブルートフォースに対する制限要因でもある。行われる攻撃の回数を削減することはできるが、攻撃のサイズが十分大きくなると一部の環境での振る舞いは侵入検知システムと似たものになりうる。

PaXプロジェクトが最初に「ASLR」という造語を発明した。PaXはASLRの最初の設計と実装を 2001年7月に発行した。これは現在でも最も完全な実装であり、2002年10月からはカーネルスタックのランダム化も提供している。PaXは他の実装と比べて、各ランダム化されたレイアウトごとに最大のエントロピーを与える実装であり続けている^[3]。

いくつかの主流の、汎用目的のオペレーティングシステムがASLRを実装している。

OpenBSDはASLRをサポートした（そしてデフォルトで有効にした）、最初の主流のオペレーティングシステムの1つとなった^[4]。

Linuxは弱い^[5]形のASLRを、カーネルバージョン2.6.12からデフォルトで有効にした。PaXとExec ShieldのLinuxカーネルに対するパッチ集はより完全な実装を提供する。Adamantix、Alpine Linux、Hardened Gentoo、およびHardened Linux From Scratchを含む各種のLinuxディストリビューションはPaXのASLR実装をデフォルトで備えている。

Linux用のExec Shieldパッチは16バイトの間隔上で19ビットのスタックエントロピーを供給する。そして4096バイトの1ページ間隔上で8ビットのmmap()エントロピーを供給する。これは524288通りの位置がありうる8MBの広さの領域にスタック基底を置く。そして256通りの位置がありうる1MBの広さの領域にmmap()基底を置く。

位置独立実行ファイル (PIE) の機能はメイン実行ファイルバイナリのランダムな基底アドレスを2003年から実装する。これはメイン実行ファイルに対して、共有ライブラリで使われるものと同じアドレスのランダム性を提供する。PIEの機能はネットワークに直接向き合うデーモンにのみ使われている - PIE機能は同じ実行ファイルでprelinkの機能と同時に使うことができない。

prelinkツールは実行時ではなくprelink時にランダム化を実装する。なぜならば仕様によりprelink は、動的リンカが行わなければならなくなる前にライブラリの再配置を行うことで、プログラムを何度も走らせても再配置が1回しか行われないようにすることが目的だからである。結果として、真のアドレス空間ランダム化はprelinkの目的を打ち消してしまう。

マイクロソフトのWindows Vista（後述の通り2008年3月リリースのSP1から）、Windows Server 2008、Windows 7、およびWindows Server 2008 R2は、ASLRが有効となるよう特別にリンクされた実行ファイルとダイナミックリンクライブラリについてのみではあるが、デフォルトでASLRを有効にしている^[6]。これにはService Pack 1より前のWindows Vista上のInternet Explorer 7が含まれていなかった。ASLRとDEPは両方がアプリケーション互換性の目的で無効にされていた^[7]。Internet Explorer 8を含む、より新しいバージョンはこれらの保護を有効にした。すべての実行ファイルとライブラリで強制的にASLRを有効または無効にするレジストリ設定が存在する。レジストリキー "HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Memory Management\MoveImages" である^[8]。

ヒープ、スタック、プロセス環境ブロック、およびスレッド情報ブロックの位置もランダム化される。シマンテックのセキュリティホワイトペーパーは、32ビットのWindows VistaにおけるASLRは期待されるほど堅牢ではない可能性があると注意しており、マイクロソフトはその実装の弱点を認めている^[9]。

WehnTrust^[10]やOzone^[11]のようなホストベースの侵入検知システムも、ASLRをWindows XPとWindows Server 2003オペレーティングシステムに提供している。しかし、これらの実装の完全な詳細は公開されていない^[12]。

Solaris 11.1 よりサポートされた^[13]。

Appleは、Mac OS X v10.5（2007年10月リリース）で、一部のライブラリオフセットのランダム化を導入した^[14]。この実装は、ASLRが防ぐことを目的とした攻撃に対する完全な保護を提供しない^{[15][16][17][18]}。

Mac OS X Lion 10.7（2011年7月リリース）では、AppleはASLR実装をすべてのアプリケーションに拡大した。32ビットアプリケーションでも利用できるようになり（ヒープメモリ保護も同様）、64ビットと32ビットアプリケーションの攻撃に対する耐性が向上した^[19]。

OS X Mountain Lion 10.8（2012年7月リリース）以降では、システム起動時にカーネルだけでなく、kextやzoneを含むシステム全体がランダムに再配置される^[20]。

Appleは、iOS 4.3（2011年4月リリース）でASLRを導入した^[21]。

Android 4.0 Ice Cream Sandwichはシステムとサードパーティーのアプリケーションをメモリ管理の問題に起因する脆弱性攻撃から保護するためのASLRを提供する。また、4.1においては位置独立実行ファイル (PIE) への対応が追加された^[22]。

• バッファオーバーフロー
• スタックオーバーフロー
• スタックオーバーフロー保護
• NXビット
• 情報量（情報エントロピー）
• ヒープスプレー（英語版）

• PaXのASLRに関する文書（英語）
• PaXのExecShieldとW^Xに対する比較（英語）
• Windows Vista beta 2のASLR（英語）
• PaXのASLR保護を迂回する方法（英語）
• アプリケーション（もしくはライブラリ）のASLRとDEPサポートのテスト（英語）