💵 😐 🐴 Hyperscanで複数の正規表現を見つける 🕜 💑 ⚗️

この記事では、ハイパースキャンシステムを使用して多くの正規表現の実行を最適化した経験についてお話したいと思います。 rspamdスパムフィルターを開発する際、spamassassin向けに書かれた大量の古いルールを数年の作業で移植する必要に直面しました。私の最初の決定は、これらのルールを読み取り、それらから構文ツリーを構築するプラグインを書くことでした。次に、このツリーでさまざまな最適化を実行して、全体の実行時間を短縮しました（これについて簡単に説明しました）。

残念ながら、操作中にpcreが依然としてボトルネックであることが判明し、大きな文字ではこのルールセットは遅すぎます。たとえば、メガバイトサイズの文字で、pcreは約1ギガバイト（！）のテキストをチェックすることが判明しました。正規表現のテキストの量を制限するなどのさまざまなトリックは、ルールに悪影響を及ぼし、pcre_jit_execを介したjit高速パスを集中的に使用してpcreを最適化することは非常に危険であることが判明しました-いくつかの古い表現は、たとえばUTF-8の文字を「傷つけた」ため、プログラムスタックが破損する再現可能なバグが発生しました。しかし、高負荷の会議で、Vyacheslav Olkhovchenkovと話をし、彼はハイパースキャンを見るようにアドバイスしました。次に、要点を説明し、それが何をもたらしたのかを説明します。

ハイパースキャンについて簡単に

Hyperscanはかなり長い歴史を持つプロジェクトであり、Deep Packet Introspection（DPI）ソリューションを販売するために作成されました。しかし、昨年10月にIntelはソースコードをオープンすることを決定し、さらにBSDライセンスの下でさえ決定しました。このプロジェクトはC ++で書かれており、ブーストをかなり集中的に使用しています。これにより、移植時に特定の問題が発生します（後で詳しく説明します）。内部では、ハイパースキャンは非決定性有限状態マシン（NFA）に基づく非バックトラッキング正規表現エンジンです。原則として、すべての最新のパフォーマンス指向の正規表現エンジンは同じ理論を使用して記述され、バックトラッキングを完全に放棄します（もちろん、線形検索速度を確保したい場合は非常に合理的です）。私にとって最も重要なハイパースキャン機能は、いくつかのテキストで多くの正規表現を同時に実行できることでした。 pcreで同じことを行うための単純なアプローチは、複数の式を|と組み合わせて試すことです。一種の「ソーセージ」で：

  （？：re1）|（？：re2）| ... |（？：reN）

。残念ながら、このアプローチは機能しません。タスクは、以前に機能した式だけでなく、指定された式のセットからすべてのオカレンスを見つけることであるためです。 Hyperscanはそのようには機能しません。検出された各式に対して、テキスト内の位置（ただし、エントリの最後の文字のみ）でコールバック関数を呼び出します。これは次の図に示すことができます。

ハイパースキャンアーキテクチャ

Hyperscanは、コンパイラと実際にはエンジンの2つの部分で構成されています。コンパイラーは、ライブラリーの非常に大きな部分であり、式の束を取り、そのためのNFAを構成し、たとえばAVX2などのベクトル命令を使用して、このNFAをアセンブラーコードに変換できます。このタスクは難しく、リソースを消費するため、コンパイラーは結果コードをシリアル化して後で使用することもできます。検索エンジンは小さなライブラリであり、実際、特定のテキストでNFAを実行するように設計されています。プリコンパイルされた式セットのみを使用するアプリケーションの場合、別個のlibhs_runtimeライブラリを使用できます。これは、コンパイラ+エンジンlibhsを組み合わせたライブラリよりもはるかに小さくなります。まず、ハイパースキャンを構築しようとしました。これは、システムにかなり新しいブーストがあれば、非常に簡単なタスクであることがわかりました（最小バージョン1.57）。おそらく唯一の発言は、デバッグシンボルを使用してビルドする場合、ライブラリは巨大であるということです-私のMacbookでは約200MBです。また、デフォルトでは静的ライブラリのみが収集されるため、接続時に、バイナリのサイズも200Mbの領域で取得されます。デバッグシンボルが必要ない場合は、指定せずにハイパースキャンを収集することをお勧めします

  -DCMAKE_BUILD_TYPE = MinSizeRel

設定段階でcmakeを使用します。

テストコード

それから、ハイパースキャンとpcreを比較して、ネタバレの下で見ることができる非常に粗雑なプロトタイプを書いてみました（私はあなたに警告します-これはプロトタイプコードで、品質を主張せずに急いで書かれました）。

Pcreとハイパースキャンの比較コード

#include <iostream> #include <string> #include <fstream> #include <vector> #include <stdexcept> #include <algorithm> #include <set> #include "pcre.h" #include "hs.h" #include <time.h> #ifdef __APPLE__ #include <mach/mach_time.h> #endif using namespace std; double get_ticks(void) { double res; #if defined(__APPLE__) res = mach_absolute_time() / 1000000000.; #else struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); res = (double)ts.tv_sec + ts.tv_nsec / 1000000000.; #endif return res; } struct pcre_regexp { pcre* re; pcre_extra* extra; pcre_regexp(const string& pattern) { const char* err; int err_off; re = pcre_compile(pattern.c_str(), PCRE_NEWLINE_ANYCRLF, &err, &err_off, NULL); if (re == NULL) { throw invalid_argument(string("cannot compile: '") + pattern + "' error: " + err + " at offset: " + to_string(err_off)); } extra = pcre_study(re, PCRE_STUDY_JIT_COMPILE, &err); if (extra == NULL) { throw invalid_argument(string("cannot study: '") + pattern + "' error: " + err + " at offset: " + to_string(err_off)); } } }; struct cb_context { set<int> approx_re; vector<pcre_regexp> pcre_vec; }; struct cb_data { struct cb_context* ctx; vector<int> matched; const std::string* str; }; bool remove_uncompileable(const string& s, int id, struct cb_context* ctx) { hs_compile_error_t* hs_errors; hs_database_t* hs_db; if (hs_compile(s.c_str(), HS_FLAG_ALLOWEMPTY, HS_MODE_BLOCK, NULL, &hs_db, &hs_errors) != HS_SUCCESS) { cout << "pattern: '" << s << "', error: " << hs_errors->message << endl; if (hs_compile(s.c_str(), HS_FLAG_ALLOWEMPTY | HS_FLAG_PREFILTER, HS_MODE_BLOCK, NULL, &hs_db, &hs_errors) != HS_SUCCESS) { cout << "completely bad pattern: '" << s << "', error: " << hs_errors->message << endl; return true; } else { ctx->approx_re.insert(id); } } else { hs_free_database(hs_db); } return false; } int match_cb(unsigned int id, unsigned long long from, unsigned long long to, unsigned int flags, void* context) { auto cbdata = (struct cb_data*)context; auto& matched = cbdata->matched; if (cbdata->ctx->approx_re.find(id) != cbdata->ctx->approx_re.end()) { int ovec[3]; auto re = cbdata->ctx->pcre_vec[id]; auto* begin = cbdata->str->data(); auto* p = begin; auto sz = cbdata->str->size(); while (pcre_exec(re.re, re.extra, p, sz - (p - begin), 0, 0, ovec, 3) > 0) { p = p + ovec[1]; matched[id]++; } } else { matched[id]++; } return 0; } int main(int argc, char** argv) { ifstream refile(argv[1]); vector<string> re_vec; double t1, t2, total_ticks = 0; struct cb_context ctx; int ls; pcre_config(PCRE_CONFIG_LINK_SIZE, &ls); cout << ls << endl; for (std::string line; std::getline(refile, line);) { re_vec.push_back(line); } string re_pipe; const char** pats = new const char*[re_vec.size()]; unsigned int i = 0, *ids = new unsigned int[re_vec.size()]; //re_vec.erase(remove_if(re_vec.begin(), re_vec.end(), remove_uncompileable), re_vec.end()); for (i = 0; i < re_vec.size(); i++) { const auto& r = re_vec[i]; remove_uncompileable(r, i, &ctx); pats[i] = r.c_str(); ids[i] = i; re_pipe = re_pipe + string("(") + r + string(")|"); } // Last | re_pipe.erase(re_pipe.size() - 1); total_ticks = 0; for (const auto& r : re_vec) { t1 = get_ticks(); ctx.pcre_vec.emplace_back(r); t2 = get_ticks(); total_ticks += t2 - t1; } cout << "PCRE compile time: " << total_ticks << endl; ifstream input(argv[2]); std::string in_str((std::istreambuf_iterator<char>(input)), std::istreambuf_iterator<char>()); hs_compile_error_t* hs_errors; hs_database_t* hs_db; hs_platform_info_t plt; hs_populate_platform(&plt); unsigned int* flags = new unsigned int[re_vec.size()]; for (i = 0; i < re_vec.size(); i++) { if (ctx.approx_re.find(i) != ctx.approx_re.end()) { flags[i] = HS_FLAG_PREFILTER; } else { flags[i] = 0; } } t1 = get_ticks(); if (hs_compile_multi(pats, flags, ids, re_vec.size(), HS_MODE_BLOCK, &plt, &hs_db, &hs_errors) != HS_SUCCESS) { cout << "BAD pattern: '" << re_vec[hs_errors->expression] << "', error: " << hs_errors->message << endl; return -101; } t2 = get_ticks(); cout << "Hyperscan compile time: " << (t2 - t1) << "; approx re: " << ctx.approx_re.size() << "; total re: " << re_vec.size() << endl; char* bytes = NULL; size_t bytes_len; t1 = get_ticks(); if (hs_serialize_database(hs_db, &bytes, &bytes_len) != HS_SUCCESS) { cout << "BAD" << endl; return -101; } t2 = get_ticks(); cout << "Hyperscan serialize time: " << (t2 - t1) << "; size: " << bytes_len << " bytes" << endl; hs_database_t* hs_db1 = NULL; t1 = get_ticks(); if (hs_deserialize_database(bytes, bytes_len, &hs_db1) != HS_SUCCESS) { cout << "BAD1" << endl; return -101; } t2 = get_ticks(); cout << "Hyperscan deserialize time: " << (t2 - t1) << "; size: " << bytes_len << " bytes" << endl; auto matches = 0; total_ticks = 0; for (const auto& re : ctx.pcre_vec) { int ovec[3]; auto* begin = in_str.data(); auto* p = begin; auto sz = in_str.size(); t1 = get_ticks(); while (pcre_exec(re.re, re.extra, p, sz - (p - begin), 0, 0, ovec, 3) > 0) { p = p + ovec[1]; matches++; } t2 = get_ticks(); total_ticks += t2 - t1; } //cout << re_pipe << endl; cout << "Time for individual re: " << total_ticks << "; matches: " << matches << endl; //cout << "Time for piped re: " << (t2 - t1) << endl; hs_scratch_t* scratch = NULL; int rc; if ((rc = hs_alloc_scratch(hs_db1, &scratch)) != HS_SUCCESS) { cout << "bad scratch: " << rc << endl; return -102; } struct cb_data cbdata; cbdata.ctx = &ctx; cbdata.matched = vector<int>(re_vec.size(), 0); cbdata.str = &in_str; t1 = get_ticks(); if ((rc = hs_scan(hs_db1, in_str.data(), in_str.size(), 0, scratch, match_cb, &cbdata)) != HS_SUCCESS) { cout << "bad scan: " << rc << endl; return -103; } t2 = get_ticks(); matches = 0; for_each(cbdata.matched.begin(), cbdata.matched.end(), [&matches](int elt) { matches += elt; }); cout << "Time for hyperscan re: " << (t2 - t1) << "; matches: " << matches << endl; return 0; }

結果は非常に印象的でした。1メガバイトのスパムメールと1000個までの正規表現のセットで、次の結果が得られました。

 PCREコンパイル時間：0.0138553
ハイパースキャンのコンパイル時間：4.94309; 約re：191; 合計日時：971
ハイパースキャンのシリアル化時間：0.00312218; サイズ：5242956バイト
ハイパースキャンのデシリアライズ時間：0.00359501; サイズ：5242956バイト
個々の日時：0.440707; マッチ：7
ハイパースキャンの時間：0.0770988; マッチ：7

プレフィルター

ハイパースキャンの最も印象的な機能の1つは、プレフィルターとして機能することです。このモードは、式にサポートされていないコンストラクトがある場合、たとえば同じバックトラッキングがある場合に便利です。このモードでは、ハイパースキャンは、指定されたサポートされていない式の保証されたスーパーセットである式を作成します。つまり、新しい式は最初の操作のすべてのケースで機能することが保証されていますが、他のケースでも機能し、誤検知操作が発生する可能性があります。そのため、pcreなどの従来の正規表現エンジンで結果を確認する必要があります（ただし、この場合はテキスト全体を実行する必要はありませんが、事前表現の最初から発生箇所まで確認する必要があります）。これは、次の図に明確に示されています。

コンパイルの問題

残念ながら、2つの不快な瞬間が明らかになりました。これらの最初はコンパイル時間です— pcreと比較して非現実的に長い時間がかかります。 2番目のポイントは、一部の式がコンパイル中に単純にプリフィルターにコンパイルされるという事実に関連しています。最も単純な「悪質な」表現は、たとえば次のとおりです。

 <a \ s [^>] {0,2048} \ bhref =（？：3D）？。？（https ?: [^> "'\＃] {8,29} [^>"' \＃：\ /？＆=]）[^>] {0,2048}>（？：[^ <] {0,1024} <（?! \ / A）[^>] {1,1024}>）{0、 99} \ s {0.10}（？！\ 1）https？[^ \ W <] {1,3} [^ <] {5}

結果として、式をコンパイルする前に、すべての事前フィルター式が最初にプロセスの別のフォークでチェックされました。式のコンパイルが長すぎる場合、このプロセスは破られ、式は絶望的とマークされます。つまり、常にpcreが使用されます。これらの表現の約4000が見つかりました。それらはすべて私の大好きなspamassassin'aから来ており、「脳のperl」と呼ばれる病気の非常に特徴的な産物です。 Intelエンジニアとのある程度のコミュニケーションの後、彼らは無限のコンパイルを修正しましたが、上記の正規表現はまだ1分程度でコンパイルされますが、実際の目的には受け入れられません。

ハイパースキャンが機能するためには、式のセットをいわゆる「クラス」に分解する必要があることも判明しました。これは、セットからの正規表現を介してチェックされる入力テキストのタイプです。そのようなクラスを次の図に示します。

コンパイルには、次のアプローチを使用しました。

別のプロセスで、式クラスのチェックを開始し、クラスごとに、コンパイル済みの有効なファイルが既に存在するかどうかを調べます。
そのようなファイルがない場合、または間違った式のセットが含まれている場合（式パターンのハッシュによってチェックされます）、予備フィルターのコンパイル時間をチェックしてコンパイルします。
すべての式がキャッシュでコンパイルされると、すべてのプロセスにメッセージをスキャナーに送信し、スキャナーがキャッシュ式を読み込み、pcreからhyperscanに切り替えることを受信しました。

このアプローチにより、高価で長いハイパースキャンコンパイルを待つのではなく、（pcreを使用して）開始直後にメールのチェックを開始し、コンパイルが完了したらすぐにpcreからハイパースキャンに切り替えます（キャッシュデスクを離れずに呼び出されます）。また、チェックおよびトリガーされた正規表現にビットセットを使用することにより、スキャンで既に実行されている文字の処理を切り替えるときに邪魔されないようにすることもできます。

結論

rspamd + hyperscanの過程で、次のようになりました。

それは：

 len：610591、time：2492.457ms real、882.251ms virtual
正規表現の統計：4095 pcre正規表現がスキャンされ、18個の正規表現が一致し、pcreを使用して694Mバイトがスキャンされました

次のようになりました：

 len：610591、time：654.596msリアルタイム、309.785msバーチャル
正規表現の統計：34 pcre正規表現がスキャンされ、41個の正規表現が一致、8.41Mバイトがpcreを使用してスキャンされ、 
スキャンされた合計9.56Mバイト

ハイパースキャンバージョンで一致する正規表現の数が多いのは、pcreに対して実行される構文ツリー最適化が原因ですが、ハイパースキャンの場合は役に立ちません（すべての式が同時にチェックされるため）。

Hyperscanバージョンはすでに生産されており、rspamdの新しいバージョンに含まれています。正規表現（DPI、プロキシなど）をチェックするためのパフォーマンスクリティカルなプロジェクト、およびテキスト内の静的な行を見つけるためのアプリケーションについて、ハイパースキャンを自信を持ってアドバイスできます。

最後のタスクでは、ハイパースキャンと、従来そのような目的で使用されていたaho-corasickアルゴリズムを比較しました。 Mischa Sandbergで知っている最速の実装を比較しました。

そのような行が多数あるメガバイト文字の1万行の静的行の比較結果（つまり、複雑度O（M + N）のaho-corrasicの最悪の条件、ここでMは見つかった行の数）：

動作コンパイル時間：0.0743811
ハイパースキャンのコンパイル時間：0.1547; 約re：0; 合計日時：7400
ハイパースキャンのシリアル化時間：0.000178297; サイズ：1250856バイト
ハイパースキャンデシリアライズ時間：0.000312379; サイズ：1250856バイト
ハイパースキャンの再時間：0.117938; 一致：3001024
行動の時間：0.100427; マッチ：3000144

残念ながら、ac-trieコードのエラーが原因でヒット数が収束しなかったのに対し、ハイパースキャンはミスを犯していませんでした。

また、この記事の資料はプレゼンテーションで入手できます。コードは、githubの rspamdプロジェクトで見ることができます

Hyperscanで複数の正規表現を見つける

ハイパースキャンについて簡単に

ハイパースキャンアーキテクチャ

テストコード

プレフィルター

コンパイルの問題

結論

More articles: