Systems and Methods for Spam Detection Using Character Histograms

• US 20130191469A1
• Filed: 01/25/2012
• Published: 07/25/2013
• Est. Priority Date: 01/25/2012
• Status: Active Grant

• Current Assignee: Bitdefender IPR Management Limited (Bitdefender LLC)
• Original Assignee: Bitdefender IPR Management Limited (Bitdefender LLC)
• Inventors: DICHIU, Daniel, LUPSESCU, Lucian Z.
• Granted Patent: US 8,954,519 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: H04L 51/212 using filtering or selective blocking
• CPC Class Codes: H04L 63/0263 Rule management

Abstract

Described spam detection techniques including string identification, pre-filtering, and character histogram and timestamp comparison steps facilitate accurate, computationally-efficient detection of rapidly-changing spam arriving in short-lasting waves. In some embodiments, a computer system extracts a target character string from an electronic communication such as a blog comment, transmits it to an anti-spam server, and receives an indicator of whether the respective electronic communication is spam or non-spam from the anti-spam server. The anti-spam server determines whether the electronic communication is spam or non-spam according to certain features of the character histogram of the target string. Some embodiments also perform an unsupervised clustering of incoming target strings into clusters, wherein all members of a cluster have similar character histograms.

Claims

1. A method comprising:

employing a computer system to receive a target string forming a part of an electronic communication;

in response to receiving the target string, employing the computer system to determine a string eligibility criterion according to the target string;

employing the computer system to pre-filter a corpus of reference strings according to the string eligibility criterion, to produce a plurality of candidate strings;

in response to selecting the candidate strings, employing the computer system to perform a first comparison between a character histogram of the target string and a character histogram of a candidate string of the plurality of candidate strings, and a second comparison between a timestamp of the electronic communication and a timestamp of the candidate string; and

employing the computer system to determine whether the electronic communication is spam or non-spam according to a result of the first comparison and the second comparison.

2. The method of claim 1, wherein the corpus of reference strings comprises a plurality of clusters, each cluster including a set of mutually-similar strings, wherein each candidate string of the plurality of candidate strings is representative of a distinct cluster, and wherein the method further comprises, in response to performing the first comparison, employing the computer system to select a cluster from the plurality of clusters and to assign the target string to the selected cluster.

3. The method of claim 2, further comprising determining whether the target communication is spam or non-spam according to a plurality of timestamps, each timestamp of the plurality of timestamps corresponding to a member of the selected cluster.

4. The method of claim 2, further comprising:

in response to assigning the target string to the selected cluster, determining a count of cluster members of the selected cluster; and

determining whether the electronic communication is spam or non-spam according to the count of cluster members.

5. The method of claim 2, further comprising identifying the electronic communication as belonging to a selected spam wave according to the selected cluster.

6. The method of claim 1, wherein pre-filtering the corpus comprises:

determining a first string length of the target string and a second string length of a reference string of the corpus, and

when the first string length differs from the second string length by an amount smaller than a predetermined threshold, adding the reference string to the set of candidate strings.

7. The method of claim 1, wherein pre-filtering the corpus comprises:

determining a first count of distinct characters of the target string and a second count of distinct characters of a reference string of the corpus, and

when the first count differs from the second count by an amount smaller than a predetermined threshold, adding the reference string to the set of candidate strings.

8. The method of claim 1, wherein pre-filtering the corpus comprises:

determining a first string score of the target string as a function of;

9. The method of claim 1, wherein performing the first comparison comprises determining an inter-string distance as a function of:

10. The method of claim 9, wherein the inter-string distance is further determined as a function of:

11. The method of claim 1, wherein performing the first comparison comprises determining an inter-string distance as a function of:

12. The method of claim 1, wherein the electronic communication comprises a blog comment.

13. The method of claim 1, wherein the electronic communication comprises a message posted on a social network site.

14. A computer system comprising at least a processor programmed to:

receive a target string forming a part of an electronic communication;

in response to receiving the target string, determine a string eligibility criterion according to the target string;

pre-filter a corpus of reference strings according to the string eligibility criterion, to produce a plurality of candidate strings;

in response to selecting the candidate strings, perform a first comparison between a character histogram of the target string and a character histogram of a candidate string of the plurality of candidate strings, and a second comparison between a timestamp of the electronic communication and a timestamp of the candidate string; and

determine whether the electronic communication is spam or non-spam according to a result of the first comparison and the second comparison.

15. The system of claim 14, wherein the corpus of reference strings comprises a plurality of clusters, each cluster including a set of similar strings, wherein each candidate string of the plurality of candidate strings is representative of a distinct cluster, and wherein the processor is further programmed, in response to performing the first comparison, to select a cluster from the plurality of clusters and to assign the target string to the selected cluster.

16. The system of claim 15, further comprising determining whether the target communication is spam or non-spam according to a plurality of timestamps, each timestamp of the plurality of timestamps corresponding to a member of the selected cluster.

17. The system of claim 15, wherein the processor is further programmed to:

in response to assigning the target string to the selected cluster, determine a count of cluster members of the selected cluster; and

determine whether the electronic communication is spam or non-spam according to the count of cluster members.

18. The system of claim 15, wherein the processor is further programmed to identify the electronic communication as belonging to a selected spam wave according to the selected cluster.

19. The system of claim 14, wherein pre-filtering the corpus comprises:

determining a first string length of the target string and a second string length of a reference string of the corpus, and

when the first string length differs from the second string length by an amount smaller than a predetermined threshold, adding the reference string to the set of candidate strings.

20. The system of claim 14, wherein pre-filtering the corpus comprises:

determining a first count of distinct characters of the target string and a second count of distinct characters of a reference string of the corpus, and

when the first count differs from the second count by an amount smaller than a predetermined threshold, adding the reference string to the set of candidate strings.

21. The system of claim 14, wherein pre-filtering the corpus comprises:

determining a first string score of the target string as a function of;

22. The system of claim 14, wherein performing the first comparison comprises determining an inter-string distance as a function of:

23. The system of claim 22, wherein the inter-string distance is further determined as a function of:

24. The system of claim 14, wherein performing the first comparison comprises determining an inter-string distance as a function of:

25. The system of claim 14, wherein the electronic communication comprises a blog comment.

26. The system of claim 14, wherein the electronic communication comprises a message posted on a social network site.

27. A method comprising:

employing a computer system to receive an electronic communication;

in response to receiving the electronic communication, employing the computer system to extract a target string from the electronic communication;

employing the computer system to transmit the target string to an anti-spam server; and

in response to transmitting the target string, receiving a target label indicative of whether the electronic communication is spam or non-spam, wherein the target label is determined at the anti-spam server and wherein determining the target label comprises;

employing the anti-spam server to determine an eligibility criterion according to the target string;

employing the anti-spam server to pre-filter a corpus of reference strings according to the criterion condition, to produce a plurality of candidate strings;

in response to selecting the candidate strings, employing the anti-spam server to perform a first comparison between a character histogram of the target string and a character histogram of a candidate string of the plurality of candidate strings, and a second comparison between a timestamp of the electronic communication and a timestamp of the candidate string; and

employing the anti-spam server to determine the target label according to a result of the first comparison and the second comparison.

28. A method comprising:

employing a computer system to receive a target string forming a part of an electronic communication;

in response to receiving the target string, employing the computer system to determine a string eligibility criterion according to the target string;

employing the computer system to pre-filter a corpus of reference strings according to the string eligibility criterion, to produce a plurality of candidate strings;

in response to selecting the candidate strings, employing the computer system to determine an inter-string distance separating the target string from a candidate string of the plurality of candidate strings, the inter-string distance determined according to a count of occurrences of a selected character within the target string and a count of occurrences of the selected character within the candidate string; and

employing the computer system to determine whether the electronic communication is spam or non-spam according to the inter-string distance.