PaX

PaX は、メモリに関する最小特権保護を実装したLinuxカーネル向けコンピュータセキュリティパッチである。最小特権の手法により、プログラムは正しい動作以外は何もできなくなる。PaX は2000年にリリースされた。
PaX はデータ用メモリページを実行不可とし、コード用メモリページを書き込み不可にすると共に無作為な配置を行う。これによりセキュリティを危険にさらす様々な動作が不可能になる（バッファオーバーランの一種など）。データページの実行不可設定により、データをコードとして実行できなくなる。コードページの書き込み不可設定により、不正なライブラリ実行が難しくなる。ただし、変数やポインタの書き換えは防げない。
PaX は The PaX Team が保守しているが、個々の開発者は匿名である。

意義

コンピュータのセキュリティ問題の大半は、実行時に何かを書き換えられるような抜け穴（バグであることが多い）がプログラムにあることが原因である。Ubuntuの初期の44通の Security Notice を分類すると、41%はバッファオーバーランを原因とする脆弱性、11.4%は整数オーバフロー、15.9%は不正データの処理上の問題であった。これらのバグを悪用すると、外部からコードを注入して実行させたり、既存コードを不正な順序で実行させることができる。なお、この分析は非常に簡単なものであって、詳細に脆弱性を分析すれば結果は変わってくるだろう。
ワームやコンピュータウイルスなどの攻撃の多くは、メモリの内容を書き換えてマルウェアコードを実行できるようにすることで行われる。あるいは、データを実行するよう誘導するなどの手法がある。そのようなマルウェアの実行をブロックできれば、そのような侵入によって損害を被る可能性は激減する。Sasserのようなワームもそれによって対処可能である。
PaX は、そのような様々な攻撃を防ぐため、非常に汎用的な方法で防御するよう設計された。メモリのアクセス権（リード、ライト、実行の組合せ）を制御することで不正コードの実行を防ぎ、同時に正当なコードの実行には影響を与えないよう設計されている。若干のオーバーヘッドはあるが、PaX はDoS攻撃や外部からのコード注入制御の可能性を減らし、攻撃者にスーパーユーザー特権を与えるのを防ぎ、ハードディスク上の重要な情報へのアクセスを防ぎ、単に影響を受けたプログラムやプロセスがクラッシュするだけで済む。
DoS攻撃は、実行されるだけで迷惑であり、リソースや時間の浪費となる（企業のウェブサイトが攻撃された場合、ビジネス機会が失われる）。しかし、PaX があればデータを書き換えられたり、情報を外部にコピーされたりすることがなくなる。ただし環境によっては DoS 攻撃の類は攻撃されること自体が許容されない。サービス水準合意などの契約条件では、侵入者によるサービス低下が単なるコスト問題以上の契約違反として扱われる。それでも多くの場合、セキュリティを強化して重要な情報を保護することには意味がある。
多くのバグはメモリ破壊の原因となる。そのようなバグを利用して、プログラムが意図していない動作をさせることが可能となる。PaX はそのようなバグの検出や修正が可能なわけではなく、そのようなバグを利用した悪意ある攻撃を防ぐことにある。そのようなバグの一部は深刻度が減じられ、不正な動作をする代わりにプログラムを終了させる。
PaX はバッファオーバーフローを直接防ぐことはできないが、それを利用して不正なアクセスを行おうとするのを効果的に防ぐ。Stack Smashing Protector や StackGuard はバッファオーバフローそのものを検出し、そのような動作をしようとしたプログラムを終了させる。このような手法を Stack Smashing Protection と呼び、実際にオーバフロー状態となる前に防ぐ。一方 PaX はより汎用的な手法であり、オーバフローが発生してから実際のダメージが発生するのを防ぐ。どちらの手法でも結果的には同じ効果が得られるが、完全に重複する手法というわけではない。従って、両方の手法を同時に使うことで、システムをより安全にすることが（原理的には）可能である。一部のLinuxディストリビューションでは、PaX と Stack Smashing Protection の両方を採用している。
2004年中ごろ、PaXはLinuxカーネルのメインのソースツリーには含まれていなかった。これは、PaXチームがPaXを不完全であると考えていたためである。x86を含む多くのCPUアーキテクチャでは完全に機能しているが、いくつかのアーキテクチャでは部分的にしか実装されていないか、全く実装されていない。PaXが実装されているアーキテクチャとしては、IA-32 (x86)、AMD64、IA-64、Alpha、PA-RISC、MIPS、PowerPC、SPARC がある。

PaX が提供する機能

PaX が提供するのはNXビット（あるいはそれに相当する各CPU/MMUアーキテクチャにある機能）の機能を使った（あるいはそれをOSでエミュレートした）メモリ保護機能である。また、return-to-libc攻撃や、メモリ空間配置に関する知識に依存した攻撃を防ぐため、アドレス空間配置のランダム化を行う。

実行空間保護

PaX の主要機能は実行空間保護である。一部プロセッサにあるNXビットの機能を用いて任意のコードの実行を防ぐ。それによって、コード注入やシェルコードといった攻撃を防ぐ。NXビットを持たないIA-32系CPUでは、PaX はその機能を様々な手段でエミュレートできる。
Linuxを含む多くのOSでは、ハードウェアのNXビットの機能を利用して、メモリのアクセス権を適切に設定する。図1は、1つのロードされたライブラリのあるプログラムのメモリセグメント群を簡単に図示したものである。緑のセグメントはデータで、青のセグメントはコードである。一般に、AMD64なども含めたプロセッサでのアドレス空間は、デフォルトでは図1のように明確にデータ部とコード部が定義されている。しかし、Linux ではデフォルトではアプリケーションが自身のメモリ保護設定を変更することを防ぐことができず、コード部を書き込み可能にしたり、データ部をコードとして実行することが可能となっている。PaX はそのような変更を防ぐとともに、典型的な操作に最適な最も制限のきつい保護設定を保証する。
実行空間保護が起動しているとき、mprotect() 制限も含まれ、PaX は本来コード部でなかった領域を実行可能にするような操作を不可能にする。これにより、書き込み可能だったことのある領域に存在するコードは実行不能となり、悪意があるかどうかとは関係なく、コードを後から注入することが不可能となる。
すると、Javaのジャストインタイムコンパイル方式のように、実行時にコードを生成して実行する必要のあるアプリケーションは動作できなくなる。しかし多くの場合、そのような機能を必要としているプログラムは、それに依存しないように書き換えることが可能である。根本的に実行時のコード生成が必要なものについては、システムアドミニストレータがその実行ファイルに印を付け、その実行ファイルについては制限が課せられないようにすることができる。
PaX チームは mmap() システムコールをどう扱うかを決定する必要に迫られた。mmap は共有メモリのマッピングや共有ライブラリのロードに使われる。そのため、使われている状況によっては書き込み可能なページや実行可能なページを生成できるようにしなければならない。PaX の現在の実装では、デフォルトで書き込み可能な無名メモリページのマッピングが可能となっている。ファイルのマッピングは mmap() コールが書き込みのパーミッションを指定している場合のみ書き込み可能にできる。mmap() は書き込みと実行が同時に可能なマッピングを生成しない。これは引数で明示的に指示されている場合でもエラーとなる。

実行不可ページの厳格化

デフォルトでは、Linux はNXビットを使って実行不可ページを正しく設定することはしていない。しかも、アーキテクチャによってはNXビットと同等の機能を持たないものもある。PaX は実行不可なページをなるべく実際に実行不可とするセキュリティポリシーに従って、設定を行う。
さらに、CPU がNXビット相当の機能を提供していないとしても、PaX は同等機能をいくつかの手法で提供（エミュレート）する。エミュレートによって性能は低下するが、セキュリティは向上する。しかも、一部の手法のオーバーヘッドは無視できるほど小さい。

PAGEEXEC

PAGEEXEC は NXビットを使うか、エミュレートする。NXビットがサポートされていないプロセッサの場合、各ページにエミュレートされたNXビットが付与される。その具体的方法はCPUのアーキテクチャに依存する。NXビットのあるプロセッサでは、PAGEEXEC は単にそれを使い性能をなるべく低下させないようにしている。
IA-32 では、NXビットのエミュレーションは実行不可ページのパーミッションレベルを変更することで行われる。この場合、あるページを実行しようとして、同時にそれがTLBにキャッシュされていなければ、プロテクション例外が発生する。IA-32 ではメモリ管理ユニットがこれをOSに通知する。実行コード用TLBとデータ用TLBは分離されているのが一般的であり、書き込み可能なページを初めて実行しようとしたとき、必ずLinuxカーネルとPaXがそれを検出できる。この例外を検出すると、プロセスを終了させるか、実行を継続できるようTLBを設定するかをカーネルが選択する。
PAGEEXEC は仮想空間を2つに分けることがないという利点がある。しかし、エミュレーションは後述の SEGMEXEC より遅く、場合によっては深刻な性能低下を招く。
2004年5月に登場した新たなIA-32用 PAGEEXEC は、実行可能ページの最高の仮想アドレスを覚えておき、それより大きなアドレスのページはユーザーページとする。これにより、スタックなどの高位のアドレスにある領域は性能低下なしに処理され、低位のアドレスにある領域は従来通りに処理される。これは、Exec Shield や OpenBSD の W^X (Write XOR Execute) 実装に似ている。

SEGMEXEC

SEGMEXEC は、IA-32 向けのNXビットエミュレーションであり、アドレス空間を2つに分割し、コードを両方の空間にマッピング（ミラーリング）する。命令フェッチの際、分割を跨いでアドレス変換が行われる。コードがそこにマッピングされていなければ、プログラムは終了させられる。
SEGMEXEC は仮想空間の大きさを半分にしてしまう。通常、個々のプロセスの仮想空間は 3GiB ある。SEGMEXEC を使うと、それが 1.5GiB ずつに分割され、一方がミラーリングに使われる。そのような問題はあるが、エミュレーション時の性能低下は少ない。2つの仮想空間にマッピングされる物理メモリは同じ実体であるため、メモリ使用量が増加することはない。

トランポリン・エミュレーション

トランポリンとは、GNUコンパイラコレクションで実装されているもので、コールスタック上に実行時に小さなコードを生成するものである。つまり、トランポリンはスタック上のメモリを実行可とする必要があり、PaX ではそのようなプログラムは終了させられてしまう。
トランポリンは自己書き換えコードの一種であるため、PaX にひっかかり、プログラムの終了を招く。PaX はこれを防ぐため、トランポリン生成を識別し、その実行を許可するようになっている。しかし、これはセキュリティを弱める可能性があるとされている。

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

アドレス空間配置のランダム化（ASLR）は、アドレス空間配置に関する知識を利用した攻撃に対処する技法である。それは、既存のコードをプログラマが意図しない順序で実行させる攻撃である。
PaX におけるASLRはスタック領域とヒープ領域のベースアドレスをプロセス毎に無作為に変化させる。また、オプションで mmap() や実行コード部のベースアドレスもランダム化する。これにより攻撃側が攻撃すべき位置を推測するのが難しくなる。
図2は、アドレス空間配置のランダム化を施したアドレス空間を図示したものである。点線と矢印で示された部分が仮想空間上の各領域間のランダムな空隙を示している。カーネルがプロセスを初期化するとき、これら矢印の長さが無作為に変化させられる（各領域の並び順は基本的に変わらない）。
プログラムの実行中、ヒープ領域はメモリアドレスの大きい方に成長していく。逆にスタックはアドレスの小さい方に成長していく。これらの領域を各プログラムがどれだけ必要とするかはOSには不明である。いわゆるプラグインなどの動的ライブラリを実行中にロードする場合、通常はヒープの前に置かれる。OSまたはプログラムはそれらライブラリを配置するのに適切なオフセットを選択しなければならない。PaX はアドレスのMSB側の部分をランダム化しない。これによって大まかな配置が守られ、各領域が重ならないようにする。
ランダム化の効果は CPU に依存する。32ビットのCPUでは、一般に仮想アドレスは32ビットであり、4GiB の空間にアクセス可能である。Linux は先頭 1GiB をカーネル用に使っているため、ユーザープロセスが使えるのは 3GiB である。SEGMEXEC はこれを半分に分割するので、ランダム化は 1.5GiB の範囲で行われる。ページサイズは 4KiB であり、ランダム化はページサイズ単位に行われる。MSB側の4ビットはランダム化されないので、ヒープ領域は仮想空間の先頭に、スタック領域は最後尾に配置される。このため、ヒープやスタックのランダム化される範囲は16ビット程度で表される範囲になる。
64ビットCPUでは、仮想空間はより大きくなる。従って、ランダム化はさらに大胆に行われることになり、攻撃される可能性がそれだけ少なくなると言える。

スタックベースのランダム化

PaX は、スタックのベースアドレス（のオフセット）を16バイト単位にランダム化し、同時にセグメントの配置をページ単位の空隙の大きさをランダム化する。全体としてのランダム化の程度は仮想空間サイズに依存する。例えば、32ビットの場合、スタックベースは256MiBの範囲のどこかに設定され、可能な位置は1600万通り、エントロピーは24ビットとなる。
スタックベースのランダム化は、シェルコードとreturn-to-libc攻撃のペイロードに影響を与える。シェルコード攻撃はスタック上のリターンポインタをペイロード内を指すよう変更しようとする。一方、return-to-libc攻撃はスタック上のフレームポインタを書き換えようとする。どちらにしても、成功する可能性は大幅に減る。スタックの位置は予測不可能となり、ペイロードによる書き換えは単にプログラムをクラッシュさせる結果となる。
シェルコードの場合、ペイロードの前にNOP命令（何もしない命令）をたくさん並べておくことがある。こうすることで、ジャンプ先が予測と多少違っても攻撃が成功するようになる。しかし、16バイトぶんのNOP命令を並べても、成功確率は1/16Mから2/16Mになるだけである。また、128バイトのNOP命令を並べても、成功確率は9/16Mにしかならない。成功確率はNOP命令数に比例する。
return-to-libc攻撃はコードを書き込むわけではなく、ある固定幅のスタックフレームを書き換える。このため、スタックフレームは正確に16バイト境界に配置されていなければならない。一般にスタックフレームは16バイトよりも大きいので、スタックフレームを繰り返し書き込むことで成功確率を上げようとする。

mmap() ベースのランダム化

POSIXでは、mmap() システムコールはプロセスが指定したオフセットかカーネルが選択したオフセットにメモリを配置する。無名メモリを使えば、中身のないメモリがマッピングされ、ファイルを指定すればその中身がマッピングされる。ダイナミックリンクライブラリは mmap() を使ってロードされ、コード部とライブラリのデータ部がそれぞれマッピングされる。データ部に書き込みがあれば、コピーオンライトの要領で無名メモリへのコピーが行われる。
mmap() では、仮想空間上のマッピングすべきオフセットを指定することもある。オフセットが指定されないと、OSが自動的に選択する。Linux のオフセット計算方法は予測可能であり、事前に定義された「mmap()ベース」を始点として計算される。このため、プロセスを起動したときに必ずロードされる標準Cライブラリ（あるいは libc）は常に同じアドレスにロードされる。
mmap()ベースのランダム化を行う場合、PaX はmmap()ベースをランダムにシフトさせ、全てのライブラリおよび他のmmap()コールでのマッピング位置を変えてしまう。このため、ダイナミックリンクされるコード（共有オブジェクト）は毎回ランダムに異なる位置にマッピングされる。攻撃者は特定のライブラリが特定のアドレスにロードされていることを当てにしていることが多い。従って、この機能によってreturn-to-libc攻撃が困難となる。ただし、シェルコードを使った攻撃では GOT（global offset table）を参照することで任意の関数のアドレスを参照可能である。
PaX はライブラリのロード順序は変化させない。従って、1つのライブラリのアドレスがわかれば、他の全てのライブラリの位置もわかってしまう。しかし、もっと重大な問題として、いったんライブラリの位置がわかってしまうと、他のランダム化をしていても意味がないという問題がある（シェルコードはライブラリ内の関数のアドレスさえ分かれば攻撃可能）。
ET_DYN 型の実行ファイル（PIC化されたライブラリ）をロードするとき、そのベースアドレスもランダム化される（mmap() を使うので通常の共有オブジェクトと同じである）。
スタックを実行不可にする機能と mmap() のランダム化を組み合わせると、return-to-libc攻撃の成功確率は激減する。32ビットシステムでは、本来の確率の16分の1になる。さらにスタックベースのランダム化を加えると、もっと攻撃が困難になる。

ET_EXEC ベースのランダム化

PaX は通常の配置アドレスが固定のコードもランダム配置可能であるが、若干問題がある。第一に、性能低下を招くことがある。第二にPaXがプロセスを予期しない理由で終了させてしまうという問題が発生することがある。従って、ET_DYN（ダイナミックリンクライブラリのファイル型）でコンパイルすることが推奨されている（その場合、完全なPICコードになるため）。
また、本来固定であるはずの ET_EXEC ベースのランダム化を行うと、PaX のVMミラーリングに起因するセキュリティ問題を引き起こす。対処していない古い PaX を使うときは、SEGMEXEC によるNXビット・エミュレーションをOFFにし、RANDEXEC による実行アドレスベースのランダム化をOFFにすることで対処する必要がある。

実行ファイルマーキング

PaX は、ELF形式の実行ファイルに印を付ける chpax や paxctl というツールを備えている。これらはELFヘッダ部に印を付けるので、ファイルシステムに依存することなく、実行ファイル自身に印を付けることができる。つまり、パッケージ化やコピー、暗号化などにおいても印が保持される。
PaX は実行ファイルについて、PAGEEXEC、SEGMEXEC、mmap()のランダム化、スタックのランダム化、ヒープのランダム化、ET_EXEC のランダム化、mprotect()の制限、トランポリン・エミュレーションという機能のON/OFFをマーキング可能である。
chpax では strip などでマーキングが消されることがあるので、paxctl で PT_PAX_FLAGS を設定するのが最も安全である。paxctl は PaX 用フラグを組み込んだ新たなELFプログラムヘッダ形式を使っている。各フラグはON/OFF/未設定の状態がある。未設定の場合どうするかは、カーネル内のPaXコードが設定に基づいて判断する。