The subject disclosure is directed towards a technology for efficiently emulating program code that is protected by one or more various code virtualization techniques to detect the presence of malware. An emulation engine emulates a program containing a mix of native code, custom (e.g., virtualized obfuscated) code, and at least one emulator and/or interpreter that understands the custom code, by building a custom emulation component that is built by detecting and analyzing the internal emulator or interpreter. The custom emulation component may access a translation table built from the analysis, and also may simplify a plurality of instructions in the program into a lesser number of instructions in an intermediate language used for emulation.