3

Bloom Filters の使用法に関するウィキペディアの記事を読んでいました。入力された URL が悪意のあるものかどうかを検出するために Google Chrome でブルーム フィルターが使用されることが記事で言及されました。偽陽性の存在のため

Google Chrome Web ブラウザーは、Bloom フィルターを使用して悪意のある URL を識別します。URL は最初にローカル ブルーム フィルタと照合され、ヒットした場合にのみ URL の完全なチェックが実行されます。

完全なチェックは、Google が悪意のある URL のリストの厳しいテーブルを保存し、その URL がテーブルに存在するかどうかをチェックするためにハッシュされることを意味すると推測しています。だとしたら、ハッシュテーブル+ブルームフィルターよりもハッシュテーブルだけの方がいいのではないでしょうか??

これについて教えてください。フルチェックの私のバージョンは正しいですか???

4

5 に答える 5

1

ブルーム フィルタは、Web クエリよりもはるかに小さくて高速であるだけでなく、Google の悪意のある URL API を、そうでなければ途方もない作業負荷から保護します。

于 2014-01-22T10:10:08.553 に答える
1

ブルーム フィルターは確率的データ構造であり、要素が確実にセットに含まれていないか、セットに含まれている可能性があることを示します。ブルーム フィルターは、ハッシュマップと比較して (構成されているハッシュ関数とエラー率に応じて) 少ないスペースを必要とします。ハッシュマップは要素が存在するかどうかを判断できますが、ブルームフィルターは要素が存在しないことを決定論的にチェックすることしかできません。

Google Chrome の使用例を見てみましょう。ユーザーが URL を入力すると、その URL が安全かどうかを検証する必要があります。URL を検証するために、chrome は google サーバーを呼び出すことができます (内部的に google はこれを見つけるために任意のデータ構造を維持できます)。ただし、このアプローチには複数の課題があります。Chrome で提供されるすべての URL リクエストに対して、URL 検証は Google サーバーを介して行われます。これにより、Google サーバーへの追加の依存関係、ネットワーク ラウンドトリップ時間、およびすべての URL を検証するための高可用性を維持するための要件が​​追加されます。世界中の Chrome ブラウザから起動された URL。

このデータはあまり頻繁に変更されないため (1 時間ほどで更新される可能性があります)、Chrome はすべての悪意のあるサイトのデータをブルーム フィルターとしてバンドルすることを検討し、Google はこのデータをクライアントと定期的に同期する可能性があります (悪意のあるサイトは、本格的なウェブサイト。)ユーザーが Chrome で URL を開くと、ブルーム フィルターがチェックされ、URL が存在しない場合は安全です。存在する場合、ブルーム フィルターはそれについて確信がないため、トラフィックは検証のために Google サーバーに送られます (このトラフィックは、すべてのトラフィックをルーティングする場合に比べてはるかに少なくなります)。

于 2020-08-15T23:51:13.850 に答える