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, Test case generation, Genetic algorithm, Fitness function, Dominance node

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] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] YAO Min. Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem [J]. Computer Science, 2020, 47(6A): 124-129.
[7] BAO Zhen-shan, GUO Jun-nan, XIE Yuan and ZHANG Wen-bo. Model for Stock Price Trend Prediction Based on LSTM and GA [J]. Computer Science, 2020, 47(6A): 467-473.
[8] MA Chuang, LV Xiao-fei and LIANG yan-ming. Agricultural Product Quality Classification Based on GA-SVM [J]. Computer Science, 2020, 47(6A): 517-520.
[9] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[10] HU Shi-juan, LU Hai-yan, XIANG Lei, SHEN Wan-qiang. Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP [J]. Computer Science, 2020, 47(6): 219-224.
[11] ZHANG Ju, WANG Hao, LUO Shu-ting, GENG Hai-jun, YIN Xia. Hybrid Software Defined Network Energy Efficient Routing Algorithm Based on Genetic Algorithm [J]. Computer Science, 2020, 47(6): 236-241.
[12] JIN Xiao-min, HUA Wen-qiang. Energy Optimization Oriented Resource Management in Mobile Cloud Computing [J]. Computer Science, 2020, 47(6): 247-251.
[13] BAI Wei, PAN Zhi-song, XIA Shi-ming, CHENG Ang-xuan. Network Security Configuration Generation Framework Based on Genetic Algorithm Optimization [J]. Computer Science, 2020, 47(5): 306-312.
[14] LIU Xiao-tong,WANG Wei,LI Ze-yu,SHEN Si-wan,JIANG Xiao-ming. Recognition Algorithm of Red and White Cells in Urine Based on Improved BP Neural Network [J]. Computer Science, 2020, 47(2): 102-105.
[15] WANG Xiao-hui, ZHANG Liang, LI Jun-qing, SUN Yu-cui, TIAN Jie, HAN Rui-yi. Study on XGBoost Improved Method Based on Genetic Algorithm and Random Forest [J]. Computer Science, 2020, 47(11A): 454-458.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[5] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[6] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[7] YANG Yu-qi, ZHANG Guo-an and JIN Xi-long. Dual-cluster-head Routing Protocol Based on Vehicle Density in VANETs[J]. Computer Science, 2018, 45(4): 126 -130 .
[8] SHI Chao, XIE Zai-peng, LIU Han and LV Xin. Optimization of Container Deployment Strategy Based on Stable Matching[J]. Computer Science, 2018, 45(4): 131 -136 .
[9] HAN Kui-kui, XIE Zai-peng and LV Xin. Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm[J]. Computer Science, 2018, 45(4): 137 -142 .
[10] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151 .