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 also address the issue of defining security of program obfuscation. We argue that requirements to obfuscation may be different and dependent on potential applications. Therefore, it makes sense to deal with a broad spectrum of security definitions for program obfuscation. In this paper we analyze five models for studying various aspects of obfuscation: “black box” model of total obfuscation, “grey box” model of total obfuscation, obfuscation for software protection, constant hiding, and predicate obfuscation. For each of these models we consider the applications where the model may be valid, positive and negative results on the existence of secure obfuscation in the framework of the model, and relationships with other models of program obfuscation.
This work is supported by RFBR grant 06-01-00584.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aucsmith, D.: Tamper resistant software: an implementation. In: Anderson, R. (ed.) Information Hiding. LNCS, vol. 1174, pp. 317–333. Springer, Heidelberg (1996)
Arboit, G.: A method for watermarking java programs via opaque predicates. 5-th International Conference on Electronic Commerce Research (2002)
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001)
Bhatkar, S., DuVarney, D.C., Sekar, R.: Efficient techniques for comprehensive protection from memory error exploits. USENIX Security (2005)
Canetti, R.: Towards realizing random oracles: hash functions that hide all partial information. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997)
Canetti, R., Micciancio, D.D., Reingold, O.: Perfectly one-way probabilistic hash functions. In: 30-th ACM Symposium on Theory of Computing, pp. 131–140 (1998)
Chess, D., White, S.: An undetectable computer virus. In: 2000 Virus Bulletin Conference (2000)
Chow, S., Gu, Y., Johnson, H., Zakharov, V.: An approach to obfuscation of control-flow of sequential programs. In: Wilhelm, R. (ed.) Informatics. LNCS, vol. 2000, pp. 144–155. Springer, Heidelberg (2001)
Cohen, F.: Operating system protection through program evolution. Computers and Security 12(6), 565–584 (1993)
Collberg, C., Thomborson, C., Low, D.: A Taxonomy of Obfuscating Transformations. Tech. Report, N 148, Univ. of Auckland (1997)
Collberg, C., Thomborson, C., Low, D., Collberg, C., Thomborson, C., Low, D.: Manufacturing cheap, resilient and stealthy opaque constructs. In: Symposium on Principles of Programming Languages, pp. 184–196 (1998)
Collberg, C., Thomborson, C.: Watermarking, Tamper-Proofing, and Obfuscation - Tools for Software Protection. IEEE Transactions on Software Engineering 28(6) (2002)
Dalla Preda, M., Giacobazzi, R.: Semantic-based code obfuscation by abstract interpretation. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1325–1336. Springer, Heidelberg (2005)
D’Anna, L., Matt, B., Reisse, A., Van Vleck, T., Schwab, S., LeBlanc, P.: Self- Protecting Mobile Agents Obfuscation Report, Report #03-015, Network Associates Laboratories (June 2003)
Diffie, W., Hellman, M.: New directions in cryptography. IEEE Transactions om Information Theory IT-22(6), 644–654 (1976)
Dodis, Y., Smith, A.: Correcting errors without leaking partial informtion. In: 37th ACM Symposium on Theory of Computing, pp. 654–663 (2005)
Goldreich, O., Levin, L: A hard-core predicate to any one-way function. In: 21th ACM Symposium on Theory of Computing, pp. 210–217 (1989)
Goldwasser, S., Tauman Kalai, Y.: On the impossibility of obfuscation with auxiliary input. In: 46th IEEE Symposium on Foundations of Computer Science, pp. 553–562 (2005)
Goldwasser, S., Rothblum, G.N.: On best possible obfuction. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 194–213. Springer, Heidelberg (2007)
Hada, S.: Zero-knowledge and code obfuscation. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 443–457. Springer, Heidelberg (2000)
Hohl, F.: Time limited blackbox security: protecting mobile agents from malicious hosts. In: Vigna, G. (ed.) Mobile Agents and Security. LNCS, vol. 1419, pp. 92–113. Springer, Heidelberg (1998)
Hofheinz, D., Malone-Lee, J., Stam, M.: Obfuscation for cryptographic purpose. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 214–232. Springer, Heidelberg (2007)
Linn, C., Debray, S.: Obfuscation of executable code to improve resistance to static disassambly. In: 10th ACM Conference on Computer and Communication Security, pp. 290–299 (2003)
Lynn, B., Prabhakaran, M., Sahai, A.: Positive results and techniques for obfuscation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 20–39. Springer, Heidelberg (2004)
Ogiso, T., Sakabe, Y., Soshi, M., Miyaji, A.: Software obfuscation on a theoretical basis and its implementation. IEEE Trans. Fundamentals E86-A(1) (2003)
Ostrovsky, R., Skeith, W.E.: Private searching on streaming data. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 223–240. Springer, Heidelberg (2005)
Szor, P., Ferrie, P.: Hunting for metamorphic. In: 2001 Virus Bulletin Conference, pp. 123–144 (2001)
Valiant, L.: A theory of learnable. Communications of the ACM 27(11), 1134–1142 (1984)
Varnovsky, N.P., Zakharov, V.A.: On the possibility of provably secure obfuscating programs. In: Broy, M., Zamulin, A.V. (eds.) PSI 2003. LNCS, vol. 2890, pp. 91–102. Springer, Heidelberg (2004)
Varnovsky, N.P.: A note on the concept of obfuscation. In: Proceedings of Institute for System Programming, Moscow, vol. 6, pp. 127–137 (2004)
Wang, C., Davidson, J., Hill, J., Knight, J.: Protection of software-based survivability mechanisms. In: International Conference of Dependable Systems and Networks (2001)
Wee, H.: On obfuscating point functions. In: 37th Symposium on Theory of Computing, pp. 523–532 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kuzurin, N., Shokurov, A., Varnovsky, N., Zakharov, V. (2007). On the Concept of Software Obfuscation in Computer Security. In: Garay, J.A., Lenstra, A.K., Mambo, M., Peralta, R. (eds) Information Security. ISC 2007. Lecture Notes in Computer Science, vol 4779. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75496-1_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-75496-1_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75495-4
Online ISBN: 978-3-540-75496-1
eBook Packages: Computer ScienceComputer Science (R0)