The　detection　of　unknown　malicious　executables　is　beyond　the　capability　of　many　existing　detection　approaches.　Machine　learning　or　data　mining　methods　can　identify　new　or　unknown　malicious　executables　with　some　degree　of　success.　Feature　set　is　a　key　to　apply　data　mining　or　machine　learning　to　successfully　detect　malicious　executables.　In　this　paper,　we　present　an　approach　that　conducts　an　exhaustive　feature　search　on　a　set　of　malicious　executables　and　strives　to　obviate　over-fitting.　To　improve　the　performance　of　Bayesian　classifier,　we　present　a　novel　algorithm　called　Half　Increment　Näive　Bayes　(HIB),　which　selects　the　features　by　carrying　an　evolutional　search.　We　also　evaluate　the　predictive　power　of　a　classifier,　and　we　show　that　our　classifier　yields　high　detection　rates　and　learning　speed.　©　2009　Springer　Netherlands.