Applying Slicing-based Testability Transformation to Improve Test Data Generation with Symbolic Execution

doi:10.23940/ijpe.21.07.p3.589599

Abstract

Abstract: Symbolic execution techniques are widely adopted in diverse fields, including software quality analysis, software defect detection and so on. Symbolic execution engines assist people to apply the technique on exploiting and test data generation conveniently. However, symbolic execution is quite hard to scale to large and complicated programs which have massive paths and conditional statements due to path explosion. Moreover, for the development cycle of software systems, the necessity to generate test data frequently and rapidly makes them tough to apply symbolic execution technique on software testing. In this paper, we propose three modes of slicing-based testability transformations to change the semantics of programs while maintaining or improving the code coverage of generated test data by the symbolic execution tool: KLEE. The concept of these testability transformations is in decreasing the execution load of KLEE through shortening execution paths in programs. Our proposed testability transformation Mode 1 (TTM1) slices programs with an automated program slicing tool and takes functions in the program as the slicing criterion. On the other hand, our proposed testability transformations Mode 2 (TTM2) and Mode 3 (TTM3) slice programs manually and limit the max depth of paths in programs to a specific value as the slicing criterion. Experimental results show TTM1 could decrease 4.5% of solver queries while increasing 6.6% of code coverage on average. TTM2 could decrease 7.7% of solver queries while increasing 5.4% of coverage on average. TTM3 could decrease 17.6% of solver queries while increasing 3.6% of coverage on average. It can be observed that though the semantics of programs change due to slicing, the coverage of test data generated by KLEE could maintain the same or even become higher. Our finding also indicates that there is room to design slicing-based testability transformations to improve quality of test generation with symbolic execution.

Key words: symbolic execution, testability transformation, program slicing, KLEE, automated test generation

Hsin-Yu Chien, Chin-Yu Huang, and Chih-Chiang Fang. Applying Slicing-based Testability Transformation to Improve Test Data Generation with Symbolic Execution [J]. Int J Performability Eng, 2021, 17(7): 589-599.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

1. Jones C.C.Software quality: Analysis and guidelines for success. Thomson Learning, 1997.
2. Beizer, B. Software system testing and quality assurance. Van Nostrand Reinhold Co., 1984
3. Offutt, J. and Ammann, P.Introduction to software testing. Cambridge: Cambridge University Press, pp. 27, 2008.
4. Myers, G.J. Sandler, C. and Badgett, T. The art of software testing. John Wiley & Sons, 2011.
5. B. Beizer, Software Testing Techniques, Van Nostrand Reinhold, 1983.
6. Hailpern, B. and Santhanam, P.Software debugging, testing, and verification.IBM Systems Journal, 41(1), pp.4-12, 2002.
7. Bertolino, A. May.Software testing research: Achievements, challenges, dreams. InFuture of Software Engineering (FOSE'07), pp. 85-103. IEEE, 2007.
8. Qiu W., Lian G., Zhou P. and Huang K.Test sample allocation method for testability verification test. Quality and Reliability Engineering International,36(5), pp.1592-1603, 2020.
9. Leung, H.K. and White, L.Insights into regression testing (software testing). InProceedings. Conference on Software Maintenance-1989, pp. 60-69. IEEE, October 1989.
10. M.Fowler, Continuous Integration, <https://www.martinfowler.com/articles/continuousIntegration.html>. Accessed 5 July 2020.
11. Yoo, S. and Harman, M.Regression testing minimization, selection and prioritization: a survey. Software testing, verification and reliability,22(2), pp.67-120, 2012.
12. Campos, J., Arcuri, A. Fraser, G. and Abreu, R. Continuous test generation: Enhancing continuous integration with automated test generation. InProceedings of the 29th ACM/IEEE international conference on Automated software engineering, pp.55-66, September 2014.
13. Kalaee, A. and Rafe, V.An optimal solution for test case generation using ROBDD graph and PSO algorithm. Quality and Reliability Engineering International,32(7), pp.2263-2279, 2016.
14. DATPROF, https://www.datprof.com. Accessed 5 July 2020.
15. mockaroo, https://www.mockaroo.com. Accessed 5 July 2020.
16. Randoop, https://randoop.github.io/randoop. Accessed 5 July 2020.
17. Pacheco, C. and Ernst, M.D.Randoop: feedback-directed random testing for Java. InCompanion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companion, pp. 815-816, October 2007.
18. Angerer F., Grimmer A., Prähofer H. and Grünbacher P.Change impact analysis for maintenance and evolution of variable software systems. Automated Software Engineering,26(2), pp.417-461, 2019.
19. Intana, A. and Sriraksa, T.Impact Analysis Framework of Test Cases Based on Changes of Use Case Based Requirements. In2019 23rd International Computer Science and Engineering Conference (ICSEC). IEEE, pp. 230-235, 2019.
20. Parashar, P., Bhatia, R. and Kalia, A.Change impact analysis: A tool for effective regression testing. In International Conference on Information Intelligence, Systems, Technology and Management, Springer, Berlin, Heidelberg, pp. 160-169, March 2011
21. Duran, J.W. and Ntafos, S.C.An evaluation of random testing. IEEE transactions on Software Engineering,(4), pp.438-444, 1984.
22. Hamlet, R. and Maciniak, J.Random testing, Encyclopedia of software engineering.Wiley: New York, pp.970-978, 1994.
23. Bueno, P.M., Jino, M. and Wong, W.E.Diversity oriented test data generation using metaheuristic search techniques.Information Sciences, 259, pp.490-509, 2014.
24. Clarke L.A.A system to generate test data and symbolically execute programs. IEEE Transactions on software engineering,(3), pp.215-222, 1976.
25. King J.C.Symbolic execution and program testing. Communications of the ACM,19(7), pp.385-394, 1976.
26. Cadar, C. and Sen, K.Symbolic execution for software testing: three decades later. Communications of the ACM,56(2), pp.82-90, 2013.
27. Zaddach J., Bruno L., Francillon A. and Balzarotti D.AVATAR: A Framework to Support Dynamic Security Analysis of Embedded Systems' Firmwares. InNDSS, 23, pp. 1-16, February 2014.
28. Gao R., Hu L., Wong W.E., Lu H.L. and Huang S.K.Effective test generation for combinatorial decision coverage. In 2016 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C). IEEE, pp. 47-54, August 2016.
29. Cadar, C., Dunbar, D. and Engler, D.R.Klee: unassisted and automatic generation of high-coverage tests for complex systems programs. InOSDI, 8, pp. 209-224, December 2008.
30. Bucur, S., Kinder, J. and Candea, G.Prototyping symbolic execution engines for interpreted languages. InProceedings of the 19th international conference on Architectural support for programming languages and operating systems, pp. 239-254, February 2014.
31. Burnim, J. and Sen, K.Heuristics for scalable dynamic test generation. In 2008 23rd IEEE/ACM International Conference on Automated Software Engineering. IEEE, pp. 443-446, September 2008.
32. angr, http://angr.io. Accessed 5 July 2020.
33. Cadar C., Godefroid P., Khurshid S., Pasareanu C.S., Sen K., Tillmann N. and Visser W.Symbolic execution for software testing in practice: preliminary assessment. In 2011 33rd International Conference on Software Engineering (ICSE). IEEE, pp. 1066-1071, May 2011.
34. Harman M., Hu L., Hierons R., Wegener J., Sthamer H., Baresel A. and Roper M.Testability transformation. IEEE Transactions on Software Engineering,30(1), pp.3-16, 2004.
35. Cadar C.Targeted program transformations for symbolic execution. InProceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, pp. 906-909, August 2015.
36. Dong S., Olivo O., Zhang L. and Khurshid S.Studying the influence of standard compiler optimizations on symbolic execution. In 2015 IEEE 26th International Symposium on Software Reliability Engineering (ISSRE). IEEE, pp. 205-215, November 2015.
37. Converse, H., Olivo, O. and Khurshid, S.Non-semantics-preserving transformations for higher-coverage test generation using symbolic execution. In 2017 IEEE International Conference on Software Testing, Verification and Validation (ICST). IEEE, pp. 241-252, March 2017.
38. Weiser M.Program slicing. IEEE Transactions on software engineering,(4), pp.352-357, 1984.
39. Godefroid, P. and Luchaup, D.Automatic partial loop summarization in dynamic test generation. InProceedings of the 2011 International Symposium on Software Testing and Analysis, pp. 23-33, July 2011.
40. Li Y., Su Z., Wang L. and Li X.Steering symbolic execution to less traveled paths. ACM SigPlan Notices,48(10), pp.19-32, 2013.
41. Person S., Yang G., Rungta N. and Khurshid S.Directed incremental symbolic execution. Acm Sigplan Notices,46(6), pp.504-515, 2011.
42. Siddiqui, J.H. and Khurshid, S.Scaling symbolic execution using ranged analysis. ACM SIGPLAN Notices,47(10), pp.523-536, 2012.
43. KLEE, https://klee.github.io. Accessed 5 July 2020.
44. LLVM, http://llvm.org. Accessed 5 July 2020.
45. KLEE's options, https://klee.github.io/docs/options. Accessed 5 July 2020.
46. Kapus, T. and Cadar, C.Automatic testing of symbolic execution engines via program generation and differential testing. In 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, pp. 590-600, October 2017.
47. Rullán M., Oliver J., Ferrer C. and Blom F.C.Testability enhancement of a basic set of CMOS cells. Quality and reliability engineering international,10(4), pp.279-288, 1994.
48. Kansomkeat, S. and Rivepiboon, W.An analysis technique to increase testability of object‐oriented components. Software testing, verification and reliability,18(4), pp.193-219, 2008.
49. GCC, https://gcc.gnu.org. Accessed 5 July 2020.
50. Gallagher K.B.,J., R. Lyle. Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering,17(8), pp.751-761, 1991.
51. Lanubile, F. and Visaggio, G.Extracting reusable functions by flow graph based program slicing. IEEE Transactions on Software Engineering,23(4), pp.246-259, 1997.
52. De Lucia, A., Fasolino, A.R. and Munro, M. Understanding function behaviors through program slicing. In WPC'96. 4th Workshop on Program Comprehension. IEEE, pp. 9-18, March 1996.
53. Cheney J.Program slicing and data provenance. IEEE Data Eng. Bull.,30(4), pp.22-28, 2007.
54. Li X., Cao Y., Feng Z. and Liu R.Web service security analysis model based on program slicing. In 2010 10th International Conference on Quality Software. IEEE, pp. 422-428, July, 2010.
55. Zhang, Z. and Lin, M.Program slicing research based on MSV in software security field. In 2011 6th International Conference on Computer Science & Education (ICCSE). IEEE, pp. 1107-1110, August 2011.
56. Wang, Y., Li, Z. and Guo, T.Program slicing stored XSS bugs in web application. In 2011 Fifth International Conference on Theoretical aspects of software engineering. IEEE, pp. 191-194, August 2011.
57. Talukder, M., Islam, S. and Falcarin, P.Analysis of obfuscated code with program slicing. In 2019 International Conference on Cyber Security and Protection of Digital Services (Cyber Security). IEEE, pp. 1-7, June 2019.
58. Sahoo, S. and Ray, A.A framework for optimization of regression testing of web services using slicing. In 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI). IEEE, pp. 1017-1022, September 2017.
59. Tip F.Survey of program slicing techniques, Journal of Programming Languages. 3, 1995.
60. Y. T.Song and D. T. Huynh, “Forward Dynamic Object-Oriented Program Slicing,” in Proceedings of the 1999 IEEE Symposium on Application-Specific Systems and Software Engineering and Technology, Richardson, TX, USA, pp. 230-237, Mar 1999.
61. Samuel, P. and Surendran, A.Forward slicing algorithm based test data generation. In 2010 3rd International Conference on Computer Science and Information Technology, 8. IEEE, pp. 270-274, July 2010.
62. Alomari, H.W., Collard, M.L. and Maletic, J.I.A very efficient and scalable forward static slicing approach. In 2012 19th Working Conference on Reverse Engineering. IEEE, pp. 425-434, October 2012.
63. Lei, Y., Mao, X. and Chen, T.Y.Backward-slice-based statistical fault localization without test oracles. In 2013 13th International Conference on Quality Software. IEEE, pp. 212-221, July 2013.
64. Giffhorn, D. and Hammer, C.Precise slicing of concurrent programs. Automated Software Engineering,16(2), pp.197-234, 2009.
65. Nanda, M.G. and Ramesh, S.Interprocedural slicing of multithreaded programs with applications to Java. ACM Transactions on Programming Languages and Systems (TOPLAS),28(6), pp.1088-1144, 2006.
66. Krinke J.Context-sensitive slicing of concurrent programs. InProceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, pp. 178-187, September 2003.
67. Arora, V., Bhatia, R.K. and Singh, M. Evaluation of flow graph and dependence graphs for program representation. International Journal of Computer Applications, 56(14), 2012.
68. Frama-C, https://frama-c.com/index.html. Accessed 5 July 2020.
69. dg, https://github.com/mchalupa/dg. Accessed 5 July 2020.
70. M. Chalupa, Slicing of LLVM Bitcode, Masaryk University, 2016.
71. Coreutils 6.11, https://ftp.gnu.org/gnu/coreutils. Accessed 5 July 2020.
72. gcov, https://gcc.gnu.org/onlinedocs/gcc/Gcov.html. Accessed 5 July 2020.