基于函数调用序列模式和函数调用图的程序缺陷检测方法*

崔展齐

(北京信息科技大学 计算机学院，北京 100101)

程序中通常会隐含大量编程规则，由于受到开发时间和进度的限制，且此类规则数量众多，软件工程师很少使用规范的文档来描述这些规则.部分编程规则隐藏较深，软件工程师甚至并未意识到其存在，采用传统的代码评审方法不能发现违反此类规则的缺陷.若程序员在编程过程中忽视或违反这些规则，则有可能会引发软件缺陷.软件缺陷挖掘是自动识别程序隐含规则的有效手段，其通过分析软件代码、文档等相关数据，以识别隐含的缺陷模式或编程规则，并据此来自动发现软件缺陷[1].软件缺陷挖掘能有效检测程序缺陷，且能在很大程度上实现自动化，人力成本开销较小[2-6].我们在此前的工作中，在一组开源项目上进行了实验，结果表明通过函数调用序列模式挖掘能有效发现程序中的相关缺陷，并降低误报的疑似缺陷数[7].

然而，现有技术方案仍存在误报率较高，待检测疑似缺陷数量较大的问题.通常情况下，使用数据挖掘技术识别出的隐式编程规则数量比较多，导致所检测出的违反隐式编程规则的疑似缺陷数量更大.对疑似缺陷进行确认通常需要工程师在理解相关代码片段的基础上，根据自身经验和专业能力进行判断，极有可能引入误判，且难以自动化.人工确认疑似缺陷过程枯燥且需要耗费大量时间和精力.例如，在我们此前的工作中，仅对内存数据库Redis的源程序进行挖掘，就发现了8条函数调用序列模式和16个疑似缺陷.然而，经人工确认之后，其中仅有1个是确认的缺陷.

通过分析发现，在之前的工作中，只使用了函数内部的路径，缺少函数调用关系的全局信息，导致产生大量误报疑似缺陷.例如，根据挖掘Redis源程序发现的序列模式，检测到hashTypeInitIterator()方法中只调用了dictGetIterator()方法，未调用dictReleaseIterator()方法，因此将其作为一个疑似缺陷报告.我们对源程序进行分析发现，hashTypeInitIterator()仅在hashTypeConvertZiplist()和genericHgetallCommand()两个方法中被调用，每次调用之后都会调用hashTypeReleaseIterator()方法，而在hashTypeReleaseIterator()方法中即调用了dictReleaseIterator().因此，上述疑似缺陷为误报，误报产生的原因是未能有效利用函数调用关系全局信息.

1 基于函数调用序列模式和函数调用图的缺陷检测方法

针对上述问题，本文提出了一种基于函数调用序列模式和函数调用图的缺陷检测方法.首先，通过文献[7]提出的方法，挖掘过程内函数调用序列集，获取程序中隐含的函数调用序列模式；然后，通过分析待检测程序，生成过程间函数调用图；最后，结合函数调用序列模式和函数调用图，检测程序中违反序列模式的疑似缺陷.方法框架如图1所示.

1.1 函数调用序列模式挖掘

函数定义体中一般会包含多处函数调用语句，在PR-Miner[3]等方法中，通常将一个函数内的函数调用语句作为一个事务，在程序所有函数定义所组成的事务集上使用频繁项集挖掘算法[8-10]进行挖掘，以找出函数调用关联规则，再用于检测违反关联规则的疑似缺陷.这类方法在挖掘过程中忽视了程序中函数调用的先后顺序信息，导致缺陷检测的精度降低.

针对这一问题，我们在文献[7]中提出了基于函数调用序列模式挖掘的缺陷检测方法.序列模式挖掘是一种常用的数据挖掘方法[11]，文献[7]中采用了GSP算法[12].该方法的详细过程，在此不再赘述，仅给出几个后续步骤要使用的概念.

在函数调用序列模式挖掘中，待检测程序中每条程序调用语句即为项，若干项组成的集合为项集，序列则是若干项集组成的有序列表.序列的长度指序列中包含项集的个数，长度为K的序列记为K-序列.如果序列t中每个项集都是序列s中一个项集的子集，则称t是s的子序列，或称s包含t.一个序列s的支持度计数(supCount)是指在整个序列数据集中包含s的序列个数，给定一个最小支持度阈值minSupCount，如果序列s的支持度计数不小于minSupCount，则称序列s为序列数据集中的频繁序列或序列模式.不采用支持度低于minSupCount的序列模式，即不关注在函数调用序列集中出现次数过少的序列模式.此外，GSP算法中还增加了最小/最大时间约束(minGap/maxGap)，两个事件的间隔不大于maxGap且不小于minGap，才被认为在同一个序列中.在函数调用序列模式挖掘中，当两个函数调用语句间隔较远时，其存在调用模式的可能性也较低.

挖掘函数调用序列模式，即根据minSupCount和maxGap对函数调用序列模式进行筛选，找出所有序列模式集合FS的过程.

1.2 函数调用图

分析上述函数调用序列模式挖掘过程发现，每一条函数调用序列均来自于一个函数定义内部.因此，只使用了过程内函数调用信息，缺少过程间函数调用的上下文信息.

为保存函数间相互调用的逻辑关系，本文使用了过程间函数调用图.将过程间函数调用图定义如下：

定义1过程间函数调用图(inter-procedural function call graph，IFCG)是一个2元组(N,E)，其中：N={n1,n2, …,ni}，是一个有穷的节点集合，其中n∈N是一个函数定义；E={e1,e2, …,ej}，是一个有穷的有向边集合，(nl,nm)⊂(N×N)表示函数nl中对函数nm进行了调用.

算法1生成过程间函数调用图

1 输入: 程序P={fd1,fd2, …,fdn}

2 输出: 过程间函数调用图(IFCG)

3 方法: GenerateIFCG(P,IFCG)

4 forfdiinP//遍历P中的所有函数定义fdi

5ni=new node(fdi,FCi)//为fdi建立一个节点

6 IFCG.N.Push(ni)//将创建节点加入N

7 forniin IFCG.N//遍历N所有节点

8 forfcjinni.FC//遍历所有函数调用语句

9 获取fcj的函数定义对应的结点nj

10 if edge(ni,nj) not inE//E中没有对应边

11eij=new edge(ni,nj)//建立一条边

12 IFCG.E.Push(eij)

13 return IFCG

Caller和Callee分别是获取指定节点的调用函数和被调用函数的两个函数，对每个元素n∈N，Caller(n)={nk|nk∈N∧(nk,n)∈E}，Callee(n)={nk|nk∈N∧(n,nk)∈E}.

算法1为过程间函数调用图的生成过程.算法输入程序P由n个函数定义组成，表示为集合P={fd1,fd2, …,fdn}，其中，一个函数定义fdi中包含的函数调用所组成的序列为FCi=.算法输出为程序的过程间函数调用图(IFCG)=(N,E)，N为节点集合，节点ni=(fdi,FCi)，E为边集合，边eij=(ni,nj).算法首先遍历P中的所有函数定义fdi，为每个函数定义建立一个节点ni，并将其加入N；然后遍历N中所有节点ni，再嵌套遍历ni.FCi中包含的调用语句序列，对于FCi中的每个fcj，获取fcj的函数定义对应的结点nj，检查是否存在从ni指向nj的一条边，若不存在，则建立一条边eij，并将其加入E.

1.3 缺陷检测

在生成序列模式集合FS和函数调用图后，需要对源程序进行分析，以检测疑似缺陷，即程序中函数调用方式违反函数调用序列模式的位置.对长度为k的函数调用序列模式α=，支持计数supCount(α)为FS中包含α的所有序列的计数.这种计算方式只考虑了在一个函数体内部的函数调用语句.为利用函数调用图中的上下文关系信息，将支持计数计算扩展为supCount(α,d)，其中，d表示函数调用序列向上和向下扩展的层数，supCount(α,d)为将FS中的序列扩展d层之后，包含α的所有序列的计数.α的最大前缀为长度为k-1的序列β=，若函数定义fdi对应的函数调用序列FCi在扩展d层后，包含β，但不包含α，则称fdi存在违反序列模式α的函数定义，怀疑度(suspicious)定义为：

通常情况下，可以认为程序员只是偶尔会犯错，程序中大多数函数调用顺序是正确的，因此，只将怀疑度超过最小怀疑度(minSus)的缺陷作为疑似缺陷报告.

为检测疑似缺陷，可对源程序P进行扫描，逐条检查是否存在违反集合FS中序列模式的函数定义.

算法2 疑似缺陷检测1234567891011121314151617181920输入：序列模式集合FS，过程间函数调用图IFCG，扩展层数d输出：疑似缺陷列表(bugList)方法：FindBugs(FS，IFCG，d)forfcsiinFS//遍历序列模式集合 βi=fcsi的最大前缀 forniinIFCG．N//遍历所有函数序列 if(ni．FCi包含βi) supCount＿βi++//βi支持度递增if(Contain(ni，fcsi，d)==true) supCount＿fcsi++//fcsi支持度递增else//加入疑似bug临时列表 tempbugList．add(fdi) //若怀疑度大于最小怀疑度 if(minSus

算法3 基于函数调用图的函数调用序列匹配检测12345678910输入：初始节点n，函数调用序列fcs，扩展层数d输出：是否包含函数调用序列方法：Contain(n，fcs，d)N=upTraverse({n}，d)N=downTraverse(N，d)foreachninN if(n．FC包含fcs) returnfalsereturntrue11121314151617181920212223242526272829方法：upTraverse(N，d)//向上扩展N’=NforeachninNi=dwhile(i--大于0)N’．remove(n)foreachniinCaller(n)将ni中调用n后的子序列拼接到n．FC后N’．add(n．FC)N’=upTraverse(N’，i)returnN’方法：downTraverse(N，d)//向下扩展while(i--大于0)foreachninNfornjinn．FCtempFC=nullfornkinCallee(nj)tempFC．append(nk．FCk)将nj替换为tempFCreturnN

算法2为疑似缺陷检测过程.算法输入为序列模式集合FS, 过程间函数调用图为IFCG，扩展层数为d，算法的输出疑似缺陷列表为bugList.第6～19行为对序列模式集合FS逐条遍历.首先，获取序列模式fcsi的前缀βi，并在第8～14行中使用过程间函数调用图对程序进行遍历，将检测到违反序列模式的疑似缺陷加入临时缺陷列表中.然后在遍历完整个程序后，将计算出的序列模式fcsi怀疑度与最小怀疑度(minSus)进行比较，若大于(minSus)且小于1，则将临时缺陷列表加入缺陷列表中.最后在完成程序扫描后，第20行返回疑似缺陷列表.

算法2中使用到的函数调用序列匹配方法在算法3中描述.第4～10行定义Contain方法，该方法通过upTraverse方法将函数调用序列逐层向上扩展，再通过downTraverse方法将函数调用序列逐层向下扩展，然后将扩展后的函数调用序列与序列模式fcs进行比较，并返回比较结果.向上扩展时，由于函数可能会在多处被调用，所以可能会扩展为多个函数调用序列，其中任意一个函数调用序列不包含指定序列则都将会返回false.

2 实验与结果

在上述基于程序调用序列模式和函数调用图的缺陷检测方法的基础上，我们实现了一项原型工具，并进行了一组实验以验证所提出方法的有效性.实验平台为Intel i7 2.3 GHz处理器、8 GB内存计算机，软件环境为Ubuntu16.04、Python3.4.

2.1 实验设计

为合理评估所提出方法的有效性，便于与已有方法进行对比，我们使用了文献[7]的3个开源项目实验对象，即内存数据库Redis，跨平台脚本语言Lua和嵌入式系统数据库Sqlite.实验对象基本情况如表1所示.在实验中，函数调用序列模式挖掘算法使用的参数为：最小支持度0.01，最大时间间隔10.使用函数调用图进行缺陷检测时，所使用最小怀疑度为0.9，扩展层数为1.

在实验中，生成的函数调用序列经预处理后使用数据挖掘工具Rapidminer 7.2.1进行序列模式挖掘，再根据挖掘出的函数序列模式和生成的全局函数调用图扫描程序，识别出违反函数调用序列模式的位置，作为疑似缺陷报告.

表1 实验对象基本情况[7]

表2 时间开销统计

2.2 实验结果分析

表3 疑似缺陷报告及确认情况

表2对两种方法检测疑似缺陷的运行时间开销进行了比较.其中，进行序列模式挖掘和人工验证的时间没有统计在内.从结果可以看出，本文所提出方法所需的运行时间大于文献[7]的方法，3个实验对象累计耗时1 750.5 ms，比文献[7]方法累计耗时759.0 ms增加了1.3倍.但是，疑似缺陷检测是完全自动化的，并不会增加额外的人力成本开销，而缺陷自动检测技术的关键在于尽可能降低人工确认疑似缺陷的开销.

为验证基于函数调用序列模式和函数调用图的缺陷检测方法减少误报和发现缺陷的能力.表3将两种方法的缺陷检测及确认情况进行了统计.我们将缺陷检测结果分为：疑似缺陷数、确认缺陷数和确认为误报的缺陷数3类.从表3中可以看出，本文所提出方法所报告的疑似缺陷数明显减少，有效减少了缺陷误报，共报告了10个疑似缺陷，与文献[7]方法报告的26个疑似缺陷相比，减少了61.5%.同时，两种方法都检测到了同样的确认缺陷.上述实验结果表明，本文所提出方法报告疑似缺陷数明显减少，且能与文献[7]中的方法发现同样多的真实缺陷.因此，该方法将能有效降低疑似缺陷的人工确认开销.

3 结 论

针对现有的基于函数调用序列模式挖掘的缺陷检测方法所检测出的疑似缺陷数量较大，对疑似缺陷进行人工确认需要耗费大量时间和精力，且极有可能引入误判的问题，本文提出通过使用函数调用图，充分利用函数调用上下文信息，对疑似缺陷进行自动过滤.实验结果表明，在不影响缺陷检测率的前提下，该方法有效降低了需要人工确认的疑似缺陷数量.在本文研究的基础上，我们计划通过使用程序历史版本等更多信息和更加有针对性的程序编程规则挖掘算法，进一步提高缺陷检测精度.

参考文献

[1] 黎铭, 霍轩. 半监督软件缺陷挖掘研究综述[J]. 数据采集与处理, 2016, 31(01):56-64.

[2] LI Z, LU S, MYAGMAR S, et al. CP-Miner: a tool for finding copy-Paste and related bugs in operating system code[C]// The Proceedings of Conference on Symposium on Operating Systems Design and Implementation，2004: 289-302.

[3] LI Z, ZHOU Y. PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code[C]// The Proceedings of European Software Engineering Conference Held Jointly with, ACM Sigsoft International Symposium on Foundations of Software Engineering, 2005, Lisbon, Portugal, September，2005:306-315.

[4] LU S, PARK S, HU C, et al. MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs[C]// The Proceedings of ACM Symposium on Operating Systems Principles 2007,Stevenson, Washington, USA, October，2010: 103-116.

[5] XIE T, PEI J. MAPO: mining API usages from open source repositories[C]// The Proceedings of International Workshop on Mining Software Repositories, Shanghai, China, May，2006: 54-57.

[6] QU W, JIA Y, JIANG M. Pattern mining of cloned codes in software systems[J]. Information Sciences, 2014, 259(3): 544-554.

[7] 崔展齐, 牟永敏, 张志华,等. 基于函数调用序列模式挖掘的程序缺陷检测[J]. 计算机科学, 2017, 44(11): 226-231.

[8] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases[C]// The Proceedings of International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc，1994: 487-499.

[9] HAN J. Mining frequent patterns without candidate generation[J]. ACM Sigmod Record, 2000, 29(2): 1-12.

[10] 党红恩,赵尔平,刘炜,等.利用数据变换与并行运算的闭频繁项集挖掘方法[J].湘潭大学自然科学学报,2018,40(1):119-122.

[11] 潘力, 黄继海, 王磊. 基于分层有限状态机的时间序列数据挖掘与预测方法[J]. 湘潭大学自然科学学报, 2017,39(4): 18-21.

[12] SRIKANT R, AGRAWAL R. Mining sequential patterns: generalizations and performance improvements[C]// The Proceedings of International Conference on Extending Database Technology: Advances in Database Technology. Springer-Verlag, 1996: 1-17.