Spam email detection based on n-grams with feature selection

• US 7,912,907 B1
• Filed: 10/07/2005
• Issued: 03/22/2011
• Est. Priority Date: 10/07/2005
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Jensen, Sanford, Mantel, Eli
• Primary Examiner(s): Neurauter, Jr.; George C
• Assistant Examiner(s): PFIZENMAYER, MARK C
• Application Number:
  US11/246,876
• Time in Patent Office: 1,992 Days
• Field of Search: 709/206, 706/52, 707/780
• US Class Current: 709/206
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

A similarity measurement manager uses n-gram analysis to identify spam email messages. The similarity measurement manager tokenizing an email message into a plurality of overlapping n-grams, wherein n is large enough to identify uniqueness of artifacts. The similarity measurement manager employs feature selection by comparing the created n-grams to n-grams of known artifacts which were created according to the same methodology. Created n-grams that match an n-gram of a known artifact are ignored. The similarity measurement manager compares the remaining created n-grams to pluralities of n-grams of known spam email messages, the n-grams of the known spam email messages being themselves created by executing the same steps. The similarity measurement manager determines whether the email message comprises spam based on whether or not the n-gram comparison indicates that it is substantially similar to a known spam email message.

Claims

1. A computer implemented method for identifying spam email messages, the method comprising the steps of:

tokenizing an email message into a collection of overlapping n-grams;

comparing the collection of n-grams to n-grams of known artifacts found in email messages due to how the email messages were produced and transmitted, wherein the known artifacts comprise machine-generated text artifacts included in the email messages by email service providers;

removing n-grams that match an n-gram of a known artifact from the collection;

comparing the remaining n-grams in the collection to n-grams of known spam email messages; and

determining whether the email message comprises spam based on results of the second comparing step.

2. The method of claim 1 further comprising:

responsive to a threshold percentage of the remaining n-grams in the collection matching n-grams of a known spam email message, determining that the email message comprises spam.

3. The method of claim 1 further comprising:

responsive to a threshold percentage of the remaining n-grams in the collection not matching n-grams of any known spam email message, determining that the email message does not comprise spam.

4. The method of claim 1 wherein:

n comprises an integer greater than 4.

5. The method of claim 1 further comprising:

creating each n-gram using only a subset of bits comprising each character.

6. The method of claim 1 further comprising:

inputting the collection of n-grams into a permutation box; and

utilizing output of the permutation box for comparing, wherein the n-grams to which the output of the permutation box is compared have themselves been passed through the permutation box.

7. The method of claim 1 further comprising:

inputting the collection of n-grams into a substitution box; and

utilizing output of the substitution box for comparing, wherein the n-grams to which the output of the substitution box is compared have themselves been passed through the substitution box.

8. The method of claim 1 further comprising:

isolating a predictable subset of n-grams of the email message; and

utilizing the isolated predictable subset to compare to pluralities of n-grams of known spam email messages, wherein each plurality of n-grams of a known spam email message itself comprises an isolated predictable subset of the known spam email message.

9. The method of claim 1 wherein the n-grams of the known spam email messages are themselves created by executing at least the tokenizing, first comparing, and removing steps.

10. The method of claim 1 wherein n-grams further comprise character-level n-grams or byte-level n-grams.

11. A non-transitory computer readable storage medium containing an executable computer program product for identifying spam email messages, the computer program product comprising:

program code, when executed by a computer processor, causing the computer processor to tokenize an email message into a collection of overlapping n-grams;

program code, when executed by a computer processor, causing the computer processor to compare the collection of n-grams to n-grams of known artifacts found in email messages due to how the email messages were produced and transmitted, wherein the known artifacts comprise machine-generated text artifacts included in the email messages by email service providers;

program code, when executed by a computer processor, causing the computer processor to remove n-grams that match an n-gram of a known artifact from the collection;

program code, when executed by a computer processor, causing the computer processor to compare the remaining n-grams in the collection to n-grams of known spam email messages; and

program code, when executed by a computer processor, causing the computer processor to determine whether the email message comprises spam based on results of the second comparing step.

12. The computer program product of claim 11 further comprising:

program code, when executed by a computer processor, causing the computer processor to determine, responsive to a threshold percentage of the remaining n-grams in the collection matching n-grams of a known spam email message, that the email message comprises spam.

13. The computer program product of claim 11 further comprising:

program code, when executed by a computer processor, causing the computer processor to determine, responsive to a threshold percentage of the remaining n-grams in the collection not matching n-grams of any known spam email message, that the email message does not comprise spam.

14. The computer program product of claim 11 further comprising:

program code, when executed by a computer processor, causing the computer processor to input the collection of n-grams into a permutation box; and

program code, when executed by a computer processor, causing the computer processor to utilize output of the permutation box for comparing, wherein the n-grams to which the output of the permutation box is compared have themselves been passed through the permutation box.

15. The computer program product of claim 11 further comprising:

program code, when executed by a computer processor, causing the computer processor to input the collection of n-grams into a substitution box; and

program code, when executed by a computer processor, causing the computer processor to utilize output of the substitution box for comparing, wherein the n-grams to which the output of the substitution box is compared have themselves been passed through the substitution box.

16. A computer system for identifying spam email messages, the computer system comprising:

a computer processor for executing computer program instructions; and

a non-transitory computer-readable storage medium having executable computer program instructions tangibly embodied thereon, the executable computer program instructions comprising program instructions, when executed by the computer processor, causing the computer processor to instructions;

tokenize an email message into a collection of overlapping n-grams;

compare the collection of n-grams to n-grams of known artifacts found in email messages due to how the email messages were produced and transmitted, wherein the known artifacts comprise machine-generated text artifacts included in the email messages by email service providers;

remove n-grams that match an n-gram of a known artifact from the collection;

compare the remaining n-grams in the collection to n-grams of known spam email messages; and

determine whether the email message comprises spam based on results of the second comparing step.

17. The computer system of claim 16 wherein the executable computer program instructions further comprises program instructions, when executed by the computer processor, causing the computer processor to:

determine that the email message comprises spam responsive to a threshold percentage of the remaining n-grams in the collection matching n-grams of a known spam email message.

18. The computer system of claim 16 wherein the executable computer program instructions further comprises program instructions, when executed by the computer processor, causing the computer processor to:

determine that the email message does not comprises spam responsive to a threshold percentage of the remaining n-grams in the collection not matching n-grams of any known spam email message.

19. The computer system of claim 16, wherein the n-grams of the known spam email messages are themselves created by executing at least the tokenizing, first comparing, and removing steps.