Spam detection using linear genetic programming

Abstract

Spam refers to unsolicited bulk email. Many algorithms have been applied to the spam detection problem and many programs have been developed. The problem is an adversarial one and an ongoing fight against spammers. We prove that reliable Spam detection is an NP-complete problem, by mapping email spams to metamorphic viruses and applying Spinellis [“Reliable identification of bounded-length viruses is NP-complete” Inf. Theory IEEE Trans. On. 49, 1, 280–284 (2003).]‘s proof of NP- completeness of metamorphic viruses. Using a number of features extracted from the SpamAssassin Data set, a linear genetic programming (LGP) system called Gagenes LGP (or GLGP) has been implemented. The system has been shown to give 99.83% accuracy, higher than Awad et al. [3]’s result with the Naïve Bayes algorithm. GLGP’s recall and precision are higher than Awad et al.’s, and GLGP’s Accuracy is also higher than the reported results by Lai and Tsai [19].