タイトルが進むにつれて、次の制約を伴うパターン マッチングに利用できる最速のアルゴリズムについてアドバイスを求めたいと思います。
長い辞書: 256
短いが固定長ではないルール (最大で 1 から 3 または 4 バイトの深さ)
少数 (150) のルール (3 バイトの場合) または中 (~1K) の場合は 4
Snort で使用されている現在の AC-DFA または Snort で再び使用される AC-DFA-Split よりも優れたパフォーマンス
ソフトウェアベース (E5 の E3 のような最近の COTS システム) 理想的には、現在は 128 ビット幅であり、近い将来には CPU の 64 に対して 256 になるため、いくつかの SIMD / SSE を採用したいと考えています。
このプロジェクトは、Sigmatch ペーパーに示されているアルゴリズムを使用して Snort AC を事前にフィルタリングすることから始めましたが、残念ながら結果はそれほど印象的ではありませんでした (GCC でコンパイルすると最大 12% 改善されましたが、ICC では改善されませんでした)。
その後、IPP ライブラリを介して SSE 4.2 に存在する新しいパターン マッチング機能を活用しようとしましたが、パフォーマンスはまったく向上しませんでした (マシン コードで直接実行する方が良いと思いますが、より複雑になることは間違いありません)。
というわけで、元のアイデアに戻ります。現在、Head Body Segmentation AC の方針に沿って作業していますが、提案されている頭側の AC-DFA を置き換えない限り、パフォーマンスを向上させるのは非常に難しいことを認識していますが、少なくとも、大幅なパフォーマンス低下
ビット並列処理のアイデアを使用すると長いパターンに大量のメモリが使用されることは承知していますが、正確には問題の範囲はせいぜい 3 または 4 バイトの長さに縮小されているため、実行可能な代替手段となっています。
特にNedtriesを見つけましたが、皆さんの意見やより良い代替案があるかどうかを知りたいです
理想的には、ソース コードは C であり、オープン ソース ライセンスの下にあります。
IMHO、私たちのアイデアは、一度に1バイト移動してさまざまなサイズに対処するものを検索することでしたが、SIMD / SSEを使用して可能な限り多くの並列処理を利用し、可能な限り分岐を少なくしようとすることで非常に効率的に行います
これを少し賢明な方法で行うのか、それともバイト単位で行うのかはわかりません
適切なキーボードに戻る:D
本質的に、ほとんどのアルゴリズムは、現在のハードウェア機能や制限を正しく活用していません。それらはキャッシュが非常に非効率的であり、特定レベルの並列処理 (SIMD、SSE など) を可能にする COTS CPU に現在存在する機能を利用していないことは言うまでもありません。
これはまさに私たちが求めているものであり、すべてのルールの長さをカバーしようとするのではなく、短いルールのみをカバーしようとするという利点を備えた、すべてを適切に考慮するアルゴリズム (または既存のアルゴリズムの実装) です。
たとえば、適切なキャッシュ効率、強化された並列処理などにより、今日の NFA のパフォーマンスは、はるかに少ないメモリ要件で DFA と対になる可能性があると主張している NFA に関するいくつかの論文を見てきました。