应用过程间分析技术的并行错误模式匹配方法
郑炜, 蔺军, 黄月明, 冯晨, 吴潇雪     
西北工业大学 软件与微电子学院, 陕西 西安 710072
摘要: 过程间分析技术通常用于静态检测并行程序中的错误模式实例,目前已成为静态测试、错误模式匹配等领域的研究热点。然而,现存的过程内分析技术对于并行错误的静态测试效果尚不够理想。为此,文章试图运用过程间分析技术对并行程序进行"错误模式"的匹配。通过遍历构建的全局控制流图,分析图中单个节点所包含的语句,对其中可能出现错误的程序进行了错误模式的匹配,最终得出"错误定位"的结果。通过在实际开源系统中的应用,结果表明文中所提出的方法效果良好,具有较好的错误定位能力。
关键词: 并行程序     静态测试     过程间分析     错误模式     错误检测    

近年来,由于多核技术的迅速发展,使得主流软件系统的构建模式已由单线程串行方式转换为多线程的并行方式[1]。然而,在并行处理方式得到广泛应用的同时,也出现了很多并行错误,导致并行处理效率的下降,极端情况下可能会使并行处理速率远远低于串行方式处理速率,结果反而得不偿失。由于并行程序线程交互时序的不确定性,使得检测并行程序中的错误比检测串行程序错误困难得多[2]。如果放任这些错误,可能导致威胁到软件的安全,有可能造成严重的财产或安全损失。因此,需要保证软件的质量,有效地控制软件开发和软件维护费用,对软件中可能的错误进行全面、系统、充分的检测。

目前,在并行程序测试领域,已有很多成果出现,例如Microsoft公司开发了一款叫做Microsoft CHESS[3]的并行错误检测工具,可用于检测Windows和.NET程序。Gao和Zhang等[4]分别提出了针对一般顺序违背的错误检测工具 2ndStriker和ConMen,它们涉及了文件操作、指针操作、变量初始化检查等顺序。对于死锁的错误检测,中国科技大学的黄理提出了一种基于Pertri网的多线程死锁检测方法[5]

不过,以上这些方法都需要大量的人工参与,或者局限于某种具体的错误类型。错误模式是程序中已发生的bug和潜在bug之间重复出现的相互关系[6]。使用错误模式作为检测的依据,可以扩展并行检测方法的通用性,开发者可以很快识别新发生的bug,还可以预防某些bug的发生。虽然错误模式最终也许不会导致错误的出现,但对于开发者而言,还是建议避免错误模式的产生。即使是经验丰富的开发者也会在开发过程中引入错误模式 [7]。CBP(concurrency bug pattern)是错误模式中的一类[8],它应用于并行程序的检测过程中。

本文试图引入错误模式理论来解决并行程序错误定位的问题,通过使用FindBugs[9]作为用户的接口,运用过程间分析技术[10]对并行Java程序中函数之间的调用关系以及变量之间的影响进行分析,最后使用CBP与程序中可能会出现错误的代码进行匹配以期得出错误定位的结果。

1 基于过程间分析的并行错误模式匹配 1.1 错误模式理论基础

错误模式与正则表达式相似,且它的适用范围更广,可以针对各种类型的数据结构,而正则表达式中的模式只针对字符串[11]。如正则表达式里“^A.*” 这个pattern 表示以A开头、后续一个或多个字符组成的字符串。狭义上看,模式可以当作某个类型的内部数据在结构上抽象出来的表达式。而模式匹配则是检验出某个变量是否符合这种pattern。错误模式和语言本身相关联,不同的语言有着不同的错误模式 [12],如以Java语言为背景,则可以将其分为4个层次,即故障模式、漏洞模式、缺陷模式和规则模式[13]

1.2 基于错误模式的测试指标

P是待测程序,将缺陷模式M分成类M={M1,M2,…,Mn},每类分成Mi={Mi1,Mi2,…,MiL},从P中计算和M相匹配的检查点的集合I={I1,I2,…,Im},可以定义如下技术指标。

定义1 (漏报率Er) 漏报率是指未检测出来的匹配点个数与程序中全部匹配点个数的比例[14],即

(1)

式中,P是程序,M是缺陷模式,A是算法,I(M,P)是程序P中包含的与M相匹配的检查点的数目,I(M,A,P)是采用A算法时从P中计算出来的与M相匹配的检查点数目。

定义2 (准确率Cr) 准确率是指已正确匹配的点的个数与匹配结果不确定的点的个数之和与程序中包含的总匹配点数目的比例[14],即

(2)

式中,IY(M,A,P)是指当利用A算法时,已正确匹配的检查点个数;是指利用A算法时进行匹配得出的不确定检查点个数。

定义3 (误报率Dr) 误报率是指已检测出来的匹配点中,被错误匹配的点的个数与程序中所包含的匹配点数目的比例[14],即

(3)

式中,IN(M,A,P)是指采用算法A被错误匹配的点的个数。

定义4 (缺陷检测率Ddr) 缺陷检测率是指利用A算法正确匹配的点的个数与程序中包含的匹配点数目的比例[14],即

(4)
1.3 并行错误模式的匹配实现

静态分析技术可以根据对过程的注重程度分为过程内分析和过程间分析。过程内分析只注重分析单个过程,而过程间分析则针对多个过程[15]。显然,后者的精确度较高。由于FindBugs采用过程内分析技术,忽略了函数的上下文环境以及变量之间的影响,所以本文只将FindBugs作为用户的接口,而使用更为精确的过程间分析技术,对可能存在缺陷模式的源程序进行错误定位。具体的分析步骤为:首先创建程序的全局控制流图[16],分析函数之间的调用关系。之后对单个函数进行过程内分析,检测函数内语句。最后模拟程序的执行路径,将已存在的错误模式与源代码进行匹配,得出错误定位结果。上述处理流程如图 1所示:

图 1 错误模式匹配流程图
2 常见的并行错误模式以及检测方法 2.1 同步可重用的对象

一类常见的并行错误模式称为“同步可重用的对象”[17]。在Java中,并行程序同步具有2种方式:①synchronized方法;②使用同步代码块。由于同步代码块更为灵活,所以本文只针对同步代码块方式。对于同步对象的选择,也有一定规范。其中之一是不能使用可重用对象进行同步,例如integer、string和boolean类型。假定现在存在2个线程A、B。在线程A中将某一封装类的对象作为同步代码块的对象进行同步,在另一线程B中也使用了同一类型且值相同的对象作为同步对象,此时即使2个对象的名称不一样,但是因为它们的值相同,这就使得2个对象在内存中的位置是一致的,对其中任何一个对象进行操作都会作用到另一个对象,最终会导致对象的重用。此时如果线程A发生了死锁,也可能会导致线程B陷入死锁状态。图 2是此类错误模式的实例:

图 2 同步可重用对象

又如使用new函数创建对象,每次得到的结果都不一样。那么即使对象的名称一致,实际上对象在内存中的位置也是不同的。所以,当程序中出现此类错误模式的实例时,通常可以使用new函数构造对象的方法进行解决,这样对象重用的情况就不会再出现,图 3为解决此问题的具体描述。

图 3 同步不可重用对象
2.2 同步固有的锁对象

另一类常见的并行错误模式称为“同步固有的锁对象”[17]。在Java中,存在固有的锁类型ReentrantLock,它自身具有lock()和unlock()方法,通过这2种方法,可以实现同步。如果将此类型的对象作为同步对象,则容易产生双重锁的情况,最终有可能导致程序出错。图 4是此类错误模式的一个实例:

图 4 同步固有的锁对象

由于ReentrantLock自身可以实现同步,所以直接使用lock()和unlock()方法,采用图 5所示的方式可解决此类同步问题。

图 5 使用锁对象同步
2.3 错误模式检测方法

在对实际程序检测之前,需要构建源程序所对应的控制流图。控制流图是对源代码的结构化表示,图中的节点表示源程序的一条或多条语句,节点之间的边表示语句之间的执行路径。通常一个控制流图有且只有一个起始和终止节点。起始节点的入度为零,终止节点的出度为零。而在这二者之间的节点可以分为顺序节点和分支节点。图 5展示了程序中可能出现的3种基本结构,各种节点的表现形式也在其中体现。

图 6 基本程序结构图

大多数程序都是由这3种结构构成,因此可以将源程序转换为控制流图进行表达。图 7是一个转换实例。

图 7 源代码控制流图

控制流图构成之后就可以进行遍历,首先遍历图上的每一个节点,之后再遍历节点包含的每一条函数语句,判断语句是否符合同步代码块的书写方式,最后对于符合条件的语句进行错误模式匹配,由此可得出错误实例的具体位置,图 8是实现流程的伪代码描述:

图 8 错误模式匹配伪代码
3 实验验证

通过在Apache Tomcat和Apache Commons Pool这2个开源程序中进行实际的应用,验证了本文所提出的并行错误模式匹配方法的有效性。

3.1 在Apache Tomcat中的应用

FastHttpDateFormat中检测到使用封装类long的对象作为同步代码块的对象。这符合上面所提到的错误模式,因此可以得出检测结果,如图 9所示。

图 9 Tomcat存在的错误模式实例

在此类中,所发现的并行错误实例数量为1。其中Ir(M,A,P)=1,Iu(M,A,P)=0,I(M,A,P)=1,IN(M,A,P)=0。由于通常I(M,P)未知,一般不使用Er作为衡量指标。于是,Cr=1,Dr=0,Ddr=1。

在ParallelNioSender类中,检测到2个错误模式实例,如图 10图 11所示:

图 10 Tomcat存在的错误模式实例
图 11 Tomcat存在的错误模式实例

在此类中,所发现的并行错误实例数量为2。其中第二个错误实例为误报结果,所以IY(M,A,P)=1,Iu(M,A,P)=0,I(M,A,P)=2,IN(M,A,P)=1。于是,可得结果Cr=0.5,Dr=0.5,Ddr=0.5。

3.2 在Apache Commons Pool中的应用

在StackObjectPool类中检测到使用封装类Boolean的对象作为同步的对象。得到的检测结果如图 12所示:

图 12 Commons Pool存在的错误模式

在此类中所发现的并行错误实例数量为1。其中IY(M,A,P)=1,Iu(M,A,P)=0,I(M,A,P)=1,IN(M,A,P)=0。可得测试指标Cr=1,Dr=0,Ddr=1。

综上所述,运用过程间分析技术进行错误模式匹配的误报率较低,缺陷检测率较高。并且能够检测到一些使用过程内分析技术无法检测的错误模式实例。因此,应用过程间分析技术的并行错误模式匹配方法对于错误定位的效果较为理想。

4 结论

本文针对现存的过程内分析技术在错误定位时的不足,采用了误报率较低的过程间分析技术对Java并行程序进行了错误定位,并在此基础上利用错误模式匹配方法得出检测结果。通过在实际项目中的应用,表明该技术得到的测试结果较为理想、且误报率较低。但是也存在一定的缺陷如检测过程未完全自动化、所包含的错误模式的数量有限。在未来的工作中,对于上述的缺陷还值得深入研究。

1) 增加错误模式数量:由于现阶段该技术所包含的错误模式的数量有限,因此得到的错误实例的数量也会很少,这使得该技术的应用范围尚不够令人满意。在下一阶段,将考虑添加新的错误模式。

2) 检测过程自动化:现阶段对于错误实例的检测还需要手动调试,检测过程耗费了较多时间。使得该技术的效率不是很高。未来将考虑实现检测过程的完全自动化。

参考文献
[1] Andrews G R. Concurrent Programming:Principles and Practice[M]. Boston, MA,USA: Addison Wesley Press, 1991: 425-451.
[2] Dai Zhuofang, Zhang Weihua. Concurrency Program Fault Debugging Technology Research Review[J]. Computer System Application, 2014(10): 5–6.
[3] Ball Thomas, Burckhardt Sebastian, de Halleux Peli, et al. Predictable and Progressive Testing of Multithreaded Code[J]. IEEE Trans on Software, 2011, 28(3): 75–83. DOI:10.1109/MS.2010.64
[4] Gao Q, Zhang W, Chen Z, et al. Toward Manifesting Hidden Concurrency Typestate Bugs[J]. ACM Sigplan Notices, 2012, 47(4): 239–250. DOI:10.1145/2248487
[5] 黄理, 顾乃杰, 曹华雄, 等. 基于Petri网的多线程程序死锁检测[J]. 计算机工程, 2016, 42 (4): 1–6.
Huang Li, Gu Naijie, Cao Huaxiong, et al. The Deadlock Detection of Multithreaded Program Based on Petri Net[J]. Computer Engineering, 2016, 42(4): 1–6. (in Chinese)
[6] Hong S, Kim M. Effective Pattern-Driven Concurrency Bug Detection for Operating Systems[J]. The Journal of Systems and Software, 2013, 86(2): 377–388. DOI:10.1016/j.jss.2012.08.063
[7] Kai Pan, Sunghun Kim E. James Whitehead Jr, et al. Toward an Understanding of Bug Fix Patterns[J]. Empirical software engineering, 2009, 14(3): 257–261. DOI:10.1007/s10664-009-9110-3
[8] Hovemeyer D, Pugh W. Finding Concurrency Bugs in Java[C]//Proceedings of the Podc Workshop on Concurrency & Synchronization in Java Programs, 2004:1-2
[9] Shen Haihao, Fang Jianhong, Zhao Jianjun, et al. EFindBugs:Effective Error Ranking for FindBugs[C]//2011 Fourth IEEE International Conference on Software Testing, Verification and Validation, 2011:299-308
[10] Bertrand Jeannet. Relational Interprocedural Verification of Concurrent Programs[J]. Software and Systems Modeling, 2013, 12(2): 285–306. DOI:10.1007/s10270-012-0230-7
[11] 张树壮, 吴志刚, 罗浩, 等. 一种高效的正则表达式匹配方法[J]. 高技术通讯, 2014, 24 (6): 551–557.
Zhang Shuzhuang, Wu Zhigang, Luo Hao, et al. An Efficient Approach of Regular Expression Matching[J]. High Technology Letters, 2014, 24(6): 551–557. (in Chinese)
[12] 魏雪菲, 吴健, 阮园, 等. 基于错误模式和模型检验的静态代码分析方法[J]. 计算机工程, 2012, 38 (6): 47–49.
Wei Xuefei, Wu Jian, Ruan Yuan, et al. Static Code Analysis Method Based on Bug Pattern and Model Verification[J]. Computer Engineering, 2012, 38(6): 47–49. (in Chinese)
[13]
[14] 王雅文. 基于缺陷模式的软件测试技术研究[D]. 北京:北京邮电大学,2009
Wang Yawen. Software Testing Technology Research Based on Bug Pattern[D]. Beijing, Beijing University of Posts and Telecommunications, 2009(in Chinese)
[15] 章磊.Clang上的C/C++过程间分析[D]. 合肥:中国科学技术大学,2009
Zhang Lei. C/C++ Interprocedural Analysis in Clang[D]. Hefei, University of Science and Technology of China, 2009(in Chinese)
[16] Carlos Gómez-Rodróguez. Finding the Smallest Binarization of a CFG is NP-Hard[J]. Journal of Computer and System Sciences, 2014, 80(4): 796–805. DOI:10.1016/j.jcss.2013.12.003
[17] Long F, Mohindra D, Seacord R, Svoboda D. Java Concurrency Guidelines[Z]. Pittsburgh, PA, USA:Software Engineering Institinte, 2010
Concurrency Bug Pattern Matching Based on Interprocedural Analysis Technology
Zheng Wei, Lin Jun, Huang Yueming, Feng Chen, Wu Xiaoxue     
School of Software and Microelectronics, Northwestern Polytechnical University, Xi'an 710072, China
Abstract: Interprocedural analysis technology, as statically detecting bug pattern instances in concurrency programs, becomes the hot topic of static testing, bug pattern matching and other areas. At present, the intraprocedural analysis technology doesn't have a desired effect in detecting concurrency bugs. Focused on this problem,this paper matched the concurrency program with bug patterns by using interprocedural analysis technology. Firstly, built the overall control flow graph and analyzed the statements that each node contained, then matched the problem program with the bug patterns. At last, received the fault localization results. According to the testing results in the actual open source systems, this method has a good ability to locate software faults.
Key words: concurrency program     static testing     interprocedural analysis     bug pattern     failure modes    
fault detection    
西北工业大学主办。
0

文章信息

郑炜, 蔺军, 黄月明, 冯晨, 吴潇雪
Zheng Wei, Lin Jun, Huang Yueming, Feng Chen, Wu Xiaoxue
应用过程间分析技术的并行错误模式匹配方法
Concurrency Bug Pattern Matching Based on Interprocedural Analysis Technology
西北工业大学学报, 2017, 35(1): 148-153.
Journal of Northwestern Polytechnical University, 2017, 35(1): 148-153.

文章历史

收稿日期: 2016-10-08

相关文章

工作空间