计算机科学 ›› 2020, Vol. 47 ›› Issue (9): 40-46.doi: 10.11896/jsjkx.200700021

• 计算机软件* 上一篇    下一篇

基于支配关系的数据流测试用例生成方法

吉顺慧, 张鹏程   

  1. 河海大学计算机与信息学院 南京211100
  • 收稿日期:2020-07-03 发布日期:2020-09-10
  • 通讯作者: 吉顺慧(shunhuiji@hhu.edu.cn)
  • 基金资助:
    国家自然科学基金(61702159);江苏省自然科学基金(BK20170893)

Test Case Generation Approach for Data Flow Based on Dominance Relations

JI Shun-hui, ZHANG Peng-cheng   

  1. College of Computer and Information,Hohai University,Nanjing 211100,China
  • Received:2020-07-03 Published:2020-09-10
  • About author:JI Shun-hui,born in 1987,Ph.D,lectu-rer,is a member of China Computer Federation. Her main research interests include software modeling,analysis,testing and verification.
  • Supported by:
    National Natural Science Foundation of China (61702159) and Natural Science Foundation of Jiangsu Province (BK20170893).

摘要: 程序控制流的设计是为实现正确的数据流服务的,数据流测试是非常重要的。文中将面向all-uses数据流准则的测试用例生成问题建模为多目标优化问题,提出了一种基于遗传算法的测试用例生成方法。通过构建待测程序的控制流图进行数据流分析,计算出程序中所有的定义-使用对,得到测试目标,利用面向多测试目标的遗传算法生成满足all-uses准则的最优解。遗传算法中定义了一种改进的基于支配关系的适应度函数,在分析测试用例对定义-使用对的覆盖程度时考虑了存在重定义的可能性,且考虑了定义结点和使用结点在执行路径中的先后顺序。实验结果表明,所提方法可以有效地生成满足all-uses准则的测试用例,相比其他方法可以有效地提升测试目标的覆盖率,降低生成测试用例所需的迭代次数。

关键词: 测试用例生成, 适应度函数, 数据流测试, 遗传算法, 支配结点

Abstract: The design of control flow in programs serves for realizing correct data flow. Performing the data flow testing is important. With formulating the problem of all-uses data flow criterion oriented test case generation as a many-objectives optimization problem,a genetic algorithm based test case generation approach is proposed. By constructing the control flow graph for to-be-tested program,data flow analysis is performed to compute all the definition-use pairs which are the testing requirements. Then many-objectives oriented genetic algorithm is performed to search the optimal solution for satisfying all-uses criterion. An improved fitness function is defined based on the dominance relations. The existence of killing definition,as well as the sequence of definition node and use node in the execution path,are taken into consideration to analyze the coverage of test case with respect to the definition-use pair.Experimental results show that the proposed approach can effectively generate test cases for satisfying all-uses criterion. And compared with other approaches,it can improve the coverage percentage and reduce the number of generations.

Key words: Data flow testing, Dominance node, Fitness function, Genetic algorithm, Test case generation

中图分类号: 

  • TP311
[1] RAPPS S,WEYUKER E J. Selecting Software Test Data Using Data Flow Information[J]. IEEE Transactions on Software Engineering,1985,SE-11(4):367-375.
[2] JI S H,LI B X,ZHANG P C. Test Case Selection for All-Uses Criterion-Based Regression Testing of Composite Service[J]. IEEE Access,2019,7:174438-174464.
[3] AHMED M A,HERMADI I. GA-based Multiple Paths Test Data Generator[J]. Computer & Operations Research,2008,35(10):3107-3124.
[4] GIRGIS M R. Automatic Test Data Generation for Data Flow Testing Using a Genetic Algorithm[J]. Journal of Universal Computer Science,2005,11(6):898-915.
[5] GHIDUK A S,HARROLD M J,GIRGIS M R. Using Genetic Algorithms to Aid Test-Data Generation for Data-Flow Coverage[C]//14th Asia-Pacific Software Engineering Conference,2007:41-48.
[6] GONG D,ZHANG W,YAO X. Evolutionary Generation ofTest Data for Manly Paths Coverage Based on Grouping[J]. The Journal of Systems and Software,2011,84(12):2222-2233.
[7] AHO A V,LAM M S,SETHI R,et al. Compilers:Principles,Techniques,& Tools[M]//New York:Addison-Wesley,2006:597-632.
[8] LENGAUER T,TARJAN R E. A Fast Algorithm for Finding Dominators in a Flowgraph[J]. ACM Transactions on Programming Languages and Systems,1979,1(1):121-141.
[9] VARSHNEY S,MEHROTRA M. Search-based Test DataGenerator for Data-Flow Dependencies Using Dominance Concepts,Branch Distance and Elitism[J]. Arabian Journal for Science and Engineering,2016,41:853-881.
[10] ANDREOU A S,ECONOMIDES K A,SOFOKLEOUS A A. An Automatic Software Test-data Generation Schema Based on Data Flow Criteria and Genetic Algorithms[C]//Seventh International Conference on Computer and Information Technology,2007:867-872.
[11] DENG M J,CHEN R,DU Z J. Automatic Test Data Generation Model by Combining Dataflow Analysis with Genetic Algorithm[C]//Joint Conference on Pervasive Computing,2009:429-433.
[12] JAFFARI A,YOO C J,LEE J. Automatic Test Data Generation Using the Activity Diagram and Search-Based Technique[J]. Applied Sciences,2020,10(10):1-21.
[13] VIVANTI M,GORLA A M,FRASER G. Search-based Data-flow Test Generation[C]//IEEE 24th International Symposium on Software Reliability Engineering (ISSRE).2013:370-379.
[14] CHEN J Q,JIANG S J,ZHANG Z G. Approach for Test Case Generation Based on Data Flow Criterion[J]. Computer Science,2017,44(2):107-111.
[15] JIANG S,CHEN J,ZHANG Y,QIAN J,WANG R,XUE M. Evolutionary Approach to Generating Test Data for Data Flow Test[J]. IET Software,2018,12(4):318-323.
[16] GHIDUK A S. A New Software Data-Flow Testing Approach via Ant Colony Algorithms[J]. Universal Journal of Computer Science and Engineering Technology,2010,1(1):64-72.
[17] NAYAK N,MOHAPATRA D P. Automatic Test Data Generation for Data Flow Testing Using Particle Swarm Optimization[C]//International Conference on Contemporary Computing,2010:1-12.
[18] KUMAR S,YADAV D K,KHAN D A. An Accelerating PSO Algorithm Based Test Data Generator for Data-flow Dependencies Using Dominance Concepts[J]. International Journal of System Assurance Engineering and Management,2017,8(2):S1534-S1552.
[19] KUMAR S,YADAV D K,KHAN D A. A Novel Approach to Automate Test Data Generation for Data Flow Testing Based on Hybrid Adaptive PSO-GA Algorithm[J]. International Journal of Advanced Intelligence Paradigms,2018,9(2/3):278-312.
[20] SHEORAN S,MITTAL N,GELBUKH A. Artificial Bee Colony Algorithm in Data Flow Testing for Optimal Test Suite Generation[J]. International Journal of System Assurance Engineering and Management,2020,11(2):340-349.
[1] 杨浩雄, 高晶, 邵恩露.
考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题
Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery
计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2] 沈彪, 沈立炜, 李弋.
空间众包任务的路径动态调度方法
Dynamic Task Scheduling Method for Space Crowdsourcing
计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[3] 吴善杰, 王新.
基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法
Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks
计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[4] 王金恒, 单志龙, 谭汉松, 王煜林.
基于遗传优化PNN神经网络的网络安全态势评估
Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network
计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[5] 郑增乾, 王锟, 赵涛, 蒋维, 孟利民.
带宽和时延受限的流媒体服务器集群负载均衡机制
Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster
计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[6] 汪文轩, 胡军, 胡建成, 康介祥, 王辉, 高忠杰.
一种面向形式化表格需求模型的测试用例生成方法
Test Case Generation Method Oriented to Tabular Form Formal Requirement Model
计算机科学, 2021, 48(5): 16-24. https://doi.org/10.11896/jsjkx.201000048
[7] 左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智.
异构无人机编队防御及评估策略研究
Study on Heterogeneous UAV Formation Defense and Evaluation Strategy
计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[8] 高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同.
基于投影圆度和遗传算法的空间圆柱面拟合方法
Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm
计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057
[9] 姚泽玮, 林嘉雯, 胡俊钦, 陈星.
基于PSO-GA的多边缘负载均衡方法
PSO-GA Based Approach to Multi-edge Load Balancing
计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[10] 高基旭, 王珺.
一种基于遗传算法的多边缘协同计算卸载方案
Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm
计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088
[11] 董明刚, 黄宇扬, 敬超.
基于遗传实例和特征选择的K近邻训练集优化方法
K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection
计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089
[12] 梁正友, 何景琳, 孙宇.
一种用于微表情自动识别的三维卷积神经网络进化方法
Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition
计算机科学, 2020, 47(8): 227-232. https://doi.org/10.11896/jsjkx.190700009
[13] 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊.
智能3D打印路径规划算法
Intelligent 3D Printing Path Planning Algorithm
计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[14] 包振山, 郭俊南, 谢源, 张文博.
基于LSTM-GA的股票价格涨跌预测模型
Model for Stock Price Trend Prediction Based on LSTM and GA
计算机科学, 2020, 47(6A): 467-473. https://doi.org/10.11896/JsJkx.190900128
[15] 马创, 吕孝飞, 梁炎明.
基于GA-SVM的农产品质量分类
Agricultural Product Quality Classification Based on GA-SVM
计算机科学, 2020, 47(6A): 517-520. https://doi.org/10.11896/JsJkx.190900184
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!