On Characteristics of Symbolic Execution in the Problem of Assessing the Quality of Obfuscating Transformations

Obfuscation is used to protect programs from analysis and reverse engineering. There are theoretically effective and resistant obfuscation methods, but most of them are not implemented in practice yet. The main reasons are large overhead for the execution of obfuscated code and the limitation of application only to a specific class of programs. On the other hand, a large number of obfuscation methods have been developed that are applied in practice. The existing approaches to the assessment of such obfuscation methods are based mainly on the static characteristics of programs. Therefore, the comprehensive (taking into account the dynamic characteristics of programs) justification of their effectiveness and resistance is a relevant task. It seems that such a justification can be made using machine learning methods, based on feature vectors that describe both static and dynamic characteristics of programs. In this paper, it is proposed to build such a vector on the basis of characteristics of two compared programs: the original and obfuscated, original and deobfuscated, obfuscated and deobfuscated. In order to obtain the dynamic characteristics of the program, a scheme based on a symbolic execution is constructed and presented in this paper. The choice of the symbolic execution is justified by the fact that such characteristics can describe the difficulty of comprehension of the program in dynamic analysis. The paper proposes two implementations of the scheme: extended and simplified. The extended scheme is closer to the process of analyzing a program by an analyst, since it includes the steps of disassembly and translation into intermediate code, while in the simplified scheme these steps are excluded. In order to identify the characteristics of symbolic execution that are suitable for assessing the effectiveness and resistance of obfuscation based on machine learning methods, experiments with the developed schemes were carried out. Based on the obtained results, a set of suitable characteristics is determined.

1. C. Collberg and C. Ерomborson, “Watermarking, Tamper-Proofing, and Obfuscation - Tools for Software Protection”, IEEE Transactions on Software Engineering, vol. 28, pp. 735–746, Aug. 2002. doi: 10.1109/TSE.2002.1027797.

2. S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B.Waters, “Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits”, in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 40–49. doi: 10.1109/FOCS.2013.13.

3. H. Xu, Y. Zhou, J. Ming, and M. Lyu, “Layered obfuscation: a taxonomy of software obfuscation techniques for layered security”, Cybersecurity, vol. 3, p. 9, Apr. 2020. doi: 10.1186/s42400-020-00049-3.

4. C. Collberg, C. Thomborson, and D. Low, “A Taxonomy of Obfuscating Transformations”, Tech. Report, N 148, Dept. of Computer Science, Univ. of Auckland, Jul. 1997.

5. Y. Kanzaki, A. Monden, and C. Collberg, “Code Artificiality: A Metric for the Code Stealth Based on an N-Gram Model”, in 2015 IEEE/ACM 1st International Workshop on Software Protection, 2015, pp. 31–37. doi: 10.1109/SPRO.2015.14.

6. R. Mohsen and A. Pinto, “Algorithmic Information Theory for Obfuscation Security”, in Proceedings of the 12th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2015), 2015, pp. 76–87. doi: 10.5220/0005548200760087.

7. R. Mohsen and A. Pinto, “Evaluating Obfuscation Security: A Quantitative Approach”, in International Symposium on Foundations and Practice of Security, Springer, Oct. 2015, pp. 174–192, isbn: 978-3-319-30302-4. doi: 10.1007/978-3-319-30303-1_11.

8. M. Ceccato, M. Di Penta, J. Nagra, P. Falcarin, F. Ricca, M. Torchiano, and P. Tonella, “The Effectiveness of Source Code Obfuscation: an Experimental Assessment”, in 2009 IEEE 17th International Conference on Program Comprehension, May 2009, pp. 178–187. doi: 10.1109/ICPC.2009.5090041.

9. J. Siegmund, “Program Comprehension: Past, Present, and Future”, in 2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER), vol. 5, Mar. 2016, pp. 13–20. doi: 10.1109/SANER.2016.35.

10. E. Avidan and D. Feitelson, “From Obfuscation to Comprehension”, in 2015 IEEE 23rd International Conference on Program Comprehension, May 2015, pp. 178–181. doi: 10.1109/ICPC.2015.27.

11. P. Borisov and Y. Kosolapov, “On the Automatic Analysis of the Practical Resistance of Obfusting Transformations”, Modeling and Analysis of Information Systems, vol. 26, no. 3, pp. 317–331, Sep. 2019. doi: 10.18255/1818-1015-2019-3-317-331.

12. J. King, “Symbolic Execution and Program Testing”, Commun. ACM, vol. 19, no. 7, pp. 385–394, Jul. 1976. doi: 10.1145/360248.360252.

13. B. Yadegari and S. Debray, “Symbolic Execution of Obfuscated Code”, in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Oct. 2015, pp. 732–744. doi: 10.1145/2810103.2813663.

14. C. La‹ner and V. Adve, “LLVM: A Compilation Framework for Lifelong Program Analysis and Transformation”, in Proceedings of the International Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization, ser. CGO ’04, USA: IEEE Computer Society, 2004, pp. 75–86, isbn: 0769521029.

15. P. F. Brown, P. V. deSouza, R. L. Mercer, V. J. D. Pietra, and J. C. Lai, “Class-Based n-Gram Models of Natural Language”, Comput. Linguist., vol. 18, no. 4, pp. 467–479, Dec. 1992, issn: 0891-2017.

16. N. Zhang, Hikari – an improvement over Obfuscator-LLVM, 2017.

17. A. Dinaburg and A. Ruef, “Mcsema: Static translation of x86 instructions to llvm”, in ReCon 2014 Conference, Montreal, Canada, 2014.

18. C. Cadar and M. Nowack, “KLEE symbolic execution engine in 2019”, International Journal on Software Tools for Technology Transfer, Jun. 2020. doi: 10.1007/s10009-020-00570-3.

19. S. Muchnick, Advanced Compiler Design Implementation. 1997, isbn: 9781558603202.

20. C. Eagle, Œe IDA pro book: the unoffcial guide to the world’s most popular disassembler, 2nd ed. No Starch Press, isbn: 1593273959.

21. G. Ravipati, A. R. Bernat, N. Rosenblum, B. P. Miller, and J. K. Hollingsworth, “Towards the Deconstruction of Dyninst”, UW Madison, Tech. Rep., Jul. 2007, pp. 1–9.

22. R. N. Horspool and N. Marovac, “An approach to the problem of detranslation of computer programs”, The Computer Journal, vol. 23, no. 3, pp. 223–229, 1980.

23. C. Visual and B. Unit, Microsoft portable executable and common object file format specification, 1999.

24. H. Lu, Elf: From the programmer’s perspective, 1995.

25. J. Kroustek, P. Matula, J. Konˇcickˇy, and D. Kol´a´r, “Accurate Retargetable Decompilation Using Additional Debugging Information”, Jan. 2012.

26. S. Dasgupta, S. Dinesh, D. Venkatesh, V. S. Adve, and C. W. Fletcher, “Scalable validation of binary lifters”, Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 655–671, 2020.

27. S. Banescu, C. Collberg, V. Ganesh, Z. Newsham, and A. Pretschner, “Code obfuscation against symbolic execution attacks”, Dec. 2016, pp. 189–200. doi: 10.1145/2991079.2991114.

28. P. Junod, J. Rinaldini, J. Wehrli, and J. Michielin, “Obfuscator-LLVM – Software Protection for the Masses”, May 2015, pp. 3–9. doi: 10.1109/SPRO.2015.10.

29. T. Laszl´o and ´A. Kiss, “Obfuscating C++ Programs via Control Flow Flattening”, ´ Annales Universitatis Scientiarum Budapestinensis de Rolando Eotv¨os Nominatae. Sectio Computatorica, vol. 30, no. 1, pp. 3–19, 2009.

30. Y. Kosolapov and P. Borisov, “Similarity Features For The Evaluation Of Obfuscation Effectiveness”, in 2020 International Conference on Decision Aid Sciences and Application (DASA), 2020, pp. 898–902. doi: 10.1109/DASA51403.2020.9317301.