GRAPH BASED BOT-USER DETECTION

• US 20100095374A1
• Filed: 10/10/2008
• Published: 04/15/2010
• Est. Priority Date: 10/10/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gillum, Eliot C., Zhao, Yao, Ke, Qifa, Yu, Fang, Xie, Yinglian
• Granted Patent: US 8,069,210 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 2463/144 Detection or countermeasures against botnets
• CPC Class Codes: H04L 51/212 using filtering or selective blocking
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Computer implemented methods are disclosed for detecting bot-user groups that send spam email over a web-based email service. Embodiments of the present system employ a two-prong approach to detecting bot-user groups. The first prong employs a historical-based approach for detecting anomalous changes in user account information, such as aggressive bot-user signups. The second prong of the present system entails constructing a large user-user relationship graph, which identifies bot-user sub-graphs through finding tightly connected subgraph components.

Claims

1. A computer implemented method for detecting bot-user accounts on a web-based email system, comprising the steps of:

a) determining a group of seed accounts that are potentially bot-user accounts;

b) examining a degree to which the seed and other candidate accounts share the same computers for sending emails; and

c) identifying bot-user accounts on the web-based emails system based on the results of said steps a) and b).

2. The computer-implemented method of claim 1, wherein said step a) of examining historical user account data to detect an anomaly in the changes in the user account data comprises the step of examining the number of user account signups within the predefined period of time.

3. The computer-implemented method of claim 1, wherein said step b) of examining a degree to which user accounts share the same computers for sending emails comprises the step of examining a degree to which user accounts share the same IP addresses when sending emails.

4. The computer-implemented method of claim 1, wherein said step b) of examining a degree to which user accounts share the same computers for sending emails comprises the step of constructing a graph wherein the vertices are user accounts and two vertices are connected by an edge if the corresponding two user accounts share at least one IP address within a predefined period of time.

5. The computer-implemented method of claim 4, wherein two or more user accounts sharing a threshold number of computers within a predefined period of time is indicative of a bot-user group.

6. The computer-implemented method of claim 4, further comprising the step of assigning a weight to an edge between any pairs of vertices, the weight of an edge between a pair of vertices representing one or more of the following:

i) the number of computers shared between the corresponding two user accounts, and ii) shared characteristics including at least one of login time, signup date and sending patterns.

7. The computer-implemented method of claim 6, wherein a disproportionate drop off in the amount of connected vertices from one weight to the next successive weight indicates one or more bot-user groups at the lower weight.

8. The computer-implemented method of claim 7, further comprising examining the one or more bot-user groups identified at the lower weight to determine how many bot-user groups are in the one or more identified bot-user groups.

9. The computer-implemented method of claim 1, further comprising the step of pruning the results obtained in said step c) to remove accounts that were falsely indicated to be bot-user accounts.

10. The computer-implemented method of claim 9, wherein the step of pruning the results comprises at least one of the following:

i) examining the size of emails sent from different user accounts in a suspicious group of user accounts, with email sizes more uniformly distributed indicating that the accounts in the group are less likely to be bot-user accounts, ii) examining the number of emails per day sent from different user accounts in a suspicious group of user accounts, with the number of emails less uniformly distributed indicating that the accounts in the group are less likely to be bot-user accounts, and iii) examining the login times of different user accounts in a suspicious group of user accounts, with the login times less uniformly distributed indicating that the accounts in the group are less likely to be bot-user accounts, and iv) examining the signup date of different user accounts in a suspicious group of user, with signup dates less uniformly distributed indicating that the accounts in the group are less likely to be bot-user accounts.

11. The computer-implemented method of claim 1, further comprising the step of examining similarities between user accounts to determine an existence of bot-user accounts by examining at least one of:

a) similar account signup times between two or more user accounts;

b) sharing account signup IP addresses between two or more user accounts;

c) similar signup information, including at least one of the same country code, same zip code, similar user name patterns, and similar signup interfaces between two or more user accounts;

d) login behavior, including whether a user account sends emails each time the user logs in;

e) similar email sending mail behavior, including a similarity of emails sent, email sizes, whether having attachments, the inter email sending time between two or more user accounts, the non-delivery reports received from those sent messages, the alphabetic and volume distribution of recipients; and

f) account information, including at least one of the similarity of the folders in two or more email accounts, the contents of inbox in two or more email accounts, the contents of the sent messages box in two or more email accounts, and the contact list in two or more email accounts.

12. A computer implemented method for detecting bot-user accounts on a web-based email system, comprising the steps of:

a) constructing a graph wherein the vertices are user accounts and a pair of vertices are connected by an edge if the corresponding two user accounts share a common account characteristic within a predefined period of time; and

b) identifying one or more bot-user groups from a group of user accounts sharing a threshold number of IP addresses within a predefined period of time.

13. The computer-implemented method of claim 12, wherein said step a) of constructing a graph wherein vertices are connected by an edge if the corresponding two user accounts share a common account characteristic comprises the step of vertices being connected by an edge if the corresponding two user accounts share one or more of the same IP addresses within a predefined period of time.

14. The computer-implemented method of claim 13, further comprising the step of assigning a weight to an edge between any pairs of vertices, the weight of an edge between a pair of vertices representing the number of different ASes where two corresponding user accounts share IP addresses.

15. The computer-implemented method of claim 14, wherein a disproportionate drop off in the amount of connected vertices from one weight to the next successive weight indicates one or more bot-user groups at the lower weight.

16. The computer-implemented method of claim 15, further comprising examining the one or more bot-user groups identified at the lower weight to determine how many bot-user groups are in the one or more identified bot-user groups.

17. The computer-implemented method of claim 12, further comprising the step of pruning the results by examining the size of emails and the number of emails per day sent from different user accounts in a candidate group of user accounts, with email sizes more uniformly distributed indicating that the accounts in the group are less likely to be bot-user accounts.

18. The computer-implemented method of claim 12, wherein the common account characteristic shared by the two user accounts include at least one of:

a) similar account signup times between the two user accounts;

b) sharing account signup IP addresses between the two user accounts;

c) similar signup information, including at least one of the same country code, same zip code, similar user name patterns, and similar signup interfaces between the two user accounts;

d) login behavior, including whether a user account sends emails each time the user logs in;

e) similar email sending mail behavior, including a similarity of number of emails sent, email sizes, whether having attachments, the inter email sending time between the two user accounts, a number of non-delivery reports received from those sent messages, the alphabetic and volume distribution of recipients; and

f) account information, including at least one of the similarity of the folders in the two email accounts, the contents of inbox in the two email accounts, a contents of the sent messages box in the two email accounts, and the content of contact list in the two email accounts.

19. A computer implemented method for detecting bot-user accounts on a web-based email system, comprising the steps of:

a) constructing a graph wherein the vertices are user accounts and a pair of vertices are connected by an edge if the corresponding two user accounts share one or more of the same IP addresses within a predefined period of time;

b) assigning a weight to an edge between any pairs of vertices, the weight of an edge between a pair of vertices representing the number of IP addresses shared between the corresponding two user accounts; and

c) examining the number of user accounts connected by vertices at successive weights, wherein a disproportionate drop off in the amount of connected vertices from one weight to the next successive weight indicates one or more bot-user groups at the lower weight.

20. The computer implemented method of claim 19, further comprising the step of examining historical user account data to detect an anomaly in the changes in the volume of account signup data within a predefined period of time.