(57)【要約】【課題】高頻度のデクリメントを必要としないブルームフィルタを用いたデータ判別を、少ない記憶容量で実現することを課題とする。【解決手段】本発明は、入力データに複数のハッシュ関数を適用することにより得られるハッシュ値の組をブルームフィルタにおける対応する要素の値と比較することにより、入力データが所定のデータ集合に属するか否かを判別するデータ判別装置である。ブルームフィルタの各要素それぞれは複数のビットを有する。所定のデータ集合に新たなデータを追加してブルームフィルタを更新する場合、追加するデータに複数のハッシュ関数を適用することにより得られるハッシュ値の組に対応するブルームフィルタにおける各要素の値を、０より大きく１より小さい所定の確率でインクリメントする。【選択図】図５
2011171995.tif 000002
【特許請求の範囲】
【請求項１】
入力データに複数のハッシュ関数を適用することにより得られるハッシュ値の組をブルームフィルタにおける対応する要素の値と比較し、当該得られたハッシュ値の組に対応する前記ブルームフィルタにおける要素の値にゼロが１つもなければ、前記入力データが所定のデータ集合に属すると判別するデータ判別装置であって、
前記ブルームフィルタを、前記要素それぞれが複数のビットを有する構成として記憶する記憶部と、
前記所定のデータ集合に新たなデータを追加して前記記憶部に記憶されたブルームフィルタを更新する場合、当該追加するデータに前記複数のハッシュ関数を適用することにより得られるハッシュ値の組に対応する前記ブルームフィルタにおける各要素の値を、０より大きく１より小さい所定の確率でインクリメントする処理部と、
を備えることを特徴とするデータ判別装置。
【請求項２】
前記処理部は、
前記ブルームフィルタにおける各要素の値を所定の確率でインクリメントする場合、要素の値が大きいほど当該要素の値を低い確率でインクリメントする
ことを特徴とする請求項１に記載のデータ判別装置。
【請求項３】
前記処理部は、
所定時間ごとに、すべての前記要素の値をデクリメントする
ことを特徴とする請求項１または請求項２に記載のデータ判別装置。
【請求項４】
前記処理部は、
前記ブルームフィルタにおける要素の値のいずれかが上限値に達したときに、すべての前記要素の値をデクリメントする
ことを特徴とする請求項１または請求項２に記載のデータ判別装置。
【請求項５】
前記記憶部は、
所定のＩＰ（Internet Protocol）アドレスごとに対応した前記ブルームフィルタを記憶しており、
前記処理部は、
前記入力データを受け付けたとき、当該入力データの宛先ＩＰアドレスに対応する前記ブルームフィルタを用いて、前記判別を行う
ことを特徴とする請求項１から請求項４のいずれか１項に記載のデータ判別装置。
【請求項６】
入力データに複数のハッシュ関数を適用することにより得られるハッシュ値の組をブルームフィルタにおける対応する要素の値と比較し、当該得られたハッシュ値の組に対応する前記ブルームフィルタにおける要素の値にゼロが１つもなければ、前記入力データが所定のデータ集合に属すると判別するデータ判別装置によるデータ判別方法であって、
前記データ判別装置は、前記ブルームフィルタを、前記要素それぞれが複数のビットを有する構成として記憶する記憶部と、処理部と、を備えており、
前記処理部は、
前記所定のデータ集合に新たなデータを追加して前記記憶部に記憶されたブルームフィルタを更新する場合、当該追加するデータに前記複数のハッシュ関数を適用することにより得られるハッシュ値の組に対応する前記ブルームフィルタにおける各要素の値を、０より大きく１より小さい所定の確率でインクリメントする
ことを特徴とするデータ判別方法。
【請求項７】
コンピュータを請求項１から請求項５のいずれか１項に記載のデータ判別装置として動作させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上で転送されるパケットなどのデータが所定のデータ集合に属するか否かを判別する技術に属する。
【背景技術】
【０００２】
従来、パケットの判別を行う技術としては、例えば、パケットのアプリケーション層データを扱って判別処理等を行う「Deep Packet Inspection」という技術がある。これは、オートマトン等を使うことで文字列パターンを高速に判定することが可能な技術である。また、可変長でないパターンを高速に検出する方法としては、ブルームフィルタ（Bloom Filter：以下「ＢＦ」とも称する。）を用いたものが存在する（非特許文献１参照）。
【０００３】
ＢＦでは、複数のサンプルデータを正例（正解とするデータ）と負例（不正解とするデータ）に分別しておき、例えば、正例を複数のハッシュ（hash）関数にかけてバッファに格納しておくことで、新たなデータが正例に含まれるか否かを判別可能とする。
【０００４】
具体的には、ＢＦを実現する場合、例えば、最初すべて「０（ゼロ）」に初期化した長さＭビットのビット配列（初期状態のブルームフィルタ）と、ｋ個の互いに異なるハッシュ関数ｆ１，ｆ２，…，ｆｋと、複数のサンプルデータとを用いる。例えば、図１０（ａ）では、７ビットの初期状態のブルームフィルタを表している。
【０００５】
そして、あるサンプルデータについて、上記ｋ個の各ハッシュ関数により第１ハッシュ値ｈｆ１，ｈｆ２，…，ｈｆｋを得る。そして、これらの第１ハッシュ値をＭで除した第２ハッシュ値（剰余）を求め、求めたそれぞれの第２ハッシュ値に対応するビット配列上の各ビットを「１」とする処理を行う。これらを、各サンプルデータについて行う。つまり、ビット配列には多くの「１」が並ぶことになる。
【０００６】
例えば、図１０（ｂ）では、２つのサンプルデータについて、第２ハッシュ値に対応する要素（判定対象部分）の値を「１」とした７ビットのビット配列（（ｂ１）と（ｂ２））を表している。そして、図１０（ａ）に示す初期状態のブルームフィルタに対して、ビット配列（ｂ１）とビット配列（ｂ２）における「１」のビットを反映する処理を行う。そうすると、図１０（ｃ）に示すブルームフィルタとなる。
【０００７】
次に、新たな判別対象データについて、同様に、上記ｋ個の各ハッシュ関数により第１ハッシュ値ｈｆ１，ｈｆ２，…，ｈｆｋを得て、さらに、これらの第１ハッシュ値をＭで除した第２ハッシュ値（剰余）を求める。そして、その求めた第２ハッシュ値のそれぞれに対応するビット配列上の各ビット値を参照し、それらがすべて「１」となっているか否かを判定する。これらがすべて「１」となっていれば、その判別対象データは、サンプルデータ集合に含まれていると判定する。一方、いずれか一つでも「１」となっていなければ、その判別対象データは、サンプルデータ集合に含まれていないと判定する。
【０００８】
例えば、新たな判別対象データが前記した２つのサンプルデータのうちのいずれかであり、ここではそのデータについての第２ハッシュ値に基づくビット配列が（ｄ１）（（ｂ１）と同じ）に示すようになったとする。そうすると、当該ビット配列（ｄ１）においてビットが「１」になっているのは第１要素、第４要素、第５要素である。そして、図１０（ｃ）に示すブルームフィルタにおける第１要素、第４要素、第５要素の値はすべて「１」となっているので、当該判別対象データはサンプルデータ集合に含まれていると判定する。この判定結果は正しい。
【０００９】
一方、例えば、新たな判別対象データがＮＧデータ（サンプルデータ以外のデータ）であり、そのデータについての第２ハッシュ値に基づくビット配列が（ｄ２）に示すようになったとする。そうすると、当該ビット配列（ｄ２）においてビットが「１」になっているのは第２要素、第３要素、第７要素である。そして、図１０（ｃ）に示すブルームフィルタにおいて、第２要素、第７要素の値は「１」となっているが、第３要素の値は「０」であり「１」となっていないので、当該判別対象データは、サンプルデータ集合に含まれていないと判定する。この判定結果は正しい。
【００１０】
しかし、非特許文献１のＢＦでは、正例にサンプルデータが追加される度に、偽陽性が高まるという性質がある。つまり、ブルームフィルタ上に「１」のビットが増えれば増えるほど、ＮＧデータについても、ブルームフィルタにおける対応する各要素の値がすべて「１」となっていて、サンプルデータ集合に含まれていると判定することがある。
【００１１】
例えば、新たな判別対象データがＮＧデータであり、そのデータについての第２ハッシュ値に基づくビット配列が図１０（ｄ）の（ｄ３）に示すようになったとする。そうすると、当該ビット配列（ｄ３）においてビットが「１」になっているのは第１要素、第２要素、第７要素である。そして、図１０（ｃ）に示すブルームフィルタにおける第１要素、第２要素、第７要素の値はすべて「１」となっているので、当該判別対象データはサンプルデータ集合に含まれていると判定する。しかし、この判定結果は誤っている。
【００１２】
これを解決するためには、例えば、カウント・ブルームフィルタ（以下、「ＣＢＦ」と称する。）と呼ばれる、ブルームフィルタの一要素に対して複数ビットを使用する方法がある（非特許文献２参照）。例えば、図１０（ｅ）では、ブルームフィルタの一要素に対して３ビットを使用したＣＢＦを示している。
【００１３】
非特許文献２の技術では、具体的には、ブルームフィルタの一要素に複数ビットがあることを利用して、正例にサンプルデータの追加があって第２ハッシュ値の値の重複がある度に該当する要素の値をインクリメントする。さらに、所定時間の経過時に、全要素の値をデクリメントする。これにより、新しくて高頻度のサンプルデータを残した可能性が高い正例となり、偽陽性の増加を抑制することが可能となる。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Sarang Dharmapurikar, et al., “Deep Packet Inspection using Parallel Bloom Filters”, IEEE Micro, IEEE Computer Society, January/February 2004, Volume24, Issue 1, p.52-61
【非特許文献２】Gianni Antichi, et al., “Counting Bloom Filters for Pattern Matching and Anti-Evasion at the Wire Speed”, IEEE Network Magagine, IEEE Computer Society, January/February 2009, Volume23, Issue 1, p.30-35
【発明の概要】
【発明が解決しようとする課題】
【００１５】
しかしながら、非特許文献２のＣＢＦでは、各要素に複数ビットを用いるため、ある程度の要素の値を数えることが可能であるが、大量に到達するデータに対しては、すぐに要素の値が上限に到達してしまうという欠点があり、頻繁にデクリメントする必要があった。そうすると、短期間であっても、その期間、未到達のデータについては、デクリメントによってＣＢＦから削除されてしまうことになるという問題があった。
【００１６】
また、この問題を回避するために、ブルームフィルタの各要素に多くのビットを割り当てて、大量に到達するデータに対応する要素の値がすぐには上限に到達しないようにする方法もある。しかし、その場合、ＣＢＦに要する記憶容量が大きくなってしまい好ましくないという問題があった。
【００１７】
そこで、本発明は、前記した問題に鑑みてなされたものであり、高頻度のデクリメントを必要としないブルームフィルタを用いたデータ判別を、少ない記憶容量で実現することを課題とする。
【課題を解決するための手段】
【００１８】
前記課題を解決するために、本発明は、入力データに複数のハッシュ関数を適用することにより得られるハッシュ値の組をブルームフィルタにおける対応する要素の値と比較し、当該得られたハッシュ値の組に対応するブルームフィルタにおける要素の値にゼロが１つもなければ、入力データが所定のデータ集合に属すると判別するデータ判別装置であって、ブルームフィルタを、要素それぞれが複数のビットを有する構成として記憶する記憶部と、所定のデータ集合に新たなデータを追加して記憶部に記憶されたブルームフィルタを更新する場合、当該追加するデータに複数のハッシュ関数を適用することにより得られるハッシュ値の組に対応するブルームフィルタにおける各要素の値を、０より大きく１より小さい所定の確率でインクリメントする処理部と、を備えることを特徴とする。
【００１９】
かかる発明によれば、所定のデータ集合に新たなデータを追加してブルームフィルタを更新する場合、追加するデータに前記複数のハッシュ関数を適用することにより得られるハッシュ値の組に対応するブルームフィルタにおける各要素の値を、０より大きく１より小さい所定の確率でインクリメントすることで、各要素の値が上限値に達する可能性を低減させることができ、高頻度のデクリメントを必要としないブルームフィルタを用いたデータ判別を、少ない記憶容量で実現することができる。
【００２０】
また、本発明は、処理部が、ブルームフィルタにおける各要素の値を所定の確率でインクリメントする場合、要素の値が大きいほど当該要素の値を低い確率でインクリメントすることを特徴とする。
【００２１】
かかる発明によれば、ブルームフィルタにおける各要素の値を所定の確率でインクリメントする場合、要素の値が大きいほど当該要素の値を低い確率でインクリメントすることで、各要素の値が上限値に達する可能性をさらに低減することができ、また、要素の値が小さい場合に高い確率でインクリメントするのでブルームフィルタの判別精度をさらに上げることができる。
【００２２】
また、本発明は、処理部が、所定時間ごとに、すべての要素の値をデクリメントすることを特徴とする。
【００２３】
かかる発明によれば、所定時間ごとにデクリメントすることにより、軽い処理負担で、各要素の値が上限値に達してから長時間が経過する事態を回避つつ、各要素で実質的にカウントできる数を増やすことができる。
【００２４】
また、本発明は、処理部が、ブルームフィルタにおける要素の値のいずれかが上限値に達したときに、すべての要素の値をデクリメントすることを特徴とする。
【００２５】
かかる発明によれば、ブルームフィルタにおける要素の値のいずれかが上限値に達したときにデクリメントすることにより、各要素の値を適切なタイミングでデクリメントすることができ、各要素の値が上限値に達してから長時間が経過する事態をより確実に回避つつ、各要素で実質的にカウントできる数を増やすことができる。
【００２６】
また、本発明は、記憶部が、所定のＩＰアドレスごとに対応したブルームフィルタを記憶しており、処理部が、入力データを受け付けたとき、当該入力データの宛先ＩＰアドレスに対応するブルームフィルタを用いて、判別を行うことを特徴とする。
【００２７】
かかる発明によれば、入力データの宛先ＩＰアドレスごとに別々のブルームフィルタを用いることで、ブルームフィルタの各要素の値が上限値に達する可能性をさらに低減することができる。
【００２８】
また、本発明は、コンピュータをデータ判別装置として動作させるためのプログラムである。かかる発明によれば、このプログラムをインストールしたコンピュータをデータ判別装置として動作させることができる。
【発明の効果】
【００２９】
本発明によれば、高頻度のデクリメントを必要としないブルームフィルタを用いたデータ判別を、少ない記憶容量で実現することができる。
【図面の簡単な説明】
【００３０】
【図１】本実施形態におけるデータ判別装置と他の装置との接続関係を示す図である。
【図２】データ判別装置の機能構成図である。
【図３】端末とデータ判別装置の動作のシーケンス図である。
【図４】正／負例用バッファへのデータ追加の説明図である。
【図５】正／負例用バッファへデータを追加する際のインクリメント確率の説明図である。
【図６】正／負例用バッファにおけるデクリメントの説明図である。
【図７】正／負例用バッファへデータを追加する動作を示すフローチャートである。
【図８】データ判別装置の適用例の説明図である。
【図９】データ判別装置の適用例の説明図である。
【図１０】ブルームフィルタの説明図である。
【発明を実施するための形態】
【００３１】
以下、本発明を実施するための形態（以下、「実施形態」と称する。）について、図面を参照（言及図以外の図面も適宜参照）して詳細に説明する。
【００３２】
図１に示すように、端末２ａ（２）、２ｂ（２）は、ネットワーク４を介してサーバ３に対してリクエストやレスポンスのパケットを送受信することでアクセスを行い、その経路上にデータ判別装置１が配置されている。
【００３３】
図２に示すように、コンピュータ装置であるデータ判別装置１は、パケット受信部１１、パケット組立部１２、データハッシュ部１３（処理部）、フィルタＤＢ（Data Base）１４（記憶部）、フィルタ検査部１５（処理部）、リダイレクト生成部１６、パケット転送部１７、認証部１８を備え、それらはＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、各種インタフェースなどにより実現される。各部の動作等は、図３を参照して後記する。
【００３４】
なお、この図２では、端末２からのパケットをパケット受信部１１で受信して、パケット転送部１７からサーバ３にパケットを送信するものとしたが、逆に、サーバ３からのパケットをパケット受信部１１で受信し、パケット転送部１７から端末２にパケットを送信する場合も、同様の処理が行われる。
【００３５】
次に、図３を参照して、データ判別装置１において、正例にサンプルデータを追加する動作のシーケンスについて説明する。
【００３６】
＜（ａ）条件不適合時の処理＞
図３に示すように、端末２から送信されたパケット（ストリーム）は、パケット受信部１１で受信され、パケット組立部１２に渡される（ステップＳ１１）。パケット組立部１２では、受信した複数のパケットをＬ（layer）３もしくはＬ４レベルでデータに構築し（ステップＳ１２）、その構築したデータを次のデータハッシュ部１３に渡す（ステップＳ１３）。
【００３７】
データハッシュ部１３では、構築されたデータの特定の箇所を用いてハッシュ関数を適用し、ビット列を生成し、フィルタ検査部１５に渡す（ステップＳ１４）。フィルタ検査部１５は、フィルタＤＢ１４に要求して（ステップＳ１５）正負例用バッファ（正例用バッファと負例用バッファ）を参照しながら（ステップＳ１６）、このビット列が正例に該当するか否かを判定する。なお、ステップＳ１６では、正例用バッファのみを参照して、このビット列が正例に該当するか否かを判定してもよい。
【００３８】
フィルタ検査部１５は、このビット列を正例と判定しなかった（条件に不適合であった）場合（ステップＳ１７）、構築前のパケットを破棄し、リダイレクト生成部１６で生成したリダイレクトパケットを認証部１８に渡す（ステップＳ１８）。
【００３９】
＜（ｂ）認証処理＞
認証部１８は、端末２に、ポップアップ等からなる認証画面を表示させ、ステップＳ１７で条件に不適合であったデータをサンプルデータとして正例用バッファに追加登録するか否かを問い合わせる（ステップＳ２１）。ユーザの操作によって端末２からＹｅｓの返信があった場合（ステップＳ２２）、認証部１８は、そのデータに対応するビット列（データハッシュ部１３が作成。詳細は後記）を正例用バッファに追加する（ステップＳ２３）。また、認証部１８は、リダイレクトパケットを端末２に送信する（ステップＳ２４）。
【００４０】
＜（ｃ）条件適合時の処理＞
リダイレクトパケットを受信した端末２は、再度同じパケット（ストリーム）を送信する（ステップＳ３１）。ステップＳ３２〜Ｓ３６の処理はステップＳ１２〜Ｓ１６の処理と同様であるため、説明を省略する。
【００４１】
ステップＳ３６の後、フィルタ検査部１５は、受信したビット列が正例に該当するか否かを判定するが、ステップＳ１７の場合と異なり、正例用バッファに当該データに対応するビット列が追加登録されているため、受信したビット列は正例用バッファ（条件）に適合する（ステップＳ３７）。
【００４２】
フィルタ検査部１５は当該データをパケット転送部１７に渡し（ステップＳ３８）、パケット転送部１７は当該データを本来の宛先のサーバ３に転送する（ステップＳ３９）。
【００４３】
なお、ステップＳ２２でＮｏの返信があった場合、ステップＳ２３で当該データに対応するビット列を負例用バッファに追加登録するようにしてもよい。
【００４４】
次に、図３のシーケンスのステップＳ２３の処理イメージについて、図４を参照して説明する。図４に示すように、まず、データハッシュ部１３で生成されたビット列（以下、「生成ビット列」とも称する。）は、７要素、３ビット／要素であり、また、ＢＦ用のハッシュ関数が４つである場合を例にとって説明する。
【００４５】
なお、ＢＦ用のハッシュ関数が４つであるので、生成ビット列における７要素のうち４要素の値が「００１」となっている。また、特許請求の範囲における「ハッシュ値の組」とは、生成ビット列において「００１」となっている要素の組（前記した第２ハッシュ値の組）のことを指す。
【００４６】
ステップＳ２２の返信内容がＹｅｓの場合、生成ビット列は正例用バッファに追加される。なお、ステップＳ２２の返信内容がＮｏの場合、生成ビット列を負例用バッファに追加するようにしてもよい。
【００４７】
次に、図５を参照して、正／負例用バッファ（正例用バッファまたは負例用バッファ。以下、単に「バッファ」とも称する。）へデータを追加する際の各要素におけるインクリメント確率について説明する。図５に示すように、正／負例用バッファに生成ビット列を追加する場合、その追加は要素毎に行われ、インクリメント確率も要素毎に独立に計算される。
【００４８】
各要素におけるインクリメント確率は、現在バッファの各要素に入っている要素の値を基に計算される。ここでは、インクリメント確率が、所定の基底（ｍ：０＜ｍ＜１）の要素の値乗に比例する場合を例にとって説明する。例えば、図５に示すように、第１要素では、要素の値が「０１１（１０進数で「３」）」なので、「ｍ３」がインクリメント確率となる。なお、第５要素のように、要素の値が「１１１」と上限値（最大値）となっている場合は、例外的にインクリメント確率を「０」とする。
【００４９】
このようにすると、要素の値が大きいほどインクリメント確率が下がるため、要素の値が上限値に達する確率を低く抑えることができる。つまり、全要素の値をデクリメントする頻度を大きく低減することができる。
【００５０】
次に、正／負例用バッファにおけるデクリメントについて説明する。図６に示すように、しばらく時間がたって正／負例用バッファに何個かのビット列が追加された後、正／負例用バッファをデクリメントする場合、全要素の値について、一律に「１」を減算する。ただし、すでに「０」になっている要素については、そのまま「０」とする。
【００５１】
これにより、各要素における格納個数の上限を１／ｍ倍（ｍが１／２なら２倍）したことと同様の効果を得ることができる。つまり、各要素の値に関する相対的な比率を変化させずに、バッファへの新しいビット列の反映を残すことができる。
【００５２】
次に、正／負例用バッファへデータを追加する動作（図３のステップＳ２３に相当）について説明する。図７に示すように、データハッシュ部１３は、パケットから構築したデータにハッシュ関数を適用することでビット列を生成し（ステップＳ１０１）、ビット列中の各要素についてステップＳ１０３、Ｓ１０４の処理を行う（ステップＳ１０２〜Ｓ１０５）。
【００５３】
データハッシュ部１３は、ある要素について、ビット列のビットが立っている（「１」である）か否かを判定し（ステップＳ１０３）、ＹｅｓであればステップＳ１０４に進み、ＮｏであればステップＳ１０４をスキップして次の要素の処理（次のステップＳ１０３）に進む。
【００５４】
データハッシュ部１３は、図５を参照して説明したように、要素の値に応じたインクリメント確率でその要素の値をインクリメントし（ステップＳ１０４）、次の要素の処理（次のステップＳ１０３）に進む。
【００５５】
このようにして、本実施形態のデータ判別装置１によれば、ブルームフィルタを用いたデータ判別において、各要素の値を所定のインクリメント確率でインクリメントするため、高頻度のデクリメントを必要としないブルームフィルタを用いたデータ判別を、少ない記憶容量で実現することができる。
【００５６】
つまり、例えば、バッファ（ブルームフィルタ）の各要素が３ビットの場合、従来技術では、ある要素についてビットの立ったビット列が７つ適用されると、バッファにおけるその要素の値が上限値（２進数で「１１１」）に達する。これに対して、本実施形態のデータ判別装置１では、同様の条件で、基底ｍが「１／２」の場合、要素の値が「０００」から「００１」になるのにビット列が１つ、要素の値が「００１」から「０１０」になるのにビット列が平均２つ、要素の値が「０１０」から「０１１」になるのにビット列が平均４つ、以下同様に、要素の値が１つ増えるのに、平均８つ、平均１６個、平均３２個、平均６４個、つまり、バッファにおけるその要素の値が上限値に達するまでにビット列が合計１２７個必要となる。
【００５７】
一般化して言えば、バッファ（ブルームフィルタ）の各要素がｉビットの場合、従来技術では、ある要素についてビットの立ったビット列が（２ｉ−１）個適用されると、バッファにおけるその要素の値が上限値に達する。これに対して、本実施形態のデータ判別装置１では、同様の条件で、基底ｍの場合、ビット列が｛（１／ｍ）^（２ｉ−１）−１｝個適用されると、バッファにおけるその要素の値が上限値に達する。このように、本実施形態のデータ判別装置１におけるブルームフィルタによれば、従来技術に比較して、各要素のビット数が同じでも、各要素で実質的にカウントできる数を飛躍的に大きくできるという効果を奏する。
【００５８】
なお、基底ｍは、データ判別装置１の管理者が「０＜ｍ＜１」を満たす範囲で適宜設定すればよい。具体的には、要素の値が上限値に達する確率の低減を重視するのであればｍを小さい値に設定すればよいし、また、デクリメントによる情報損失の可能性の低減を重視するのであればｍを大きい値に設定すればよい。なお、特許請求の範囲において「ブルームフィルタにおける各要素の値を、０より大きく１より小さい所定の確率でインクリメントする」と記載しているが、これは、要素の値が０のときに１の確率でインクリメントしたり、要素の値が上限値のときにインクリメントしないことまで排除しているわけではない。
【００５９】
また、デクリメントのタイミングは、例えば、所定時間ごとに、あるいは、ブルームフィルタにおける要素の値のいずれかが上限値に達したときなどであればよい。例えば、所定時間ごとにデクリメントする場合は、処理負担が軽くて済む。また、ブルームフィルタにおける要素の値のいずれかが上限値に達したときにデクリメントする場合は、各要素の値が上限値に達してから長時間が経過する事態をより確実に回避できる。
【００６０】
なお、データ判別装置１に実行させるためのプログラムを作成し、データ判別装置１にインストールすれば、データ判別装置１は、そのプログラムに基づいた各機能を実現することができる。
【００６１】
（適用例）
次に、本実施形態のデータ判別装置１の適用例について説明する。図８は、ＮＡＴ（Network Address Translation）装置５やプロキシ装置６に関するユーザをネットワーク４上で判別するシステムにデータ判別装置１を適用した場合を表している。
【００６２】
ネットワーク４上には、多くのＮＡＴ装置５やプロキシ装置６が存在し、その総ユーザ数は膨大である。したがって、本実施形態のデータ判別装置１であっても、すべてのＮＡＴ装置５やプロキシ装置６に対して単一の正／負例用バッファを構築するよりは、正／負例用バッファをいくつかに分割したほうが、偽陽性をより低減できる。
【００６３】
そこで、ＮＡＴ装置５やプロキシ装置６のＩＰアドレスごとに、正／負例用バッファを持つようにする。例えば、データ判別装置１では、ＩＰアドレスが「Ａ」のＮＡＴ装置５について、また、ＩＰアドレスが「Ｂ」のプロキシ装置６について、別々の正／負例用バッファ（正例用バッファと負例用バッファ）を持つようにする。
【００６４】
また、データハッシュ部１３でハッシュ関数を適用する対象としては、ＨＴＴＰ（Hyper Text Transfer Protocol）リクエストに含まれるＣｏｏｋｉｅ（ＨＴＴＰボディの一部）を想定する。同じドメインの宛先に関しては、基本的に同じＣｏｏｋｉｅが付与されることが多いため、ユーザの区別が可能となるからである。
【００６５】
また、図９は、データ判別装置１を用いたサービス例を表している。図９（ａ）の例では、データ判別装置１がネットワーク４（ＮＷ）上のファイアウォール装置７と連携し、ＮＡＴ装置５のユーザを区別して、特定のユーザからのアクセスの場合にファイアウォール装置７において通信を遮断（「×」の箇所）する。
【００６６】
また、図９（ｂ）では、データ判別装置１は、ネットワーク４上に存在するＤＰＩ（Deep Packet Inspection）装置８及び広告サーバ９と連携して、プロキシ装置６のユーザに応じて適切な広告を挿入するサービスを表している。なお、ＤＰＩ装置８は、転送されるパケットの中身を書き換えることが可能なネットワーク装置である。データ判別装置１によって識別されたユーザ情報をこのＤＰＩ装置８に通知し、それに合わせた広告データを広告サーバ９によって挿入するようにパケットを改変することで、ネットワーク側での広告配信を実現することが可能となる。
【００６７】
以上で本実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。
例えば、インクリメント確率は、前記した例のように、要素の値が大きいほど低い確率になるようにしてもよいが、これに限定されない。例えば、バッファの各要素が３ビットの場合、要素の値が「０００」から「０１０」まではインクリメント確率を２／３とし、「０１１」から「１１１」まではインクリメント確率を１／３とするなど、インクリメント確率を段階的に設定してもよい。その他、インクリメント確率は、データ判別装置１の管理者が所定の確率に適宜設定すればよい。
また、データ判別装置１において、複数のブルームフィルタと複数の並列プロセッサを用意し、データ判別に関して並列処理を行うようにしてもよい。
【００６８】
また、本発明は、パケットのトラフィック傾向の把握を可能とするため、トラフィック解析の技術に適用することができる。
また、本発明は、固定計算量によるデータ識別を行うため、機械学習の分野に適用することができる。
【００６９】
また、本発明は、大量のパケットを対象に高速識別が可能であるため、ストリーム処理技術に適用することができる。
その他、具体的な構成について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００７０】
１      データ判別装置
２ａ、２ｂ、２  端末
３      サーバ
４      ネットワーク
５      ＮＡＴ装置
６      プロキシ装置
７      ファイアウォール装置
８      ＤＰＩ装置
９      広告サーバ
１１    パケット受信部
１２    パケット組立部
１３    データハッシュ部（処理部）
１４    フィルタＤＢ（記憶部）
１５    フィルタ検査部（処理部）
１６    リダイレクト生成部
１７    パケット転送部
１８    認証部
【図１】
2011171995.tif 000003
【図２】
2011171995.tif 000004
【図３】
2011171995.tif 000005
【図４】
2011171995.tif 000006
【図５】
2011171995.tif 000007
【図６】
2011171995.tif 000008
【図７】
2011171995.tif 000009
【図８】
2011171995.tif 000010
【図９】
2011171995.tif 000011
【図１０】
2011171995.tif 000012