Dictionary attack e-mail identification

• US 7,406,503 B1
• Filed: 08/28/2003
• Issued: 07/29/2008
• Est. Priority Date: 08/28/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Eilebrecht, Eric L., Little, Charles Reeves II
• Primary Examiner(s): Caldwell; Andrew
• Assistant Examiner(s): Frink; John M
• Application Number:
  US10/651,316
• Time in Patent Office: 1,797 Days
• Field of Search: 709/206, 709/207
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

User IDs in addresses to which an e-mail is addressed are logically ordered into a 2D matrix of rows each having one user ID. For each column in the 2D matrix, a column count is found by counting the highest number of matching characters in the column. A column quotient is calculated for each column by dividing the column count by the total number of rows in the 2D matrix. A weighted column quotient is calculated for each column by multiplying the column quotient by a weight that is based on the left-to-right order of the column in the 2D matrix. A numerical assessment is made of the similarity of the user IDs in the addresses to which the e-mail is addressed by adding up the weighted column quotients for the columns in the 2D matrix.

Claims

1. A method comprising:

assessing the similarity of addresses to which an e-mail is addressed wherein the assessment comprises assessing the similarity of the user IDs of the addresses wherein the assessment of the similarity of the user IDs is weighted heavier for the leftmost characters of the User IDs than for the rightmost characters of the User IDs, the weight decreasing from left to right for each character of the user IDs wherein differences in weight between the character positions is non-linear; and

deriving a spam value from the assessment.

2. The method as defined in claim 1, further comprising:

analyzing the likelihood that the e-mail is spam; and

determining the e-mail to be spam when the analysis finds that the e-mail is likely to be spam and the spam value exceeds a predetermined threshold.

3. The method as defined in claim 2, wherein the analyzing comprises one or more tests which evaluate the likelihood that the e-mail is spam.

4. A computer readable medium comprising instructions that, when executed by a computer, performs the method of claim 1.

5. A method comprising:

columnizing, in left-to-right order, the characters in the respective user IDs in a plurality of addresses to which an electronic mail (e-mail) is addressed;

for each said column;

counting the highest number of identical characters to arrive at a repeat total for the column;

dividing the repeat total by the number of addresses to which the e-mail is addressed to arrive at a quotient; and

weighting the quotient by a factor according to the relative left-to-right order of the column to arrive at a weighted quotient;

summing the weighted quotients for the columns to arrive at a first spam value.

6. The method as defined in claim 5, wherein the weighted quotient comprises the quotient multiplied by the factor.

7. The method as defined in claim 5, wherein:

the weighted quotient comprises the quotient multiplied by the factor;

the factor comprises W(c); and

W(c) comprises ln((n+(c+1)(e−

1))/(n+c(e−

1)));

wherein;

n comprises the number of characters in the longest user ID of the addresses to which the e-mail is addressed;

c comprises the relative left-to-right number of the column; and

e is the Euler number constant.

8. The method as defined in claim 7, wherein the c is equal to zero for the first column in the left-to-right order.

9. The method as defined in claim 7, wherein n is not more than 72.

10. The method as defined in claim 5, further comprising, prior to the columnizing, obtaining the user ID for each said address by parsing the characters thereof in order from the left-to-right prior to the occurrence of an “

@”

character.

11. The method as defined in claim 5, wherein each said quotient has a value not less than zero and not more than one.

12. The method as defined in claim 5, wherein the addresses are included in either a “

to”

field or a “

cc”

field of the e-mail.

13. The method as defined in claim 5, wherein a count of the number of addresses is not more than fifty.

14. The method as defined in claim 5, wherein the first spam value is a confidence level assessment as to whether the e-mail was sent incident to a spammers dictionary attack.

15. The method as defined in claim 5, further comprising performing the columnizing and the summing prior to sending the e-mail to any said address to which the e-mail is addressed.

16. The method as defined in claim 5, further comprising, prior to the columnizing and the summing, receiving the e-mail at an e-mail service provider address that is used in conjunction with an e-mail service provider that provides e-mail services to one or more of the addresses to which the e-mail is addressed.

17. The method as defined in claim 5, further comprising, when the number of characters in the user ID of any said address is greater than a predetermined number:

skipping the columnizing and the summing; and

sending the e-mail to the addresses to which the e-mail is addressed.

18. The method as defined in claim 5, wherein each said address comprises:

the user ID prior to a leftmost @ character;

an optional machine/sub-machine name after a period character that follows the user ID;

a domain name after a period character that follows either the user ID or the optional machine/sub-machine name;

a top level domain after a period character that follows the domain name; and

an optional sequence of country code characters after a period character that follows the top level domain name.

19. A computer readable medium comprising instructions that, when executed by a computer, perform the method of claim 5.

20. A method comprising, for each of a plurality of untransmitted e-mails, the steps of:

(a) columnizing, in left-to-right order, the characters in the respective user IDs in a plurality of addresses to which the untransmitted e-mail is addressed;

(b) for each said column;

counting the highest number of identical characters to arrive at a repeat total for the column;

dividing the repeat total by the number of addresses to which the untransmitted e-mail is addressed to arrive at a quotient; and

weighting the quotient by a factor according to the relative left-to-right order of the column to arrive at a weighted quotient;

(c) summing the weighted quotients for the columns to arrive at a first spam value;

(d) altering one or more of the user IDs in the addresses to which the untransmitted e-mail is addressed; and

(e) repeating the steps (a) through (d) until the first spam value is outside of a predetermined range of values.

21. The method as defined in claim 20, further comprising generating the plurality of untransmitted e-mails each of which is spam, whereby step (e) can assist in avoiding a detection of a spam dictionary attack.

22. A computer readable medium comprising instructions that, when executed by a computer, perform the method of claim 20.

23. A method comprising:

columnizing, in left-to-right order, the characters in the respective user IDs in a plurality of addresses to which an e-mail is addressed;

for each said column;

counting the highest number of identical characters to arrive at a repeat total for the column;

dividing the repeat total by the number of addresses to which the e-mail is addressed to arrive at a quotient; and

weighting the quotient by a factor according to the relative left-to-right order of the column to arrive at a weighted quotient;

summing the weighted quotients for the columns to arrive at a first confidence level assessment as to whether the e-mail is spam;

performing one or more other confidence level assessments that each assess whether the e-mail is spam;

using each of the first and other confidence level assessments to arrive at a final spam value; and

determining, based upon the final spam value, whether to deliver the e-mail to any said address.

24. The method as defined in claim 23, wherein the one or more other confidence level assessments includes determining that the number of characters in the user ID of any said address is greater than a predetermined number.

25. The method as defined in claim 23 wherein the one or more other confidence level assessments includes identifying a subject field for the e-mail any of a plurality of predetermined key words, characters, or character strings.

26. The method as defined in claim 23, wherein the one or more other confidence level assessments includes a count of the number of addresses exceeding a predetermined maximum.

27. The method as defined in claim 23, further comprising:

weighting each of the first and other confidence level assessments that assess whether the e-mail is spam; and

arriving at a final spam value using the weighted confidence level assessments.

28. The method as defined in claim 27, further comprising preventing, based upon the final spam value and a sent-from address of the e-mail, the delivery of any other e-mail that is received from the sent-from address of the e-mail.

29. The method as defined in claim 27, further comprising determining, based upon the final spam value, whether to deliver the e-mail to each said address.

30. The method as defined in claim 27, further comprising delivering the e-mail to each said address when the final spam value is beneath a predetermined confidence level.

31. A computer readable medium comprising instructions that, when by a computer, perform the method of claim 23.

32. For the user IDs in a plurality of addresses to which an e-mail is addressed, the user IDs being logically ordered into a two dimensional (2D) matrix of rows each having one said user ID, a method comprising:

for each column in the 2D matrix;

finding a column count by counting the highest number of matching characters in the column;

calculating a column quotient by dividing the column count by the total number of rows in the 2D matrix; and

calculating a weighted column quotient by multiplying the column quotient by a weight that is based on the left-to-right order of the column in the 2D matrix;

calculating a numerical assessment of the similarity of the user IDs in the plurality of addresses to which the e-mail is addressed by adding up the weighted column quotients for the columns in the 2D matrix.

33. The method as defined in claim 32, wherein the weight for each respective said column in the 2D matrix comprises ln((n+(c+1)(e−

1))/(n+c(e−

1)));

wherein;

n comprises the number of characters in the longest user ID in the matrix;

c comprises the number of the relative left-to-right order of the column; and

e is the Euler number constant.

34. The method as defined in claim 33, wherein the c is equal to zero for the first column in the left-to-right order.

35. The method as defined in claim 32, wherein the numerical assessment is a confidence level assessment as to whether the e-mail was sent incident to a spammer'"'"'s dictionary attack.

36. The method as defined in claim 32, further comprising performing the finding and each said calculating prior to sending the e-mail to any said address to which the e-mail is addressed.

37. The method as defined in claim 32, further comprising, prior to the finding and each said calculating, receiving the e-mail at an e-mail service provider address that is used in conjunction with an e-mail service provider that provides e-mail services to one or more of the addresses to which the e-mail is addressed.

38. A computer readable medium comprising instructions that, when executed by a computer, perform the method of claim 32.

39. A method comprising, for each of a plurality of untransmitted e-mails, the steps of:

for the user IDs in a plurality of addresses to which the untransmitted e-mail is addressed, the user IDs being logically ordered into a two dimensional (2D) matrix of rows each having one said user ID, for each column in the 2D matrix;

(i) finding a column count by counting the highest number of matching characters in the column;

(ii) calculating a column quotient by dividing the column count by the total number of rows in the 2D matrix;

(iii) calculating a weighted column quotient by multiplying the column quotient by a weight that is based on the left-to-right order of the column in the 2D matrix;

(iv) calculating a numerical assessment of the similarity of the user IDs in the plurality of addresses to which the e-mail is addressed by adding up the weighted column quotients for the columns in the 2D matrix,

(v) altering one or more of the user IDs in the addresses to which the untransmitted e-mail is addressed; and

(vi) repeating the steps (i) through (v) until the numerical assessment is outside of a predetermined range of values.

40. The method as defined in claim 39, further comprising generating the plurality of untransmitted e-mails each of which is spam, whereby step (vi) can assist in avoiding a detection of a spam dictionary attack.

41. A computer readable medium comprising instructions that, when executed by a computer, perform the method of claim 39.

42. For the user IDs in a plurality of addresses to which an e-mail is addressed, the user IDs being logically ordered into a two dimensional (2D) matrix of rows each having one said user ID, a method comprising:

for each column in the 2D matrix;

finding a column count by counting the highest number of matching characters in the column;

calculating a column quotient by dividing the column count by the total number of rows in the 2D matrix; and

calculating a weighted column quotient by multiplying the column quotient by a weight that is based on the left-to-right order of the column in the 2D matrix;

calculating a first confidence level assessment as to whether the e-mail is spam by adding up the weighted column quotients for the columns in the 2D matrix;

performing one or more other confidence level assessments that each assess whether the e-mail is spam;

using each of the first and other confidence level assessments to arrive at a final spam assessment; and

determining, based upon the final spam assessment, whether to deliver the e-mail to any said address.

43. The method as defined in claim 42, further comprising assessing, based upon the final spam assessment and a sent-from address of the e-mail, whether to prevent the delivery of any other e-mail that is received from the sent-from address of the e-mail.

44. The method as defined in claim 42, wherein the one or more other confidence level assessments are selected from the group consisting of:

determining that the number of characters in the user ID of any said address is greater than a predetermined number;

identifying in a subject field for the e-mail any of a plurality of predetermined key words, characters, or character strings; and

a count of the number of addresses exceeding a predetermined maximum.

45. The method as defined in claim 42, further comprising including a weighting factor in any of the first and other confidence level assessments, wherein each said weighting factor represents the relative significance of the respective confidence level assessment in which the weighting factor is included.

46. A computer readable medium comprising instructions that, when executed by a computer, perform the method of claim 42.

47. A method comprising the steps, for each of a plurality of untransmitted e-mails:

(a) performing the method of claim 46 upon the untransmitted e-mail to thereby calculate the first confidence level assessment thereof; and

(b) altering one or more of the user IDs in the addresses to which the untransmitted e-mail is addressed; and

(c) repeating steps (a) and (b) until the first confidence level assessment is outside of a predetermined range of values.

48. The method as defined in claim 47, further comprising generating the plurality of untransmitted e-mails each of which is spam, whereby step (c) can assist in avoiding a detection of a spam dictionary attack.

49. A computer readable medium comprising instructions that, when executed by a computer, perform the method of claim 47.

50. A method comprising:

for the respective user IDs in a plurality of addresses to which an e-mail is addressed, where the characters of the respective user IDs are logically and collectively columnized, deriving a numerical expression of the degree of repetition of the most common character for each column; and

weighting the numerical expression for each column by a respective weight for each column to obtain respective weighted column values, wherein the respective weight for each column is selected such that the sum of the weighted column values is equal to a confidence level of about 100 percent (100%) when the user IDs in the plurality of addresses are identical.

51. The method as defined in claim 50, further comprising:

altering one or more of the user IDs in the addresses to which the e-mail is addressed; and

repeating the deriving, weighting and altering until the confidence level is below a predetermined percentage.

52. The method as defined in claim 51, wherein the e-mail is untransmitted, and the method further comprises:

generating a plurality of the untransmitted e-mails; and

performing the repeating for each said untransmitted e-mail.

53. The method as defined in claim 52, further comprising transmitting each of the untransmitted e-mails to the respective addresses therein.

54. A computer readable medium comprising instructions that, when executed by a computer, performs the method of claim 50.

55. A method comprising:

generating logically columnized user IDs;

deriving a numerical expression of the degree of repetition of the most common character for each column;

weighting the numerical expression for each column by a respective weight for each column to obtain respective weighted column values, wherein the respective weight for each column is selected such that the sum of the weighted column values is equal to a confidence level of about 100 percent (100%) when the user IDs are identical;

if the confidence level is above a predetermined percentage, repeating the deriving and weighting using an alteration of the user IDs until the confidence level is below the predetermined percentage;

dividing the user IDs into respective groups; and

for each group, forming an e-mail and a respective e-mail address for each user ID in the group.

56. The method as defined in claim 55, further comprising transmitting the e-mails to the respective addresses therein.

57. The method as defined in claim 55, wherein the user IDs are generated incident to a dictionary spam attack.

58. A computer readable medium comprising instructions that, when executed by a computer, performs the method of claim 55.