Abstract
Theoretical investigations of obfuscation have been built around a model of a single Turing machine which interacts with a user. A drawback of this model is that it cannot account for the most common approach to obfuscation used by malware: the observer effect. The observer effect describes the situation in which the act of observing something changes it. Malware implements the observer effect by detecting and acting on changes in its environment caused by user observation. Malware that leverages the observer effect is considered to be environmentally sensitive.
To account for environmental sensitivity, we initiate a theoretical study of obfuscation with regards to programs that interact with a user and an environment. We define the System-Interaction model to formally represent this additional dimension of interaction. We also define a semantically obfuscated program within our model as one that hides all semantic predicates from a computationally bounded adversary. This is possible while still remaining useful because semantically obfuscated programs can interact with an environment while showing nothing to the user. In this paper, we analyze the necessary and sufficient conditions of achieving this standard of obfuscation and show how these conditions relate to real-world programs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Apon, D., Huang, Y., Katz, J., Malozemoff, A.J.: Implementing cryptographic program obfuscation (2014)
Arora, S., Barak, B.: Randomized computation. In: Computational Complexity: A Modern Approach, pp. 121–122. Cambridge University Press, New York (2012). Chap. 7, Sect. 7.5.3
Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. Cryptology ePrint Archive, Report 2013/631 (2013). http://eprint.iacr.org/2013/631.pdf. Accessed 6 Apr 2015
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. Cryptology ePrint Archive, Report 2001/069 (2001). http://eprint.iacr.org/
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 1. Springer, Heidelberg (2001)
Basile, C., et al.: Towards a formal model for software tamper resistance. COSIC, University of Leuven, Flanders, Belgium (2009). https://www.cosic.esat.kuleuven.be/publications/article-1280.pdf. Accessed 6 Apr 2015
Beaucamps, P., Filiol, E.: On the possibility of practically obfuscating programs towards a unified perspective of code protection. J. Comput. Virol. 3(1), 3–21 (2007)
Bernstein, D.J., Hülsing, A., Lange, T., Niederhagen, R.: Bad directions in cryptographic hash functions. In: Foo, E., Stebila, D. (eds.) ACISP 2015. LNCS, vol. 9144, pp. 488–508. Springer, Heidelberg (2015)
Bitansky, N., Canetti, R.: On strong simulation and composable point obfuscation. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 520–537. Springer, Heidelberg (2010)
Bitansky, N., Canetti, R., Kalai, Y.T., Paneth, O.: On virtual grey box obfuscation for general circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 108–125. Springer, Heidelberg (2014)
Borello, J.M., Mé, L.: Code obfuscation techniques for metamorphic viruses. J. Comput. Virol. 4(3), 211–220 (2008)
Brakerski, Z., Rothblum, G.N.: Virtual black-box obfuscation for all circuits via generic graded encoding. Cryptology ePrint Archive, Report 2013/563 (2013). http://eprint.iacr.org/2013-563.pdf, http://eprint.iacr.org/2013-563.pdf. Accessed 6 Apr 2015
Canetti, R., Varia, M.: Non-malleable obfuscation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 73–90. Springer, Heidelberg (2009)
Chen, X., Andersen, J., Mao, Z., Bailey, M., Nazario, J.: Towards an understanding of anti-virtualization and anti-debugging behavior in modern malware. In: IEEE International Conference on Dependable Systems and Networks with FTCS and DCC, DSN 2008, pp. 177–186, June 2008
Collberg, C., Thomborson, C., Low, D.: A taxonomy of obfuscating transformations. Technical report 148. Department of Computer Science University of Auckland, 36 p., July 1997. http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:A+Taxonomy+of+Obfuscating+Transformations#0
Dinaburg, A., Royal, P., Sharif, M., Lee, W.: Ether: malware analysis via hardware virtualization extensions. In: Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS 2008, pp. 51–62 (2008). http://dl.acm.org/citation.cfm?id=1455779
Ferrie, P.: Attacks on more virtual machine emulators. Technical report. Symantec Advanced Threat Research (2007)
Ferrie, P.: The Ultimate Anti-Debugging Reference, May 2011. http://pferrie.host22.com/papers/antidebug.pdf. Accessed 6 Apr 2015
Garfinkel, T., Adams, K., Warfield, A., Franklin, J.: Compatibility is not transparency: VMM detection myths and realities. In: Proceedings of 11th USENIX Workshop on Hot Topics in Operating Systems, pp. 6:1–6:6 (2007). http://dl.acm.org/citation.cfm?id=1361397.1361403
Garg, S., et al.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS 2013, pp. 40–49 (2013)
Goldwasser, S., Rothblum, G.N.: On best-possible obfuscation. In: Proceedings of 4th Theory Cryptography Conference, pp. 194–213 (2007)
Kang, M.G., Yin, H., Hanna, S., McCamant, S., Song, D.: Emulating emulation-resistant malware. In: Proceedings of the 1st ACM Workshop on Virtual Machine Security, VMSec 2009, pp. 11–22. ACM, New York (2009). http://doi.acm.org/10.1145/1655148.1655151
Moon, P.: The use of packers, obfuscators and encryptors in modern malware the use of packers, obfuscators and encryptors in modern malware. Technical report, Royal Holloway University of London, March 2015
Nithyanand, R., Solis, J.: A theoretical analysis: physical unclonable functions and the software protection problem. In: Proceedings of 2012 IEEE Symposium Security and Privacy Workshop, pp. 1–11 (2012)
Nithyanand, R., Sion, R., Solis, J.: Solving the software protection problem with intrinsic personal physical unclonable functions. Sandia National Laboratories, Livermore, CA, USA. Report SAND2011-6603 (2011)
Paleari, R., Martignoni, L., Roglia, G.F., Bruschi, D.: A fistful of red-pills: how to automatically generate procedures to detect CPU emulators. In: Proceedings of the 3rd USENIX Conference on Offensive Technologies, WOOT 2009, p. 2. USENIX Association, Berkeley (2009). http://dl.acm.org/citation.cfm?id=1855876.1855878
Plaga, R., Koob, F.: A formal definition and a new security mechanism of physical unclonable functions. In: Proceedings 16th International GI/ITG Conference Measurement, Modeling, and Evaluation of Computing Systems and Dependability and Fault Tolerance, pp. 228–301 (2012). http://arxiv.org/abs/1204.0987
Popov, I.V., Debray, S.K., Andrews, G.R.: Binary obfuscation using signals. In: Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, SS 2007, pp. 19:1–19:16. USENIX Association, Berkeley (2007). http://dl.acm.org/citation.cfm?id=1362903.1362922
Saxena, A., Wyseur, B., Preneel, B.: Towards security notions for white-box cryptography. In: Samarati, P., Yung, M., Martinelli, F., Ardagna, C.A. (eds.) ISC 2009. LNCS, vol. 5735, pp. 49–58. Springer, Heidelberg (2009)
Sikorski, M., Honig, A.: Practical Malware Analysis: The Hands-On Guide to Dissecting Malicious Software, 1st edn. No Starch Press, San Francisco (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Blackthorne, J., Kaiser, B., Yener, B. (2016). A Formal Framework for Environmentally Sensitive Malware. In: Monrose, F., Dacier, M., Blanc, G., Garcia-Alfaro, J. (eds) Research in Attacks, Intrusions, and Defenses. RAID 2016. Lecture Notes in Computer Science(), vol 9854. Springer, Cham. https://doi.org/10.1007/978-3-319-45719-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-45719-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45718-5
Online ISBN: 978-3-319-45719-2
eBook Packages: Computer ScienceComputer Science (R0)