Mauro Baluda
ABSTRACT
Search Based Software Testing (SBST) and Symbolic Execution (SE) have emerged as the most effective among the fully automated test input generation techniques. However, none of the two techniques satisfactorily solves the problem of generating test cases that exercise specific code elements, as it is required for example in security vulnerability testing. This paper proposes EvoSE, an approach that combines the strengths of SBST and SE. EvoSE implements an evolutionary algorithm that searches the program control flow graph for symbolic paths that traverse the minimum number of unsatisfiable branch conditions. Preliminary evaluation shows that EvoSE outperforms state-of-the-art SE search strategies when targeting specific code elements.
- S. Anand, E. K. Burke, T. Y. Chen, J. Clark, M. B. Cohen, W. Grieskamp, M. Harman, M. J. Harrold, and P. Mcminn. An orchestrated survey of methodologies for automated software test case generation. J. of Systems and Software, 86(8):1978–2001, 2013. Google Scholar
Digital Library
- A. Arcuri. It really does matter how you normalize the branch distance in search-based software testing. Software Testing, Verification and Reliability, 23(2):119–147, 2013.Google ScholarCross Ref
- A. Baars, M. Harman, Y. Hassoun, K. Lakhotia, P. McMinn, P. Tonella, and T. Vos. Symbolic search-based testing. In Automated Software Engineering (ASE), 2011 26th IEEE/ACM International Conference on, pages 53–62, Nov 2011. Google ScholarDigital Library
- M. Baluda, P. Braione, G. Denaro, and M. Pezzè. Enhancing structural software coverage by incrementally computing branch executability. Software Quality Journal, 19(4):725–751, 2011. Google ScholarDigital Library
- P. Dinges and G. Agha. Solving complex path conditions through heuristic search on induced polytopes. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, pages 425–436, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. SpringerVerlag, 2003. Google ScholarDigital Library
- G. Fraser and A. Arcuri. Whole test suite generation. IEEE Transactions on Software Engineering, 39(2):276 –291, feb. 2013. Google ScholarDigital Library
- J. P. Galeotti, G. Fraser, and A. Arcuri. Improving search-based test suite generation with dynamic symbolic execution. In IEEE International Symposium on Software Reliability Engineering, 2013.Google ScholarCross Ref
- P. Godefroid and S. Khurshid. Exploring very large state spaces using genetic algorithms. In J.-P. Katoen and P. Stevens, editors, Tools and Algorithms for the Construction and Analysis of Systems, volume 2280 of Lecture Notes in Computer Science, pages 266–280. Springer Berlin Heidelberg, 2002. Google ScholarDigital Library
- H. Ishibuchi, T. Yoshida, and T. Murata. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. Evolutionary Computation, IEEE Transactions on, 7(2):204–223, April 2003. Google ScholarDigital Library
- P. Larra˜ naga, C. Kuijpers, R. Murga, I. Inza, and S. Dizdarevic. Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2):129–170, 1999. Google ScholarDigital Library
- K.-K. Ma, K. Y. Phang, J. S. Foster, and M. Hicks. Directed symbolic execution. In Proceedings of the 18th International Conference on Static Analysis, SAS’11, pages 95–111, Berlin, Heidelberg, 2011. Springer-Verlag. Google ScholarDigital Library
- P. D. Marinescu and C. Cadar. Katch: High-coverage testing of software patches. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013, pages 235–245, New York, NY, USA, 2013. ACM. Google ScholarDigital Library
- S. Sidiroglou-Douskos, E. Lahtinen, N. Rittenhouse, P. Piselli, F. Long, D. Kim, and M. Rinard. Targeted automatic integer overflow discovery using goal-directed conditional branch enforcement. SIGPLAN Not., 50(4):473–486, Mar. 2015. Google ScholarDigital Library
- N. Tracey, J. Clark, K. Mander, and J. McDermid. An automated framework for structural test-data generation. In Proceedings of the 13th IEEE International Conference on Automated Software Engineering, ASE ’98, Washington, DC, USA, 1998. IEEE Computer Society. Google ScholarDigital Library
- P. Tsankov, W. Jin, A. Orso, and S. Sinha. Execution hijacking: Improving dynamic analysis by flying off course. In Proceedings of the 2011 Fourth IEEE International Conference on Software Testing, Verification and Validation, ICST ’11, pages 200–209, Washington, DC, USA, 2011. IEEE Computer Society. Google ScholarDigital Library
- T. Xie, N. Tillmann, P. de Halleux, and W. Schulte. Fitness-guided path exploration in dynamic symbolic execution. In Proceedings of the 39th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2009), pages 359–368, June-July 2009.Google ScholarCross Ref
Index Terms
- EvoSE: evolutionary symbolic execution
Recommendations
An orchestrated survey of methodologies for automated software test case generation
Test case generation is among the most labour-intensive tasks in software testing. It also has a strong impact on the effectiveness and efficiency of software testing. For these reasons, it has been one of the most active research topics in software ...
An Automated Testing Tool for Java Application Using Symbolic Execution Based Test Case Generation
APSEC '13: Proceedings of the 2013 20th Asia-Pacific Software Engineering Conference (APSEC) - Volume 02We are developing a test case generation service that uses symbolic execution technique, to support testing of Java programs. In addition to program under test, we need drivers and stubs to execute the service. However, preparing drivers and stubs ...
Guest Editors' Introduction: Software Testing Practices in Industry
Four papers and a roundtable discussion shed light on the current state of software testing practices. Case studies from industry experience address topics including unit-testing practices, agile testing, and automating software testing. Although many ...
Comments