Group based spam classification

• US 8,504,627 B2
• Filed: 04/05/2010
• Issued: 08/06/2013
• Est. Priority Date: 01/24/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Bright Sun Technologies, Series 42 of Allied Security Trust I (Allied Security Trust)
• Inventors: Alspector, Joshua, Kolcz, Aleksander, Chowdhury, Abdur R.
• Primary Examiner(s): HOANG, HIEU T
• Application Number:
  US12/754,182
• Publication Number:
  US 20100191819A1
• Time in Patent Office: 1,219 Days
• Field of Search: 709/206, 709/207, 707/737
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

An e-mail filter is used to classify received e-mails so that some of the classes may be filtered, blocked, or marked. The e-mail filter may include a classifier that can classify an e-mail as belonging to a particular class and an e-mail grouper that can detect substantially similar, but possibly not identical, e-mails. The e-mail grouper determines groups of substantially similar e-mails in an incoming e-mail stream. For each group, the classifier determines whether one or more test e-mails from the group belongs to the particular class. The classifier then designates the class to which the other e-mails in the group belong based on the results for the test e-mails.

Claims

1. A method of classifying e-mails, the method comprising:

receiving a plurality of e-mails that each include a respective header portion and content portion;

storing the received plurality of e-mails;

analyzing, using at least one processor, the content portions of the stored plurality of e-mails to cluster the plurality of e-mails into multiple groups of substantially duplicate e-mails;

storing the multiple groups of substantially duplicate e-mails;

selecting a test e-mail from a group of the stored multiple groups;

determining a class for the test email based on the content portion of the test e-mail; and

classifying a non-test e-mail in the group based on the determined class of the test e-mail.

2. The method of claim 1 wherein analyzing the content portions of the stored e-mails to cluster the e-mails into multiple groups of substantially duplicate e-mails comprises:

performing duplicate detection on a received e-mail when the e-mail is received to determine if the received e-mail is a substantial duplicate of e-mails in an existing group of substantially duplicate e-mails;

adding the received e-mail to the existing group of substantially duplicate e-mails when the received e-mail is a substantial duplicate of e-mails in the existing group; and

using the received e-mail to start a new group of substantially duplicate e-mails when the received e-mail is not a substantial duplicate of e-mails in the existing group of substantially duplicate e-mails.

3. The method of claim 1 wherein analyzing the content portions of the stored plurality of e-mails to cluster the plurality of e-mails into multiple groups of substantially duplicate e-mails comprises:

performing duplicate detection on a set of stored plurality of e-mails to cluster the set of stored plurality of e-mails into groups of substantially duplicate e-mails.

4. The method of claim 1 further comprising:

receiving a new e-mail;

performing duplicate detection on the new e-mail to determine if the new e-mail is a substantial duplicate of the e-mails in the group;

classifying the new e-mail based on the class of the one or more test e-mails when the new e-mail is a substantial duplicate of the e-mails in the group.

5. The method of claim 1 wherein the substantially duplicate e-mails in the group are part of a larger population of substantially duplicate e-mails, the method further comprising selecting a size for the group such that a proportion of the e-mails in the group belonging to a particular class accurately reflects a proportion of the e-mails in the larger population that belong to the particular class.

6. The method of claim 1 further comprising:

selecting multiple test e-mails.

7. The method of claim 6 wherein classifying at least one non-test e-mail comprises classifying the at least one non-test e-mail into a particular class when a proportion of the multiple test e-mails belonging to the particular class exceeds a threshold proportion.

8. The method of claim 7 wherein selecting multiple test e-mails comprises selecting a sufficient number of test e-mails such that a proportion of the multiple test e-mails belonging to the particular class accurately reflects a proportion of the e-mails in the stored group that belong to the particular class.

9. The method of claim 8 wherein the particular class is spam.

10. The method of claim 9 wherein the threshold proportion is based on a misclassification cost of misclassifying spam e-mail as non-spam e-mail and a misclassification cost of misclassifying non-spam e-mail as spam e-mail.

11. The method of claim 1 wherein determining a class for the test e-mail comprises determining whether the e-mail is a spam e-mail such that spam e-mail in the received e-mails can be filtered.

23. The method of claim 1, wherein analyzing the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate emails comprises:

determining hash representations of the stored plurality of e-mails; and

clustering the stored plurality of e-mails into multiple groups based on the determined hash representations.

24. The method of claim 1, wherein analyzing the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate emails comprises:

comparing attributes of the stored plurality of e-mails to a predetermined set of attributes;

determining fingerprints for the stored plurality of e-mails based on the comparison; and

clustering the stored plurality of e-mails into multiple groups based on the determined fingerprints.

12. A non-transitory computer-usable storage medium having a computer program embodied thereon for classifying e-mails, the computer program comprising instructions for causing at least one processor to perform the following operations:

receive a plurality of e-mails that each include a respective header portion and content portion;

store the received plurality of e-mails;

analyze the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails;

store the multiple groups of substantially duplicate e-mails;

select a test e-mail from a group of the stored multiple groups;

determine a class for the test e-mail based on the content portion of the test e-mail; and

classify a non-test e-mail in the group based on the determined class of the test e-mail.

13. The computer-usable storage medium of claim 12 wherein, to analyze the content portion of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails, the computer program further comprises instructions for causing to the at least one processor to:

perform duplicate detection on a received e-mail when the e-mail is received to determine if the received e-mail is a substantial duplicate of e-mails in an existing group of substantially duplicate e-mails;

add the received e-mail to the existing group of substantially duplicate e-mails when the received e-mail is a substantial duplicate of e-mails in the existing group; and

use the received e-mail to start a new group of substantially duplicate e-mails when the received e-mail is not a substantial duplicate of e-mails in the existing group of substantially duplicate e-mails.

14. The computer-usable storage medium of claim 12 wherein, to analyze the content portion of the stored plurality of e-mails to cluster the stored plurality of e-mails into groups of substantially duplicate e-mails, the computer program further comprises instructions for causing the at least one processor to:

perform duplicate detection on the set of stored e-mails to cluster the set of stored e-mails into groups of substantially duplicate e-mails.

15. The computer-usable medium of claim 12 wherein the computer program further comprises instructions for causing the at least one processor to:

receive a new e-mail;

perform duplicate detection on the new e-mail to determine if the new e-mail is substantially identical to the e-mails in the group;

classify the new e-mail based on the class of the one or more test e-mails when the new e-mail is substantially identical to the e-mails in the group.

16. The computer-usable storage medium of claim 12 wherein the substantially duplicate e-mails in the group are part of a larger population of substantially duplicate e-mails, the computer program further comprising instructions for causing the at least one processor to select a size for the group such that a proportion of the e-mails in the at least one stored group belonging to a particular class accurately reflects a proportion of the e-mails in the larger population that belong to the particular class.

17. The computer-usable storage medium of claim 12 wherein the computer program further comprises instructions for causing the at least one processor to select multiple test e-mails.

18. The computer-usable storage medium of claim 17 wherein, to classify at least one non-test e-mail, the computer program further comprises instructions for causing the at least one processor to classify the at least one non-test e-mail into a particular class when a proportion of the multiple test e-mails belonging to the particular class exceeds a threshold proportion.

19. The computer-usable storage medium of claim 18 wherein, to select multiple test e-mails, the computer program further comprises instructions for causing the at least one processor to select a sufficient number of test e-mails such that a proportion of the multiple test e-mails belonging to the particular class accurately reflects a proportion of the e-mails in the one stored group that belong to the particular class.

20. The computer-usable storage medium of claim 19 wherein the particular class is spam.

21. The computer-usable storage medium of claim 20 wherein the threshold proportion is based on a misclassification cost of misclassifying spam e-mail as non-spam e-mail and a misclassification cost of misclassifying non-spam e-mail as spam e-mail.

22. The computer-usable storage medium of claim 12 wherein, to determine a class for the test e-mail, the computer program further comprises instructions for causing the at least one processor to determine whether the e-mail is a spam e-mail such that spam e-mail in the received e-mails can be filtered.

25. The computer-usable storage medium of claim 12, wherein the instructions for causing the computer to analyze the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails comprise instructions for causing the at least one processor to:

determine hash representations of the stored plurality of e-mails; and

cluster the stored plurality of e-mails into multiple groups based on the determined hash representations.

26. The computer-usable storage medium of claim 12, wherein the instructions for causing the computer to analyze the content portions of the stored plurality of e-mails to cluster the stored plurality of e-mails into multiple groups of substantially duplicate e-mails comprise instructions for causing the at least one processor to:

compare attributes of the stored plurality of e-mails to a predetermined set of attributes;

determine fingerprints for the stored plurality of e-mails based on the comparison; and

cluster the stored plurality of e-mails into multiple groups based on the determined fingerprints.