计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2011年第06期杂志 文档列表

《软件测试》专辑前言951-952

摘要：近年来，随着计算机技术的进步，以软件系统为核心的计算机应用已经渗透到各行各业，在国民经济、国防领域以及人们的日常生活中发挥着越来越重要的作用．因此，当今社会对高质量软件的需求也越来越迫切．但是，随着软件规模的不断增长，软件质量问题逐渐成为制约计算机发展和应用的瓶颈之一．

一种目标制导的混合执行测试方法953-964

摘要：混合执行测试（concolic testing）是一种将具体执行与符号执行相结合的自动化测试方法．由于混合执行测试从程序本身出发，未将目标缺陷的先验知识作为指导，会导致生成和执行大量不能发现缺陷的测试输入，从发现缺陷的角度看浪费了时间和计算资源开销．这个问题在具有时间、成本及资源约束的实际测试任务中更加突出．为解决这一问题，文中提出了一种结合静态分析和混合执行测试技术的目标制导的混合执行测试方法：使用静态分析工具分析待测程序中可能含有缺陷的可疑语句及其缺陷类型，并将静态分析所报告的可疑语句作为目标指导测试．目标制导的混合执行测试技术分为3个步骤：首先，计算从程序各分支到待检测缺陷语句的可达性；其次，对待测试程序进行插装以支持混合执行测试；第三，使用静态分析的结果和可达性信息作为指导，只生成和执行可能会覆盖待检测缺陷语句的测试输入，以避免生成和执行不能发现缺陷的测试输入．基于此方法，作者实现了一个测试缓冲区溢出缺陷的原型工具：TARGET，并在一组C语言基准程序上进行了对比实验．实验结果表明与原有的混合执行测试技术相比较，TARGET能在更短的时间内发现程序中更多的缺陷．

基于FSM的测试理论、方法及评估965-984

摘要：为搭建基于FSM的测试方法由理论研究通往工业应用的桥梁，文中讨论了若干基于FSM模型的测试方法及其相关理论，提出构造区分序列的理论及测试序列集合冗余约简的理论，补充并实现了若干基于FSM的测试生成算法．随后文中提出了基于FSM的测试方法评估的5项量化指标，实验评估了若干基于FSM模型的测试方法，给出了一些基于FSM测试的经验建议．文中的评估有助于基于FSM的测试方法在工业中的推广．

基于模型的网构软件可达性检测方法研究1001-1011

摘要：针对网构软件（Internetware）可达性检测中存在状态空间“爆炸”等问题，提出了一种基于网构软件代数模型的可达性检测方法．根据网构软件特性建立其代数模型，通过引入网构相关和网构空间概念，进一步扩展网构软件代数模型．通过明确网构软件可达性与网构组合运算表达式的关系，把可达性判定转化成递归表达式（网构线性相关）判定上来；通过建立网构空间到线性空间映射，把网构线性相关判定问题转化成齐次线性方程组非零解的判定上来．转换过程把线性相关的网构进行压缩，从而有效地抑制了状态空间的增长．给出了可达性检测算法，并讨论了该方法的实际应用．

基于模型的Web应用测试1012-1028

摘要：提出了基于模型的Web应用测试方法，包括建模、测试用例生成、测试用例的执行、模型以及测试用例的可视化等关键技术．设计并实现一个基于模型的Web应用测试系统．以FSM作为被测web应用的形式测试模型，集成了模型转换器、测试目标分析器、测试序列生成器、FSM和测试序列可视化以及Web应用测试执行引擎等工具．除支持状态覆盖、迁移覆盖、迁移对覆盖等传统的覆盖准则外，还改进／提出了优化状态迁移覆盖、完整消息传递覆盖、完整功能交互覆盖和功能循环交互覆盖等覆盖准则．该文以兴宁水库移民信息管理系统为例演示了该系统．

用户需求驱动的Web服务测试1029-1040

摘要：Web服务涉及开发者、提供者、注册中心、用户等多方，各方测试目的、所掌握的资源以及所使用的测试方法各异．以用户需求来驱动Web服务测试，更切合现状且能提升测试效率．文中建立了用户需求特征模型，引入层次关系、控制结构、约束条件等要素；对照目标级、服务组合、原子服务需求，分别进行基于等价类划分、数据流分析和变异测试的测试用例生成选择；当需求变动时，通过波动分析能迅速定位到服务的相关路径和变量，保证回归测试的效率；最后通过行程安排实例展示了工作流程和实验结果．

一种基于认知模型检测的Web服务组合验证方法1041-1061

摘要：近几年Web服务组合的形式化验证逐渐成为研究热点．模型检测作为形式化验证的一种主流技术，可以克服传统软件测试用例生成不完备的不足，同时具有验证自动化的优点．该文提出并实现了一种Web服务组合的认知模型检测方法，将Web服务组合建模为多主体系统，在分析BPEL语言控制流程基础上，提出BPEL活动的形式化模型，给出活动执行语义．进而以迁移七元组为中间形式，开发从BPEL流程到迁移七元组集合以及从这些迁移七元组到MCTK（一种我们开发的多主体系统模型检测工具）输入语言的自动转换算法，最终通过MCTK进行验证．实验结果表明开发的算法不仅可以有效验证Web服务组合的时态逻辑规范，而且可以验证多主体系统特有的认知逻辑规范及其时态组合．

一种基于耦合度量的类间集成测试序的确定方法1062-1074

摘要：类间测试顺序的确定是类集成测试中难以解决的一个关键问题．类的测试序列不同，构造相应的测试桩需要花费的代价也会不同．每一个测试桩复杂度度量的准确性决定最终打破环路所需构造测试桩的总体复杂度．对于类间测试顺序问题，文章提出一种基于耦合度量的类间集成测试序的确定方法．采用类间耦合度量与基于图的启发式算法相结合的方法，其中，前者用于度量每一个测试桩的复杂度，后者用于在保证测试桩总体复杂度尽可能小的条件下来打破环路．首先提出一种在度量中使用的耦合权重的计算方法，对测试桩的复杂度进行新的耦合度量；然后给出一种有效打破环路的基于图的启发式算法；最后实现了类间测试序列自动生成工具——TOGOS．实验结果表明：文中的方法较现有的方法总体复杂度有明显的降低，从而节约了测试成本．

一种基于动态依赖关系的类集成测试方法1075-1089

摘要：类间集成测试是面向对象软件测试的重要组成部分，合适的测试顺序能够极大地节省测试成本．类间依赖关系构成环路的情况下，需要删除某些依赖关系以消除环路，同时需要引进测试桩．忽略类间动态依赖关系导致测试桩的数目不足，难以完成测试．文中提出一种基于动态依赖关系的类集成测试方法．首先分析了类之间的静态依赖和动态依赖关系；然后在保证测试桩的数目尽可能少的前提下，给出了边的删除规则以及消除由静态依赖关系和动态依赖关系形成的环路的算法，在此基础上，进一步提出测试顺序分配策略和算法；最后针对提出的方法开发了基于测试级的类测试序列自动生成工具——TLOG．实验结果表明：该方法较其它方法需要较少的测试桩，测试效率有明显提高．

运行时异常对软件静态测试的影响研究1090-1099

摘要：当程序的执行过程中出现运行时异常，控制流动态地变更可能会产生非预期的执行逻辑，由此引入的缺陷将给软件静态测试工作带来巨大的挑战．针对这一问题，提出一种结合运行时异常的静态测试方法，将缺陷检测及控制流扩展交替执行，通过扩展分析路径达到提高测试充分度的目的．以异常模式状态机描述运行时异常行为，在包含运行时异常的控制流上，应用迭代方程得到运行时异常控制流序列，将在传统控制流上的一次缺陷检测过程扩展为在异常控制流序列上的多次检测．实验结果表明，结合运行时异常的静态测试方法虽然增加了时间开销，且引入一定的误报，但却可以发现传统测试方法所遗漏的缺陷，这点在航空、航天等高可信领域尤为重要．

提高路径敏感缺陷检测方法的效率及精度研究1100-1113

摘要：路径敏感的缺陷检测方法其缺陷状态会关联当前控制流节点的所有数据流信息，由于其中包含与缺陷检测无关的数据流，因此会导致分析效率下降．为了避免全路径敏感分析时的路径爆炸问题，一般会在控制流汇合节点进行缺陷状态合并，而这种粗糙的合并策略带来的精度损失会引起误报．针对上述问题，文中提出一种基于缺陷的程序切片方法，该方法基于缺陷特征和路径条件建立切片准则，根据控制流节点上的数据流信息与切片准则的包含关系进行程序切片，得到的切片程序在缺陷检测时切片掉了缺陷无关节点且与源程序完全等价，以提高缺陷检测效率．为了进一步减少路径敏感分析方法的误报，提出一种基于切片的缺陷状态合并策略，根据控制流分支节点的路径条件，对缺陷状态添加状态属性，从而有选择地对控制流汇合节点进行状态合并，减少精度损失．文中所述方法已在缺陷检测系统（DTSGCC）中实现．对大量Linux中GCC开源工程的测试结果表明，文中提出的方法可以提高路径敏感缺陷检测方法的效率，并减少误报．

一个可半自动化扩展的静态代码缺陷分析工具1114-1125

摘要：基于缺陷模式的代码缺陷分析技术根据预先设定的缺陷模式知识对受检代码进行缺陷分析．这种分析技术具有使用简单、查找速度快等优点，是近年来静态代码缺陷分析方法中发展比较迅速的新技术．但是目前基于这种分析技术的大多数工具并没有为用户提供足够易用、高效的扩展方式以扩充其缺陷检测能力．针对这一问题，作者提出了一个“可半自动化扩展”的代码缺陷静态分析方法，设计并实现了一个支持该方法的工具——CODA（COde Defect Analysis tool）. CODA不仅提供了“缺陷模式描述模板”以帮助用户快速地手工扩充缺陷模式库，还能在用户的指导下半自动化地挖掘新缺陷模式以快速扩充其缺陷模式库．一旦新的缺陷模式被定义并添加至缺陷模式库中，CODA便能自动具有针对该类缺陷的检测能力．

基于部分覆盖表的错误交互定位方法1126-1136

摘要：在组合测试定位模型的基础上提出了部分覆盖表的错误交互定位方法，该方法在错误交互个数已知的条件下，通过生成部分覆盖表，利用测试用例运行结果提供的信息来对软件错误交互定位．从理论上证明了部分覆盖表等价于一类特殊的错误定位表，进而研究了部分覆盖表行数的上界，提出生成部分覆盖表的贪心算法，从而给出了定位引发软件故障的错误交互的非自适应算法，并通过实验验证了该方法的有效性．

复杂软件的级联故障建模1137-1147

摘要：软件复杂性的增加直接导致软件故障的复杂性增加．从系统科学的角度出发，采用复杂网络等方法和技术在整体上研究复杂软件的级联故障特性是研究软件质量的一个新视角．以函数为节点、以调用关系为边，提出了使用有向边和边权表述函数间的调用关系和紧密程度的拓扑模型．通过引入函数容错能力和软件故障强度建立复杂软件的级联故障模型，模拟软件运行时的故障传播行为．对3个实际软件网络的实验结果表明，弱的故障强度、少的初始故障节点和高的容错能力均会减缓故障的传播速度和缩小故障的波及范围．分析了部分软件节点最终未被感染的原因，文中模型有助于为软件工程人员准确检测复杂软件的复杂性和容错性提供新的思路．

基于ACO—SVM的软件缺陷预测模型的研究1148-1154

摘要：针对传统软件缺陷预测模型的应用范围通常被局限在一定的子空间而影响其适用性和准确性的问题，文中利用支持向量机（SVM）的非线性运算能力和蚁群优化算法（ACO）的寻优能力提出了一种基于ACO—SVM的软件缺陷预测模型．文中首先对待预测的数据进行主成分分析降低数据的维数以提高运算速度，然后根据蚁群优化算法来计算最优的SVM参数，然后再运用SVM进行软件缺陷的预测．并基于十折交叉方法进行实验，通过与传统方法的对比，证明文中方法具有较高的预测精度．