full text - Workshop on Internet Technology

The Fifth Workshop on Internet Technology – WIT2003
スケーラブルパケットキャプチャシステムの実現
Implementation of a Scalable Packet Capture System SPACE
加藤 和夫 †
大須賀 怜 †
†
高木 淳史 †
高橋 直久 †
名古屋工業大学大学院 工学研究科
概要
本稿では，高速ネットワークの監視，診断のための基
本要素として，速度，場所，時間，条件に関するスケーラ
ビリティの向上を目指した選択的なパケットキャプチャ
システム SPACE を提案し，その実現法について述べる．
提案システムでは，内容と数量に基づきパケットを選択
することにより，DoS 攻撃など，あらかじめフィルタで
指定困難なパケットを選択的にキャプチャすることを可
能とする．また，近似を用いた空間分割型パケットフィル
タリングにより，大量のキャプチャ条件を指定した場合
にも高速なパケット選択を可能とする．汎用 PC をベー
スとして，連続的なパケットキャプチャを可能とするた
め，このようなキャプチャ機能と大容量バッファをネッ
トワークインターフェイスカード (NIC) に搭載する．本
稿ではまた，実験システムについて述べ，TCP/IP ヘッ
ダ情報の収集についての簡単な評価実験を行う．
1
片山 喜章 †
はじめに
インターネットが社会基盤として重要になるに従って，
ネットワークを監視，診断する基本技術として，パケッ
トキャプチャシステム [1] の重要性が高まっている．パ
ケットキャプチャシステムは，ネットワーク上のパケッ
トを収集するツールであり，収集したパケットをログと
して記録し，ログを解析することによりネットワークの
監視，診断を行うことができる．
近年，ネットワークで扱われる情報量は飛躍的に増加
し，ネットワークの回線速度も高速になっている．これ
に伴い，パケットキャプチャシステムの高速ネットワーク
への対応が必要とされている．しかし，高速ネットワー
クではパケットが瞬時に大量に発生するため，PCI バス
の転送速度がボトルネックとなりすべてのパケットを収
集できないといった問題がある．さらに，定常的観測を
行う場合には，ログを記録するために膨大な記憶容量が
必要となる．
このような問題に対し，文献 [2] では，RAID システム
を構築し，NIC デバイスドライバーの改良と分散処理を
行うことにより，1GbE でのパケットヘッダ収集を実現
している．しかし，この手法では，256Byte 以下のパケッ
トがワイヤーレートで発生するような場合にはパケット
の取りこぼしが発生する．
また，既存のネットワーク試験装置 [3, 4, 5] では，高
速な専用ハードウェアを用いることにより，1∼10Gbps
の高速なネットワークでのパケットキャプチャを実現し
ている．しかし，ハードウェアの制約から，数個程度の
–1–
キャプチャ条件しか指定できず，数十秒ときわめて短時
間しかパケットを取り込むことができない．
一方，インターネットでは多様な情報が多重化されて
転送されているため，トラヒックの解析を行うためには
多地点での観測が必要となる．この場合には，多地点での
観測結果を照合するため，高精度な広域同期の実現が必
要となる．さらに，実用的には，パケットキャプチャシス
テムの小型化，低価格化が望まれる．ここで，tcpdump
などのソフトウェアによりパケットをキャプチャするこ
とにより，システムの小型化，低価格化を実現すること
ができる．しかし，ソフトウェアベースのシステムでは，
高速ネットワークに対応することができない．
本論文では，このような問題に対し，スケーラブルパ
ケットキャプチャシステム (SPACE：Scalable Packet Capture System) を提案する．SPACE では，内容と数量に
基づくパケット選択機能を 1 チップで実現し，PC へ通信
機能の一部として搭載し，以下に示すスケーラビリティ
の向上を目標とする．
1. 速度：パケットを受信するとすぐにパケットの選択，
切り出しを行うことにより，回線速度の高速化に対
応可能とする．
2. 場所：汎用 PC をベースとすることで小型化・低価
格化を実現する．また，GPS を用いた高精度広域同
期クロックを実現し，観測地点数の増大に対応可能
とする．
3. 時間：必要なパケットのみキャプチャすることによ
りデータ量を削減し，観測時間の長期化及び定常観
測に対応可能とする．
4. 条件：キャプチャ条件数に依存しないパケット選択
方式を提案し，キャプチャ条件数の増加に対応可能
とする．
SPACE では，PC 上のソフトウェアと専用ハードウェ
アが協調してパケットをキャプチャすることにより，専
用ハードウェアを最小限の構成で実現する．これにより，
ネットワークインターフェイスカード (NIC) 上に内容と
数量に基づく選択的パケットキャプチャ機能を搭載する．
パケットキャプチャ処理の多くを NIC 上で行うことによ
り，汎用 PC をベースとして，上記のスケーラビリティ
向上を実現する．
次に，提案システムの実現法の特徴を示す．
1. 内容と数量に基づくパケット選択法
フィルタリングとパケットの計数を連携して行うこ
とにより，内容と数量に基づくパケット選択を実現
する．これにより，DoS 攻撃など，従来のフィルタ
Implementation of a Scalable Packet Capture System SPACE
2
ࠠࡖࡊ࠴ࡖ᧦ઙ
࡙࡯ࠩࠗࡦ࠲࡯ࡈࠚࠗࠬ
ࡈࠖ࡞࠲ቯ⟵
H࡮࡮
H࡮࡮
0+%ࠦࡑࡦ࠼
⸃ᨆ
ࡈࠖ࡞࠲
ࠦࡦࡄࠗ࡜
2%+ࠗࡦ࠲࡯ࡈࠚࠗࠬ
ᐢၞหᦼࠢࡠ࠶ࠢ
ಽ⸃೙ᓮ
࠺࡯࠲
࠲ࠗࡓ
ࠬ࠲ࡦࡊ
ࡄࠤ࠶࠻ㆬᛯ
ࡈ࡟࡯ࡓో૕
෶ߪ৻ㇱ
ࠠࡖࡊ࠴ࡖ࠺࡯࠲
ಾࠅ಴ߒ
ᾖว⚿ᨐ
ࡄࠤ࠶࠻⸘ᢙ
ࡈࠖ࡞࠲࡝ࡦࠣ
ᾖว೙ᓮ
࠺࡯࠲
52#%'0+%
ࡋ࠶࠳ᖱႎ
ࡈ࡟࡯ࡓ
࠺࡯࠲࡝ࡦࠢጀ೙ᓮ
‛ℂጀ೙ᓮ
⋙ⷞ
ࡀ࠶࠻ࡢ࡯ࠢ
࠲࠶ࡇࡦࠣ
図 1: システム構成図
31
23
ࠕ࡚ࠢࠪࡦࠦ࡯࠼
関連研究
52#%'2%
ࠠࡖࡊ࠴ࡖ
ࡈ࡟࡯ࡓ
⺒ߺ಴ߒ
ࡈ࡟䳦ࡓࡃ䳟ࡈ䳚
ではあらかじめ指定困難なパケットについても選択
的にキャプチャできるようにする．
2. 1 チップ化可能なパケット選択機能の実現法
事前に作成したパケット分類表を用いることにより，
フィルタ数に依存しない時間で高速にパケットを分
類可能な，空間分割パケット分類法 [6, 7] を用いる．
この手法では，フィルタ数が多い場合に分類表のデー
タ量が膨大となる問題があるため，近似計算を導入
して分類表のデータ量を削減する，近似型空間分割
パケットフィルタリングを提案する．
以下では，2 章において関連研究について述べ，3 章で
は提案システムの概要を述べる．また，4 章では内容と
数量に基づくパケット選択の実現法について述べる．さ
らに，5 章において 1 チップ化可能なパケット選択機能
の実現法として，近似型空間分割パケットフィルタリン
グについて述べる．6 章では実験システムについて述べ，
簡単な評価実験を行う．
22
16
15
reserved
0
ࡈ࡟࡯ࡓ㐳
࠼ࡔࠗࡦ⼂೎ሶ
1 章では，ネットワーク監視の基本要素である，パケッ
トモニタ技術全般に関する関連研究と問題点について述
べた．本節では，提案システムの具体的な実現法に関連
する研究について述べる．
文献 [8] ではパケットの流量に着目して，large flow(ト
ラヒックの大部分を占める一部の流量の大きなフロー) を
識別し，その流量を見積もるための 2 つの手法を提案し
ている．この手法では，フローの定義を行い，その定義
に基づきパケットを計数することにより，large flow を検
出し，その流量を見積もる．しかし，DDoS 攻撃のよう
に多数のホストから一つのホストへ大量に送信され場合
には，フローの流量は少ないため，これらのパケットを
検出することができない．提案システムでは，フィルタ
リングの結果を計数することにより，このようなパケッ
トを検出し選択的にキャプチャできるようにする．
また，文献 [6, 7] では，空間分割型フィルタリングに
よりパケットを分類する手法が提案されている．文献 [6]
の手法では，n 次元問題を n-1 次元問題に簡約化するフィ
ルタ分別関数を導入し，部分計算と最適化により，ヘッ
ダ長 14 バイト，フィルタ数 10,000 のフィルタリングの
場合に，708kB のメモリで平均 16.8 回のメモリ参照によ
りパケットを分類している．文献 [7] では，空間を並列
に処理することにより，ヘッダ長 11 バイト，フィルタ数
3,000 のフィルタリングの場合に，500kB 程度のメモリ
を用いて数回のメモリ参照によりパケットを分類してい
る．しかし，FPGA などのハードウェアとして実装する
場合には，メモリの使用量を数 10KB 程度に抑える必要
がある．提案システムでは，空間の近似によりメモリの
使用量を最小限に抑えることを可能とする．
一方，文献 [9] では，汎用 PC と専用ハードウェアを
用いた 10Gbps ネットワークのモニタリングシステムが
提案されている．このシステムでは，パケットのヘッダ
情報をフロー毎に統合することにより，キャプチャデー
タの圧縮を行う．これにより，OC-192 ネットワークのワ
イヤーレートトラヒックから，すべてのパケットのヘッ
ダ情報を収集可能としている．しかし，このシステムで
は，パケットのデータ部分を用いて，ネットワークを詳
細に監視，診断することができない．提案システムでは，
–2–
࠲ࠗࡓࠬ࠲ࡦࡊ
ࠠࡖࡊ࠴ࡖ࠺࡯࠲
図 2: キャプチャフレームの形式
ネットワークの監視，診断に必要なパケットのみを選択
的にキャプチャすることにより，このような用途へも適
用できるようにする．
3
提案システムの概要
図 1 に提案システムの構成を示す．提案システムは，
PC 上のソフトウェア (SPACE–PC) と選択的キャプチャ
機能及び大容量バッファを搭載した NIC(SPACE–NIC)
からなる．SPACE–NIC においてキャプチャ処理の多く
を行うことにより，汎用 PC を用いて高速ネットワーク
におけるパケットキャプチャを実現する．
3.1
SPACE–NIC の基本機能
SPACE–NIC では，パケットを受信するとすぐにパケッ
ト選択機能により，キャプチャするパケットを選択する．
パケットが選択されると，キャプチャデータ切り出し機
能により，パケットの必要な部分のみを切り出す．さら
に，タイムスタンプ等のキャプチャヘッダ情報を付加し，
図 2 に示すキャプチャフレームの形式で，フレームバッ
ファに格納する．
SPACE–NIC では，以下に示す基本機能を実現する．
1. キャプチャデータ切り出し機能
パケットの必要な部分のみを選択的にキャプチャす
ることにより，SPACE–NIC から SPACE–PC への
データ転送量を軽減させる．
オペレータの指定に従い，パケットの先頭から start
バイト目と stop バイト目の範囲を切り出す．
2. パケット選択機能
必要なパケットのみを選択的にキャプチャすること
により，さらにデータ転送量を軽減させる．
フィルタリングとパケット計数を連携することに
より，内容と数量に基づくパケット選択を実現する．
The Fifth Workshop on Internet Technology – WIT2003
これにより，以下に示すパケットを選択的にキャプ
チャできるようにする．
(a) 特定のヘッダ情報を持つパケット (特定のホス
トへのパケット等)
(b) 短期間に集中するパケット (DoS 攻撃やサーバ
へのアクセスの集中等)
i. 特定のヘッダ情報を持つパケット
ii. あらかじめ送信元/宛先 IP アドレスが予測
できないパケット
このとき，フィルタリングに空間分割パケット分類
法 [6, 7] を用いることにより，フィルタ数が多い場
合にも高速にパケットを選択できるようにする．
3. 大容量フレームバッファ機能
キャプチャデータ読み出しサイクルの揺らぎ，及び
データ転送量の揺らぎを吸収する．
4. 高精度広域同期クロック機能
各パケットに GPS を用いた高精度広域同期タイム
スタンプを付加することにより，多地点での観測結
果を照合できるようにする．
これらの基本機能により，すべてのパケットの TCP/IP
ヘッダ情報のみを収集してネットワークの統計情報を計
測することや，高速ネットワークにおいて特定のパケッ
トのみを選択的に監視，診断することなどを可能とする．
3.2
提案システム実現上のアプローチ
提案システムは，高速ネットワークにおける選択的パ
ケットキャプチャを実現するため，高速なパケットフィル
タリング手法が必要となる．また，選択的パケットキャ
プチャ機構を NIC 上に実装するため，パケット選択機能
などの基本機能は簡易な機構で実現し，1 チップ化する
必要がある．さらに，使用できるメモリ容量にも数 10kB
と制限がある．
ここで，ルーティングテーブル探索やファイヤーウォー
ルにおけるフィルタリングでは，すべてのパケットに対
してルールの照合が正確に行われなければならない．し
かし，ネットワーク監視・診断システムにおけるパケット
キャプチャでは，監視，診断に必要のないパケットに関
しては，ルールとの照合結果に反してキャプチャしてし
まったとしても良いという特性がある．たとえば HTTP
による通信のトラヒックを監視したい場合，HTTP のパ
ケットはすべてキャプチャされなければならない．しか
し，その他のパケットについては本来キャプチャすべき
でないパケットでも少量ならばキャプチャしても良いと
いえる．キャプチャしたとしても，診断の際に取り除く
ことができるため，少量で容易に取り除くことができる
のならば大きな問題にならない．
そこで，近似を行わない場合にキャプチャされるパケ
ットはかならずキャプチャすることを保証するように，
キャプチャ条件の近似 (安全な近似) を行う．これにより
SPACE–NIC の基本機能を簡易な機構で実現し，使用メ
モリ容量を抑制できるようにする．
4
内容と数量に基づくパケット選択法
提案システムでは，フィルタリングとパケット計数を
連携して行うことにより，内容と数量に基づくパケット
選択を実現する．これにより，3 章で述べたようなパケッ
トを選択的にキャプチャできるようにする．
以下，4.1 節では内容と数量に基づくパケットのキャプ
CCL
rule
filter–id
filter
condition
field–condition
range
interval
start–value
end–value
value
field
byte–condition
byte–position
byte–range
byte–interval
byte–start–value
byte–end–value
byte–value
action
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
rule {rule}
(filter–id filter action)
integer
(condition {condition})
field–condition | byte–condition
(field range)
interval | value | ANY
start–value end–value
value
value
net–addr | host–addr | port-num | ...
IPsrc | IPdst | PORTsrc | ...
(byte–position byte–range)
0 | 1 | 2 | 3 | ... | 58 | 59
byte–interval | byte–value
byte–start–value byte–end–value
byte–value
byte–value
0 | 1 | 2 | 3 | ... | 254 | 255
ACCEPT | WEAKLY–ACCEPT |
WEAKLY–REJECT | REJECT
図 3: CCL：Capture Control List
チャ条件の記述を与え，4.2 節においてフィルタリングと
パケット計数の連携法について述べる．
4.1
内容と数量に基づくキャプチャ条件の記
述法
提案システムでは，オペレータは Capture Control
List(CCL) 及び Threshold Condition(Th.C) を用いて内
容と数量に基づくキャプチャ条件を記述する．
Th.C は観測時間 ∆ とパケット数 τ からなる．提案シ
ステムでは ∆ 時間内に τ 個以上のパケットが到着した場
合に，パケットが集中していると判定する．
CCL は，図 3 に示すように rule の集合からなる．rule
は filter–id と filter，action の組であり，各 rule は filter–
id により区別される．また，filter は，パケットに対する
照合条件 (condition) の集合からなる．condition は，パ
ケットヘッダの特定のフィールド (IP アドレスやポート
番号等) が満たすべき条件 (field–condition)，又はパケッ
トヘッダの特定の位置にあるバイト値が満たすべき条件
(byte–condition) である．field–condition には，パケット
ヘッダの特定のフィールド (field) と，その値が満たすべ
き範囲 (range) を領域 (interval)，値 (value)，ANY(後述)
のいずれかとして指定する．また，byte–condition には，
パケットの先頭からの位置 (byte–position) と，その位置
のバイト値が満たすべき範囲 (byte–range) を領域 (byte–
interval) 又は値 (byte–value) として指定する．今回の実
装では，byte–condition を用いる場合には，byte-position
としてパケットの先頭 0–59Byte の範囲の値のみを許す．
一方，action には，filter のすべての照合条件を満たすパ
ケットに対するキャプチャ動作を指定する．
以下では，アクション及びフィールドの ANY 指定に
ついて詳細を述べる．
4.1.1 4 つのアクション指定
従来の多くのキャプチャシステムでは，図 4(a) に示す
ように，フィルタの照合条件を満たすパケットに対し ACCEPT(キャプチャする．以降 A)，又は REJECT(キャプ
–3–
Implementation of a Scalable Packet Capture System SPACE
reject
packets/Ǎ
ߔࠆ ߒߥ޿
ࠠ䏔ࡊ࠴䏔
ߔࠆ ߒߥ޿
ࠠ䏔ࡊ࠴䏔
accept
accept
reject
weakly-accept
ANY
packet
IPsrc
packets/Ǎ
IPdst
(a)2 アクション
(b)4 アクション
図 4: 4 つのアクション
4.2.1
たとえば，hostA への HTTP によるアクセスを定常
的に監視したい場合には，キャプチャ条件として “IPdst
hostA PORTdst 80 A” のように指定する．一方，hostA
への HTTP によるアクセスが集中した場合に，それら
のパケットをキャプチャしたい場合には，“IPdst hostA
PORTdst 80 W–A” のように指定すればよい．これによ
り，アクセスが集中して異常が発生したと判断し，警告
するなどといったことが可能となる．さらに，telnet サー
バ hostA を定常的に監視するが，演習時などアクセスが
集中する場合にはログの肥大化を避けるため監視したく
ない場合には，“IPdst hostA PORTdst 23 W–R” と指定
すればよい．
ANY 指定
DoS 攻撃のパケットのように，あらかじめその送信元
IP アドレスが予測できないようなパケットに対しても，
大量に受信した場合にはキャプチャできるようにするた
めに，特定の値の代わりに “ある値” を意味する ANY を
用いてキャプチャ条件を記述できるようにする．
たとえば，あらかじめ予測できないが，あるホストが
大量にパケットを送信している場合に，それらのパケッ
トをキャプチャしたい場合には，キャプチャ条件として
“IPsrc ANY W–A” と指定すればよい．これにより，輻
輳の原因となるような大量のパケットを送信しているホ
ストが存在すると判断し，警告するなどといったことが
可能となる．
CEVKQP
tf ts td
VOCR
VUGNGEVQT
㑣୯್ቯ
パケット照合法
図 5 に示すように，フィルタリングによるパケットの
分類 (フィルタ照合) とパケット計数値の判定 (閾値判定)
を連携して行う．
• フィルタ照合 SIERRA(F, x1 , x2 , ..., xN )
パケットヘッダの値 x1 , x2 , ..., xN をキーとして，フィ
ルタ集合 F の照合条件とキーとの比較を行う．
フィルタ照合では，すべての照合条件を満たすフィ
ルタ集合を決定し，フィルタの優先度に従い，パケッ
トの属するフィルタを一意に決定する．さらに，決
定したフィルタからパケットに対する action と閾値
判定結果選択式 (t–selector．後述) を決定する．
• 閾値判定 T hreshold(k, ∆, τ )
入力されたキー k について，それぞれ ∆ 時間内の
出現数を計数し，計数値が閾値 τ 以上であるか判定
する．
このとき，図 5 のように，フィルタ照合の結果
(filter–id) について計数することにより，特定のヘッ
ダ情報を持つパケットが短期間に集中しているかを
判定できるようにする．また，送信元/宛先 IP アド
レスについて計数することにより，あらかじめパケッ
トの送信元/宛先が予測できないパケットが短期間に
集中しているかを判定できるようにする．
さらに，これらの計数値の判定結果から，閾値判
定結果マップ (t–map) と呼ぶ 3 ビットの組 (tf ts td )
を決定する．ここで，tf ，ts ，td はそれぞれ，フィ
ルタ識別子，送信元 IP アドレス，宛先 IP アドレス
に対する閾値判定結果である．たとえば，フィルタ
識別子をキーとした計数値が τ 以上であれば，tf の
値を 1 とする．
4.2.2
パケット選択法
フィルタ照合により決定される action と t–selector，
及び閾値判定の結果である t–map に基づきパケットを
選択/破棄する．
パケットのアクションが ACCEPT (a0 a1 =11) 又は REJECT (a0 a1 =00) である場合には，アクションに従いパ
ケットを選択/破棄する．
一方，アクションが WEAKLY–ACCEPT (a0 a1 =10)
又は WEAKLY–REJECT (a0 a1 =01) である場合には，
t–map に従いパケットを選択/破棄する．tf ，ts ，td を用
いて論理演算を行い，その結果が真 “1” であればパケット
が集中していると判定し，パケットを選択/破棄する．こ
こで，表 1 に示すように，t–selector に従って，t–map に
対する論理演算式 (選択式) を変更する．たとえば，action
が WEAKLY–ACCEPT であり，t–selector が “110” で
ある場合には，tf ∗ (ts + td ) の演算結果が “1” であれば
パケットが集中していると判定し，パケットを選択する．
このように，t–selector に従って t–map の論理演算式
今回の実装では，送信元/宛先 IP アドレスの値として
のみ ANY を用いることを許している．
4.2
a0 a1
ss sd so
図 5: フィルタリングとパケット計数の連携
チャしない．以降 R) の動作を指定する．提案システム
では，これに加えて図 4(b) に示すように，WEAKLY–
ACCEPT(以降 W–A) 及び WEAKLY–REJECT(以降
W–R) の 2 つのアクションを導入することにより，パケッ
トの数量を考慮したアクションの指定を可能にする．こ
こで，W–A はフィルタの照合条件を満たすパケットが ∆
時間内に τ 個以上の場合にキャプチャし，W–R は τ 個
以上の場合にキャプチャをやめることを意味する．
4.1.2
ࡈࠖ࡞࠲ᾖว
filter-id
weakly-reject
ANY
Ǽ
x1 x2 ....... xN
フィルタリングとパケット計数の連携方式
提案方式では，オペレータが指定したキャプチャ条件
に基づき，フィルタリングとパケット計数によりパケッ
トを照合する．さらに，照合結果に従いパケットを選択
する．これにより，3.1 節で述べたように，以下に示すパ
ケットを選択的にキャプチャできるようにする．
• 特定のヘッダ情報を持つパケット
• 短期間に集中するパケット
本節では，まずパケット照合法について述べ，次にパケッ
ト選択法について述べる．
–4–
The Fifth Workshop on Internet Technology – WIT2003
]_
&
表 1: t–selector と選択式
t–selector
選択式
ss sd so
0 0 dc
tf
1 0 dc
tf ∗ ts
0 1 dc
tf ∗ td
1 1
0 tf ∗ (ts + td )
1 tf ∗ (ts ∗ td )
1 1
dc：don’t care
]HH_
&
]H_ ]_
& &
f1
f1,ff2
[
2CEMGV
Z[
を変更することにより，送信元/宛先 IP アドレス及び
filter–id の 3 つの計数のみで，オペレータが指定したキャ
プチャ条件に基づき，パケットを選択/破棄することを可
能とする．以下に，t–selector の決定方法を示す．
近似型空間分割パケットフィルタリ
ング
フィルタ数の増大に対応するため，フィルタ照合機能
において空間分割パケットフィルタリングを用いる．フィ
ルタリングを多次元点位置決定問題としてとらえ，与え
られたフィルタ集合を元に，図 6 のようにパケットヘッ
ダの各フィールドを各次元のキーとした多次元空間上に
フィルタを配置する．あらかじめ，上記の空間を探索表
として作成しておくことにより，一定回数の表の探索に
よりフィルタ数に依存しない時間でパケットを分類する
ことを可能とする
しかし，空間分割パケットフィルタリングでは，フィ
Z
_
ࡈࠖ࡞࠲㓸ว
࠼ࡔࠗࡦ⼂೎ሶ
& ]_
& ]H_
& ]HH_ f2
t–selector 決定法 まず，フィルタの照合条件に IP ア
ドレスが満たすべき値として ANY が指定されていない
場合には，フィルタ識別子の閾値判定結果 (tf ) により，
パケットが集中しているか判定できる．また，ANY が指
定されている場合にも，tf を考慮する必要がある．従っ
て，t–selector では送信元/宛先 IP アドレスの閾値判定
結果 (ts /td ) をどのように扱うかを指定すればよい．ここ
で，t–selector の ss ，sd ビットはそれぞれ，ts ，td を考
慮することを意味する．すなわち，フィルタの照合条件
に “IPsrc ANY” がある場合には ss を，“IPdst ANY” が
ある場合には sd を “1” とする．
次に，フィルタの照合条件に “IPsrc ANY IPdst ANY”
がある場合には，IP アドレス対を計数し，計数値が閾値
以上であるか判定して，パケットが集中しているかを決定
する必要がある．このとき，3.2 節で述べたように，キャ
プチャ条件に指定されたパケットは必ず選択するような
近似 (安全な近似) を行う．すなわち上記のパケットは，
ts =1 かつ td =1 であるパケットの中に含まれているため，
ts ∗ td =1 であるような場合にパケットを選択/破棄すれば
良い．従って，このような場合には t–selector を “111”(ts
と td の AND) とする．
一方，フィルタの照合条件に IP アドレスが満たすべき
値として ANY が指定されたルールが複数存在した場合
には，これらのルールを統合する．たとえば，“f1 IPsrc
ANY W–A” と “f2 IPdst ANY W–A” というルールが指
定された場合には，ts =1 又は td =1 である場合 (ts +td =1)
にパケットを選択すればよい．従って，“f1 IPsrc ANY
or IPdst ANY W–A” のようにルールを統合する．この
ような場合には，t–selector を “110”(ts と td の OR) と
する．
5
]H_
&
& ]H_
& ]_
2 次元空間での例，“f1 x 3,22 y 11,28”，“f2 x 12,29 y 3,20”
図 6: 2 次元空間へのフィルタ配置例
ルタ数が多い場合は，探索表が巨大になってしまうとと
もに，探索表を生成するための事前計算に多大の時間を
要する問題がある．そこで，3.2 節で述べたように，近似
を行わない場合にキャプチャされるパケットはかならず
キャプチャすることを保証するように近似を行う．これ
により，探索表の大きさを抑制する．
以下では，まず，空間分割パケットフィルタリングに
ついて述べ，次に，探索表の近似方法について述べる．
5.1
空間分割パケットフィルタリング
空間分割型パケットフィルタリングでは，以下に示す
関数を用いてフィルタリングを行う．
• フィルタ集合のふるい関数 sieve(F, xi , i)
i 番目のキーの値が xi のとき，入力フィルタ集合 F
のうち，xi が i 番目の条件を満たすフィルタ集合を
選択する関数．
• フィルタ集合の積関数 product(F1 , F2 , ..., FN )
入力フィルタ集合 F1 , F2 , ..., FN の積集合を求める
関数．
• フィルタ照合関数 SIERRA(F, x1 , x2 , ..., xN )
N 個の sieve を用いて，入力フィルタ集合 F のう
ち，N 個のキー (x1 , x2 , ..., xN ) の値がすべての条
件を満たすフィルタ集合を選択する関数．
たとえば，N =4 の場合には，4 個の sieve を直列
に並べることにより SIERRA を実現できる．
SIERRA(f, x1 , x2 , ..., xN ) =
sieve(sieve(sieve(sieve(F, x1 , 1), x2 , 2)x3 , 3)x4 , 4)
また，4 個の sieve を並列に並べ，product で積集合
をとってもよい．以下では，sieve を並列に配置す
る場合について説明する．
SIERRA(f, x1 , x2 , ..., xN ) =
product(product(sieve(F, x1 , 1), sieve(F, x2 , 2)),
product(sieve(F, x3 , 3), sieve(F, x4 , 4))
ここで，それぞれの関数は，空間上にフィルタを配置す
るための作表計算，及び空間を参照するための索表計算
(タビュレーション) の 2 つの計算に分解できる．
5.1.1 フィルタコンパイラ (作表計算)
作表計算は部分計算が可能である．すなわち，キーの
値を必要とせず，フィルタ集合が与えられれば計算を行
うことが可能であり，パケットキャプチャを開始する前
–5–
Implementation of a Scalable Packet Capture System SPACE
ࡄࠤ䳟࠻ࡋ 䳟 ࠳
表 2: sieve 探索表及び product 探索表
(c)product 探索表
(a)X に対する sieve 探索表
x1
0–2
3–11
12–22
23–29
30–31
F1
00
10
11
01
00
D1
0
1
2
3
0
(b)Y に対する sieve 探索表
x2
0–2
3–10
11–20
21–28
29–31
F2
00
01
11
10
00
D2
0
1
2
3
0
D1
0
0
0
0
1
1
1
1
2
2
2
2
3
3
3
3
D2
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
F12
00
00
00
00
00
00
10
10
00
01
11
10
00
01
01
00
D12
0
0
0
0
0
0
1
1
0
2
3
1
0
2
2
0
x1
x2
x3
x4
sieve
࠼ࡔࠗࡦ⼂೎ሶ
product
sieve
product
sieve
ㆡวߔࠆ
ࡈࠖ࡞࠲
product
sieve
図 7: フィルタ照合 (索表計算) フロー
それぞれ 1 回のメモリ参照により実現できる．また，
各 sieve，product は並列処理することが可能である．
従って，この場合には，フィルタ数に関係なく，3 ス
テップですべてのキーが条件を満たすフィルタ集合
を求めることができる．
5.2
2 次元空間での例，“f1 x 3,22 y 11,28”，“f2 x 12,29 y 3,20”
に計算しておくことができる．
• sieve の作表計算
表 2(a)，(b) に示すように，キーの値と出力フィル
タ集合の対応表 (sieve 探索表) を作成し，フィルタ
集合の識別子としてドメイン識別子を (Di ) 求める．
表のエントリー数は，キーが取り得る値の数となる．
• product の作表計算
表 2(c) に示すように，2 つのドメイン識別子 (フィル
タ集合) の組と出力フィルタ集合の対応表 (product
探索表) を作成し，フィルタ集合の識別子としてド
メイン識別子を求める．表のエントリー数は，ドメ
イン識別子が取り得る値の数となる．
• SIERRA の作表計算
入力されるキーの数だけ，キーの取り得るすべての
値について sieve 探索表のエントリーを作成する．同
様に，入力として与えられる可能性のあるドメイン
識別子の組について product 探索表のエントリーを
作成する．
5.1.2 フィルタ照合 (索表計算)
• sieve の索表計算
各次元のキーの値とそれに対応する sieve 探索表か
ら，ドメイン識別子を求める．
• product の索表計算
2 つのドメイン識別子の組とそれに対応する product
探索表から，ドメイン識別子を求める．
• SIERRA の索表計算
図 7 に，N =4 の場合の SIERRA 索表計算の手順
を示す．まず，パケットヘッダーの値をキーとして，
すべてのキーに対して sieve 索表計算を行う．次に，
2 つの sieve 索表計算の結果から得られるドメイン
識別子の組を用いて，product 索表計算を行う．さ
らに，2 つの product 索表計算の結果により得られ
るドメイン識別子の組を用いて，product 索表計算
を繰り返す．これにより，すべてのキーが条件を満
たすフィルタ集合を求め，得られたフィルタ集合に
おいて，最も優先度の高いフィルタを選択する．
ここで，sieve 索表計算及び product 索表計算は
–6–
探索表の近似方法
フィルタ数が多い場合に，探索表が巨大となる問題を
解決するため，作表計算時にダミーフィルタを挿入する
ことにより，探索表の近似を行い，制御データ量を削減
する．
• sieve 作表計算の近似
sieve(F, xi , i) = Fi ，sieve(F, xj , j) = Fj のとき，
sieve(F, xi , i) = Fj とすることを sieve(F, xi , i) を
近似するという．例えば，表 2(a) において，23 ≤
x1 ≤ 31 の範囲に，f1 をダミーフィルタとして挿
入することにより，表 3(a) のように，D1 = 2, 3 を
D1 = 2 に統合する．これにより，表 3(c) に示すよ
うに，product 探索表のエントリー数を削減できる．
このとき，Fi ⊂ Fj かつ，Fj − Fi に含まれる
フィルタのアクションが ACCEPT 又は WEAKLY–
ACCEPT である場合に，この近似はポジティブな
近似であるという．一方，上記のアクションが REJECT 又は WEAKLY–REJECT である場合，ある
いは，Fi ⊃ Fj である場合にはネガティブな近似で
あるという．
• product 作表計算の近似
product(Fi1 , Fi2 ) = Fi ，product(Fj1 , Fj2 ) = Fj
の と き ，product(Fi1 , Fi2 ) = Fj と す る こ と を
product(Fi1 , Fi2 ) を近似するという．このとき，Fi ，
Fj の関係に従い，sieve 作表計算の近似と同様に，
ポジティブな近似とネガティブな近似を定義する．
• SIERRA 作表計算の近似
すべての sieve 作表計算と product 作表計算におい
てポジティブな近似のみを許す．これにより，作表計
算の近似を許さない場合にキャプチャされるパケッ
トは，かならずキャプチャするように，探索表の近
似を行うことができる．近似方法の詳細については
別途報告する．
6
実験システム
現在，提案システムに対して以下に示す評価を行うた
め，実験システムを開発中である．
1. ネットワーク中のすべてのパケットをキャプチャし
監視するような場合の適用領域を明らかにする．
2. 特定のヘッダ値を持つパケットを選択し，キャプチャ・
監視するような場合の適用領域を明らかにする．
The Fifth Workshop on Internet Technology – WIT2003
表 3: 近似後の探索表
(a)X に対する sieve 探索表
(c)product 探索表
x1
0–2
3–11
12–29
30–31
F1
00
10
11
00
D1
0
1
2
0
D1
0
0
0
1
1
1
2
2
2
D1 = 2, 3 を D1 = 2 に統合
(b)Y に対する sieve 探索表
x2
0–2
3–10
11–28
29–31
F2
00
01
11
00
D2
0
1
2
0
D2 = 2, 3 を D2 = 2 に統合
D2
0
1
2
0
1
2
0
1
2
F12
00
00
00
00
00
10
00
01
11
D12
0
0
0
0
0
1
0
2
3
NW/IF
PCI Bus
GPS/IF
D1 = 2 又は D2 = 2 の場合近似
により，誤ってキャプチャする可
能性がある．
DIMM
FPGA
2 次元空間での例，“f1 x 3,22 y 11,28”，“f2 x 12,29 y 3,20”
図 8: 試作 SPACE-NIC の外観及び主な仕様
3. 内容と数量に基づくパケット選択により，
(a) 特定のヘッダ情報を持つパケット
(b) あらかじめ IP アドレスが予測困難なパケット
が短時間に集中した場合に検出可能であること，及
びその適用領域を明らかにする．
6.1
)D'
実験システムの構成
提案システムの適用領域を明らかにするため，選択的
キャプチャ機能と大容量バッファを搭載した NIC と汎用
PC により，SPACE を実現する．
図 8 に試作した SPACE-NIC の外観及びその主な仕様
を示す．現在，システムは開発途中であるが，タイムス
タンプ機能，パケット切り出し機能，フレームバッファ
格納機能は試作した SPACE–NIC 上で動作している．タ
イムスタンプ機能は，全二重のネットワークにおいて，2
枚の SPACE–NIC により上りと下りのパケットを別々に
監視する場合などに，2 枚の SPACE–NIC のクロックを
同期するため，1pps と 25Mpps(SPACE–NIC 内部クロッ
ク) を分配する機構を実現している．また，大容量フレー
ムバッファとして最大 2GB の SDRAM を搭載可能であ
る．本稿ではこれら実装を完了した機能を用いた簡単な
評価実験の結果を示す．
一方，残りの機能についてはソフトウェアとして実装
するとともに，試作 SPACE–NIC と連携させて内容と数
量に基づくパケット選択を実現し，機能の確認を行った．
6.2
1000BASE–T(802.3ab)
データバス：32bit (64bit に拡張可能)
クロック：33MHz，66MHz
入力：1pps 信号，10MHz 信号
出力：1pps 信号，25MHz 信号
最大 2GB 書き込み時：3.2Gbit/s
読み出し時：2.432Gbit/s
Xilinx Virtex–II XC2V6000–5BF957C
評価実験
試作 SPACE–NIC を用いて図 9 に示す実験環境を構
築し，インターネットにおいて TCP/IP ヘッダを収集
する場合について簡単な評価実験を行う．実験環境では，
SPACE 実験システムとトラヒックジェネレータ (Anritsu
MD1230[3]) が 1GbE により接続される．トラヒックジェ
ネレータにより任意の Ethernet フレームを発生させる．
ここで，文献 [10] では，20 地点でインターネットのト
ラヒックを計測した結果，ほとんどの計測地点での平均
パケット長が 500B から 1000B の範囲であったと報告し
ている．このことから，本実験では平均パケット長 500B
のトラヒックについて評価を行う．また，試作 SPACE–
NIC では 1GB の大容量バッファを搭載しているため，
70B(キャプチャフレームヘッダ 16B ＋ Ethernet ヘッダ
14B ＋ TCP/IP ヘッダ 40B) のキャプチャフレームを約
–7–
࠻࡜ࡅ࠶ࠢ
ࠫࠚࡀ࡟࡯࠲
52#%'ታ㛎ࠪࠬ࠹ࡓ
OS
RedHat Linux 8.0
Motherboard
ASUSTeK A7M266-D
CPU
AMD Athlon MP 2000+
Memory
1GByte(PC2100)
Hard Disk
30GByte(Maxtor 5T030H3)
図 9: 実験環境
15,000,000 個バッファリングすることが可能である．こ
れによりパケット長のばらつきをある程度吸収できるた
め，本実験では固定長のワイヤーレートのトラヒックに
ついて評価を行う．
実験では，トラヒックジェネレータにより固定長 500B
の Ethernet フレームをワイヤーレートで発生させる．こ
のとき，SPACE 実験システムにおいてフレームを収集
し，発生させたフレーム中，収集できたフレームの割合
(収集率) を測定する．実験手順を以下に示す．
• Step–1: SPACE–NIC でパケットの切り出す
• Step–2: SPACE–PC 上のメモリへの取り込む
• Step–3: キャプチャデータを記録
このとき評価項目として，以下の実験を行う．
• 評価 1: システム全体の評価
現段階のシステムで，1Gbps ネットワークへの対応
できるかを評価するため，Step–3 において，HDD
へ記録する．
• 評価 2: PCI バスの転送速度の限界の評価
現段階での PCI バスの転送速度の限界を評価するた
め，Step–3 において，パケットを破棄する (HDD の
影響を除外)．
また，比較のため SPACE 実験システムと同一の PC
及び市販の GbENIC を用い，tcpdump によりパケット
を収集した場合についても実験を行う．
ここで，実験システムは，現在開発途中であるため，デ
バイスドライバや SPACE–PC プログラムに対するチュー
Implementation of a Scalable Packet Capture System SPACE
㪪㪧㪘㪚㪜
㩿㪊㪉㪹㫀㫋㪗㪍㪍㪤㪟㫑㪀
㪐㪇
㫋㪺㫇㪻㫌㫄㫇
㩿㪥㪼㫋㪾㪼㪸㫉㩷㪞㪘㪊㪇㪉㪫㪀
㩿㪊㪉㪹㫀㫋㪗㪍㪍㪤㪟㫑㪀
㪏㪇
෼㓸₸㩷㪲㩼㪴
㪎㪇
㪍㪇
㪈㪇㪇
㫋㪺㫇㪻㫌㫄㫇
㩿㪠㫅㫋㪼㫃㩷㪛㪼㫊㫂㫋㫆㫇㩷㪘㪻㪸㫇㫋㪼㫉㪀
㩿㪊㪉㪹㫀㫋㪗㪍㪍㪤㪟㫑㪀
㫋㪺㫇㪻㫌㫄㫇
㩿㪠㫅㫋㪼㫃㩷㪪㪼㫉㫍㪼㫉㩷㪘㪻㪸㫇㫋㪼㫉㪀
㩿㪍㪋㪹㫀㫋㪗㪍㪍㪤㪟㫑㪀
㫋㪺㫇㪻㫌㫄㫇
㩿㪊㪚㪦㪤㩷㪊㪚㪐㪐㪍㪙㪄㪫㪀
㩿㪍㪋㪹㫀㫋㪗㪍㪍㪤㪟㫑㪀
㪐㪇
㪏㪇
㪎㪇
෼㓸₸㩷㪲㩼㪴
㪈㪇㪇
㪌㪇
㪋㪇
㪌㪇
㪋㪇
㪊㪇
㪊㪇
㪉㪇
㪉㪇
㪈㪇
㪈㪇
㪇
㪇
㪋㪇
㪍㪇
㪏㪇
㪈㪇㪇
㪈㪉㪇 㪈㪋㪇 㪈㪍㪇 㪈㪏㪇 㪉㪇㪇
ಾ䉍಴䈚䉰䉟䉵㩷㪲㪙㫐㫋㪼㪴
㪉㪉㪇
㪉㪋㪇
㪉㪍㪇
㪪㪧㪘㪚㪜㩿㪆㪻㪼㫍㪆㪿㪻㪸㪉㪀
㩿㪊㪉㪹㫀㫋㪗㪍㪍㪤㪟㫑㪀
㪪㪧㪘㪚㪜㩿㪆㪻㪼㫍㪆㫅㫌㫃㫃㪀
㩿㪊㪉㪹㫀㫋㪗㪍㪍㪤㪟㫑㪀
㪠㫅㫋㪼㫃㩷㪪㪼㫉㫍㪼㫉㩷㪘㪻㪸㫇㫋㪼㫉㩿㪆㪻㪼㫍㪆㪿㪻㪸㪉㪀
㩿㪍㪋㪹㫀㫋㪗㪍㪍㪥㪟㫑㪀
㪠㫅㫋㪼㫃㩷㪪㪼㫉㫍㪼㫉㩷㪘㪻㪸㫇㫋㪼㫉㩿㪆㪻㪼㫍㪆㫅㫌㫃㫃㪀
㩿㪍㪋㪹㫀㫋㪗㪍㪍㪥㪟㫑㪀
㪇
図 10: フレーム切り出しサイズに対する収集率
㪈㪇㪇
㪉㪇㪇
㪊㪇㪇
ಾ䉍಴䈚䉰䉟䉵㩷㪲㪙㫐㫋㪼㪴
㪋㪇㪇
㪌㪇㪇
図 11: フレーム切り出しサイズに対する収集率
7
ニングは行っていないことに注意されたい．
6.3
㪍㪇
実験結果及び考察
tcpdump に対して 10,000,000 個 (約 40 秒) の Ethernet
フレームを，SPACE 実験システムに対しては 150,000,000
個 (約 10 分) の Ethernet フレームをそれぞれワイヤー
レートで発生させた．このとき，フレームの先頭から 54B，
80B，96B，128B，256B を切り出した場合について，そ
れぞれ収集率を測定した．
6.3.1 評価 1: システム全体の評価
図 10 に HDD へ記録した場合のフレーム切り出しサ
イズに対する収集率を示す．図 10 より，tcpdump では，
NIC，フレーム切り出しサイズに関係なくフレームの取
りこぼしが発生しているのに対し，SPACE 実験システム
では，先頭から 54B，80B を切り出した場合には，フレー
ムの取りこぼしが発生していない．また，SPACE 実験シ
ステムにおいてフレームの先頭から 54B を切り出した場
合については，3,600,000,000 個 (約 4 時間) のワイヤー
レートトラヒックを収集した場合にも収集率が 100%で
あった．
このことから，現段階の実装でも，1Gbps ネットワー
クにおいて TCP/IP ヘッダ情報を収集する場合には，
汎用 PC と SPACE–NIC により，定常的な観測が可能
であるといえる．また，パケット選択機能を用いて約
11%(54B/500B) 程度にキャプチャするパケットを選択
することにより，パケット全体を定常的にキャプチャす
ることが可能であるといえる．
6.3.2 評価 2: PCI バスの転送速度の限界の評価
図 11 に HDD へ書き出さなかった場合のフレーム切り
出しサイズに対する収集率を示す．図 10 より，SPACE 実
験システムではフレームの取りこぼしなく先頭から 300B
を切り出すことができた．
このことから，評価 1 では HDD への書き込み速度が
ボトルネックとなっているといえる．従って，RAID シ
ステムを構築するなど，HDD への書き込み速度の向上に
より，デバイスドライバの最適化なしに，約 5.5Gbps の
ネットワークへの対応が可能となる．しかし，この場合に
はシステムの大型化，高価格化を考慮する必要がある．一
方，SPACE–NIC のパケット選択機能を用いて 600Mbps
程度にキャプチャするパケットを選択し，SPACE–PC に
おいて，snort などのソフトウェアに処理を引き継ぐと
行った利用も可能である．
–8–
おわりに
本稿では，高速ネットワークの監視のための基本要素
として，速度，場所，時間，条件のスケーラビリティの向
上を目標としたパケットキャプチャシステム SPACE を
提案し，その実現法を述べた．
実験により，提案システムでは 1Gbps ネットワークに
おいてワイヤーレートのトラヒックが発生している場合に
も，汎用 PC と SPACE–NIC を用いて定常的に TCP/IP
ヘッダの収集が可能であることを示した．しかし，最小サ
イズのパケットが長時間連続する場合には，パケットの取
りこぼしが発生する可能性があるため，このような場合
についても評価を行う必要がある．また，試作システムで
は，デバイスドライバや SPACE–PC のプログラムに対
する最適化を行っていないため，これらの最適化も今後
の課題である．さらに，現在実装中である SPACE–NIC
のパケット照合機能を完成させ，パケット選択を行った
場合の適用領域や制限を評価する予定である．
謝辞 SPACE–NIC のハードウェアを開発して頂いた，
吉田松寿氏をはじめとする富士通 VLSI(株) の関係各位
に深く感謝する．
参考文献
[1] 鶴 正人，尾家祐二，“インターネットの特性測定技術とその研究
開発動向”，情報処理学会会誌，vol. 42，no. 2，pp. 192–197，
2001.
[2] T.Hasegawa，T.Ogishi，T.Hasegawa，“A framework for
gigabit–rate packet header collation to realize cost–effective
internet monitoring system”，IPSJ Journal，vol. 42，no. 12，
pp. 3082–3092，Dec. 2001.
[3] アンリツ株式会社, MD1230A, http://www.anritsu.co.jp/.
[4] Finisar Corporation, THGnotebook, http://www.qualitynet.co.jp/.
[5] 東陽テクニカ, AX/4000, http://www.toyo-spirent.com/.
[6] N. Takahashi，“A systolic sieve array for real–time packet
classification”，IPSJ Journal，vol. 42，no. 2，pp. 166–177，
Feb. 2001.
[7] P. Gupta and N. McKeown, “Packet classification on multiple fields,” Proc. ACM SIGCOMM’99, Aug. 1999.
[8] C. Estan and G. Varghese, “New directions in traffic measurement and accounting,” Proc. ACM SIGCOMM’02, Aug.
2002.
[9] G. Iannaccone, C. Diot, I. Graham and N. McKeown, “Monitoring very high speed links,” Proc. ACM SIGCOMM Internet Measurement Workshop, Nov. 2001.
[10] M. Fomenkov, K. Keys, D. Moore and k. claffy, “Longitudinal study of internet traffic from 1998-2001: a view from 20
high performance sites,” Tech. rep., CAIDA, Apr. 2003.