（计算机软件与理论专业论文）自动化单元测试中的路径空间缩减的研究.pdf

t h e s i sf o rm a s t e rd e g r e ei n2 0 1 1 u n i v e r s i t yc o d e ：1 0 2 6 9 m e t r i cn u m b e r ：5 1 0 8 1 5 0 0 0 0 9 e as tc hin anor maluni v e r s i t y r e s e a r c ho np a t hs p a c er e d u c t i o ni na u t o m a t e du n i tt e s t c o l l e g e ： m a j o rf i e l d ： s p e c i a l t y ： s q 鱼i 巡墨 皇e 凸g i q 皇呈 i 凸g ! d 兰! l 主婪! 皇 q 田巳u ! 金 墨q 鱼i 巡坌 皇坌d 垡! b 皇q 盟 s o f t w ar ev er i f i c a t i o n a d v i s o r ： q i 鱼凸gh 皇。 q 鱼全g 垡坌d g 竖 g r a d u a t e ：t a 0s u n 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文失衡样本分类问题的自动过滤算法的研究，是在华 东师范大学攻读盘圭痛士( 请勾选) 学位期间，在导师的指导下进行的研究工作及取得的 研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究 成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名： b j w - 枷! f 年j 月口日 华东师范大学学位论文著作权使用声明 失衡样本分类问题的自动过滤算法的研究系本人在华东师范大学攻读学位期间在 ， 导师指导下完成的互踏博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学所有。 本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关机构如国 家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位论文进入华东师范 大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国博士、硕士学位论文共建 单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合 理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文宰， 于年，月日解密，解密后适用上述授权。 沁乃2 不保密，适用上述授权。 导师签名本人签名 硷盗 一 钞f 年厂月；。日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学 位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未 经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文， 均适用上述授权) 。 逊透硕士学位论文答辩委员会成员名单 姓名职称单位备注 刘静教授华东师范大学主席 软件学院 陈铭松副教授华东师范大学 软件学院 彭超副教授华东师范大学 软件学院 目录 摘要 a b s t r a c t 第一章绪论 1 1 研究现状1 1 1 1d a r t 和c u t e 2 1 1 2p e x ? 3 1 2本文贡献4 1 3 本文结构k 5 第二章相关技术介绍” 2 1 2 2 2 3 第三章 3 1 3 1 1 3 2 第四章 符号执行”6 符号执行与用例生成7 程序数据流分析以及程序切片：8 前向性函数依赖分析技术n 指针别名模型j 1 3 p o i n t s t o 关系模型1 3 前向的函数调用依赖分析1 s 部分符号执行技术 第五章 实现与实验评估 4 1 4 2 实现2 4 实验评估2 6 第六章相关工作 第七章工作总结 3 2 参考文献3 3 致谢 摘要 自动化单元测试采用符号执行与约束求解的技术，通过动态执行程序，收集 执行路径上的分支选择上的约束信息，通过约束求解生成覆盖该路径的测试用例， 继而执行新的测试用例搜集新的路径约束。这个过程自动迭代执行，覆盖更多的 程序分支，直至完成对待被测程序完成指定覆盖要准则，最终实现程序的测试工 作。近几年这个方向上的工作得到很多的关注，涌现了大量的比较成熟的产品， 如自动化测试工具d a r t ，c u t e ，p e x 等等。 对于单元测试，一个很难克服的问题就是程序路径空间爆炸。一个程序的程 序空间在某些情况下，如出现循环递归等结构时，更是无数条。尤其是在覆盖率 要求比较严格的情况下，如分支覆盖，全路径覆盖，路径空间便很难被有效地探 索完整。任何一个现有的的解决方法，都不能有效解决程序路径空间爆炸的问题。 本文中我们在不影响被测单元分支覆盖准则要求前提下，提出几条关于空间缩减 的方法，减少不必要的函数空间探索，通过寻找等价路径来减少路径空间探索。 我们的实验表明，采用我们的方法会在既能保证测试结果的前提下有效地减小程 序路径空间。 关键字：软件测试，自动化测试，符号执行，约束求解，路径空间缩减 a b s t r a c t a u t o m a t e du n i tt e s ta d o p t ss y m b o l i ce x e c u t i o na n dc o n s t r a i n ts o l v i n g t e c h n i q u e s i to b t a i n st h es y m b o li cv a l u e so ft h ep a t hd u r i n gt h e e x e c u t i o n ，a f t e rt h a ti tm o d i f i e st h ec o n s t r a i n ta n dg e n e r a t ean e wt e s t i n p u t t h i sw o r ki sm a n i p u l a t e db yi t e r a t i o n sa u t o m a t i c a l l yt oa c h i e v e t h eu n i tt e s tg o a l i nr e c e n ty e a r s ，m a n ys u c ht o o l sa r ed e v e l o p e d ，s u c h a sd a r t ，c u t e ，p e xa n ds oo n h o w e v e r ，f o ru n i tt e s t ，o n ed i f f i c u l t yi sh o wt ot a c k l e w i t ht h e e x p l o s i o no fp a t hs p a c e ，t h e r e sn os t r o n ga n dp e r s u a s i v es o l u t i o n c u r r e n t l y i nt h i sp a p e r ，w ep r e s e n to u rs o l u t i o no nh o wt oe l i m i n a t et h e p a t hs p a c et h r o u g hr e m o v i n gi r r e l e v a n tp a r to fp a t hi nc o m p o s i t i o n a l f u n c t i o n sa n dc o m b i n i n ge q u i v a l e n t p a t h sw i t ha f f e c t i n gt h eb r a n c h c o v e r a g er a t eo ft h et o b e t e s t e du n i t o u re x p e r i m e n t sr e v e a lt h a to u r s o l u t i o nc a ns i g n i f i c a n t l ye l i m i n a t et h ep a t hs p a c ew i t h o u ta f f e c t i n gt h e u n itt e s tr e s u l t k e y w o r d s ：s o f t w a r et e s t ，s y m b o l i ce x e c u t i o n ，c o n s t r a i n ts o l v i n g ，p a t h s p a c er e d u c e 第一章绪论 单元测试是软件测试中的一个必须环节，对于保证软件正确性，可信赖性起 着相当大的作用。单元测试是一种白盒测试方法，是由程序员在知晓程序逻辑以 及代码结构的前提下执行，所以它对程序功能的正确性，完整性有着先天的针对 性，因而单元测试对程序的质量有着无法忽略的极其重要的影响。 单元测试也是一项很消耗人力和时间资源的工作。程序员需要设计大量数目 的测试用例，来检测对程序的的行为是否满足要求。事实上，理论证明覆盖程序 的所有行为是一项在有限的资源条件下不可能完成的任务。于是在学术界和工业 界，人们提出了各种类的覆盖准则，如语句覆盖，路径覆盖等等。对于不同级别 的要求，对待测程序的单元测试便需要达到某些指定的对应的覆盖准则。其中分 支覆盖和路径覆盖是比较常用，要求比较的高的两种覆盖准则。后者又可以细分 划为基本路径覆盖，全路径覆盖等等。事实上，无论是哪一种准则，要完全达到 它们的要求，仍然是一项艰巨的任务。实际工作中，由于程序员的时间精力以及 开发资源所限，单元测试工作更难以达到这些准则要求。所以自动化单元测试有 着非常积极的意义，既能节省大量的资源，又能达到更高的路径覆盖要求。它将 大程度改善软件的质量问题，对提高软件的可信赖性有着相当大的促进作用。 符号执行是一项很常用的程序分析技术 2 0 。它广泛用于单元化测试用例自 动生成( t e s tc a s eg e n e r a t i o n ) 和测试用例集增强( t e s ts u i t ea u g m e n t a t i o n ) 研究方向中。符号执行通过执行程序路径，搜集出现该路径上分支信息，以及变 量的符号值信息。对于出现在路径上的变量取值，符号执行并不是记录该变量的 具体取值( 在内存里储存的真实值) ，而是记录它们的符号值。然而符号执行对 计算资源的消耗非常大，尤其是需要对程序的路径一一分析时。而通常程序的路 径条数并没有限制，由些以来，常规的符号执行对资源消耗的没有一个可信赖的 度量性。 1 1 研究现状 传统的单元测试主要是使用随机测试的策略，通过大量执行随机生成的测试 用例，来测试被测试的单元是否能够达到预期的要求。实际上为了使得单元测试 l 结果更加有说服力，常常会使用覆盖率作为一个重要的衡量标准。然而对于随机 测试，由于随机生成的测试有用例具有很大的随机性，无法对不同结构的程序达 到覆盖要求。因此，它很难保证被执行的测试用例能够达到覆盖标准。所以随机 测试的实际效果，是很难以得到保障的。 模型检测也是一项用于检测软件正确性的重要技术 1 3 1 8 。模型检测技术 通过对被待测序建立抽象模型，再在模型层次上检测该模型是否满足要求的规范， 如果能找到某些模型状态不满足规范，则证明被测程序中存在着错误。由于模型 是对程序的一个抽象，所以通常会出现些虚假的模型状态，这些状态违反了规范， 所以此时需要对模型做进一步的精化 1 3 1 8 3 。这个精化过程常常是迭代完成。 模型检测技术能够精准判断被测程序是否满足需求，但是由于为被测程序建立模 型，和将程序的性质通过形式化的方法抽象成能够使用的规范，都是项劳动量很 大复杂度很高的工作。所以在实践中，模型检测并不是能够广泛使用，高效率的 检测软件质量的手段。 随着计算机的计算能力和存储能力的不断增强，完成特定路径覆盖标准的自 动化单元测试越来越切实可行。尤其是动态符号执行在近几年的兴起 4 2 1 2 2 。符号执行是指程序在执行时不是使用具体的取值来运算，它是使 用程序输入的符号值参与运算。由于静态执行 3 0 儿1 1 先天性的劣势，使得静态 符号执行在搜集符号信息时无法得到精准的符号信息，比如出现循环时，由于无 法知晓循环执行的次数，所以便无法得到循环结束后的精准符号信息。然而动态 符号执行会与具体执行同时进行，因此可以捕捉到更为精确的符号信息，比如路 径上的条件约束。此外现在的求解器的运算能力也越来越强，开始能处理较复杂 的约束。此背景下，自动化单元测试成为一个热门的研究方向。国内外多个研究 小组在这方面取得了突破，发明了多个用以自动单元测试的工具。如微软研究院 推出的d a r t 工具 1 6 ；美国加州大学伯克利分校计算机系推出的c u t e 工具 2 6 ； 微软研究院推出的p e x 工具 2 7 以及斯坦福的e x e 工具 1 0 。这些工具都是采用 动态符号执行与约束求解的技术，自动生成测试用例，完成自动化测试。 i i 1d a r t 和c u t e d a r t ( d i r e c t e da u t o m a t e dr a n d o mt e s t ) 是g o d e f r o i d 于2 0 0 5 年发布的一 个自动化测试工具。d a r t 在具体执行程序时，同步进行符号执行。符号执行帮 助d a r t 搜集程序路径中的路径信息，以此来生成下一次程序执行需要的测试用 2 例。如此迭代，理论上d a r t 可以完整地完成对程序所有空间的遍历，完成一项 很出色的单元测试工作。它使用静态程序代码分析工具，植入监控代码 ( i n s t r u m e n t a t i o n ) ，记录在执行过程中程序各种信息，如路径条件( p a t h c o n d i t i o n ) 和程序变量的符号值，来生成一组约束表达式。这组表达式代表了这 条路径上的所有约束信息。再通过修改约束表达式上的某些项生成新的约束表达 式。该新表达的解便是一个潜在的新的测试用例。 然而，d a r t 只能够支持整型数据c 语言程序，这点大大减小了它的广泛适用 性。因为实际中程序包含更多的类型，甚至有指针，结构体，数组等复杂数据类 型，所以d a r t 的使用局限性很大。除此之外，d a r t 在生成新测试用例使用的方 法是深度优先法，通过修改约束表达式的末项来生成新的约束表达式。这样的简 洁做法效率很高，但是在遇到复杂结构的程序时，容易卡在某个状态( 比如循环) ， 如此无法继续完成对程序的路径覆盖。实际上d a r t 使用一个深度限制参数来避 免这种情况，但是这样更加造成了对路径的探索不完整，如果一条路径长度超过 了深度限制参数值，那么d a r t 将不再继续探索下去，于是造成了不完整的探索 现象。 在真实实验上，d a r t 的表现只是中规中矩，尤其是它的路径探索算法，理论 上它在计算资源足够充足的情况下，可以完成对程序空间的遍历。但是实际上它 不可能达到这样的标准。 c u t e ( ac o n c o l i cu n i tt e s te n g i n ef o rca n dj a v ap r o g r a m ) ，由k o u s h i k s e n 于同年，即2 0 0 5 年发布。该工具同样使用具体执行与符号执行相接合的方 法，通过搜集出来的路径约束生成新的测试用例。迭代测试完成语句覆盖和断言 覆盖的目标。与d a r t 不同的是，c u t e 可以支持较复杂的数据类型，如结构体， 指针等。 1 1 2p e x p e x 是微软研究院2 0 0 8 年发布的针对n e t 平台程序的一个自动化白盒测试 工具。如今微软已经将这个工具集成到其v is u a ls t u d i o 的开发环境中。p e x 通 过使用动态符号执行技术，不断地生成新的测试用例来反复执行被测程序，以覆 盖程序中的不同的路径，以执行路径绑定的模型检测工作。它使用了微软自己开 发的z 3 定理证明器 3 1 ，一个效率很高的支持非线性约束求解的定理证明器。 此外，p e x 也支持了多种路径搜索策略，以更好地达到语句覆盖标准下的白盒测 3 试目标。 1 2 本文贡献 本文通过深入分析当前的自动化单元测试的现状，发现这些工作的优势与不 足。同时深入考察了工业界及学术界对单元测试的质量要求准则，对照研究当前 工作在这方面的缺陷。我们发现当前的单元测试工具，在测试覆盖率上，尤其是 路径覆盖上，并没有一个成熟的规范，更没有一个成熟的策略来解决这个问题。 对于单元测试来说，待测程序的路径空间巨大始终是一个极难解决的问题，因此 要实现一定的路径覆盖标准，就必须需要同时结合路径覆盖准则和缩减路径空间。 所以，为了解决上述问题，本文的目标为，1 ) 实现自己的单元测试工具，使用 符号执行，具体执行与约束求解等技术。2 ) 本文提出并实现几项路径空间缩减 的算法，以使得在实际的单元测试中，测试资源消耗( 时间和计算资源) 可以度量 化。本文的贡献与创新之处如下所示。 我们实现了自己的针对c 语言的自动化单元测试工具c a u t ( cl a n g u a g e a u t o m a t e du n i tt e s tt o o l k i t ) 。c a u t 通过符号执行与具体执行搜集出程序的 路径信息，继而求解约束生成新的测试用例，从而完成自动化单元测试的目标。 c a u t 采用静态分析与动态执行结合的分析方式，能够处理c 语言的各种数据类 型，除了极个别的类型暂时不提供支持，如函数指针。另外，c a u t 开放了多种 接口，用以支持各种路径覆盖准则。 我们提出了纵向缩减路径空间缩减的方法。因为路径代表的是一个程序执行 时的迹，所以减少些这条迹上的一些不必要部分，将会缩减很多执行与探索时间。 针对这种情况，我们提出了去除无关函数调用，以避免反复的函数调用造成的空 间爆炸问题。使用这种方法，我们通过静态分析，找出程序中的某些函数调用， 而这些函数调用不影响程序后继路径选择。这些和函数调用可以不使用符号执行， 而仅仅用具体执行，实验证明，这样的探索可以减少大量的计算资源。 对于需要被符号执行的被调用函数，我们提出了部分符号执行方法。在保证 被测单元的分支覆盖的前提下，c a u t 会尽量减少对被调用的子函数的空间探索， 也就是不去完整地对它里面的所有分支进行符号执行。c a u t 采用静态分析和动 态符号执行结合的方法，在程序满足了待测单元的分支覆盖后，便停止对其它子 函数的空间探索。该方法在很大程序上也减轻了符号执行的负担，节省了自动化 单元测试所战胜的计算资源。 4 1 3 本文结构 本文共分为五章。第一章针对自动化单元测试进行背景介绍，并提出了现在 的工作中存在的问题和我们的研究目标。第二章介绍我们的解决文案里涉及到的 相关技术。第三，四章着重介绍我们的路径空间缩减方法，主要是前向函数依赖 分析技术和部分符号执行技术。第五章讲述我们的解决文案的实现，并通过真实 实验来呈现我们的算法的效果。最后一章是我们的工作总结与未来展望。 5 2 1 符号执行 第二章相关技术介绍 符号执行是一种对程序的抽象解释，它是在对程序的分析过程中，跟踪程序 中变量的符号值，而不是具体值。符号值指的是对变量值的一个抽象，一个变量 的符号值，可以是一个符号值单子，也可以是由很多变量的符号值通过数学运算 符连接起来的一个数学表达式。 表1 符号执行示例 如表l 中，对于变量c ，它的取值是由变量a ，b 决定的。对于上例，c 的符 号值如下如示，我们用s y m ( a ) 来表示变量a 的符号值： s y m ( c ) ：= s y m ( a ) + 2 木s y m ( b ) 由上例可见，对于程序语句，每个赋值语句的左值，其符号值是由语句右边 的变量的符号值通过操作符连接起来，构成一个符号值表达式。在遇到分支语句 中，如上例中的第5 0 行，我们可以计算出以下的符号值表达式t s y m ( c ) = = 1 0 0 因此，对于每一次执行的程序路径，我们得到一系列的执行过的语句，或者 是赋值语句，或者是分支语句。对于任何一种语句，都可以有如上所示的两种形 6 式的符号表达式。这些符号表达式的交，称之为路径条件，记为p a t hc o n d i t i o n ， 用以表示程序执行到这条路径的符号值执行情况。由于程序中其它变量，要么是 常量，要么是由程序输入的变量决定，所以这些变量会被输入变量的符号值通过 操作符连接起来的数学表达式来表示出来。如此可知，路径条件表示出程序中的 某条特定路径对应的程序输入的约束。换言之，满足路径条件的程序输入，都会 执行对应的程序路径。 p a t h c o n d i t i o n = s y m ( c ) ：= s y m ( a ) + 2 s y m ( b ) as y m ( c ) = = 1 0 0 2 2 符号执行与用例生成 在近十年的软件测试自动化方向的研究中，符号执行开始流行成为一个基本 技术。目前主流的自动化单元测试研究，都是建立在符号执行的基础之上的。这 是因为，记录下程序的输入值，使得程序中出现的变量，尤其是程序的输出，都 能够用符号值表达出来。更确切地说，程序的输出会是一个关于输入变量符号值 的一个数学表达式。因此，使用符号执行，可以建立起程序输出变量与程序输入 的联系，通过观察程序输出的符号值，来研究程序输入对程序输出的影响，也就 是程序测试工作。 具体来说，路径条件它代表了一系列的程序的测试用例，这些用例它们在执 行时在都是在一条路径上。因为它们都满足路径条件，也就意味着，这些测试用 例在遇到路径选择时，即在程序分支处，它们的选择都是一样的。这是因为对每 个路径分支处的约束，假设这个约束为c ，这个c 显然被包含在路径条件p a t h c o n d i t i o n 中，如此，这些用例要么都满足c ，要么都满足c 。 综上所述，通过符号执行，可以获得程序的特定路径的路径条件，而这个路 径条件代表着一系列测试用例，这些用例在执行时都是覆盖程序中的同一条路径。 此外，如果对路径条件中的某些约束处的取值取反，就得到一个新的路径条件， 这个路径条件很可能就是一个新的程序路径的路径约束。如上例，在对行5 0 处 的约束取反，得到以下一个新的路径条件： p c = s y m ( c ) ：= s y m ( a ) + 2 s y m ( b ) as y m ( c ) ! = 1 0 0 7 求解这个路径条件p c ，可以得到类似这样的一组解 ，显然发现， 执行这个测试用例，程序将覆盖到分支选择的e l s e 分支，即行7 0 处，而不是行 6 0 。 此外，由于程序是顺序执行的，所以对于一个路径条件来说，出现在顺序的 后面的约束，是受前面的约束控制的，尤其是分支结构，假设有以下表2 的条件 嵌套分支程序： 表2p a t hc o n d i t i o n 岽例 行2 0 处的分支是嵌套在行1 0 的分支体内。假设有一条路径执行了行1 0 ，2 0 ， 得到的路径条件：p c = ( n 0 ) a ( 61 = 0 ) ，如果改变前一个约束，a o ，那么从 实际程序结构上看，这个路径约束是不可能满足的p c = ( 口0 ) a ( b t = 0 ) 。因 为如果前面一个约束是取a o ) 6 0r e t u m a ； 7 0e l s er e t u r n - a ； 如上例表4 中，程序的输出是变量a 的值，或者a 的相反数。通过数据流分 析，发现a 的取值与变量b 无关。因此在本程序内，关于变量b 的操作对a 的结 果都是没有影响的，所以这些代码可以被切除掉，同时又不影响我们所关心的程 序状态。上表的右边是切片结果。 使用程序切片，可以使得程序的规模进一步缩小。尤其是在关心程序的特定 状态时。如程序输出。通过程序切片，可以剔除对程序输出结果没有影响的其它 程序结构，达到缩减程序的目的。 程序切片是建立在程序分析的数据流分析基础之上的。因此，按照沿着数据 流分析方向，程序切片也可以分为前向切片与后向切片。而按照是否执行程序来 完成分析，程序切片又可以分为动态切片与静态静片。在本文中，针对我们的使 9 用 的 第三章前向性函数依赖分析技术 正如前文所述，对于真实的程序进行自动化单元测试，处理组合单元是一个 很有挑战性的问题。很多情况下，待测单元会调用其它函数来处理一些子任务。 而符号执行在自动化单元测试中又是一个很耗计算资源的工作。在这篇文章里， 我们提出了在组合测试中减轻符号执行的负担的方法。 被调用函数的数据依赖分析检测出待测单元中不影响程序后继路径选择的 被调用函数。如果这些被调用函数不影响后继路径选择，这些函数将不使用符号 执行：以下如表5 所示是一个简单示例。 表5f i b 函数示例 在此例中，程序主要是3 条路径，分别对应于程序中的三个分支。为了满足 覆盖程序里路径，需要生成4 个测试用例，为：n l 。然后 传统的符号执行技术会递归分析被调用的行6 0 处的f i b 函数。递归性层层分析 会造成大量的工作负担，而实际上这些的工作对于满足路径覆盖是没有意义的， 因为行6 0 处的f i b 函数调用是不影响路径选择的。如图2 所示，该单元的数据 依赖图显示，被递归调用的函数是不影响条件分支节点( 图中有圆角矩形表示) ， 也就是说不影响路径选择。程序后面的分支如何选择，是走哪些分支，是不会受 这个调用函数影响。因此，这个被调用的函数不需要记录符号值用以约束搜集。 图1 显示了f i b 函数的依赖图。图中的圆角矩形为程序中的分支点，矩形为赋值 语句。实线箭头为控制流，虚线箭头表示函数调用。 1 1 图1f i b 函数控制流图 在实际程序中，这种函数调用，称之为函数依赖，非常常见。在这种情况下， 一个函数会与其它多个函数相关系，被其它函数调用，或者调用其它函数。于是 通过函数依赖分析，可以确定某些函数是否影响程序后继路径的选择，然后相应 采取是否符号执行的策略。我们采用了静态分析的方法，使用了前向数据依赖分 析技术来找到函数依赖。因为在数据依赖分析中，指针会造成隐式的数据依赖， 如下例所示。我们同时采用了指针别名分析模型来解决这个问题。 在以下表6 中的例子中，函数f 调用了函数g 。直观上看行6 0 处的函数调用 g ( b ) 并没有影响到后继程序的路径选择，因为后面只有一个分支节点，行8 0 处， 变量c 决定这个分支的走向。但是实际上，我们可以发现由于变量c 被指针变量 a ，b 同时指向，而函数调用g ( b ) 影响了指针b 指向的内存内容，也就是指针变量 a 所指向的内存内容。在行7 0 处，a 指向的内存的值赋值给变量c ，所以该函数 调用是对行8 0 处路径选择有直接影响。因此我们需要对指针的隐形数据影响做 分析，以使得函数依赖分析更为准确。 表6 函数依赖分析示例 3 1 指针别名模型 c a u t 使用c i l 实现i n s t r u m e n t a t i o n 。c i l 可以将c 语言代码转换成一个中 间形式的c 语言代码，主要是以三地址式的形式。在这样的情况下指针别名问题 就转换为指针的数据依赖分析问题。如果有一个指针变量被某个函数调用影响， 而且这个指针的别名同时影响某些后继的路径选择，那么这个函数调用被视为对 后继路径有影响，需要被符号执行。此外，指针的类型强制转换也需要被考虑。 本章节详细陈述指针别名模型的算法与实现。 3 1 1 p o i n t s t o 关系模型 c a u t 使用p o i n t s t o 关系来表达指针与其指向的变量的关系，以 这样的二元组形式。这个二元组表示：v 1 是一个指针变量，它指向变量v 2 。在 指针别名分析模型中，集合p s a 被用作保存所有的指向关系，也就是保存一系列 的 - - 元组。由于c i l 会将c 语言的代码转换到一个三地址式的中间形式， 这个过程同时将涉及到指针的运算也简化到以下的几种场景： p = & v ：这种情况表示指针p 被变量v 的地址赋值。所以指针p 会 指向变量v 。因此可以如此表示： 。 p l ：p 2 ：这种情况表示指针p 1 被指针p 2 赋值。p 1 指向p 2 所指向 的内容，意味着p 1 将是p 2 的别名。因此对于所有的t ，如果 存在，则将有 。 v = ( t y p e ) p ：这种情况发生在变量v 和变量p 是不同类型，比如 是不同级别的指针，由于涉及到强制类型转换，处理方法将比第2 种更为复杂。指针的级数也将被保存，比如i n t * * 就是一个2 级指针 数据类型。当采用了显示表达指针的级数信息，下述例子解释了如 何处理指针的强制类型转换问题。 表7 示例：多级指针类型转换 在表7 中例子中，p l 是一个1 级的i n t 型指针，而p 2 是一个2 级的i n t 型 指针。在行4 0 处，发生了一个强制类型的转换，将一个2 级的i n t 指针强制赋 值给一个1 级的i n t 型指针。使用规则l ，2 ，p s a 被更新成这样的一个集合： ， ， ) 。但是对于指针变量p 1 的p o i n t s t o 关系分析， 会得到这样的结果 ，而不是 ， 。这是因为考虑 到指针p 1 是一个1 级的指针，所以在递归地寻找它指向的内容时，寻找过程将 在找到它的下一级指向内容时立即返回，而不是继续寻找，相反，对于指针p 2 ， 它的指向结果如下： ， ) 。这样的结果也是由它的数据类 型决定。所以，对于一个指针变量，将会被找出多少个级别的指向关系，是由它 本身的级数决定，换而言之，是由它的数据类型本身决定，而不是在p s a 集合中 找出所有的潜在指向关系。 使用前文所呈现的规则，可以为待测试的单元计算出p s a 。在p s a 的帮助下， 在处理函数依赖时指针的隐式的影响可以被正确处理了。 1 4 3 2 前向的函数调用依赖分析 条件或是循环语句决定着程序的路径选择( 都是分支语句) ，进而影响着单元 测试对路径的覆盖。所以无论是条件语句，还是循环语句，其中出现的变量需要 被搜集符号值，以构建路径条件约束表达式。因此，如果这些变量没有被该路径 上之前的函数调用所影响，那么那些函数调用就不需要被符号执行展开，对它们 仅仅使用具体执行就已足够。本章节将呈述如何发掘函数调用与分支语句中的变 量间的影响关系，从而决定是否对该函数调用以符号执行还是具体执行。 为了处理函数依赖分析，需要三个变量因子： 活动集a 用来记录被函数调用影响的变量。如果一个变量被一个函 数调用所影响，它将被记录到此集合里。之后如果有变量被集合里 的某些变量重新定义，那么这个重新被定义的变量需要被加到活动 集里。相反如果活动集里有变量被活动集外的变量重新定义，那么 这个被重新定义的变量需要被从活动集中移出。 定义集d e f 用于记录对于一个语句中被定义的变量。 使用集r e f 用于表示一个语句中被使用的变量。 总得来说，这个分析工作是在逐行扫描和分析源程序的代码时进行。因为c i l 会将源代码转换到一个三地址式的中间形式，并且代码是以作用域为单位组合在 一起。所以函数依赖分析也以作用域为单位来扫描。扫描算法如图2 所示。 a n a l y z es c o p e ldl 一一 一 、， i n p u t ：b ( b l o c ko fs t a t e m e n t s ) i fi s _ i n s t r u c t i o n s ( b ) t h e n 一 。 1 、 i o r e a c hs1 1 1ba n a l y z e _ s t a t e m e n t ( s ) ； e l s ei fi sl o o p ( b ) t h e n b d = g e 乙l o o p _ b o d y ( b ) ； a n a l y z e _ s c o p e ( b d ) ； a n a l y z e _ s c o p e ( b d ) ；s h o u l db ee x e c u t e dt w i c e ! e l s ei fi s _ b r a n c h ( b ) t h e n i f b = 舻乙fb r a n c h ( b ) ； e l s e b = g e t _ e l s e _ b r a n c h ( b ) ； a n a l y s e 图2 函数依赖分析扫描算法 因为函数调用之后的路径选择是被关注的对象，所以在每一个函数调用之后 的每个分支语句，无论是条件判断语句，还是循环语句，都需要被分析处理。由 于c a u t 的函数依赖分析工作是由静态分析完成的，分析工作采取了保守做法： 条件分支的两个分支都需要被分析处理，循环被视作多次迭代处理。这是因为循 环语句的独特结构。因为对于一个循环，它的数据依赖不仅仅影响它之后的语句， 如果循环是多次迭代，它也会影响这个循环本身。 图3 展现了前向函数依赖分析算法。该算法的核心在于对每个语句的分析处 理。对语句的分析是建立在d e f 和r e f 两个集合之上。d e f 集体用来检查对于一 个语句，它新定义了哪些变量，它主要用来更新活动集a 。r e f 集合记录了一个 语句中使用了哪此变量，很明显，对于分支语句，只有使用变量，并没有定义新 变量。而使用的这些变量就影响着此分支的数据流取向。因此，分析分支语句的 使用的变量有无被之前的函数调用所影响便是此算法的根本思想。另外，如果使 用的变量中有指针变量出现，算法会扩充r e f 集合，通过该指针找到它所有的别 名，把这些别名也加入到r e f 集合。算法会遍历源程序多次，直到所有的函数调 用的数据依赖被分析完。对于每个分析，算法需要处理如下任务： 从程序的开始处，开始执行指针p o i n t s - t o 分析。在这个分析的过程中，如 果出现了函数调用语句，同时这个函数调用语句之前并没有分析处理过，则算法 要为这个函数调用创建一个活动集，每个函数调用都有一个活动集。否则忽略此 函数调用，继续往后分析。 如果某语句中存在变量，同时存在于活动集和r e f 集合中，这说明这个语句 新定义的变量被活动集中的变量影响，换言这，新定义的变量就是被活动集对应 的函数调用所影响。因而这新定义的变量将被加到该活动集中完成更新。此外， 如果该语句所使用的变量没有一个出现在活动集中，而被定义的变量存在于活动 集，这意味被定义的变量被其它变量重新定义，将不再受活动集对应的函数调用 影响，该变量必须从活动集中移除。 因为分支语句只使用变量，因此对于它所使用的变量，很容易判断它们是否 在活动集里。如果存在，则意味着此分支语句被该活动集对应的函数调用所影响， 则对于这个函数调用的依赖分析结束。反之，依赖分析将继续进行，直至找出一 个分支被该函数调用影响，或者到达程序末尾。 示例：表8 通过一个实例展示了前向函数依赖的结果。该例子是出自t a r 1 程序中的“x h e a d e r _ s e t k e y w o r d e q u a l ”函数( i s t c 中) 。t a r 是一个在u n i x 系统上非常有名的一个压缩解压缩程序。通过使用函数调用依赖分析，发现在图 中的第2 2 行，函数“a s s i g n _ s t r i n g 所修改的变量并没有影响到任何后续的分 支选择。所以当c a u t 执行这个函数时会仅仅只使用具体执行，而不使用符号执 行。此外，在行8 处的循环，该处的函数调用c a u t 会生成一个活动集 t m p 4 ) 。 活动集中的变量会影响前一行的代码，如果循环多次执行的话。可见，对于循环 处理，保守的做法是对循环的分析处理需要连续执行两次。 表8t a r 程序分析结果 ns t m tr e fd e fp s as e taa f f c t 1 p 。e q ； e qpp ，* e q 2 i f ( e q 一1 】一：)e q n o n e p ，* e q p ，* e q 3 p 一； ppp ，* e q 4 g l o b a l = f a l s e ；n o n e g l o b a lp ，* e q ) 5 l m l p l = p k 、) l ，= , p ，k wt m p l p ，* e q 6n n p 2 = i s s p a c e ( 木p ) ； 木pt m p 2p ，* e qt m p 2 7 t m p 3 = t m p1 & & t r a p 2 ； t m p l ，t m p 2 t m p 3 p ，* e q t m p 2 ，t m 。 w h i l e ( t r u e ) p 3 8 n o n e p ，* e q t m p 2 ，t m 6 i f ( t r a p 3 ) p 3 p 。； 9 e l s eb r e a k ； t m p 2 t mt m p 3p ，* e q ) p 3 1 0 水p = 0 ； p pp ，* e q 1 1 w h i l e ( t r u e ) n o n e i f ( t r a p 4 ) 1 2 ，l c p ，l c pp ，* e q 1 3n o n e p ，* e q 1 7 p = e q + 1 ； 1 4 衄p 4 = i s s p a c e ( 奉p ) ； t m p 4p ，* e qt m p 4 1 6 m a p 4 = m l p 4 1 5 & & ( 木p ) ；e qpp ，* e qt m p 4 1 6 矿h ； 木pt m p 4p ，* e qt m p 4 1 7 t m p 4 ，i c pt m p 4p ，* e qt m p 4 1 8 e l s eb r e a k ； ppp ，* e qi m p 4 1 9 t r a p 5 = 2 0 s t r c m p ( k w , e x t e n d e r n a m e ”) ； k w t r a p 5p ，* e qt r a p 5 2 1 i f ( t m p 5 - - 一4 ) ) 2 2 a s s i g n _ s t r i n g ( & e x t e n d t r a p 5p ，* e qt m p 5 e r _ n a m e ，p ) ； e x t e n d e rn a p ，* e q木p 2 0 e l s e m e ，p 2 3n o 第四章部分符号执行技术 如前文所述，通过函数调用依赖性分析，可以找到待测单元中对后续路径选 择无影响的函数调用。对于这些被调用的函数，c a u t 对它们具体招待，而不是 符号执行。因为符号执行是项很消耗计算资源的运算。 此外，对于被调用的函数，如果它们影响待测单元的后续路径选择，c a u t 对它们采用部分符号的方法。即不会以覆盖路径的目标测试这些被调用的函数。 只关心这些函数的影响的变量，如何影响后续的路径选择。换言之，只有待测单 元是以路径覆盖为目标，其它任何函数，是符号执行还是具体执行，都是以覆盖 待测单元的路径为准则。这个章节将介绍对于这些被调用的函数如何进行部分符 号执行。 本算法方首先定义了路径树结构，用以存储路径执行树数据。后者是在符号 执行时建立起来的。图x 给出了它的形式化定义。该结构是一个树形的数据结构， 树上的节点关联到程序的分支判断语句。非叶子节点有五个内部成员，分别为函 数编号，语句号，谓词，左子节点指针，右子节点指针。其中函数编号和语句号 用来标记对应语句在待测单元中的位置信息。而谓词是对应于分支语句上的判断 条件。左子节点表示在对该谓词的取值取真时程序的走向，反之右子节点表示谓 词取假时程序走向。换言之，从该树的根节点到叶子节点对应着待测单元的一条 路径。对于叶子节点，它们只有一个内部成员，一个布尔值变量，用以记录从根 到该叶子节点的这条路径是否被探索过。随着待测单元的不断被探索测试，这棵 路径树也在不断增长。 11 0i n ta b s ( i n tx ) 1 2 0 13 0 亚( x 1 0 ) 图8p a t h t r e e 数据类型定义 c a u t 自动测试目的在于生成测试用例用来更多地覆盖待测单元的路径。而部 分符号执行算法的思想就在于在探索被调用的函数时，不去探索它的所有路径， 而只生成某些用例，使得被调用的函数返回结果能足以覆盖到待测单元的路径。 以下例子用以详细说明这个算法。 一 e 一 一 s e 一 11 0i n ta b s ( i n tx ) 1 2 0 1 3 0f ( x l o ) 图4 示例：t e s t m e 被测单元 在图4 上例中，函数“t e s t _ m e 是