Anti-virus systems traditionally use signatures to detect malicious executables, but this method beyond the capability of many existing detection approaches. In this paper, we present a data mining approach to detect unknown malicious executables. The feature set is a key to applying data mining or machine learning to successfully detect malicious executables. We propose a method to extract features which are most representative of viral properties. To improve the performance of the Bayesian classifier, we present a novel algorithm called half increment naive Bayes (HIB). We also evaluate the predictive power of the classifier, and show that our classifier yields high detection rates and works at a high learning speed.