基于路径相似度的并行程序多路径覆盖调度序列排序  

Path similarity-based scheduling sequence sorting for multi-path coverage of parallel programs

作　　者：潘峰 巩敦卫 田甜[2] 姚香娟 李吟[4] Feng PAN;Dunwei GONG;Tian TIAN;Xiangjuan YAO;Yin LI(School of Inform ation and Control Engineering,China University of Mining and Technology,Xuzhou 221116,China;School of Com puter Science and Technology,Shandong Jianzhu University,Jinan 251100,China;School of Mathem atics,China University of Mining and Technology,Xuzhou 221116,China;Jiangsu Automation Research Institute,Lianyungang 222061,China)

机构地区：[1]中国矿业大学信息与控制工程学院,徐州221116 [2]山东建筑大学计算机科学与技术学院,济南251100 [3]中国矿业大学数学学院,徐州221116 [4]江苏自动化研究所,连云港222061

出　　处：《中国科学：信息科学》2021年第4期565-581,共17页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61773384,61573362,61503220);国家重点研发计划(批准号:2018YFB1003802-01)资助项目。

摘　　要：测试是提高软件可靠性的重要方法.消息传递并行程序中存在的不确定通信语句,使得进程执行顺序具有不确定性,这增加了测试该类程序的难度.鉴于进程执行顺序对目标路径覆盖难易程度的影响,本文研究消息传递并行程序多路径覆盖调度序列排序方法,以提高多路径覆盖测试数据生成的效率.首先,在每个调度序列下,以每个采样的程序输入执行程序,生成路径覆盖矩阵;然后,针对每条目标路径,分别计算与路径覆盖矩阵中每条路径的相似度,生成多个路径相似度矩阵;接着,基于这些路径相似度矩阵的特征量,评价调度序列的性能,并依此对调度序列排序;最后,基于调度序列排序集,使用随机采样法,生成覆盖所有目标路径的测试数据,并使用缺陷检测平均百分比(average percentage of faults detected,APFD)指标评估调度序列排序集.将所提方法应用于9个基准并行程序中,并与随机方法和传统方法进行比较.实验结果表明,所提方法对路径覆盖率没有影响,但显著减少了被测程序执行次数和运行时间.Testing is an important way of improving the reliability of a software product. Uncertain communication statements in the message-passing parallel program can lead to uncertainty in the order of the execution of processes, which increases the difficulty of testing. Taking into consideration the influence of an uncertain process-execution order on the difficulty of covering target paths, in this paper, we focus on a method for sorting scheduling sequences in a message-passing parallel program to enable multi-path coverage and improve the efficiency of generating test data for multi-path coverage. To fulfill this task, we first execute a parallel program on each sample in each scheduling sequence to generate a path coverage matrix. Then, we produce a number of path similarity matrixes based on the similarity of each path in the coverage matrix and for each target. Next,we evaluate each scheduling sequence with respect to the characteristics of the similarity matrixes, based on which we sort the scheduling sequences. Finally, we generate test data for multi-path coverage by performing a random sampling of the sorted scheduling sequence set, which are evaluated using the APFD index. We applied the proposed method to nine benchmark parallel programs, and compared the performances of the random and traditional methods. The experimental results indicate that the proposed method has no effect on path coverage,but significantly reduces the number of program executions during the test and running time.

关 键 词：消息传递并行程序 多路径覆盖 测试 调度序列排序 路径相似度 

分 类 号：TP311.53[自动化与计算机技术—计算机软件与理论]