Computer Science ›› 2020, Vol. 47 ›› Issue (9): 40-46.doi: 10.11896/jsjkx.200700021

• Computer Software • Previous Articles     Next Articles

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).

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

CLC Number: 

  • 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] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[3] WU Shan-jie, WANG Xin. Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks [J]. Computer Science, 2021, 48(7): 308-315.
[4] WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[5] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[6] WANG Wen-xuan, HU Jun, HU Jian-cheng, KANG Jie-xiang, WANG Hui, GAO Zhong-jie. Test Case Generation Method Oriented to Tabular Form Formal Requirement Model [J]. Computer Science, 2021, 48(5): 16-24.
[7] ZUO Jian-kai, WU Jie-hong, CHEN Jia-tong, LIU Ze-yuan, LI Zhong-zhi. Study on Heterogeneous UAV Formation Defense and Evaluation Strategy [J]. Computer Science, 2021, 48(2): 55-63.
[8] GAO Shuai, XIA Liang-bin, SHENG Liang, DU Hong-liang, YUAN Yuan, HAN He-tong. Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm [J]. Computer Science, 2021, 48(11A): 166-169.
[9] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[10] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[11] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[12] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
[13] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[14] FENG Bing-chao and WU Jing-li. Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System [J]. Computer Science, 2020, 47(6A): 114-118.
[15] YAO Min. Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem [J]. Computer Science, 2020, 47(6A): 124-129.
Full text



No Suggested Reading articles found!