Malware has been posing a major threat for computer systems. The huge amount and diversity of its variants, such as computer viruses, Internet worms and Trojan horses, render classic security defenses ineffective. For the existence of active adversaries which constantly attempt to evade anti-malware, traditional signature-based approaches fail to detect malware which is new or obfuscated. This paper presents a general malware detection framework based on Kolmogorov complexity. As an example, we use a statistical data compression model which is Dynamic Markov Compression (DMC) to classify a code instance either as a “malware” or “benign” code instance. Our preliminary results are very promising. Our experimental results also demonstrate the framework can effectively detect unknown and obfuscated malware with high quality.