软件代码测试技术

北京邮电大学网络与交换技术国家重点实验室 北京 1000876

概述

软件测试技术可以从多种角度进行分类，如按开发阶段可分为单元测试、集成测试、系统测试、确认测试和验收测试，按是否需要程序执行可分为静态测试和动态测试，按是否需要源代码可分为白盒测试和黑盒测试，按程序运行特性可分为功能测试和性能测试，按功能测试类型可分为逻辑功能测试、安装卸载测试、易用性测试、兼容性测试、安全性测试、图形界面测试等，按性能测试类型可分为一般性能测试、压力测试、负载测试、稳定性测试，另外，还有回归测试、冒烟测试、随机测试等等。基于以上测试分类，对于白盒测试可根据是否需要程序运行进一步划分为静态白盒测试和动态白盒测试。

静态白盒测试主要包括缺陷检测技术、规则审查技术和质量度量技术。缺陷检测技术针对源代码中存在的一些潜在语法或语义错误进行检测，如对可能为空的指针进行解引用、对已分配的内存没有及时释放、使用未经过初始化的数据等问题，其难点在于需要准确地计算出复杂的执行语义，典型的工具有Klocwork的Klocwork Insight[1]、Coverity的Coverity Static Analysis[2]、Fortify的Static Code Analyzer[3]，GIMPEL SOFTWARE的PC-Lint[4]、北邮的DTS[5]、北航的QESAT[6]和北大的COBOT[7]；规则审查技术针对一些特定的开发规范进行检查，如版式规范、命名规范、书写规范等，该技术在语法层面上进行检测难度不大，典型工具有Parasoft的Jtest和C++test[8]、Rational的Software Analyzer[9]、MicroFocus公司DevPartner中的Source Code Review[10]功能、Telelogic公司Logiscope中的RuleChecker[11]功能和马里兰大学的FindBugs[12]；质量度量技术首先定义若干个度量元，通过度量元的组合形成质量标准，最后通过组合质量标准形成质量因素，该技术也是在语法层面展开的，典型的工具是Telelogic公司Logiscope中的Audit功能。

动态白盒测试主要包括单元技术、测试评估技术和运行监控技术。单元技术基于被测单元的代码及逻辑结构产生并执行测试用例，其难点在于如何对复杂结构及路径进行求解，典型的数据生成工具有斯坦福大学的KLEE[13]、贝尔实验室的DART[14]、伯克利大学的CUTE[15]和北邮最新研发的CTS[16]；测试评估技术针对程序结构的覆盖情况对测试充分度进行评估，如语句覆盖、分支覆盖、MC/DC覆盖、基本路径覆盖、定义/使用覆盖等，典型工具有Parasoft系列test工具的覆盖功能、MicroFocus公司DevPartner中的Code Coverage Analysis功能、Telelogic公司Logiscope中的TestChecker功能、IBM公司PurifyPlus[17]中的PureCoverage、北航QESAT中的覆盖统计功能、北邮CTS中的覆盖统计功能、深圳领测科技有限公司的VcTester[18]、广州凯乐软件技术有限公司的Visual Unit[19]；运行监控技术采用插桩或变异的方法对源程序进行一定的修改，在运行过程中收集并监控错误执行状态，典型的工具有Agitar公司的AgitarOne[20]、Parasoft公司的Insure++、IBM公司PurifyPlus下的Purify。

在以上基于代码的软件测试技术中，涉及复杂程序执行语义的缺陷检测技术和涉及复杂逻辑结构的单元测试技术具有相当的难度，目前得到国内外众多高校及科研机构的研究，本文就这两个方面的相关内容进行介绍。

1 缺陷检测技术

针对缺陷检测技术的研究，本文概括为如下四个部分：技术特点、技术架构、缺陷模式和关键技术。

1.1 技术特点

传统软件测试基于软件的某些性质，如功能、覆盖、性能等，这些测试虽然是必要的，但由于不是对软件中的缺陷直接测试，因此就检测缺陷的能力而言，基于代码的缺陷检测技术具有一定的优势，主要包括如下6点。

1) 覆盖范围广。传统方法要达到较高的测试覆盖范围，依赖于测试用例的数量及质量，这将带来大量的测试开销。而缺陷检测技术不需要执行程序，采用静态的方法覆盖程序结构及路径，这样可以覆盖到更多的问题。

2) 测试效率高。传统方法需要设计并执行大量测试用例，这个开销在整个测试过程中占有极大的比例。缺陷检测技术采用静态方法分析及计算，其效率相对于动态方法要高出许多。

3) 故障定位准。对于有些动态方法发现的问题，其根源可能来自于多种情况，对其进行准确的定位具有一定的困难。而静态方法在发现问题的同时，可以对相关信息进行准确的定位。

4) 小概率故障检测能力。对于某些小概率事件，依赖于执行测试用例的动态方法是很难覆盖到的，而通过分析程序结构得到路径的静态方法却相对容易实现，尽管有些复杂条件是很难计算的。

5) 非显性故障检测能力。对于某些没有明确现象的故障，如内存泄漏或无冲突的内容使用等，动态方法即使覆盖到了也难以发现。而静态方法却可以直接发现问题，尽管其可能没有直接的后果。

6) 测试人员要求低。传统测试方法要得到较好的效果，需要完成一定的测试设计及测试开发工作，甚至还需要熟悉系统业务流程，这对测试人员有着较高的要求。而面向故障的测试技术仅需要流程化的工具使用，对人员的要求较前者要低得多。

1.2 技术架构

缺陷检测技术架构可划分为输入、基础、计算、测试及分析5个部分，具体内容如图1所示。

图1 缺陷检测技术架构

1) 输入部分。测试文件指被测程序源代码或经过头文件展开、条件编译及宏替换等预处理后的中间代码；配置文件中包括为使系统正常或有效运行所提供的一些参数；模式文件中包含故障模式的相关描述及配置信息。

2) 基础部分。此部分针对输入的程序文件，构建出一些基础数据结构，在分析、计算及测试过程中使用。

3) 计算部分。采用静态方法计算出动态运行时的状态，包括计算不同类型对象在运行时的取值信息、分析过程中的可达及不可达路径、采用函数摘要替代被调函数完全展开等内容。

4) 测试部分。针对输入的配置文件及模式文件解析缺陷模式，构建相应状态机；针对输入文件中不同分析对象，创建状态机实例；基于基础数据结构运行状态机实例，并在其执行过程中发现故障。

5) 分析部分。基于检测到的缺陷及其相关信息，利用工具分析界面对测试结果的正确性进行分析，并将确认的结果导出。

1.3 缺陷模式

软件缺陷模式有很多，目前常用的就有数百种，本文将其归纳为故障、安全、疑问及规则4类模式。

1)故障模式。该类模式可能引起运行异常或错误，如被分配的内存在使用后没有正确释放、访问可能为空的指针内容、访问超过有效边界的数组内容、使用非法操作数进行运算、使用未经过正常初始化的数据、使用已经释放的指针内容等，该类缺陷被触发后将引起较为严重的后果，如异常退出或系统宕机，因此应尽量避免此类问题。

2) 安全模式。该类模式导致软件中存在安全隐患及漏洞，如对从外部获取的不安全数据未经验证即使用、对缓冲区的使用超过其规定的安全范围、使用了不安全的API函数、密码相关操作不安全等，该类模式对应的代码在正常操作下并没有问题，但对其异常操作却可能造成严重的后果，如拒绝服务或数据丢失，因此应谨慎对待此类问题。

3) 疑问模式。该类模式可能影响执行效率或导致逻辑错误，如循环中的低效操作、字符串的低效操作、冗余的对象方法、无意义的比较、相同的条件分支等，该类缺陷容易使人产生质疑，影响对程序真实意图的判断。

4) 规则模式。该类模式旨在统一编码规范，避免程序员的不良习惯造成的错误，如声明定义规则、版面书写规则、分支控制规则、运算处理规则、过程调用规则、语句使用规则等。

1.4 关键技术

在各类缺陷模式中，对疑问模式及规则模式的检测仅需要利用抽象语法树等基础数据结构，这类模式的检测精度相对较高。对故障模式及部分安全模式的检测需要程序执行语义信息，这就可能会遇到对某些特殊的情况，如对复杂的路径条件、过程间数据传播及对象表达式的分析及计算，由于缺少程序动态执行信息可能造成误报及漏报的情况。为了更好地提高缺陷检测精度，作者将相关技术总结如下。

1) 抽象解释。抽象解释技术用抽象对象域上的计算替代具体对象域上的计算，本质上是在计算效率和计算精度之间取得均衡。抽象域用于程序变量取值信息的近似表示，可分为关系型和非关系型两类：非关系型抽象域假设变量之间相互独立，如区间抽象域；关系型抽象域考虑变量之间的关联关系，如八边形抽象域、八面体抽象域和区间多面体域等。关系型抽象域相对于非关系型来说更精确，但其计算也相对复杂。

2) 路径分析。从路径抽象和近似的角度，静态分析方法可以划分为路径敏感和路径不敏感两种方法。路径不敏感方法不考虑程序控制流程中的不可达路径，会引入较多的误报，而完整路径分析又会产生无限状态空间。既能避免完整路径分析带来的组合爆炸，对给定缺陷来说又足够精确的路径分析方法，是提高准确性和实用性的重要手段。

3) 过程分析。精确的分析方法应包括过程内分析和过程间分析，过程间分析可以分为上下文敏感和上下文不敏感。最精确的上下文敏感方法是完整程序分析，但该方法无疑将要求大量的时间和内存开销，在大型程序的分析过程中无法实现。在复杂度和精度之间达到合适平衡的上下文敏感函数间分析方法，是提高静态缺陷检测准确性的重要内容。

4) 缺陷检测。若采用有限状态机来描述缺陷模式，缺陷检测基本过程可转化为一个传统的数据流问题。在分析过程中首先根据每类缺陷的不同状态机创建条件，创建一系列的缺陷状态机实例，然后沿着控制流计算各缺陷状态机实例在每个程序位置上的可能状态集合，如发现可能状态集合中包含错误状态即报告一个潜在的缺陷。

2 单元测试技术

针对单元测试技术的研究，本文概括为如下3个部分：技术架构、覆盖准则和关键技术。

2.1 技术架构

测试用例生成架构可划分为以下4个部分，具体内容如图2所示。

图2 单元测试技术架构

1) 程序预处理。对被测程序进行预处理，其目的是生成独立运行的被测单元，主要工作包括静态分析、单元划分、插装、打桩、重命名main函数、建立测试用例框架、建立测试结果框架等。

2) 测试用例生成。随机测试用例生成方法包括：基于区间运算结果、基于输入域划分、基于路径划分、基于边界值划分等；基于分支限界的测试用例生成方法包括：路径自动生成和基于分支限界的测试用例自动生成；人工辅助测试用例生成方法基于自动生成的部分结果，结合人工干预来实现用例的生成。

3) 测试执行、故障定位与结果分析。测试执行：可单步、连续执行被测单元的测试用例，执行结果生成结果矩阵；故障定位：一旦测试执行发现故障，可依据结果矩阵和启发算法对故障快速定位；测试效果分析：对覆盖率进行统计。

4) 结果呈现。软件性质显示：函数调用图、控制流图、软件代码性质(代码行、文件个数、函数个数、变量数、注析率、McCabe数等)；测试结果显示：反相显示被覆盖的代码、故障定位辅助支持显示、人工辅助测试用例生成、测试用例库显示。

2.2 覆盖准则

测试覆盖准则是指覆盖测试的标准，包括语句覆盖、分支覆盖、谓词覆盖、MC/DC覆盖、路径覆盖、定义使用覆盖等，不同的准则对应要测试的对象或程序元素不同。典型的几种覆盖准则如下。

1) 语句覆盖。语句覆盖测试是最简单的结构性测试方法之一。它要求在测试中，程序中的每条语句都得到执行。在控制流图中，要求所有语句都被运行的充分必要条件是覆盖图中的所有节点。

2) 分支覆盖。语句覆盖测试是最基本的覆盖测试技术，虽然它能保证所有语句都被执行，但并不能保证每条分支都被执行到；因此，分支测试要求程序中的每个取“真”分支和取“假”分支都至少经历一次。在控制流图中，分支表现为图中的一条有向边。

3) 谓词覆盖。一个分支的条件是由谓词组成的，单个谓词称为原子谓词，原子谓词通过逻辑运算符可以构成复合谓词。原子谓词覆盖要求每个原子谓词都至少获得一次“真”值和一次“假”值；分支—谓词覆盖不仅要求每个原子谓词都至少获得一次“真”值和一次“假”值，还要求每个复合谓词本身也至少获得一次“真”值和一次“假”值；复合谓词覆盖要求复合谓词中每个原子谓词的各种组合情况都至少出现一次。

4) 数据流覆盖。与控制流的覆盖思想不同，数据流覆盖面向程序中的变量。定义覆盖要求每个变量的定义至少被覆盖一次，引用覆盖要求每个变量的所有引用都至少被覆盖一次。考虑到回路中有无穷的引用情况，定义-引用覆盖为消除回路后的引用覆盖。

2.3 关键技术

在自动化单元测试中，主要涉及如下几个方面的技术。

1) 数据生成。数据生成可分解为4个部分。预处理部分：提供支持的部分，要面向任何类型的程序；回退部分：对一个表达式中的某个变量而言，选择合理的赋值使之能满足求解的需要；回溯部分：当发生矛盾时改变前面某个变量的赋值；加速部分：非数值类型变量处理的加速、复杂表达式处理的加速、等式处理的加速、小区间有限回退技术等。

2) 故障定位。通过分析计算各程序语句发生故障的可疑度得到定位结果。针对测试用例对应的执行路径集冗余问题，消除重复的执行路径以及与失败执行路径最不相似的成功执行路径，将约简后的执行路径集作为可疑空间，通过路径边元素的可疑度计算语句块可疑度，最终得到根据可疑度大小进行排序的语句块序列，实现对故障的自动定位。

3) 回归测试。单元回归测试的优化工作在于构造一个合理的测试用例集合，使得既能对软件修改所影响的范围进行充分测试，又能尽量避免冗余测试，排除与修改内容无关的测试用例。

3 工具应用

缺陷测试系统(DTS)由北京邮电大学、北京博天院信息技术有限公司联合研发，是国内第一套面向代码缺陷的测试工具。CTS是由北京邮电大学和北京博天院信息技术有限公司联合研发的一款面向C语言的单元覆盖测试工具。

3.1 测试Android4.0

Android4.0的代码由三个部分构成，其底层有5 919 784行C代码，中间层有6 158 454行C++代码，部分上层有5 336 619行Java代码。DTS累积测试时间为219小时，分析及确认的工作量为5人月。缺陷检测结果见表1，平均故障类缺陷密度为2/KLOC，平均安全类缺陷密度为9.6/KLOC，平均疑问类缺陷密度为20/KLOC，平均规则类缺陷密度为74.5/KLOC。

表1 Android4.0的缺陷检测结果

3.2 测试开源程序

对于开源程序的测试，从Sourceforge中选取排名靠前的20个工程，Java代码总计1 344 179行，C代码总计100 725行，C++代码总计111 918行。对其中故障类缺陷的分析结果见表2，平均故障密度为4.5/KLOC。

表2 对开源程序的缺陷检测结果

3.3 测试数据生成

对3个开源工程进行测试数据生成的测试，3个工程的属性如表3。

利用CTS分别对其进行语句覆盖、分支覆盖、MC/DC覆盖3种覆盖准则下的测试数据自动生成，测试结果如表4，工程aa200c中有77个被测单元，有40个单元能够达到100%覆盖，平均覆盖率在80%以上，完成三种覆盖准则的测试数据生成总用时为108分钟。工程qlib中有365个被测单元，平均有177个单元能够达到100%覆盖，平均覆盖率为68%，完成3种覆盖准则的测试数据生成总用时为444分钟。工程deco中有319个被测单元，平均有41个单元能够达到100%覆盖，平均覆盖率为38%，由于deco工程中存在大量的复杂数据类型(例如函数指针、字符串结构等)，所以有很多覆盖率为0的情况，导致平均覆盖率效果不如前两个工程，完成3种覆盖准则的测试数据生成总用时为484分钟。

表3 3个开源工程属性

表4 测试数据生成结果

3.4 国际工具对比

国际上典型的缺陷检测工具有Klocwork、Coverity、Fortify和Logiscope等，DTS与其对比结果分别见图3～图6。

针对表2中的20个开源工程，图3中为Klocwork的K9与DTS针对故障类缺陷的对比结果。图3中交集部分为双方共同检测出，最外侧部分为双方的误报，其余部分为比对方多报的缺陷。其中K9的准确率为73.9%，DTS的准确率为75.9%；K9的相对漏报率为59%，DTS的相对漏报率为11.6%。

图3 DTS与K9的对比结果

针对表2中的4个开源程序(Playa、dgvideo、spgateway、bwchess)和3个军工程序，图4中为Logiscope与DTS的所有缺陷类型对比结果。Logiscope的规则侧重于质量度量，分为建议类和强制类。DTS的1317个故障类缺陷Logiscope均没有覆盖，其它类型的缺陷与Logiscope的交集有5 407个，而Logiscope的45 055个建议类缺陷DTS也没有覆盖。

图4 DTS与Logiscope的对比结果

针对表2中的UUCP工程，图5中为Coverity与DTS针对故障类缺陷的对比结果。图5中各部分的含义与图3中一致。其中Coverity的准确率为80.72%，DTS的准确率为71.68%；Coverity的相对漏报率为90.7%，DTS的相对漏报率为6.24%。

图5 DTS与Coverity的对比结果

针对表2中的spell和barcode工程，图6中为Fortify与DTS的对比结果。双方共同测出内存泄漏和缓冲区溢出问题15个，而Fortify的269个安全缺陷DTS没有测出，而DTS的1491个其它缺陷Fortify没有测出。

图6 DTS与Fortify的对比结果

3.5 国内应用情况

自2006年以来，DTS在4个国家863项目及2个自然科学基金项目资助下完成，主要技术指标达到国际先进、国内领先的水平。基于相关研究成果，发表论文70余篇，申请专利30余项(授权10余项)，获得软件著作权登记17项。

DTS目前已经在全国发行近500多个试用版，在美国、日本、欧洲、香港、澳门有零星使用，在国内航天、航空、造船、银行、证券、电信、电力、交通、冶金等领域广泛应用，拥有50多个商用单位，成功应用于神舟、嫦娥及天宫等航空航天工程。

4 结束语

在基于代码的软件测试技术中，缺陷模式检测和测试数据生成是效率很高的测试方法，具有其它测试无法替代的地位。随着此技术的逐步成熟，相应测试工具必然会在市场上广泛流行。

在美国，面向缺陷模式的测试服务是软件测试市场的主流方向之一。在我国，该技术的研究及应用虽然刚刚起步，但已收到了很好的效果。在单元测试方面已经得到广泛应用，但对复杂结构对象、循环结构和函数调用的处理仍存在较大的困难，这将是未来几年的研究趋势。

参考文献

[1]Domain Market.com[EB/OL].[2015-04-20].http://www.klocwork.com

[2]Code Advisor on Demand[EB/OL].[2015-04-20].http://www.coverity.com

[3]Application Security[EB/OL].[2015-04-20].http://www.fortify.com

[4]Gimpel Software[EB/OL].[2015-04-20].http://www.gimpel.com

[5]北京博天院信息技术有限公司[EB/OL].[2015-04-20].http://www.dtstesting.com

[6]中国测试平台[EB/OL].[2015-04-20].http://www.chinatesting.cn/331/12585331.shtml

[7]库博[EB/OL].[2015-04-20].http://cobot.net.cn

[8]PARASOFT[EB/OL].[2015-04-20].http://www.parasoft.com

[9]Rational Software Analyzer Developer Edition[EB/OL].[2015-04-20].http://www-03.ibm.com/software/products/zh/rsade

[10]Software Testing[EB/OL].[2015-04-20].http://www.borland.com/Products/Software-Testing

[11]Elelogic Logiscope[EB/OL].[2015-04-20].ftp://public.dhe.ibm.com/software/rationalsdp/documentation/archive/Logiscope/version_6-5/ReviewerJava.pdf

[12]FindBugs[EB/OL].[2015-04-20].http://sourceforge.net/projects/f i ndbugs/

[13]Cadar C,Dunbar D,Engler D.KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs[C]//USENIX Symposium on Operating Systems Design and Implementation(OSDI 2008),San Diego,CA,USA,2008

[14]Koushik S,Darko M,Gul A.CUTE:a concolic unit testing engine for C[C]//The 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering,2005:263-272

[15]Godefroid P,Klarlund P,Sen P.DART:directed automated random testing[C]//The 2005 ACM SIGPLAN conference on Programming language design and implementation(PLDI),2005:213-223

[16]唐容.支持非数值型测试用例自动生成的抽象内存建模技术研究[D].北京邮电大学,2013

[17]使用IBM Rational PurifyPlus[EB/OL].[2015-04-20].http://www.ibm.com/developerworks/cn/rational/07/0306_chitale/

[18]经典的单元测试工具VcTester介绍[EB/OL].[2015-04-20].http://www.ltesting.net/html/30/n-161730.html

[19]凯乐软件[EB/OL].[2015-04-20].http://www.kailesoft.com

[20]Agitar Technologies[EB/OL].[2015-04-20].http://www.agitar.com/solutions/products/agitarone.html