System and method for spam filtering using shingles

• US 8,996,638 B2
• Filed: 11/01/2013
• Issued: 03/31/2015
• Est. Priority Date: 06/06/2013
• Status: Active Grant

• Current Assignee: Kaspersky Lab ZAO
• Original Assignee: Kaspersky Lab ZAO
• Inventors: Skvortsov, Vladimir A., Loseva, Darya V., Zagorsky, Sergey G.
• Primary Examiner(s): Christensen, Scott B
• Application Number:
  US14/069,889
• Publication Number:
  US 20140365585A1
• Time in Patent Office: 515 Days
• Field of Search: None
• US Class Current: 709/206
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 51/212 using filtering or selective blocking
• CPC Class Codes: H04L 51/52 for supporting social networking services

Abstract

Disclosed system and methods for detecting spam using shingles. In one aspect, the system receives an electronic message including at least a text portion. The system identifies in the received message insignificant text portions. The system then removes identified insignificant text portions to generate an abridged message. The system then generates a set of shingles from the abridged message. The system then indentifies in the generated set of shingles one or more shingles that occur only in messages not containing spam. The system then removes one or more identified shingles from the generated set of shingles to generate a reduced set of shingles. The system then performs spam filtering of the reduced set of shingles to determine whether the received message contains spam.

Claims

1. A computer-implemented method for detecting spam, the method comprising:

receiving an electronic message;

identifying in the received message one or more insignificant text portions based on a text pattern database storing a plurality of defined insignificant text patterns not containing spam, each defined insignificant text pattern comprising a text pattern, text identification information and a usage frequency;

removing the one or more identified insignificant text portions from the message to generate an abridged message upon detecting the one or more identified insignificant text portions matching at least one of the plurality of defined insignificant text patterns;

canonizing text of the abridge message;

generating a set of shingles from the abridged and canonized message;

identifying in generated set of shingles one or more shingles based on a shingles database storing a plurality of defined insignificant shingles that occur only in messages not containing spam, each defined insignificant shingle comprising a hash, a shingle pattern, text identification information corresponding to the shingle pattern, and a usage frequency;

removing one or more identified shingles from the generated set of shingles to generate a reduced set of shingles upon detecting the one or more identified shingles matching at least one of the plurality of defined shingles; and

performing spam filtering of the reduced set of shingles to determine whether the received message contains spam.

2. The method of claim 1, wherein the plurality of defined insignificant text patterns comprise a plurality of words, phrases, symbols that occur only in messages not containing spam.

3. The method of claim 2, further comprising:

collecting from known users messages not containing spam;

identifying in the collected messages insignificant text patterns and shingles; and

storing the identified insignificant text patterns and insignificant shingles in each respective text pattern database and shingles database.

4. The method of claim 1, wherein performing spam filtering of the reduced set of shingles to determine whether the received message contains spam includes performing Bayes spam filtering of the reduced set of shingles.

5. The method of claim 1, wherein performing spam filtering of the reduced set of shingles to determine whether the received message contains spam includes performing cluster filtering of the reduced set of shingles.

6. A computer system for detecting spam, the system comprising:

a processor configured to;

receive an electronic message;

identify in the received message one or more insignificant text portions based on a text pattern database storing a plurality of defined insignificant text patterns not containing spam, each defined insignificant text pattern comprising a text pattern, text identification information and a usage frequency;

remove the one or more identified insignificant text portions from the message to generate an abridged message upon detecting the one or more identified insignificant text portions matching at least one of the plurality of defined insignificant text patterns;

canonize text of the abridge message;

generate a set of shingles from the abridged and canonized message;

identify in the generated set of shingles one or more shingles based on a shingles database storing a plurality of defined insignificant shingles that occur only in messages not containing spam, each defined insignificant shingle comprising a hash, a shingle pattern, text identification information corresponding to the shingle pattern, and a usage frequency;

remove one or more identified shingles from the generated set of shingles to generate a reduced set of shingles upon detecting the one or more identified shingles matching at least one of the plurality of defined shingles; and

perform spam filtering of the reduced set of shingles to determine whether the received message contains spam.

7. The system of claim 6, wherein the plurality of defined insignificant text patterns comprise a plurality of words, phrases, symbols that occur only in messages not containing spam.

8. The system of claim 7, wherein the processor is further configured to:

collect from known users messages not containing spam;

identify in the collected messages insignificant text patterns and shingles; and

store the identified insignificant text patterns and insignificant shingles in each respective text pattern database and shingles database.

9. The system of claim 6, wherein to perform spam filtering of the reduced set of shingles to determine whether the received message contains spam, the processor is further configured to perform Bayes spam filtering of the reduced set of shingles.

10. The system of claim 6, wherein to perform spam filtering of the reduced set of shingles to determine whether the received message contains spam, the processor is further configured to perform cluster filtering of the reduced set of shingles.

11. A computer program product stored on a non-transitory computer-readable storage medium, the computer program product comprising computer-executable instructions for detecting spam, including instructions for:

receiving an electronic message;

identifying in the received message one or more insignificant text portions based on a text pattern database storing a plurality of defined insignificant text patterns not containing spam, each defined insignificant text pattern comprising a text pattern, text identification information and a usage frequency;

removing the one or more identified insignificant text portions from the message to generate an abridged message upon detecting the one or more identified insignificant text portions matching at least one of the plurality of defined insignificant text patterns;

canonizing text of the abridge message;

generating a set of shingles from the abridged and canonized message;

identifying in the generated set of shingles one or more shingles based on a shingles database storing a plurality of defined insignificant shingles that occur only in messages not containing spam, each defined insignificant shingle comprising a hash, a shingle pattern, text identification information corresponding to the shingle pattern, and a usage frequency;

removing one or more identified shingles from the generated set of shingles to generate a reduced set of shingles upon detecting the one or more identified shingles matching at least one of the plurality of defined shingles; and

performing spam filtering of the reduced set of shingles determine whether the received message contains spam.

12. The product of claim 11, wherein the plurality of defined insignificant text patterns comprise a plurality of words, phrases, symbols that occur only in messages not containing spam.

13. The product of claim 12, further comprising instructions for:

collecting from known users messages not containing spam;

identifying in the collected messages insignificant text patterns and shingles; and

storing the identified insignificant text patterns and insignificant shingles in each respective text pattern database and shingles database.

14. The product of claim 11, wherein instructions for performing spam filtering of the reduced set of shingles to determine whether the received message contains spam include instructions for performing Bayes spam filtering of the reduced set of shingles.

15. The product of claim 11, wherein instructions for performing spam filtering of the reduced set of shingles to determine whether the received message contains spam include instructions for performing cluster filtering of the reduced set of shingles.