一种用于软件静态测试的关键字并行搜索方法*

熊　宇

(武汉数字工程研究所　武汉　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