research-article

How to kill symbolic deobfuscation for free (or: unleashing the potential of path-oriented protections)

Authors:

Mathilde Ollivier,

Sébastien Bardin,

Richard Bonichon,

Jean-Yves MarionAuthors Info & Claims

ACSAC '19: Proceedings of the 35th Annual Computer Security Applications Conference

Pages 177 - 189

https://doi.org/10.1145/3359789.3359812

Published: 09 December 2019 Publication History

Abstract

Code obfuscation is a major tool for protecting software intellectual property from attacks such as reverse engineering or code tampering. Yet, recently proposed (automated) attacks based on Dynamic Symbolic Execution (DSE) shows very promising results, hence threatening software integrity. Current defenses are not fully satisfactory, being either not efficient against symbolic reasoning, or affecting runtime performance too much, or being too easy to spot. We present and study a new class of anti-DSE protections coined as path-oriented protections targeting the weakest spot of DSE, namely path exploration. We propose a lightweight, efficient, resistant and analytically proved class of obfuscation algorithms designed to hinder DSE-based attacks. Extensive evaluation demonstrates that these approaches critically counter symbolic deobfuscation while yielding only a very slight overhead.

References

[1]

Tigress challenge. http://tigress.cs.arizona.edu/challenges.html.

[2]

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. Journal of Systems and Software, 2013.

Digital Library

[3]

Thanassis Avgerinos, Alexandre Rebert, Sang Kil Cha, and David Brumley. Enhancing symbolic execution with veritesting. Commun. ACM, 59(6), 2016.

[4]

Gogul Balakrishnan and Thomas W. Reps. WYSINWYX: what you see is not what you execute. ACM Trans. Program. Lang. Syst., 32, 2010.

[5]

Sebastian Banescu, Christian S. Collberg, Vijay Ganesh, Zack Newsham, and Alexander Pretschner. Code obfuscation against symbolic execution attacks. In Annual Conference on Computer Security Applications, ACSAC 2016, 2016.

Digital Library

[6]

Sebastian Banescu, Christian S. Collberg, and Alexander Pretschner. Predicting the resilience of obfuscated code against symbolic execution attacks via machine learning. In USENIX Security Symposium, 2017.

[7]

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Advances in Cryptology - CRYPTO, 2001.

Digital Library

[8]

Sébastien Bardin, Robin David, and Jean-Yves Marion. Backward-bounded DSE: targeting infeasibility questions on obfuscated codes. In 2017 IEEE Symposium on Security and Privacy, SP, 2017.

[9]

Clark Barrett and Cesare Tinelli. Satisfiability Modulo Theories. Springer International Publishing, 2018.

[10]

Armin Biere. Bounded Model Checking. In Handbook of Satisfiability. 2009.

Digital Library

[11]

Fabrizio Biondi, Sébastien Josse, Axel Legay, and Thomas Sirvent. Effectiveness of synthesis in concolic deobfuscation. Computers & Security, 70, 2017.

[12]

Guillaume Bonfante, José M. Fernandez, Jean-Yves Marion, Benjamin Rouxel, Fabrice Sabatier, and Aurélien Thierry. Codisasm: Medium scale concatic disassembly of self-modifying binaries with overlapping instructions. In Conference on Computer and Communications Security, 2015.

[13]

David Brumley, Cody Hartwig, Zhenkai Liang, James Newsome, Dawn Xiaodong Song, and Heng Yin. Automatically identifying trigger-based behavior in malware. In Wenke Lee, Cliff Wang, and David Dagon, editors, Botnet Detection: Countering the Largest Security Threat, volume 36 of Advances in Information Security, pages 65--88. Springer, 2008.

[14]

Robert Brummayer and Armin Biere. Boolector: An efficient SMT solver for bit-vectors and arrays. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS, 2009.

Digital Library

[15]

Roberto Bruni, Roberto Giacobazzi, and Roberta Gori. Code obfuscation against abstract model checking attacks. In Verification, Model Checking, and Abstract Interpretation - 19th International Conference, VMCAI, 2018.

[16]

Cristian Cadar. Targeted program transformations for symbolic execution. In Meeting on Foundations of Software Engineering, ESEC/FSE, 2015.

Digital Library

[17]

Cristian Cadar, Daniel Dunbar, and Dawson R. Engler. KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs. In 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI, 2008.

Digital Library

[18]

Cristian Cadar and Koushik Sen. Symbolic execution for software testing: three decades later. Commun. ACM, 56(2), 2013.

[19]

Mariano Ceccato, Paolo Tonella, Cataldo Basile, Paolo Falcarin, Marco Torchiano, Bart Coppens, and Bjorn De Sutter. Understanding the behaviour of hackers while performing attack tasks in a professional setting and in a public challenge. Empirical Software Engineering, 24(1):240--286, Feb 2019.

Digital Library

[20]

Sang Kil Cha, Thanassis Avgerinos, Alexandre Rebert, and David Brumley. Unleashing mayhem on binary code. In Symposium on Security and Privacy, SP, 2012.

Digital Library

[21]

Christian Collberg and Jasvir Nagra. Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection. Addison-Wesley Professional, 1st edition, 2009.

[22]

Christian Collberg, Clark Thomborson, and Douglas Low. A taxonomy of obfuscating transformations, 1997.

[23]

Christian S. Collberg, Sam Martin, Jonathan Myers, and Jasvir Nagra. Distributed application tamper detection via continuous software updates. In Annual Computer Security Applications Conference, ACSAC, 2012.

Digital Library

[24]

Kevin Coogan, Gen Lu, and Saumya K. Debray. Deobfuscation of virtualization-obfuscated software: a semantics-based approach. In Conference on Computer and Communications Security, CCS, 2011.

Digital Library

[25]

Robin David, Sébastien Bardin, Josselin Feist, Laurent Mounier, Marie-Laure Potet, Thanh Dinh Ta, and Jean-Yves Marion. Specification of concretization and symbolization policies in symbolic execution. In International Symposium on Software Testing and Analysis, ISSTA 2016, 2016.

Digital Library

[26]

Robin David, Sébastien Bardin, Thanh Dinh Ta, Laurent Mounier, Josselin Feist, Marie-Laure Potet, and Jean-Yves Marion. BINSEC/SE: A dynamic symbolic execution toolkit for binary-level analysis. In IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering, SANER, 2016.

[27]

Leonardo Mendonça de Moura and Nikolaj Bjørner. Z3: an efficient SMT solver. In Tools and Algorithms for the Construction and Analysis of Systems, TACAS, 2008.

[28]

Saumya K. Debray and Jay Patel. Reverse engineering self-modifying code: Unpacker extraction. In Working Conference on Reverse Engineering, WCRE, 2010.

[29]

Ninon Eyrolles, Louis Goubin, and Marion Videau. Defeating mba-based obfuscation. In Proceedings of the 2016 ACM Workshop on Software PROtection, SPRO@CCS 2016, 2016.

Digital Library

[30]

Patrice Godefroid, Michael Y. Levin, and David A. Molnar. SAGE: whitebox fuzzing for security testing. Commun. ACM, 55(3), 2012.

[31]

Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar, and Grégoire Sutre. Lazy abstraction. In The 29th SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), 2002.

Digital Library

[32]

Min Gyung Kang, Pongsin Poosankam, and Heng Yin. Renovo: a hidden code extractor for packed executables. In ACM Workshop Recurring Malcode (WORM). ACM, 2007.

[33]

Johannes Kinder. Towards static analysis of virtualization-obfuscated binaries. In 19th Working Conference on Reverse Engineering, WCRE, 2012.

Digital Library

[34]

Dave King, Boniface Hicks, Michael Hicks, and Trent Jaeger. Implicit flows: Can't live with 'em, can't live without 'em. In Information Systems Security, 4th International Conference, ICISS, 2008.

[35]

Yin Liu and Ana Milanova. Static information flow analysis with handling of implicit flows and a study on effects of implicit flows vs explicit flows. In 14th European Conference on Software Maintenance and Reengineering, CSMR, 2010.

[36]

Saeed Nejati, Jia Hui Liang, Catherine H. Gebotys, Krzysztof Czarnecki, and Vijay Ganesh. Adaptive restart and cegar-based solver for inverting cryptographic hash functions. In VSTTE, 2017.

[37]

Jonathan Salwan, Sébastien Bardin, and Marie-Laure Potet. Symbolic deobfuscation: from virtualized code back to the original. In 5th Conference on Detection of Intrusions and malware & Vulnerability Assessment (DIMVA), 2018.

[38]

Florent Saudel and Jonathan Salwan. Triton : Framework d'exÃl'cution concolique. In SSTIC, 2015.

[39]

Sebastian Schrittwieser, Stefan Katzenbeisser, Johannes Kinder, Georg Merzdovnik, and Edgar Weippl. Protecting software through obfuscation: Can it keep pace with progress in code analysis? ACM Comput. Surv., 49(1), 2016.

[40]

Edward J. Schwartz, Thanassis Avgerinos, and David Brumley. All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask). In Symposium on Security and Privacy, S&P, 2010.

Digital Library

[41]

Hovav Shacham. The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86). In Conference on Computer and Communications Security, CCS, 2007.

Digital Library

[42]

Monirul I. Sharif, Andrea Lanzi, Jonathon T. Giffin, and Wenke Lee. Impeding malware analysis using conditional code obfuscation. In Network and Distributed System Security Symposium, NDSS, 2008.

[43]

Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario Polino, Andrew Dutcher, John Grosen, Siji Feng, Christophe Hauser, Christopher Krügel, and Giovanni Vigna. SOK: (state of) the art of war: Offensive techniques in binary analysis. In IEEE Symposium on Security and Privacy, SP, 2016.

[44]

Venkatesh Srinivasan and Thomas W. Reps. An improved algorithm for slicing machine code. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2016. ACM.

[45]

Jon Stephens, Babak Yadegari, Christian S. Collberg, Saumya Debray, and Carlos Scheidegger. Probabilistic obfuscation through covert channels. In European Symposium on Security and Privacy, EuroS&P, 2018.

[46]

Julien Vanegue and Sean Heelan. SMT solvers in software security. In 6th USENIX Workshop on Offensive Technologies, WOOT'12, 2012.

[47]

Chenxi Wang, Jonathan Hill, John Knight, and Jack Davidson. Software tamper resistance: Obstructing static analysis of programs. Technical report, Charlottesville, VA, USA, 2000.

[48]

Chenxi Wang, Jonathan Hill, John C. Knight, and Jack W. Davidson. Protection of software-based survivability mechanisms. In International Conference on Dependable Systems and Networks (DSN), 2001.

[49]

Zhi Wang, Jiang Ming, Chunfu Jia, and Debin Gao. Linear obfuscation to combat symbolic execution. In European Symposium on Research in Computer Security, ESORICS, 2011.

[50]

Babak Yadegari and Saumya Debray. Symbolic execution of obfuscated code. In Conference on Computer and Communications Security (CCS), 2015.

Digital Library

[51]

Babak Yadegari, Brian Johannesmeyer, Ben Whitely, and Saumya Debray. A generic approach to automatic deobfuscation of executable code. In Symposium on Security and Privacy, SP, 2015.

Digital Library

[52]

Yongxin Zhou, Alec Main, Yuan Xiang Gu, and Harold Johnson. Information hiding in software with mixed boolean-arithmetic transforms. In Information Security Applications, WISA, 2007.

Cited By

De Sutter BSchrittwieser SCoppens BKochberger P(2024)Evaluation Methodologies in Software Protection ResearchACM Computing Surveys10.1145/3702314Online publication date: 2-Nov-2024
https://doi.org/10.1145/3702314
Black CScott-Hayward S(2024)Defeating Data Plane Attacks With Program ObfuscationIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.327793921:3(1317-1330)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3277939
Benoit TMarion JBardin SChandra SBlincoe KTonella P(2023)Scalable Program Clone Search through Spectral AnalysisProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616279(808-820)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616279
Show More Cited By

Index Terms

How to kill symbolic deobfuscation for free (or: unleashing the potential of path-oriented protections)
1. Security and privacy
2. Software and its engineering
  1. Software organization and properties
    1. Software functional properties
      1. Formal methods

Recommendations

N-version Obfuscation
CPSS '16: Proceedings of the 2nd ACM International Workshop on Cyber-Physical System Security

Although existing for decades, software tampering attack is still a main threat to systems, such as Android, and cyber physical systems. Many approaches have been proposed to thwart specific procedures of tampering, e.g., obfuscation and self-...
A Novel Software Protection Approach for Code Obfuscation to Enhance Software Security

Over the past few decades ago, software developers analyzed robustly several forms of software protection against illegal copying or piracy. With the expansion in digital technology, the risk of illegal copying of software also amplifies. The increasing ...
Teaching Cyber Security Using Competitive Software Obfuscation and Reverse Engineering Activities
SIGCSE '18: Proceedings of the 49th ACM Technical Symposium on Computer Science Education

Teaching cyber security techniques can be challenging due to the complexity associated with building secure systems. The major issue is these systems could easily be broken if proper protection techniques are not employed. This requires students to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ACSAC '19: Proceedings of the 35th Annual Computer Security Applications Conference

December 2019

821 pages

ISBN:9781450376280

DOI:10.1145/3359789

Conference Chair:
David Balenson
SRI International

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 December 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ACSAC '19

ACSAC '19: 2019 Annual Computer Security Applications Conference

December 9 - 13, 2019

Puerto Rico, San Juan, USA

Acceptance Rates

ACSAC '19 Paper Acceptance Rate 60 of 266 submissions, 23%;

Overall Acceptance Rate 104 of 497 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
393
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

De Sutter BSchrittwieser SCoppens BKochberger P(2024)Evaluation Methodologies in Software Protection ResearchACM Computing Surveys10.1145/3702314Online publication date: 2-Nov-2024
https://doi.org/10.1145/3702314
Black CScott-Hayward S(2024)Defeating Data Plane Attacks With Program ObfuscationIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.327793921:3(1317-1330)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3277939
Benoit TMarion JBardin SChandra SBlincoe KTonella P(2023)Scalable Program Clone Search through Spectral AnalysisProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616279(808-820)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616279
Zhang PWu CPeng MZeng KYu DLai YKang YWang WWang ZDubach CBruening DHardekopf B(2023)Khaos: The Impact of Inter-procedural Code Obfuscation on Binary Diffing TechniquesProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580007(55-67)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580007
De Pasquale GNakanishi FFerla DCavallaro L(2023)ROPfuscator: Robust Obfuscation with ROP2023 IEEE Security and Privacy Workshops (SPW)10.1109/SPW59333.2023.00026(1-10)Online publication date: May-2023
https://doi.org/10.1109/SPW59333.2023.00026
Todd McDonald JManikyam RBardin SBonichon RAndel TCarambat J(2023)Evaluating Defensive Countermeasures for Software-Based Hardware AbstractionE-Business and Telecommunications10.1007/978-3-031-36840-0_13(281-304)Online publication date: 22-Jul-2023
https://doi.org/10.1007/978-3-031-36840-0_13
Jung CKim DChen AWang WZheng YLee KKwon YDwyer MDamian DZeller A(2022)Hiding critical program components via ambiguous translationProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510139(1120-1132)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510139
Van den Broeck JCoppens BDe Sutter B(2022)Flexible software protectionComputers and Security10.1016/j.cose.2022.102636116:COnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.cose.2022.102636
Banescu SValenzuela SGuggenmos MAhmadvand MPretschner A(2021)Dynamic Taint Analysis versus Obfuscated Self-CheckingProceedings of the 37th Annual Computer Security Applications Conference10.1145/3485832.3485926(182-193)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3485832.3485926
Menguy GBardin SBonichon RLima CKim YKim JVigna GShi E(2021)Search-Based Local Black-Box DeobfuscationProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3485337(2384-2386)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3485337
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents