アルゴリズム問題演習 - 大規模ブラックリスト IP マッチング

多くの IT 企業では、アルゴリズムは面接で非常に重要な部分を占めていますが、実際の仕事でアルゴリズムに遭遇することはほとんどなく、あまり実用的ではないと不満を言う人も多くいます。弊社が面接でよく使う質問について解説します。最下層では非常にシンプルなアルゴリズムが使われていますが、実際の業務では比較的見やすいシナリオである、大規模なブラックリストIPマッチングについて解説します。同時に、セキュリティゲートウェイで開発した例を使用して検証を行います。

1. 問題とシナリオ

問題: IP セグメントのリストが膨大にあり、特定の IP がそれらのいずれかに属しているかどうかをすばやく確認する必要があります。

これは実際にはよくある問題です。当社のセキュリティゲートウェイを例にとると、少なくとも次のシナリオで必要になります。

シナリオ 1: 単純なブラックリストとホワイトリストのマッチング

ゲートウェイの場合、ブラックリストとホワイトリストのマッチングは基本的な機能です。

内部 IP はホワイトリストに登録してバイパスする必要があります。会社の規模や地理的な場所によっては、ホワイトリストの数が多すぎる場合があります。
攻撃元の IP をブラックリストに登録してブロックする必要があります。現在のインターネットでは、さまざまなスキャンや攻撃が依然として横行しており、ブラックリストに登録された IP が大量に取得されることが容易であり、リアルタイムでブロックする必要があります。
同様の参考として、nginx のブラックリスト機能を参照できます。拒否ステートメント「deny 192.168.1.0/24;」を通じて、アクセス制御の対象となる IP セグメントのグループを定義できます。

シナリオ2: 実際のIPアドレスを取得する

実際の IP アドレスを取得することは、トラフィックのソースパスが異なる可能性があるため、一部の Web サイトにとっては非常に厄介な問題です。

ブラウザ-->ゲートウェイ。このメソッドは、TCP のリモートアドレスである remote_address を直接受け取ります。
ブラウザ --> lb --> ゲートウェイ。中間に他のロードバランサが存在する場合があり、通常は XFF ヘッダーによって識別されます。
ブラウザ --> cdn --> lb --> ゲートウェイ。一部のトラフィックは CDN または Cloud WAF を通過するため、CDN IP アドレスを識別するために XFF ヘッダーを特別に処理する必要があります。
ブラウザ --> cdn --> lb --> ... --> lb --> ゲートウェイ。実際のシナリオでは、リダイレクトや内部の多層ゲートウェイの影響により、より複雑なシナリオが発生する可能性があります。

同様の参考として、nginx の real ip 関数を参照できます。原理も比較的単純です。「set_real_ip_from 192.168.1.0/24;」のようなステートメントを通じて内部 IP リストを設定できます。このように、XFF ヘッダーを処理するときに、後ろから前に向かって検索し、再帰モードで、内部 IP ではない最初の値、つまり実際の IP を見つけます。これでこの記事の質問に戻ります。

シナリオ 3: トラフィックのラベル付け

この部分の機能は、バックエンドのビジネスモジュールによって実装されることが多いです。製品を開発する際には、リクエストが来たときに何らかの自動アノテーションを行って、バックエンドの負担を軽減したいと考えています。より便利なものは次のとおりです。

IP の場所を特定します。 IP ロケーションは通常、数十万のネットワークセグメントで構成されるインデックスであり、迅速な判断が必要です。
基地局のラベル付け。現在、インターネットアクセスには 4G が広く使用されているため、基地局の IP は慎重に扱う必要があり、基地局データも多数の IP セグメントで構成されています。
クラウドサーバーの注釈。現在、ほとんどの攻撃はクラウドサーバーから発生しています。これらの注釈は、バックエンドのセキュリティとリスク管理サービスに役立ちます。クラウドサーバーリストも、膨大な IP セグメントリストを通じて表示されます。

上記のシナリオは、比較的簡単に遭遇する大規模な IP セグメントリストを照合するいくつかのアプリケーションシナリオについて説明しています。

2. アルゴリズムの説明

アルゴリズム 1: ハッシュマップ

ほとんどの人の最初の反応は、ハッシュマップを使用して一致させることですが、これは理論的には可能です (ネットワークセグメントを独立した IP に分割する) が、基本的には使用できません。

ネットワークマスクは必ずしも 24 ビットである必要はなく、32 ビット以内の任意の数値にすることができます。そのため、普遍性を確保したい場合は、独立した IP に完全に分割する必要があります。
実際の IP アドレスを取得するという一般的なシナリオでも、顧客側でこれに遭遇したことがあります。複数の CDN メーカーを使用しているため、1,300 を超える CDN ネットワークセグメントがあります。これらがすべて 24 ビットマスクの C クラスアドレスであると仮定すると、332,800 を超える IP アドレスが存在することになります。ハッシュマップを作成すると、大量のメモリが消費されます。
ゲートウェイは通常、複数のプロセスまたは複数のインスタンスを介して水平に拡張されるため、このメモリの無駄も指数関数的に増加します。

したがって、ハッシュマップ方式はクエリには効率的ですが、実装レベルでは実現可能ではありません。

アルゴリズム2: ネットワークセグメントリストの順次マッチング

現在、ほとんどのオープンソース実装がこの方式を採用していることがわかります。たとえば、シナリオの段落で説明した nginx の 2 つの機能モジュールは、accss モジュールと realip モジュールにあります。これらは、設定を cidr リストとして保存し、それらを 1 つずつ照合します。別の実装は、openresty の lua-resty-iputils モジュールです。このコードはより直感的に見えます。

ローカル関数 ip_in_cidrs(ip, cidrs)
 ローカル bin_ip、 bin_octets = ip2bin (ip)
 bin_ipでない場合は
 nil、bin_octetsを返す
 終わり
 _,cidr in ipairs(cidrs) の場合
 bin_ip > = cidr[1]かつbin_ip < = cidr[2]の場合
 真を返す
 終わり
 終わり
 偽を返す
終わり

オープンソース実装は、ほとんどの単純なシナリオを処理するのに十分ですが、その後のテストでは、IP セグメントの数が増えると、パフォーマンスがまだ不足していることが示されています。

アルゴリズム3: 二分探索

実際のアルゴリズムは非常にシンプルで、バイナリ検索を使用するだけです。これらの IP セグメントが互いに隣接していないと仮定して、図に示すように、Java に似たバイナリ検索を使用します。

隣接していない 4 つの IP セグメント A、B、C、D があるとします。各セグメントは、開始 IP の整数表現と終了 IP の整数表現の 2 つの数値に変換できます。たとえば、0.0.0.0/24 は [0, 255] に変換できます。このように、4 つのネットワークセグメントは 8 つの数字に変換され、並べ替えることができます。ネットワークセグメントは互いに隣接していないため、図に示すように、1 つの IP セグメントが別の IP セグメントに接続されている必要があります。このマッチングアルゴリズムはよりシンプルになります:

照会された IP を数値に変換し、配列内でバイナリ検索を実行します。
Java のバイナリ検索の実装を参照してください。クエリがヒットした場合は、ヒット番号のインデックスが直接返されます。クエリがヒットしなかった場合は、負の数が返され、その絶対値は挿入位置を示します (具体的な実装は少し変更する必要がありますが、ここでは省略します)。
2 番目のステップで、戻り値が正の場合、おめでとうございます。見つかったので、直接ヒットです。
2 番目のステップでは、返された値が負の数であり、挿入座標が奇数 (1、3、5、7) である場合、挿入ポイントがネットワークセグメント内に正確に含まれていることを意味し、ヒットを示します。
2 番目のステップでは、返された値が負の数で、挿入座標が偶数 (0、2、4、6、8) の場合、挿入ポイントが 2 つのネットワークセグメントの間にあることを意味し、この IP はどのネットワークセグメントとも一致しないことを意味します。
作業は完了しました。

したがって、アルゴリズム全体は非常にシンプルですが、ネットワークセグメントが互いに隣接していないことを前提としているため、見落とされがちです。以下は簡単な説明です。

任意の 2 つのネットワークセグメント A と B には、次の 3 つの関係があります。

まったく隣接していません。 AとBには重複する部分はありません。
包含、つまり、A に B が含まれるか、B に A が含まれます。この状況は、データの前処理中に検出され、排除できます (大きなネットワークセグメントのみが保持されます)。
A と B は交差しますが、互いを含みません。つまり、2 つのネットワークセグメントが絡み合っています。次の図は、この状況が真実ではないことを示しています。

上の図は、任意の 2 つのネットワークセグメントを示しています。

「*」はマスクを示します
2つのネットワークセグメント、合計32ビット、サブネット部分の最初のX連続ビットは同じです
最初のネットワークセグメントには Y ビットが残っており、2 番目のネットワークセグメントには Z ビットが残っています。

それで：

Y == Z == 0と仮定すると、2つのネットワークセグメントは完全に等しいことになります。
Y == 0 && Z != 0 は、最初のネットワークセグメントに 2 番目のネットワークセグメントが含まれていることを示します。Y != 0 && Z == 0 は、2 番目のネットワークセグメントの方が大きいことを示します。
Y != 0 && Z != 0 はグラフ上の直感的な表現です。ネットワークセグメント内の IP は * 部分のみを変更できるため、少なくとも中央の数ビットが異なるため、2 つのネットワークセグメントが同じ IP を持つことは不可能です。

したがって、元データがある程度前処理されていれば、バイナリ検索は安全かつ効果的な方法です。

3. テストデータ

最近はかなり多くの携帯電話が発売されているので、私たちもその傾向を追ってスコアを計算してみます。

テストは、4 コア 1.2GHz CPU と 1G メモリを搭載した Raspberry Pi 3 Model B で実施されました。
パフォーマンステストは、50 の接続で 30 秒間 wrk を使用して実行されました。

テスト1: ベンチマークテスト

http://10.0.0.5/ で 30 秒のテストを実行しています
12 スレッドと 50 接続
スレッド統計 平均標準偏差 最大 +/- 標準偏差
レイテンシー 6.54ms 4.80ms 194.75ms 99.29%
要求/秒 617.22 56.76 1.05k 80.42%
レイテンシ分布
50% 6.22ミリ秒
75% 6.99ミリ秒
90% 7.78ミリ秒
99% 10.74ミリ秒
30.10秒で221915リクエスト、40.62MB読み取り
リクエスト数/秒: 7373.42
転送速度/秒: 1.35MB

テスト2: 10,000個のブラックリスト + ハッシュマップ

http://10.0.0.5/block_ip_1w で 30 秒のテストを実行しています
12 スレッドと 50 接続
スレッド統計 平均標準偏差 最大 +/- 標準偏差
レイテンシー 7.75ms 2.34ms 94.11ms 85.57%
要求/秒 512.72 68.86 780.00 74.28%
レイテンシ分布
50% 7.21ミリ秒
75% 8.36ミリ秒
90% 10.63ミリ秒
99% 14.07ミリ秒
30.09秒で184298リクエスト、32.16MB読み取り
リクエスト数/秒: 6125.35
転送速度/秒: 1.07MB

テスト 3: 10,000 個のブラックリスト + lua-resty-utils モジュールの順次検索

http://10.0.0.5/block_iputils_1w で 30 秒のテストを実行中
12 スレッドと 50 接続
スレッド統計 平均標準偏差 最大 +/- 標準偏差
レイテンシー 162.93ms 100.27ms 1.96s 95.22%
要求/秒 27.47 12.28 150.00 66.46%
レイテンシ分布
50% 155.88ミリ秒
75% 159.40ミリ秒
90% 161.54ミリ秒
99% 670.13ミリ秒
30.09秒で9164リクエスト、1.60MB読み取り
ソケット エラー: 接続 0、読み取り 0、書き込み 0、タイムアウト 11
リクエスト数/秒: 304.52
転送速度/秒: 54.41KB

テスト4: 10,000個のブラックリスト + バイナリ検索

http://10.0.0.5/block_ipcidr_bin_1w で 30 秒のテストを実行しています
12 スレッドと 50 接続
スレッド統計 平均標準偏差 最大 +/- 標準偏差
レイテンシー 9.60ms 6.78ms 196.80ms 97.53%
要求/秒 427.92 82.80 0.89k 60.15%
レイテンシ分布
50% 8.45ミリ秒
75% 10.94ミリ秒
90% 12.55ミリ秒
99% 18.58ミリ秒
30.10秒で153892リクエスト、26.85MB読み取り
リクエスト数/秒: 5112.69
転送速度/秒: 0.89MB