学位论文 > 优秀研究生学位论文题录展示

面向路径的测试数据自动生成方法研究

作　者: 单锦辉
导　师: 齐治昌
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 测试数据自动生成面向路径的测试软件测试数据流分析程序切片白盒测试黑盒测试
分类号: TP311.53
类　型: 博士论文
年　份: 2002年
下　载: 1184次
引　用: 38次
阅　读: 论文下载

内容摘要

软件测试是现阶段保障软件质量的重要手段。软件测试中的诸如语句覆盖、路径覆盖等问题可以归结为面向路径的测试数据的生成问题。该问题在本文中简称为问题2，可以描述为：给定一个程序P和P中一条路径W，设P的输入空间为D，求(?)∈D，使得P以(?)为输入运行，所经过的路径为W。自动求解该问题将有效地提高软件测试的效率和质量。求解问题2的实质在于约束系统的建立和求解。建立约束系统的困难是分析、化简路径W上的各种语句成分和各种数据类型，建立尽可能简洁的约束系统；求解约束系统的主要困难是处理可能存在的非线性约束。Matiyasevic和E.J.Weyuker等人的研究表明：不存在通用的有效的算法，对于任意的P和W，能生成使W被经过的输入数据。但是实际应用的需要迫使人们进行研究，并提出各种方法求解问题2。本文首先简要介绍该领域的研究进展，将现有的求解方法分为四类——随机法、静态法、动态法和试探法，介绍和分析每一类中有代表性的方法，并探讨研究方向。迭代松弛法是Neelam Gupta等人提出的一种自动求解问题2的方法。该方法通过分析W上各语句之间的静态、动态数据依赖关系，构造谓词片和输入依赖集，用线性算术表示对谓词函数进行线性化，仅能够用于白盒测试数据的自动生成。 Neelam Gupta等人将最小二乘解法用于求解问题2。Jon Edvardsson等人指出，对于谓词函数均为输入变量的线性函数的程序路径，Neelam Gupta等人提出的求解方法是不完备的和非终止的，并建议采用线性规划、线性(混合)整数规划方法。本文改进迭代松弛法，省略构造谓词片和输入依赖集的过程。更进一步，当用均差作为谓词函数关于输入变量的导数的近似时，计算线性算术表示就全部转化为计算谓词残量，而后者无须分析W上各语句之间的静态、动态数据依赖关系。此时，改进后的方法比原方法生成测试数据的能力更强，能够用于黑盒测试数据的自动生成。改进后的方法建立线性约束系统的效率更高。本文给出一种模型语言；给出一个比较完整的形式化描述，该描述可用于证明与静态、动态数据依赖关系有关的程序性质；给出迭代松弛法中各概念的形式化定义；深入研究迭代松弛法及其改进后的方法的程序理论，其结果包括：将Neelam Gupta等人提出的谓词片推广为路径静态切片，证明路径静态切片构造算法的正确性，证明改进后的方法与原方法所生成的线性约束系统相同。本文提出一个面向路径的测试数据生成框架。该框架以改进后的迭代松弛法为核心算法，对于谓词函数均为输入变量的线性函数的程序路径，采用基于线性规划、线性(混合)整数规划的约束求解器；对于谓词函数中含有输入变量的非线性函数的程序路径，采用线性规划、线性(混合)整数规划和最小二乘解法相结合的约束求解器。它具有以下国防科学技术大学研究生院学位论文性质：若W上各谓词函数均为输入变量的线性函数，并且所有输入变量均无整数限制；则框架迭代一次后，或者找到W的解，或者保证w不可行；当谓词函数中含有输入变量的非线性函数时，可能需要迭代多次。本文开发了面向路径的测试数据生成框架的一个原型工具。用实际的程序路径对该工具进行实验。初步的实验结果表明框架是比较有效的，不仅能够用于白盒、黑盒测试数据的自动生成，而且能够用于面向断言的测试数据自动生成和回归测试数据的自动生成。

全文目录

插图目录  6-7
表格目录  7-8
中文摘要  8-10
英文摘要  10-12
第一章绪论  12-26
  §1．1 立题背景  12-20
    §1．1．1 软件生存周期  12-14
    §1．1．2 保障软件质量的技术手段  14-16
    §1．1．3 软件测试的技术和过程  16-18
    §1．1．4 持续的软件测试与软件可测试性  18-19
    §1．1．5 软件测试的充分性准则  19-20
  §1．2 问题2的提出  20-21
  §1．3 存在的问题  21-24
  §1．4 本文的目标与主要工作  24-25
  §1．5 论文结构  25-26
第二章面向路径的测试数据自动生成方法述评  26-34
  §2．1 随机法  26-27
  §2．2 静态法  27-28
    §2．2．1 符号执行  27
    §2．2．2 区间算术法  27-28
  §2．3 动态法  28-30
    §2．3．1 直线式程序法  28-29
    §2．3．2 BogdanKorel提出的方法  29
    §2．3．3 M．Gallagher等人提出的方法  29-30
    §2．3．4 迭代松弛法  30
  §2．4 试探法  30-31
    §2．4．1 遗传算法  31
    §2．4．2 模拟退火  31
  §2．5 小结  31-34
第三章迭代松弛法及其改进  34-47
  §3．1 迭代松弛法  34-39
    §3．1．1 迭代松弛法简介  34-37
    §3．1．2 迭代松弛法的算法描述  37
    §3．1．3 迭代松弛法的讨论  37-39
  §3．2 迭代松弛法的改进  39-41
    §3．2．1 改进后的迭代松弛法的讨论  40-41
  §3．3 实例  41-46
  §3．4 小结  46-47
第四章改进后的迭代松弛法与原方法线性约束等价性证明  47-57
  §4．1 模型语言L  47-48
  §4．2 L的操作语义  48-50
  §4．3 构造路径静态切片  50-51
  §4．4 线性化谓词函数  51-55
    §4．4．1 输入依赖集的构造  51-52
    §4．4．2 线性算术表示的构造  52-54
    §4．4．3 线性约束的构造  54-55
  §4．5 迭代松弛法及其改进后的方法构造线性约束系统的时空效率分析  55
  §4．6 小结  55-57
第五章面向路径的测试数据生成框架及应用  57-62
  §5．1 面向路径的测试数据生成框架  57-58
  §5．2 面向路径的测试数据生成框架的应用  58-61
    §5．2．1 单元测试  59
    §5．2．2 组装测试  59-61
  §5．3 小结  61-62
第六章系统原型（简称PTDG）开发  62-70
  §6．1 UML和Tcl／Tk简介  62-63
    §6．1．1 UML简介  62
    §6．1．2 Tcl／Tk简介  62-63
  §6．2 PTDG的分析  63-64
  §6．3 PTDG的设计  64-67
    §6．3．1 用例图的设计  64
    §6．3．2 顺序图的设计  64-66
    §6．3．3 类图的设计  66
    §6．3．4 图形用户界面的设计  66-67
  §6．4 PTDG的实现  67-69
    §6．4．1 词法分析器、语法分析器的实现  67
    §6．4．2 约束求解器的实现  67-68
    §6．4．3 图形用户界面的实现  68-69
  §6．5 小结  69-70
第七章实验  70-77
  §7．1 线性约束的程序路径  70-71
  §7．2 非线性约束的程序路径  71-72
  §7．3 面向断言和回归测试的测试数据的自动生成  72-75
  §7．4 小结  75-77
第八章结束语  77-79
  §8．1 本文主要贡献  77-78
  §8．2 今后研究工作  78
  §8．3 小结  78-79
攻读博士学位期间已录用发表的论文和撰写的技术报告  79-80
致谢  80-81
参考文献  81-88
附录A 部分性质、引理、定理证明  88-96

相似论文

面向对象分层测试的方法研究,TP311.53
基于形式化UML测试序列生成方法研究,TP311.53
基于程序切片的电子海图系统软件测试技术研究,TP311.53
用户权限管理系统可靠性测试的研究与应用,TP311.53
高职院校教学案例库的创建探究,TP311.53-4
基于中国电信闪铃系统与平台项目的软件测试,TP311.53
表面形貌区域法分析评定算法及软件系统研究,TP311.52
基于Process Engine的Web Services自动化测试研究,TP311.52
自动化测试在分组传输网管接口测试中的应用,TP311.52
一个自动化软件测试系统的设计与实现,TP311.53
基于QTP的SAFFRON自动化测试框架的研究,TP311.52
电信BOSS系统软件测试,TP311.53
基于程序执行的错误定位方法,TP311.52
基于云计算的软件测试服务研究,TP311.53
电子商务中的在线书店设计与实现,TP311.52
A基地软件检测站测试管理信息系统设计及实施关键问题研究,TP311.52
智能卡操作系统(COS)的系统测试方法的设计与实现,TP311.52
基于J2EE的软件测试用例管理系统的设计与实现,TP311.52
地图管理信息系统的设计与实现,P208
PTN网管的接口自动化测试研究与实施,TP274
基于Robot技术的GUI自动化测试系统的设计与实现,TP274