Systems and methods for generating signatures for electronic communication classification

• US 8,010,614 B1
• Filed: 11/01/2007
• Issued: 08/30/2011
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: Bitdefender IPR Management Limited (Bitdefender LLC)
• Original Assignee: Bitdefender IPR Management Limited (Bitdefender LLC)
• Inventors: Cosoi, Catalin A., Musat, Claudiu C. N.
• Primary Examiner(s): Nguyen; Phuoc
• Assistant Examiner(s): John; Clarence
• Application Number:
  US11/933,515
• Time in Patent Office: 1,398 Days
• Field of Search: 709/206, 709220-225
• 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

In some embodiments, fully-automated spam identification is facilitated by accelerating a signature extraction process, allowing the use of a relatively large number of signatures finely tailored to individual spam waves, rather than a smaller number of highly-accurate signatures generated under human supervision. The signature extraction process is performed in a distributed manner. A message corpus is classified into a plurality of message clusters. Cluster-specific spam identification text patterns are extracted selectively from members of each cluster, and the text patterns are combined into cluster-specific spam identification signatures. A cluster may represent an individual spam wave. Genetic algorithms are used to optimize the set of spam identification signatures by selecting the highest-performing combinations of cluster-specific spam identification text patterns. Performing signature extraction at a subclass level allows accelerating the signature extraction process, which in turn allows frequent signature updates and facilitates fully automated spam identification.

Claims

1. A computer system comprising a memory storing instructions which, when executed, cause the computer system to form:

a message aggregator configured to assign messages of a spam message corpus to a plurality of spam message clusters, the plurality of spam message clusters including a first and a second spam message cluster, wherein the message aggregator is configured to compute a hyperspace representation of a message of the spam message corpus, and to assign the message to a selected cluster according to a hyperspace distance between the hyperspace representation and a center of the selected cluster;

a pattern extractor connected to the message aggregator and configured to, in response to assigning the messages to the plurality of spam message clusters, extract a first set of cluster-specific spam identification text patterns from members of the first spam message cluster; and

a spam identification signature builder connected to the pattern extractor and configured to combine a first subset of the first set of cluster-specific spam identification text patterns into a first set of spam identification signatures for the first spam message cluster, wherein each spam identification signature of the first set of spam identification signatures includes a predetermined conjunction of at least two spam identification text patterns of the first subset of the first set of cluster-specific spam identification text patterns.

2. The system of claim 1, wherein the pattern extractor is configured to extract a second set of cluster-specific spam identification text patterns from members of the second spam message cluster, and wherein the spam identification signature builder is configured to combine a second subset of the second set of cluster-specific spam identification text patterns into a second set of spam identification signatures for the second spam message cluster, wherein each spam identification signature of the second set of spam identification signatures includes a predetermined conjunction of at least two spam identification text patterns of the second subset of the second set of cluster-specific spam identification text patterns.

3. The system of claim 1, further comprising a message classifier connected to the spam identification signature builder and configured to determine whether an incoming message is spam or non-spam according to the first set of spam identification signatures.

4. The system of claim 3, wherein the message classifier is configured to determine whether the incoming message is spam or non-spam according to the second set of spam identification signatures.

5. The system of claim 1, wherein the message aggregator is configured to assign a message of the spam message corpus to a selected cluster according to a set of message layout features of the message, wherein the message layout features include a set of relative positions of a plurality of message metaword substructures.

6. The system of claim 1, wherein the pattern extractor is configured to compute one of the first set of cluster-specific spam identification text patterns according to a suffix tree representation of a cluster-specific character string, wherein the cluster-specific character string includes a section of a message of the first spam message cluster.

7. The system of claim 1, wherein the spam identification signature builder comprises a signature optimizer configured to evaluate a spam-identification effectiveness of the first set of spam identification signatures, and to optimize the first set of spam identification signatures according to the spam-identification effectiveness.

8. The system of claim 7, wherein optimizing the first set of spam identification signatures comprises performing a mutation of a first spam identification signature of the first set of spam identification signatures.

9. The system of claim 7, wherein optimizing the first set of spam identification signatures comprises performing a crossover recombination of a first and a second spam identification signature of the first set of spam identification signatures, wherein performing the crossover recombination comprises swapping each value of a first set of elements of the first spam identification signature with a corresponding value of a second set of elements of the second spam identification signature.

10. The system of claim 1, wherein the message aggregator is configured to receive an updated message corpus and assign messages of the updated message corpus to the plurality of spam message clusters, and wherein the spam identification signature builder is configured to generate updated spam identification signatures for the plurality of message clusters using the updated message corpus.

24. The system of claim 1, wherein each spam identification signature consists of a predetermined conjunction of a plurality of spam identification text patterns.

11. A computer-implemented method comprising:

assigning messages of a spam message corpus to a plurality of spam message clusters, the plurality of spam message clusters including a first and a second spam message cluster, wherein assigning messages of the spam message corpus to the plurality of spam message clusters comprises computing a hyperspace representation of a message of the spam message corpus, and assigning the message to a selected cluster according to a hyperspace distance between the hyperspace representation and a center of the selected cluster;

in response to assigning the messages to the plurality of spam message clusters, extracting a first set of cluster-specific spam identification text patterns from members of the first spam message cluster; and

combining a first subset of the first set of cluster-specific spam identification text patterns into a first set of spam identification signatures for the first spam message cluster, wherein each spam identification signature of the first set of spam identification signatures includes a predetermined conjunction of at least two spam identification text patterns of the first subset of the first set of cluster-specific spam identification text patterns.

12. The method of claim 11, further comprising:

extracting a second set of cluster-specific spam identification text patterns from members of the second spam message cluster, and

combining a second subset of the second set of cluster-specific spam identification text patterns into a second set of spam identification signatures for the second spam message cluster, wherein each spam identification signature of the second set of spam identification signatures includes a predetermined conjunction of at least two spam identification text patterns of the second subset of the second set of cluster-specific spam identification text patterns.

13. The method of claim 11, further comprising determining whether an incoming message is spam or non-spam according to the first set of spam identification signatures.

14. The method of claim 13, further comprising determining whether the incoming message is spam or non-spam according to the second set of spam identification signatures.

15. The method of claim 11, comprising assigning a message of the spam message corpus to a selected cluster according to a set of message layout features of the message, wherein the message layout features include a set of relative positions of a plurality of message metaword substructures.

16. The method of claim 11, further comprising computing one of the first set of cluster-specific spam identification text patterns according to a suffix tree representation of a cluster-specific character string, wherein the cluster-specific character string includes a section of a message of the first spam message cluster.

17. The method of claim 11, further comprising evaluating a spam-identification effectiveness of the first set of spam identification signatures, and optimizing the first set of spam identification signatures according to the spam-identification effectiveness.

18. The method of claim 17, wherein optimizing the first set of spam identification signatures comprises performing a mutation of a first spam identification signature of the first set of spam identification signatures.

19. The method of claim 17, wherein optimizing the first set of spam identification signatures comprises performing a crossover recombination of a first and a second spam identification signature of the first set of spam identification signatures, wherein performing the crossover recombination comprises swapping each value of a first set of elements of the first spam identification signature with a corresponding value of a second set of elements of the second spam identification signature.

20. The method of claim 11, further comprising receiving an updated message corpus, assigning messages of the updated message corpus to the plurality of spam message clusters, and generating updated spam identification signatures for the plurality of message clusters using the updated message corpus.

21. A computer-implemented spam-filtering method comprising:

receiving a set of cluster-specific spam identification signatures, wherein the cluster-specific spam identification signatures are generated by;

assigning messages of a spam message corpus to a plurality of spam message clusters including a first and second spam message cluster, wherein assigning messages of the spam message corpus to the plurality of spam message clusters comprises computing a hyperspace representation of a message of the spam message corpus, and assigning the message to a selected cluster according to a hyperspace distance between the hyperspace representation and a center of the selected cluster;

in response to assigning the messages to the plurality of spam message clusters, extracting a set of cluster-specific spam identification text patterns from members of the first spam message cluster; and

combining a subset of the set of cluster-specific spam identification text patterns into a set of cluster-specific spam identification signatures for the first spam message cluster, wherein each spam identification signature includes a predetermined conjunction of at least two spam identification text patterns; and

deciding whether an incoming message is spam or non-spam according to the cluster-specific spam identification signatures.

22. A non-transitory computer-readable storage medium encoding instructions which, when executed on a computer system, cause the computer system to perform the steps of:

assigning messages of a spam message corpus to a plurality of spam message clusters, the plurality of spam message clusters including a first and a second spam message cluster, wherein assigning messages of the spam message corpus to the plurality of spam message clusters comprises computing a hyperspace representation of a message of the spam message corpus, and assigning the message to a selected cluster according to a hyperspace distance between the hyperspace representation and a center of the selected cluster;

in response to assigning the messages to the plurality of spam message clusters, extracting a set of cluster-specific spam identification text patterns from members of the first spam message cluster; and

combining a subset of the set of cluster-specific spam identification text patterns into a set of spam identification signatures for the first spam message cluster, wherein each spam identification signature of the set of spam identification signatures includes a predetermined conjunction of at least two spam identification text patterns of the subset of the set of cluster-specific spam identification text patterns.

23. A non-transitory computer-readable storage medium encoding instructions which, when executed on a computer system, cause the computer system to perform the steps of:

receiving a set of cluster-specific spam identification signatures, wherein the cluster-specific spam identification signatures are generated by;

assigning messages of a spam message corpus to a plurality of spam message clusters including a first and second spam message cluster, wherein assigning messages of the spam message corpus to the plurality of spam message clusters comprises computing a hyperspace representation of a message of the spam message corpus, and assigning the message to a selected cluster according to a hyperspace distance between the hyperspace representation and a center of the selected cluster;

in response to assigning the messages to the plurality of spam message clusters, extracting a set of cluster-specific spam identification text patterns from members of the first spam message cluster; and

combining a subset of the set of cluster-specific spam identification text patterns into a set of cluster-specific spam identification signatures for the first spam message cluster, wherein each spam identification signature includes a predetermined conjunction of at least two spam identification text patterns; and

deciding whether an incoming message is spam or non-spam according to the cluster-specific spam identification signatures.