main-pub.dvi

高速ネットワーク向け

ネットワークモニタ回路の設計と実装

桐

村

昌

行

†

高

本

佳

史

††

森

亮

憲

†

安

本

慶

一

†††

中

田

明

夫

††

東

野

輝

夫

†† インターネットや高速ネットワークの発展に伴い，ネットワークを流れる大量のトラフィックをリ アルタイムで監視するネットワークモニタの必要性が高まってきている．ネットワークモニタに対し ては監視項目の追加・変更に柔軟に対応することが要求される．本論文では，柔軟性を持ちかつ，高 速ネットワークに対応するために，FPGA （Field Programmable Gate Arrays）を用いてネットワーク モニタを実装することを考える．そこで，ネットワークモニタを設計，実装するための手法，および

自動合成可能なネットワークモニタの仕様記述法を提案する．仕様は並行同期EFSM モデルで記述す

る．提案手法で合成される回路は監視項目などに基づいてパイプライン処理や並列処理を行うが，設 計者はこれらの処理の詳細を指定する必要がない．FPGA 回路を自動合成するツールを開発し，合成 される回路の速度や大きさについて評価した．

Design and Implementation of Network Monitoring Circuits

for High Speed Networks

M

ASAYUKI

K

IRIMURA

,

†

Y

_OSHIFUMI

T

_AKAMOTO

,

††

T

_AKANORI

M

_ORI

,

†

K

EIICHI

Y

ASUMOTO

,

†††

A

_KIO

N

_AKATA††

and T

_ERUO

H

_IGASHINO††

Due to the recent progress of the Internet, we need high-speed network monitors which can observe mil-lions of packets per second. We need to modify monitoring facilities and their capacities depending on mon-itoring items and network speed. In this paper, we propose (1) a methodology for designing and implement-ing such network monitors flexibly and (2) a high-level synthesis technique which automatically synthesizes FPGA circuits from specifications of network monitors in a model called concurrent synchronous EFSMs. The proposed technique makes it possible to synthesize an FPGA circuit suitable for given monitoring items and parameters where the designer need not consider about how pipe-line processing and parallel processing should be adopted. We have developed a tool to automatically derive FPGA circuits and evaluated the speed and size of derived circuits.

1. ま え が き

近年，インターネットが急速に発展，普及してきて

いる．これに伴い,サービス妨害（DoS : Denial of

Ser-vice）攻撃やフラッディング（flooding）などの悪意の

ある行為が増加してきており，このような行為の防止

およびホストの防御が重要になってきている1)∼3)．こ

のことから，ネットワークに対する攻撃を検出するた

† 大阪大学大学院基礎工学研究科

Graduate School of Engineering Science, Osaka University †† 大阪大学大学院情報科学研究科

Graduate School of Information Science and Technology, Osaka University

††† 奈良先端科学技術大学院大学情報科学研究科

Graduate School of Information Science, Nara Institute of Science and Technology めのさまざまなシステムおよびソフトウェアが提案さ れている4)∼6)．文献4)では，FDDIネットワークに対 するリアルタイムネットワークモニタが提案されてい る．文献5)および6)では，分散DoS攻撃を防止する 手法が提案されている． 近年，ネットワークやホストに対する攻撃を検出す るツールとしてネットワークモニタが注目されてい る．攻撃を検出する方法としてネットワークを流れた パケットのログをすべてディスクなどに記録したあと で解析する方法がある17)．この方式は，モニタ対象と するネットワークの規模によっては大量のデータを記 憶するための記憶装置が必要となる．また，リアルタ イムで攻撃の検出ができないなどの欠点がある． また，ネットワークモニタは，検出項目の頻繁な追 加・変更が行われるため，ソフトウェアとして実装さ 1

れることが多い．SNORTなどソフトウェアとして実 現されたネットワークモニタは，プロトコルやIPア ドレス，ポート番号などをパラメタとした規則群を与 え，規則に一致した場合に指定した動作を実行する． 本論文では，インターネットバックボーンのような高 速ネットワークに対応するためのネットワークモニタ を実現することを考えている．ソフトウェアで実現さ れたネットワークモニタでは，規則が複雑になるにつ れて，100Mbpsのトラフィックでもパケットの取りこ ぼしがあることが報告されている19)．また，文献20) では，パターンマッチングアルゴリズムを工夫するこ とで，Pentium II 450MHzのPCで，約500Mbps程度 のトラフィックからDoS攻撃の一つであるsmurfを検 出するネットワークモニタが実現されている．最新の CPUを用いることで，1∼2Gbps程度のトラフィック を扱えるネットワークモニタを実現することは可能だ と考えられるが，10Gbpsを超える高速バックボーン で利用したい場合や，検出項目を追加したい場合には， ソフトウェアでの実現は困難であると考えられる． より高速なネットワークに対応するために，ネット ワークモニタをハードウェアで実装する手法が提案 されている8),9)．しかし，ハードウェアでネットワー クモニタを実装すると検出項目の追加・変更に対応す ることが難しくなる．これを解決する一つの手法とし

て，ネットワークモニタをFPGA（Field Programmable

Gate Arrays）などの再構成可能なハードウェア回路で 実装することが考えられる．

本論文では，並行プロセスをモデル化するための 並行同期EFSM（Extended Finite State Machine）10),11) を使い，ネットワークモニタの設計，実装手法，お よびネットワークモニタの仕様（並行同期EFSM）か らFPGA回路を自動合成する手法を提案する．提案 手法では検出項目ごとに対応するモジュールを並行同 期EFSMで記述する．各モジュールに対する並行同期 EFSMをあらかじめ作成し，ライブラリに登録してお く．これにより，ネットワークモニタの設計者は，ラ イブラリに登録されている各モジュールを組合せるこ とでネットワークモニタを設計することができる．ま た，提案手法で合成されるFPGA回路は，高速に動作 するようにパイプライン処理や並行処理が自動的に適 用される．この際，設計者は並行モジュール間のパイ プライン処理の詳細を指定する必要はない． 本論文では，IPフラッディング2)検出モジュール と，SYNフラッド2)検出モジュールの設計と実装に ついて述べる．どちらのモジュールも，ある特定のIP アドレスに対するパケット数が閾値を越えるかどうか を調べることで，フラッディングが発生しているかど うかを検出する．この閾値は検出対象の種類や通信路 の帯域幅，統計データ3),7),12)などに基づいて決定する． ライブラリでは，閾値はパラメータとして指定されて いる．提案手法では，指定したパラメータ値に基づい て，異なるFPGA回路を自動合成する． 上記のモジュールを並行同期EFSMで記述し，文献 10)，11)の手法を用いてハードウェア記述言語VHDL の記述に変換し，SYNOPSYS社13)の論理合成ツール

（FPGA Express）を用いてFPGA回路を合成した．そ

の結果，FPGA回路の面積，動作速度ともに実用上問 題ないことを確認した． 以降，2章ではシステム記述モデルと回路合成につ いて，3章では提案するネットワークモニタについて述 べる．また，4章で回路合成の結果について説明する．

2. システム記述モデルと回路合成

2.1 並行同期EFSM

並行同期EFSMは，複数のEFSMとEFSM間の同

期制御情報で構成される．各EFSMは有限個のレジス タ（変数）を持ち，各アクションでは，ゲートを介し て，入力値をレジスタに取り込んだり，外部に値を出 力することができる．また，各アクションの実行条件 として論理式（ガード式）を設定することができる． アクションは，g v[f]と記述する．ここで，gはゲー ト，vは入力変数?x : t（xは変数名，tは変数の型） と出力式!Eの列，fはガード式を表す． 並行同期EFSMでは，与えられたEFSMの任意の部 分集合が，あるゲートに対する遷移を同時に実行する ことで，そのゲートを介してデータを交換することが できる．これをマルチランデブ14)と呼ぶ．LOTOS14) で用いられる並列オペレータを利用して以下のように 並行同期EFSMを記述する． S::= S|[gate list]|S | S|||S | M

ここで，MはEFSMの名前であり，gate listには

EFSM間で同期させたいアクションに対するゲートの

リストを記述する．また，|||は，アクションを同期さ

せないことを表す（gate list= ∅に相当）．また，一

対のEFSM間での同期だけでなく，E1|[a]|(E2|[a]|E3)

のように一対多や多対多の同期も記述することができ る．これは，データの一斉配布や排他制御などを記述 するときに有用である．

図1の並行同期EFSM E1|[a, b]|(E2|[a]|E3)では，

ゲートaに対するアクションがE1, E2, E3すべての

EFSM間で同時に実行される．例えば，E1, E2, E3で

s0 s1 s2 a!0 b!0 a!1 b!0 E1 s0 s1 b?x[x>=0] a?x a!f(x) E2 s0 s1 E3 a?y b?z a?y 図 1 並行同期 EFSM の例（E1|[a, b]|(E2|[a]|E3)）

Fig. 1 An example of concurrent synchronous EFSMs

値0が入力変数x, yに代入される．このとき，出力 値0と変数x, yの型が一致していなければならない． また，E1がa!1，E3 がa?yを実行し，E2がa!f(x) を実行する場合，f(x)の値は1でなければならない． 複数のマルチランデブが競合する場合は，いずれか 一つが選択される．図1の並行同期EFSMにおいて， E₁ がb!0を実行する場合，E₂のb?x[x ≥ 0]または E3のb?zのいずれか一方と同期実行される． 2.2 回路合成手法 我々は文献10)，11)において，並行同期EFSM群 として記述されたシステムの動作仕様をレジスタ転送 レベルVHDL記述へと変換する方法およびツールを 提案している．以下では，変換手法の概要について説 明する． 2.2.1 マルチランデブ制御のための情報 一般に並行同期EFSMでは,動的に同期アクション の組合せを決定し，ガード式が満たされるかを判定す る必要がある．このような動的計算はパフォーマンス を低下させる．そこで,（1）同期実行されるアクショ ンの組と関係するEFSM名の組，（2）（1）の組に対す るガード式，に関する情報をあらかじめ求めておく． 図1に対する同期アクションの組は表1のようにな る．p1からp4はゲートaに対するアクション，p5と p6はゲートbに対するアクションを表している． 一般に，同期アクションの組は非常に多くなるので， 表2のように各EFSMの同一ゲートのアクションを 1つにまとめて（ランデブ情報と呼ぶ）よりコンパク トな表（マルチランデブ表と呼ぶ）として表す．ここ では省略するが，並行同期EFSMからマルチランデ ブ表を自動的に生成することができる10)． 2.2.2 導出される回路のアーキテクチャ 与えられた並行同期EFSM群から，各EFSMに対 応する順序回路と，2.2.1節の情報に基づくマルチラン デブ制御部で構成される回路を生成する．我々が文献 10)，11)で提案している回路合成手法では，各EFSM に対応する順序回路とマルチランデブ制御部で構成さ れる回路を生成する． 表 1 図 1 に対する同期アクションの組 Table 1 Tuples of synchronized actions for Fig.1

E1 E2 E3

p1 (a!0, a?x a?y)

p2 (a!0, a!f(x) a?y)

p3 (a!1, a?x a?y)

p4 (a!1, a!f(x) a?y)

p5 (b!0 b?x[x ≥ 0]) p6 (b!0 b?z) 2.2.2.1 EFSMに対する順序回路 図1の仕様に対して図2のような回路が生成される． 各EFSMに対する順序回路は，状態を保持するレジス タ（E1, E2, E3）を持つ．また，各順序回路は同じク ロックを参照して動作する．EFSMは各クロックごと に，現状態から実行可能なアクションのうち一つを実 行し，次の状態に遷移する．一方，実行可能なアクショ ンが存在しないときには現状態で待機する．EFSM中 で用いられている各変数は，レジスタとして実現され， 変数への代入を行うアクションの実行によって，各レ ジスタの値は更新される． 2.2.2.2 マルチランデブ制御部 マルチランデブ制御部は，同期判定部と競合回避部 で構成される． 同期判定部では，各クロックごとに実行可能な同期 アクションの組を判定する．同期判定部では，ランデ ブ情報ごとに同期判定回路を設ける（図2のR1から R₄）．同期アクションは，その同期に関わるすべての アクションが実行可能であるときに実行することがで きるのでn入力のAND回路で実現する．ここで，n は同期を行うEFSMの個数である． 図1と表2に対する同期判定部は図3のようにな る．E1のイベントa!1が実行可能になるとE1の順序 回路から信号aj,1 okが1になり各Rj（j= 1 . . . 4） に送られる．同様にE2のa?x, E3のa?yが実行可能 になると信号aj,2 ok，aj.3 okが1になりRjへ送ら れる．Rjへの入力がすべて1になれば，ゲートaに 対するアクションの実行許可信号a_j okを各EFSMに 送る．信号を受け取ったEFSMはゲートaに対する アクションを実行する． 競合回避部は，競合する複数の同期アクションの組 が同時に実行可能となったときに，いずれか一つを選 択する回路である．選択の方法はいくつか考えられる が，ここでは簡単のために，あらかじめ設定した優先 度に従って選択を行うものとする． 図1では表2より，ゲートbに対する同期アクショ ンの組合せとしてr3とr4がある．例えば, r3がr4よ りも優先度が高い場合，競合回避部は図2の破線内の

表 2 図 1 に対するマルチランデブ表 Table 2 Rendezvous table for Fig.1

E1 E2 E3

r1 ({a!0}, {a?x,a!f(x)}, {a?y})

r2 ({a!1}, {a?x,a!f(x)}, {a?y})

r3 ({b!0}, {b?x[x ≥ 0]}) r4 ({b!0}, {b?z}) ようになる． 同期アクションの実行可能性判定に，他のEFSMの 出力値が必要な場合（ガード式の判定など）がある． そこで，各同期アクションの組に属するEFSM間に データ転送パスを設置する．データ転送パスは，複数 の同期アクション組で同時に利用される可能性がある ので，ランデブ情報ごとに設置する．なお，ランデブ 情報をグループ化し，パスを共用させることでパスの 効率化を計ることができる．マルチランデブ制御部の 詳細については文献11)参照．

3. 提案するネットワークモニタ

本論文では，以下のような手順でネットワークモニ タを開発する． ( 1 ) ネットワークモニタを構成する各モジュールを 並行同期EFSMで記述する． ( 2 ) 検出項目およびフラッディング検出時のアドレ スの分割数やカウンタの閾値などのパラメタ値 を与え，目的とするネットワークモニタの仕様 を導出する． ( 3 ) 文献文献10)，11)の手法を用いて，並行同期 EFSMからVHDL記述を生成する．

( 4 ) SYNOPSYS社13)の論理合成ツール（FPGA

Ex-press）を用いて，VHDL記述からFPGA回路 を合成する．

本論文で対象とするネットワークモニタはヘッダ情

報取得モジュール（Header Information Capturing

Mod-ule）と，ネットワークモニタモジュール（Network Monitoring Module）で構成され，ヘッダ情報取得モ ジュールは既存のモジュール8),9)を使うと仮定する． ヘッダ情報取得モジュールでは，「送信元IPアドレス」， 「送信先IPアドレス」，「パケットの種類」などを表す ビット列が得られる． 提案手法では構成される回路の規模を小さくし，ク ロック周波数を大きくするため，FPGAに格納できる レジスタのみを使用して，外部メモリを使用しない構 成法を考える． E1 E2 E3 R1 R2 R3 R4 Data Path Priority Encoder (R3>R4) Executability Checking Part Conflict Avoidance Part Rendezvous Enabled Data Path Event Enabled r1 r2 r3 r4 not for r1 and r2 for r4 for r3 図 2 生成される回路の構成 Fig. 2 Architecture of the derived circuit 3.1 IPフラッディング検出モジュール 3.1.1 IPフラッディング検出モジュールの構成 IPフラッディング検出モジュールの構成を図4に示 す．図中の矢印はマルチランデブによるデータの受渡 しを表す．括弧内は，マルチランデブのゲート名およ び渡されるデータ名を表す．この回路への入力はヘッ ダ情報取得モジュールで得られたヘッダ情報である． まずGET PACKETモジュールがヘッダ情報から そのパケットの送信元（送信先）IP アドレスを取 得する．FILTERINGモジュールでは，すでにフラッ ディングを起こしていると判定された一定個数のIP アドレスを保持しておき，保持しているアドレスと 同じアドレスを持つパケットを検出候補から外す．

GET PACKETモジュールとFILTERINGモジュール に対するEFSMを図5に示す．GET PACKETモジュー ルは，ヘッダ情報取得モジュールからパケットのヘッ ダ情報headerを受け取り，それに含まれるアドレス 情報(Address(header))を送出する動作を繰り返す．

一方，FILTERINGモジュールは受け取ったアドレス

情報addrをCheck(addr, table0)で判定し，既に保 持しているアドレスであればその情報を無視し，ま だ保持していないアドレスであれば，IP COUNTER モジュールにその情報を渡す．ここで，Address()や Check()などの関数は，プリミティブとして使用でき るものと仮定している．実際の回路合成時には，これ らの関数を組み合わせ回路として実現するVHDL記 述を与える必要がある． IP COUNTER モ ジュー ル で は ，FILTERING モ ジュールを通過した32ビットのIPアドレスをいく つかのビット列（パーティション）に分割し，それぞ れのビット列ごとにフラッディングしているビットパ ターンを並列処理によって特定する．ここで，各パー ティションが含むビット数をパーティションサイズと

E1

E2

E3

AND Gate

j

j,1

a _ok

j,2

a _ok

j,3

a _ok

a _ok

j

R

図 3 同期判定回路 Fig. 3 Synchronization checking circuit

呼ぶ．パーティションサイズを4にした場合，パーティ ション数は8（= 32 ÷ 4）となり，各パーティション のビットパターンは16（= 24）種類となる．各パー ティションに対して，ビットパターンと同数のカウン タを用意し，各ビットパターンごとにパケット数を数 える．ある一定時間にカウンタの値が閾値を越えると， 対応するIPアドレスがフラッディングを起こしてい るIPアドレスの一部であると判断する．すべてのパー ティションに対してそのパーティションに対するビッ トパターンが特定されるまで同じ処理を繰り返す．こ のようにして，フラッディングを起こしているIPア ドレスを検出する．上記の処理で検出されたIPアド レスはFLOODING TABLEモジュールに記録してお く．検出したIPアドレスをFILTERINGモジュールに 送り，そのIPアドレスをフィルタリングする． 3.1.1.1 IP COUNTERモジュール IP COUNTERモジュールの詳細を図6に示す．図6 ではパーティションサイズが4であるので，8個のビッ トカウンタ（BitCounter0–BitCounter7）と8個のビッ トテーブル（BitTable0–BitTable7）でモジュールが構 成されている．まず，最上位の4ビットを担当してい るBitCounter0が，ある一定時間，ビットパターンごと に出現した数を数える．出現数が最初に閾値を越えた ビットパターンをフラッディングを引き起こしている IPアドレスの一部であると判定し，BitTable0に保存 する．この閾値はネットワークモニタが監視するネッ トワークの環境に依存する．また，与えられた閾値を 越えるビットパターンが出現しない場合，フラッディ ングが発生していないと判断し，BitCounter0をリセッ

トする．次にBitCounter1が，上位4bitがBitTable0

の値に一致したアドレスに対して，BitCounter0と同 様の処理を行う．IP COUNTERモジュールは以上の 処理を順にBitCouter7まで行なう．このように上位か ら順番に4bitずつアドレスを特定することによって， 最終的にフラッディングしているアドレスを特定する． BitCounterとBitTableを図6のように配置することに GET_PACKET FILTERING (PacketData, addr) IP_COUNTER FLOODING_TABLE DISPLAY_DEVICE (IpFilterdData, addr) (FloodIpData, addr) (ResultData, table0) : Data Flow : Hardware Module 図 4 IP フラッディング検出モジュール Fig. 4 IP flooding detection module

より，パイプライン処理を行うことができる． 3.1.1.2 BitCounterモジュール BitCounterは図7のような構成をしている．パー ティションサイズが4である場合，各BitCounterに は0000から1111の24 種類のビットパターンが入 力される．そこで，各ビットパターンを担当する24 個のPtCounterを用意する．PtCounterは，入力され たビットパターンが自分の担当するビットパターンと 一致すればカウンタの値を1増やす．この処理をあ る一定時間繰返し，閾値に一番最初に到達したビット パターンをBitCounterの出力とする．PtCounterに 対するEFSMを図8に示す．EFSMでは受け取った IPアドレスaddrから指定したパーティションのビッ ト列(パーティション長および何番目のパーティショ ンかを psize, pnumで指定) を取り出し，担当ビッ トパターンpatternと一致するかどうかを判定する

(BitSeq(addr, psize, pnum) = pattern)．一致すれ

ば，カウンタCounterの値を増やす．その後，条件

式Count < T hresholdおよびCount≥ T hreshold

で閾値を越えたかどうかの判定を行う．ここで，関数 BitSeq()は組み合わせ回路として利用できることを 仮定している． 3.2 SYNフラッド検出モジュール SYNフラッドは2端末間のTCPベース通信におい てSYN+ACKパケットに対応するACKパケットが返 信されないことに起因して生じる．そこで，SYNフ ラッド検出モジュールは，SYN+ACKパケットに対応 するACKパケットの有無を監視し，対応するACKパ ケットが返ってこない場合，SYNフラッドが起こって いるとみなし，被害を受けているホストのIPアドレ

GET_PACKET FILTERING GetPacket?header PacketData!Address(header) PacketData?addr IgnorePacket [Check(adr, table0)=TRUE] IpFilteredData!addr [Check(addr, table0)=FALSE]

図 5 GET PACKET と FILTERING に対する EFSM Fig. 5 EFSMs for GET PACKET and FILTERRING

スを特定する．本検出モジュールでは, IPアドレスの 32ビットのうち環境に応じて特定のビット列のみを監 視して,そのビットパターンを特定する．例えば，ド メインの特定などを目的にする場合，上位8ビットを 監視することなどが考えられる． 3.2.1 SYNフラッド検出モジュールの構成 SYNフラッド検出回路の構成を図9に示す．先に述 べたIPフラッディング検出モジュールと同様，ヘッダ情 報取得モジュールの出力からGET PACKETモジュー ルが必要なヘッダ情報を抽出する．ここで抽出する情 報は，送信元IPアドレス，送信先IPアドレスとTCP ヘッダ制御用フラグビット列である．フラグビット列 は6ビットで構成され，パケットの種類を表している． この6ビットのなかにSYN，ACKに対応するビット

があり，ビットの組（SYN, ACK）が（1, 0）ならSYN

パケット，（1, 1）ならSYN+ACKパケット，（0, 1）な

らACKパケットであることを表している．

3.2.1.1 FILTERINGモジュール

FILTERINGモジュールは，GET PACKETモジュー

ルによって抽出されたビット列のうち（SYN, ACK） ビット組を調べ，SYN+ACKパケットとACKパケッ トのみを抽出する．さらに，FILTERINGモジュール は，SYNフラッドで攻撃されているホストのIPアド レスを検出するために，パケットがSYN+ACKパケッ トならば送信先アドレスを，ACKパケットなら送信 元アドレスを抽出する．例えば，攻撃されているホス トのIPアドレスのうち4ビットを検出するのであれ ば，24個のSYN COUNTERを準備し各カウンタが対 応するビット列の数を数えればよい． 3.2.1.2 SYN COUNTERモジュール 図10はSYN COUNTERの構成を表している．ま ず，PT CHECKERモジュールがヘッダ情報から必要な ビット列を抽出し，担当しているビット列であるかどう かを判定する．担当ビット列であれば，PT CHECKER はSA CHECKERにビット列を渡す．SA CHECKER

は，ビット組（SYN, ACK）からSYN+ACKパケット

かACKパケットかを調べる．SYN+ACKパケットな

ら変数MEMの値を1増やす．また，ACKパケット

BitCounter0 : Data Flow

: Hardware Module : Memory BitTable0 BitTable1 BitCounter1 BitCounter7 ... FLOODING_TABLE ...

From FILTERING Module

図 6 IP COUNTER モジュール Fig. 6 IP COUNTER module

ならMEMの値を1減らす．これにより，MEMは，

SYN+ACKパケットの数とACKパケットの数の差を

保持する．SYNフラッドが発生した場合，ACKパケッ

トが返信されないのでMEMの値が増加する．そこで，

MEM CHECKERモジュールはMEMの値が閾値を越 えるかどうかを調べる．この閾値は環境に依存する．

閾値を越えた場合，対応するビット列を含むIPアド

レスに対して攻撃が行なわれていると判定する．判定 後，MEM CHECKERはDISPLAY DEVICEにビット

パターンを送り，MEMをリセットする．

4. 評

価

並行同期EFSMの仕様から，EFSMとマルチラン デブ表で構成される中間プログラムを導出するツール と，中間プログラムからVHDL記述を生成するツー ルを実装した10),11)．VHDL記述は，市販の論理合成

ツール（SYNOPSYS社のFPGA Expressなど）を用

いてFPGA回路に変換することができる． 4.1 回路合成の結果 前述のフラッディング検出モジュール（IP-FLOOD） とSYNフラッド検出モジュール（SYN-FLOOD）を論 理合成した．どちらのモジュールについてもパーティ ションサイズは4とした．また，論理合成を行なう際，

FPGAチップセットとしてALTERA社のFLEX10K

シリーズを指定した．合成した結果，表3のように なった． IP-FLOODの論理合成にかかった時間は約17分で， 得られた回路のゲート数は約14,000，クロック周波数 は約12.5MHzであった．また，SYN-FLOODの論理 合成にかかった時間は約2分で，回路のゲート数は約 3,300，クロック周波数は約12.5MHzであった． 4.2 SYNフラッド検出モジュールに対する考察 SYN-FLOODにおいて抽出するビット数に対する回 路面積とクロック周波数の変化を表4に示す．抽出す

: Data Flow : Hardware Module

To BitTable or

FLOODING_TABLE Device From FILTERING Module 0000

PtCounter 0001PtCounter ... 1111PtCounter

図 7 BitCounter モジュール Fig. 7 BitCounter module

るビット数が一つ増えるたびにカウンタ数が2倍にな

るので，回路面積が2倍程度に増加している．一方，

カウンタの演算はすべて並列に処理しているため，ク ロック周波数はそれほど低下していない．

クロック周波数が低下しているのはマルチランデ

ブ制御部で制御するEFSM（SYN COUNTER）の数

が増加しているためと考えられる．SYN-FLOODで は図 11(a)のようにFILTERING モジュールがすべ てのSYN COUNTERと同期をとることでパケット 情報を送信している．fan-outの制限から，同期する SYN COUNTERの数が増加すると，一度にすべての SYN COUNTERにデータを転送できない．そこで，論 理合成ツールが自動でfan-outの制限を満たすように 中継用の論理ゲートを挿入し，1クロックで処理しよ うとするため，FILTERINGモジュールのクロック周 波数が低下してしまう． そこで図11(b)のように同期データ転送を2段（2ク ロック）に分割し，FILTERINGモジュールはfan-out 制限を満たす範囲で中継用のダミーモジュールDに1 クロック目でデータ転送を行い，各ダミーモジュール Dが2クロック目でSYN COUNTERにデータ転送を 行うようにすることで，クロック周波数の低下を防ぐ ことができる．このように変更した回路の回路面積と クロック周波数を表5に示す．項目Stepsは図11にお ける段数，Dummiesはダミーモジュールの数，つまり FILTERINGモジュールが直接同期するモジュールの数 を指す．また, Branchesは各ダミーモジュール（1段の

場合はFILTERINGモジュール）からSYN COUNTER への分岐，つまり同期すべきカウンタの数を表してい る．回路面積は，段数の増加，ダミーモジュールの数 に応じて若干増加している．また，ダミーモジュール を追加し，2段で処理を行なうと1段で処理するより もクロック周波数が1∼3MHz向上している． 4.3 IPフラッディング検出モジュールの処理能力 各モジュールが1秒間にどれくらいのパケットを処 理できるかを考察する．今回作成したIPフラッディン グ検出モジュールでのパケットの流れと各サブモジュー IpFilteredData ?addr IgnorePacket

[BitSeq(addr, psize, pnum)!=pattern] Count:=Count+1

[BitSeq(addr, psize, pnum)=pattern]

IgnoreCount [Count<Threshold] CheckedData!addr [Count>=Threshold]

図 8 BitCounter に対する EFSM Fig. 8 EFSM for BitCounter

ル（EFSM）の関係を図12に示す．各サブモジュール は左側の実線で囲んだものであり，右側はEFSMを表 す．EFSM間の点線で囲んだものは転送するデータを 表し，Pctはパケット情報，Cntはカウンタ情報，Ptn はビットパターンを表すビット列，Reqは外部からの リクエスト信号，TblはフラッディングIPアドレスの 集合を表す．図12より，それぞれのサブモジュール で一連の処理を行うアクション系列は高々3アクショ ンで構成されている．各サブモジュールはそのアク ション系列を実行したあと初期状態に戻る．各サブモ ジュールは独立に動作しており，パイプライン処理が 可能である．原則1つのアクションを実行するために 必要なクロック数は1である．よってクロック周波数 が12.45MHzで，アクション数が最大3なので，毎秒 約415万パケット（12.45（MHz）÷ 3）を処理する ことができる．ただし，実際にはパケット分割処理や， カウント処理などにおいて付加的な作業が追加される 場合もある．しかし，アクション系列が10アクショ ンで構成されていても，毎秒100万パケット以上を処 理することができる． 4.4 ネットワーク環境に対応した閾値の決定 IPフラッディング検出モジュールもSYNフラッド 検出モジュールも取得したIPアドレスを分割し，各々 のカウンタモジュールに渡してカウント処理を行って いる．カウンタモジュールは担当するビットパターン の出現数がある閾値を越えた段階でフラッディングと みなす． ここでは，毎秒100万パケットが流れるような環境 を考える．このような環境では，毎秒1000パケット増 加するといった小規模なフラッディングは，IPフラッ ディングとして扱わない．一方，トラフィックの5%か ら10%程度（毎秒5万から10万パケット）のフラッ ディングが発生すれば，ネットワークが混雑し障害の

表 5 5bit 抽出での段数と分岐数による評価

Table 5 Evaluation depending on the numbers of vertical steps and branches when using 5 bit partition Name Steps Dummies Branches Area(gates) Clocks(MHz) SYN0-64 1 0 64 7062 11.51 SYN2-32 2 2 32 7171 12.45 SYN4-16 2 4 16 7410 14.90 : Data Flow : Hardware Module 0000 SYN_COUNTER GET_PACKET FILTERING 0001 SYN_COUNTER ... 1111SYN_COUNTER DISPLAY_DEVICE 図 9 SYN フラッド検出回路 Fig. 9 SYN flood detection module

原因となる．ここでは，このような量のIPフラッディ ングを検出することを考える． あるIPアドレスに対して毎秒10万パケットのフラッ ディングパケットが送られるとする．パーティション サイズを4とし，8個のIP COUNTERモジュールを 使うとすると，それぞれのIP COUNTERに毎秒約6.3 万（100万÷ 16）のパケットが入力される．パケット が持つIPアドレスには偏りがあると考えられる．い ま，IPアドレスのビットパターンに最大で50%の変動 があると仮定すると，各IP COUNTERには毎秒3.1 万∼9.5万（6.3万± 50%）のパケットが入力される． このとき，IP COUNTER中の各BitCounterの閾値を 毎秒9.8万に設定する．このようにすると，ある特定 のIPアドレスに対するパケットが毎秒10万パケット を越えた場合，そのIPアドレスのパケット総数は，IP アドレスのビットパターンの偏りに関わらず毎秒9.8 万を越える．このことから，パーティションサイズが 4の8個のIP COUNTERでこのIPフラッディングを 検出することができる． なお，同じモジュールで毎秒6000パケットのフラッ ディングを検出したい場合，パーティションサイズが4 のIP COUNTERモジュールでは各カウンタに最低で も毎秒3.1万以上のパケットが入力されるのでこの構成 では適当な閾値を設定できない．そこで，パーティショ ンサイズを8とし，4個のIP COUNTERを利用すると， 1個のIP COUNTERあたり毎秒入力されるパケット数 は，3,906（100万÷ 256）となり，ビットパターンに 50%の偏りがあったとしても，3906+50%=5940となり，

PT_CHECKER _{: Data Flow}

: Hardware Module : Memory

MEM

To DISPLAY_DEVICE From FILTERING Module

SA_CHECKER

MEM_CHECKER

図 10 SYN カウンタ Fig. 10 SYN COUNTER

6000を越えないので，閾値を6000程度に設定すると， ビットパターンの偏りに関わらずIPフラッディングを検 出することができる．ただしこの場合，IP COUNTER 中のBitCounterの総数は256 × 4 = 1024個となり， 回路サイズがBitCounterの総数に応じて増大する． 監視を行ないたいネットワークに対して，Nを1秒 間に流れるパケット数，DをIPアドレスのビットパ ターンの偏り，F を検出したい1秒あたりのパケッ ト数とする．N, D, F から自動的にパーティションサ イズとIP COUNTERの数を決めることができる．ま た，パーティションサイズとIP COUNTERの数から， IP COUNTERモジュールに対するFPGA回路を導出 することができる．一方，文献3)ではインターネッ トバックボーンを流れるSYN+ACK,ACKパケットの 量は最大で5%程度であると述べられている．このこ とから，SYN-FLOODモジュールは我々のツールを用 いることで自動的に作成することができる．

5. 考

察

ネットワークモニタをソフトウェアで実現した場合， 数百Mbpsのネットワークに適用できる19),20)．本論 文では，バックボーンなど10Gbps程度の高速ネット ワークを流れるパケットをリアルタイムに監視するこ とを目標としている．文献[15]から平均のパケットサ イズは400byte程度であるので，約毎秒300万パケッ トを処理できる性能がネットワークモニタに必要とな る．提案手法で合成したIPフラッディングモジュー ル，SYNフラッドモジュールは，ともに12.45MHzで

表 3 各検出回路の論理合成結果 Table 3 Results for two modules

回路名 IP-FLOOD SYN-FLOOD EFSM の数 156 67 論理合成時間(sec) 1048 123 クロック周波数(MHz) 12.45 12.45 回路ゲート数(gate) 14181 3392 ラッチ数 15169 482 FF 数 385 328 動作し，処理のステップ数も3であるので，毎秒約 415万パケットを処理することができ，目標性能を満 たしている．さらに，動作速度を向上させる方法とし て，一度に多くのモジュール間でデータの受渡しが行 われる部分にダミーモジュールを挟むことによって， FPGA回路が動作するクロック周波数を向上させるこ とができる． Snortなどソフトウェアで実現されたネットワーク モニタの場合，規則を追加することにより，様々な項 目を検出することがでる．提案手法では，各項目に対 する規則を1つのEFSMとして記述し，他の項目を 検出するEFSMと並列動作させることで，様々な項目 を同時に検出することができる． 例えば，Land攻撃に対するSnortの規則は以下のよ うになる．

alert tcp $EXTERNAL_NET any -> $HOME_NET any

(msg:"DOS Land attack"; id:3868; seq: 3868; flags:S; reference:cve,CVE-1999-0016;

classtype:attempted-dos; sid:269; rev:2;)

上記の規則では，プロトコルがtcpでSYNフラグが1

になっており，かつパケットの送信元IPアドレス

EX-TERNAL NETおよび送信先IPアドレスHOME NET を比較し，等しければメッセージを出力するという

動作が記述されている．提案手法では，3章で述べた

GET PACKETモジュールからSYNフラグおよびIP アドレスをマルチランデブにより受け取り，比較した 結果が等しければ報告するようなEFSMを記述する ことで，この規則を実現することができる． Snortなどのソフトウェアベースのネットワークモ ニタでは，規則の数が増加すると，各パケットにそれ らの規則を順番に適用するため，扱うことができる最 大トラフィックが減少することが予想される．一方， 提案手法では，各規則を並列に適用できるため，速度 低下を最小限に抑えることができる．

6. あ と が き

本論文では，ネットワークモニタのハードウェア化 表 4 bit 抽出数による評価 Table 4 Evaluations depending on the number of bits Name Bit EFSMs Area(gates) Clocks(MHz) SYN2 2 19 843 13.37 SYN3 3 35 1700 13.37 SYN4 4 67 3392 12.45 SYN5 5 131 7062 11.51 SYN6 6 259 14680 10.55 SYN7 7 515 30848 9.63 SYN8 8 1027 64598 8.67 について提案・実装を行った．SYNOPSYS社の論理合

成ツールFPGA Expressを用いて，FPGA回路の合成 を行い，回路の面積とその速度を計測した．その結果， 面積，速度ともに実用上問題ないことが確認できた． 提案手法では，ネットワークモニタが持つパラメータ （パーティションサイズ，閾値）に基づいて，自動的 に回路を合成する． 今後は，様々なモニタ項目に対応する基本モジュー ルを作成し，ネットワークモニタ作成の支援ツールと して利用できるようにする予定である．

参 考 文 献

1) A. S. Tanenbaum: “Computer Networks, Third Edition ”. Prentice-Hall Inc. (1996).

2) L. Garber: “Denial-of-Service Attacks Rip the In-ternet”, Proc. of IEEE Computer, pp. 12–17 (2000). 3) D. Moore, G. M. Voelker and S. Savage:

“Infer-ring Internet Denial-of-Service Activity”, USENIX Security Symposium (2001).

4) V. Paxson: “Bro: A System for Detecting Network Intruders in Real-Time”, Computer Networks, Vol. 31, No.23–24, pp. 2435-2463 (1999).

5) K. Park and H. Kee: “On the Effectiveness of Route-Based Packet Filtering for Distributed DoS Attack Prevention in Power-Law Internets”, Proc. of ACM SIGCOMM2001, pp. 15–26 (2001).

6) G. Mansfield et. al: “Towards Trapping Wily In-truders in the Large”, Computer Networks, Vol. 34, pp. 659–670 (2000).

7) K. Claffy, G. J. Miller and K. Thompson: “the na-ture of the beast: recent traffic measurements from an Internet backbone”, Proc. of INET’98 (1998), http://www.caida.org/outreach/papers/1998/ Inet98/ 8) 八木 哲,小倉 穀,川野 哲生,丸山 充,高橋 直久 : “メタモニタ：適応型ネットワークトラヒック 観測機構”,情報処理学会論文誌, Vol.41, No.2, pp. 444–451 (2000).

9) Z. D. Ditta, J. R. Cox Jr and G. M. Parulkar: “Design of the APIC: A High Performance ATM Host-Network Interface Chip”, Proc. of IEEE

INFO-: Dummy Module

FILTERING

D (a)One Step (b)Two Step

D

FILTERING

To SYN_COUNTER Modules To SYN_COUNTER Modules From GET_PACKET Modules From GET_PACKET Modules

...

D ... D

図 11 カウンタ処理の分散 Fig. 11 Distribution of IP counter processing COM’95, pp. 179–187 (1995).

10) K. Yasumoto, A. Kitajima, T. Higashino and K. Taniguchi: “Hardware Synthesis from Proto-col Specifications in LOTOS”, Proc. of Joint Intl. Conf. on 11th Formal Description Techniques and 18th Protocol Specification, Testing, and Verifica-tion (FORTE/PSTV’98), pp. 405–420 (1998). 11) H. Katagiri, K. Yasumoto, A. Kitajima, T.

Hi-gashino and K. Taniguchi: “Hardware Implementa-tion of CommunicaImplementa-tion Protocols Modeled by Con-current EFSMs with Multi-Way Synchronization”, 37th IEEE/ACM Design Automation Conference (DAC-2000), pp. 762–767 (2000).

12) J. Apisdorf, K. Claffy and K. Thompson: “OC3MON:Flexible, Affordable, High-Performance Statistics

Collec-tion”, Proc. of INET’97 (1997),

http://www.isoc.org/isoc/whatis/conferences/ inet/97/proceedings/F1/F1 2.HTM

13) SYNOPSYS Inc. http://www.synopsys.com/ 14) ISO : “Information Processing System, Open

Sys-tems Interconnection, LOTOS - A Formal Descrip-tion Technique Based on the Temporal Ordering of Observational Behavior”, ISO 8807 (1989). 15) WIDE Project: “Packet traces from WIDE

back-bone”,

http://tracer.csl.sony.co.jp/mawi/

16) R. Sekar and Y. Guang and S. Verma and T. Shanbhag: “A High-Performance Network Intrusion Detection System”, ACM Conference on Computer and Communications Security, pp. 8–17 (1999). 17) T. Kato, T. Ogishi, A. Idoue and K. Suzuki:

“De-sign of Protocol Monitor Emulating Behaviors of TCP/IP Protocols”, Proc. of IFIP 10th International Workshop on Testing of Communicating Systems (IWTCS’97), pp. 416–431 (1997).

18) Snort: http://www.snort.org/

19) M. Gokhale, D. Dubois, A. Dubois, M. Boorman, S. Poole and V. Hogsett: “Granidt: Towards Giga-bit Rate Network Intrusion Detection Technology”, Proc. of 12th International Conference on Field Programmable Logic and Applications (FPL2002), LNCS2438, pp. 393–403 (2002).

20) R. Sekar and Y. Guang and S. Verma and T.

Shanbhag: “A High-Performance Network Intrusion Detection System”, ACM Conference on Computer and Communications Security, pp. 8–17 (1999).

(平成?年?月?日受付) (平成?年?月?日採録) 桐村 昌行（正会員） 平成12年大阪大学基礎工学部情 報工学科卒業．平成14年同大学大 学院博士前期課程修了．現在，三菱 電機株式会社．在学中，実時間シス テムや分散システムの仕様記述・実 装に関する研究に従事． 高本 佳史 平成13年大阪大学基礎工学部情 報科学科卒業．現在，同大学大学院 博士前期課程在学中．実時間システ ムや分散システムの仕様記述・実装 に関する研究に従事． 森 亮憲（学生会員） 平成10年大阪大学基礎工学部情 報工学科卒業．平成12年同大学大 学院博士前期課程修了．現在，同大 学大学院博士後期課程在学中．通信 プロトコルの適合性試験，検証法な どの研究に従事． 安本 慶一（正会員） 平成3年大阪大学基礎工学部情報 工学科卒業．平成7年同大学大学院 博士後期課程退学後，滋賀大学経済 学部助手．現在，奈良先端科学技術 大学院大学助教授．工学博士．平成 9年モントリオール大学客員研究員．通信プロトコル や分散システムの形式仕様記述・実装法に関する研究 に従事．

中田 明夫（正会員） 平成4大阪大学基礎工学部情報工 学科卒業．平成9同大学大学院博士 後期課程了．現在，大阪大学大学院 情報科学研究科助教授．博士（工学）． 実時間システムや分散システムの仕 様記述と検証法，プロセス代数，時相論理などの研究 に従事． 東野 輝夫（正会員） 昭和54年大阪大学基礎工学部情 報工学科卒業．昭和59年同大学大 学院博士課程修了．現在，大阪大学 大学院情報科学研究科教授．工学博 士．分散システム，通信プロトコル 等の研究に従事．電子情報通信学会，ACM各会員．

IEEE Senior Member.

GET_PACKET IP_FILTERING IP_COUNTER FLOODING_TABLE DISPLAY_DEVICE FILTER COUNTER TABLE Pct Pct Pct Pct Pct Pct Tbl : Hardware Module : Data Flow (Event) : Data

図 12 IP フラッディング検出モジュールの一連の処理 Fig. 12 Processing stages of IP flooding detecting module