USING SOCIAL GRAPHS TO COMBAT MALICIOUS ATTACKS

• US 20120246720A1
• Filed: 03/24/2011
• Published: 09/27/2012
• Est. Priority Date: 03/24/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xie, Yinglian, Yu, Fang, Abadi, Martin, Gillum, Eliot C., Mao, Zhuoqing Morley, Walter, Jason D., Vitaldevara, Krishna, Huang, Junxian
• Granted Patent: US 8,434,150 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• CPC Class Codes: H04L 51/212 using filtering or selective blocking
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

Detection of user accounts associated with spammer attacks may be performed by constructing a social graph of email users. Biggest connected components (BCC) of the social graph may be used to identify legitimate user accounts, as the majority of the users in the biggest connected components are legitimate users. BCC users may be used to identify more legitimate users. Using degree-based detection techniques and PageRank based detection techniques, the hijacked user accounts and spammer user accounts may be identified. The users'"'"' email sending and receiving behaviors may also be examined, and the subgraph structure may be used to detect stealthy attackers. From the social graph analysis, legitimate user accounts, malicious user accounts, and compromised user accounts can be identified.

Claims

1. A method for classifying a user account, comprising:

constructing a directed graph of user accounts within a provider system, wherein a node of the directed graph is associated with the user account and an edge of the directed graph is determined by a direction of communications sent or received by the user account associated with the node;

constructing an undirected graph of user accounts within a provider system, wherein a node of the undirected graph is associated with the user account and an edge of the undirected graph is determined by one of a social relationship and communication patterns of the user account associated with the node;

determining a biggest connected component of the undirected graph; and

classifying user accounts in the biggest connected component as a set of good users.

2. The method of claim 1, further comprising:

expanding the set of good users using the directed graph to create an expanded good user set; and

developing a good user profile from the set of good users and the expanded good user set.

3. The method of claim 2, further comprising:

selecting users from the set of good users as voucher accounts that are used to vouch for legitimate accounts, or using authorities or entities to vouch for legitimate accounts; and

backtracking vouching of the legitimate accounts if one of the voucher accounts is compromised such that the other legitimate accounts are marked as malicious accounts.

4. The method of claim 2, further comprising:

using the good user profile to detect hijacked user accounts and attacker-created accounts.

5. The method of claim 4, further comprising:

applying a degree-based detection to the node to analyze an in-degree, an out-degree, and a friend-degree, wherein the in-degree represents a number of emails sent to the node, wherein the out-degree represents a number of emails sent by the node, and wherein the friend-degree represents a number of undirected edges associated with the node;

determining a ranking of the node to ascertain a reputation score that is propagated to recipient user accounts and sender user accounts associated with the node; and

determining a reputation score ratio to classify the user account associated with the node as a legitimate user account, a malicious user account, or a legitimate user account that has been compromised.

6. The method of claim 5, further comprising determining the ratio as a badness-goodness ratio, wherein if a predetermined badness-goodness ratio threshold is exceeded, the user account associated with the node is classified as a malicious user account.

7. The method of claim 5, further comprising determining the reputation score for the node as a goodness score and a badness score, wherein the goodness score is based on a number of emails sent to the user account from other legitimate user accounts, and wherein the badness score is determined based on inverse edges in the directed graph.

8. The method of claim 5, wherein the degree-based detection is defined based on a threshold N, and wherein if the out-degree is less than or equal to N, then the user account is a legitimate user account.

9. The method of claim 8, wherein the friend-degree is analyzed based on if the out-degree is less than N for an inactive user, then the user account is considered a legitimate user account, and wherein if the out-degree is greater than N and the friend-degree is greater than a second threshold, K, then the user account is considered a legitimate user account.

10. The method of claim 1, further comprising applying a weight to the edge of the directed and undirected graphs, wherein the weight represents the strength of social relationship between two accounts or represents the degree of communication between two accounts.

11. A system for classifying user accounts, comprising:

a cluster of computing devices, each computing device having a processor;

a memory communicatively coupled to the processor; and

an account management framework that executes in the processor from the memory and that, when executed by the processor, causes the system to register a user account in a registration component, to perform a vouching process that validates the user account in accordance with a social graph associated with the user account at a vouching component, and to classify the user account into either a trusted component or a quarantine component based on whether the user account is a legitimate user account or a malicious user account, respectively.

12. The system of claim 11, wherein the vouching component determines if the user account has received emails from a predetermined number of legitimate user accounts before allowing the user account to send emails.

13. The system of claim 11, wherein the vouching component checks a connectivity among other user accounts that send emails to the user account, and wherein the vouching component checks a reputation of each of the other user accounts to determine if the user account is a legitimate user account.

14. The system of claim 11, wherein a user associated with the user account provides a list of email addresses, and wherein the vouching component determines from the list of email addresses whether the user associated with the user account is a legitimate user.

15. The system of claim 11, wherein the user account is put into the quarantine component to limit functionality of the user account.

16. The system of claim 11, wherein a reputation is determined in accordance with at least one of connectivity of the user account with other user accounts, a clustering coefficient of the user account, or a connectivity with a biggest connected component in the social graph.

17. The system of claim 16, wherein the user account is monitored over time to update the reputation associated with the user account.

18. The system of claim 16, wherein the reputation is based on a goodness score and a badness score.

19. An email system providing malicious user account detection, comprising:

an email server that processes email sent to and from uniquely identified user accounts, the email server maintaining information about processed email and the uniquely identified user accounts in a database; and

a detection server that receives the information about the email from the email server and analyzes the information in accordance with a directed graph and an undirected graph constructed about the uniquely identified user accounts,

wherein each node of the directed graph and the undirected graph is associated with each uniquely identified user account and each edge of the directed graph is determined by a direction of emails sent or received by the uniquely identified user account associated with each node, and

wherein the undirected graph is analyzed to determine biggest connected components of the undirected graph, and a connectivity of each node to the biggest connected components to classify the node.

20. The email system of claim 19, wherein a degree-based detection and ranking detection is applied to each node of the directed graph to determine a reputation score of each node, the reputation score being propagated to other nodes and being used to classify each uniquely identified user account as a legitimate user account, a malicious user account, or a legitimate user account that has been compromised.