Malicious code is an increasingly important problem that threatens the security of computer systems. The tradi- tional line of defense against malware is composed of mal- ware detectors such as virus and spyware scanners. Un- fortunately, both researchers and malware authors have demonstrated that these scanners, which use pattern match- ing to identify malware, can be easily evaded by simple code transformations. To address this shortcoming, more pow- erful malware detectors have been proposed. These tools rely on semantic signatures and employ static analysis tech- niques such as model checking and theorem proving to per- form detection. While it has been shown that these systems are highly effective in identifying current malware, it is less clear how successful they would be against adversaries that take into account the novel detection mechanisms. The goal of this paper is to explore the limits of static analysis for the detection of malicious code. To this end, we present a binary obfuscation scheme that relies on the idea of opaque constants, which are primitives that allow us to load a constant into a register such that an analysis tool cannot determine its value. Based on opaque constants, we build obfuscation transformations that obscure program control flow, disguise access to local and global variables, and interrupt tracking of values held in processor registers. Using our proposed obfuscation approach, we were able to show that advanced semantics-based malware detectors can be evaded. Moreover, our opaque constant primitive can be applied in a way such that is provably hard to an- alyze for any static code analyzer. This demonstrates that static analysis techniques alone might no longer be suffi- cient to identify malware.