M. Zubair Shafiq nexGIN RCSyeda Momina Tabish nexGIN RCMuddassar Farooq nexGIN RC download slides (PDF) Since the dawn of the new millennium, there has been an exponential increase in the volume and sophistication of executable malware. Malware writers use sophisticated code obfuscation and encryption (aka packing) techniques to circumvent signatures used by commercial off-the-shelf anti-virus software. In fact, it is claimed that more than half of new malware is created by simply re-packing existing malware. Malware packing is undoubtedly the most challenging problem faced by anti-virus vendors nowadays. In this paper we present a novel scheme, 'PE-Probe', which utilizes morphological (or structural) information of portable executables to detect zero-day (i.e. previously unseen) malicious executables. Our proposed scheme is fully robust to code obfuscation and packing techniques. First, it classifies a given test executable as packed or non-packed based on well-studied heuristics. Based on the previous outcome, the test executable is compared to either of the specialized structural models (for packed/non-packed executables) for malware detection. PE-Probe is real-time deployable as its scanning time is, on average, less than quarter of a second per executable. Through carefully designed experiments, we verify the reliability and robustness of our proposed scheme in stringent testing scenarios. The analysis presented in this study is done on a data set consisting of more than half a million malicious executable files obtained from OffensiveComputing.org.