Eskin+ (2001)
学生の吉田くんが研究で参考にしている論文です。システムコール列を観察して、侵入検知を行う研究はいろいろあります。ふつうはシステムコール列をn-gramの列に変換して、解析をするのですが、この論文ではプロセスごとに特性が異なり、固定長のn-gramでは対応できないことを主張しています。また、プロセス内部にあってもプログラムの構造からn-gramの長さを可変にするべきだとも主張し、そのための学習方法を提案しています。新規性が高い論文です。
- E. Eskin, W. Lee, and S. J. Stolfo, "Modeling system calls for intrusion detection with dynamic window sizes," in proceedings of the DARPA conference on Exposition on information survivability (DISCES '01), pp. 165-175, 2001.
| 問題点 | 提案 | 評価 |
|---|---|---|
| 不正検知システムの精度の改善 | 可変長なイベント部分列 | プロセスごとに適切なウィンドウサイズが異なり、それがエントロピーが予想できることを示している |
| プログラムの非決定性 | ワイルドカードの導入 | 議論にとどまり、評価はしていない |
| 学習 | あらゆるモデルが示す予測を結果の合算 | 基本的には論文[3]で示されていると思う。学習に要する時間は書いて欲しかった。 |
概要
侵入検知システム(IDS: Intrusion detection systems)は、収集したデータを分析して既知のあるいは道の攻撃を発見するものです。不正検知(anomaly detection)では、収集されたデータからシステムの正常状態に関するモデルを作成します。不正検知システムは、システムの実際の挙動と(正常状態の)モデルからの乖離から侵入を検知する仕組みです。
不正検知システムが侵入を検知する能力は、正常状態のモデルとしてどれだけ信頼性のおけるものが作成できるかにかかってきます。通常は、ログとして得られる、一連のイベント列を固定長の短いイベント部分列に区切ったものを基本としてモデルを構築します。*1
著者らは、イベント列を可変長のイベント部分列に分割することで、モデルの信頼性を向上できるのではないかと考え、二つの方式を提案しています。この研究が対象としているのはシステムコール列なのですが、発想の原点は、システムコールの部分列が発生する確率は等確率とは限らず、むしろ大きな偏差があるということです。*2この性質を情報理論(情報理論と情報技術(IT)はまったく別のことを指します。シャノンによって創始された計算機科学の分野で通信工学などの基礎理論の一つです。情報エントロピーの概念は情報理論から生まれました。)を応用して発見することができるとしています。
情報エントロピーを利用した最適ウィンドウサイズの導出
ウィンドウとは、上述のシステムコールの部分列のことで、その長さがウィンドウサイズです。ウィンドウサイズに求められるのは、そのウィンドウの内容からそのウィンドウの次のシステムコールを比較的正確に求めることです。この論文では、ウィンドウとその直後のシステムコールの発生が、より一様であるほど、不正検知システムの性能が向上するとしています。*3
情報理論においてデータの一様性は情報エントロピーとして扱われます。詳しくは情報理論の教科書を見て下さい。そこで、システムコール列について、ウィンドウサイズを変化させて情報エントロピーを計算します。このなかで情報エントロピーが最小となるウィンドウサイズを採用すると最も効果的な不正検知が可能となるようです。
この結果、アプリケーションによって最適なウィンドウサイズが異なるであろうことが予想されました。ftp > 10, ps (LL) > 10, eject = 4, xlock = 4, named = 5, login = 3, ps (UNM) = 5 という結果です。*4で、実際にMIT Lincoln研究所で公開された IDS に関するデータセットで実験を行った結果も報告されているのですが、概ね、この結果の通りになったようです。例外は、ps (UNM) は情報エントロピーがウィンドウサイズ = 5 を主張していますが、実験で最もよかったのはウィンドウサイズ = 3でした。グラフが読み難いので、ほかにも矛盾した結果があるのかもしれません。
可変長ウィンドウサイズの導出
可変長ウィンドウサイズを採用する背景には、システムコールを発生させているプロセスの振舞いをそのプロセスの元となっているプログラムのコールグラフでモデルできることにあります。一見、構造のない線形なシステムコール列であっても、その背後のモデルは複雑だということです。このことから、ウィンドウサイズの長短に得失があることが理解できます。つまり、長いウィンドウを採用すれば、コールグラフにおけるパスを一意に定める可能性が高まる反面、各ウィンドウに相当する状態をプロセスが実現する頻度が少なくなり、結果としてウィンドウから得る頻度情報に雑音が増えてしまいます。また、もうひとつの動機付けとして [ioctl; mmap; (open | close); mmap; unlink] のようなコールグラフがあったときに適切な正常実行のパターンとしてワイルドカードを用いて [ioctl; mmap; _; mmap; unlink] とするのが自然です。*5
疎マルコフ変換器
彼らが採用したモデルは、確率つきのシステムコールパターンの集合です。システムコールパターンは、ワイルドカード(_)を含むシステムコールの部分列です。*6システムコールパターンの集合をTRIEのような木構造を用いて表現し、sparse prediction tree(疎予測木?)と呼んでいます。
予測木に確率を与えるときには、予測木の葉にシステムコールごとにカウンターを用意し、練習用のデータから得られるウィンドウが葉に該当する頻度を計測し、最後にそれらを確率に変換します。*7
問題となるのは予測木の形をどうするか、そしてどのようにワイルドカードを挿入するかということです。基本的なアイデアは(驚け！)、一定以下の高さのすべての木を生成し、それらに対して前述の学習を施す方法です。当然のことながら、高さhに対して(n+1)**hだけの木は存在するわけです。で、それらに対する重みづけをBayes法で修正することによって、信頼性の高い木を生成するということです。もちろん、この方法を単純に試みるのは計算コストが高すぎるのですが、Eskinらによって効率的な方法が提案されているそうです。
提案方法は、前述のLincoln研究所のIDSデータにもとづいて評価し、いずれの実験についてもほかの手法を凌駕することが示されています。最悪の IDS の検知率 = 1.0 としたときの false positive(要するに最悪の false positive)が ps (UNM) の場合で、0.03%ということです。この数値をどう思うかということですね。正常なシステムコールのうち0.03%が誤って侵入と判定されるというのは一日に何回、誤判定があるということだろうか？
感想
いろいろ面白かったです。この論文だけでは詳細が分らないので、Eskinらの論文を見たいところです。
関連研究
- C. Warrender, S. Forrest, and B. Pearlmutter, "Detecting intrusions using system calls: alternative data models." in proceedings of the 1999 IEEE Symposium on Security and privacy, pp. 133-145, 1999.
*1:[e1; e2; e3; ...]に対して長さ3の部分列は[ (e1, e2, e3); (e2, e3, e4); (e3, e4, e5); ...]のように作成できます。
*2:このことを最初に指摘したのはMarceauの論文らしい
*3:直感的には分るんだけれども、いまいちしっくりこない。。。
*4:LLはLincoln Laboratory、UNMはUniversity of New Mexicoのことでしょう。
*5:Wagnerがやっていた手法に似ています。プログラム依存グラフから、システムコール列を出力する非決定性プッシュダウンオートマトンを生成し、それを正常モデルとして用いる研究です。原理的にfalse positive = 0 にするのですが、Wagner の方法は実行速度が遅くなり、現実的ではありませんでした。わたしの学生だった鷹岡くんはオートマトンの動作を決定化することを試み、通常のプロセスに対して数10%のオーバーヘッドで実行することに成功しました。
*6:論文では*を用いていたが、正規表現と紛らわしいので、ここでは _ を用いた。
*7:結果を滑らかにするために、実際の頻度＋αで確率を算出しているらしいが、詳しい説明はない。
