Basis Path Based Test Suite Minimization Using Genetic Algorithm

Full Text (PDF, 1071KB), PP.36-49

Views: 0 Downloads: 0


Anbunathan R 1,* Anirban Basu 2

1. Test Manager and Research Scholar, Bharathiar University, Coimbatore, India

2. Department of CSE, APS College of Engineering, Bangalore, India

* Corresponding author.


Received: 1 Nov. 2017 / Revised: 5 Jan. 2018 / Accepted: 9 Feb. 2018 / Published: 8 Nov. 2018

Index Terms

Test automation, Genetic Algorithm, Executable Test generation


UML State Diagram is used to represent the behavior of the System Under Test (SUT) when an event occurs. The state of the system is determined by the event that occurs randomly. The system state changes when the transition relationship between the States is satisfied. Test cases are generated from State Chart Diagram to test the behavior of the system. When multiple decision nodes are present in the same path, path explosion occurs. A method is proposed to generate Basis Path (BP) test cases with node coverage using Genetic Algorithm (GA) to overcome this problem. Experiments are conducted upon various Android applications and the efficiency of the algorithm is evaluated through the code coverage and the mutation analysis. Using this approach, BP test cases, Robotium test scripts are generated for 10 Android applications and observed an average of 70% reduction in the test case number concerning all path test cases. The resulted average code coverage is 74%, and Defect Removal Efficiency (DRE) is 95%. The experimental results show that the proposed method is effective when compared to other methods.

Cite This Paper

Anbunathan R, Anirban Basu, "Basis Path Based Test Suite Minimization Using Genetic Algorithm", International Journal of Intelligent Systems and Applications(IJISA), Vol.10, No.11, pp.36-49, 2018. DOI:10.5815/ijisa.2018.11.05


[1]Anirban Basu, Software Quality Assurance, Testing and Metrics, PHI Learning, 2015.
[2]Goldberg, D.E, Genetic Algorithms: in search, optimization and machine learning, Addison Wesley, M.A, 1989.
[3]Ruilian Zhao, Zheng Li, and Qian Wang. “Test Generation for Programs with Binary Tree Structure as Input”, International Journal of Software Engineering and Knowledge Engineering, vol. 25, no. 07, pp. 1129-1151, 2015.
[4]Ruilian Zhao, Mark Harman and Zheng Li. Empirical Study on the Efficiency of Search Based Test Generation for EFSM Models, in the proceedings of Third International Conference on Software Testing, Verification and Validation, 2010.
[5]Zheng Li, Mark Harman, and Robert M. Hierons. Search Algorithms for Regression Test Case Prioritization, IEEE Transactions On Software Engineering, vol. 33, no. 4, April 2007.
[6]P.R., Srivastava and Tai-hoon Kim, “Application of genetic algorithm in software testing” International Journal of Software Engineering and its Applications, vol. 3, no. 4, pp.87-96, 2009.
[7]P.R., Srivastava and Baby, “Automatic test sequence generation for state transition testing via ant colony optimization”, in: M. Chis, (Ed.), Evolutionary Computation and Optimization Algorithms in Software Engineering: Applications and Techniques, pp. 161–183, 2010.
[8]P.R., Srivastava, B. Mallikarjun, Xin-She Yang. “Optimal test sequence generation using firefly algorithm”, Elsevier, Swarm and Evolutionary Computation vol.8, pp44–53, 2013.
[9]P.R., Srivastava, Ashish Kumar Singh, Hemraj Kumhar, Mohit Jain. “Optimal Test Sequence Generation in State Based Testing Using Cuckoo Search”, International Journal of Applied Evolutionary Computation, 3(3), 17-32, July-September 2012.
[10]Pei Gong, Ruilian Zhao, Zheng Li. “Faster Mutation-based Fault Localization With A Novel Mutation Execution Strategy”, in the proceedings of IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pp 1-10, 2015.
[11]R. Lefticaru and F. Ipate. “Automatic State-Based Test Generation Using Genetic Algorithm”, in Ninth International Symposium on Symbolic and Numeric Algorithm for Scientific Computing, pp 188–195, 2008.
[12]Ernesto C. B. de Matos, Anamaria M. Moreira and João B. de Souza Neto, “An empirical study of test generation with BETA”, in Springer Journal of the Brazilian Computer Society, vol. 22, no. 8, 2016.
[13]Premal B. Nirpal and K. V. Kale. Using Genetic Algorithm for Automated Efficient Software Test Case Generation for Path Testing, in International Journal of Advanced Networking and Applications Vol. 02, No. 06, pp. 911-915, 2011.
[14]C. D. Nguyen, A. Marchetto, and P. Tonella. "Combining model-based and combinatorial testing for effective test case generation", in Proceedings of the 2012 International Symposium on Software Testing and Analysis (ISSTA), pp. 100-110, 2012.
[15]R. Mahmood, N. Mirzaei, and S. Malek. "EvoDroid: segmented evolutionary testing of Android apps", In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE), pp. 599-609, 2014.
[16]A. Machiry, R. Tahiliani, and M. Naik. Dynodroid: An input generation system for android apps. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013, pages 224–234, 2013.
[17]Dan Liu, Xuejun Wang, Jianmin Wang, Automatic Test Case Generation Based On Genetic Algorithm, Journal of Theoretical and Applied Information Technology, Vol. 48 No.1 , 2013.
[18]P. Samuel R. Mall A.K. Bothra, "Automatic test case generation using unified modeling language (UML) state diagrams", The Institution of Engineering and Technology, 2008.
[19]Ranjita Swain, Vikas Panthi and Durga Prasad Mohapatra, "Automatic Test case Generation From UML State Chart Diagram", International Journal of Computer Applications, vol. 42, no. 7, March 2012.
[20]Santosh Kumar Swain, Durga Prasad Mohapatra, Rajib Mall, “Test Case Generation Based on State and Activity Models”, In Journal of Object Technology, vol. 9, no. 5, pp. 1-27, 2010.
[21]M. Shirole, A. Suthar, and R. Kumar, "Generation of Improved Test Cases from UML State Diagram Using Genetic Algorithm," in Proceedings of the 4th India Software Engineering Conference, pp. 125-134, 2011.
[22]Anbunathan R and Anirban Basu. "Auto Test Generation from UML Use Case State Chart Diagrams", International Journal of Advanced Research in Computer Science and Software Engineering, Vol. 6, No.1, pp. 169-190, January 2016.
[23]Anbunathan R and Anirban Basu. "Automatic Test Generation from UML Sequence Diagrams for Android Mobiles", International Journal of Applied Engineering Research, Vol. 11, No.7, pp. 4961-4979, 2016.
[24]Anbunathan R and Anirban Basu. "Executable Test Generation from UML Activity Diagram Using Genetic Algorithm", International Journal of Computer Science and Information Technology & Security, Vol.7, No.3, May-June 2017.
[25]Anbunathan R and Anirban Basu. "Dataflow test case generation from UML Class Diagrams", IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), pp 134-142, 2013.
[26]Rajesh Ku. Sahoo, Santosh Kumar Nanda, Durga Prasad Mohapatra, Manas Ranjan Patra,"Model Driven Test Case Optimization of UML Combinational Diagrams Using Hybrid Bee Colony Algorithm", International Journal of Intelligent Systems and Applications(IJISA), Vol.9, No.6, pp.43-54, 2017.