Program obfuscation: a quantitative approach

ABSTRACT

Despite the recent advances in the theory underlying obfuscation, there still is a need to evaluate the quality of practical obfuscating transformations more quickly and easily. This paper presents the first steps toward a comprehensive evaluation suite consisting of a number of deobfuscating transformations and complexity metrics that can be readily applied on existing and future transformations in the domain of binary obfuscation. In particular, a framework based on software complexity metrics measuring four program properties: code, control flow, data and data flow is suggested. A number of well-known obfuscating and deobfuscating transformations are evaluated based upon their impact on a set of complexity metrics. This enables us to quantitatively evaluate the potency of the (de)obfuscating transformations.

REFERENCES

• 1: A. Appel. Deobfuscation is in np, August 2002.
• 2: G. Arboit. A method for watermarking java programs via opaque predicates. In The Fifth International Conference on Electronic Commerce Research (ICECR-5), 2002.
• 3: David Aucsmith, Tamper Resistant Software: An Implementation, Proceedings of the First International Workshop on Information Hiding, p.317-333, May 30-June 01, 1996
• 4: G. Balakrishnan and T. Reps. Analyzing memory accesses in x86 executables. In Proc. Int. Conf. on Compiler Construction, pages 5--23, 2004.
• 5: Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
• 6: P. Biondi and F. Desclaux. Silver needle in the skype. In BlackHat Europe, 2006.
• 7: Bruno De Bus , Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Koen De Bosschere, Link-time optimization of ARM binaries, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 8: Ran Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.455-469, August 17-21, 1997
• 9: Cloakware Corp: S. Chow, H. Johnson, and Y. Gu. Tamper Resistant Software - Control Flow Encoding, Patent US 6,779,114, Filed 1999, Granted 2004.
• 10: Frederick B. Cohen, Operating system protection through program evolution, Computers and Security, v.12 n.6, p.565-584, Oct. 1993 [doi>10.1016/0167-4048(93)90054-9]
• 11: C. Collberg , E. Carter , S. Debray , A. Huntwork , J. Kececioglu , C. Linn , M. Stepp, Dynamic path-based software watermarking, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 12: C. Collberg, C. Thomborson, and D. Low. A taxonomy of obfuscating transformations. Technical Report 148, University of Auckland, 1997.
• 13: Christian Collberg , Clark Thomborson , Douglas Low, Manufacturing cheap, resilient, and stealthy opaque constructs, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268962]
• 14: C. Cook. Information theory metric for assembly language. Software Engineering Strategies, pages 52--60, 1993.
• 15: M. Dalla Preda, M. Madou, K. De Bosschere, and R. Giacobazzi. Opaque predicates detection by abstract interpretation. Algebraic Methodology and Software Technology, LNCS 4019:81--95, 2006.
• 16: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 17: Hideaki Goto , Masahiro Mambo , Kenjiro Matsumura , Hiroki Shizuya, An Approach to the Objective and Quantitative Evaluation of Tamper-Resistant Software, Proceedings of the Third International Workshop on Information Security, p.82-96, December 20-21, 2000
• 18: Maurice H. Halstead, Elements of Software Science (Operating and programming systems series), Elsevier Science Inc., New York, NY, 1977
• 19: Warren A. Harrison , Kenneth I. Magel, A complexity measure based on nesting level, ACM SIGPLAN Notices, v.16 n.3, p.63-74, March 1981 [doi>10.1145/947825.947829]
• 20: K. Heffner and C. Collberg. The obfuscation executive. Information Security Conference (ISC04), 2004.
• 21: S. Henry , D. Kafura, Software Structure Metrics Based on Information Flow, IEEE Transactions on Software Engineering, v.7 n.5, p.510-518, September 1981 [doi>10.1109/TSE.1981.231113]
• 22: Christopher Kruegel , William Robertson , Fredrik Valeur , Giovanni Vigna, Static disassembly of obfuscated binaries, Proceedings of the 13th conference on USENIX Security Symposium, p.18-18, August 09-13, 2004, San Diego, CA
• 23: Cullen Linn , Saumya Debray, Obfuscation of executable code to improve resistance to static disassembly, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948149]
• 24: B. Lynn, M. Prabhakaran, and A. Sahai. Positive results and techniques for obfuscation. In EUROCRYPT, 2004.
• 25: Matias Madou , Bertrand Anckaert , Bjorn De Sutter , Koen De Bosschere, Hybrid static-dynamic attacks against software protection mechanisms, Proceedings of the 5th ACM workshop on Digital rights management, November 07-07, 2005, Alexandria, VA, USA [doi>10.1145/1102546.1102560]
• 26: J. Maebe, M. Ronsse, and K. De Bosschere. DIOTA: Dynamic Instrumentation, Optimization and Transformation of Applications. In Proc. Int. Conf. on Parallel Architectures and Compilation Techniques (PACT), september 2002.
• 27: T. J. McCabe, A Complexity Measure, IEEE Transactions on Software Engineering, v.2 n.4, p.308-320, July 1976 [doi>10.1109/TSE.1976.233837]
• 28: John C. Munson , Taghi M. Khoshgoftaar, Measurement of data structure complexity, Journal of Systems and Software, v.20 n.3, p.217-225, March 1993 [doi>10.1016/0164-1212(93)90065-6]
• 29: G. Myles and C. Collberg. Software watermarking via opaque predicates: Implementation, analysis, and attacks, 2004.
• 30: N. Naeem, M. Batchelder, and L. Hendren. Metrics for measuring the effectiveness of decompilers and obfuscators. Technical Report 2006-4, McGill University, School of Computer Science: Sable Research Group, June 2006.
• 31: P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. LNCS, 1592:223--238, 1999.
• 32: Fabien A. P. Petitcolas , Ross J. Anderson , Markus G. Kuhn, Attacks on Copyright Marking Systems, Proceedings of the Second International Workshop on Information Hiding, p.218-238, April 14-17, 1998
• 33: B. Schwarz , S. Debray , G. Andrews, Disassembly of Executable Code Revisited, Proceedings of the Ninth Working Conference on Reverse Engineering (WCRE'02), p.45, October 29-November 01, 2002
• 34: Kuo-Chung Tai, A program complexity metric based on data flow information in control graphs, Proceedings of the 7th international conference on Software engineering, p.239-248, March 26-29, 1984, Orlando, Florida, United States
• 35: Sharath K. Udupa , Saumya K. Debray , Matias Madou, Deobfuscation: Reverse Engineering Obfuscated Code, Proceedings of the 12th Working Conference on Reverse Engineering, p.45-54, November 07-11, 2005 [doi>10.1109/WCRE.2005.13]
• 36: Chenxi Wang , John Knight, A security architecture for survivability mechanisms, University of Virginia, Charlottesville, VA, 2001
• 37: Chenxi Wang , Jonathan Hill , John Knight , Jack Davidson, Software Tamper Resistance: Obstructing Static Analysis of Programs, University of Virginia, Charlottesville, VA, 2000
• 38: M. R. Woodward , M. A. Hennell , D. Hedley, A Measure of Control Flow Complexity in Program Text, IEEE Transactions on Software Engineering, v.5 n.1, p.45-50, January 1979 [doi>10.1109/TSE.1979.226497]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.0 General
          Subjects: Protection mechanisms

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

General Terms:
Measurement, Security

Keywords:
metrics, program obfuscation, quantification