高速パケットキャプチャのための選択近似機能を有する空間分割型パケット分類器の実現と評価

全文

(1)社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 2003−DSM−31 （16） 2003／11／26. 高速パケットキャプチャのための選択近似機能を有する空間分割型パケット分類器の実現と評価大須賀怜 † 加藤和夫 † 片山喜章 † 高橋直久 † 概要: ネットワーク監視では，流れるパケットをキャプチャして内容を分析する方法が広く用いられている．近年の高速かつ大規模なネットワークでは全てのパケットをキャプチャするのは困難であり，その実現のためには高価なハードウェアが必要となる．そこで，必要なパケットだけを選択してキャプチャできれば高速ネットワークへの対応が容易になる．一方，複雑な条件に対しても高速にパケットを選択するために空間分割型パケット分類法を用いた方式が提案されている．この方式では分類条件が複雑になると事前計算に多大の時間を要すること及び実行時に必要な各種データ量が膨大になることが問題となる．本稿では，選択近似機能を有する空間分割型パケット分類方式を提案する．この方式ではパケットキャプチャの持つ，必要なパケットさえ必ず取れていればいいという特性に着目してパケットの分類に誤差を許す事により近似を実現する．これにより事前計算時間の短縮と実行時に必要なデータ量の削減が可能になる．評価実験では，16 バイトのフィールドをキーとして使用するフィルタを 100 個用いる場合でも，使用メモリ量を 1/5 程度に抑えて高速なパケットキャプチャシステムを実現可能である事を確認した．. Implementation and Evaluation of Space-Division Packet Classification with Selective Approximation for High-Speed Packet Caputuring Satoshi Osuga†. Kazuo Kato†. Yoshiaki Katayama†. Naohisa Takahashi†. Abstract: The mothod which caputuring packets and analyze its contents is common in network monitoring. It is difficult to capture all packets in a high-speed and large-scale network. If only required packets are selected and captured, the correspondence to a high-speed network will become easy. On the other hand, space-division packet classifiers are proposed in order to select packets at high-speed. If the rules for packet classification become complicated, it will pose a problem that much time is consumed for prior calculation and that the amount of data required at the time of execution becomes huge. In this paper, we propose a space-division packet classification with selective approximation. In this method, an approximation of packet classification is presented so as to reduce the amount of data for packet classification by allowing errors in packet classification paying attention to the characteristic which this system has that what is necessary is have just surely taken even the required packet. Thereby, shortening of prior calculation time and curtailment of the amount of data required at the time of execution are attained. It was checked in the experiment that high-speed packet caputuring system can be implemented in holding down memory to 1/5 even when using 100 filters which use 16 bytes of field for key.. 1. はじめに. ネットワークの監視・診断ではネットワークを流れるパケットを収集して，その中身から状態を把握するパケットキャプチャシステムが広く使われている．しかし，高速なネットワークでは膨大な量のパケットが短時間で流れてくるため，パケットキャプチャシステム内部での転送速度やディスクの書き込み速度，記憶装置の容量といったハードウェア上の制限や，キャプチャ後にそれらの処理が追いつかないといったソフトウェア上の制限により，流れるパケット全てをキャプチャし監視・診断を行うのは困難である．そこで，フィルタリング技術を用いてキャプチャするパケットの監視・診断に必要なパケットだけに絞り込むという方法が考えられる．この方法を用いればパケットキャプチャシステムが処理するトラフィック量を減らす事が可能になる．しかし，高速なネットワークでフィルタリングを行うにはフィルタリング速度も高速でなければならない．一方，多数のフィルタに対しても高速なフィルタリングが行える方式として空間分割型のパケット分類方式がある [2]∼[6] ．しかし，大規模で複雑なネットワークではフィルタリングの分類条件も複雑かつ多数になり，空間分割型のパケット分類方式を用いるには多くのメモリが必要となり，高コストになってしまう．このため本稿では，選択近似機能を有する空間分割型パケット分類方式を提案する．本方式は，パケットキャプチャでは必要なパケットが必ずキャプチャされていれば余分なパケットがキャプチャされていても † 名古屋工業大学. 大学院工学研究科 Graduate School of Engineering, Nagoya Institute of Technology. 後で取り除く事ができるという特性に着目してキャプチャ条件の近似を行う事により必要なメモリ量を減らす．本方式の特徴は次の通りである．特徴 1 キャプチャの条件に合致したパケットは必ず選択することを保証するように空間分割により作成される領域を統合して近似する機能を実現し，実行時に必要なデータ量を削減する特徴 2 パケット分類機能を 1 チップで実現可能にするため，メモリ容量に応じて近似の度合を制御する機構を提供する．特徴 3 特徴 1 を実現するとキャプチャの条件に合致しないパケットもキャプチャされ，ノイズが発生する場合がある．そこで次の 2 つの近似機能を実現し，ユーザの用途に応じて選択的に使用できるようにする • ノイズの発生量を抑える事を優先して領域統合する (α近似) • 近似処理のための時間を抑える事を優先して領域統合する (β近似) 本稿の構成は次の通り．まず 2 でパケット分類問題を定義する．3 では関連研究について述べ，従来の手法を概観する．4 で，提案方式の実現法について述べ，5 では選択近似機能の詳細な実現法について述べる．6 では，評価実験について述べ，7 で実験結果について考察する．. 2 パケット分類器 2.1. 機能概要. 分類時に参照するパケットのフィールドをキーと呼び，各キーが満たすべき条件を記述したルールをフィ. −91− 1.

(2) ルタと呼ぶ．フィルタの順序付き集合をフィルタセッ文献 [1] ∼[4] の方式は，前述のように並列型のトと呼び，フィルタの識別子の集合で表す．パケット SIERRA の 1 つの実現法と位置づけられる．[3] の方分類器は，フィルタセット F とパケット P が与えら式では，分割された空間を並列に処理する事によりれた時，次節で述べる照合法によりキーとフィルタの 3000 個のフィルタでも 300KB 程度のメモリを用いてルールとを照合し，パケット P の全てのキーが対応す数回のテーブル参照のみで分類している．しかし，近るルールとの照合に成功するフィルタ (実行可能フィ年の高速ネットワークに対応するにはテーブルをきわルタと呼ぶ) すべてからなる集合 F’ を選ぶ関数である．めて高速にアクセスできるメモリ (プロセッサ内部のキャッシュメモリなど) に収める必要があり，高コスト 2.2 照合法となる． • 完全一致照合 (exact matching) フィルタのルール文献 [ 5][6] の方式はパイプライン型 SIERRA の最適でキーの値を v と指定した時，パケットのキーの化によりメモリ量の削減を行っているが，1 チップ化値が v と一致すれば照合に成功するにはまだメモリ量が大きい． • プレフィクス照合 (prefix matching) フィルタの本論文では SIERRA の計算で特定の近似を許して，ルールでキーの値を v/p と指定した時，パケット 1 チップに収められる程度にテーブルサイズを小さくのキーの値の上位 p ビットが v の上位 p ビットとする事で，複数のフィールドをキーとした多数のフィ一致すれば照合に成功ルタを低コストで高速に分類可能にする． • 領域照合 (range matching) フィルタのルールでキーの値を v1-v2 と指定した時，パケットのキー 4 提案方式の実現法 SIERRA の実現方式として SIERRA の計算を作表の値が v1 以上かつ v2 以下であれば照合に成功計算と索表計算に分割し，索表計算をそのままハード 2.3 関数による表現ウェアにマッピングして高速化を実現するため並列型パケット分類器は，計算幾何学的なアプローチによ SIERRA を採用する．1 チップで実現するため近似をり，パケット分類問題を多次元空間における点位置決導入し，表の大きさを任意に制御可能にする．ここで定問題として捉えることができる [2]∼[6] ．すなわち，近似とは，sieve 及び product の計算を近似することパケットのキーの数を n としたとき，キーの値は n 次により索表計算で用いる表を小さくする事を意味す元空間の座標として表され，フィルタにより n 次元空る．これは，ダミーフィルタの追加やフィルタの削除間の領域が指定される．分類器は，与えられたパケッにより実現される．ルーティングテーブル探索やファトがどのフィルタの指定領域に含まれるか決定する．イアーウォール等の一般的なパケット分類では，全てフィルタを篩にかける関数 sieve を導入し，この篩ののパケットに対してルールとの照合が正確に行われな配列 SIERRA(SIEve aRRAy) を用いると分類器は以下ければならない．しかし，ネットワーク監視・診断シのように定義できる [5][6] ．ステム等のパケットキャプチャ用のパケット分類ではルールとの照合で近似により誤差が生じて監視・診断 SIERRA(F, k1, k2, k3, ..., kn) = に必要の無いパケットをキャプチャして保存しても後 sieve(sieve(sieve(...sieve(F, k1, 1), で診断の際に取り除けばよい．例えば，HTTP による k2, 2), k3, 3), ..., kn, n) 通信のトラヒックを監視したい場合，HTTP のパケッ • フィルタ篩関数 sieve(F, ki, i) トは全てキャプチャされなければならないが，それ以 i 番目のキーの値が ki のとき，i 番目の条件が満外のパケットは廃棄してもキャプチャしても監視結果たされるフィルタの集合を入力フィルタ集合 F かに影響を与えない．この特性によりキャプチャ条件のら選択する関数近似が可能になる． • フィルタ照合関数 SIERRA(F, k1, k2, k3, ..., kn) 4.1 作表計算と索表計算の分割 n 個の sieve を用いて，n 個のキーの値がすべて対 SIERRA の関数 sieve と product はそれぞれ作表計算応する条件を満たすフィルタを入力フィルタ集合と索表計算の 2 つの計算に分解できる．sieve の作表計 F から選択する関数算では，キーの値と出力フィルタ集合の対応表 (sieve ここで，複数の sieve の計算に対して，その積集合を表) を作成する．この表のエントリー数は，キーが取り求める関数 product を導入すると，並列型の SIERRA 得る値の数になる．sieve の策表計算では，sieve 表とを定義できる．例えば n=4 の場合は次のようになる．キーの値から出力フィルタ集合を求める．product の作 SIERRA(F, k1, k2, k3, k4) = 表計算では，2 つの入力フィルタ集合の組と出力フィ product(product(sieve(F, k1, 1), sieve(F, k2, 2)), ルタ集合の対応表 (product 表) を作成する．この索表 product(sieve(F, k3, 3), sieve(F, k4, 4))) 計算では，この表と 2 つの入力フィルタ集合の組から出力フィルタ集合を求める． • フィルタ集合の積関数 product(F1, F2) SIERRA の作表計算では，入力として与えられる可入力フィルタ集合 F1, F2 の積集合を求める関数能性のあるフィルタ集合の数だけ sieve 表を作成する．同様に，入力として与えられる可能性のあるフィルタ 3 関連研究パケットの分類について，高速ルーティングテーブ集合の組の数だけ product 表のエントリーを作成する． SIERRA の索表計算は次のように行う．最初にすべル探索のために連想メモリ (CAM) を用いた方式 [1] がある．この方式では，簡単なハードウェアで高速なパてのキーに対して，それぞれ対応する sieve 表とキーのケットの分類が可能であるが，高コストになるためフィ値から出力フィルタ集合を求める．次に 2 つの sieve のルタ数が多い場合やキーが長い場合には適応が難しい．索表計算の結果によりできるフィルタ集合の組と，そソフトウェアによる実現方式として V.Srinivasan られに対応する product 表から出力フィルタ集合を求めの方式 [2] や Pantaj Gupta らの方式 [3] がある．これらる．さらに，2 つの product 表の索表計算の結果によりの手法ではどちらも次元ごとに分割して積を求めるとできるフィルタ集合の組と，それに対応する product 表いう空間分割によるパケットの分類を行っている．から出力フィルタ集合を求めることを繰り返す．本節 V.Srinvisan らの方式では複数のフィールドをキーとでは送信元 IP アドレスと宛先 IP アドレスの 2 つのキーした場合でも少ないメモリ量で平均的に高速なパケッを用いた次の二次元のフィルタを例として，SIERRA トの分類が可能で有る．しかし，最悪の場合にはかなの実現法を示す． F1 送信元 IP アドレスが A∼C で宛先 IP アドレスがりの時間がかかる．. 2 −92−.

(3) F∼H のものをキャプチャする F2 送信元 IP アドレスが B∼D で宛先 IP アドレスが E∼G のものをキャプチャする二次元での SIERRA は次のように表される． SIERRA(f, k1, k2) = product(sieve(F, k1, 1), sieve(F, k2, 2)) この時，作表計算と索表計算は次のようになる． (作表計算) STEP1(sieve) 宛て先 IP アドレスと送信元 IP アドレスの 2 個のキーを軸とした 2 次元空間上にフィルタが照合に成功する領域を表し (図 1)，次元ごとに射影を求め，キーの値とその値に対して照合に成功するフィルタ集合の対を表にする (表 1,2) STEP2 フィルタ集合が同じキーの値に対し同一の識別子 (ID) を割り当てる (表 3,4) STEP3(product) それぞれの表の ID の組み合わせを求める (表 5) (索表計算) STEP4(sieve) 受信パケットから各次元のキーの値を取り出し，STEP2 で作成した表を参照してキーの値に対応する ID を求める STEP5(product) STEP2 で作成した表を参照して ID の組に対応する ID を求める STEP6 STEP3 で求めた表を参照し，STEP5 で求めた ID の組に対するフィルタ集合を決定する表 1: 送信元 IP アドレス表 2: 宛先 IP アドレスのの領域定義表領域定義表 Key 0∼ A∼ B∼ C∼ D∼. Filterset {} {F1} {F1,F2} {F2} {}. Key 0∼ E∼ F∼ G∼ H∼. Filterset {} {F2} {F1,F2} {F1} {}. 表 3: 送信元 IP アドレス表 4: 宛先 IP アドレスのの分類表分類表 Key 0∼ A∼ B∼ C∼ D∼. ID1 0 1 2 3 0. Key 0∼ E∼ F∼ G∼ H∼. 表 5: ID の組合わせの領域定義表 (IP アドレス) ID1 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3. 4.2. ID2 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3. Filterset {} {} {} {} {} {} {F1} {F1} {} {F2} {F1,F2} {F1} {} {F2} {F2} {}. !. ID2 0 1 2 3 0. # $ % '& ( " # $ %

(4) . 図 1: 空間上のフィルタ. 並列型 SIERRA の実現法. キーが N 種類の場合，フィルタを N 次元の空間で表現して N 入力の product によりフィルタ集合を決定する事が可能である．例えば 4 次元の場合，4 入力の product により SIERRA は次の様に計算できる． SIERRA(f, k1, k2, k3, k4) = product4(sieve(F, k1, 1), sieve(F, k2, 2), sieve(F, k3, 3), sieve(F, k4, 4)). しかし，N 次元の空間を表現するには膨大なメモリが必要となる．そこで，図 2 のように作表計算の STEP2 と STEP3 を繰り返して段階的に処理する事で使用メモリ量を抑えて実現する．索表計算では図 3 のように STEP5 を各段階で並列に行う事でメモリ参照回数を抑えて実現する．例えば 4 次元の場合，SIERRA の計算は次のようになる． SIERRA(F, k1, k2, k3, k4) = product(product(sieve(F, k1, 1), sieve(F, k2, 2)), product(sieve(F, k3, 3), sieve(F, k4, 4)))

(5)

(6) . . !#"$. . 図 2: 作表計算の流れ. 図 3: 索表計算の流れ. 4.3 sieve 関数と product 関数の近似計算 SIERRA の各 STEP における表の大きさは前 STEP の出力フィルタ集合の種類 (異なるフィルタ集合の数) で決まる．そこで提案方式では STEP3 の表を小さくしデータ量を削減するために，STEP2 で領域統合による近似を行う．sieve 及び product における近似は次のように定義される． • sieve(F, ki, i)=O, sieve(F, ki’, i)=O’ (O’ , O) のとき，sieve(F, ki, i) の値を O’ とすることを sieve(F, ki, i) を近似するという • product(F1, F2)=O, product(F1’, F2’)=O’ (O’ , O) のとき，product(F1, F2) の値を O’ とすることを product(F1, F2) を近似するという例として，図 1 の空間を図 4 のように斜線と波線で示した 2 つの領域を統合してフィルタ 2 の領域を拡大する場合を考える．これは表 1 においてキーが A 以上 B 以下のときにダミーフィルタ F2 を混入させることに対応する．すると，表 1・表 5 はそれぞれ表 6・表 9 のように近似される．表 7 は表 5 に比べてデータ量が減っている事が分かる．この時，ダミーフィルタによって本来のフィルタの照合結果を正しく表していない領域 (誤差領域) が生じる．例えば，送信元 IP アドレスが A∼B で宛先 IP アドレスが E∼F のパケットは本来廃棄されるはずであるが，キャプチャされてしまう．このように，誤差領域によって余分にキャプチャされてしまうパケットをノイズと呼ぶ．また，図 5 のように領域統合して F2 の領域の一部を取り除くと，送信元 IP アドレスが B∼C で宛先 IP アドレスが E∼F のパケットは本来キャプチャされるはずなのに廃棄されてしまう．本方式では，このような誤差領域にパケットを廃棄する領域が含まれる統合を禁止する事により，キャプチャの条件に合致したパケットは必ず選択することを保証する (特徴 1 の実現)．この近似処理は領域の大きさを変化させるだけなので，次のような特徴が有る． • 索表計算は近似無しの場合と同じ方法を適用可能 • 文献 [5][6] 等，他の空間分割を用いたパケット分. 3 −93−.

(7) み合わせごとにフィルタ集合の差を求める．類方式にも適応可能近似を実現するためにはどの出力にどのようなダ STEP2-2-1(α) 各次元でフィルタ領域の幅を求める例:送信元 IP アドレスの次元で F1 の幅は A と C ミーフィルタを混入させるか決定するアルゴリズムの差，F2 の幅は B と D の差が必要となる．アルゴリズムの詳細は次章で述べる． STEP2-2-2(α) 各フィルタ領域について次元ごとの幅の積を求め，体積を算出する例:F1 の各次元での幅はそれぞれ C-A,J-H,H-F,L-K なので体積 VF1 は (C-A)(J-H)(H-F)(L-K) STEP2-2-3(α) 各フィルタ領域の体積を近似する次元での幅で割った商を求め，各フィルタ領域の切り口の大きさを算出する例:F1 の送信元 IP アドレスの次元での切り口の大きさは VF1 /(C-A) = (J-H)(H-F)(L-K) 図 4: 領域統合の例図 5: 禁止される統合の例 STEP2-2-4(α) 近似する次元での各 ID の幅 (その ID が割り当てられているキーの数) を求める表 7: 近似後の表 5 例:送信元 IP アドレスの次元で 3 の ID の幅は D-C ID1 ID2 Filterset 0 0 {} STEP2-2-5(α) 全ての ID の組について統合によって表 6: 近似後の表 1 0 1 {} 変化する領域の切り口の大きさと ID の幅との積 0 2 {} Key Filterset ID1 0 3 {} を求め，領域の体積の差 (統合を行った時に生じ 0∼ {} 0 2 0 {} A∼ {F1,F2} 2 る誤差領域の体積) を算出する 2 1 {F2} B∼ {F1,F2} 2 2 2 {F1,F2} 例:送信元 IP アドレスの次元で 2 と 3 の ID の組 C∼ {F2} 3 2 3 {F2} の領域の体積の差は (J-H)(H-F)(L-K) × (D-C) D∼ {} 0 3 0 {} 3 1 {F2} 最後に，次の 2 つの STEP を繰り返す事によりフィル 3 2 {F2} タ集合の差が小さい識別子の組から順に，ID の数が 3 3 {} 十分に減るまで領域を統合する． 5 選択近似機能の実現法 STEP2-3-1(α) 最も領域の体積の差が小さい ID の組今回，SIERRA の近似アルゴリズムとしてノイズ量を統合するを抑えるアプローチを取るα近似と近似計算に要する STEP2-3-2(α) 統合により領域が変化した ID を含む時間を抑えるアプローチを取るβ近似を提案する (特 ID の組のみ領域の体積の差を再計算する徴 3 の実現)．以下でα近似 · β近似の動作を説明する．以上の STEP によりα近似は実現される．. !. 5.1. # $ % '& ( " # $ %

(8) . α近似. "#!. % & '

(9) ( $ % & ' . 5.2. β近似. β近似は STEP2 を次のように拡張し実現される． α近似では近似によって変化するフィルタ領域の大 STEP2-1( β) STEP2 と同じきさに着目して，フィルタ領域の変化量が小さくなるように統合領域を選択する事でノイズ量を抑える．こ STEP2-2(β) ハッシュ値の等しい ID の組を選び，領域を統合するの方式では，各キーが全ての値を均一に取る場合には確実にノイズ量が抑えられるが，実際のパケットでは β近似ではこのように統合する領域を高速に選択するキーの値が偏っている．そのため，実験によりこの方ことで近似に要する時間の増加を少なく抑えている．式でノイズ量を抑えられるのかを評価する必要が有る． 6 評価実験 α近似は STEP2 を次のように拡張して実現する．実験により次の事を確認する． STEP2-1(α) STEP2 と同じ • 近似によるメモリ量削減効果 STEP2-2(α) ID の組み合わせごとにフィルタ集合の • α近似のノイズ量削減効果差を求める STEP2-3(α) フィルタ集合の差が小さい ID の組から • β近似がコンパイル時間に与える影響順に，ID の数が十分に減るまで領域を統合する 6.1 実験システム α近似ではこのようにフィルタ集合の差に着目して領域統合することにより誤差領域を小さく抑えている．評価実験のため下記 3 つのサブシステムを実現した． STEP2-2(α) と STEP2-3(α) の詳細について 4.1 節でユーザが記述したフィルタがキャプチャシステムに渡用いたフィルタを拡張した次の 2 つのフィルタを例にされるまでのデータの流れを図 6 に示す． • トランスレータ動作の詳細を説明する．ユーザが CCL 記述ユーザ F1 送信元 IP アドレスが A∼C かつ送信元ポート番号言語によって記述しが H∼J で宛先 IP アドレスが F∼H かつ宛先ポー CCL 記述言語たフィルタをコンパト番号が K∼L のものをキャプチャするイラが理解可能な形トランスレータ F2 送信元 IP アドレスが B∼D かつ送信元ポート番式に変換する号が M∼N で宛先 IP アドレスが E∼G かつ宛先中間コード • コンパイラポート番号が O∼P のものをキャプチャするフィルタを空間上にまず最初に STEP2-1(α) で表 3,4,8,9 にように ID が求コンパイラ表現し近似を行い，められる．索表計算で用いる表分類表表 8: 送信元ポート番号表 9: 宛先ポート番号 (分類表) を作成する KEY FILTERSET ID3 KEY FILTERSET ID4 0∼ {} 0 0∼ {} 0 • キャプチャシステムキャプチャシステム I∼ {F1} 1 M∼ {F2} 1 パケットヘッダの値 J∼ {F1,F2} 2 N∼ {F1,F2} 2 に従い分類表の探索図 6 システム全体での K∼ {F2} 3 O∼ {F1} 3 フィルタのデータの L∼ {} 0 P∼ {} 0 を繰り返してパケッ流れ次に STEP2-2(α) を次の様なステップで行い ID の組トを分類する. 4 −94−.

(10) 6.1.1 CCL 記述言語実験システムでは”CCL(Caputure Control List) 記述言語”[7] を用いてルールを記述する．例として，CCL 記述言語を用いて”133.68.13.0/24 のポート 80 番宛のパケットを全てキャプチャ”というルールを表現すると次のようになる． (10 ((IPdst 133.68.13.0/24) (PORTdst 80)) ACCEPT). 6.1.2 トランスレータと中間言語コンパイラでは前節の CCL で記述されたルール集合をトランスレータによって変換したビットマップで表現した中間コードを入力として扱う．この中間コードでは 1 つのキーの条件を 256 ビット (32 バイト) で表現する．ルール 1 つは 256*16=4096 ビット (512 バイト) で表現される．例えば，キーの値が”100 以上 200 以下”と指定された場合，中間コードでは”00 00 00 00 00 00 F0 FF FF FF FF FF FF 00 00 00”となる．. 下”という指定があった場合，16 進数で表現すると”00C8 以上 0258 以下”となり，上位バイトは”00 以上 02 以下”であるが下位バイトは上位バイトの値によって領域が変化する． 4. フィールドごとに条件指定を許しているので 2 つ以上のフィールドの内容を条件として用いる事はできない例えば、”送信元 IP アドレスと宛先 IP アドレスが同じもの”等．. ・制約事項に対する対応方法本システムは必要の無いパケットをできるだけ破棄する事によりキャプチャシステムが取り込むパケットの量を減らす事を目的であり，ルールとの正確な照合は取り込んだ後に改めて行われる．よって，取るべきパケットが確実に取れるのならばルールの変更が可能である．そこで，次の方法により制約に対応する． 1. ペイロードのチェックはせず，ルールのヘッダに関する記述だけを使用 6.1.3 コンパイラと分類表 2. 使用頻度が高いフィールドから順に 16 個選択 4・5 章で述べた表を作成する．コンパイラの動作 3. ルールを分割して複数のルールで表現環境は次の表の通りである．上記の例の場合，”上位バイト 00 かつ下位バイト C8 以上”・”上位バイト 01 かつ下位バイト 0 以上表 10: コンパイル環境 FF 以下”・”上位バイト 02 かつ下位バイト 0 以上 CPU Xeon 2.4GHz MEMORY PC2100 512MB REG × 2 58 以下”という 3 つのルールに分割される． HDD Maxtor MX4R080L0 MOTHER BOARD SuperMicro X5DPE-G2 4 の制約は対応できないため，ルール自体を除外する事にする．また，これらの対応によってルールを変更コンパイラが出力する分類表のデータ構造を表 11 にすると幾つかのルールの内容が等しくなるので，重複示す．したルールは 1 つにまとめる．表 11: 分類表のデータ構造 STEP3 で組み合わせる表の数 reserved キーとするフィールドの位置最初の STEP2 で作成される表の MaxID 2 回目以降の STEP2 で作成される表の MaxID 2 回目以降の STEP2 で作成される表のエントリ数最初の STEP2 で作成される表 2 回目以降の STEP2 で作成される表. 1 バイト. 6.2. 実験用データ. (1) サンプルルール実験で用いるルールはオープンソースの IDS である”snort”[8] が使用しているルールを利用して作成す 1 バイト×キーフィールドのる．snort のルールは幾つかの種類に分類されており，数 (16) 4 バイト×各表のエントリ数 2027 個のルールが有る．その中でペイロードも参照し ×表の数 (8+4+2+1) ているものは 1834 個である．本システムではヘッダ 4 バイト×各表のエントリ数の内容からパケットを選択しているため，ヘッダとペ ×表の数 (8+4+2+1) 1 バイト×キーフィールドのイロードの両方を参照しているルールに関してはヘッ幅 (256) ×キーフィールドの数 (16) ダのみを参照する事にし，ペイロードのみ参照してい 4 バイト×各表のエントリ数 ×表の数 (8+4+2+1) るルールは使用しない事とした．次に各ルールが使用しているキーフィールドを調べたところ，合計 28 バこの分類表の大きさがキャプチャシステムに要求さイトのフィールドを使用している事がわかった．実験れるメモリ量となる．環境として用いるキャプチャシステムはパケットの先 6.1.4 キャプチャシステム頭 64 バイトの中から 16 バイトをキーフィールドとし実験 2 で誤差の評価に用いたパケットキャプチャシて選択する仕様になっているため，このままでは snort ステムは文献 [7] の提案に基づいて作成されたシステのルールは適応できない．そこで，まず使用頻度の低ムである．このシステムではパケットの分類を数回のいフィールドを省略する事によりキーフィールドを 16 メモリ参照のみのフィルタ数に依存しない時間で実現バイトまで減らす事にした．使用頻度の高いフィールできる．簡単なハードウェアで実装を行うため，キードから順に並べたところ次の表のようになった．表 12: 各フィールドの使用回数として使用できるフィールド数とフィールド幅は固定フィールド名使用回数であり，今回の実験システムではフィールド数 16 個， Protocol 1995 フィールドの幅は 8 ビットとした． IP destination 1928 6.1.5 実験システムの制約事項とその対応方法 PORT destination 1576 ・制約事項 IP source 280 PORT source 280 1. パケットの先頭 64 バイトからキーとなるフィー ICMP TYPE 131 ルドを選択するため，ペイロードを参照するルー ICMP CODE 56 ルは記述できない． Length 42 TCP Flags 38 2. 今回実験に用いるキャプチャシステムではキーと ICMP ID 16 して選択するフィールドの数が 16 個で固定のた Fragment Bits 7 め，ルール全体で 17 個以上のフィールドをキー Identifier 7 としている場合は記述できない． TCP Sequence Number 6 3. フィールドをバイト単位でキーとして扱うため， ICMP Sequence Number 6 2 バイト以上で表現される値 (ポート番号等) を TCP ACK Number 6 TTL 3 領域照合する場合には単一のルールでは扱えない場合がある．例えば”ポート番号 200 以上 600 以これらのフィールドのうち，次の組み合わせはパケッ 3 バイト 8 バイト. 5 −95−.

(11) の事が分かる． 1. 近似を大きくするとコンパイル時間が短くなる 2. β近似は近似を行わない場合に比べてコンパイル時間が短縮される 1 の結果は近似によってデータ量が減少するため各処以上より，ルールに使用するキーとして次の 7 つの理における計算量が減り，コンパイルに要する時間が短縮されたと考えられる．また，2 の結果について図フィールド，計 16 バイトを選択する事にした． 6 と図 7 を比較するとβ近似は近似に要する時間がコ表 13: 今回選択したフィールドンパイル全体の処理時間に比べて極めて短く，近似処フィールド名バイト数理に要する時間より他の処理が高速化された時間の方 Protocol 1 が大きいため近似無しの場合より高速にコンパイルで IP destination 4 IP source 4 きていると考えられる．トの同じ場所を使用する． • • • •. ICMP TYPE と PORT source の上位バイト ICMP CODE と PORT destination の下位バイト ICMP ID と TCP Sequence Number ICMP Sequence Number と TCP ACK Number. PORT destination PORT source Length TCP Flags. 2 2 2 1. 実験 2 フィルタ誤差による影響図 8 で各ファイルサイズにおけるノイズ率を比較すると次の事が分かる．以上の処理により重複するルールが幾つか生じるため， 1. α近似の方が常にノイズ率が低く，β近似より 5%∼60%程度抑える事ができた重複したルールは 1 つにまとめた．その結果，ルール数は 454 個になった．実験ではこの 454 個のルールの 2. ファイルサイズ半分以下でもα近似で約 4%，β 中からランダムに選択した 100 個のルールを使用する．近似で約 16%程度のノイズに抑えられているが， (2) サンプルトラヒックファイルサイズ 1/5 前後でノイズ率が急激に増加サンプルパケットとして MAWI[9] で公開されているしているトラヒックアーカイブの中から samplepoint-B の 2003 1 の結果よりα近似はノイズ量の抑制に有効な方式で年 09 月 07 日のものを使用する．あると言える．また，2 の結果から近似無しの場合に必要なメモリの 1/5 程度のメモリを用意するとノイズ 6.3 実験項目をあまり増加させずにコストを下げられると言える．実験 1 コンパイル時間の測定この実験では，近似無し・α近似・β近似の 3 つの場合について，コンパイル時の処理速度を比較する．計 8 おわりに本稿では選択近似機能を有する空間分割型パケット測する処理時間はコンパイル処理全体の時間と、各ステップにおける時間である．6.1.3 節で述べたように，分類器を提案した．実験により，16 バイトのフィール分類表の大きさがキャプチャシステムに要求されるメドをキーとして使用するフィルタを 100 個用いる場合モリ量となり，近似する量を多くしていくと分類表はでも，使用メモリ量を 1/5 程度に抑えて高速なパケッ小さくなっていく．この実験により近似がコンパイルトキャプチャシステムを実現可能である事を確認した．時間に与える影響を明らかにする．結果は図 6∼7 の今後の課題として，キャプチャ条件の動的変更への対応とノイズ量をより低減する近似手法の研究，データようになった． . &('*),+ ')(+* 構造の最適化の実現が挙げられる． . , &.' & ' / .. $%. #. . $. !". . "#. .

(12). 参考文献. 1) Anthony J., McAuley, Paul Francis, ”Fast Routing Table Lookup Using CAMs”, IEEE INFOCOM 93 2) V.Srinvasan, S.Suri, G.Varghese, ”Packet Classification using Tuple Space Search”, SIGCOMM99, October 1999 3) Pantaj Gupta and Nick McKeown ”Packet Classification on Multiple Fields” RFC - Recursive flow classification ACM SIGCOMM’98 4) T.V. Lakshman, D. Stiliadis. ”High-Speed Policy-Based Packet Forwarding Using Efficient Multi-dimensional Range Matching”, In Proceedings of ACM SIGCOMM’98, pages 203-214. 5) 高橋直久, ”フィルタ sieve 関数の部分計算に基づく実時間パケット分類器”, 日本ソフトウェア科学会インターネット技術ワークショップ WIT 99, pp.190-197, 1999 6) N. Takahashi, ”A Systolic Sieve Array for Real-time Packet Classification”, Journal of IPSJ, Vol42, No.2., February 2001. 7) 加藤和夫，大須賀怜，高木淳史，片山善章，高橋直久, ”スケーラブルパケットキャプチャシステムの実現”, WIT2003 8) Sourcefire, INC. ”The Open Source Network Intrusion Detection System” http://www.snort.org/ 9) WIDE Project, ”MAWI Working group Traffic Archive” http://tracer.csl.sony.co.jp/mawi/. !. . (+*. . . . . %&. 0 1 3 5.6 8; @ 2 4 79 :=<?>A . . .

(13). . .2 59 7; :=< -/ 02 3+46 >@? 1 8. 図 6: コンパイル時間図 7: 近似処理時間実験 2 ノイズの影響この実験では，α近似・β 近似により生じる誤差領 &('*),+

(14) - &.' 域によって余分にキャプ / &.' %. チャされるパケット (ノイ # $ ズ) の割合と分類表の大 !" きさとの関係について考察し，ノイズ量を抑える事とメモリ容量を減少させる事のトレードオフに 5. 687; <>=@?B 02 1 3 9 A 4 : ついて考察する．ノイズ量を示す値として”ノイズ図 8: ノイズ率率”を次のように定義する．ノイズの数ノイズ率 = 破棄すべきパケットの数 × 100[%] 結果は図 8 のようになった．. 7. 実験結果の考察. 実験 1 コンパイル時間の測定図 6 よりコンパイル全体の処理時間を比較すると次. 6E −96−.

(15)