符号执行技术在测试用例生成中的应用

曾嘉彦

（四川大学计算机学院，成都 610225）

符号执行技术在测试用例生成中的应用

曾嘉彦

（四川大学计算机学院，成都 610225）

符号执行技术提出近四十年，随着计算机科学与技术的发展，在软件工程领域得到广泛的应用，成为一种流行的自动测试技术。对符号执行技术在测试用例生成中的应用展开综述，全方位地叙述符号执行技术的基本原理、面临的问题和挑战以及相应的改进策略、相关的典型案例，并介绍和比较现有的工具，对学术界和工业界提供相应的参考。

符号执行；Concolic测试；自动化测试；测试用例生成

1 符号执行技术基本原理

符号执行技术（Symbolic Execution）[1]由JC.King在1976年提出，将软件的测试问题转化为了符号表达式求解的数学问题。

很多家长担心孩子乱花钱，会“剥夺”孩子们掌控钱的机会。比如要买什么东西，统统向父母伸手要，孩子们得到了压岁钱，家长们也会说：“压岁钱由父母来帮你保管”，全数地将压岁钱收回去。这样做的弊端是，孩子们会因此养成要花钱就伸手，一有钱就赶快花光的习惯，而缺乏对消费的规划意识。

符号执行的核心思想是：采用抽象化符号代替程序中具体的输入，依次解析程序的语句和指令，在程序控制流图的基础上生成符号执行树，并为每一条路径建立一系列的以输入符号为变量的路径表达式，即路径条件。对路径表达式进行求解，得到符号变量的解的集合，即获得了对应程序路径的具体输入值。

使用具体的数值简化路径中的符号约束的方法被称为动态符号执行（Dynamic Symbolic Execution，DSE），也被称为Concolic测试（Concolic Testing）。

也许与王羲之喜鹅有关，华堂村的白鹅养殖历史悠久，远近闻名.华堂村的白鹅养殖一直是一家一户主要利用天然杂草、采用传统的放牧方式养殖，在本地集市上出售，收益很低.随着放牧地减少，现在几乎没有农户饲养了.

《琵琶记》①是中国传统戏剧的经典之作，被誉为“南戏之祖”，历来受到各代研究者的关注。《琵琶记》产生于宋元之交，颇具时代的烙印，因而受到褒贬不一的评价。

2 符号执行技术的挑战与改进

CREST：CREST[14]是一个针对执行路径过多的程序构建和实验的启发式动态符号执行测试工具，它能实现更快的测试速度。

2.1 路径爆炸问题

路径爆炸（Path Explosion）是动态符号执行的广泛应用最主要的障碍。路径爆炸是指程序的可执行路径的数量随着执行路径的长度增长而指数式增加。

（1）路径引导技术

对DSE搜索策略进行改善，可以有效地引导DSE实现高结构覆盖率，缓解路径爆炸。大部分现有的符号执行测试工具（EXE/CUTE/DART）基于深度优先搜索（DFS）和广度优先搜索（BFS），DFS和BFS以固定的搜索顺序遍历目标程序，通常会卡在程序的特定区域，导致测试覆盖率降低。

分代搜索（Generational search）[2]提出于2008年，从四个方面缓解路径爆炸：能够处理大型程序庞大的状态空间；产生最大数量的测试用例同时避免冗余；最大化代码覆盖率；使用弹性的策略处理分歧。Fuzzgrind和SAGE工具就使用了分代搜索。

①不同年龄医护工作者职业认同水平具有差异性。其中年龄＞50岁的医护工作者职业认同程度高于其他年龄医护工作者，≤30岁的医护工作者职业认同程度最低，随着年龄增加医护工作者职业认同程度提高。

（2）路径修剪技术

SAGE：SAGE[15]是由微软公司开发的商业测试软件，Win7系统在开发过程中的大约三分之一的缺陷是由SAGE通过文件模糊测试发现的。

几十年过去了，030与719早已成为孙宝国研究之路上的往事，因为在那之后，他又研制出了多种香料，毫不夸张地讲，我们现在吃到的许多食品，其香味都来自于孙宝国的研究成果。这么香的味道，是如何实现的呢？其奥秘就来自于孙宝国的“味料同源”——中国特色肉味香精制造新理念。

回归测试中，由于程序的修改，部分测试用例将会失效，需要生成新的测试用例以扩充测试集。2010年，Thummalapenta Suresh等人针对回归测试用例的自动生成提出了DyGen[11]，即通过挖掘程序执行时的动态踪迹记录生成测试用例。Zhihong Xu等人将Concolic测试方法和遗传算法用于测试套件增强中，并取得一定成效。

符号执行技术固有的并行性质和多核计算机的发展，促使并行化方法成为提高符号执行效率的重要手段。Staats Matt等人提出一种静态分区技术，它是基于初始实际执行路径前置条件集合对符号执行树进行划分的并行符号执行方法。CLOUD9[6]是运行在云计算平台上的并行符号执行自动测试系统，它在符号执行过程中动态划分并调度符号执行树，遇到新的分支就将它分配到空闲节点，从而维持负载均衡。由于符号执行树形态的未知性，静态划分和动态划分都易造成负载不均衡，降低并行效率。不过，动态划分能调整结点负载，但节点间频繁的负载切换会导致大量冗余通信开销。

（1）GUI测试

符号执行技术遇到的另一个问题是，无法直接对一些通用类库或本机代码进行分析，如字符串。Web程序和数据库应用程序中往往要频繁地进行字符串操作。Wassermann Gary等人在Web测试中通过有限状态机和约束解析算法对字符串建模解决字符串约束问题；Emmi等人则提出了一种新的约束求解器，它能够同时求解线性运算约束和字符串约束。

2.3 指针操作问题

一个符号化的指针变量表示引用一个取决于符号表达式值的地址，即符号化的指针变量依赖于一些不被信任的变量值，符号执行因而难以直接处理程序中的指针变量。最简单的解决方案就是将符号化的指针具体化，然而，将具体化容易因为实际执行路径不匹配约束求解器指定的路径从而产生分歧。对此，B.Elkarablieh和P.Godefroid提出了一种精确的解决方案[7]，即通过建立内存模型表示程序执行时任意符号化指针解引用的内存区域，主动注入新的约束并绑定符号地址用于处理符号化指针操作。

2.4 浮点数计算问题

现有约束求解器不处理浮点数运算的舍入误差问题，如Z3/STP/Yices/CVC3，因此符号执行技术遇到了处理浮点数运算的问题。开发支持浮点数运算的约束求解器易导致复杂的约束条件，加重路径爆炸。Godefroid Patrice等人在2010年提出了一种方法缓解浮点数运算难题，即通过一个小的前期静态分析和边际执行开销，从而避免了浮点约束收集和求解。Bagnara R等人提出一个新版本的FPSE工具，它通过使用精确的投影函数解决含浮点数计算的路径约束。

3 符号执行技术在测试用例生成中的应用案例

2.2 字符串处理问题

为了检测和反映患者的氧合动态情况，并且可以提前发现缺血性心脏病围术期存在的初期低氧血症状，利用血氧饱和度检测仪可以实现持续性的观测，并为以后的护理和治疗提供相关依据。血氧饱和度检测主要指在患者的指端甲床固定探头指套，以手指作为血红蛋白响应容器，检测组织床光传导的强度，来统计有关血氧饱和度的量。血氧饱和度的计数可以实时反应患者的呼吸情况以及动脉血氧的动态状况，为患有低氧血症的患者初期提供相关数据。本次研究选择本院在收容诊治的50名患有缺血性心脏病在围术期间血氧饱和度减少的患者作为本次研究的实验对象，对医学临床上的相关护理干预措施进行分析，现报告如下。

Ganov Svetoslav R.等人将符号执行的概念引入GUI测试，提出了一个新的名为Barad的基于符号执行的GUI测试框架，解决了传统GUI测试框架不能有效验证GUI程序测试类的共同弱点。

（2）Web测试

为了减少搜索空间同时保持覆盖率，启发式搜索（Heuristic search strategy）和随机策略（Random strategy）被引入用于分支的选择，KLEE工具就采用了随机策略。随机策略的优点是：具有很大的自由度；能有效避免饥饿。因而，交错随机策略与其他的搜索策略探索符号执行树能够提高整体的效率和覆盖率。通常，启发式搜索能获得比随机策略更好的效果，现已被广泛用于符号执行的改进中。Yu Dong等人提出了一个名为DYNASTY[3]的基于分支残留的启发式搜索策略生成方法，并支持重复路径的迅速检测。Li You等人通过探索长度为N的子路径频率分布，优先遍历程序中很少被遍历的部分。

2008年，Wassermann Gary等人将Concolic测试框架引入Web应用测试中，并针对PHP脚本语言的特性，提出了一个基于Concolic测试框架的自动化的测试生成算法并设法解决了三大挑战：一是通过有限状态机和约束解析算法对字符串建模以解决字符串约束问题；二是开发新的算法来检测字符串值以防止SQL注入攻击；三是通过在运行时收集数值的方法，在查询执行的地方构建一个可返回的时间片并且记录该时间片的约束。

（3）数据库应用程序测试

2007年，Emmi Michael等人提出了一个基于Concolic执行的算法[8]用于数据库程序的测试数据自动生成。该算法生成两种输入数据，一种是访问数据库的应用程序的输入数据，一种是相应的数据库记录，并系统地探索程序中包括依赖返回数据的所有执行路径。该算法不能基于现有数据库状态生成有效的输入。Kai Pan等人在2011年提出了一种不同于Emmi等人的方法[9]，能够在不生成新的数据库状态的前提下实现应用程序的高代码覆盖率。他们对现有数据库状态构造辅助查询，并执行这些查询，从而生成有效的程序输入值。

（4）嵌入式应用程序测试

Kim Yunho等人将动态符号执行技术用于嵌入式应用测试，并对此展开了一系列的研究。2011年，Kim Yunho等人为嵌入式C程序开发了一个可扩展的Concolic测试工具SCORE[10]。SCORE利用大量的分布式计算节点，实现线性加速，能够显著减少Concolic测试的时间开销，并实现了可扩展性。2012年，Kim Yunho等人使用CREST工具测试三星的Linux平台（SLP）的文件管理器，安防库和busybox LS。通过案例研究发现，手工的测试验证不够可靠，Concolic测试方法可以有效提高工业嵌入式应用程序的质量。

（5）回归测试中的用例生成

在学校的教学过程中，教师在教学前利用数字媒体技术引入一个话题来导出所需要教学的知识，能够有效地激发学生的好奇心，提升其学习兴趣，提升学生的情感，提高学生的专业核心能力，就能够高效地进行教学安排。

（3）并行符号执行

4 符号执行技术的测试用例生成工具

在本节中介绍了若干有代表性的符号执行工具，并对其影响进行初步的评估。

如表1所列测点偏移量对应关系，解析程序即按此进行数据包解析，同时生成一项测点信息的配置表存储在数据库中，便于之后作为某台盾构的特征信息查看。在生成测点信息配置表过程中，以各测点所属盾构机子系统分组，如此在后续对盾构机子系统部件进行分析时提供便利，如图3。

DART（Directed Automated Random Testing）: DART[12]结合了动态符号执行、随机测试、模型检测等技术，许多扩展和工具都由它衍生而来。

CUTE和jCUTE：jCUTE[13]是CUTE的Java版本，CUTE是DART的扩展，能够处理含指针操作的动态数据结构的多线程程序。

本节对符号执行技术在实践中面临的若干个问题和挑战进行分类探讨。

路径修剪（Path pruning）技术专注于避免冗余路径的探索。RWset分析技术[4]通过跟踪程序内存位置读取和写入，判断路径是否能够探索到新的程序行为，修剪那些与已经探索过的路径产生同样效果的执行状态。eXpress工具[5]将动态符号执行引入回归测试中并修剪那些在程序行为上没有差异的程序版本的路径，从而指导符号执行有效地生成回归测试用例。

BIM技术文档信息管理中，项目文档准备、项目模型准备、检索排序和数据关联是其管理结果实现的四个基本阶段。一般情况下下，当项目数据准备完成后，BIM系统会对数据进行必要的分析，并在确保文字信息频率矩阵形成的基础上，实现了错误信息的有效剔除，进而促进了文档信息预处理的完成。模型准备和分类是基于IFC的标准进行的，其在保证项目文档信息精度的同时，确保了关联系统下的模型建立和施工指导。

为了促进水产养殖行业的健康发展，生产出更多绿色无污染的产品，在实际工作中，养殖户要在自动化养殖的基础上，融入环保理念，减少药物的应用。此外，还可以研发和使用绿色环保型药物，减少水产养殖中水体污染问题的发生，保证水体质量。目前，我国已经在绿色环保型药物的研究上取得了一定的成绩，这将会进一步推动水产养殖行业健康发展[2]。

PEX.：PEX[16]是基于动态符号执行的.NET自动测试工具。PEX采用近似的方法处理字符串和浮点运算，支持原始类型的测试输入以及复杂数据类型。

EXE：EXE[17]是一个重点针对测试复杂的系统代码开发的符号执行工具。它的模型内存达到位级精度，并通过优化达到足够快的约束求解速度。

KLEE：KLEE[18]是重新设计的EXE，支持动态符号执行，具有位级精度的模型内存，采用了多种约束求解的优化和启发式搜索，以获取更高的覆盖率。

Fuzzgrind：Fuzzgrind是一个基于符号执行的自动模糊测试工具，2009年由Sogeti/ESEC实验室开发。

Splat：Splat是一个基于符号执行的定向随机测试工具，它能够快速地检测缓冲区溢出。

根据收集的文献资料，本文将上述10个符号执行工具的基本情况进行如下比较和分析，如表1所示。

5 结语

本文根据系统文献综述方法，对符号执行技术在测试用例生成中的应用和研究相关文献进行了分析和综述。符号执行技术在国内外研究学者的共同努力下，逐渐成为一种成熟的自动用例生成技术。

他的眼睛望着对面闪耀的酒店霓虹，心里回味着刚才这句话。他想到了什么似的，笑了一声。很短暂的一瞬。那手在他手里惊诧了一下，好像在问你笑什么？果然，他侧目看见了一双疑惑的眼神。很美的一双眼睛。就这么打动他的一双眼睛。

表1 符号执行工具比较

启发式搜索算法能有效地引导符号执行的路径探索，引入并行计算能显著提高执行效率，开发新的更有效的启发式搜索和实现并行化将会成为符号执行技术的发展趋势。而符号执行技术固有的一些弱点，如路径爆炸，也需要更完善的解决方案来改进。此外，符号执行技术与其他的优秀测试用例生成技术，如模型检测技术、基于搜索的测试生成技术的结合也是未来的一个发展趋势。

唐代开放的社会风气中，一方面，承接前代的传统，上层妇女因文才受到帝王表彰从而具有获得官职的机会。上官婉儿因才华卓著受到武则天任用，官员的章表书奏多委任于她，中宗时期，又大被重用，不久即拜为昭仪。

[1]J.C.King.Symbolic Execution and Program Testing.Communications of the ACM,vol.19,pp.385-394,1976.

[2]G.Campana.Fuzzgrind:an Automatic Fuzzing Tool.Hack.lu,2009.

[3]D.Yu,L.Mengxiang,Y.Kai,Z.Yi,C.Yinli.Achieving High Branch Coverage with Fewer Paths.in Computer Software and Applications Conference Workshops（COMPSACW）,2011 IEEE 35th Annual,2011,pp.155-160.

[4]P.Boonstoppel,C.Cadar,D.Engler.RWset:Attacking Path Explosion in Constraint-Based Test Generation.in 14th International Conference onTools and Algorithms for the Construction and Analysis of Systems,TACAS2008.March 29,2008-April 6,2008, Budapest,Hungary,2008,pp.351-366.

[5]K.Taneja,T.Xie,N.Tillmann,J.De Halleux.eXpress:Guided Path Exploration for Efficient Regression Test Generation.in 20th International Symposium on Software Testing and Analysis,ISSTA 2011,July 17,2011-July 21,2011,Toronto,ON,Canada,2011,pp. 1-11.

[6]S.Bucur,V.Ureche,C.Zamfir,G.Candea.Parallel Symbolic Execution for Automated Real-World Software Testing.Presented at the Proceedings of the Sixth Conference on Computer Systems,Salzburg,Austria,2011.

[7]B.Elkarablieh,P.Godefroid,M.Y.Levin.Precise Pointer Reasoning for Dynamic Test Generation.in Proceedings of the Eighteenth International Symposium on Software Testing and Analysis,2009,pp.129-140.

[8]M.Emmi,R.Majumdar,K.Sen.Dynamic Test Input Generation for Database Applications.2007 ACM International Symposium on Software Testing and Analysis,ISSTA'07,pp.151-162,2007.

[9]P.Kai,W.Xintao,X.Tao.Generating Program Inputs for Database Application Testing.2011 26th IEEE/ACM International Conference on Automated Software Engineering,pp.73-82,2011 2011.

[10]Y.Kim，M.Kim.SCORE:A Scalable Concolic Testing Tool for Reliable Embedded Software.in 19th ACM SIGSOFT Symposium on Foundations of Software Engineering,SIGSOFT/FSE'11,September 5,2011-September 9,2011,Szeged,Hungary,2011,pp.420-423.

[11]S.Thummalapenta,J.De Halleux,N.Tillmann,S.Wadsworth.DyGen:Automatic Generation of High-Coverage Tests Via Mining Gigabytes of Dynamic Traces.in 4th International Conference on Tests and Proofs,TAP 2010,July 1,2010-July 2,2010,Malaga,Spain, 2010,pp.77-93.

[12]P.Godefroid,N.Klarlund,K.Sen.DART:Directed Automated Random Testing.Acm Sigplan Notices,vol.40,pp.213-223,Jun 2005.

[13]S.Koushik，G.Agha.CUTE and jCUTE:Concolic Unit Testing and Explicit Path Model-Checking Tools（Tool Paper）.Computer Aided Verification.18th International Conference.CAV 2006.Proceedings（Lecture Notes in Computer Science Vol.4144）,pp.419-23,2006.

[14]S.Godboley,G.S.Prashanth,D.P.Mohapatro,B.Majhi.Increase in Modified Condition/Decision Coverage Using Program Code Transformer.2013 3rd IEEE International Advance Computing Conference（IACC 2013）,pp.1400-7,2012 2012.

[15]J.P.Escobedo,C.Gaston,P.Le Gall,A.Cavalli.Testing Web Service Orchestrators in Context:A Symbolic Approach.Proceedings of the 2010 8th IEEE International Conference on Software Engineering and Formal Methods（SEFM 2010）,pp.257-67,2010.

[16]D.Vanoverberghe,N.Tillmann,F.Piessens.Test Input Generation for Programs with Pointers.in 15th International Conference onTools and Algorithms for the Construction and Analysis of Systems,TACAS 2009.

[17]C.Cadar,V.Ganesh,P.M.Pawlowski,D.L.Dill,D.R.Engler.EXE:Automatically Generating Inputs of Death.ACM Transactions on Information and System Security,vol.12,2008.

[18]K.YoungJoo,K.Moonzoo,K.Yunho,J.Uijune.Comparison of Search Strategies of KLEE Concolic Testing Tool.Journal of KIISE: Computing Practices and Letters,vol.18,pp.321-5,April 2012.

Symbolic Execution for Automated Test Generation

ZENG Jia-yan

（College of Computer Science,Sichuan University,Chengdu 610225）

Symbolic execution has been proposed nearly four decades,it has been widely used in software engineering and became a popular automated testing technique,due in part to the progress in computer science and techniques.Summarizes the symbolic execution for automatic test case generation,intends to provide the appropriate reference for academia or industry.Describes the basic principles of symbolic execution techniques,describes the corresponding improvement strategies to problems facing symbolic execution,introduces the typical case of symbolic execution in automatic test case generation,introduces and made comparison of existing symbolic execution tools,and discusses the future trends of symbolic execution.

Symbolic Execution;Concolic Testing;Automated Testing;Test Generation

1007-1423（2017）04-0012-05

10.3969/j.issn.1007-1423.2017.04.003

曾嘉彦（1992-），女，广东韶关人，硕士，研究方向为自动化测试、数据挖掘

2016-12-15

2017-01-15