Main Article Content


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.

Article Details

Author Biography

Achmad Arwan, Universitas Brawijaya

Informatic Engineering department, Faculty of computer sciencr
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.


  1. Pressman RS (2009) Software Engineering A Practitioner’s Approach 7th Ed - Roger S. Pressman
  2. Sommerville I (2011) Software Engineering, 9th ed. Pearson
  3. Elodie V (2011) White Box Coverage and Control Flow Graphs. 1–33
  4. 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
  5. 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
  6. 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
  7. 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
  8. Csallner C, Smaragdakis Y (2004) JCrasher: An automatic robustness tester for Java. Softw - Pract Exp 34:1025–1050 . doi: 10.1002/spe.602
  9. Tonella P, Ceccato M, Ãòø Ã’ (2004) Aspect Mining through the Formal Concept Analysis of Execution Traces µ ¿ µ ¿ µ ¿ µ ¿ µ µ
  10. 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
  11. 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
  12. 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
  13. Prasetya W (2014) T3, a Combinator-based Random Testing Tool for Java: Benchmarking. 8432: . doi: 10.1007/978-3-319-07785-7
  14. 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
  15. 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
  16. 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
  17. 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:
  18. 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
  19. Ghiduk AS (2014) Automatic generation of basis test paths using variable length genetic algorithm. Inf. Process. Lett. 114:304–316
  20. 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
  21. Arwan, A., & Rusdianto DS (2018) Determining Basis Test Paths using Genetic Algorithm and J48. Int J Electr Comput Eng 8:
  22. Sedgewick R, Wayne K (2011) Algorithms
  23. 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
  24. Kurniawan TA (2007) Pengujian Struktur Program Dengan Pengujian Jalur Dasar ( Basis Path Testing ) : Teori Dan Aplikasi. EECCIS 1:29–32
  25. 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