Source: http://www.google.com/patents/US20040073617?dq=7,181,690
Timestamp: 2017-09-22 04:58:09
Document Index: 133636466

Matched Legal Cases: ['§ 119', 'Application No. 60', '§ 119', 'Application No. 60', '§ 119', 'Application No. 60']

Patent US20040073617 - Hash-based systems and methods for detecting and preventing transmission of ... - Google Patents
A system (120) detects transmission of potentially unwanted e-mail messages. The system (120) may receive e-mail messages and generate hash values based on one or more portions of the e-mail messages. The system (120) may then determine whether the generated hash values match hash values associated with...http://www.google.com/patents/US20040073617?utm_source=gb-gplus-sharePatent US20040073617 - Hash-based systems and methods for detecting and preventing transmission of unwanted e-mail
Publication number US20040073617 A1
Application number US 10/654,771
Also published as US8204945, US8272060, US20090031129, US20090031136, US20090132669, US20090158046, US20090158435, US20090182867, US20090313339, US20100205265, US20100205670, US20100205671, US20100205672, US20130014261
Publication number 10654771, 654771, US 2004/0073617 A1, US 2004/073617 A1, US 20040073617 A1, US 20040073617A1, US 2004073617 A1, US 2004073617A1, US-A1-20040073617, US-A1-2004073617, US2004/0073617A1, US2004/073617A1, US20040073617 A1, US20040073617A1, US2004073617 A1, US2004073617A1
Inventors Walter Milliken, William Strayer, Stephen Milligan
Original Assignee Milliken Walter Clark, Strayer William Timothy, Milligan Stephen Douglas
Patent Citations (99), Referenced by (297), Classifications (11), Legal Events (6)
US 20040073617 A1
generating hash values, as generated hash values, based on one or more portions of the plurality of e-mail messages;
determining whether the generated hash values match hash values associated with prior e-mail messages; and
determining that one of the plurality of e-mail messages is a potentially unwanted e-mail message when one or more of the generated hash values associated with the one of the plurality of e-mail messages match one or more of the hash values associated with the prior e-mail messages.
3. The method of claim 1, wherein the generating hash values includes:
4. The method of claim 1, wherein the generating hash values includes:
5. The method of claim 1, wherein the generating hash values includes:
6. The method of claim 1, wherein the generating hash values includes:
7. The method of claim 1, wherein the generating hash values includes:
8. The method of claim 1, wherein the generating hash values includes:
9. The method of claim 1, wherein the generating hash values includes:
10. The method of claim 1, wherein the generating hash values includes:
comparing the generated hash values to hash values corresponding to known unwanted e-mails.
12. The method of claim 11, wherein the known unwanted e-mails include at least one of e-mails containing a virus, e-mails containing a worm, and unsolicited commercial e-mails.
hashing at least one of a main text and an attachment to generate one or more first hash values, and
determining a first suspicion count based on a number of the hash values associated with the prior e-mail messages that match the one or more first hash values, and
determining a second suspicion count based on a number of the hash values associated with the prior e-mail messages that match the second hash value.
16. The method of claim 15, wherein the determining that one of the plurality of e-mail messages is a potentially unwanted e-mail message includes:
determining that the one of the plurality of e-mail messages is a potentially unwanted email message when the first suspicion count is significantly higher than the second suspicion count.
taking remedial action when the one of the plurality of e-mail messages is a potentially unwanted e-mail message, the taking remedial action including at least one of:
discarding the one of the plurality of e-mail messages,
bouncing the one of the plurality of e-mail messages,
marking the one of the plurality of e-mail messages with a warning,
subjecting the one of the plurality of e-mail messages to a virus or worm detection process,
creating a notification message, and
generating a suspicion score for the one of the plurality of e-mail messages and using the suspicion score to identify further processing for the one of the plurality of e-mail messages.
generating a suspicion score for the plurality of e-mail messages based on a result of the determination of whether the generated hash values match hash values associated with prior e-mail messages; and
taking remedial action when the one of the plurality of e-mail messages is a potentially unwanted e-mail message, the taking remedial action including:
determining whether a newly received e-mail message exceeds a mail quota,
identifying an earlier-received e-mail message with a highest suspicion score,
determining whether the suspicion score of the newly received e-mail message is lower than the suspicion score of the earlier-received e-mail message when the newly received e-mail message exceeds the mail quota,
deleting the earlier-received e-mail message when the suspicion score of the newly received e-mail message is lower than the suspicion score of the earlier-received e-mail message, and
storing the newly received e-mail message.
19. The method of claim 1, wherein the generating hash values and the determining whether the hash values match hash values associated with prior e-mail messages are performed incrementally as the plurality of e-mail messages are being received.
taking remedial action when the suspicion score of an e-mail message of the plurality of e-mail messages is above a threshold, the taking remedial action including rejecting the e-mail message.
21. The method of claim 20, wherein the rejecting occurs before the e-mail message is completely received.
comparing the generated hash values to known legitimate mailing lists; and
passing the plurality of e-mail messages without further examination when the generated hash values match one or more of the known legitimate mailing lists.
23. The method of claim 22, wherein the comparing the generated hash values includes:
determining whether the plurality of e-mail messages originated from the known legitimate mailing lists.
24. The method of claim 1, wherein the generating hash values includes:
hashing sender-related header fields to generate one or more second hash values.
25. The method of claim 24, wherein the sender-related header fields include at least one of a From header field, a Sender header field, and a Reply-To header field.
determining a first suspicion count based on a number of the hash values associated with the prior e-mail messages that match the first hash value, and
determining one or more second suspicion counts based on a number of the hash values associated with the prior e-mail messages that match the one or more second hash values.
27. The method of claim 26, wherein the determining that one of the plurality of e-mail messages is a potentially unwanted e-mail message includes:
determining that the one of the plurality of e-mail messages is a potentially unwanted e-mail message when the first suspicion count is higher than the one or more second suspicion counts.
28. The method of claim 1, wherein the generating hash values includes:
29. The method of claim 28, wherein the determining whether the generated hash values match hash values associated with prior e-mail messages includes:
determining whether the main text hash matches a substantially higher number of the hash values associated with the prior e-mail messages than the at least one header hash; and
wherein the determining that one of the plurality of e-mail messages is a potentially unwanted e-mail message includes:
determining that the one of the plurality of e-mail messages is a potentially unwanted e-mail message when the main text hash matches a substantially higher number of the hash values associated with the prior e-mail messages than the at least one header hash.
30. A system for detecting transmission of potentially unwanted e-mails, comprising:
means for hashing one or more portions of the plurality of e-mails to generate hash values, as generated hash values;
means for determining whether the generated hash values match hash values associated with prior e-mails; and
means for determining that the plurality of e-mails are potentially unwanted e-mails when one or more of the generated hash values match one or more of the hash values associated with the prior e-mails.
31. A mail server, comprising:
one or more hash memories configured to store count values associated with a plurality of hash values; and
receive an e-mail message,
hash one or more portions of the e-mail message to generate hash values, as generated hash values,
increment the count values corresponding to the generated hash values, as incremented count values, and
determine whether the e-mail message is a potentially unwanted e-mail message based on the incremented count values.
32. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to perform a plurality of hashes on a plurality of variable-sized blocks of a main text of the e-mail message.
33. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to perform a plurality of hashes on a plurality of fixed-sized blocks of a main text of the e-mail message.
34. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to perform a plurality of hashes on a main text of the e-mail message using a plurality of different hash functions.
35. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to:
attempt to expand an attachment of the e-mail message, and
hash the attachment after attempting to expand the attachment.
36. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to perform a plurality of hashes on a plurality of variable-sized blocks of an attachment of the e-mail message.
37. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to perform a plurality of hashes on a plurality of fixed-sized blocks of an attachment of the e-mail message.
38. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to perform a plurality of hashes on an attachment of the e-mail message using a plurality of different hash functions.
39. The server of claim 31, wherein the hash processor is further configured to compare the generated hash values to hash values corresponding to known unwanted e-mails.
40. The server of claim 39, wherein the known unwanted e-mails include at least one of e-mails containing a virus, e-mails containing a worm, and unsolicited commercial e-mails.
41. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to:
hash at least one of a main text and an attachment of the e-mail message to generate one or more first hash values, and
hash a concatenation of first and second header fields of the e-mail message to generate a second hash value.
42. The server of claim 41, wherein the first and second header fields include a From header field and a To header field.
43. The server of claim 41, wherein when determining whether the e-mail message is a potentially unwanted e-mail message, the hash processor is configured to identify the e-mail message as a potentially unwanted e-mail message when the count value corresponding to one or more first hash values is significantly higher than the count value corresponding to the second hash value.
44. The server of claim 31, wherein the hash processor is further configured to take remedial action when the e-mail message is a potentially unwanted e-mail message, when taking remedial action, the hash processor is configured to at least one of:
discard the e-mail message,
bounce the e-mail message,
mark the e-mail message with a warning,
subject the e-mail message to a virus or worm detection process,
create a notification message, and
generate a suspicion score for the e-mail message and use the suspicion score to identify further processing for the e-mail message.
45. The server of claim 31, wherein the hash processor is further configured to:
generate a suspicion score for the e-mail message based on the incremented count values,
determine whether a newly received e-mail message exceeds a mail quota,
identify an earlier-received e-mail message with a highest suspicion score,
determine whether a suspicion score of the newly received e-mail message is lower than the suspicion score of the earlier-received e-mail message when the newly received e-mail message exceeds the mail quota,
delete the earlier-received e-mail message when the suspicion score of the newly received e-mail message is lower than the suspicion score of the earlier-received e-mail message, and
store the newly received e-mail message.
46. The server of claim 31, wherein the hash processor is configured to hash the one or more portions of the e-mail message and increment the count values incrementally as the e-mail message is being received.
47. The server of claim 46, wherein the hash processor is further configured to:
reject the e-mail message when the suspicion score of the e-mail message is above a threshold.
48. The server of claim 47, wherein the rejecting occurs before the e-mail message is completely received.
49. The server of claim 31, wherein the hash processor is further configured to:
compare the generated hash values to known legitimate mailing lists, and
pass the e-mail message without further examination when the generated hash values match one of the known legitimate mailing lists.
50. The server of claim 49, wherein the hash processor is configured to:
determine whether the e-mail message originated from one of the known legitimate mailing lists.
51. The server of claim 31, wherein the hash processor is configured to:
hash a main text of the e-mail message to generate a first hash value, and
hash sender-related header fields of the e-mail message to generate one or more second hash values.
52. The server of claim 51, wherein the sender-related header fields include at least one of a From header field, a Sender header field, and a Reply-To header field.
53. The server of claim 51, wherein when determining whether the e-mail message is a potentially unwanted e-mail message, the hash processor is configured to identify the e-mail message as a potentially unwanted e-mail message when the count value corresponding to the first hash value is higher than the count values corresponding to the one or more second hash values.
54. The server of claim 31, wherein when hashing one or more portions of the e-mail message, the hash processor is configured to:
perform a plurality of hashes on a main text of the e-mail message to generate main text hashes, and
hash at least one header field of the e-mail message to generate at least one header hash.
55. The server of claim 54, when determining whether the e-mail message is a potentially unwanted e-mail message, the hash processor is configured to:
generate a score for the main text based on count values corresponding to the main text hashes and a score for the at least one header field based on the count value corresponding to the at least one header hash, and
identify the e-mail message as a potentially unwanted e-mail message when the score for the main text is substantially higher than the score for the at least one header hash.
56. A method for detecting transmission of unwanted e-mail messages, comprising:
receiving a plurality of e-mail messages; and
detecting unwanted e-mail messages from the plurality of e-mail messages based on hashes of previously received e-mail messages, where multiple hashes are performed on each of the plurality of e-mail messages.
57. A method for detecting transmission of potentially unwanted e-mail messages, comprising:
generating a plurality of hash values, as generated hash values, over blocks of the received e-mail message, the blocks including at least two of a main text portion, an attachment portion, and a header portion of the received e-mail message;
determining that the received e-mail message is a potentially unwanted e-mail message when one or more of the generated hash values associated with the received e-mail message match one or more of the hash values associated with the prior e-mail messages.
58. The method of claim 57, wherein the blocks are variable-sized blocks of the received e-mail message.
59. In a network of cooperating mail servers, one of the mail servers comprising:
one or more hash memories configured to store information relating to hash values corresponding to previously-observed e-mails; and
receive at least some of the hash values from another one or more of the cooperating mail servers,
store information relating to the at least some of the hash values in at least one of the one or more hash memories,
hash one or more portions of the received e-mail message to generate hash values, as generated hash values,
determine whether the generated hash values match the hash values corresponding to previously-observed e-mails, and
identify the received e-mail message as a potentially unwanted e-mail message when one or more of the generated hash values associated with the received e-mail message match one or more of the hash values corresponding to previously-observed e-mails.
60. A mail server, comprising:
receive e-mail messages,
hash one or more portions of the received e-mail messages to generate hash values, as generated hash values,
generate suspicion scores for the received e-mail messages based on the incremented count values.
61. The server of claim 60, wherein the hash processor is further configured to:
maintain a counter corresponding to each of the one or more hash memories, and
decrement ones of the count values based on the counter.
62. The server of claim 61, wherein the hash processor is configured to:
determine when a value of the counter reaches a threshold, and
decrement one of the count values each time another one of the count values is incremented after the value of the counter reaches the threshold.
63. The server of claim 62, wherein the hash processor is further configured to:
identify a count value to decrement,
determine whether the identified count value is non-zero, and
decrement the identified count value when the identified count value is non-zero.
64. The server of claim 63, wherein the hash processor is further configured to:
examine next sequential ones of the count values until a non-zero count value is found when the identified count value is zero, and
decrement the non-zero count value.
65. A method for preventing transmission of unwanted e-mail messages, comprising:
generating a plurality of hash values, as generated hash values, over portions of the e-mail message as the e-mail message is being received;
incrementally determining whether the generated hash values match hash values associated with prior e-mail messages;
generating a suspicion score for the e-mail message based on the incremental determining; and
rejecting the e-mail message when the suspicion score of the e-mail message is above a threshold.
66. The method of claim 65, wherein the rejecting occurs before the e-mail message is completely received.
This application claims priority under 35 U.S.C. § 119 based on U.S. Provisional Application No. 60/407,975, filed Sep. 5, 2002, the disclosure of which is incorporated herein by reference. This application is also a continuation-in-part of U.S. patent application Ser. No. 10/251,403, filed Sep. 20, 2002, which claims priority under 35 U.S.C. § 119 based on U.S. Provisional Application No. 60/341,462, filed Dec. 14, 2001, both of which are incorporated herein by reference. This application is also a continuation-in-part of U.S. patent application Ser. No. 09/881,145, and U.S. patent application Ser. No. 09/881,074, both of which were filed on Jun. 14, 2001, and both of which claim priority under 35 U.S.C. § 119 based on U.S. Provisional Application No. 60/212,425, filed Jun. 19, 2000, all of which are incorporated herein by reference.
Existing techniques for detecting viruses, worms, and spam examine each e-mail message individually. In the case of viruses and worms, this typically means examining attachments for byte-strings found in known viruses and worms (possibly after uncompressing or de-archiving attached files), or simulating execution of the attachment in a “safe” compartment and examining its behaviors. Similarly, existing spam filters usually examine a single e-mail message looking for heuristic traits commonly found in unsolicited commercial e-mail, such as an abundance of Uniform Resource Locators (URLs), heavy use of all-capital-letter words, use of colored text or large fonts, and the like, and then “score” the message based on the number and types of such traits found. Both the anti-virus and the anti-spam techniques can demand significant processing of each message, adding to the resource burden imposed by unwanted email. Neither technique makes use of information collected from other recent messages.
In accordance with a further aspect of the invention, a method for detecting transmission of potentially unwanted e-mail messages is provided. The method includes receiving an e-mail message; generating hash values over blocks of the e-mail message, where the blocks include at least two of a main text portion, an attachment portion, and a header portion of the e-mail message; determining whether the generated hash values match hash values associated with prior e-mail messages; and determining that the e-mail message is a potentially unwanted e-mail message when one or more of the generated hash values associated with the email message match one or more of the hash values associated with the prior e-mail messages.
In accordance with yet another aspect of the invention, a mail server is provided. The mail server includes one or more hash memories and a hash processor. The one or more hash memories is/are configured to store count values associated with hash values. The hash processor is configured to receive e-mail messages, hash one or more portions of the received email messages to generate hash values, increment the count values corresponding to the generated hash values, as incremented count values, and generate suspicion scores for the received e-mail messages based on the incremented count values.
[0019]FIG. 2 is an exemplary diagram of the e-mail server of FIG. 1 according to an implementation consistent with the principles of the invention;
[0020]FIG. 3 is an exemplary functional block diagram of the e-mail server of FIG. 2 according to an implementation consistent with the principles of the invention;
[0021]FIG. 4 is an exemplary diagram of the hash processing block of FIG. 3 according to an implementation consistent with the principles of the invention; and
[0032]FIG. 1 is a diagram of an exemplary system 100 in which systems and methods consistent with the present invention may be implemented. System 100 includes mail clients 110 connected to a mail server 120 via a network 130. Connections made in system 100 may be via wired, wireless, and/or optical communication paths. While FIG. 1 shows three mail clients 110 and a single mail server 120, there can be more or fewer clients and servers in other implementations consistent with the principles of the invention.
[0036]FIG. 2 is an exemplary diagram of mail server 120 according to an implementation consistent with the principles of the invention. Server 120 may include bus 210, processor 220, main memory 230, read only memory (ROM) 240, storage device 250, input device 260, output device 270, and communication interface 280. Bus 210 permits communication among the components of server 120.
[0041]FIG. 3 is an exemplary functional block diagram of mail server 120 according to an implementation consistent with the principles of the invention. Server 120 may include a Simple Mail Transfer Protocol (SMTP) block 310, a Post Office Protocol (POP) block 320, an Internet Message Access Protocol (IMAP) block 330, and a hash processing block 340.
IMAP block 330 may provide another mechanism by which mail clients 110 can retrieve e-mail from mail server 120. IMAP block 330 may permit mail clients 110 to access remote e-mail as if the e-mail was local to mail clients 1110.
[0046]FIG. 4 is an exemplary diagram of hash processing block 340 according to an implementation consistent with the principles of the invention. Hash processing block 340 may include hash processor 410 and one or more hash memories 420. Hash processor 410 may include a conventional processor, an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or some other type of device that generates one or more representations for each received e-mail and records the e-mail representations in hash memory 420.
To further illustrate the use of representations, a 32-bit hash value, or digest, may be computed across portions of each e-mail. Then the hash value may be stored in hash memory 420 or may be used as an index, or address, into hash memory 420. Using the hash value, or an index derived therefrom, results in efficient use of hash memory 420 while still allowing the content of each e-mail passing through mail server 120 to be identified.
For e-mail following the Internet mail standard RFC 822 (and its various extensions), hashing of certain individual e-mail header fields into field-specific hash memories 420 may be useful. Among the header fields for which this may be helpful are: (1) various sender-related fields, such as “From:”, “Sender:”, “Reply-To:”, “Return-Path:” and “Error-To:”; (2) the “To:” field (often a fixed value for a mailing list, frequently missing or idiosyncratic in spam messages); and (3) the last few “Received:” headers (i.e., the earliest ones, since they are normally added at the top of the message), excluding any obvious timestamp data. It may also be useful to hash a combination of the “From:” field and the e-mail address of the recipient (transferred as part of the SMTP mail-transfer protocol, and not necessarily found in the message itself).
If the message text is substantially replicated (e.g., greater than 90%), hash processor 410 may check one or more portions of the e-mail message against known legitimate mailing lists within hash memory 420 (act 522) (FIG. 5C). For example, hash processor 410 may hash the From or Sender fields of the e-mail message and compare it/them to known legitimate mailing lists within hash memory 420. Hash processor 410 may also determine whether the e-mail actually appears to originate from the correct source for the mailing list by examining, for example, the sequence of Received headers. Hash processor 410 may further examine a combination of the From or Sender fields and the recipient address to determine if the recipient has previously received e-mail from the sender. This is typical for mailing lists, but a typical of unwanted e-mail, which will normally not have access to the actual list of recipients for the mailing list. Failure of this examination may simply pass the message on, but mark it as “suspicious,” since the recipient may simply be a new subscriber to the mailing list, or the mailings may be infrequent enough to not persist in the hash counters between mailings.
US20050014749 * Jun 21, 2004 Jan 20, 2005 Amgen Inc. Piperazine derivatives and methods of use
US8996638 Nov 1, 2013 Mar 31, 2015 Kaspersky Lab Zao System and method for spam filtering using shingles
US9223971 * Jan 28, 2014 Dec 29, 2015 Exelis Inc. User reporting and automatic threat processing of suspicious email
US9391936 Feb 17, 2015 Jul 12, 2016 AO Kaspersky Lab System and method for spam filtering using insignificant shingles
US9576131 * Aug 10, 2015 Feb 21, 2017 Juniper Networks, Inc. Malware detection system and method for mobile platforms
US20060095523 * Jun 17, 2005 May 4, 2006 Bruno Decarpigny System and method for sending messages into a communications network by electronic mail, based on the use of a send filter
US20090158429 * Jan 28, 2009 Jun 18, 2009 Marshall Van Alstyne Methods and systems for enabling analysis of communication content while preserving confidentiality
US20150347753 * Aug 10, 2015 Dec 3, 2015 Juniper Networks, Inc. Malware detection system and method for mobile platforms
EP2315407A3 * Sep 24, 2010 Jun 19, 2013 Comcast Cable Communications, LLC Address couplet communication filtering
EP2811699A1 * Nov 26, 2013 Dec 10, 2014 Kaspersky Lab, ZAO System and method for spam filtering using shingles
WO2006048529A1 * Oct 26, 2005 May 11, 2006 Bruno Decarpigny System and method for transmitting messages in an electronic messaging communication network, using a transmission filter
WO2009146536A1 Jun 1, 2009 Dec 10, 2009 Corporation De L'ecole Polytechnique De Montreal File presence detection and monitoring
WO2012007202A1 * May 13, 2011 Jan 19, 2012 F-Secure Corporation Identifying polymorphic malware
Cooperative Classification H04L63/145, H04L51/12, G06F21/562
European Classification H04L63/14D1, G06F21/56B, H04L12/58F
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:MILLIKEN, WALTER CLARK;STRAYER, WILLIAM TIMOTHY;MILLIGAN, STEPHEN DOUGLAS;REEL/FRAME:014474/0767
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:BBN TECHNOLOGIES CORP.;REEL/FRAME:021567/0572
Owner name: AZURE NETWORKS, LLC,TEXAS
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:STRAGENT, LLC;REEL/FRAME:023909/0810