(57)【要約】【課題】  パケットの検索時間を短縮することが可能なパケットログ記録装置を実現する。【解決手段】  ネットワークを伝播するパケットを記録するパケットログ記録装置において、第１の記憶手段と、この第１の記憶手段よりもデータの読み出し速度が低速である第２の記憶手段と、取得したパケットの一部をハッシュ関数を用いてハッシュ値に変換し、このハッシュ値をアドレスとみなして第１の記憶手段に形成された記録テーブルにビットを立てて一定周期毎に順次記録すると共に第２の記憶手段に形成されたサマリテーブルの同一アドレスに各記録テーブルの値を積算する演算制御手段とを設ける。【選択図】                    図１
2005159794.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを伝播するパケットを記録するパケットログ記録装置において、
第１の記憶手段と、
この第１の記憶手段よりもデータの読み出し速度が低速である第２の記憶手段と、
取得したパケットの一部をハッシュ関数を用いてハッシュ値に変換し、このハッシュ値をアドレスとみなして前記第１の記憶手段に形成された記録テーブルにビットを立てて一定周期毎に順次記録すると共に前記第２の記憶手段に形成されたサマリテーブルの同一アドレスに各記録テーブルの値を積算する演算制御手段と
を備えたことを特徴とするパケットログ記録装置。
【請求項２】
前記演算制御手段が、
集約数毎に前記サマリテーブルを順次切り換えて各記録テーブルの値を順次積算することを特徴とする
請求項１記載のパケットログ記録装置。
【請求項３】
前記演算制御手段が、
前記集約数毎に前記第１の記憶手段に形成された前記集約数と等しい枚数の前記記録テーブルをクリアすることを特徴とする
請求項２記載のパケットログ記録装置。
【請求項４】
前記演算制御手段が、
前記記録テーブルの値をグループ化して前記サマリテーブルに積算することを特徴とする
請求項１乃至請求項３のいずれかに記載のパケットログ記録装置。
【請求項５】
パケット経路追跡システムに適用したことを特徴とする
請求項１乃至請求項４のいずれかに記載のパケットログ記録装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを伝播するパケットを記録するパケットログ記録装置に関し、特に、パケットの検索時間を短縮することが可能なパケットログ記録装置に関する。
【背景技術】
【０００２】
従来のネットワークを伝播するパケットを記録するパケットログ記録装置に関連する先行技術文献としては次のようなものがある。
【０００３】
【特許文献１】特開２００１−０５３８０１号公報
【特許文献２】特開２００３−２９８６４８号公報
【特許文献３】特開２００３−２９８６５１号公報
【０００４】
従来のインターネット上ではパケットを連続してターゲットに送信して当該ターゲットの提供するサービスを停止等させるＤｏＳ攻撃（Denial of Service attack：サービス停止攻撃：以下、単にＤｏＳと呼ぶ。）が問題になっている。
【０００５】
特に、複数地点から一斉に一つのターゲットに対してＤｏＳ攻撃を行うＤＤｏＳ（Distributed ＤｏＳ：分散型ＤｏＳ：以下、単にＤＤｏＳと呼ぶ。）が大きな問題になっている。
【０００６】
このため、このようなＤＤｏＳ攻撃等を防止するため、不正なパケットの発信源を特定するパケット経路追跡システムが考案されている。
【０００７】
図７はこのような従来のパケット経路追跡システムの一例を示す構成ブロック図である。図７において１は攻撃者（アタッカー）が操作する端末、２はＤＤｏＳ攻撃等のターゲットとなるサーバ、３及び４はＩＳＰ（Internet Service Provider：インターネットサービス提供業者：以下、単にＩＳＰと呼ぶ。）、５，６，７及び８はルータ、９，１０及び１１は伝播するパケットの情報を記録するパケットログ記録装置である。
【０００８】
端末１はルータ５を介してＩＳＰ３に接続され、ＩＳＰ３はルータ６及びルータ７を介してＩＳＰ４に接続される。また、サーバ２はルータ８を介してＩＳＰ４に接続される。
【０００９】
さらに、端末１とルータ５との間の回線にはパケットログ記録装置９が接続され、ルータ６とルータ７との間の回線にはパケットログ記録装置１０が接続され、サーバ２とルータ８との間の回線にはパケットログ記録装置１１が接続される。
【００１０】
ここで、図７に示す従来のパケット経路追跡システムの動作を図８及び図９を用いて説明する。図８は攻撃者（アタッカー）の攻撃経路を示す説明図、図９はパケットの記録状況を説明する説明図である。
【００１１】
図８中”ＡＴ０１”に示すように攻撃者（アタッカー）は端末１からＩＳＰ３及びＩＳＰ４を介してターゲットであるサーバ２に対してＤｏＳ攻撃等を行う。
【００１２】
一方、パケットログ記録装置９，１０及び１１は接続された回線を伝播するパケットを取得して記憶手段に順次記録して行く。
【００１３】
例えば、図９中”ＬＧ１１”、”ＬＧ１２”及び”ＬＧ１３”に示すようにパケットログ記録装置９，１０及び１１はＤｏＳ攻撃のために伝播する不正なパケットを取得して記憶手段に順次記録する。
【００１４】
そして、ＤｏＳ攻撃等を受けたサーバ２が受信した不正なパケットと、パケットログ記録装置９，１０及び１１にそれぞれ記録されたパケットを比較して当該不正なパケットが伝播した経路を特定する。
【００１５】
例えば、図８に示すＤｏＳ攻撃等に用いられた不正なパケットはパケットログ記録装置９，１０及び１１に記録されているので図８中”ＡＴ０１”に示すような不正なパケットの伝播経路を特定することが可能になる。
【００１６】
但し、監視している回線に伝播するパケットの全ての情報を順次記録するために、記憶手段には膨大な記憶容量が必要になるため、効率良くパケットの情報を保持する方法が考案されている。
【００１７】
図１０はこのようなパケットログ記録装置の具体例を示す構成ブロック図であり、１２はＣＰＵ（Central Processing Unit）等の演算制御手段、１３はＲＡＭ（Random Access Memory）等の記憶手段である。
【００１８】
観測点である回線からの入力は演算制御手段１２に接続され、演算制御手段１２の出力は記憶手段１３に接続される。
【００１９】
ここで、図１０に示すパケットログ記録装置の動作を図１１を用いて説明する。図１１は取得したパケットの記録方法を説明する説明図である。
【００２０】
図１０中”ＬＧ２１”に示すように観測点である回線から入力されたパケットは演算制御手段１２に取り込まれ、ＩＰ（Internet Protocol）パケットの中で伝播中に不変である部分等を抽出する。
【００２１】
そして、演算制御手段１２は抽出された情報をハッシュ関数を用いてハッシュ値に変換し、このハッシュ値を記憶手段１３のアドレスとみなして、該当するアドレスにビットを立てる等してある特定のパケットが伝播したことを記録する。
【００２２】
ここで、ハッシュ関数とは、原文から固定長の疑似乱数（ハッシュ値）を生成する関数であって、このハッシュ関数は不可逆な一方向関数を含むために生成されたハッシュ値から元の原文を再現することはできない。また、同じハッシュ値となる異なるデータを作成することは極めて困難である。
【００２３】
例えば、演算制御手段１２が、図１１中”ＰＩ３１”に示すような取得したパケットから抽出された伝播中に不変である部分にハッシュ関数を適用して、図１１中”ＨＶ３１”に示すようなハッシュ値（例えば、ＸＸＸＸＨ：１６ビットの１６進数表現）を得られた場合を想定する。
【００２４】
この場合、演算制御手段１２は得られたハッシュ値（ＸＸＸＸＨ）を記憶手段１３のアドレスとみなして、”ＸＸＸＸＨ”のアドレスに図１１中”ＷＤ３１”に示すようにデータを書き込む。
【００２５】
例えば、データの書込み方法としては”００００００００Ｂ（８ビットデータ）”から”０００００００１Ｂ”等（ビットを立てる）に変更することによってある特定のパケットが伝播したことを記録する。
【００２６】
そして、ＤｏＳ攻撃等を受けたサーバが受信した不正なパケットに前記ハッシュ関数を適用して得られたハッシュ値に対応する記憶手段１３のアドレスにビットが立っていれば不正なパケットがパケットログ記録装置が接続された回線を伝播したことになる。
【００２７】
この結果、図１０に示すパケットログ記録装置ではパケットの情報を全て記憶手段に記録するのではなく、パケットの一部分にハッシュ関数を適用して得られたハッシュ値に対応する記憶手段のアドレスに記録する（ビットを立てる）ことにより、記憶手段の記憶容量は小さくて良く、効率良くパケットの情報を保持することが可能である。
【００２８】
但し、図１０に示すパケットログ記録装置では、時間の経過に伴い記憶手段１３に立っているビット数が増加して、場合によっては全てのビットが立ってしまい、パケットログ記録装置が接続された回線を伝播したパケットの頻度（伝播数）を把握することができなくなってしまう。
【００２９】
このため、演算制御手段１２は、記憶手段１３に複数の記録テーブルを作成して一定周期毎に当該記録テーブルを順次切り換えて行くことにより、パケットログ記録装置が接続された回線を伝播したパケットの頻度（伝播数）を把握することが可能になる。
【発明の開示】
【発明が解決しようとする課題】
【００３０】
しかし、このような方法であっても時間の経過に伴い記録テーブルが増加することになり、高速ネットワークにパケットログ記録装置を適用した場合、記録テーブルの数が膨大になり、パケットの検索時間が極めて長くなってしまうと言った問題点があった。
【００３１】
さらに、記録テーブルの数が膨大になった場合、ＲＡＭ等の高速の記憶手段に全ての記録テーブルを記憶させておくことは現実的ではなく、ハードディスク等の低速な記憶手段（２次記憶装置）に保管されざるを得ない。
【００３２】
この場合、ハードディスク等の低速な記憶手段はＲＡＭ等の高速の記憶手段と比較して、データの読み出し速度が格段に遅く、加えて、ディスクのシーク（目的のトラックにヘッドを移動させる動作）が行われると、１つの記録テーブルの検索に”ミリ秒”単位の時間がかかることになる。
【００３３】
例えば、記録テーブルの総数が”８０００枚”、１つの記録テーブルの検索が”５〜１０ミリ秒”であると想定すると、１つのパケットを検索するに要する時間”Ｔｓ”は、
Ｔｓ＝（５〜１０）×８０００＝４０〜８０秒      （１）
となってしまい、このような検索時間では実用に適さなくなってしまう。
従って本発明が解決しようとする課題は、パケットの検索時間を短縮することが可能なパケットログ記録装置を実現することにある。
【課題を解決するための手段】
【００３４】
このような課題を達成するために、本発明のうち請求項１記載の発明は、
ネットワークを伝播するパケットを記録するパケットログ記録装置において、
第１の記憶手段と、この第１の記憶手段よりもデータの読み出し速度が低速である第２の記憶手段と、取得したパケットの一部をハッシュ関数を用いてハッシュ値に変換し、このハッシュ値をアドレスとみなして前記第１の記憶手段に形成された記録テーブルにビットを立てて一定周期毎に順次記録すると共に前記第２の記憶手段に形成されたサマリテーブルの同一アドレスに各記録テーブルの値を積算する演算制御手段とを備えたことにより、パケットの検索時間を短縮することが可能になる。
【００３５】
請求項２記載の発明は、
請求項１記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
集約数毎に前記サマリテーブルを順次切り換えて各記録テーブルの値を順次積算することにより、パケットの検索時間を短縮することが可能になる。
【００３６】
請求項３記載の発明は、
請求項２記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
集約数毎に前記第１の記憶手段に形成された前記集約数と等しい枚数の前記記録テーブルをクリアすることにより、第１の記憶手段のコストを抑えることが可能になる。
【００３７】
請求項４記載の発明は、
請求項１乃至請求項３のいずれかに記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
前記記録テーブルの値をグループ化して前記サマリテーブルに積算することにより、パケットの伝播数を各グループ単位で把握することが可能になる。
【００３８】
請求項５記載の発明は、
請求項１乃至請求項４のいずれかに記載の発明であるパケットログ記録装置において、
パケット経路追跡システムに適用したことにより、パケットの検索時間を短縮することが可能になる。
【発明の効果】
【００３９】
本発明によれば次のような効果がある。
請求項１，２及び請求項５の発明によれば、取得したパケットの一部をハッシュ関数を用いてハッシュ値に変換し、このハッシュ値をアドレスとみなして記録テーブルにビットを立てて一定周期毎に順次記録すると共にサマリテーブルの同一アドレスに各記録テーブルの値を積算することにより、パケットの検索時間を短縮することが可能になる。
【００４０】
また、請求項３の発明によれば、集約数毎に第１の記憶手段に形成された集約数と等しい枚数の記録テーブルをクリアすることにより、第１の記憶手段のコストを抑えることが可能になる。
【００４１】
また、請求項４の発明によれば、記録テーブルの値をグループ化してサマリテーブルに集約することにより、パケットの伝播数を各グループ単位で把握することが可能になる。
【発明を実施するための最良の形態】
【００４２】
以下本発明を図面を用いて詳細に説明する。図１は本発明に係るパケットログ記録装置の一実施例を示す構成ブロック図である。図１において１４はＣＰＵ等の演算制御手段、１５はＲＡＭ等の読み出し速度が高速の記憶手段、１６はハードディスク等の読み出し速度が低速の記憶手段である。
【００４３】
観測点である回線からの入力は演算制御手段１４に接続され、演算制御手段１４の入出力は記憶手段１５に接続される。また、演算制御手段１４の入出力は記憶手段１６に接続される。
【００４４】
ここで、図１に示す実施例の動作を図２、図３及び図４を用いて説明する。但し、図１１に示すパケットの記録方法と重複する部分の説明は省略する。図２は演算制御手段１４の動作を説明するフロー図、図３及び図４は記録テーブルとサマリテーブルとの関係を説明する説明図である。
【００４５】
図２中”Ｓ００１”において演算制御手段１４は、取得したパケットに基づきハッシュ値を求める。
【００４６】
例えば、観測点である回線から入力されたパケットは演算制御手段１４に取り込まれ、ＩＰパケットの中で伝播中に不変である部分等を抽出し、抽出された情報をハッシュ関数を用いてハッシュ値に変換する。
【００４７】
そして、図２中”Ｓ００２”において演算制御手段１４は、求めたハッシュ値を記憶手段１５に形成された記憶テーブルのアドレスとみなして、該当するアドレスにビットを立てる等してある特定のパケットが伝播したことを記録する。
【００４８】
さらに、図２中”Ｓ００３”において演算制御手段１４は、求めたハッシュ値を記憶手段１６に形成されたサマリテーブルのアドレスとみなして、該当するアドレスにビットを加算、言い換えれば、ビットを積算等してある特定のパケットが何回伝播したかを記録する。
【００４９】
例えば、記憶手段１６に形成されたサマリテーブルの前記ハッシュ値が示すアドレスに既に”１（＝０００００００１Ｂ：８ビットデータ）”が記憶されていれば、当該アドレスの値をインクリメント（データを１だけ増加させる）して”２（＝００００００１０Ｂ：８ビットデータ）”とする。
【００５０】
具体的には、図３中”ＰＴ４１”に示す記憶手段１５に形成された記録テーブルのアドレス（ハッシュ値に相当）にビットが立った場合、図３中”ＡＤ４１”に示すように記憶手段１６に形成されたサマリテーブルの同一アドレス（ハッシュ値に相当）のデータをインクリメントする。
【００５１】
図２中”Ｓ００４”において演算制御手段１４は、予め設定されている一定周期を経過したか否かを判断し、もし、一定時間を経過していないと判断した場合には、図２中”Ｓ００１”のステップに戻る。
【００５２】
もし、図２中”Ｓ００４”において一定時間を経過したと判断した場合には、図２中”Ｓ００５”において演算制御手段１４は、記憶手段１５に形成されている記録テーブルを切り換える。
【００５３】
具体的には、これまで記録してきた記録テーブルを退避させると共に新規の記録テーブルに対してハッシュ値をアドレスとみなして、ビットを立てる等してある特定のパケットが伝播したことを記録する。
【００５４】
例えば、図３中”ＲＴ４１”、”ＲＴ４２”，”ＲＴ４３”及び”ＲＴ４４”は記憶手段１５に形成されている記録テーブルであり、一定時間の経過に伴い、図３中”ＲＴ４１”、”ＲＴ４２”、”ＲＴ４３”及び”ＲＴ４４”の順番で順次伝播したパケットが記録されて行く。
【００５５】
そして、図２中”Ｓ００６"において演算制御手段１４は、予め設定されたサマリテーブルの最大の集約数（例えば、１２８枚）に到達したか否かを判断し、もし、集約数に到達していない場合には図２中”Ｓ００１”のステップに戻る。
【００５６】
もし、図２中”Ｓ００６”において集約数に到達していると判断した場合には、図２中”Ｓ００７”において演算制御手段１４は、記憶手段１６に形成されているサマリテーブルを切り換える。
【００５７】
具体的には、これまで記録してきたサマリテーブルを退避させると共に新規のサマリテーブルに対してハッシュ値をアドレスとみなして、ビットを加算、言い換えれば、ビットを積算等してある特定のパケットが何回伝播したかを記録する。
【００５８】
演算制御手段１４が、図２に示すような動作を繰り返すことにより、時間の経過と共に図４中”ＳＴ５１”、”ＳＴ５２”及び”ＳＴ５３”に示すようにサマリテーブルが順次作成されて行く。
【００５９】
すなわち、時間の経過と共に作成された図４中”ＲＴ５１”、”ＲＴ５２”、”ＲＴ５３”及び”ＲＴ５４”に示す記録テーブルの内容は図４中”ＳＴ５１”に示すサマリテーブルに集約される。同様に、図４中”ＲＴ５５”〜”ＲＴ５６”及び”ＲＴ５７”〜”ＲＴ５８”の記録テーブルはそれぞれ図４中”ＳＴ５２”及び”ＳＴ５３”に示すサマリテーブルに集約されることになる。
【００６０】
このように、集約された１枚のサマリテーブルを検索することにより、集約された記録テーブルのうち何枚にパケットが記録されているのかを即座に把握することができる。
【００６１】
例えば、図４中”ＰＴ５１”に示す記憶手段１６に形成されたサマリテーブルのアドレス（ハッシュ値に相当）の値は”５”であり、このため、集約された記録テーブルのうち”５枚”の記録テーブルに、アドレス（ハッシュ値に相当）に対応するパケットが伝播したことが記録されていることが分かる。
【００６２】
同様に、例えば、図４中”ＰＴ５２”及び”ＰＴ５３”に示す記憶手段１６に形成されたサマリテーブルのアドレス（ハッシュ値に相当）の値は”７”及び”０”であり、このため、集約された記録テーブルのうち”７枚”若しくは”０枚”の記録テーブルに、アドレス（ハッシュ値に相当）に対応するパケットが伝播したことが記録されていることが分かる。
【００６３】
さらに、集約された１枚のサマリテーブルを検索することにより、集約数分の記録テーブルを検索したのと同等の検索を行うことができるので、パケットの検索時間を短縮することが可能になる。
【００６４】
例えば、集約数を”１２８”とすれば、図４中”ＳＴ５１”等に示すサマリテーブルを検索することにより、パケットの検索時間は”１／１２８”に短縮されることになる。
【００６５】
この結果、取得したパケットの一部をハッシュ関数を用いてハッシュ値に変換し、このハッシュ値をアドレスとみなして記録テーブルにビットを立てて一定周期毎に順次記録すると共にサマリテーブルの同一アドレスに各記録テーブルの値を積算し、集約数毎にサマリテーブルを順次切り換えて行くことにより、パケットの検索時間を短縮することが可能になる。
【００６６】
なお、図１に示す実施例では、集約数毎にサマリテーブルを順次切り換えながら記録テーブルの値をサマリテーブルに積算（集約）しているが、単純に全ての記録テーブルの値を１つのサマリテーブルに積算（集約）しても勿論構わない。
【００６７】
また、図１に示す実施例では、ただ単に、記録テーブルの値をサマリテーブルに積算（集約）しているが、集約数毎に記憶手段１５に形成された集約数と等しい枚数の記録テーブルをクリア（処分）しても構わない。
【００６８】
この場合には、記憶手段１５の記憶容量は集約数の等しい枚数の記録テーブルを格納するのに十分は容量で済むことになるので、全ての記録テーブルを保存することを想定した場合と比較して、記憶手段１５のコストを抑えることが可能になる。
【００６９】
また、図１に示す実施例では、ただ単に、記録テーブルの値をサマリテーブルに積算（集約）しているが、記録テーブルの値をグループ化して集約しても構わない。図５は記録テーブルの値をサマリテーブルに積算した場合を示す説明図、図６は記録テーブルの値をグループ化して集約した場合を説明する説明図である。
【００７０】
集約数を”１２８”とした場合、図１に示す実施例では、図５中”ＲＴ６１”、”ＲＴ６２”、”ＲＴ６３”及び”ＲＴ６４”に示す１２８枚の記録テーブルは図５中”ＳＴ６１”に示すサマリテーブルに集約される。
【００７１】
この際、図５中”ＳＤ６１”に示すように集約された値は”７ビット（２７ ＝１２８）”の値として積算される。
【００７２】
このように積算された値を検索した場合、１回の検索では、図５中”ＰＴ６１”に示す記憶手段１６に形成されたサマリテーブルのアドレス（ハッシュ値に相当）に対応するパケットの全体（記録テーブル１２８枚分）の伝播数は把握できるものの、どの時間帯の記録テーブルで記録されたものであるかまで把握することができない。
【００７３】
一方、図６は１２８枚の記録テーブルを８分割（１６枚毎）してグループ化し、各グループを”４ビット（２４ ＝１６）”の値として集約している。
【００７４】
すなわち、図６中”ＲＴ７１”、”ＲＴ７２”、”ＲＴ７３”及び”ＲＴ７４”に示す１６枚の記録テーブルは図６中”ＳＧ７１”に示す４ビットに第１のグループとして集約される。
【００７５】
同様に、図６中”ＲＴ７５”〜”ＲＴ７６”に示す１６枚の記録テーブルは図６中”ＳＧ７２”に示す４ビットに第２のグループとして集約され、そして、図６中”ＲＴ７７”〜”ＲＴ７８”に示す１６枚の記録テーブルは図６中”ＳＧ７３”に示す４ビットに第８のグループとして集約される。
【００７６】
このように積算された値を検索した場合、１回の検索であっても、図６中”ＰＴ７１”に示す記憶手段１６に形成されたサマリテーブルのアドレス（ハッシュ値に相当）に対応するパケットの伝播数を、図６中”ＳＧ７１”、”ＳＧ７２”及び”ＳＧ７３”に示す各グループ単位で把握することが可能になる。
【図面の簡単な説明】
【００７７】
【図１】本発明に係るパケットログ記録装置の一実施例を示す構成ブロック図である。
【図２】演算制御手段の動作を説明するフロー図である。
【図３】記録テーブルとサマリテーブルとの関係を説明する説明図である。
【図４】記録テーブルとサマリテーブルとの関係を説明する説明図である。
【図５】記録テーブルの値をサマリテーブルに積算した場合を示す説明図である。
【図６】記録テーブルの値をグループ化して集約した場合を説明する説明図である。
【図７】従来のパケット経路追跡システムの一例を示す構成ブロック図である。
【図８】攻撃者（アタッカー）の攻撃経路を示す説明図である。
【図９】パケットの記録状況を説明する説明図である。
【図１０】パケットログ記録装置の具体例を示す構成ブロック図である。
【図１１】取得したパケットの記録方法を説明する説明図である。
【符号の説明】
【００７８】
１  端末
２  サーバ
３，４  ＩＳＰ
５，６，７，８  ルータ
９，１０，１１  パケットログ記録装置
１２，１４  演算制御手段
１３，１５，１６  記憶手段
【図１】
2005159794.tif 000003
【図２】
2005159794.tif 000004
【図３】
2005159794.tif 000005
【図４】
2005159794.tif 000006
【図５】
2005159794.tif 000007
【図６】
2005159794.tif 000008
【図７】
2005159794.tif 000009
【図８】
2005159794.tif 000010
【図９】
2005159794.tif 000011
【図１０】
2005159794.tif 000012
【図１１】
2005159794.tif 000013