计算机科学 ›› 2020, Vol. 47 ›› Issue (9): 40-46.doi: 10.11896/jsjkx.200700021
吉顺慧, 张鹏程
JI Shun-hui, ZHANG Peng-cheng
摘要: 程序控制流的设计是为实现正确的数据流服务的,数据流测试是非常重要的。文中将面向all-uses数据流准则的测试用例生成问题建模为多目标优化问题,提出了一种基于遗传算法的测试用例生成方法。通过构建待测程序的控制流图进行数据流分析,计算出程序中所有的定义-使用对,得到测试目标,利用面向多测试目标的遗传算法生成满足all-uses准则的最优解。遗传算法中定义了一种改进的基于支配关系的适应度函数,在分析测试用例对定义-使用对的覆盖程度时考虑了存在重定义的可能性,且考虑了定义结点和使用结点在执行路径中的先后顺序。实验结果表明,所提方法可以有效地生成满足all-uses准则的测试用例,相比其他方法可以有效地提升测试目标的覆盖率,降低生成测试用例所需的迭代次数。
中图分类号:
[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 |
|