Joint PL / Security Seminar

Shai Rubin (web)
University of Wisconsin, Madison (web)
Computer Sciences Department (web)

On the (Im)possibility of Obfuscating Programs

In a recent paper, Barak et. el. show that obfuscation of programs is impossible [1]. However, every day hackers evade detection systems (Network Intrusion Detection Systems and anti-virus software) by obfuscating their programs, i.e., worms and viruses. Furthermore, researchers continue to actively explore new techniques for program obfuscation [2]. How can it be that academic researchers and, more disturbing, hackers successfully perform what Barak has proved to be impossible?

In this talk, I will address this question. First, I will present Barak's theoretical model for obfuscation and his impossibility result. Then, I will try to pinpoint the differences between his theoretical model and the real world; differences that make Barak's proof valid and, at the same time, do not prevent hackers from effectively obfuscate viruses.

Live discussion is encouraged.

1. B. Barak, O. Goldreich R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, "On the (Im)possibility of Obfuscating Programs", CRYPTO 2001.
2. Cullen Linn and Saumya Debray. "Obfuscation of Executable Code to Improve Resistance to Static Disassembly", CCS 2003.