(57)【要約】【課題】ハッシュ値がたまたま一致してしまう確率を低減することが可能なパケットログ記録装置を実現する。【解決手段】ネットワークの複数の観測点を伝播するパケットを記録するパケットログ記録装置において、パケットの情報を記録する記憶手段と、複数の観測点の一を伝播するパケットを取り込み伝播中に不変である部分を抽出してハッシュ関数を適用し、得られたハッシュ値を記憶手段のアドレスとみなしてこのアドレスの特定のビットにデータを書き込むと共にパラメータが予め設定した閾値を超過した場合に１つのパケットに適用するハッシュ関数の数を削減する演算制御手段とを設ける。【選択図】　　　　　　　　　　図１
2004128545.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの複数の観測点を伝播するパケットを記録するパケットログ記録装置において、
前記パケットの情報を記録する記憶手段と、
複数の前記観測点の一を伝播するパケットを取り込み伝播中に不変である部分を抽出してハッシュ関数を適用し、得られたハッシュ値を前記記憶手段のアドレスとみなしてこのアドレスの特定のビットにデータを書き込むと共にパラメータが予め設定した閾値を超過した場合に１つのパケットに適用するハッシュ関数の数を削減する演算制御手段と
を備えたことを特徴とするパケットログ記録装置。
【請求項２】
前記演算制御手段が、
前記パラメータが予め設定した前記閾値を超過した場合に前記記憶手段の記憶容量を増加させることを特徴とする
請求項１記載のパケットログ記録装置。
【請求項３】
前記演算制御手段が、
前記記憶手段の一部をログ記憶領域としておき、必要に応じて未使用の記憶領域をログの記憶領域として用いることによって前記記憶手段の記憶容量を増加させることを特徴とする
請求項２記載のパケットログ記録装置。
【請求項４】
前記演算制御手段が、
前記記憶手段の他に未使用の記憶手段を別途準備しておき、必要に応じて未使用の記憶手段をログの記憶領域として用いることによって実質的に前記記憶手段の記憶容量を増加させることを特徴とする
請求項２記載のパケットログ記録装置。
【請求項５】
前記演算制御手段が、
前記記憶手段内に複数のログの記憶領域を設けて当該複数のログの記憶領域の切り替えて使用する場合には、前記パラメータが予め設定した前記閾値を超過した場合に当該切り替え周期を変えることを特徴とする
請求項１記載のパケットログ記録装置。
【請求項６】
前記演算制御手段が、
前記記憶手段のデータの埋まり率を前記パラメータとして予め設定した前記閾値と比較することを特徴とする
請求項１乃至請求項５のいずれかに記載のパケットログ記録装置。
【請求項７】
前記演算制御手段が、
前記埋まり率から演算して求めた正解確率を前記パラメータとして予め設定した前記閾値と比較することを特徴とする
請求項６記載のパケットログ記録装置。
【請求項８】
前記演算制御手段が、
パケットの通過量を前記パラメータとして予め設定した前記閾値と比較することを特徴とする
請求項１乃至請求項５のいずれかに記載のパケットログ記録装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワークを伝播するパケットを記録してパケットの伝播経路を追跡するパケット経路追跡システムで用いられるパケットログ記録装置に関し、特にハッシュ値がたまたま一致してしまう確率を低減することが可能なパケットログ記録装置に関する。
【０００２】
【従来の技術】
従来のネットワークを伝播するパケットを記録してパケットの伝播経路を追跡するパケット経路追跡システムで用いられるパケットログ記録装置に関連する先行技術文献としては次のようなものがある。
【０００３】
【特許文献１】
特開平１０−１６４０６４号公報
【０００４】
従来のインターネット上ではパケットを連続してターゲットに送信して当該ターゲットの提供するサービスを停止等させるＤｏＳ攻撃（Ｄｅｎｉａｌ　ｏｆ　Ｓｅｒｖｉｃｅ　ａｔｔａｃｋ：サービス停止攻撃：以下、単にＤｏＳと呼ぶ。）が問題になっている。
【０００５】
特に、複数地点から一斉に一つのターゲットに対してＤｏＳ攻撃を行うＤＤｏＳ（Ｄｉｓｔｒｉｂｕｔｅｄ　ＤｏＳ：分散型ＤｏＳ：以下、単にＤＤｏＳと呼ぶ。）が大きな問題になっている。
【０００６】
このため、このようなＤＤｏＳ攻撃等を防止するため、不正なパケットの発信源を特定するパケット経路追跡システムが考案されている。
【０００７】
図４はこのような従来のパケット経路追跡システムの一例を示す構成ブロック図である。図４において１は攻撃者（アタッカー）が操作する端末、２はＤＤｏＳ攻撃等のターゲットとなるサーバ、３及び４はＩＳＰ（Ｉｎｔｅｒｎｅｔ　Ｓｅｒｖｉｃｅ　Ｐｒｏｖｉｄｅｒ：インターネットサービス提供業者：以下、単にＩＳＰと呼ぶ。）、５，６，７及び８はルータ、９，１０及び１１は伝播するパケットの情報を記録するパケットログ記録装置である。
【０００８】
端末１はルータ５を介してＩＳＰ３に接続され、ＩＳＰ３はルータ６及びルータ７を介してＩＳＰ４に接続される。また、サーバ２はルータ８を介してＩＳＰ４に接続される。
【０００９】
さらに、端末１とルータ５との間の回線にはパケットログ記録装置９が接続され、ルータ６とルータ７との間の回線にはパケットログ記録装置１０が接続され、サーバ２とルータ８との間の回線にはパケットログ記録装置１１が接続される。
【００１０】
ここで、図４に示す従来のパケット経路追跡システムの動作を図５及び図６を用いて説明する。図５は攻撃者（アタッカー）の攻撃経路を示す説明図、図６はパケットの記録状況を説明する説明図である。
【００１１】
図５中”ＡＴ０１”に示すように攻撃者（アタッカー）は端末１からＩＳＰ３及びＩＳＰ４を介してターゲットであるサーバ２に対してＤｏＳ攻撃等を行う。
【００１２】
一方、パケットログ記録装置９，１０及び１１は接続された回線を伝播するパケットを取得して記憶手段に順次記録して行く。
【００１３】
例えば、図６中”ＬＧ１１”、”ＬＧ１２”及び”ＬＧ１３”に示すようにパケットログ記録装置９，１０及び１１はＤｏＳ攻撃のために伝播する不正なパケットを取得して記憶手段に順次記録する。
【００１４】
そして、ＤｏＳ攻撃等を受けたサーバ２が受信した不正なパケットと、パケットログ記録装置９，１０及び１１にそれぞれ記録されたパケットを比較して当該不正なパケットが伝播した経路を特定する。
【００１５】
例えば、図５に示すＤｏＳ攻撃等に用いられた不正なパケットはパケットログ記録装置９，１０及び１１に記録されているので図５中”ＡＴ０１”に示すような不正なパケットの伝播経路を特定することが可能になる。
【００１６】
但し、監視している回線に伝播するパケットの全ての情報を順次記録するために、記憶手段には膨大な記憶容量が必要になるため、効率良くパケットの情報を保持する方法が考案されている。
【００１７】
図７はこのようなパケットログ記録装置の具体例を示す構成ブロック図であり、１２は演算制御手段、１３は記憶手段である。
【００１８】
観測点である回線からの入力は演算制御手段１２に接続され、演算制御手段１２の出力は記憶手段１３に接続される。
【００１９】
ここで、図７に示すパケットログ記録装置の動作を図８を用いて説明する。図８は取得したパケットの記録方法を説明する説明図である。
【００２０】
図７中”ＬＧ２１”に示すように観測点である回線から入力されたパケットは演算制御手段１２に取り込まれ、ＩＰ（Ｉｎｔｅｒｎｅｔ　Ｐｒｏｔｏｃｏｌ）パケットの中で伝播中に不変である部分等を抽出する。
【００２１】
そして、演算制御手段１２は抽出された情報をハッシュ関数を用いてハッシュ値に変換し、このハッシュ値を記憶手段１３のアドレスとみなして、該当するアドレスにビットを立てる等してある特定のパケットが伝播したことを記録する。
【００２２】
ここで、ハッシュ関数とは、原文から固定長の疑似乱数（ハッシュ値）を生成する関数であって、このハッシュ関数は不可逆な一方向関数を含むために生成されたハッシュ値から元の原文を再現することはできない。また、同じハッシュ値となる異なるデータを作成することは極めて困難である。
【００２３】
例えば、演算制御手段１２が、図８中”ＰＩ３１”に示すような取得したパケットから抽出された伝播中に不変である部分にハッシュ関数を適用して、図８中”ＨＶ３１”に示すようなハッシュ値（例えば、ＸＸＸＸＨ：１６ビットの１６進数表現）を得られた場合を想定する。
【００２４】
この場合、演算制御手段１２は得られたハッシュ値（ＸＸＸＸＨ）を記憶手段１３のアドレスとみなして、”ＸＸＸＸＨ”のアドレスに図８中”ＷＤ３１”に示すようにデータを書き込む。
【００２５】
例えば、データの書込み方法としては”００００００００Ｂ（８ビットデータ）”から”０００００００１Ｂ”等（ビットを立てる）に変更することによってある特定のパケットが伝播したことを記録する。
【００２６】
そして、ＤｏＳ攻撃等を受けたサーバが受信した不正なパケットに前記ハッシュ関数を適用して得られたハッシュ値に対応する記憶手段１３のアドレスにビットが立っていれば不正なパケットがパケットログ記録装置が接続された回線を伝播したことになる。
【００２７】
この結果、図７に示すパケットログ記録装置ではパケットの情報を全て記憶手段に記録するのではなく、パケットの一部分にハッシュ関数を適用して得られたハッシュ値に対応する記憶手段のアドレスに記録する（ビットを立てる）ことにより、記憶手段の記憶容量は小さくて良く、効率良くパケットの情報を保持することが可能である。
【００２８】
また、１つのパケットに対して複数のハッシュ関数を適用することにより、言い換えれば、１つのパケットに対して記憶手段１３の複数箇所のアドレスにデータを書き込んでおくことにより、不正なパケットをより確実に記録することが可能になる。
【００２９】
【発明が解決しようとする課題】
しかし、図７に示すパケットログ記録装置では、ＩＰパケットの中で伝播中に不変である部分等を抽出してハッシュ関数を用いてハッシュ値に変換し、このハッシュ値を記憶手段のアドレスとみなしてデータの書き込み行っているが、全く異なるＩＰパケットであってもたまたま変換されたハッシュ値が一致してしまう可能性が僅かながら存在する。
【００３０】
このため、ＤｏＳ攻撃等を受けたサーバが受信した不正なパケットに前記ハッシュ関数を適用して得られたハッシュ値に対応する記憶手段１３のアドレスにビットが立っていても、当該不正なパケットではない可能性も否定できず、また、当該不正なパケットであるか否かを判断することもできないと言った問題点があった。
従って本発明が解決しようとする課題は、ハッシュ値がたまたま一致してしまう確率を低減することが可能なパケットログ記録装置を実現することにある。
【００３１】
【課題を解決するための手段】
このような課題を達成するために、本発明のうち請求項１記載の発明は、
ネットワークの複数の観測点を伝播するパケットを記録するパケットログ記録装置において、
前記パケットの情報を記録する記憶手段と、複数の前記観測点の一を伝播するパケットを取り込み伝播中に不変である部分を抽出してハッシュ関数を適用し、得られたハッシュ値を前記記憶手段のアドレスとみなしてこのアドレスの特定のビットにデータを書き込むと共にパラメータが予め設定した閾値を超過した場合に１つのパケットに適用するハッシュ関数の数を削減する演算制御手段とを備えたことにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３２】
請求項２記載の発明は、
請求項１記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
前記パラメータが予め設定した前記閾値を超過した場合に前記記憶手段の記憶容量を増加させることにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３３】
請求項３記載の発明は、
請求項２記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
前記記憶手段の一部をログ記憶領域としておき、必要に応じて未使用の記憶領域をログの記憶領域として用いることによって前記記憶手段の記憶容量を増加させることにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３４】
請求項４記載の発明は、
請求項２記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
前記記憶手段の他に未使用の記憶手段を別途準備しておき、必要に応じて未使用の記憶手段をログの記憶領域として用いることによって実質的に前記記憶手段の記憶容量を増加させることにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３５】
請求項５記載の発明は、
請求項１記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
前記記憶手段内に複数のログの記憶領域を設けて当該複数のログの記憶領域の切り替えて使用する場合には、前記パラメータが予め設定した前記閾値を超過した場合に当該切り替え周期を変えることにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３６】
請求項６記載の発明は、
請求項１乃至請求項５のいずれかに記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
前記記憶手段のデータの埋まり率を前記パラメータとして予め設定した前記閾値と比較することにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３７】
請求項７記載の発明は、
請求項６記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
前記埋まり率から演算して求めた正解確率を前記パラメータとして予め設定した前記閾値と比較することにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３８】
請求項８記載の発明は、
請求項１乃至請求項５のいずれかに記載の発明であるパケットログ記録装置において、
前記演算制御手段が、
パケットの通過量を前記パラメータとして予め設定した前記閾値と比較することにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００３９】
【発明の実施の形態】
以下本発明を図面を用いて詳細に説明する。図１は本発明に係るパケット経路追跡システムのログ記録装置の一実施例を示す構成ブロック図である。
【００４０】
図１において１３は図７と同一符号を付してあり、１２ａは演算制御手段である。観測点である回線からの入力は演算制御手段１２ａに接続され、演算制御手段１２ａの出力は記憶手段１３に接続される。
【００４１】
ここで、図１に示す実施例の動作を図２及び図３を用いて説明する。図２は演算制御手段１２ａの動作を説明するフロー図、図３は記憶手段１３の状況の一例を示す説明図である。
【００４２】
全く異なるＩＰパケットであってもたまたま変換されたハッシュ値が一致してしまう確率はログを記録する記憶手段１３にデータが埋まってゆくほど高くなるため、記憶手段１３におけるデータの埋まり率が大きくなることを防止することにより、ハッシュ値がたまたま一致してしまう確率を低減させる。
【００４３】
すなわち、図２中”Ｓ００１”において演算制御手段１２ａは記憶手段１３の状況を検索して記憶手段１３に記録されているデータの数を取得する。
【００４４】
例えば、図３に示す記憶手段１３の状況から、図３中”ＳＤ０１”，”ＳＤ０２”，”ＳＤ０３”，”ＳＤ０４”，”ＳＤ０５”，”ＳＤ０６”及び”ＳＤ０７”に示すアドレス部分にデータが書き込まれているのでそのデータ数を取得する。
【００４５】
そして、図２中”Ｓ００２”において演算制御手段１２ａは取得した記憶手段１３に記録されているデータの数を記憶手段１３の最大記録数で除算して埋まり率を求める。
【００４６】
図２中”Ｓ００３”において演算制御手段１２ａが求めた埋まり率が予め設定した閾値を超過した否かを判断し、もし、埋まり率が閾値を超過した場合には、図２中”Ｓ００４”において演算制御手段１２ａは１つのパケットに適用するハッシュ関数の数を減少させる。
【００４７】
例えば、演算制御手段１２ａが１つのパケットに対して３つのハッシュ関数を適用して記憶手段１３の３箇所のアドレスにデータを書き込んでいた場合、適用するハッシュ関数の数を２つに削減する。
【００４８】
すなわち、１つのパケットに適用していたハッシュ関数の数を削減することにより、記憶手段１３に書き込まれるアドレス数が減少して、記憶手段１３の埋まり率が大きくなることが防止され、ハッシュ値がたまたま一致してしまう確率を低減させることが可能になる。
【００４９】
この結果、演算制御手段１２ａがログを記録する記憶手段１３のデータの埋まり率を取得して予め設定した閾値を超過した場合に１つのパケットに適用するハッシュ関数の数を削減して埋まり率が大きくなることを防止することにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【００５０】
なお、図１に示す実施例ではログを記録する記憶手段１３のデータの埋まり率を取得して予め設定した閾値を超過した場合に１つのパケットに適用するハッシュ関数の数を削減しているが、記憶手段１３の記憶容量を増加させることにより、埋まり率が大きくなることを防止しても構わない。
【００５１】
この場合、大きな記憶容量の記憶手段１３の一部をログ記憶領域としておき、必要に応じて未使用の記憶領域をログの記憶領域として用いることによって記憶手段１３の記憶容量を増加させても良い。
【００５２】
或いは、記憶手段１３の他に未使用の記憶手段を別途準備しておき、必要に応じて未使用の記憶手段をログの記憶領域として用いることによって実質的に記憶手段１３の記憶容量を増加させても良い。
【００５３】
また、図１に示す実施例ではログを記録する記憶手段１３のデータの埋まり率を取得して予め設定した閾値を超過した場合に１つのパケットに適用するハッシュ関数の数を削減しているが、記憶手段１３内に複数のログの記憶領域を設けて当該複数のログの記憶領域の切り替え使用する場合には、当該切り替え周期を変えることにより、埋まり率が大きくなることを防止しても構わない。
【００５４】
また、図１に示す実施例ではログを記録する記憶手段１３のデータの埋まり率に基づき１つのパケットに適用するハッシュ関数の数を削減等しているが、パケットの通過量に基づき１つのパケットに適用するハッシュ関数の数を削減等の処理をしても構わない。
【００５５】
また、埋まり率を”Ａ”とした場合、演算制御手段１２ａで”（１−Ａ）×１００［％］”等の演算をして、これを正解確率とし、当該正解確率に基づき１つのパケットに適用するハッシュ関数の数を削減等の処理をしても構わない。
【００５６】
また、図２に示す説明に際しては演算制御手段１２ａは記憶手段１３の状況を検索している旨記載しているが、記憶手段１３に新たに記録する回数を予めカウントしておいて、当該カウント値を参照しても構わない。
【００５７】
【発明の効果】
以上説明したことから明らかなように、本発明によれば次のような効果がある。
請求項１，２，３，４，５，６，７及び請求項８の発明によれば、演算制御手段がログを記録する記憶手段のデータの埋まり率等のパラメータを取得して予め設定した閾値を超過した場合に１つのパケットに適用するハッシュ関数の数を削減等して埋まり率が大きくなることを防止することにより、ハッシュ値がたまたま一致してしまう確率を低減することが可能になる。
【図面の簡単な説明】
【図１】本発明に係るパケット経路追跡システムのログ記録装置の一実施例を示す構成ブロック図である。
【図２】演算制御手段の動作を説明するフロー図である。
【図３】記憶手段の状況の一例を示す説明図である。
【図４】従来のパケット経路追跡システムの一例を示す構成ブロック図である。
【図５】攻撃者（アタッカー）の攻撃経路を示す説明図である。
【図６】パケットの記録状況を説明する説明図である。
【図７】パケットログ記録装置の具体例を示す構成ブロック図である。
【図８】取得したパケットの記録方法を説明する説明図である。
【符号の説明】
１　端末
２　サーバ
３，４　ＩＳＰ
５，６，７，８　ルータ
９，１０，１１　パケットログ記録装置
１２，１２ａ　演算制御手段
１３　記憶手段
【図１】
2004128545.tif 000003
【図２】
2004128545.tif 000004
【図３】
2004128545.tif 000005
【図４】
2004128545.tif 000006
【図５】
2004128545.tif 000007
【図６】
2004128545.tif 000008
【図７】
2004128545.tif 000009
【図８】
2004128545.tif 000010