research-article

Public Access

LOOP: Logic-Oriented Opaque Predicate Detection in Obfuscated Binary Code

Authors:

Dinghao WuAuthors Info & Claims

CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

Pages 757 - 768

https://doi.org/10.1145/2810103.2813617

Published: 12 October 2015 Publication History

Abstract

Opaque predicates have been widely used to insert superfluous branches for control flow obfuscation. Opaque predicates can be seamlessly applied together with other obfuscation methods such as junk code to turn reverse engineering attempts into arduous work. Previous efforts in detecting opaque predicates are far from mature. They are either ad hoc, designed for a specific problem, or have a considerably high error rate. This paper introduces LOOP, a Logic Oriented Opaque Predicate detection tool for obfuscated binary code. Being different from previous work, we do not rely on any heuristics; instead we construct general logical formulas, which represent the intrinsic characteristics of opaque predicates, by symbolic execution along a trace. We then solve these formulas with a constraint solver. The result accurately answers whether the predicate under examination is opaque or not. In addition, LOOP is obfuscation resilient and able to detect previously unknown opaque predicates. We have developed a prototype of LOOP and evaluated it with a range of common utilities and obfuscated malicious programs. Our experimental results demonstrate the efficacy and generality of LOOP. By integrating LOOP with code normalization for matching metamorphic malware variants, we show that LOOP is an appealing complement to existing malware defenses.

References

[1]

H. Agrawal and J. R. Horgan. Dynamic program slicing. ACM SIGPLAN Notices, 25(6):246--256, 1990.

Digital Library

[2]

B. Anckaert, M. Madou, B. D. Sutter, B. D. Bus, K. D. Bosschere, and B. Preneel. Program obfuscation: a quantitative approach. In Proceedings of the 2007 ACM workshop on Quality of Protection (QoP'07), 2007.

Digital Library

[3]

G. Arboit. A method for watermarking Java programs via opaque predicates. In Proceedings of 5th International Conference on Electronic Commerce Research (ICECR-5), 2002.

[4]

A. Banerjee, A. Roychoudhury, J. A. Harlie, and Z. Liang. Golden implementation driven software debugging. In Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE'10), 2010.

Digital Library

[5]

R. Bodık, R. Gupta, and M. L. Soffa. Refining data flow information using infeasible paths. In Proceedings of the 5th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE'97), 1997.

Digital Library

[6]

D. Brumley, J. Caballero, Z. Liang, J. Newsome, and D. Song. Towards automatic discovery of deviations in binary implementations with applications to error detection and fingerprint generation. In Proceedings of 16th USENIX Security Symposium, 2007.

Digital Library

[7]

D. Brumley, I. Jager, T. Avgerinos, and E. J. Schwartz. BAP: A binary analysis platform. In Proceedings of the 23rd international conference on computer aided verification (CAV'11), 2011.

Digital Library

[8]

D. Brumley and J. Newsome. Alias analysis for assembly. Technical Report Carnegie Mellon University-CS-06--180R, School of Computer Science, Carnegie Mellon University, 2006.

[9]

D. Bruschi, L. Martignoni, and M. Monga. Detecting self-mutating malware using control-flow graph matching. In Proceedings of Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA'06), 2006.

Digital Library

[10]

D. Bruschi, L. Martignoni, and M. Monga. Code normalization for self-mutating malware. IEEE Security and Privacy, 5(2), 2007.

Digital Library

[11]

P. M. S. Bueno and M. Jino. Identification of potentially infeasible program paths by monitoring the search for test data. In Proceedings of the 15th IEEE International Conference on Automated Software Engineering (ASE'00), 2000.

Digital Library

[12]

C. Cadar, D. Dunbar, and D. Engler. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the 2008 USENIX Symposium on Operating Systems Design and Implementation (OSDI'08), 2008.

Digital Library

[13]

C. Cadar, V. Ganesh, P. Pawlowski, D. Dill, and D. Engler. EXE: Automatically generating inputs of death. In Proceedings of the 2006 ACM Conference on Computer and Communications Security (CCS'06), 2006.

Digital Library

[14]

J. Cappaert and B. Preneel. A general model for hiding control flow. In Proceedings of the 10th Annual ACM Workshop on Digital Rights Management (DRM'10), 2010.

Digital Library

[15]

H. Chen, L. Yuan, X. Wu, B. Zang, B. Huang, and P.-c. Yew. Control flow obfuscation with information flow tracking. In Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 42), 2009.

Digital Library

[16]

C. Collberg, G. Myles, and A. Huntwork. Sandmark--a tool for software protection research. IEEE Security and Privacy, 1(4):40--49, July 2003.

Digital Library

[17]

C. Collberg, C. Thomborson, and D. Low. A taxonomy of obfuscating transformations. Technical report, The University of Auckland, 1997.

[18]

K. Coogan, G. Lu, and S. Debray. Deobfuscation of virtualization-obfuscated software. In Proceedings of the 18th ACM Conference on Computer and Communications Security (CCS'11), 2011.

Digital Library

[19]

B. Coppens, B. De Sutter, and J. Maebe. Feedback-driven binary code diversification. ACM Transactions on Architecture and Code Optimization (TACO), 9(4), Jan. 2013.

Digital Library

[20]

L. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10):1367--1372, 2004.

Digital Library

[21]

DefenseCode. Diving into recent 0day Javascript obfuscations. http://blog.defensecode.com/2012/10/diving-into-recent-0day-javascript.html, last reviewed, 04/27/2015.

[22]

S. Drape. Intellectual property protection using obfuscation. Technical Report RR-10-02, Oxford University Computing Laboratory, 2010.

[23]

V. Ganesh and D. L. Dill. A decision procedure for bit-vectors and arrays. In Proceedings of the 2007 International Conference in Computer Aided Verification (CAV'07), 2007.

Digital Library

[24]

P. Godefroid, N. Klarlund, and K. Sen. DART: Directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'05), 2005.

Digital Library

[25]

P. Godefroid, M. Y. Levin, and D. Molnar. Automated whitebox fuzz testing. In Proceedings of the 15th Annual Network and Distributed System Security Symposium (NDSS'08), 2008.

[26]

P. Junod, J. Rinaldini, J. Wehrli, and J. Michielin. Obfuscator-LLVM - software protection for the masses. In Proceedings of the 1st International Workshop on Software PROtection (SPRO'15), 2015.

Digital Library

[27]

M. G. Kang, S. McCamant, P. Poosankam, and D. Song. DTA+: Dynamic taint analysis with targeted control-flow propagation. In Proceedings of the 18th Annual Network and Distributed System Security Symposium (NDSS'11), 2011.

[28]

A. Kovacheva. Efficient code obfuscation for Android. Master's thesis, University of Luxembourg, August 2013.

[29]

P. Larsen, A. Homescu, S. Brunthaler, and M. Franz. SoK: Automated software diversity. In Proceedings of the 2014 IEEE Symposium on Security and Privacy (SP'14), 2014.

Digital Library

[30]

C. Linn and S. Debray. Obfuscation of executable code to improve resistance to static disassembly. In Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS'03), 2003.

Digital Library

[31]

L. Liu, J. Ming, Z. Wang, D. Gao, and C. Jia. Denial-of-service attacks on host-based generic unpackers. In Proceedings of the 11th International Conference on Information and Communications Security (ICICS'09), 2009.

Digital Library

[32]

C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation (PLDI'05), 2005.

Digital Library

[33]

M. Madou. Application Security through Program Obfuscation. PhD thesis, Ghent University, September 2007.

[34]

M. Madou, L. Van Put, and K. De Bosschere. LOCO: An interactive code (de)obfuscation tool. In Proceedings of the 2006 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation (PEPM'06), 2006.

Digital Library

[35]

A. Majumdar and C. Thomborson. Securing mobile agents control flow using opaque predicates. In Proceedings of the 9th International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES'05), 2005.

Digital Library

[36]

J. Ming, M. Pan, and D. Gao. iBinHunt: Binary hunting with inter-procedural control flow. In Proceedings of the 15th Annual International Conference on Information Security and Cryptology (ICISC'12), 2012.

Digital Library

[37]

A. Moser, C. Kruegel, and E. Kirda. Limits of static analysis for malware detection. In Proceedings of the 23th Annual Computer Security Applications Conference (ACSAC'07), December 2007.

[38]

L. D. Moura and N. Bjørner. Z3: an efficient SMT solver. In Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2008.

Digital Library

[39]

G. Myles and C. Collberg. Software watermarking via opaque predicates: Implementation, analysis, and attacks. Electronic Commerce Research, 6(2):155 -- 171, April 2006.

Digital Library

[40]

M. N. Ngo and H. B. K. Tan. Detecting large number of infeasible paths through recognizing their patterns. In Proceedings of the the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC-FSE'07), 2007.

Digital Library

[41]

J. Palsberg, S. Krishnaswamy, M. Kwon, D. Ma, Q. Shao, and Y. Zhang. Experience with software watermarking. In Proceedings of the 16th Annual Computer Security Applications Conference (ACSAC'00), 2000.

Digital Library

[42]

M. D. Preda, M. Madou, K. D. Bosschere, and R. Giacobazzi. Opaque predicate detection by abstract interpretation. In Proceedings of 11th International Conference on Algebriac Methodology and Software Technology (AMAST'06), 2006.

Digital Library

[43]

N. A. Quyn. OptiCode: Machine code deobfuscation for malware analysis. In Proceedings of the 2013 SyScan, 2013.

[44]

P. Szor. The Art of Computer Virus Research and Defense. Addison-Wesley Professional, February 2005.

Digital Library

[45]

S. K. Udupa, S. K. Debray, and M. Madou. Deobfuscation: Reverse engineering obfuscated code. In Proceedings of the 12th Working Conference on Reverse Engineering (WCRE'05), 2005.

Digital Library

[46]

C. Wang, J. Hill, J. C. Knight, and J. W. Davidson. Protection of software-based survivability mechanisms. In Proceedings of the 2001 International Conference on Dependable Systems and Networks (DSN'01), 2001.

Digital Library

[47]

S. Wang, P. Wang, and D. Wu. Reassembleable disassembling. In Proceedings of the 24th USENIX Security Symposium (USENIX Security'15), 2015.

Digital Library

[48]

Z. Wang, J. Ming, C. Jia, and D. Gao. Linear obfuscation to combat symbolic execution. In Proceedings of the 2011 European Symposium on Research in Computer Security (ESORICS'11), 2011.

Digital Library

[49]

F. Zhang, D. Wu, P. Liu, and S. Zhu. Program logic based software plagiarism detection. In Proceedings of the 25th IEEE International Symposium on Software Reliability Engineering (ISSRE'14), 2014.

Digital Library

Cited By

Botacin M(2024)Fuzzing and Symbolic Execution for Multipath Malware Tracing: Bridging Theory and Practice via Survey and ExperimentsDigital Threats: Research and Practice10.1145/37001475:4(1-33)Online publication date: 11-Oct-2024
https://dl.acm.org/doi/10.1145/3700147
Yong Wong MValakuzhy KAhamad MBlough DMonrose F(2024)Understanding LLMs Ability to Aid Malware Analysts in Bypassing Evasion TechniquesCompanion Proceedings of the 26th International Conference on Multimodal Interaction10.1145/3686215.3690147(36-40)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3686215.3690147
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
Show More Cited By

Index Terms

Recommendations

LOM: Lightweight Classifier for Obfuscation Methods
Information Security Applications
Abstract
Obfuscation is an important technique that renders it difficult to analyze programs and has been developed for copyright protection. When an obfuscation is applied to a program, the logic of a program can be very complex and de-obfuscation can be ...
A Generic Approach to Automatic Deobfuscation of Executable Code
SP '15: Proceedings of the 2015 IEEE Symposium on Security and Privacy

Malicious software are usually obfuscated to avoid detection and resist analysis. When new malware is encountered, such obfuscations have to be penetrated or removed ("deobfuscated") in order to understand the internal logic of the code and devise ...
SoK: Automatic Deobfuscation of Virtualization-protected Applications
ARES '21: Proceedings of the 16th International Conference on Availability, Reliability and Security

Malware authors often rely on code obfuscation to hide the malicious functionality of their software, making detection and analysis more difficult. One of the most advanced techniques for binary obfuscation is virtualization-based obfuscation, which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

October 2015

1750 pages

ISBN:9781450338325

DOI:10.1145/2810103

General Chair:
Indrajit Ray
Colorado State University, USA
,
Program Chairs:
Ninghui Li
Purdue University, USA
,
Christopher Kruegel
University of California, Santa Barbara, USA

Copyright © 2015 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]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
Office of Naval Research

Conference

CCS'15

Sponsor:

SIGSAC

CCS'15: The 22nd ACM Conference on Computer and Communications Security

October 12 - 16, 2015

Colorado, Denver, USA

Acceptance Rates

CCS '15 Paper Acceptance Rate 128 of 660 submissions, 19%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
1,352
Total Downloads

Downloads (Last 12 months)238
Downloads (Last 6 weeks)30

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Botacin M(2024)Fuzzing and Symbolic Execution for Multipath Malware Tracing: Bridging Theory and Practice via Survey and ExperimentsDigital Threats: Research and Practice10.1145/37001475:4(1-33)Online publication date: 11-Oct-2024
https://dl.acm.org/doi/10.1145/3700147
Yong Wong MValakuzhy KAhamad MBlough DMonrose F(2024)Understanding LLMs Ability to Aid Malware Analysts in Bypassing Evasion TechniquesCompanion Proceedings of the 26th International Conference on Multimodal Interaction10.1145/3686215.3690147(36-40)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3686215.3690147
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
Jeon HLee SCho E(2024)Dynamic Opaque Predicate Detection with a Recursive Matching Method2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC61105.2024.00223(1530-1531)Online publication date: 2-Jul-2024
https://doi.org/10.1109/COMPSAC61105.2024.00223
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
Tian ZHe RZhao HChen L(2023)Function-Level Code Obfuscation Detection Through Self-Attention-Guided Multi-Representation FusionInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819402350066334:04(651-673)Online publication date: 11-Dec-2023
https://doi.org/10.1142/S0218194023500663
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
Zhang NAlden DXu DWang SJaeger TRuml W(2023)No Free Lunch: On the Increased Code Reuse Attack Surface of Obfuscated Programs2023 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58367.2023.00039(313-326)Online publication date: Jun-2023
https://doi.org/10.1109/DSN58367.2023.00039
Qingyang WQuanrui HYuqiao NChenya BZhen GShiwen S(2023)A Survey of Binary Code Security Analysis2023 6th International Conference on Data Science and Information Technology (DSIT)10.1109/DSIT60026.2023.00015(42-49)Online publication date: 28-Jul-2023
https://doi.org/10.1109/DSIT60026.2023.00015
Jeon HKang SLee SCho E(2023)Assessing Opaque Predicates: Unveiling the Efficacy of Popular Obfuscators with a Rapid Deobfuscator2023 30th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC60848.2023.00093(651-652)Online publication date: 4-Dec-2023
https://doi.org/10.1109/APSEC60848.2023.00093
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten