The Problems and Challenges of Infeasible Paths in Static Analysis

  • Authors

    • Abdalla Wasef Marashdih
    • Zarul Fitri Zaaba
    • Saman M. Almufti
    https://doi.org/10.14419/ijet.v7i4.19.23175

    Received date: December 5, 2018

    Accepted date: December 5, 2018

    Published date: November 27, 2018

  • Infeasible Paths, Path Testing, Static Analysis, Software Testing, Security, Vulnerabilities.

  • Abstract

    Static analysis is valuable because it imparts the ability to examine all program paths. However, many of these paths are classified as infeasible paths, which signify that these paths will fail to execute. In static analysis, these paths will lead to results that are high false positive. Because static analysis has a vital part in the detection of vulnerabilities and threats in the software as well as in program analysis, improving static analysis is necessary to obtain accurate results and lessen the occurrence of false positive results. Being able to detect infeasible paths is useful in the improvement and development of the results of static analysis. However, the process that is used to identify these infeasible paths is not simple, especially because numerous tools and methods still do not have the efficiency in detecting these kinds of paths within the static analysis. This paper will review the infeasible paths problem in the static analysis, the new methods of solving this problem, and the reassessment of this vital issue in software testing. This paper will also discuss the importance of exposing and getting rid of these paths.

  • References

    1. Da Fonseca, J. C. C. Martin, and M. P. A. Vieira, “A practical expe-rience on the impact of plugins in web security,” in 2014 IEEE 33rd International Symposium on Reliable Distributed Systems (SRDS), pp. 21-30.
    2. A., Avizienis,J. C.Laprie, B.Randell, and C. Landwehr, “Basic con-cepts and taxonomy of dependable and secure computing,”IEEE transactions on dependable and secure computing, vol. 1, no. 1, pp. 11-33, Jan. 2004.
    3. A. W.Marashdih, and Z. F.Zaaba,“Cross Site Scripting: Detection Approaches in Web Application,”(IJACSA) International Journal of Advanced Computer Science and Applications, vol. 7, no. 10, Oct. 2016.
    4. D. Hedley, and M. A. Hennell, “The causes and effects of infeasi-ble paths in computer programs,”in 1985 Proceedings of the 8th in-ternational conference on Software engineering, pp. 259-266.
    5. M., Papadakis, and N. Malevris, “A symbolic execution tool based on the elimination of infeasible paths,” in 2010 Fifth International Conference on Software Engineering Advances (ICSEA), pp. 435-440.
    6. M., Delahaye, B. Botella, and A. Gotlieb, “Infeasible pathgenerali-zation in dynamic symbolic execution,”Information and Software Technology, vol. 58, pp. 403-418, Feb. 2015.
    7. A. S.Ghiduk, “Automatic generation of basis test paths using varia-ble length genetic algorithm,” Information Processing Letters, vol. 114, no. 6, pp. 304-316, Jun. 2014.
    8. M. A., Ahmed, and I.Hermadi, “GA-based multiple paths test data generator,”Computers & Operations Research, vol. 35, no. 10, pp. 3107-3124, Oct. 2008.
    9. D.Gong, W.Zhang, and X. Yao, “Evolutionary generation of test data for many paths coverage based on grouping,”Journal of Sys-tems and Software, vol. 84, no.12, pp. 2222-2233, Dec. 2011.
    10. P. M. S.Bueno, and M. Jino, “Identification of potentially infeasible program paths by monitoring the search for test data,” in2000 Pro-ceedings Fifteenth IEEE International Conference on Automated Software Engineering, ASE, pp. 209-218, Sep. 2011.
    11. N.Gupta, A. P.Mathur, and M. L.Soffa,“Generating test data for branch coverage,”in 2000 proceedings Automated Software Engi-neering, ASE, pp. 219-227, Sep. 2000.
    12. V.Prokhorenko, K. K. R.Choo, and H. Ashman, “Web application protection techniques: A taxonomy,”Journal of Network and Com-puter Applications, vol. 60, pp. 95-112, Jan. 2016.
    13. B.Barhoush, and I. Alsmadi, “Infeasible Paths Detection Using Static Analysis,”The Research Bulletin of Jordan ACM, vol. 2, no. 3, pp. 120-126, 2013.
    14. M. N.Ngo, and H. B. K.Tan, “Heuristics-based infeasible path de-tection for dynamic test data generation,”Information and Software Technology, vol. 50, no. 7-8, pp. 641-655, Jun. 2008.
    15. D. Gong, and X.Yao,“Automatic detection of infeasible paths in software testing,” IET software, vol. 4, no. 5, pp. 361-370, Oct. 2010.
    16. G.Balakrishnan, S.Sankaranarayanan, F.Ivančić, O.Wei, and A.Gupta, “SLR: Path-sensitive analysis through infeasible-path de-tection and syntactic language refinement,”in 2008 International Static Analysis Symposium, pp. 238-254.
    17. T. Ball, “Paths between Imperative and Functional Program-ming,”ACM SIGPLAN Notices, vol. 34, no. 2, pp. 21-25, Feb. 1999.
    18. A. W.Marashdih, Z. F.Zaaba, and H. K.Omer, “Web Security: De-tection of Cross Site Scripting in PHP Web Application using Ge-netic Algorithm,”International Journal of Advanced Computer Sci-ence and Applications (IJACSA), vol. 8, no. 5, May 2017.
    19. S.Ding, and H. B. K.Tan, “Detection of Infeasible Paths: Ap-proaches and Challenges,”in International Conference on Evalua-tion of Novel Approaches to Software Engineering, Jun 2012, pp. 64-78.
    20. H.Liu, and H. B. K. Tan, “Covering code behavior on input valida-tion in functional testing,” Information and Software Technology, vol. 51, no. 2, pp. 546-553, Feb. 2009.
    21. H.Liu, and H. B. K. Tan, “Testing input validation in Web applica-tions through automated model recovery,”Journal of Systems and Software, vol. 81, no. 2, pp. 222-233, Feb. 2008.
    22. H.Liu, and H. B. K. Tan, “An approach for the maintenance of in-put validation,”Information and Software Technology, vol. 50, no. 5, pp. 449-461, Apr. 2008.
    23. H.Liu, and H. B. K. Tan, “An approach to aid the understanding and maintenance of input validation,”in 2006 22nd IEEE Interna-tional Conference on Software Maintenance, ICSM'06, pp. 370-379.
    24. M. N.Ngo, and H. B. K. Tan, “Applying static analysis for auto-mated extraction of database interactions in web applica-tions,”Information and software technology, vol. 50, no. 3, pp. 160-175, Feb. 2008.
    25. M. N.Ngo, and H. B. K.Tan,“Detecting large number of infeasible paths through recognizing their patterns,”in 2007 Proceedings of the the 6th joint meeting of the European software engineering confer-ence and the ACM SIGSOFT symposium on The foundations of software engineering, pp. 215-224.
    26. T.Yano, E.Martins, and F. L.de Sousa, “MOST: a multi-objective search-based testing from EFSM,” in 2011 IEEE Fourth Interna-tional Conference on Software Testing, Verification and Validation Workshops (ICSTW), pp. 164-173.
    27. A. S.Kalaji, R. M.Hierons, and S.Swift, “Generating feasible transi-tion paths for testing from an extended finite state machine (EFSM),” in 2009 International Conference on Software Testing Verification and Validation, ICST'09,pp. 230-239.
    28. S.Wong, C. Y.Ooi, Y. W.Hau, M. N.Marsono, and N.Shaikh-Husin, “Feasible transition path generation for EFSM-based sys-tem testing,” in 2013 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1724-1727.
    29. D.Jayaraman, and S.Tragoudas,“Performance validation through implicit removal of infeasible paths of the behavioral description,” in 2013 14th International Symposium on Quality Electronic Design (ISQED), pp. 552-557.
    30. I.Hermadi, C.Lokan, and R.Sarker,“Dynamic stopping criteria for search-based test data generation for path testing,”Information and Software Technology, vol. 56, no. 4, pp. 395-407, Apr. 2014.
    31. J.Ruiz, and H.Cassé, “Using smt solving for the lookup of infeasible paths in binary programs,” in OASIcs-OpenAccess Series in Infor-matics, vol. 47, 2015.
    32. J.Ruiz, H.Cassé, and M. de Michiel, “Working Around Loops for Infeasible Path Detection in Binary Programs,” in 2017 IEEE 17th International Working Conference on Source Code Analysis and Manipulation (SCAM), pp. 1-10.
    33. J.Gustafsson, A.Betts, A.Ermedahl, and B. Lisper, “The Mälardalen WCET benchmarks: Past, present and future,” In OASIcs-OpenAccess Series in Informatics, vol. 15, 2010.
    34. A. W. Marashdih, and Z. F. Zaaba, “Cross Site Scripting: Removing Approaches in Web Application,”Procedia Computer Science, vol. 124, pp. 647-655, Dec. 2017.
    35. A. W. Marashdih, and Z. F. Zaaba, “Detection and Removing Cross Site Scripting Vulnerability in PHP Web Application,” in 2017 In-ternational Conference on Promising Electronic Technologies (ICPET), pp. 26-31.
    36. M. A.Ahmed, and F. Ali, “Multiple-path testing for cross site script-ing using genetic algorithms,” Journal of Systems Architecture,vol. 64, pp. 50-62, Mar. 2016.

  • Downloads

  • How to Cite

    Wasef Marashdih, A., Fitri Zaaba, Z., & M. Almufti, S. (2018). The Problems and Challenges of Infeasible Paths in Static Analysis. International Journal of Engineering and Technology, 7(4.19). https://doi.org/10.14419/ijet.v7i4.19.23175