二叉树结构型测试数据生成方法研究

论文摘要

软件测试是软件工程学科的重要组成部分,在实际的软件开发过程中,软件测试所发挥的重要作用已得到软件开发人员的广泛认同。软件测试以发现软件中潜藏的缺陷和错误为目的,确保软件的可靠性和提高软件的质量。测试数据自动生成是软件测试中的一个重要环节,目前关于测试数据生成的研究主要集中于数值和字符串类型的数据,对于指针和动态数据结构类型的测试数据生成研究较少。而且,现有的解决动态数据结构类型输入数据的测试生成方法大多采用静态方法,这对于复杂动态数据结构的测试数据生成实现困难,并且测试生成效率较低。二叉树是一种广泛使用并且具有代表性的动态数据结构,为此,本课题针对二叉树结构,以路径覆盖为测试准则,提出了一种基于concolic的二叉树结构型测试数据自动生成方法,使用遗传搜索算法生成二叉树结构的形态,并利用约束求解确定其数据域的值。针对二叉树结构型测试数据的特点,设计了一种新的染色体编码方式,用以表示二叉树结构的形态,探讨了适用于二叉树结构的交叉操作和变异操作。同时,通过约束解决技术求解其数据域的值,实现面向路径的二叉树结构型测试数据自动生成方法。为验证本课题提出的二叉树结构型测试数据自动生成方法的可行性,选取二叉树操作程序进行大量实验。实验结果表明,基于遗传算法的二叉树形态测试生成方法是行之有效的,不仅能够实现以二叉树结构类型为输入的面向路径的测试数据自动生成,而且其测试生成效果明显优于随机生成方法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 本文的研究背景与意义
• 1.2 国内外软件测试数据生成研究现状
• 1.3 本文的主要工作及创新点
• 1.4 本文的组织结构
• 第二章 软件测试数据生成方法概述
• 2.1 不同类型的测试数据生成方法概述
• 2.1.1 数值型测试数据生成方法
• 2.1.2 字符串型测试数据生成方法
• 2.1.3 动态数据结构型测试数据生成方法
• 2.2 基于不同启发式搜索算法的测试数据生成方法概述
• 2.2.1 遗传算法
• 2.2.2 蚁群算法
• 2.2.3 模拟退火算法
• 2.2.4 禁忌搜索算法
• 2.3 基于不同测试准则的测试数据生成方法概述
• 2.3.1 面向单目标的测试数据生成
• 2.3.2 面向多目标的测试数据生成
• 2.3.3 面向单路径的测试数据生成
• 2.3.4 面向多路径的测试数据生成方法
• 第三章 一种面向路径的二叉树结构型测试数据自动生成方法研究
• 3.1 二叉树结构型测试数据的特点
• 3.2 面向路径的二叉树结构型测试数据生成方法框架
• 3.3 一种基于遗传算法的二叉树形态生成方法研究
• 3.3.1 二叉树形态的编码设计
• 3.3.2 初始种群二叉树形态的生成
• 3.3.3 适应度函数的构造
• 3.3.4 选择操作的设计
• 3.3.5 交叉操作的设计
• 3.3.6 变异操作的设计
• 3.3.7 个体的评估过程
• 3.4 二叉树数据域值的生成方法
• 第四章 实验及结果分析
• 4.1 面向路径的二叉树结构型测试数据自动生成实验设计
• 4.1.1 被测源程序和路径的选择
• 4.1.2 遗传算法参数的设定
• 4.1.3 实验设计
• 4.2 实验结果及分析
• 4.3 影响测试生成效率的因素分析
• 第五章 结论与展望
• 5.1 本文的结论
• 5.2 进一步的工作
• 参考文献
• 附录
• 致谢
• 研究成果及发表的学术论文
• 作者和导师简介
• 附件