并行程序路径覆盖测试数据的协同进化生成方法

作     者：王子鸣 

作者单位：中国矿业大学 

学位级别：硕士

导师姓名：巩敦卫

授予年度：2018年

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

主      题：并行程序 路径覆盖 测试数据生成 协同进化 遗传算法 

摘      要：随着近年来并行程序的广泛应用,并行程序的测试问题也逐渐被人们重视。其中,消息传递并行程序是一种常用的并行程序,这类程序的路径覆盖测试数据生成问题可以通过遗传算法进行求解。但是,传统方法没有充分利用并行程序调度序列提供的知识,导致算法效率难以满足需求。因此,改进并行程序的测试方法是十分必要的。针对这类问题,本文提出一种测试数据协同进化生成方法,并开发了相应原型系统,提高了测试效率。本文主要有以下内容:(1)提出了一种并行程序路径覆盖测试数据协同进化生成方法。首先,根据调度序列生成对应的种群;然后,给出种群与个体的性能评价方法;最后,依据种群与个体性能,在进化过程中执行个体迁移、种群消亡、种群合并等操作,生成测试数据。该方法与传统遗传算法相比,不但没有引入对调度序列人工分析等额外人工干预,提高了测试自动化程度,而且在生成测试数据的过程中使用多个调度序列,通过评价各调度序列生成测试数据的难易程度得到对应种群的性能,进化过程中将资源更多地分配给性能较好的种群,提高了算法效率。(2)开发了并行程序路径覆盖测试数据生成原型系统。该原型系统包括程序处理、进化求解和结果处理等3个模块,用于对程序执行前的预处理、使用所提方法进行进化求解,以及结果保存和输出等。进化求解模块是该原型系统的主要部分,使用C语言编写,主要包种群定义、种群初始化,以及种群迁移、种群消亡、种群合并、种群规模计算、适应值计算、编码、解码、选择、交叉、变异等函数。利用该原型系统能够针对不同程序使用本文所提方法自动高效生成测试数据,提高了测试效率。本文所提方法能够针对并行程序高效生成测试数据,对软件测试的发展做出了积极的贡献。