一種用于軟件靜態測試的關鍵字并行搜索方法*

熊　宇

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

?

一種用于軟件靜態測試的關鍵字并行搜索方法*

熊宇

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

摘要針對軟件靜態測試工具在執行代碼分析過程中消耗大量時間用于搜索掃描的問題，提出一種基于模式匹配技術的多關鍵詞并行搜索方法，建立了一種多關鍵詞并行搜索框架。通過設計一個仿真系統，驗證了該搜索架構的正確性，達到了比較好的效果，搜索速度有明顯提升。

關鍵詞軟件靜態測試; 模式匹配; 多關鍵詞并行搜索

Class NumberTP311.5; TP391.1

1引言

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

2常用的靜態分析工具軟件和關鍵

詞搜索技術

2.1靜態分析工具軟件

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

2.2關鍵詞搜索技術

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

2.3模式匹配技術

模式匹配問題是計算機科學中的一個基本問題，最初起源于人工智能領域的研究，在入侵檢測、內容過濾、計算機病毒、特征碼匹配、基因序列比較等應用中起著重要的作用。

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

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

模式匹配算法的種類有很多，大致可分為兩種類別，如圖1所示。根據一次匹配模式串數量的不同，模式匹配算法一般可以分為單模式匹配、多模式匹配；根據匹配成功的結果的準確程度可以劃分為精確匹配和模糊匹配等。

圖1　模式匹配算法的分類

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

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

3多關鍵字并行搜索方法

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

定義1：模式串Pi。在字符串比較過程中用來判斷待比較字符串是否正確的標準字符串，設最短長度為m。

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

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

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

定義5：模式串摘要。由單向Hash函數對模式串進行作用而產生的固定長度的值。

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

雖然W-M算法具有字符跳躍距離大的優點，但也存在很多缺點[9]。

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

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

圖2　改進的W-M模式匹配算法操作示意圖

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

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

3.2基于多模匹配算法的關鍵詞并行搜索架構

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

3.2.1關鍵詞集合的預處理

為實現基于多模式匹配算法的關鍵詞并行搜索，需要對所有關鍵詞串進行預處理并建立五個初始化表，參見表1。

表1　五個初始化表的作用

3.2.2并行搜索架構

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

7) 查找SHIFT表獲取最大移動距離，判斷是否到達T的最后一個字符，是，則停止搜索，退出；否，則將T移動相應距離進入匹配窗口，轉1)。

并行搜索架構參見圖4。

4驗證與分析

通過設計一個仿真系統，驗證了該搜索架構的正確性，達到了比較好的效果。尤其是采用文獻[10]提出的硬件實現方法后，搜索速度非常高。

圖4　基于多模匹配的關鍵詞并行搜索架構

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

關于空間復雜度：相比較原算法，增加了SUFF表，該表的空間大小取決于b的長度，在不優化的前提下，占用空間為2b，可見該架構占用了較大的空間資源。但是在當前存儲器資源越來越便宜的情況下，還是可取的。

關于哈希表的構造：不難看出，FLAG表和SUFF表都是稀疏表，可以采用相關的優化存儲方法來實現它們，從而降低對空間的占用。

5結語

基于模式匹配技術，論文提出了一種的多關鍵字并行搜索方法和架構，并把它應用于軟件靜態測試過程的關鍵詞搜索與匹配檢查過程，取得了較好的效果。目前國內關于軟件測試實現方法研究的文獻很少，希望本文的工作對相關的研究有一定的啟發作用，論文提出的方法也可以廣泛應用于信息檢索。

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

[1] 歐嵬,吳純青.幾種字符串匹配算法的分析和比較[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] 袁榮亮.基于入侵檢測系統的多模匹配算法的研究[D].西安：西安科技大學,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].計算機應用與軟件,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] 熊宇.一種安全規則可配置的網絡防護專用電路的設計與實現[D].武漢：武漢大學,2015.

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

一.總要求

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

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

示例1:

[1] 焦李成,杜海峰,等．免疫優化計算、學習與識別[M].北京:科學出版社,2006．

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

[2] 李詩靈,陳寧,趙學彧．基于粒子群算法的城市軌道交通接運公交規劃[J]．武漢理工大學學報(交通工程與科學版)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．

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

◆普通圖書(原著):

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

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

[4]中國社會科學院語言研究所詞典編輯室．現代漢語詞典[M]．修訂本．北京:商務印書館,1996:258-260．

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

◆普通圖書(譯著):

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

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

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

◆期刊(有卷)

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

[8]蔣超,張沛,張永軍,等．基于SRLG不相關的共享通路保護算法[J]．光通信技術,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．

◆期刊(無卷)

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

[10]周可,馮丹,王芳,等．網絡磁盤陣列流水調度研究[J]．計算機學報,2005(3):319-325．

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

三.電子文獻的著錄格式

◆電子文獻:

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

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

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

四.學位論文與論文集的著錄格式

◆學位論文:

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

[13]孫玉文．漢語變調構詞研究[D]．北京:北京大學文學院,2000．

◆論文集:

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

[14]白書龍．植物開花研究[C]//李承森．植物科學進展．北京:高等教育出版社,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日

作者簡介:熊宇,女,碩士,助理工程師,研究方向：軟件測試。

中圖分類號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