CFP last date
20 June 2024
Reseach Article

Automatic Generation of Data Flow Test Paths using a Genetic Algorithm

by Moheb R. Girgis, Ahmed S. Ghiduk, Eman H. Abd-elkawy
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 89 - Number 12
Year of Publication: 2014
Authors: Moheb R. Girgis, Ahmed S. Ghiduk, Eman H. Abd-elkawy

Moheb R. Girgis, Ahmed S. Ghiduk, Eman H. Abd-elkawy . Automatic Generation of Data Flow Test Paths using a Genetic Algorithm. International Journal of Computer Applications. 89, 12 ( March 2014), 29-36. DOI=10.5120/15684-4534

@article{ 10.5120/15684-4534,
author = { Moheb R. Girgis, Ahmed S. Ghiduk, Eman H. Abd-elkawy },
title = { Automatic Generation of Data Flow Test Paths using a Genetic Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { March 2014 },
volume = { 89 },
number = { 12 },
month = { March },
year = { 2014 },
issn = { 0975-8887 },
pages = { 29-36 },
numpages = {9},
url = { },
doi = { 10.5120/15684-4534 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Journal Article
%1 2024-02-06T22:09:04.384384+05:30
%A Moheb R. Girgis
%A Ahmed S. Ghiduk
%A Eman H. Abd-elkawy
%T Automatic Generation of Data Flow Test Paths using a Genetic Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 89
%N 12
%P 29-36
%D 2014
%I Foundation of Computer Science (FCS), NY, USA

Path testing a program involves generating all paths through the program, and finding a set of program inputs that will execute every path. Since it is impossible to cover all paths in a program, path testing can be relaxed by selecting a subset of all executable paths that fulfill a certain path selection criterion and finding test data to cover it. The automatic generation of such test paths leads to more test coverage paths thus resulting in efficient and effective testing strategy. This paper presents a structural-oriented technique that uses a genetic algorithm (GA) for automatic generation of a set of test paths that cover the all-uses criterion. In the case of programs that have loops, the proposed technique generates paths according to the ZOT-subset criterion, which requires paths that traverse loops zero, one and two times. The proposed GA uses a binary vector as a chromosome to represent the edges in the DD-graph of the program under test. The set of paths generated by the proposed GA can be passed to a test data generation tool to find program inputs that will execute them. Experiments have been carried out to evaluate the effectiveness of the proposed GA compared to the random test path generation technique.

  1. A. Bertolino, M. Marre, "Automatic Generation of Path Covers Based on the Control flow analysis of computer Programs" IEEE Transaction on Software on software Engineering, Vol. 20, No. 12, pp. 885-899, 1994.
  2. T. McCabe, J. Thomas, Structural Testing: A Software Testing Methodology Using the Cyclomatic Complexity Metric, NIST Special Publication 500-99, Washington D. C. , 1982.
  3. J. Poole, "A Method to Determine a Basis Set of Paths to Perform Program Testing" http://hissa. nist. gov//publications/nistir5737, 2004
  4. Z. Guangmei, C. Rui, L. Xiaowei, H. Congying "The Automatic Generation of Basis Set of Path for Path Testing", Proceedings of the 14th Asian Test Symposium (ATS '05), 2005.
  5. Jun Yan, Jian Zhang "An efficient method to generate feasible paths for basis path testing" Information Processing Letters, Vol. 107, Issues 3-4, pp. 87-92, 31 July 2008.
  6. Z. Zhonglin, M. Lingxia,"An Improved Method of Acquiring Basis Path for Software Testing" Proceedings of 5th International Conference on Computer Science & Education, pp. 1891-1894, China, 2010.
  7. D. Qingfeng, D. Xiao "An Improved Algorithm for Basis Path Testing" International Conference on Business Management and Electronic Information (BMEI), pp. 175 – 178, 2011.
  8. M. Pei, E. D. Goodman, Z. Gao, and K. Zhong, "Automated Software Test Data Generation Using A Genetic Algorithm", Technical Report GARAGe of Michigan State University,1994.
  9. M. Roper, I. Maclean, A. Brooks, J. Miller, and M. Wood, "Genetic Algorithms and the Automatic Generation of Test Data", Technical Report RR/95/195 [EFoCS-19-95], University of Strathclyde, Glasgow G1 1XH, U. K, 1995.
  10. A. E. L. Watkins, "A Tool for the Automatic Generation of Test Data Using Genetic Algorithms", In Proceedings of Software Quality Conference, Dundee, Scotland, 1995.
  11. B. F. Jones, D. E. Eyres, and H. -H. Sthamer, "A strategy for using genetic algorithms to automate branch and fault-based testing', The Computer Journal, Vol. 41, No. 2, 98-107, 1998.
  12. R. P. Pargas, M. J. Harrold, and R. R. Peck, 'Test-Data Generation Using Genetic Algorithms", The Journal of Software Testing, Verification and Reliability, 1999.
  13. P. M. S. Bueno, and M. Jino, "Identification of potentially infeasible program paths by monitoring the search for test data", The 15th International Conference on Automated Software Engineering (ASE'00), Grenoble, France, 2000.
  14. J. -C. Lin and P. -L. Yeh, "Automatic test data generation for path testing using GAs", Information Sciences, 131 (1-4), 47-64, 2001.
  15. C. C. Michael, G. McGraw, and M. A. Schatz, "Generating Software Test Data by Evolution", IEEE Transactions on Software Engineering, Vol. 27, No. 12, 1085-1110, 2001.
  16. P. M. S. Bueno and M. Jino, "Automatic Test Data Generation For Program Paths Using Genetic Algorithms", International Journal of Software Engineering and Knowledge Engineering, December 2002, Vol. 12, No. 06, pp. 691-709.
  17. M. R. Girgis, "Automatic test data generation for data flow testing using a genetic algorithm", Journal of Universal computer Science, vol. 11, no. 5, pp. 898-915, 2005.
  18. A. S. Ghiduk, M. J. Harrold, M. R. Girgis, "Using genetic algorithms to aid test-data generation for data flow coverage", Proc. of 14th Asia-Pacific Software Engineering Conference (APSEC 07), 2007, pp. 41-48. IEEE Press.
  19. D. W. Gong, W. Q. Zhang, X. J. Yao, "Evolutionary Generation of Test Data for Many Paths Coverage Based on Grouping", Journal of Systems and Software, Vol. 84, No. 12, pp. 2222–2233, 2011.
  20. M. R. Girgis, A. S. Ghiduk, and E. H. Abd-Elkawy, "An Approach For Enhancing Regression Testing Using Genetic Algorithm and Data Flow Analysis", International Journal of Intelligent Computing and Information Science, Vol. 13, No. 2, APRIL 2013, pp. 115-132.
  21. I. Hermadi, C. Lokan, and R. Sarker, "Genetic Algorithm Based Path Testing: Challenges and Key Parameters", Second WRI World Congress on Software Engineering, 2010
  22. J. R. Bint, Renate Site, "Optimizing Testing Efficiency with Error Prone Path Identification and Genetic Algorithms" 2004 Australian Software Engineering Conference (ASWEC'04), Australia, pp. 106-115, 2004.
  23. A. S. Ghiduk, "Automatic Generation of Basis Test Paths Using Variable Length Genetic Algorithm" International Journal of Information Processing Letters, vol. 114, pp. 304-3016, 2014.
  24. S. Rapps and E. J. Weyuker, "Selecting software test data using data flow information", IEEE Transactions on Software Engineering, Vol. 11, No. 4, pp. 367-375, 1985.
  25. Girgis, M. R. (1992) 'An experimental evaluation of a symbolic execution system', Software Engineering Journal, 7 (4), 285-290.
  26. M. R. Girgis, "Using symbolic execution and data flow criteria to aid test data selection", The Journal of Software Testing, Verification and Reliability, Vol. 3, No. 2, pp. 101-112, 1993.
  27. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, Mass. , 1989.
Index Terms

Computer Science
Information Sciences


Automatic test path generation Data flow testing Genetic algorithms.