Towards integral binary execution: implementing oblivious hashing using overlapped instruction encodings

ABSTRACT

Executing binaries without interference by an outside adversary has been an ongoing duel between protection methods and attacks. Recently, an efficient kernel-patch attack has been presented against commonly used self-checking code techniques that use checksumming ahead of execution. While methods based on self-modifying code can defend against this attack, such techniques depend on low-level architectural details and may not be practical in the long run. An alternative defense is to use oblivious hashing (OH). Instead of checking code integrity prior to execution, OH can verify untampered runtime behavior continuously. However, earlier OH approaches have some weaknesses, particularly with binary code: Physical instruction bytes cannot be easily checked during execution, and an attacker may be able to detect and remove OH checks, since OH alone does not provide tamper-resistance or obfuscation.

In our approach, we deliberately overlap a program's basic blocks so that they share instruction bytes. This increases tamper-resistance implicitly because malicious modifications affect multiple instructions simultaneously. Also, our scheme facilitates explicit anti-tampering checks via injection of OH instructions overlapped with target code, enabling OH that can verify integrity of both runtime state and executing instructions. Thus, our method addresses anti-checksum attacks without resorting to self-modifying code, and also extends OH to verify physical code, not only program state. In addition, overlapping facilitates resistance against disassembly and decompilation. Our approach works on processor architectures and byte-codes that support variable-length instructions. To our knowledge, this is the first technique that blends tamper-resistance into architecture and therefore significantly improves robustness of binaries.

REFERENCES

• 1: Cloakware. http://www.cloakware.com.
• 2: Dotfuscator. http://www.preemptive.com/products/dotfuscator.
• 3: Safedisc. http://www.macrovision.com/products/safedisc.
• 4: SpecCPU benchmark. http://www.spec.org.
• 5: Trusted Computing Platform Alliance. http://www.trustedpc.org.
• 6: Martín Abadi , Mihai Budiu , Úlfar Erlingsson , Jay Ligatti, Control-flow integrity, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102165]
• 7: Bertrand Anckaert , Mariusz Jakubowski , Ramarathnam Venkatesan, Proteus: virtualization for diversified tamper-resistance, Proceedings of the ACM workshop on Digital rights management, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179509.1179521]
• 8: David Aucsmith, Tamper Resistant Software: An Implementation, Proceedings of the First International Workshop on Information Hiding, p.317-333, May 30-June 01, 1996
• 9: 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
• 10: David Brumley , Dan Boneh, Remote timing attacks are practical, Proceedings of the 12th conference on USENIX Security Symposium, p.1-1, August 04-08, 2003, Washington, DC
• 11: D. Boneh and R. Lipton. On the importance of checking cryptographic protocols for faults. In Eurocrypt 1997.
• 12: M. Cary, M. Jakubowski, and R. Venkatesan. Iterated obfuscation for white-boxing AES-like cipers (unpublished).
• 13: Hoi Chang , Mikhail J. Atallah, Protecting Software Code by Guards, Revised Papers from the ACM CCS-8 Workshop on Security and Privacy in Digital Rights Management, p.160-175, November 05, 2001
• 14: Yuqun Chen , Ramarathnam Venkatesan , Matthew Cary , Ruoming Pang , Saurabh Sinha , Mariusz H. Jakubowski, Oblivious Hashing: A Stealthy Software Integrity Verification Primitive, Revised Papers from the 5th International Workshop on Information Hiding, p.400-414, October 07-09, 2002
• 15: S. Chow, P. Eisen, H. Johnson, and P. van Oorschot. A white-box DES implementation for DRM applications. In ACM DRM 2002.
• 16: 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]
• 17: Christian S. Collberg , Clark Thomborson, Watermarking, tamper-proffing, and obfuscation: tools for software protection, IEEE Transactions on Software Engineering, v.28 n.8, p.735-746, August 2002 [doi>10.1109/TSE.2002.1027797]
• 18: 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]
• 19: 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]
• 20: N. Dedic, M. H. Jakubowski, and R. Venkatesan. A graph game model for software tamper protection. In Information Hiding, 2007.
• 21: Paul England , Butler Lampson , John Manferdelli , Marcus Peinado , Bryan Willman, A Trusted Open Platform, Computer, v.36 n.7, p.55-62, July 2003 [doi>10.1109/MC.2003.1212691]
• 22: S. Forrest , A. Somayaji , D. Ackley, Building Diverse Computer Systems, Proceedings of the 6th Workshop on Hot Topics in Operating Systems (HotOS-VI), p.67, May 05-06, 1997
• 23: Tal Garfinkel , Ben Pfaff , Jim Chow , Mendel Rosenblum , Dan Boneh, Terra: a virtual machine-based platform for trusted computing, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 24: W. H. Gates. Personal communication.
• 25: Jonathon T. Giffin , Mihai Christodorescu , Louis Kruger, Strengthening Software Self-Checksumming via Self-Modifying Code, Proceedings of the 21st Annual Computer Security Applications Conference, p.23-32, December 05-09, 2005 [doi>10.1109/CSAC.2005.53]
• 26: Bill Horne , Lesley R. Matheson , Casey Sheehan , Robert Endre Tarjan, Dynamic Self-Checking Techniques for Improved Tamper Resistance, Revised Papers from the ACM CCS-8 Workshop on Security and Privacy in Digital Rights Management, p.141-159, November 05, 2001
• 27: G. Hunt, J. Larus, D. Tarditi, and T. Wobber. Broad new OS research. In HotOS 2005.
• 28: M. Jacob, D. Boneh, and E. Felten. Attacking an obfuscated cipher by injecting faults. In ACM DRM 2002.
• 29: M. H. Jakubowski and R. Venkatesan. Protecting digital goods using oblivious checking, US Patent No. 7,080,257, filed on Aug. 30, 2000, granted on July 18, 2006.
• 30: P. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Crypto 1996.
• 31: 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
• 32: J. C. Lagarias, E. Rains, and R. J. Vanderbei. The Kruskal Count. http://xxx.lanl.gov/math.PR/0110143.
• 33: Ruby B. Lee , Peter C. S. Kwan , John P. McGregor , Jeffrey Dwoskin , Zhenghong Wang, Architecture for Protecting Critical Secrets in Microprocessors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.2-13, June 04-08, 2005
• 34: David Lie Chandramohan Thekkath , Mark Mitchell , Patrick Lincoln , Dan Boneh , John Mitchell , Mark Horowitz, Architectural support for copy and tamper resistant software, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.168-177, November 2000, Cambridge, Massachusetts, United States
• 35: C.-L. Lin, H.-Y. Chen, and T.-W. Hou. Tamper-proofing of Java programs by oblivious hashing. In CTHCP 2005: 11th Workshop on Compiler Techniques for High-Performance Computing.
• 36: B. Lynn, M. Prabhakaran, and A. Sahai. Positive results and techniques for obfuscation. In Eurocrypt 2004.
• 37: Arvind Narayanan , Vitaly Shmatikov, Obfuscated databases and group privacy, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102135]
• 38: D. A. Osvik, A. Shamir, and E. Tromer. Cache attacks and countermeasures: The case of AES. In CT-RSA 2006.
• 39: Arvind Seshadri , Mark Luk , Elaine Shi , Adrian Perrig , Leendert van Doorn , Pradeep Khosla, Pioneer: verifying code integrity and enforcing untampered code execution on legacy systems, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 40: Umesh Shankar , Monica Chew , J. D. Tygar, Side effects are not sufficient to authenticate software, Proceedings of the 13th conference on USENIX Security Symposium, p.7-7, August 09-13, 2004, San Diego, CA
• 41: Dawn Xiaodong Song , David Wagner , Xuqing Tian, Timing analysis of keystrokes and timing attacks on SSH, Proceedings of the 10th conference on USENIX Security Symposium, p.25-25, August 13-17, 2001, Washington, D.C.
• 42: A. Srivastava, A. Edwards, and H. Vo. Vulcan - binary transformation in a distributed environment. Technical Report MSR-TR-2001-50, MSR, 2001.
• 43: G. Edward Suh , Dwaine Clarke , Blaise Gassend , Marten van Dijk , Srinivas Devadas, AEGIS: architecture for tamper-evident and tamper-resistant processing, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782838]
• 44: Chenxi Wang , Jonathan Hill , John C. Knight , Jack W. Davidson, Protection of Software-Based Survivability Mechanisms, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.193-202, July 01-04, 2001
• 45: Chenxi Wang , Jonathan Hill , John Knight , Jack Davidson, Software Tamper Resistance: Obstructing Static Analysis of Programs, University of Virginia, Charlottesville, VA, 2000
• 46: Hoeteck Wee, On obfuscating point functions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060669]
• 47: Glenn Wurster , P. C. van Oorschot , Anil Somayaji, A Generic Attack on Checksumming-Based Software Tamper Resistance, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.127-138, May 08-11, 2005 [doi>10.1109/SP.2005.2]
• 48: Xiaotong Zhuang , Tao Zhang , Santosh Pande, HIDE: an infrastructure for efficiently protecting information leakage on the address bus, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.m MISCELLANEOUS

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.0 General

  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Information hiding

General Terms:
Algorithms, Reliability, Security

Keywords:
anti-disassembly, integrity checking, obfuscation, oblivious hashing, overlapped code, tamper-resistance