The current state of art in program obfuscations:definitions of obfuscation security
https://doi.org/10.15514/ISPRAS-2014-26(3)-9
Abstract
Program obfuscation is a semantic-preserving transformation aimed at bringing a program into such a form, which impedes the understanding of its algorithm and data structures or prevents extracting of some valuable information from the text of a program. Since obfuscation could find wide use in computer security, information hiding and cryptography, security requirements to program obfuscators became a major focus of interests for pioneers of theory of software obfuscation. In this paper we give a survey of various definitions of obfuscation security and main results that establish possibility or impossibility of secure program obfuscation under certain cryptographic assumptions. We begin with a short retrospective survey on the origin and development of program obfuscation concept in software engineering and mathematical cryptography. In the introduction we also point out on the main difficulties in the development of practical and secure obfuscation techniques. In the next section we discuss the main line of research in the application of program obfuscation to the solution of various problems in system programming and software security. Finally, in section 3 we present and discuss a compendium of formal definitions of the program obfuscation concept developed so far in mathematical cryptography - black-box obfuscation, gray-box obfuscation, the best possible obfuscation, obfuscation with auxiliary inputs, etc.. We also make a comparative analysis of these definitions and present the main results on the (im)possibility of secure program obfuscation w.r.t. every such definition.
About the Authors
N. P. Varnovsky
Information Security Institute
Russian Federation
Russian Federation
V. A. Zakharov
Lomonosov Moscow State University, Faculty CMC
Russian Federation
Russian Federation
N. N. Kuzurin
ISP RAS
Russian Federation
Russian Federation
V. A. Shokurov
ISP RAS
Russian Federation
Russian Federation
References
1. Canetti R., Dwork C., Naor M., Ostrovsky R. Deniable encryption. Advances in Cryptology- CRYPTO 97, Lecture Notes in Computer Science, v. 1294, 1997, p. 90-104.
2. Diffie W., Hellman M. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6), 1976, p.644-654.
3. Sahai A., Waters B. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. CRYPTO ePrint 2013.
4. Collberg C., Thomborson C., Low D. A Taxonomy of Obfuscating Transformations. Technical Report, N 148, Univ. of Auckland, 1997.
5. Hada S. Zero-knowledge and code obfuscation. Advances in Cryptology- ASIACRYPT 2000, Lecture Notes in Computer Science, v. 1976, 2000, p. 443-457.
6. Cohen F. Operating system protection through program evolution. Computers and Security, v. 12, N 6, 1993, p. 565-584.
7. Savage J. Models of Computation: Exploring the Power of Computing. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 1997, 672 p.
8. Chess D., White S. An undetectable computer virus. Proceedings of the 2000 Virus Bulletin Conference, 2000.
9. Valiant L. A theory of learnable. Communications of the ACM, 1984, v. 27, N 11, p. 1134-1142.
10. Szor P., Ferrie P. Hunting for metamorphic. Proceedings of the 2001 Virus Bulletin Conference, 2001, p.123-144.
11. Bitansky N., Canetti R. On obfuscation with strong simulators. Advances in Cryptology- CRYPTO 2010, Lecture Notes in Computer Science, v. 6223, 2010, p. 520-537.
12. Collberg C., J. Nagra. Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Program Protection. Addison-Wesley Professional, 2009.
13. Goldwasser S., Kalai T.Y. On the impossibility of obfuscation with auxiliary input. Proceedings of the 46-th IEEE Symposium on Foundations of Computer Science, 2005, p. 553-562.
14. Aucsmith D. Tamper resistant software: an implementation. Information Hiding Conference, Lecture Notes in Computer Science, v. 1174, 1996, p. 317-333.
15. Scud T.T. ObjObf - x86/Linux ELF relocateable object obfuscator, 2003. http://packetstormsecurity.org/files/31524/objobf-0.5.0.tar. bz2.
16. Solutions P. DashO - the premier Java obfuscator and efficiency enhancing tool. http://www.preemptive.com/products/dasho/.
17. Solutions P. Dotfuscator - the premier .NET obfuscator and efficiency enhancing tool. http://www.preemptive.com/products/dotfuscator/.
18. Z. KlassMaster. The second generation Java obfuscator. http://www.zelix.com/.
19. Ge J., Chaudhuri S., Tyagi A. Control Flow Based Obfuscation. Proceedings of the Digital Rights Management Workshop. Alexandria, VA, USA, 2005, p. 83-92
20. Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S., Ke Yang. On the (im)possibility of obfuscating programs. Advances in Cryptology - CRYPTO'01, Lecture Notes in Computer Science, v. 2139, 2001, p. 1-18 (see also Journal of the ACM 2012).
21. Varnovsky N.P. A note on the concept of obfuscation. Trudy ISP RAN [The Proceedings of ISP RAS], vol. 6, 2004, p. 127-137.
22. Kuzurin N.N., Shokurov A.V., Varnovsky N.P., Zakharov V.A. On the concept of software obfuscation in computer security. Information Security Conference, Lecture Notes in Computer Science, v. 4779, 2007, p. 281-298.
23. Goldwasser S., Rothblum G.N. On best possible obfuscation. Theory of Cryptography Conference, Lecture Notes in Computer Science, v. 4392, 2007, p. 194-213.
24. Canetti R. Towards realizing random oracles: hash functions that hide all partial information. Advances in Cryptology - CRYPTO'97, Lecture Notes in Computer Science, v. 1294, 1997, p. 455-469.
25. Varnovsky N.P., Zakharov V.A. On the possibility of provably secure obfuscating programs. Conference ``Perspectives of System Informatics'', Lecture Notes in Computer Science, v. 2890, 2004, p. 91-102.
26. Lynn B., Prabhakaran M., Sahai A. Positive results and techniques for obfuscation. Advances in Cryptology - EUROCRYPT 2004, Lecture Notes in Computer Science, v. 3027, 2004, p. 20-39.
27. Wee H. On obfuscating point functions. Proceedings of the 37-th Symposium on Theory of Computing, 2005, p. 523-532.
28. Hofheinz D., Malone-Lee J., Stam M. Obfuscation for cryptographic purpose. Theory of Cryptography Conference, Lecture Notes in Computer Science, v. 4392, p. 214-232.
29. Canetti R., Dakdouk R. R. Obfuscating point functions with multibit output. Advances in Cryptology – EUROCRYPT 2008, Lecture Notes in Computer Science, 2008, v. 4965, p. 489–508.
30. Hohenberger S., Rothblum G.N., Shelat A., Vaikuntanathan V. Securely obfuscating re-encryption. Proceedings of the 4-th Conference on Theory of Cryptography, 2007, p. 233-252
31. Canetti R., Rothblum G.N., Varia M. Obfuscation of hyperplane membership. Proceedings of the 7-th Conference on Theory of Cryptography, 2010, p. 72-89.
32. Collberg C., Thomborson C., Low D. Manufacturing cheap, resilient and stealthy opaque constructs. Proceedings of the Symposium on Principles of Programming Languages, 1998, p. 184-196.
33. de Oor A., van der Oord L. Stealthy obfuscation techniques: misleading pirates. Technical Report of Department of Computer Science University of Twente Enschede, Netherlands, 2003.
34. Naumovich G, Memon N. Preventing piracy, reverse engineering, and tampering. IEEE Computer, 2003, v. 36, N 7, p. 64-71.
35. Collberg C, Thomborson C., Watermarking, Tamper-Proofing, and Obfuscation - Tools for Software Protection. IEEE Transactions on Software Engineering, v. 28, N 6, 2002.
36. Arboit G. A method for watermarking Java programs via opaque predicates. Proceedings of the International Conference on Electronic Commerce Research. Montreal, Canada, 2002: 1-8.
37. Zhu W., Thomborson C., Wang F.-Y. A survey of software watermarking. Lecture Notes in Computer Science, v.3495, 2005, p. 454-458.
38. Myles G, Collberg C. Software watermarking via opaque predicates: Implementation, analysis, and attacks. Electronic Commerce Research, 2006, v. 6, N 2, p. 155-171.
39. Sander T., Tchudin C.F. Protecting mobile agents against malicious hosts. Mobile Agents and Security, Lecture Notes in Computer Science, 1997, p. 44-60.
40. Hohl F. Time limited blackbox security: protecting mobile agents from malicious hosts. Mobile Agents and Security, Lecture Notes in Computer Science, v. 1419, 1998, p. 92-113.
41. D'Anna L., Matt B., Reisse A., Van Vleck T. , Schwab S., LeBlanc P. Self-Protecting Mobile Agents Obfuscation Report. Tech. Rep. N 03-015, Network Associates Laboratories, June 2003.
42. Wu J., Zhang Y., Wang X. et al. A scheme for protecting mobile agents based on combining obfuscated control flow and time checking technology. Proceedings of the Conference on Computational Intelligence and Security. Harbin, Heilongjiang, China, 2007, p. 912-916
43. Roeder T., Schneider F.B. Proactive Obfuscation. ACM Transactions on Computer Systems, v. 28, N 2, 2010.
44. Ostrovsky R., Skeith W.E. Private searching on streaming data. Advances in Cryptology - CRYPTO-2005, Lecture Notes in Computer Science, v. 3621, 2005, p. 223-240.
45. Narayanan A., Shmatikov V. Obfuscated databases and group privacy. Proceedings of the 12th ACM Conference on Computer and Communications Security, 2005, p. 102-111.
46. Ivannikiov V.P., Varnovsky N.P., Zakharov V.A., Kuzurin N.P., Shokurov A.V., Kononov A.N., Kalinin A.V. Metody informazionnoy zaschity proektnyh resheniy pri izgotovlenii microelectronnyh shem [Information security techniques in the development of microelectronic circuits] Izvestiya Taganrogskogo radiotehnicheskogo universiteta [Bulletin of Taganrog Radiotechnical University], 2005, v. 4, p. 112-119.
47. Varnovsky N.P., Zakharov V.A., Kuzurin N.P., Chernov A.V., Shokurov A.V. Zadaschi I metody obespecheniya informazionnoy bezopasnosti pri proizvodstve microelectronnyh shem [Information security problems and techniques in the development of microelectronic circuits], Trudy ISP RAN [The Proceedings of ISP RAS], 2006, т. 1, с. 29-61.
48. Borello J.M., Me L. Code obfuscation technique for metamorphic viruses. Journal of Computer Virology, 2008, v. 4, p, 211-220.
49. Bhatkar S., Du Varney D.C., Sekar R. Efficient techniques for comprehensive protection from memory error exploits. USENIX Security, 2005.
50. Wroblewski G. General method of program code obfuscation. Draft, 2002, 84 p.
51. Linn C., Debray S. Obfuscation of executable code to improve resistance to static disassembly. Proceedings of the 10-th ACM Conference on Computer and Communication Security, 2003, p. 290-299.
52. Sosonkin M, Naumovich G, Memon N. Obfuscation of design intent in object-oriented applications. Proceedings of the Digital Rights Management Workshop. Washington, DC, USA, 2003, p. 142-153.
53. Collberg C., Myles G., Huntwort A. Sandmark – a tool for software protection research. IEEE Security and Privacy, 2003, v. 1, N 4, p. 40-49.
54. Heffner K., Collberg C. The obfuscation executive. Information Security Conference, Lecture Notes in Computer Science, 2004, v. 3225.
55. Chan J. T., Yang W. Advanced obfuscation techniques for Java bytecode. Journal of Systems and Software, 2004, v. 71, N 1-2, p. 1-10.
56. Cimato S., De S. A., Petrillo U. F. Overcoming the obfuscation of Java programs by identifier renaming. Journal of Systems and Software, 2005, v. 78, N 1, p. 60-72.
57. Madou M., Anckaert B., de Sutter B., de Bosschere K. Hybrid static-dynamic attacks against software protection mechanisms. Proceedings of the 5th ACM workshop on Digital rights management, 2005, p. 75-82.
58. Udupa S. K., Debray S. K., Madou M. Deobfuscation: Reverse engineering obfuscated code. Proceedings of the 12-th Working Conference on Reverse Engineering. Pittsburgh, PA, USA, 2005, p. 45-54.
59. Ge J., Chaudhuri S., Tyagi A. Control Flow Based Obfuscation. Proceedings of the Digital Rights Management Workshop. Alexandria, VA, USA, 2005, p. 83-92.
60. Chen K., Chen J. B. On instrumenting obfuscated java bytecode with aspects. Proceedings of the 2006 International Workshop on Software Engineering for Secure Systems. Shanghai, China, 2006, p. 19-26.
61. Madou M., Anckaert B., de Sutter B., de Bosschere K., Cappaert J., Preenel B. On the effectiveness of source code transformations for binary obfuscation. Proceedings of the International Conference on Software Engineering Research and Practice, 2006, p.527-533.
62. Madou M., Anckaert B., Moseley P., Debray S., de Sutter B., de Bosschere K. Software protection through dynamic code mutation. Proceedings of the 6-th international conference on Information Security Applications, 2006, p. 194-206.
63. Drape S, Majumdar A, Thomborson C. Slicing aided design of obfuscating transforms. Proceedings of the International Computing and Information Systems Conference (ICIS 2007). Melbourne, Australia, 2007, p. 1019-1024.
64. Majumdar A., Drape S., Thomborson C. Slicing obfuscations: Design, correctness, and evaluation. Proceedings of the 2007 ACM Workshop on Digital Rights. Alexandria, VA, USA, 2007, p. 70-81.
65. Batchelder M., Hendren L. Obfuscating Java: The most pain for the least gain. Proceedings of the Compiler Construction. Braga, Portugal, 2007, p. 96-110.
66. Ceccato M., Di. P. M., Nagra J. et al. Towards experimental evaluation of code obfuscation techniques. Proceedings of the 4th ACM Workshop on Quality of Protection., 2008, p. 39-46.
67. Darwish S.M., Guirguis S.K., Zalat M.S. Stealthy code obfuscation technique for software security. Proceedings of the International Conference on Computer Engineering and Systems, 2010, p. 93-99.
68. Chernov A.V. Ob odnom metode maskirovki program [On one program obfuscation techniques]. Trudy ISP RAN [The Proceedings of ISP RAS], 2003, v. 4, p. 85-119.
69. Majumdar A., Drape S., Thomborson C. et al. Metrics-based evaluation of slicing obfuscations. Proceedings of the 3rd International Symposium on Information Assurance and Security. Manchester, United Kingdom, 2007, p. 472-477.
70. Naeem N. A., Batchelder M., Hendren L. Metrics for Measuring the Effectiveness of Decompilers and Obfuscators. Proceedings of the 15th IEEE International Conference on Program. Banff, Alberta, Canada, 2007, p. 253-258.
71. Anckaert B., Madou M., De S. B. et al. Program obfuscation: A quantitative approach. Proceedings of the 2007 ACM Workshop on Quality of Protection. 2007, p. 15-20.
72. Tsai H. Y., Huang Y. L., Wagner D. A graph approach to quantitative analysis of control-flow obfuscating. IEEE Trans. on Information Forensics and Security, 2009, v. 4, N 2, p. 257-267.
73. Cousot P., Cousot R. An abstract interpretation-based framework for software watermarking. Proceedings of 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2004, p. 173-185.
74. Zakharov V.A. Ivanov K.S. Program obfuscation as obstruction of program static analysis. Trudy ISP RAN [The Proceedings of ISP RAS], 2004, v. 6. p. 141-161.
75. Zakharov V.A. Ivanov K.S. O protivodeystvii nekotorym algorytmam staticheskogo analiza program [On the hindering some program static analysis algorithms]. Trudy konferencii “Matematika i bezopasnost’ informazionnyh tehnologiy” (MaBIT-03) [Proceedings of the Conference “Mathematics and security of information technologies”], 2003, с. 282-286.
76. Dalla Preda M., Giacobazzi R. Semantic-based code obfuscation by abstract interpretation. International Colloquium on Automata, Language and Programming, Lecture Notes in Computer Science, v. 3580, 2005, p.1325-1336.
77. Zakharov V.A. Ivanov K.S. O modelyah program v svyazi s zadachey protivideystviya algoritmam ststicheskogo analiza [On the program models related with the proble of hindering program static analysis algorithms]. Trudy ISP RAN [The Proceedings of ISP RAS], 2006, т. 11.
78. Varnovsky N.P., Zakharov V.A., Kuzurin N.P., Podlovchenko R.I., Shokurov A.V., Shcherbina V.L. O primenenii metodov deobfuscazii program dlya obnaruzheniya slojnyh komputernyh virusov [On the application of program deobfuscation techniques for detecting non-trivial computer viruse]. Izvestiya Taganrogskogo radiotehnicheskogo universiteta [Bulletin of Taganrog Radiotechnical University], 2006, т. 6, с. 18-27.
79. Kuzurin N.N., Podlovchenko R.I., Scherbina V.L., Zakharov V.A. Using algebraic models of programs for detecting metamorphic malwares. Trudy ISP RAN [The Proceedings of ISP RAS], 2007, v. 12, p. 77-94.
80. Della Preda M., Giacobazzi G. Semantic-based code obfuscation by abstract interpretation. Journal of Computer Security, 2009, v. 17, N 6, p. 855-908.
81. Christodorescu M., Jha S. Static analysis of executables to detect malicious patterns. Proceedings of the 12-th Security Symposium, 2003, p. 169-186.
82. Della Preda M., Christodorescu M., Jha S., Debray S. A semantic-based approach to malware detection. Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2007, p. 377-388.
83. Della Preda M., Giacobazzi G., Debray S., Coogan K., Townsend G. Modelling Metamorphism by Abstract Interpretation. Proceedings of the 17th International Static Analysis Symposium (SAS'10). Lecture Notes in Computer Science, 2010, v. 6337, p. 218-235.
84. Majumdar A, Thomborson C. On the use of opaque predicates in mobile agent code obfuscation. Proceedings of the ISI 2005. Altanta, GA, USA, 2005, p. 648-649.
85. Majumdar A., Thomborson C. Manufacturing opaque predicates in distributed systems for code obfuscation. Proceedings of the 4th International Conference on Information Security. Hobart, Tasmania, Australia, 2006, p. 187-196.
86. Della Preda M., Giacobazzi G., Madou M., de Bosschere K. Opaque predicate detection by abstract interpretation. 11th International Conference on Algebriac Methodology and Software Technology. Lecture Notes in Computer Science, v 4019, 2006, p. 81-95.
87. Wang C., Davidson J., Hill J., Knight J. Protection of software-based survivability mechanisms. Proceedings of the International Conference of Dependable Systems and Networks, 2001.
88. Chow S., Gu Y., Johnson H., Zakharov V. An approach to obfuscation of control-flow of sequential programs. Information Security Conference, Lecture Notes in Computer Science, v. 2000, 2001, p. 144-155
89. Ogiso T., Sakabe Y., Soshi M. Miyaji A. Software obfuscation on a theoretical basis and its implementation. IEEE Transactions Fundamentals, E86-A(1), 2003.
90. Varnovsky N.P., Zakharov V.A., Kuzurin N.P., Podlovchenko R.I., Shokurov A.V. O perspektivah resheniya zadach obfuscacii komputernyh program [On the prospects of the solution of the obfuscation problems for computer programs] Trudy konferencii “Matematika i bezopasnost’ informazionnyh tehnologiy” (MaBIT-03) [Proceedings of the Conference “Mathematics and security of information technologies”], 2003, с. 344-351.
91. Ostrovsky R. Efficient computation on oblivious RAMs. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, p. 514-523.
92. Zhuang X., Zhang T., Lee H.-H. S., Pande S. Hardware assisted control flow obfuscation for embedded processes. Proceedings of the 2004 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, 2004, p. 292-302.
93. Bhatkar S., du Varney D.C., Sekar R. Address obfuscation: an efficient approach to combat a broad range of memory error exploits. Proceedings of the 12th conference on USENIX Security Symposium, 2003, v. 8.
94. Garg S., Gentry C., Halevi S., Raykova M., Sahai A., Waters B. Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits. IACR Cryptology ePrint Archive 2013, 451 (2013).
95. Hada S. Secure obfuscation for encrypted signatures. Advances in Cryptology - EUROCRYPT 2010, Lecture Notes in Computer Science, v. 6110, 2010, p. 92-112.
96. Adida B. , Wikström D. How to shuffle in piblic. Proceedings of the 4th Conference on Theory of Cryptography, Lecture Notes in Computer Science, 2007, v. 4392, p. 555-574.
97. Canetti R., Dwork C., Naor M., Ostrovsky R. Deniable encryption. Advances in Cryptology- CRYPTO 97, Lecture Notes in Computer Science, v. 1294, 1997, p. 90-104.
98. Sahai A., Waters B. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. CRYPTO ePrint 2013.
99. Hada S. Zero-knowledge and code obfuscation. Advances in Cryptology- ASIACRYPT 2000, Lecture Notes in Computer Science, v. 1976, 2000, p. 443-457.
100. Savage J. Models of Computation: Exploring the Power of Computing. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 1997, 672 p.
101. Valiant L. A theory of learnable. Communications of the ACM, 1984, v. 27, N 11, p. 1134-1142.
102. Bitansky N., Canetti R. On obfuscation with strong simulators. Advances in Cryptology- CRYPTO 2010, Lecture Notes in Computer Science, v. 6223, 2010, p. 520-537.
103. Goldwasser S., Kalai T.Y. On the impossibility of obfuscation with auxiliary input. Proceedings of the 46-th IEEE Symposium on Foundations of Computer Science, 2005, p. 553-562.
Review
For citations:
Varnovsky N.P., Zakharov V.A., Kuzurin N.N., Shokurov V.A. The current state of art in program obfuscations:definitions of obfuscation security. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(3):167-198. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(3)-9
Email this article 