maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2021-1-38-51mais-1471Research ArticleComputer System OrganizationО характеристиках символьного исполнения в задаче оценки качества обфусцирующих преобразованийOn Characteristics of Symbolic Execution in the Problem of Assessing the Quality of Obfuscating Transformationshttps://orcid.org/0000-0002-8919-8310БорисовПетр ДмитриевичBorisovPetr D.

Аспирант

ул. Мильчакова, 8а, г. Ростов-на-Дону, 344090

Postgraduate student

8a Milchakova str., Rostov-on-Don 344090

borisovpetr@mail.ruhttps://orcid.org/0000-0002-1491-524XКосолаповЮрий ВладимировичKosolapovYury V.

Кандидат технических наук

ул. Мильчакова, 8а, г. Ростов-на-Дону, 344090

PhD

8a Milchakova str., Rostov-on-Don 344090

itaim@mail.ruЮжный Федеральный УниверситетРоссияSouthern Federal UniversityRussian Federation2021230320212813851Copyright © Борисов П.Д., Косолапов Ю.В., 20212021Борисов П.Д., Косолапов Ю.В.Borisov P.D., Kosolapov Y.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1471

Обфускация применяется для защиты программ от анализа и обратного проектирования. Несмотря на то, что в настоящее время существуют теоретически стойкие методы обфускации, эти методы пока не могут применяться на практике. В основном это связано либо с затратностью по ресурсам на исполнение обфусцированного кода, либо с ограничением на применение только к конкретному классу программ. С другой стороны, разработано большое количество методов обфускации, которые применяются на практике. Существующие подходы к оценке таких обфусцирующих преобразований в большей степени основаны на статических характеристиках программ. Однако актуальна задача комплексного (учитывающего и динамические характеристики программ) обоснования их эффективности и стойкости. Представляется, что такое обоснование может быть выполнено с помощью методов машинного обучения на основе векторов признаков, описывающих как статические, так и динамические характеристики программ. В настоящей работе такой вектор предлагается строить на основе характеристик пар сравниваемых программ: исходной и обфусцированной, исходной и деобфусцированной, обфусцированной и деобфусцированной. Для получения динамических характеристик программы в работе построена схема, основанная на символьном исполнении. Выбор символьного исполнения обосновывается тем, что такие характеристики могут описать сложность понимания программы при динамическом анализе. В работе предлагается две реализации схемы: расширенная и упрощенная. Расширенная схема приближена к процессу анализа программы аналитиком, так как включает в себя этапы дизассемблирования и трансляции в промежуточный код, в то время как в упрощенной схеме эти этапы исключены. С разработанными схемами проведены эксперименты с целью выявления характеристик символьного исполнения, подходящих для оценки эффективности и стойкости обфускации на основе методов машинного обучения. На основе полученных результатов определен набор подходящих характеристик.

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.

обфускациясимвольное исполнениепохожесть программпонимание программobfuscationsymbolic executionprogram similarityprogram comprehensionReferencesC. 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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.J. King, “Symbolic Execution and Program Testing”, Commun. ACM, vol. 19, no. 7, pp. 385–394, Jul. 1976. doi: 10.1145/360248.360252.J. King, “Symbolic Execution and Program Testing”, Commun. ACM, vol. 19, no. 7, pp. 385–394, Jul. 1976. doi: 10.1145/360248.360252.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.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.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.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.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.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.N. Zhang, Hikari – an improvement over Obfuscator-LLVM, 2017.N. Zhang, Hikari – an improvement over Obfuscator-LLVM, 2017.A. Dinaburg and A. Ruef, “Mcsema: Static translation of x86 instructions to llvm”, in ReCon 2014 Conference, Montreal, Canada, 2014.A. Dinaburg and A. Ruef, “Mcsema: Static translation of x86 instructions to llvm”, in ReCon 2014 Conference, Montreal, Canada, 2014.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.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.S. Muchnick, Advanced Compiler Design Implementation. 1997, isbn: 9781558603202.S. Muchnick, Advanced Compiler Design Implementation. 1997, isbn: 9781558603202.C. Eagle, Œe IDA pro book: the unoffcial guide to the world’s most popular disassembler, 2nd ed. No Starch Press, isbn: 1593273959.C. Eagle, Œe IDA pro book: the unoffcial guide to the world’s most popular disassembler, 2nd ed. No Starch Press, isbn: 1593273959.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.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.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.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.C. Visual and B. Unit, Microsoft portable executable and common object file format specification, 1999.C. Visual and B. Unit, Microsoft portable executable and common object file format specification, 1999.H. Lu, Elf: From the programmer’s perspective, 1995.H. Lu, Elf: From the programmer’s perspective, 1995.J. Kroustek, P. Matula, J. Konˇcickˇy, and D. Kol´a´r, “Accurate Retargetable Decompilation Using Additional Debugging Information”, Jan. 2012.J. Kroustek, P. Matula, J. Konˇcickˇy, and D. Kol´a´r, “Accurate Retargetable Decompilation Using Additional Debugging Information”, Jan. 2012.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.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.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.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.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.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.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.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.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.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.

The authors declare that there are no conflicts of interest present.