Manufacturing opaque predicates in distributed systems for code obfuscation

ABSTRACT

Code obfuscation is a relatively new technique of software protection and it works by deterring reverse engineering attempts by malicious users of software. The objective of obfuscation is to make the logic embedded in code incomprehensible to automated program analysis tools used by adversaries. Opaque predicates act as tool for obfuscating control flow logic embedded within code. In this position paper, we address the problem of control-flow code obfuscation of processes executing in distributed computing environments by proposing a novel method of combining the open problems of distributed global state detection with a well-known hard combinatorial problem to manufacture opaque predicates. We name this class of new opaque predicates as distributed opaque predicates. We demonstrate our approach with an illustration and provide an extensive security analysis of code obfuscated with distributed opaque predicates. We show that our class of opaque predicates is capable of withstanding most known forms of automated static analysis attacks and a restricted class of dynamic analysis attack that could be mounted by adversaries.

REFERENCES

• 1: 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
• 2: Stanley Chow , Yuan Gu , Harold Johnson , Vladimir A. Zakharov, An Approach to the Obfuscation of Control-Flow of Sequential Computer Programs, Proceedings of the 4th International Conference on Information Security, p.144-155, October 01-03, 2001
• 3: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: Clark Thomborson , Jasvir Nagra , Ram Somaraju , Charles He, Tamper-proofing software watermarks, Proceedings of the second workshop on Australasian information security, Data Mining and Web Intelligence, and Software Internationalisation, p.27-36, January 01, 2004, Dunedin, New Zealand
• 5: SETI@home (2005), http://setiathome.ssl.berkeley.edu/ (accessed July 15 2005).
• 6: J. Palsberg , S. Krishnaswamy , Minseok Kwon , D. Ma , Qiuyun Shao , Y. Zhang, Experience with software watermarking, Proceedings of the 16th Annual Computer Security Applications Conference, p.308, December 11-15, 2000
• 7: Nagra, J. & Thomborson, C. (2004), Threading Software Watermarks. In the proceedings of 6th International Workshop on Information Hiding, LNCS Volume 3200, Springer-Verlag. Toronto, ON, Canada.
• 8: Fritz Hohl, Time Limited Blackbox Security: Protecting Mobile Agents From Malicious Hosts, Mobile Agents and Security, p.92-113, January 1998
• 9: 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]
• 10: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 11: Craig M. Chase , Vijay K. Garg, Detection of global predicates: techniques and their limitations, Distributed Computing, v.11 n.4, p.191-201, October 1998 [doi>10.1007/s004460050049]
• 12: Mattern, F. (1989), Virtual time and global states of distributed systems. In the proceedings of Workshop on Parallel and Distributed Algorithms, Elsevier Science Publication, pages 215-226.
• 13: Susan Horwitz, Precise flow-insensitive may-alias analysis is NP-hard, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.1, p.1-6, Jan. 1997 [doi>10.1145/239912.239913]
• 14: Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999 [doi>10.1145/325478.325519]
• 15: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 16: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 17: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 18: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 19: Robert Cooper , Keith Marzullo, Consistent detection of global predicates, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.167-174, May 20-21, 1991, Santa Cruz, California, United States
• 20: V. K. Garg , B. Waldecker, Detection of Weak Unstable Predicates in Distributed Programs, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.299-307, March 1994 [doi>10.1109/71.277788 ]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Authentication; Information flow controls
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Security, Theory

Keywords:
code obfuscation, distributed predicate detection, distributed systems security, mobile code protection, opaque predicates, software protection