Automation Of Independent Path Searching using Depth First Search




In a basis path testing, there are independent paths that must be passed/tested at least once to make sure there are no errors in the code and ensure all pseudocode have implemented on the code. Previously, the independent path was generated using the Genetic Algorithm, but the number of iterations influenced the likelihood of the emergence of the corresponding the independent path. Besides, the pseudocode was also unable to be used directly since it must be implemented first, this makes finding an independent path longer because it has to implement the code. This research aims to find out how to find the independent path directly from pseudocode using a graph and how well the Depth First Search algorithm in finding the independent path. It was chosen because it was able to find the paths from a point to a particular point in a graph. The result of the system accuracy test was able to find the correct independent path as much as 52 from 76 test data, where the result of accuracy is 68.4% on average.

Author Biography

Achmad Arwan, Universitas Brawijaya

Informatic Engineering department, Faculty of computer sciencr


Pressman RS (2009) Software Engineering A Practitioner’s Approach 7th Ed - Roger S. Pressman

Sommerville I (2011) Software Engineering, 9th ed. Pearson

Elodie V (2011) White Box Coverage and Control Flow Graphs. 1–33

Lam SSB, Raju MLHP, Uday KM, Swaraj C, Srivastav PR (2012) Automated generation of independent paths and test suite optimization using artificial bee colony. Procedia Eng 30:191–200 . doi: 10.1016/j.proeng.2012.01.851

Singla S, Kumar R, Kumar D (2016) Natural Computing for Automatic Test Data Generation Approach Using Spanning Tree Concepts. Procedia Comput Sci 85:929–939 . doi: 10.1016/j.procs.2016.05.284

Kun W, Yichen W (2016) Software test case generation based on the fault propagation path coverage. Proc - Annu Reliab Maintainab Symp 2016–April: . doi: 10.1109/RAMS.2016.7448004

Malhotra R, Poornima, Kumar N (2016) Automatic test data generator: A tool based on search-based techniques. 2016 5th Int Conf Reliab Infocom Technol Optim ICRITO 2016 Trends Futur Dir 570–576 . doi: 10.1109/ICRITO.2016.7785020

Csallner C, Smaragdakis Y (2004) JCrasher: An automatic robustness tester for Java. Softw - Pract Exp 34:1025–1050 . doi: 10.1002/spe.602

Tonella P, Ceccato M, Ãòø Ã’ (2004) Aspect Mining through the Formal Concept Analysis of Execution Traces µ ¿ µ ¿ µ ¿ µ ¿ µ µ

Pacheco C, Ernst MD (2007) Randoop: Feedback-Directed Random Testing for Java. Companion to 22nd ACM SIGPLAN Conf Object oriented Program Syst Appl companion - OOPSLA ’07 5:815 . doi: 10.1145/1297846.1297902

Park S, Hossain BMM, Hussain I, Csallner C, Grechanik M, Taneja K, Fu C, Xie Q (2012) CarFast: Achieving Higher Statement Coverage Faster. Proc ACM SIGSOFT 20th Int Symp Found Softw Eng 1–11 . doi: 10.1145/2393596.2393636

Baresi L, Lanzi PL, Miraz M (2010) TestFul: An evolutionary test approach for Java. ICST 2010 - 3rd Int Conf Softw Testing, Verif Valid 185–194 . doi: 10.1109/ICST.2010.54

Prasetya W (2014) T3, a Combinator-based Random Testing Tool for Java: Benchmarking. 8432: . doi: 10.1007/978-3-319-07785-7

Fraser G, Arcuri A (2011) EvoSuite : Automatic Test Suite Generation for Object-Oriented Software. Proc 19th ACM SIGSOFT Symp 13th Eur Conf Found Softw Eng 416–419 . doi: 10.1145/2025113.2025179

Sen K, Marinov D, Agha G, Sen K, Marinov D, Agha G (2005) CUTE: A concolic unit testing engine for C. 10th Eur Softw Eng Conf 13th ACM SIGSOFT Int Symp Found Softw Eng 30:263 . doi: 10.1145/1081706.1081750

Godefroid P, Klarlund N, Sen K (2005) DART: directed automated random testing. Proc 2005 ACM SIGPLAN Conf Program Lang Des Implement 213–223 . doi: 10.1145/1065010.1065036

Cadar C, Dunbar D, Engler DR (2008) KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. Proc 8th USENIX Conf Oper Syst Des Implement 209–224 . doi:

Tillmann N, de Halleux J (2008) Pex: White Box Test Generation for .NET. Proc TAP 134–153 . doi: 10.1007/978-3-540-79124-9_10

Ghiduk AS (2014) Automatic generation of basis test paths using variable length genetic algorithm. Inf. Process. Lett. 114:304–316

Arwan A, Rusdianto D (2017) Optimization of Genetic Algorithm Performance using Naïve Bayes for Basis Path Generation. Kinet Game Technol Inf Syst Comput Network, Comput Electron Control 2: . doi: 10.22219/kinetik.v2i4.370

Arwan, A., & Rusdianto DS (2018) Determining Basis Test Paths using Genetic Algorithm and J48. Int J Electr Comput Eng 8:

Sedgewick R, Wayne K (2011) Algorithms

Meiliana, Septian I, Alianto RS, Daniel, Gaol FL (2017) Automated Test Case Generation from UML Activity Diagram and Sequence Diagram using Depth First Search Algorithm. Procedia Comput Sci 116:629–637 . doi: 10.1016/j.procs.2017.10.029

Kurniawan TA (2007) Pengujian Struktur Program Dengan Pengujian Jalur Dasar ( Basis Path Testing ) : Teori Dan Aplikasi. EECCIS 1:29–32

Wang Q, Jiang S, Zhang Y (2012) An Approach to Generate Basis Path for Programs with Exception- Handling Constructs. 51:330–335 . doi: 10.7763/IPCSIT.2012.V51.56




How to Cite

Arwan, A., & Sagita, D. (2018). Automation Of Independent Path Searching using Depth First Search. Journal of Information Technology and Computer Science, 3(1), 104–112.