[發(fā)明專利]一種增量式的自動(dòng)機(jī)更新方法與系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201710112499.9
• 申請(qǐng)日: 2017-02-28
• 公開（公告）號(hào): CN107038026A
• 公開（公告）日: 2017-08-11
• 發(fā)明（設(shè)計(jì)）人: 劉燕兵;盧毓海;王曉娟;張春燕;譚建龍;郭莉
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院信息工程研究所
• 主分類號(hào): G06F9/44
• 分類號(hào): G06F9/44
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙)11200
• 代理人: 邱曉鋒

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

本發(fā)明旨在設(shè)計(jì)一種增量式的自動(dòng)機(jī)更新系統(tǒng)，用于信息過濾、內(nèi)容安全以及網(wǎng)絡(luò)數(shù)據(jù)深度包檢測(cè)等領(lǐng)域。基于規(guī)則匹配的內(nèi)容過濾系統(tǒng)經(jīng)常存在著規(guī)則更新的需求，每次的規(guī)則更新都耗時(shí)較長(zhǎng)且浪費(fèi)大量的計(jì)算資源。本發(fā)明旨在加速規(guī)則的更新操作，縮短規(guī)則的生效時(shí)間。

背景技術(shù)

在實(shí)際的內(nèi)容過濾系統(tǒng)中我們需要對(duì)相應(yīng)的匹配規(guī)則進(jìn)行實(shí)時(shí)的更新，每次更新匹配規(guī)則，對(duì)于基于自動(dòng)機(jī)的匹配算法而言，規(guī)則的更新也就意味著用于匹配的自動(dòng)機(jī)需要根據(jù)規(guī)則文件重新生成，從規(guī)則文件生成自動(dòng)機(jī)，這是一個(gè)相當(dāng)消耗時(shí)間的工作，會(huì)極大影響規(guī)則更新的生效時(shí)間。同時(shí)，對(duì)于一個(gè)負(fù)責(zé)某一種業(yè)務(wù)內(nèi)容匹配的計(jì)算機(jī)集群系統(tǒng)而言，每一次規(guī)則的更新都導(dǎo)致集群系統(tǒng)中的各個(gè)計(jì)算機(jī)都需要根據(jù)新的規(guī)則文件重新生成用于匹配的自動(dòng)機(jī)，而在每一臺(tái)匹配機(jī)上，從規(guī)則文件生成自動(dòng)機(jī)的過程都是完全相同的，這就造成了巨大的計(jì)算資源的浪費(fèi)。本發(fā)明利用數(shù)據(jù)差分方法實(shí)現(xiàn)的增量式自動(dòng)機(jī)更新方法可以有效加快規(guī)則生效時(shí)間并避免浪費(fèi)計(jì)算資源。

在計(jì)算機(jī)科學(xué)和信息學(xué)理論中，數(shù)據(jù)差分或差分壓縮是用來產(chǎn)生兩組數(shù)據(jù)(源數(shù)據(jù)和目標(biāo)數(shù)據(jù))之間的差異的技術(shù)說明，這種技術(shù)說明即是差分?jǐn)?shù)據(jù)。由差分?jǐn)?shù)據(jù)和源數(shù)據(jù)可以重新生成目標(biāo)數(shù)據(jù)，數(shù)據(jù)壓縮可以被看作是一種特殊情況下的數(shù)據(jù)差分。由于數(shù)據(jù)差分可以幫助減少硬盤空間或連接帶寬這樣的昂貴資源消耗，所以數(shù)據(jù)差分在軟件更新、數(shù)據(jù)傳輸和數(shù)據(jù)備份方面都有廣泛的應(yīng)用。

在計(jì)算機(jī)科學(xué)領(lǐng)域，串匹配算法一直是研究焦點(diǎn)之一。串匹配算法的應(yīng)用包括生物信息學(xué)、信息檢索、拼寫檢查、語(yǔ)言翻譯、數(shù)據(jù)壓縮、網(wǎng)絡(luò)入侵檢測(cè)等。隨著待處理信息量的不斷增強(qiáng)和實(shí)時(shí)處理的緊迫需求，對(duì)串匹配算法提出了更新的挑戰(zhàn)。

文獻(xiàn)“Heckel,Paul.A technique for isolating differences between files.Communications of the ACM.Volume,21.Issue,4.264–268,1978”提出了一種文本數(shù)據(jù)差分算法diff，diff已經(jīng)集成為Unix系統(tǒng)下的一個(gè)文件比較工具，他能夠輸出兩個(gè)本地文件之間的差異。典型的應(yīng)用是對(duì)相同文件的兩個(gè)版本進(jìn)行比較。diff命令逐行的顯示兩個(gè)文本文件間的差異。目前的實(shí)現(xiàn)也支持對(duì)二進(jìn)制文件進(jìn)行比較。diff的輸出為一個(gè)patch，他可以應(yīng)用到Unix系統(tǒng)中的另外一個(gè)程序中：patch。diff工具通過求解最長(zhǎng)公共序列問題來達(dá)到對(duì)文本文件的比較。

rsync(http://rsync.samba.org/documentation.html)是類unix系統(tǒng)下的數(shù)據(jù)鏡像備份工具，用于遠(yuǎn)程數(shù)據(jù)同步。rsync算法進(jìn)行數(shù)據(jù)差分的過程可以分為以下兩個(gè)步驟：(1)找出發(fā)生變化的文件；(2)找出文件中到底哪部分發(fā)生了變化，并用變化后的內(nèi)容替換原來的內(nèi)容。查找發(fā)生變化部分時(shí)，先找出可能相同的部分，然后確認(rèn)到底是不是相同，經(jīng)過這兩次校驗(yàn)后就能找到兩個(gè)文件中發(fā)生變化的部分，最后將發(fā)生變化的部分發(fā)送到目標(biāo)機(jī)器并用新的部分替代就的部分。

xdelta(http://code.google.com/p/xdelta/)算法是一個(gè)二進(jìn)制的diff工具，xdelta3是xdelta的一個(gè)增強(qiáng)版，功能更加強(qiáng)大，但命令和補(bǔ)丁與xdelta3的并不兼容，xdelta3不能處理大于2GB的文件。

文獻(xiàn)“Naive differences of executable code，Colin Percival,Computing Lab,Oxford University”公開了一種數(shù)據(jù)差分算法bsdiff。該算法是一個(gè)基于bzip2壓縮的二進(jìn)制數(shù)據(jù)差分算法。該算法生成二進(jìn)制差分?jǐn)?shù)據(jù)的步驟為：(1)讀入源文件，用后綴排序算法生成有序的索引；(2)用已生成的索引在目標(biāo)文件中搜索，找到近似匹配對(duì)。(3)生成最終的差分文件。bsdiff算法生成差分文件時(shí)的時(shí)間復(fù)雜度是O((n+m)logn)，恢復(fù)目標(biāo)文件時(shí)的時(shí)間復(fù)雜度是O(n+m)，生成差分文件時(shí)需要max(17n，9n+m)+O(1)字節(jié)的內(nèi)存，其中m為目標(biāo)文件的大小，n為源文件的大小。該算法能夠應(yīng)用到自動(dòng)機(jī)文件的數(shù)據(jù)差分上，壓縮率能夠達(dá)到0.2％-0.5％。

上述多種數(shù)據(jù)差分算法中，bsdiff算法具有最好的差分率，也適合用于對(duì)自動(dòng)機(jī)文件進(jìn)行數(shù)據(jù)差分，故本發(fā)明利用了bsdiff算法作為系統(tǒng)中的數(shù)據(jù)差分算法，實(shí)現(xiàn)了一種增量式的自動(dòng)機(jī)更新方法。

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