熊　宇

(武漢數(shù)字工程研究所　武漢　430205)

?

一種用于軟件靜態(tài)測(cè)試的關(guān)鍵字并行搜索方法*

熊宇

(武漢數(shù)字工程研究所武漢430205)

摘要針對(duì)軟件靜態(tài)測(cè)試工具在執(zhí)行代碼分析過程中消耗大量時(shí)間用于搜索掃描的問題，提出一種基于模式匹配技術(shù)的多關(guān)鍵詞并行搜索方法，建立了一種多關(guān)鍵詞并行搜索框架。通過設(shè)計(jì)一個(gè)仿真系統(tǒng)，驗(yàn)證了該搜索架構(gòu)的正確性，達(dá)到了比較好的效果，搜索速度有明顯提升。

關(guān)鍵詞軟件靜態(tài)測(cè)試; 模式匹配; 多關(guān)鍵詞并行搜索

Class NumberTP311.5; TP391.1

1引言

軟件靜態(tài)測(cè)試是軟件測(cè)試重要組成部分。其基本作用是在不運(yùn)行代碼的情況下，通過語法分析、詞法分析、控制流和數(shù)據(jù)流分析等技術(shù)對(duì)程序代碼進(jìn)行掃描，驗(yàn)證代碼是否滿足規(guī)范性、安全性、可靠性和可維護(hù)性等指標(biāo)要求的一種代碼分析技術(shù)。大量的軟件測(cè)試標(biāo)準(zhǔn)或者軟件測(cè)試實(shí)施細(xì)則都把靜態(tài)測(cè)試作為第一測(cè)試內(nèi)容。由于現(xiàn)代軟件系統(tǒng)的代碼體量越來越大，采用現(xiàn)有的靜態(tài)分析工具軟件對(duì)代碼進(jìn)行靜態(tài)分析的時(shí)間越來越長(zhǎng)。如何快速高效地進(jìn)行代碼靜態(tài)分析成為靜態(tài)分析工具急需突破的一個(gè)重點(diǎn)。而關(guān)鍵詞、特定變量或者值的掃描和搜索是實(shí)現(xiàn)軟件靜態(tài)分析的基本功能，其執(zhí)行效率決定了靜態(tài)分析工具軟件的執(zhí)行速度。提高關(guān)鍵詞搜索效率是縮短靜態(tài)分析時(shí)間的重要手段。

2常用的靜態(tài)分析工具軟件和關(guān)鍵

詞搜索技術(shù)

2.1靜態(tài)分析工具軟件

常用的工具有Klockwork、Logiscope、Testbed等。然而，軟件靜態(tài)分析技術(shù)由于其原有算法的特殊性——搜索關(guān)鍵詞及其它字符串、值并建立各類表格占用的時(shí)間、分析占用的時(shí)間、資源問題，導(dǎo)致靜態(tài)分析過程通常很慢，無法如預(yù)期的那樣有效，也沒有真正成為開發(fā)人員的日常開發(fā)工作的一部分。其中搜索關(guān)鍵詞及其它字符串、值等并建立各類表格的時(shí)間是影響靜態(tài)分析軟件執(zhí)行效率的主要因素。

2.2關(guān)鍵詞搜索技術(shù)

軟件靜態(tài)分析中的關(guān)鍵詞搜索的實(shí)質(zhì)是計(jì)算機(jī)對(duì)軟件代碼預(yù)先進(jìn)行加工，即對(duì)代碼內(nèi)容全面地分析，將那些出現(xiàn)在代碼中的關(guān)鍵詞等抽取出來進(jìn)行標(biāo)識(shí)，定位的過程。當(dāng)軟件代碼的詞法、語法和語義要素確定后(通常由軟件代碼采用的編程語言決定)，關(guān)鍵詞集合就確定下來。采用的關(guān)鍵詞搜索技術(shù)實(shí)質(zhì)上就是通常的字符串匹配算法，或者更一般地說是模式匹配算法[1]。

2.3模式匹配技術(shù)

模式匹配問題是計(jì)算機(jī)科學(xué)中的一個(gè)基本問題，最初起源于人工智能領(lǐng)域的研究，在入侵檢測(cè)、內(nèi)容過濾、計(jì)算機(jī)病毒、特征碼匹配、基因序列比較等應(yīng)用中起著重要的作用。

模式匹配問題是給定一個(gè)子串P，從待查找的字符串T中找出與P相同的所有子串。P稱為模式，T稱為目標(biāo)。如果T中存在一個(gè)或多個(gè)模式為P的子串，則給出子串P在T中的位置，稱為模式匹配成功，否則匹配失敗。

模式匹配的基本思想是：用P中的字符依次與T中的字符比較，采用自左向右匹配，匹配失敗時(shí)，返回到開始字符的下一個(gè)字符重新開始匹配。這種匹配失敗時(shí)重新開始匹配的字符位置與上次匹配的字符位置的距離叫移動(dòng)距離或安全移動(dòng)距離。提高模式匹配的效率就是盡量增大匹配失敗時(shí)的安全移動(dòng)距離。

模式匹配算法的種類有很多，大致可分為兩種類別，如圖1所示。根據(jù)一次匹配模式串?dāng)?shù)量的不同，模式匹配算法一般可以分為單模式匹配、多模式匹配；根據(jù)匹配成功的結(jié)果的準(zhǔn)確程度可以劃分為精確匹配和模糊匹配等。

圖1　模式匹配算法的分類

單模式匹配算法一次只能匹配文本串中一個(gè)模式串，常用的有Quick Search(QS)算法[2]、Knuth-Morris-Patt(KMP)算法[3]、Boyer-Moore(BM)算法[4]等。單模式匹配算法的性能隨著匹配規(guī)則數(shù)量的增加呈線性下降，多模式匹配算法是一次可同時(shí)匹配多個(gè)模式串[5]。常用的有Wu-Manber(W-M)快速匹配算法[6～7]、Aho-Corasick(AC)算法[8]等。

AC算法是基于有限狀態(tài)自動(dòng)機(jī)的DFSA(Deterministic Finite State Automata)，在匹配前需要對(duì)模式集進(jìn)行預(yù)處理，構(gòu)造一個(gè)樹型有限自動(dòng)機(jī)，然后對(duì)文本進(jìn)行一次掃描，就可發(fā)現(xiàn)模式串在文本中的所有出現(xiàn)位置。AC算法在匹配時(shí)被匹配的字符串按順序輸入，無法大距離跳躍字符串的比較操作，影響匹配速度的提高。W-M算法是基于BM單模式匹配算法上改進(jìn)而生產(chǎn)的一種多模式匹配算法，采用跳躍的思想、Hash散列的方法等多種方法提高匹配效率。

3多關(guān)鍵字并行搜索方法

3.1W-M多模式快速匹配算法研究

定義1：模式串Pi。在字符串比較過程中用來判斷待比較字符串是否正確的標(biāo)準(zhǔn)字符串，設(shè)最短長(zhǎng)度為m。

定義2：模式串集合P={P1，P2，…，Pi，…，Pw}。由若干個(gè)模式串組成的集合。

定義3：前綴子串。長(zhǎng)度為n的字符串從左往右取長(zhǎng)度為b(b≤m

定義4：后綴子串。長(zhǎng)度為n的字符串從右往左取長(zhǎng)度為b(b≤m

定義5：模式串摘要。由單向Hash函數(shù)對(duì)模式串進(jìn)行作用而產(chǎn)生的固定長(zhǎng)度的值。

W-M匹配算法是一種基于后綴搜索的多模式匹配算法，最短模式串長(zhǎng)度決定了它可以跳過的下一個(gè)安全距離。假設(shè)最短模式串P1的長(zhǎng)度為m，當(dāng)X出現(xiàn)在模式串中，安全移動(dòng)距離為m-q0，q0在所有qi(X在模式串Pi中出現(xiàn)的位置)中最大；當(dāng)X不在任何模式串中出現(xiàn)時(shí)，安全移動(dòng)距離為m-b+1。

雖然W-M算法具有字符跳躍距離大的優(yōu)點(diǎn)，但也存在很多缺點(diǎn)[9]。

針對(duì)多模匹配W-M算法存在的不足，文獻(xiàn)[10]提出了一種改進(jìn)的多模式匹配H-W-M(Hardware-Wu-Manber)算法。與W-M算法一樣，最短模式串P1的長(zhǎng)度為m，將所有模式串分成長(zhǎng)度為m的字符組，分別在第一個(gè)字符組的前綴和后綴劃分出長(zhǎng)度為b的字符子串BP和BL。當(dāng)T從左到右經(jīng)過寬度為m的匹配窗口時(shí)，其后綴X與窗口中的每一個(gè)模式串的長(zhǎng)度為b的子串(含前綴和后綴)進(jìn)行比較。如果匹配成功，則進(jìn)行全字符串的精確比較，判斷是否完全匹配，如果不成功，則將T跳躍盡可能長(zhǎng)的距離，左移入窗口，取新的后綴開始下一次匹配。與W-M算法不同的是，該算法通過進(jìn)一步考察X的后續(xù)子串X′與qi位置后

字符串的相關(guān)度，為字符串的下一次匹配增大安全移動(dòng)距離，從而加快匹配速度。當(dāng)X出現(xiàn)在模式串中，安全移動(dòng)距離為m-q0+b-a，q0在所有qi(X在模式串Pi中出現(xiàn)的位置)中最大；當(dāng)X不在任何模式串中出現(xiàn)時(shí)，安全移動(dòng)距離為m-a，其中a是X與模式串前綴BP的相關(guān)度，a

圖2　改進(jìn)的W-M模式匹配算法操作示意圖

事實(shí)上，至今為止，對(duì)W-M算法改進(jìn)大都集中在如何加快文本T的移動(dòng)上，而在后綴的匹配方面改進(jìn)很少，為了進(jìn)一步提高X在模式串Pi中的比較時(shí)間，本文采用摘要值匹配方法進(jìn)一步改善模式串比較效率。

圖3　X的hash值與Pbi的hash表匹配

3.2基于多模匹配算法的關(guān)鍵詞并行搜索架構(gòu)

設(shè)key={k1,k2,…,kw}為關(guān)鍵詞集合，與上述的模式串集合相對(duì)應(yīng)。譬如：key={begin,end,if,else,while,for,…}。找出軟件代碼T中所有的關(guān)鍵詞并確定每一個(gè)關(guān)鍵詞ki所在的位置。

3.2.1關(guān)鍵詞集合的預(yù)處理

為實(shí)現(xiàn)基于多模式匹配算法的關(guān)鍵詞并行搜索，需要對(duì)所有關(guān)鍵詞串進(jìn)行預(yù)處理并建立五個(gè)初始化表，參見表1。

表1　五個(gè)初始化表的作用

3.2.2并行搜索架構(gòu)

搜索時(shí)，讀取程序代碼的待匹配字符串T，從左向右送入匹配窗口，對(duì)落在窗口中的子串Tm執(zhí)行下述操作：

7) 查找SHIFT表獲取最大移動(dòng)距離，判斷是否到達(dá)T的最后一個(gè)字符，是，則停止搜索，退出；否，則將T移動(dòng)相應(yīng)距離進(jìn)入匹配窗口，轉(zhuǎn)1)。

并行搜索架構(gòu)參見圖4。

4驗(yàn)證與分析

通過設(shè)計(jì)一個(gè)仿真系統(tǒng)，驗(yàn)證了該搜索架構(gòu)的正確性，達(dá)到了比較好的效果。尤其是采用文獻(xiàn)[10]提出的硬件實(shí)現(xiàn)方法后，搜索速度非常高。

圖4　基于多模匹配的關(guān)鍵詞并行搜索架構(gòu)

關(guān)于時(shí)間復(fù)雜度：不考慮構(gòu)造相關(guān)表的預(yù)處理時(shí)間。計(jì)算前綴相關(guān)度時(shí)間=a；計(jì)算H(Tm)時(shí)間Thm=O(m)；計(jì)算H(X)時(shí)間Thx=O(b)；判斷X是否在窗口之中出現(xiàn)，實(shí)際上只是一個(gè)按照索引查表的過程；把原WM算法(若k個(gè)關(guān)鍵詞，O(km+kb))的字符串比較的過程變成了一個(gè)查表過程，極大的提高了判斷速度。從右向左移動(dòng)T的次數(shù)Cshift=O(n/m)(設(shè)T的長(zhǎng)度為n，)因此，整體時(shí)間復(fù)雜度為：(Thm+Thx+a)Cshift=O(n+nb/m+na/m)。

關(guān)于空間復(fù)雜度：相比較原算法，增加了SUFF表，該表的空間大小取決于b的長(zhǎng)度，在不優(yōu)化的前提下，占用空間為2b，可見該架構(gòu)占用了較大的空間資源。但是在當(dāng)前存儲(chǔ)器資源越來越便宜的情況下，還是可取的。

關(guān)于哈希表的構(gòu)造：不難看出，F(xiàn)LAG表和SUFF表都是稀疏表，可以采用相關(guān)的優(yōu)化存儲(chǔ)方法來實(shí)現(xiàn)它們，從而降低對(duì)空間的占用。

5結(jié)語

基于模式匹配技術(shù)，論文提出了一種的多關(guān)鍵字并行搜索方法和架構(gòu)，并把它應(yīng)用于軟件靜態(tài)測(cè)試過程的關(guān)鍵詞搜索與匹配檢查過程，取得了較好的效果。目前國內(nèi)關(guān)于軟件測(cè)試實(shí)現(xiàn)方法研究的文獻(xiàn)很少，希望本文的工作對(duì)相關(guān)的研究有一定的啟發(fā)作用，論文提出的方法也可以廣泛應(yīng)用于信息檢索。

參 考 文 獻(xiàn)著錄規(guī)則 中的責(zé)任者采用姓前名后的著錄形式。歐美著者的名可縮寫,姓大寫,姓和縮寫的名之間不可用“.”隔開,而是用空格。如用中譯名,可以只著錄其姓。如原文中作者為“P．S．昂溫”則在本刊要求中應(yīng)寫成“昂溫 P S”,Albert Einstein Seny應(yīng)寫成EINSTEIN A S。 的責(zé)任者之間用“,”分隔。不超過3個(gè)時(shí),全部照錄。超過3個(gè)時(shí),只著錄前3個(gè)責(zé)任者,其后加“,等”,外文用“,et al”,“et al”不必用斜體。

[1] 歐嵬,吳純青.幾種字符串匹配算法的分析和比較[J].微處理機(jī),2007,28(4)：59-61

OU Wei, WU Chunqing. Analysis and Comparison of Several String Matching Alogrithms[J]. Microprocessors,2007,28(4):59-61.

[2] KNUTH D E, MORRIS H, PRATT V R. Fast pattern matching in strings[J]. SIAM J Comp,1977,6(1):323-350.

[3] SUNDAY D M. A very fast substring search algorithm[J]. Communications of the ACM,1990,33(8):132-142.

[4] BOYER R S, MOORE J S. A fast string searching algorithm[J]. Communications of the ACM,1977,20(10):762-772.

[5] 袁榮亮.基于入侵檢測(cè)系統(tǒng)的多模匹配算法的研究[D].西安：西安科技大學(xué),2008.

YUAN Rongliang. Research of the Multi-Pattern Matching in Intrusion Detection[D]. Xi’an: Xi’an University of Science and Technology,2008.

[6] WU Sun, MANBER U. A fast algorithm for Multi-pattern searching[R]. Tucson: Department of Computer Science, University of Arizona,1994:1-11.

[7] Wu S, Manber U. Agrep-A fast approximate pattern matching tool[C]//Proc. Of the USENIX Winter Technical Conf. USENIX,1992:153-162.

[8] AHO A V, CORASICK M J. Efficient string matching: an aid to bibliographic search[J]. Communications of the ACM,1975,18(6):333-340.

[9] 劉許剛,黃海,馬宏.一種基于分段匹配的字符串匹配算法[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(3):128-131.

LIU Xugang, HUANG Hai, MA Hong. A String Matching Algorithm Based on Segmenting Matching[J]. Computer Applications and Software,2012,29(3):128-131.

[10] 熊宇.一種安全規(guī)則可配置的網(wǎng)絡(luò)防護(hù)專用電路的設(shè)計(jì)與實(shí)現(xiàn)[D].武漢：武漢大學(xué),2015.

XIONG Yu. The Design and Implementation of a Specific Network Security Protection Circuit with Configurable Rules[D]. Wuhan: Wuhan University,2015.

一.總要求

為了幫助向本刊投稿的作者按規(guī)范著錄參考文獻(xiàn),現(xiàn)將常見類型文獻(xiàn)的著錄格式作如下要求。

本刊要求雙語參考文獻(xiàn),所有的中文參考文獻(xiàn)均需附英文譯文,示例如下:

示例1:

[1] 焦李成,杜海峰,等．免疫優(yōu)化計(jì)算、學(xué)習(xí)與識(shí)別[M].北京:科學(xué)出版社,2006．

JIAO Licheng, DU Haifeng, et al Immune optimization calculation 、Learning and Recognition [M]. Beijing: Science Press,2006．

[2] 李詩靈,陳寧,趙學(xué)彧．基于粒子群算法的城市軌道交通接運(yùn)公交規(guī)劃[J]．武漢理工大學(xué)學(xué)報(bào)(交通工程與科學(xué)版)2010,34(4)780-783．

LI Shiling, CHEN Ning, ZHAO Xueyu． Planning of Feder Bus to the Urban Rail Transit Based on Particle Swarm Optimization[J]． Journal of Wuhan University of Technology(Transportation Science & Enginering),2010,34(4):780-783．

示例2:馬克思,恩格斯．示例2:YELLAND R L, JONES S C, EASTON K S, et al．

二.圖書和期刊的著錄格式

◆普通圖書(原著):

[序號(hào)]著者．書名[M]．版本(第1版不著錄)．出版地:出版者,出版年:引文頁碼．

[3]余敏．出版集團(tuán)研究[M]．北京:中國書籍出版社,2001:179-193．

[4]中國社會(huì)科學(xué)院語言研究所詞典編輯室．現(xiàn)代漢語詞典[M]．修訂本．北京:商務(wù)印書館,1996:258-260．

[5]CRAWFPRD GORMAN M． Future libries: dreams, madnes, &reality[M]． Chicago: America Library Asociation,1995．

◆普通圖書(譯著):

[序號(hào)]著者．書名[M]．譯者,譯．版本．出版地:出版者,出版年:引文頁碼．

[6]AGRAWAL G P． 非線性光纖光學(xué)[M]．胡國絳,黃超,譯．天津:天津大學(xué)出版社,1992:179-193．

[7]霍斯尼 R K． 谷物科學(xué)與工藝學(xué)原理[M]．李慶龍,譯．2版．北京:中國食品出版社,1989:15-20．

◆期刊(有卷)

[序號(hào)]著者.題名[J]．刊名,出版年份,卷(期)引文頁碼．

[8]蔣超,張沛,張永軍,等．基于SRLG不相關(guān)的共享通路保護(hù)算法[J]．光通信技術(shù),2007,31(7):4-6．

[9]DIANOV E M, BUFETOV I A, BUBNOV M M, et al． Thre-cascaded 1407nm Raman laserbased on phosphorusdoped silica fiver[J]． OPTICS LETTERS,2000,26(6):402-404．

◆期刊(無卷)

[序號(hào)]著者.題名[J]．刊名,出版年份(期):引文頁碼．

[10]周可,馮丹,王芳,等．網(wǎng)絡(luò)磁盤陣列流水調(diào)度研究[J]．計(jì)算機(jī)學(xué)報(bào),2005(3):319-325．

[11]VLATK V, MARTIN B P． Basic of quantum compwtation[J]． Proces in Quantum Electronics,1998(22):1-39．

三.電子文獻(xiàn)的著錄格式

◆電子文獻(xiàn):

[序號(hào)]主要責(zé)任者．題名:其他題名信息[文獻(xiàn)類型標(biāo)志/文獻(xiàn)載體標(biāo)志]．出版地:出版者,出版年(更新或修改日期)[引用日期]．獲取和訪問路徑．

[12]Online Computer Library Center, Inc． History of OCLC[EB/OL]．[2000-01-08]．htp://www．oclc．org．

[11]蕭鈺．出版業(yè)信息化邁入快車道[EB/OL]．(2001-12-19)[2002-04-15]．htp:∥www．creader．com/news/200112190019．htm．

四.學(xué)位論文與論文集的著錄格式

◆學(xué)位論文:

[序號(hào)]著者．題名[D]．出版地:出版者,出版年:引文頁碼．

[13]孫玉文．漢語變調(diào)構(gòu)詞研究[D]．北京:北京大學(xué)文學(xué)院,2000．

◆論文集:

[序號(hào)]著者．題名[C]//著者．專題名:其他題名．出版地:出版者,出版年:引文頁碼．

[14]白書龍．植物開花研究[C]//李承森．植物科學(xué)進(jìn)展．北京:高等教育出版社,1998:146-163．

[15]AZIEM M M A, ISMAIEL H M． Quantitative and qualitative Evaluations of Image Enhancement Techniques[C]//Procedings of the 46th IEEE International Midwest Symposium on Circuits and Systems,2003:664-669．

收稿日期:2016年1月10日,修回日期:2016年2月19日

作者簡(jiǎn)介:熊宇,女,碩士,助理工程師,研究方向：軟件測(cè)試。

中圖分類號(hào)TP311.5; TP391.1

DOI:10.3969/j.issn.1672-9722.2016.07.042

A Parallel Search Method of Multiple Key Words in Software Static Testing Based on Pattern Match

XIONG Yu

(Wuhan Digital Engineering Institute, Wuhan430205)

AbstractIt is known that software static testing tool have to spent huge of time for scanning search when it begin to implement the code analysis process. In order to solve this problem a multiple key parallel search method based on pattern match has been proposed, and a multiple key parallel search framework is established. Through the design of a simulation system, the correctness of the search framework is verified, the search speed is significantly improved.

Key Wordssoftware static testing, pattern match, multiple key parallel search