(57)【要約】【課題】  膨大なアクセス履歴を少ないリソースで保存し、かつ、高精度で検索する。【解決手段】  本発明は、収集された送信元の集合Sと宛先の集合Dが与えられると、該Sおよび該Dをそれぞれ記憶手段に格納し、該Sと該Dの組み合わせのうち、実際にアクセスしたと観測された組を要素としてBloom filterに挿入し、該記憶手段に格納し、入力されたある宛先に基づいて記憶手段を検索し、アクセスした送信元を出力する、または、入力されたある送信元に基づいて、該記憶手段を検索し、アクセスした宛先を出力する。また、Bloom filterを用いたアクセス履歴を前記記憶手段に格納する際に、アクセスした送信元数が少ない宛先を含む要素ほど、前記Bloom filterへの挿入時にハッシュ関数の個数kを大きくする、またはアクセスした宛先数が少ない送信元を含む要素ほど、該Bloom filterへの挿入時にハッシュ関数の個数kを大きくする。【選択図】  図２
2014002483.tif 000002
【特許請求の範囲】
【請求項１】
送信元と宛先の組み合わせで表現されるアクセス履歴を記憶及び検索するアクセル履歴記憶及び検索装置であって、
収集された送信元の集合Sと宛先の集合Dが与えられると、該Sおよび該Dをそれぞれ記憶手段に格納し、該Sと該Dの組み合わせのうち、実際にアクセスしたと観測された組を要素としてBloom filterに挿入し、該記憶手段に格納するアクセス履歴記録手段と、
入力されたある宛先に基づいて前記記憶手段を検索し、アクセスした送信元を出力する、または、入力されたある送信元に基づいて、該記憶手段を検索し、アクセスした宛先を出力する検索手段と、
を有することを特徴とするアクセス履歴記憶及び検索装置。
【請求項２】
前記アクセス履歴記録手段は、
前記Bloom filterを用いたアクセス履歴を前記記憶手段に格納する際に、
アクセスした送信元数が少ない宛先を含む要素ほど、前記Bloom filterへの挿入時にハッシュ関数の個数kを大きくする、またはアクセスした宛先数が少ない送信元を含む要素ほど、該Bloom filterへの挿入時にハッシュ関数の個数kを大きくする最適化手段を含む
請求項１記載のアクセス履歴記憶及び検索装置。
【請求項３】
前記最適化手段は、
前記ハッシュ関数の個数kを、
前記Bloom filterのビット数をm、
前記Bloom filterに挿入する全要素数をn、
各要素毎の誤検出率をpi (1 ≦ i ≦ n)、
各要素毎のハッシュ関数の個数をki (1 ≦ i ≦ n)を要素に持つベクトルをKとしたとき、
【数６】
2014002483.tif 000008
を用いて決定する手段を含む
請求項２記載のアクセス履歴記憶及び検索装置。
【請求項４】
前記検索手段は、
ある宛先dがされた場合に、該宛先dと送信元Sとの全ての組み合わせに対して前記Bloom filterを検索し、該宛先dにアクセスした送信元を出力する手段と、
ある送信元sが入力された場合に、該送信元sと宛先Dとの全ての組み合わせに対して前記Bloom filterを検索し、該送信元sがアクセスした宛先を出力する手段と、
を含む請求項１記載のアクセス履歴記憶及び検索装置。
【請求項５】
送信元と宛先の組み合わせで表現されるアクセス履歴を記憶及び検索するアクセル履歴記憶及び検索方法であって、
アクセス履歴を格納する記憶手段と、
アクセス履歴記録手段と、
検索手段と、を有する装置において、
前記アクセス履歴記録手段が、収集された送信元の集合Sと宛先の集合Dが与えられると、該Sおよび該Dをそれぞれ前記記憶手段に格納し、該Sと該Dの組み合わせのうち、実際にアクセスしたと観測された組を要素としてBloom filterに挿入し、該記憶手段に格納するアクセス履歴記録ステップと、
前記検索手段が、入力されたある宛先に基づいて前記記憶手段を検索し、アクセスした送信元を出力する、または、入力されたある送信元に基づいて、該記憶手段を検索し、アクセスした宛先を出力する検索ステップと、
を行うことを特徴とするアクセス履歴記憶及び検索方法。
【請求項６】
前記アクセス履歴記録ステップにおいて、
前記Bloom filterを用いたアクセス履歴を前記記憶手段に格納する際に、
アクセスした送信元数が少ない宛先を含む要素ほど、前記Bloom filterへの挿入時にハッシュ関数の個数kを大きくする、またはアクセスした宛先数が少ない送信元を含む要素ほど、該Bloom filterへの挿入時にハッシュ関数の個数kを大きくする最適化ステップを行う
請求項５記載のアクセス履歴記憶及び検索方法。
【請求項７】
前記最適化ステップにおいて、
前記ハッシュ関数の個数kを、
前記Bloom filterのビット数をm、
前記Bloom filterに挿入する全要素数をn、
各要素毎の誤検出率をpi (1 ≦ i ≦ n)、
各要素毎のハッシュ関数の個数をki (1 ≦ i ≦ n)を要素に持つベクトルをKとしたとき、
【数７】
2014002483.tif 000009
を用いて決定する
請求項６記載のアクセス履歴記憶及び検索方法。
【請求項８】
前記検索ステップにおいて、
ある宛先dがされた場合に、該宛先dと送信元Sとの全ての組み合わせに対して前記Bloom filterを検索し、該宛先dにアクセスした送信元を出力する、
または、
ある送信元sが入力された場合に、該送信元sと宛先Dとの全ての組み合わせに対して前記Bloom filterを検索し、該送信元sがアクセスした宛先を出力する
請求項５記載のアクセス履歴記憶及び検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アクセス履歴記憶及び検索装置及び方法に係り、特に、どの送信元がどの宛先にアクセスしたかを保持するアクセス履歴を、少ないリソースで作成するためのアクセス履歴記憶及び検索装置及び方法に関する。
【背景技術】
【０００２】
ネットワーク運用において、ユーザのアクセス履歴を記録しておくことは重要である。例えば、アクセス履歴を記録することにより、いつ、どのアクセス先へ、どのユーザがアクセスしたかを知ることができる。例えば、フィッシングなどの悪意あるサイトが発見されたとき、そのサイトへアクセスしたユーザを把握でき、影響範囲の把握や、アクセスしたユーザへの警告を行うことができる。なお、上記のような悪意あるサイトは発見が遅れることがあるため、アクセス履歴は長期間記録しておくことが望ましい。
【０００３】
アクセス履歴を記録する最も単純な方法は、全ての送信元と通信先(宛先)の組を保存しておくことである。しかしながら、大規模ネットワークにおいては送信元-宛先の組み合わせ数が膨大となり、保存には大量のリソースが必要となる。このことから、単純な方法でアクセス履歴を長期間記録し続けることは困難である。
【０００４】
大量の要素を効率的に格納するデータ構造としてBloom filterがあり（例えば、非特許文献１参照）、様々なネットワークアプリケーションに利用されている（例えば、非特許文献２参照）。 
Bloom filterを用いて、挿入され得る全ての要素について調べることでアクセス履歴の記録、検索を行うことができる。具体的には、まず送信元‐宛先の組を要素としてBloom filterに挿入する。ある宛先へアクセスした送信元を列挙したいときは、アクセスし得る送信元(網内の全ユーザ)全てに対し、送信元-宛先の組を作り、Bloom filterに挿入されたかどうか検索を行えばよい。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】B. Bloom, "Space/Time Tradeoffs in Hash Coding with Allowable Errors," Communications of the ACM, 1970.
【非特許文献２】A. Broder and M. Mitzenmacher, "Network Applications of Bloom Filters: A Survey," Internet Mathematics, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、Bloom filterはその特性から要素が挿入されていない場合でも、存在していると判定する誤検出が発生する。Bloom filterのパラメータ次第では、実際にアクセスしていない送信元が大量に出現してしまう可能性がある。誤検出の発生確率は挿入する要素数やBloom filterのデータサイズなどに依存するため、誤検出の発生確率を小さくするためにはそのデータサイズを十分大きくすればよい。しかし、挿入する要素数によっては、Bloom filterを用いても記憶のために大量のリソースが必要になる。
【０００７】
本発明は、上記の点に鑑みなされたもので、膨大なアクセス履歴を少ないリソースで保存し、かつ、高精度で検索することが可能なアクセス履歴記憶及び検索装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明（請求項１）は、送信元と宛先の組み合わせで表現されるアクセス履歴を記憶及び検索するアクセル履歴記憶及び検索装置であって、
収集された送信元の集合Sと宛先の集合Dが与えられると、該Sおよび該Dをそれぞれ記憶手段に格納し、該Sと該Dの組み合わせのうち、実際にアクセスしたと観測された組を要素としてBloom filterに挿入し、該記憶手段に格納するアクセス履歴記録手段と、
入力されたある宛先に基づいて前記記憶手段を検索し、アクセスした送信元を出力する、または、入力されたある送信元に基づいて、該記憶手段を検索し、アクセスした宛先を出力する検索手段と、を有する。
【０００９】
また、本発明（請求項２）は、前記アクセス履歴記録手段において、
前記Bloom filterを用いたアクセス履歴を前記記憶手段に格納する際に、
アクセスした送信元数が少ない宛先を含む要素ほど、前記Bloom filterへの挿入時にハッシュ関数の個数kを大きくする、またはアクセスした宛先数が少ない送信元を含む要素ほど、該Bloom filterへの挿入時にハッシュ関数の個数kを大きくする最適化手段を含む。
【００１０】
また、本発明（請求項３）は、前記最適化手段において、
前記ハッシュ関数の個数kを、
前記Bloom filterのビット数をm、
前記Bloom filterに挿入する全要素数をn、
各要素毎の誤検出率をpi (1 <= i <= n)、
各要素毎のハッシュ関数の個数をki (1 <= i <= n)を要素に持つベクトルをKとしたとき、
【００１１】
【数１】
2014002483.tif 000003
を用いて決定する手段を含む。
【００１２】
また、本発明（請求項４）は、前記検索手段において、
ある宛先dがされた場合に、該宛先dと送信元Sとの全ての組み合わせに対して前記Bloom filterを検索し、該宛先dにアクセスした送信元を出力する手段と、
ある送信元sが入力された場合に、該送信元sと宛先Dとの全ての組み合わせに対して前記Bloom filterを検索し、該送信元sがアクセスした宛先を出力する手段と、を含む。
【発明の効果】
【００１３】
上記のように本発明によれば、Bloom filterを用いることで、膨大なアクセス履歴を少ないリソースで長期間保持することができる。また、Bloom filterの挿入要素ごとにハッシュ関数の個数を決定することにより、検索結果の精度を高めることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施の形態におけるシステム構成図である。
【図２】本発明の一実施の形態におけるアクセス履歴記録・検索部の構成図である。
【図３】本発明の一実施の形態におけるBloom filterのデータ構造である。
【図４】本発明の一実施の形態におけるBloom filterへの要素の挿入手順である。
【図５】本発明の一実施の形態におけるBloom filterへの要素の要素挿入判定手順である。
【図６】本発明の一実施の形態におけるアクセス履歴のBloom filterへの挿入例である。
【図７】本発明の一実施の形態における検索の例である。
【図８】本発明の一実施の形態におけるアクセス数の偏りを示す図である。
【図９】本発明の一実施の形態における挿入要素毎のハッシュ関数の個数の最適化の例である。
【発明を実施するための形態】
【００１５】
以下、図面と共に本発明の実施の形態を説明する。
【００１６】
本発明は、大量の要素を効率的に格納するデータ構造として用いられているBloom filterを利用し、送信元と宛先の組み合わせのうち、実際にアクセスしたと観測された組を要素としてBloom filterに挿入し、記憶することで、膨大なアクセス履歴を少ないリソースで長期間保持するものである。
【００１７】
図１は、本発明の一実施の形態におけるシステム構成を示す。
【００１８】
同図に示すシステムは、アクセス履歴記憶・検索装置１００、運用者装置１、送信元装置２、通信先サーバ３、ルータまたはプロキシサーバ４から構成される。
【００１９】
アクセス履歴記憶・検索装置１００は、ルータまたはプロキシサーバ４からどの送信元装置２から宛先の通信先サーバ３へのアクセス情報を収集するデータ収集部１１０と、アクセス情報を取得しBloom filterを用いて記録し、運用者装置１からの検索リクエストに応じてアクセス履歴を検索するアクセス履歴記録・検索部１２０を有する。アクセス履歴記録・検索部１２０は、図２に示すように、アクセス履歴記録部１２１、アクセス履歴記憶部１２２、検索部１２３から構成される。
【００２０】
最初に、アクセス履歴記録・検索部１２０で用いられるBloom filterについて説明する。
【００２１】
Bloom Filterは任意の要素の挿入および存在の判定（検索）が可能な確率的データ構造である。図３のように、Bloom Filterの構造は0または1の値を取るビット列で表現され、要素の挿入の際には、アクセス履歴記録部１２１においてその要素に対応するビットに1を設定する。検索部１２３が要素の検索を行うときは、検索対象の要素に対応するビットの値を調べ、そのビットが1であるとき要素が存在すると判定する。対応するビットを決定するためには、任意の要素を数値に変換するハッシュ関数を用いる。Bloom Filterの特徴として、挿入する要素に対して必要な空間が非常に小さいことが挙げられる。ただし、Bloom Filterの検索操作において、ある要素を挿入していない場合でも、その要素が存在していると判定する誤検出が発生する。
【００２２】
以下、Bloom Filterの挿入、検索操作および誤検出の詳細について述べる。
【００２３】
[Bloom filterのパラメータ]
以下、Bloom FilterをB、Bloom Filterのビット長をm、Bのi番目(1 ≦ i ≦ m)のビットの値をB[i]とする。また、挿入する要素をx1, x2, …, xn、ハッシュ関数をH1，H2，…，Hkとする。ここで、k個のハッシュ関数は1からmの値を出力し、それぞれの関数が出力する値はそれぞれ異なるものとする。
【００２４】
[Bloom filterへの要素の挿入]
アクセス履歴記録部１２１におけるBloom Filterへの要素の挿入手順を図４に記す。
【００２５】
（１）まず、挿入する要素xiを、k個のハッシュ関数に適用する。
【００２６】
（２）次に、出力された値の位置のビットを1に設定する。具体的には、B[H1] = 1，…，B[Hk] = 1とする。
【００２７】
[Bloom filterにおける要素の検索]
検索部１２３がある要素がBloom Filterに挿入されたかどうかを判定する手順を図５に記す。
【００２８】
（１）まず、検索する要素xjを、k個のハッシュ関数に適用する。
【００２９】
（２）次に、出力された値の位置のビットを調べ、k個のビット全てが1の場合は要素が存在する(真)、1つでも0のビットがある場合は要素が存在しない(偽)と判定する。
【００３０】
[誤検出の発生確率]
Bloom Filterは空間効率性に優れているが、検索時において存在したい要素に対して存在すると判定する誤検出が存在する。これはハッシュ関数の衝突によって検索したビットが全て1となる可能性があるからである。Bloom filterの誤検出の発生確率は、Bloom filterのビット長m、挿入する要素数nおよびハッシュ関数の個数kによって計算される。誤検出はBloom filterのビット長mに対して、1であるビット数の割合が小さいほど少なくなる。すなわち、誤検出の発生確率を低くしたいときは、mを大きくすればよい。また、mおよびnが決まっているとき、誤検出の発生確率を最小にするkを計算することができる。
【００３１】
[Bloom filterを用いたアクセス履歴の記録および検索方法]
a個の送信元S = {s1，s2，…，sa}と、b個の宛先D = {d1，d2，…，db}が存在するとする。このとき、大規模ネットワーク上においてアクセス履歴(si, dj) (1 ≦ i ≦ a，1 ≦ j ≦ b)の組み合わせは膨大となり、全てを保持することは困難である。そこで、アクセス履歴記録部１２１は、SおよびDのみそれぞれ保存し、(si, dj)の組をBloom Filterを用いて保存することで、必要なリソースを大幅に削減することができる。アクセス履歴のBloom filterへの挿入を図６に示す。
【００３２】
ある宛先dへどの送信元がアクセスしたかを知りたいときは、検索部１２３において、dと全ての送信元の組み合わせ(sj, d) (1 ≦ j ≦ b)に対し、Bloom filterに挿入されているかを検索し、挿入されている送信元を列挙すればよい。アクセス履歴の検索を図７に示す。
【００３３】
[アクセス数の偏りとBloom filterの誤検出の課題]
ここで、アクセス履歴の偏りとBloom filterの誤検出について考える。
【００３４】
ネットワークにおけるアクセス履歴の特性に関して、少数の宛先に非常に多くの送信元がアクセスするという偏りがあることが知られている（例えば、文献「M. Aida, N. Takahashi, and T. Abe, "A proposal of Dual Zipfian Model describing HTTP access trends and its application to address cache design."』参照」。
【００３５】
例えば、アクセス送信元が多い宛先をdmajor，アクセス送信元が少ない宛先をdminorとし、それぞれの送信元数を100,000および100とする。また、全送信元数を1,000,000とし、誤検出率を0.1%となるようBloom filterを作成し、アクセス履歴を登録する。このとき、dmajor，dminorそれぞれどの送信元がアクセスしたかを検索すると、検索回数は全送信元数である1,000,000回行われ、誤検出数は1,000,000の0.1%である1,000となる。すなわち、dmajorでは101,000，dminorでは1,100の送信元が検索結果(推定値)として出力されることになる。
【００３６】
この場合の検索結果の精度を考えたとき、dmajorについては推定値が真の値の1.01倍、dminorに関しては推定値が真の値の11倍となる。この例のように、アクセス傾向の偏りによってアクセス履歴の検索によって得られる推定値と真の値の差にも偏りが出てしまう。 この例を図８に記す。
【００３７】
[挿入要素ごとのハッシュ関数の個数の最適化]
上記の課題に対して、アクセス履歴の偏りにかかわらず、推定値と真の値の差を平準化する方式を考える。前述の通り、Bloom filterの誤検出は、全ビット数mに対する、値が1であるビットの割合を少なくすればよい。
【００３８】
そこで、挿入する要素ごとにハッシュ関数の個数kを変える方式を提案する。具体的には、アクセス履歴記録部１２１において、アクセス送信元数が多い宛先を含む要素を挿入するときはハッシュ関数の個数kを小さく、アクセス送信元数が少ない宛先を含む要素を挿入するときはkの個数を大きくする。この方式を図９に記す。ここで、kの決定方法に関しては、推定値と真の値との割合が一定の割合となるようにする。例えば、推定値と真の値との差が、真の値の10%まで許容すると、上記のdmajorに関しては10,000まで、dminorに関しては10までの誤検出数を許容する。このようにすることで、アクセス傾向の偏りに関わらず推定値と真の値との差を平準化することができる。
【００３９】
本発明では、Bloom filterを、検索要素数ではなく、検索によって得られる値と真の値の差(割合)を一定にする。これにより、アクセス送信元数が多い宛先の検索時における誤検出数を許容範囲としつつ、アクセス送信元が少ない宛先の検索時の誤検出数を少なくすることができる。
【００４０】
[ハッシュ関数の個数kの決定方式例]
ここでは、各要素毎のハッシュ関数の個数kの値を決定する方式の例を記す。
【００４１】
ハッシュ関数の個数を決定するために、誤検出の発生確率を定式化する。ここで、ハッシュ関数の出力に偏りはないものとする。ある要素xj(1 ≦ j ≦n)に対するハッシュ関数の個数をkiとするとき、あるビットの値が0である確率は以下のようになる。
【００４２】
【数２】
2014002483.tif 000004
よって、n個の要素を挿入したときあるビットの値が0である確率は式1から
【００４３】
【数３】
2014002483.tif 000005
となる。ある要素xiがBloom filterに挿入されたと判定されるときは、ki個のハッシュ関数の出力に対応するビットの値が全て1のときであるので、要素xiに関する誤検出の発生確率piは式2を用いて以下のようになる。
【００４４】
【数４】
2014002483.tif 000006
上記によって得られた式3を用いて各要素のハッシュ関数の個数を決定する。
【００４５】
本発明は挿入する要素ごとに誤検出の発生確率を定め、ハッシュ関数の個数を求めるものである。前述のように、推定値と真の値との割合を一定にするよう誤検出の発生確率を定め、各piに対して
【００４６】
【数５】
2014002483.tif 000007
を満たすような各kiを計算する。ここで、mおよびnは与えられているものとする。
【００４７】
なお、上記のアクセス履歴記録・検索装置の構成要素の動作をプログラムとして構築し、アクセス履歴記録・検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４８】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用可能である。
【符号の説明】
【００４９】
１  運用者装置
２  送信元装置
３  通信先サーバ
４  ルータまたはプロキシサーバ
１００  アクセス履歴記憶・検索装置
１１０  データ収集部
１２０  アクセス履歴・記録検索部
１２１  アクセス履歴記録部
１２２  アクセス履歴記憶部
１２３  検索部
【図１】
2014002483.tif 000010
【図２】
2014002483.tif 000011
【図３】
2014002483.tif 000012
【図４】
2014002483.tif 000013
【図５】
2014002483.tif 000014
【図６】
2014002483.tif 000015
【図７】
2014002483.tif 000016
【図８】
2014002483.tif 000017
【図９】
2014002483.tif 000018