Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (14): 66-68.DOI: 10.3778/j.issn.1002-8331.2010.14.019

• 研发、设计、测试 • Previous Articles     Next Articles

Path scheduling algorithm with high code coverage based on symbolic execution

LI Chao-jun,JIANG Fan   

  1. Department of Computer Science and Technology,University of Science and Technology of China,Hefei 230027,China
  • Received:2009-03-05 Revised:2009-06-01 Online:2010-05-11 Published:2010-05-11
  • Contact: LI Chao-jun

符号执行中高语句覆盖率的路径调度

李朝君,蒋 凡   

  1. 中国科学技术大学 计算机科学技术系,合肥 230027
  • 通讯作者: 李朝君

Abstract: Symbol execution and constraint solving with path scheduling algorithm based on Depth First Searching(DFS),which is used in common,is prone to path clustering problem.In practice,the problem of path exploding,which makes it impossible to test all the paths,always exits in software.Path clustering,path exploding and finite test time cause a low level of code coverage.A new path scheduling algorithm called PSHC(Path Scheduling Algorithm with High Code Coverage) is introduced.In this algorithm,a path composes of two parts,prefix and postfix.Test is trying to execute on the path that has the shortest prefix,which has the same nodes with the paths that have been executed,and is doing the best to including the nodes not executed ever in the postfix.The experiments with PBFT(Phoenix-oriented Bug Finding Tool) imply that the PSHC algorithm can increase quickly the code coverage rate to 100% and solve the low coverage of code problem caused by path clustering which is the result of using the path scheduling algorithm oriented on DFS.The amount of paths created by PSHC don’t relate to the depth of loops.The larger the software is,the better the PSHC’s outstanding is.

Key words: symbolic execution, path scheduling, constraints solving, software testing

摘要: 符号执行和约束求解相结合的软件测试方法采用深度优先搜索的路径调度算法会造成测试路径聚居性问题,实际软件中存在路径爆炸,使得采用该算法的测试语句覆盖率低下。提出一种新的PSHC路径调度算法。先将路径分为前缀和后缀两部分,每次测试总是试图寻找这样的路径,该路径与已存在的路径具有最短的相同前缀,并且包含尽可能多的尚未被访问过的基本块作为其后缀。基于Phoenix漏洞发掘工具的实验结果表明,PSHC算法可以迅速提高测试的语句覆盖率到100%,有效解决由于深度优先搜索的路径聚居性导致的测试代码的局部性问题,PSHC算法产生的路径数与循环深度无关,软件规模越大,该算法的表现越好。

关键词: 符号执行, 路径调度, 约束求解, 软件测试

CLC Number: