The Problems and Challenges of Infeasible Paths in Static Analysis

  • Abstract
  • Keywords
  • References
  • PDF
  • 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.



  • Keywords

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

  • References

      [1] Da Fonseca, J. C. C. Martin, and M. P. A. Vieira, “A practical experience 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 concepts 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 infeasible paths in computer programs,”in 1985 Proceedings of the 8th international 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 pathgeneralization 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 variable 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 Systems 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 Proceedings 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 Engineering, 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 Computer 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 detection 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 detection and syntactic language refinement,”in 2008 International Static Analysis Symposium, pp. 238-254.

      [17] T. Ball, “Paths between Imperative and Functional Programming,”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: Detection of Cross Site Scripting in PHP Web Application using Genetic Algorithm,”International Journal of Advanced Computer Science and Applications (IJACSA), vol. 8, no. 5, May 2017.

      [19] S.Ding, and H. B. K.Tan, “Detection of Infeasible Paths: Approaches and Challenges,”in International Conference on Evaluation of Novel Approaches to Software Engineering, Jun 2012, pp. 64-78.

      [20] H.Liu, and H. B. K. Tan, “Covering code behavior on input validation 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 applications 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 input 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 International Conference on Software Maintenance, ICSM'06, pp. 370-379.

      [24] M. N.Ngo, and H. B. K. Tan, “Applying static analysis for automated extraction of database interactions in web applications,”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 conference and the ACM SIGSOFT symposium on The foundations of software engineering, pp. 215-224.

      [26] T.Yano, E.Martins, and F. Sousa, “MOST: a multi-objective search-based testing from EFSM,” in 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pp. 164-173.

      [27] A. S.Kalaji, R. M.Hierons, and S.Swift, “Generating feasible transition 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 system 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 Informatics, 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 International Conference on Promising Electronic Technologies (ICPET), pp. 26-31.

      [36] M. A.Ahmed, and F. Ali, “Multiple-path testing for cross site scripting using genetic algorithms,” Journal of Systems Architecture,vol. 64, pp. 50-62, Mar. 2016.




Article ID: 23175
DOI: 10.14419/ijet.v7i4.19.23175

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.