DETECTING DATA PROPAGATION IN A DISTRIBUTED SYSTEM

• US 20080320075A1
• Filed: 06/22/2007
• Published: 12/25/2008
• Est. Priority Date: 06/22/2007
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Livshits, Benjamin, Cui, Weidong
• Granted Patent: US 7,933,946 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 63/166 at the transport layer

Abstract

Embodiments gather historical information about data propagation by monitoring requests to and replies from a server. When a request is received from a client system to upload code onto a web site, a user identity associated with the client system is determined and a tag that uniquely identifies the uploaded data is created and mapped with the user identity into a propagation graph. The propagation graph includes nodes and edges associated with a number of client systems that made similar requests such that each node of the propagation graph corresponds to both a tag and user identity of a client system and edges within the propagation graph represent causality links between the nodes. The propagation graph can then be used for finding long propagation chains, which can be useful for detecting worm-like propagation activity.

Claims

1. In a distributed computing system, a method of using historical information about data propagation by monitoring requests to and replies from a server, the method comprising:

receiving a request from one of a plurality of client systems;

identifying that the request is used to upload data onto a web site;

determining an identity associated with the one of the plurality of client systems;

creating an tag that uniquely identifies the uploaded data;

mapping the tag and the identity into a propagation graph, which includes nodes and edges associated with a plurality of client systems that made a request to upload data to the web site such that each node of the propagation graph corresponds to both a tag and identity of a client system and edges within the propagation graph represent causality links between the nodes; and

using the propagation graph for determining at least an approximation of how many requests for uploading data to the web site have been made, where one or more of the requests originated, or both.

2. The method of claim 1, further comprising:

sending the uploaded data with the tag to a server for storage;

receiving a request from another of the plurality of client systems to download at least a portion of the uploaded data stored on the server;

identifying that the downloaded data includes the tag that uniquely identifies a node within the propagation graph;

sending the downloaded data to the another client;

subsequently receiving a new request to upload other data onto associated with the same web site where the data was previously downloaded with the tag;

determining a different identity associated with the another of the plurality of client systems;

creating a different tag that uniquely identifies the uploaded other data;

mapping the different tag and the different identity to the propagation graph such that the tag and different tag are linked together;

using the propagation graph for determining at least an approximation of how many requests for uploading data to the web site have been made, where one or more of the requests originated, or both; and

based on the determination, denying or sending the uploaded data with the different tag to the server for storage and subsequent retrieval from one or more of the plurality of client systems.

3. The method of claim 2, wherein the sending of the downloaded data to the another client comprises:

assigning a session identifier to the downloaded data such that subsequent requests associated with the web site include the session identifier to correlate such requests with the web site and the propagation graph;

extracting the tag from the downloaded data; and

sending the session identifier and the downloaded data to the another client system.

4. The method of claim 1, wherein the identifying that the request is used to upload data onto the web site comprises:

determining that the uploaded data includes HTML code, wherein the tag is included within one of the HTML elements within a parameter.

5. The method of claim 1, wherein the method is deployed at one of the server side, the client side, or a proxy between the server side and the client side.

6. The method of claim 1, wherein each node in the propagation graph can store multiple identities, and wherein each node has a depth value, which is an approximation of the number of unique identities on the path from that node to the root.

7. The method of claim 6, wherein the mapping the tag and the identity into the propagation graph comprises:

identifying if a parent node is an only predecessor of a child node to be added with the tag and identity, wherein if true the method further comprises;

determining an identity size of one or more storage station nodes that include identity values up to a predefined threshold in the path from the parent node to the root node;

assigning a depth value for child as a sum of determined identity sizes found in the one or more storage stations nodes;

copying all identities in the parent node to the child node; and

adding child node'"'"'s identity if it is unique, wherein if so the method further comprises;

incrementing the depth value of the child node by one, wherein if size of identities in the child node equals the predefined threshold, the method further comprises;

designating the child node as a storage station node.

8. The method of claim 7, wherein if the child node has two predecessors in the propagation graph, the method comprises:

comparing depth values stored at each of the multiple predecessors;

selecting a node from the two predecessors with a smaller depth value for the two predecessors and assigning the node as a parent node to the child;

removing the edge between the child and the predecessor node with a larger depth value;

determining an identity size of one or more storage station nodes that include identity values up to the predefined threshold in the path from the parent node to the root node;

assigning a depth value for child as a sum of determined identity sizes found in the one or more storage stations nodes;

copying all identities in the parent node to the child node; and

adding child node'"'"'s identity if it is unique, wherein if so the method further comprises;

incrementing the depth value of the child node by one, wherein if size of identities in the child node equals the predefined threshold, the method further comprises;

designating the child node as a storage station node.

9. The method of claim 8, wherein if the added child node'"'"'s depth value exceeds some threshold, the method further comprises:

marking a tree of the propagation graph associated with the child node and the parent node as infected by a worm; and

propagating the infected status to each node in the tree, such that all subsequent uploads that are caused by nodes within that tree are denied unless an indication is received that the infection has been resolved.

10. In a distributed computing system, a computer program product for implementing a method of using historical information about data propagation by monitoring requests to and replies from a server, the computer program product comprising one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by one or more processors of a computing system, cause the computing system to perform the following:

receive a request from one of a plurality of client systems;

identify that the request is used to upload data onto a web site;

determine a identity associated with the one of the plurality of client systems;

create an tag that uniquely identifies the uploaded data;

map the tag and the identity into a propagation graph, which includes nodes and edges associated with a plurality of client systems that made a request to upload data to the web site such that each node of the propagation graph corresponds to both a tag and identity of a client system and edges within the propagation graph represent causality links between the nodes; and

use the propagation graph for determining at least an approximation of how many requests for uploading data to the web site have been made, where one or more of the requests originated, or both.

11. The computer program product of claim 10, further comprising:

sending the uploaded data with the tag to a server for storage;

receiving a request from another of the plurality of client systems to download the at least a portion of the uploaded data stored on the server;

identifying that the downloaded data includes the tag that uniquely identifies a node within the propagation graph;

sending the downloaded data to the another client;

subsequently receiving a new request to upload other data onto associated with the same web site where the data was previously downloaded with the tag;

determining a different identity associated with the another of the plurality of client systems;

creating a different tag that uniquely identifies the uploaded other data;

mapping the different tag and the different identity to the propagation graph such that the tag and different tag are linked together;

using the propagation graph for determining at least an approximation of how many requests for uploading data to the web site have been made, where one or more of the requests originated, or both; and

based on the determination, denying or sending the uploaded data with the different tag to the server for storage and subsequent retrieval from one or more of the plurality of client systems.

12. The computer program product of claim 11, wherein the sending of the downloaded data to the another client comprises:

assigning a session identifier to the downloaded data such that subsequent requests associated with the web site include the session identifier to correlate such requests with the web site and the propagation graph;

extracting the tag from the downloaded data; and

sending the session identifier and the downloaded data to the another client system.

13. The computer program product of claim 12, wherein the another client system includes a browser plug-in in order to provide propagation of the tags and session identifier at a data transfer protocol layer so that applications cannot modify the tags or session identifiers.

14. The computer program product of claim 10, wherein the identity is an IP address for the client that requested to upload the data.

15. The computer program product of claim 10, wherein each node in the graph represents a unique identity for each of the plurality of client systems.

16. The computer program product of claim 10, wherein the propagation graph is used to dynamically check for cross-site scripting vulnerabilities such that if a length from a root node to another node of the propagation graph grows beyond a predetermined threshold, further upload requests will be denied.

17. The computer program product of claim 10, wherein the identifying that the request is used to upload data onto the web site comprises:

determined that the uploaded data includes HTML code, wherein the tag is included within one of the HTML elements within a parameter.

18. The computer program product of claim 17, wherein the tag is included in a first HTML element within the parameter.

19. The computer program product of claim 10, wherein the method is deployed at one of the server side, the client side, or a proxy between the server side and the client side.

20. The computer program product of claim 10, wherein each node in the propagation graph can store multiple identities, and wherein each node has a depth value, which is an approximation of the number of unique identities on the path from that node to the root, and wherein the mapping the tag and the identity into the propagation graph comprises:

identifying if a parent node is an only predecessor of a child node to be added with the tag and identity, wherein if true the method further comprises;

determining a identity size of one or more storage station nodes that include identity values up to a predefined threshold in the path from the parent node to the root node;

assigning a depth value for child as a sum of determined identity sizes found in the one or more storage stations nodes;

copying all identities in the parent node to the child node; and

adding child node'"'"'s identity if it is unique, wherein if so the method further comprises;

incrementing the depth value of the child node by one, wherein if size of identities in the child node equals the predefined threshold, the method further comprises;

designating the child node as a storage station node, and

wherein if the child node has more than one predecessors in the propagation graph, the method comprises;

comparing depth values stored at each of the two predecessors;

selecting a node from the two predecessors with a smaller depth value for the two predecessors and assigning the node as a parent node to the child;

removing the edges between the child and the predecessors with a depth value larger than the minimum;

determining a identity size of one or more storage station nodes that include identity values up to the predefined threshold in the path from the parent node to the root node;

assigning a depth value for child as a sum of determined identity sizes found in the one or more storage stations nodes;

copying all identities in the parent node to the child node; and

adding child node'"'"'s identity if it is unique, wherein if so the method further comprises;

incrementing the depth value of the child node by one, wherein if size of identities in the child node equals the predefined threshold, the method further comprises;

designating the child node as a storage station node; and

wherein if the added child node'"'"'s depth value exceeds some threshold, the method further comprises;

marking a tree of the propagation graph associated with the child node and the parent node as infected by a worm; and

propagating the infected status to each node in the tree, such that all subsequent uploads that are caused by nodes within that tree are denied unless an indication is received that the infection has been resolved.