多個短規則模式匹配算法

Question

正如標題的進步，我們希望得到可用於模式具有以下約束匹配上最快的算法一些建議：

朗詞典：256

短，但不固定長度規則（從1到至多3首或4個字節深度）

小（150）數量的規則（如果3個字節）或中度（〜1K）如果比用於電流AC-DFA 4

更好的性能在Snort中還是比AC-DFA-Split再次分割我們由Snort編輯

基於軟件（最近的COTS系統，如E5 E5） 理想情況下，由於目前它們是128位寬，並且在不久的將來它們將是256反對對CPU的64

我們通過預過濾Snort的交流與Sigmatch紙顯示算法開始這個項目，但（與海灣合作委員會，但沒有與ICC編譯時〜12％的改善）可悲的結果並不令人印象深刻

之後我們試圖通過IPP庫利用SSE 4.2中出現的新模式匹配功能，但根本沒有性能增益（猜測直接在機器上執行代碼會更好，但肯定更復雜）

所以回到最初的想法。現在我們正在沿着Head Body Segmentation AC進行工作，但是我們知道，除非我們替換頭部提出的AC-DFA將很難獲得改進的性能，但是至少可以支持更多的規則，而不需要顯著性能下降

我們使用位並行的想法使用大量的內存用於長模式，但恰恰是問題的範圍已經減少到3首或4個字節都知道長至多從而使之成爲一個可行的替代

我們有發現特別Nedtries，但想知道你們是怎麼想的，或者如果有更好的替代品

理想情況下，源代碼將在C a根據開源許可證。

---

恕我直言，我們的想法是要搜索的東西，同時移動1個字節，以應付不同的大小，但這樣做非常有效地利用大多數並行可以通過使用SIMD/SSE，也試圖將少枝儘可能

我不知道，如果在逐位的方式或字節明智

---

返回一個適當的鍵盤這樣做：d

實質上，大多數算法不能正確利用當前的硬件功能和限制。他們非常緩存效率低下，不會說他們不利用目前在COTS CPU中存在的功能，這些功能允許您具有一定的平行度（SIMD，SSE，...）

這是preciselly就是我們正在尋找的算法（或已有的算法的實現），妥善認爲這一切，與沒有試圖覆蓋所有規則長度的advantag，只是短暫的人

例如，我看到一些關於NFA的文章強調說，由於緩存效率正常，增強了平行度等原因，它們的性能可能與DFA配對的內存要求少得多。

Answer 1

聽起來好像您已經在使用hi性能模式匹配。除非你有一些聰明的新算法，或者可以指出數據或規則中的一些統計偏差，否則很難加速原始算法。

您可能會考慮將對作爲模式匹配元素處理。這會使狀態機的分支因素變大，但你大概不關心RAM。這可能會給你買兩個因子。

當算法上用完時，人們通常會在彙編程序中採取謹慎的手動編碼，包括巧妙地使用SSE指令。處理髮現的唯一序列可能會有幫助的技巧是對元素進行一系列比較，並通過並/或而不是條件分支來形成布爾結果，因爲分支是昂貴的。 SSE說明可能對此有所幫助，但它們的對齊要求可能會強制您將它們複製4次或8次。

如果您搜索的字符串很長，您可能會分配規則的子集來分離CPU（線程）。劃分規則可能會很棘手。

Answer 2

請看看： http://www.slideshare.net/bouma2 支持1字節和2字節類似於Baxter上面寫的。不過，如果你能提供你期望在數據庫中使用的單字節和雙字節字符串的數量，以及你期望處理的流量類型（互聯網，公司等），這​​將會有所幫助 - 畢竟，許多單字節字符串可能以每個字節的匹配結束。 Bouma2的想法是允許將事件統計納入預處理階段，從而減少誤報率。