Spam filtering with probabilistic secure hashes

• US 7,660,865 B2
• Filed: 08/12/2004
• Issued: 02/09/2010
• Est. Priority Date: 08/12/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mehr, John D., Hulten, Geoffrey J., Rounthwaite, Robert L., Goodman, Joshua T., Mishra, Manav, Murphy, Elissa E.
• Primary Examiner(s): Phillips; Hassan
• Assistant Examiner(s): Tiv; Backhean
• Application Number:
  US10/917,077
• Publication Number:
  US 20060036693A1
• Time in Patent Office: 2,007 Days
• Field of Search: 709/207, 709/206, 713/151, 713/153
• US Class Current: 709/207
• CPC Class Codes: H04L 51/212 using filtering or selective blocking
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity

Abstract

Disclosed are signature-based systems and methods that facilitate spam detection and prevention at least in part by calculating hash values for an incoming message and then determining a probability that the hash values indicate spam. In particular, the signatures generated for each incoming message can be compared to a database of both spam and good signatures. A count of the number of matches can be divided by a denominator value. The denominator value can be an overall volume of messages sent to the system per signature for example. The denominator value can be discounted to account for different treatments and timing of incoming messages. Furthermore, secure hashes can be generated by combining portions of multiple hashing components. A secure hash can be made from a combination of multiple hashing components or multiple combinations thereof. The signature based system can also be integrated with machine learning systems to optimize spam prevention.

Claims

1. One or more program storage mediums readable by at least a computer having at least one memory and at least one processor, the one or more mediums tangibly embodying one or more programs of instructions executable by the at least one computer to implement a signature-based message filtering system that facilitates spam prevention and protection comprising:

a signature assignment component that determines and assigns one or more signatures for an incoming message based in part on at least one hash function; and

a signature analysis component that determines a probability that at least a subset of the message'"'"'s signatures are indicative of spam based in part on a count of presumed spam signatures that match and a count of the overall volume of messages sent to the system per signature,

wherein the signature analysis component determines a complaint rate by taking a product of a percentage of recipient complaints by a number of read messages and dividing the product by an overall volume of incoming messages, and based upon how old the read messages are.

2. The system of claim 1, wherein the signature analysis component that determines a probability that at least a subset of the message'"'"'s signatures are indicative of spam based in part on a count of presumed spam signatures that match and a count of presumed good signatures that match.

3. The system of claim 2, further comprising a signature store that is accessible by the signature analyzing component to facilitate determining the probability, the signature store comprising signatures corresponding to the presumed good messages and presumed spam messages.

4. The system of claim 2, the signature analysis component employs good message data to facilitate determining whether the incoming message is spam.

5. The system of claim 2, the signature analysis component employs good message data from polling users participating in a feedback loop filtering system.

6. The system of claim 1, the signatures comprising at least one of a total hash value, source IP address of a message, or URLs contained in a message.

7. The system of claim 1, the signature analysis component discounts the overall values of signatures by at least a portion of incoming messages marked as junk.

8. The system of claim 1, the signature analysis component discounts the overall volume based on timing, age of presumed spam signatures, or a number of messages seen per user.

9. The system of claim 1, the signature analysis component evaluates a number of sources that report messages as junk.

10. The system of claim 9, the number of sources comprising at least two of the following:

honeypot, polling, and junk reporting.

11. The system of claim 1, the signature analysis component samples any subset of presumed spam signatures or overall volume per signature to facilitate determining whether the incoming message is spam.

12. The system of claim 1, the overall volume of messages sent to the system per signature is determined at least in part by counting messages received after receiving at least one complaint that any particular message is spam.

13. The system of claim 12, the overall volume of messages sent to the system per signature is tracked for a period of time such that at least one signature is discarded when no complaints for that signature are received in a given time period.

14. The system of claim 1, wherein multiple signatures are assigned or used per incoming message.

15. The system of claim 14, further comprising multiple hashing components used to generate secure hashes such that at least some of the signatures derive from multiple hashing components.

16. The system of claim 15, at least one of the multiple hashing components is used in at least two of the signatures.

17. The system of claim 16, further comprising an artificial intelligence component that automatically selects one or more combinations of hashing components to maximize the performance of an anti-spam system.

18. The system of claim 16, wherein at least a portion of the signatures are any one of broad or narrow.

19. The system of claim 15, at least a portion of the IP address is used in at least one hashing component.

20. The system of claim 15, at least a portion of a URL in the message is used in at least one hashing component.

21. The system of claim 20, the signature assignment component generates multiple signatures for at least a subset of the URLs when multiple URLs are present in the message.

22. The system of claim 15, at least one hashing component includes at least one of:

sender'"'"'s reputation, presence of HTML, presence of JAVA script, language of message, presence of at least one image, and presence of at least one attachment.

23. The system of claim 1 is integrated with a discriminatively trained machine learning system such that output from the signature-based message filtering system is combined with output from the signature-based system.

24. The system of claim 23, signatures that represent good messages are used to rescue messages otherwise marked as spam by the machine learning system.

25. The system of claim 23, wherein at least a portion of at least one of the following:

presumed spam signatures, presumed good signatures, and signatures assigned to incoming messages are used as features of the machine learning system.

26. The system of claim 23, wherein counts or probabilities of signatures are used as inputs into the machine learning system.

27. The system of claim 23, wherein verdicts from the signature-based message filtering system and the machine learning system are combined by another machine learning system.

28. The system of claim 23, wherein the message'"'"'s presumed spam signatures are added to a signature database when the machine learning system provides a minimum spam score for that message.

29. The system of claim 1, wherein the signature analysis component adjusts a complaint threshold in relation to elapsed time in determining the probability of spam.

30. A signature-based method that facilitates filtering messages for spam detection by a computer processor comprising:

assigning, by the computer processor, one or more signatures to an incoming message based in part upon at least one hash function;

determining a probability that at least a subset of the message'"'"'s signatures are indicative of spam based in part on a count of presumed spam signatures that match and a count of the overall volume of messages sent to the system per signature; and

determining a complaint rate by taking a product of a percentage of recipient complaints by a number of read messages and dividing the product by an overall volume of incoming messages, and based upon how old the read messages are.

31. The method of claim 30, the signatures comprising at least one of a total hash value, stored IP address, or URL of a message.

32. The method of claim 30, further comprising discounting the overall volume of messages sent to the system per signature based in part on at least one of the following:

excluding at least a portion of incoming messages are marked as junk upon receipt from the overall volume;

counting messages received only after receiving at least one complaint that any particular message is spam or at least one message in a honeypot; and

counting a number of messages seen per user within a time period.

33. The method of claim 30, determining the probability that at least a subset of the message'"'"'s signatures are indicative of spam comprises at least one of the following:

evaluating number of spam or good message sources;

analyzing a subset of presumed spam signatures; and

analyzing a subset of the overall volume of messages received per signature.

34. The method of claim 30, further comprising generating secure hashes in part by combining a plurality of hashing components to make a plurality of combinations and in part by combining a plurality of combinations.

35. The method of claim 34, wherein at least one the hashing component comprises at least a portion of an IP address and at least a portion of a URL.

36. The method of claim 34, further comprising calculating multiple signature values for at least one hashing component per message when multiple instances of the hashing component are found in the message.

37. The method of claim 34, further comprising incrementally adding one or more combinations of hashing components to a first combination to maximize the performance of an anti-spam system.

38. The method of claim 37, integrating the machine learning system comprises performing at least one of the following:

rescuing messages otherwise marked as spam by considering for good message signatures;

employing one or more signatures as features into the machine learning system;

combining verdicts from the signature-based method and the machine learning system via another machine learning system; and

adding spam signatures associated with an incoming message to a database comprising presumed spam signatures when the machine learning system provides a minimum spam score for that message.

39. The method of claim 30, further comprising integrating a discriminatively trained machine learning system therein to advance spam detection capabilities.

40. The signature-based method of claim 30, wherein determining a probability that at least a subset of the message'"'"'s signatures are indicative of spam based in part on a count of presumed spam signatures that match and a count of presumed good signatures that match.

41. The signature-based method of claim 30, further comprising adjusting a complaint threshold in relation to elapsed time in determining the probability of spam.

42. One or more program storage mediums readable by at least a computer having at least one memory and at least one processor, the one or more mediums tangibly embodying one or more programs of instructions executable by the at least one computer to implement a signature-based system that facilitates filtering messages for spam detection comprising:

means for assigning one or more signatures to an incoming message based in part upon at least one hash function; and

means for determining a probability that at least a subset of the message'"'"'s signatures are indicative of spam based in part on a match count to presumed spam signatures that match and the overall volume of messages sent to the system per signature, wherein a complaint rate is determined by taking a product of a percentage of recipient complaints by a number of read messages and dividing the product by an overall volume of incoming messages, and based upon how old the read messages are.

43. The system of claim 42, further comprising means for generating secure hashes in part by combining a plurality of hashing components to make a plurality of combinations and in part by combining a plurality of combinations.

44. A computer storage medium having stored thereon a data packet adapted to be transmitted between two or more computer processes facilitating improved detection of spam, the data packet comprising:

information which when receiving by a computer processor determines a probability that at least a subset of a message'"'"'s signatures are indicative of spam based in part on a match count to the overall volume of messages sent to the system per signature, wherein a complaint rate is determined by taking a product of a percentage of recipient complaints by a number of read messages and dividing the product by an overall volume of incoming messages, and based upon how old the read messages are.