[發(fā)明專利]用于模式匹配的方法、設(shè)備和電路

有效

• 申請?zhí)枺?/td>: 201310260868.0
• 申請日: 2013-06-27
• 公開（公告）號: CN104252469B
• 公開（公告）日: 2017-10-20
• 發(fā)明（設(shè)計(jì)）人: 劉丹;潘永峰;劉洋;陸泳;英彥
• 申請（專利權(quán)）人: 國際商業(yè)機(jī)器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國國際貿(mào)易促進(jìn)委員會(huì)專利商標(biāo)事務(wù)所11038
• 代理人: 李玲

技術(shù)領(lǐng)域

本發(fā)明涉及信息處理技術(shù)，更具體地說，涉及用于模式匹配的方法、設(shè)備和電路結(jié)構(gòu)。

背景技術(shù)

模式匹配指的是在一個(gè)模式流中尋找某種特定模式。模式匹配是計(jì)算機(jī)應(yīng)用中的一種基本技術(shù)。例如，在文本（text）中尋找目標(biāo)字符串（string）就是一種模式匹配。在這一場景下，所要找到的目標(biāo)字符串對應(yīng)于上述特定模式，而所述文本對應(yīng)于上述模式流。又例如，已被廣泛應(yīng)用于入侵檢測/入侵防御、阻止垃圾郵件、防病毒、防數(shù)據(jù)泄漏、內(nèi)容過濾等領(lǐng)域的深度包檢測（DPI）技術(shù)，其檢測數(shù)據(jù)流中是否存在具有攻擊特征的數(shù)據(jù)包或數(shù)據(jù)包序列。在這一場景下，數(shù)據(jù)流對應(yīng)于上述模式流，而具有攻擊特征的數(shù)據(jù)包或數(shù)據(jù)包序列對應(yīng)于上述特定模式。

一方面，已經(jīng)針對模式匹配進(jìn)行了長時(shí)間的研究，并且得到了大量的軟件算法。另一方面，本領(lǐng)域技術(shù)人員可以理解，硬件平臺中各電路組件是并行工作的，所以可以達(dá)到更快的速度。相應(yīng)地，期望用硬件來實(shí)現(xiàn)這些軟件算法，從而提高模式匹配的速度。然而，將整個(gè)軟件算法移植到硬件平臺上通常面臨著成本高和復(fù)雜性高的問題。因此，可以考慮將軟件算法中適合硬件實(shí)現(xiàn)的一部分移植到硬件平臺上。

發(fā)明內(nèi)容

本發(fā)明提供了用于模式匹配的方法、設(shè)備和電路。

根據(jù)本發(fā)明實(shí)施例的用于模式匹配的方法，所述模式匹配在模式流中尋找目標(biāo)模式，所述模式流和目標(biāo)模式均由元素組成，該方法包括：獲取目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)；初始化暫存區(qū)，其中所述暫存區(qū)指示模式流中的一個(gè)區(qū)間；判斷暫存區(qū)中所述目標(biāo)元素的出現(xiàn)次數(shù)是否達(dá)到所述目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)；響應(yīng)于暫存區(qū)中所述目標(biāo)元素的出現(xiàn)次數(shù)未達(dá)到所述目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)，更新所述暫存區(qū)后返回所述判斷步驟；響應(yīng)于暫存區(qū)中所述目標(biāo)元素的出現(xiàn)次數(shù)達(dá)到所述目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)，輸出所述暫存區(qū)中的元素供后續(xù)處理。

根據(jù)本發(fā)明實(shí)施例的一種用于模式匹配的設(shè)備，所述模式匹配在模式流中尋找目標(biāo)模式，所述模式流和目標(biāo)模式均由元素組成，該設(shè)備包括：獲取裝置，配置為獲取目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)；暫存區(qū)初始化裝置，配置為初始化暫存區(qū)，其中所述暫存區(qū)指示模式流中的一個(gè)區(qū)間；比較裝置，配置為判斷暫存區(qū)中所述目標(biāo)元素的出現(xiàn)次數(shù)是否達(dá)到所述目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)；更新裝置，配置為響應(yīng)于暫存區(qū)中所述目標(biāo)元素的出現(xiàn)次數(shù)未達(dá)到所述目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)，更新所述暫存區(qū)后返回進(jìn)行所述判斷；輸出裝置，配置為響應(yīng)于暫存區(qū)中所述目標(biāo)元素的出現(xiàn)次數(shù)達(dá)到所述目標(biāo)模式中的目標(biāo)元素的出現(xiàn)次數(shù)，輸出所述暫存區(qū)中的元素供后續(xù)處理。

根據(jù)本發(fā)明實(shí)施例的一種用于模式匹配的電路，包括：暫存模塊，用于存儲當(dāng)前被處理的元素；元素解析模塊，用于確定新加入暫存區(qū)的元素；暫存區(qū)特征表更新模塊，用于根據(jù)所述元素解析模塊的確定結(jié)果，更新暫存區(qū)中目標(biāo)元素的出現(xiàn)次數(shù)；暫存區(qū)特征表存儲模塊，用于記錄暫存區(qū)中各目標(biāo)元素的出現(xiàn)次數(shù)；參考特征表存儲模塊，用于存儲參考特征表；比較模塊，用于比較所述暫存區(qū)特征表存儲模塊和所述參考特征表存儲模塊，以判斷暫存區(qū)中各元素的出現(xiàn)次數(shù)是否達(dá)到目標(biāo)模式中各元素的出現(xiàn)次數(shù)。

根據(jù)本發(fā)明實(shí)施例所提供的技術(shù)方案，可以加快模式匹配的速度。

附圖說明

通過結(jié)合附圖對本公開示例性實(shí)施方式進(jìn)行更詳細(xì)的描述，本公開的上述以及其它目的、特征和優(yōu)勢將變得更加明顯，其中，在本公開示例性實(shí)施方式中，相同的參考標(biāo)號通常代表相同部件。

圖1是適于用來實(shí)現(xiàn)本發(fā)明實(shí)施方式的示例性計(jì)算機(jī)系統(tǒng)/服務(wù)器12的框圖；

圖2是根據(jù)本發(fā)明實(shí)施例的用于模式匹配的方法的流程圖；

圖3是根據(jù)本發(fā)明實(shí)施例的用于模式匹配的設(shè)備的方框圖；

圖4是根據(jù)本發(fā)明實(shí)施例的用于模式匹配的方法的運(yùn)行示意圖；

圖5是根據(jù)本發(fā)明實(shí)施例的用于模式匹配的電路的方框圖；

圖6A和圖6B示出了兩個(gè)時(shí)刻的單脈沖電流時(shí)域響應(yīng)進(jìn)行疊加的情況。

具體實(shí)施方式

下面將參照附圖更詳細(xì)地描述本公開的優(yōu)選實(shí)施方式。雖然附圖中顯示了本公開的優(yōu)選實(shí)施方式，然而應(yīng)該理解，可以以各種形式實(shí)現(xiàn)本公開而不應(yīng)被這里闡述的實(shí)施方式所限制。相反，提供這些實(shí)施方式是為了使本公開更加透徹和完整，并且能夠?qū)⒈竟_的范圍完整地傳達(dá)給本領(lǐng)域的技術(shù)人員。