Apparatus method and medium for tracing the origin of network transmissions using n-gram distribution of data

• US 20050265331A1
• Filed: 11/12/2004
• Published: 12/01/2005
• Est. Priority Date: 11/12/2003
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Stolfo, Salvatore J.
• Granted Patent: US 8,239,687 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06F 21/562 Static detection
• CPC Class Codes: G06F 21/563 by source code analysis
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 63/0218 Distributed architectures, e.g. distributed firewalls
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/029 Firewall traversal, e.g. tunnelling or, creating pinholes
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

A method, apparatus, and medium are provided for tracing the origin of network transmissions. Connection records are maintained at computer system for storing source and destination addresses. The connection records also maintain a statistical distribution of data corresponding to the data payload being transmitted. The statistical distribution can be compared to that of the connection records in order to identify the sender. The location of the sender can subsequently be determined from the source address stored in the connection record. The process can be repeated multiple times until the location of the original sender has been traced.

Claims

1. A method of tracing the location of an origin computer system that initially transmits a suspect data payload across a computer network to an end target computer system, the computer network having a plurality of computer systems, where each of the computer systems maintains connection records of transmitted data it receives, the transmitted data and connection records including a previous computer system address, a data payload, and a next computer system address, the method comprising the steps of:

(1) creating, at each of the computer systems, a connection record for each transmission received from another computer system through the computer network;

(2) generating and storing a statistical distribution for the data payload in each connection record;

(3) identifying the suspect data payload at the end target computer system and generating a statistical distribution of said suspect data payload;

(4) setting the end target computer system as the suspect computer system;

(5) comparing the suspect data payload statistical distribution to the data payload statistical distributions associated with connection records of the suspect computer system;

(6) upon finding a data payload statistical distribution that is similar to the suspect data payload statistical distribution in said step (5), determining the previous computer system address associated with the similar data payload statistical distribution;

(7) setting the computer system associated with the previous computer system address as the suspect computer system; and

(8) repeating said steps (5)-(7) until the origin computer system is determined.

2. The method of claim 1, wherein the data payload statistical distributions are byte value distributions, and the suspect data payload statistical distribution is a byte value distribution.

3. The method of claim 2, wherein the byte value distribution of each data payload is a byte frequency count, and each suspect data payload statistical distribution is a byte frequency count.

4. The method of claim 2, wherein the byte value distribution of each data payload is a rank ordered byte frequency count, and each suspect data payload statistical distribution is a rank ordered byte frequency count.

5. The method of claim 1, wherein the step of comparing further comprises the steps of:

measuring a distance metric between each data payload statistical distribution and the suspect data payload statistical distribution; and

identifying a data payload statistical distribution that is similar to the suspect data payload statistical distribution based, at least in part, on a predetermined distance to the suspect data payload.

6. The method of claim 5, wherein the distance metric is calculated based on a Mahalanobis distance between each data payload statistical distribution and the suspect data payload statistical distribution.

7. The method of claim 1, wherein the data payload statistical distributions, and the suspect data payload statistical distribution are generated using an n-gram distribution, wherein each n-gram is a variable byte grouping.

8. The method of claim 7, wherein n is a mixed value of byte groupings.

9. The method of claim 7, wherein n=1.

10. The method of claim 7, wherein n=2.

11. The method of claim 7, wherein n=3.

12. The method of claim 1, further comprising the steps of:

comparing at least a portion of said suspect data payload statistical distribution to a corresponding portion of a selected model distribution representative of normal data payloads received at said end target computer system; and

determining whether said suspect data payload is a virus or worm based, at least in part on differences detected between the at least one portion of said suspect data payload statistical distribution and the corresponding portion of said selected model distribution.

13. The method of claim 12, further comprising a step of assigning different weight factors to selected byte values of said suspect data payload statistical distribution.

14. The method of claim 12, wherein higher weight factors are assigned to byte values corresponding to operational codes of a computer system.

15. A system for tracing the location of an origin computer system that initially transmits a suspect data payload across a computer network to an end target computer system, comprising:

at least one computer system connected to said computer network for providing network service to one or more users, each said at least one computer systems maintaining connection records of transmitted data it receives, whereby the connection records include a previous computer system address, a data payload, and a next computer system address;

said at least one computer system being configured to;

(1) create a connection record for each transmission received from another computer system through said computer network;

(2) generate and store a statistical distribution for the data payload in each connection record;

(3) identify the suspect data payload at the end target computer system and generate a statistical distribution of said suspect data payload;

(4) set the end target computer system as the suspect computer system;

(5) compare the suspect data payload statistical distribution to the data payload statistical distributions associated with connection records of the suspect computer system;

(6) upon finding a data payload statistical distribution that is similar to the suspect data payload statistical distribution in said step (5), determine the previous computer system address associated with the similar data payload statistical distribution;

(7) set the computer system associated with the previous computer system address as the suspect computer system; and

(8) repeat said steps (5)-(7) until the origin computer system is determined.

16. A system for tracing the location of an origin computer system that initially transmits a suspect data payload across a computer network to an end target computer system, comprising:

at least one computer system connected to said computer network for providing network service to one or more users, each said at least one computer systems maintaining connection records of transmitted data it receives, whereby the connection records include a previous computer system address, a data payload, and a next computer system address;

(1) means for creating, at each of the computer systems, a connection record for each transmission received from another computer system through the computer network;

(2) means for generating and storing a statistical distribution for the data payload in each connection record;

(3) means for identifying the suspect data payload at the end target computer system and generating a statistical distribution of said suspect data payload;

(4) means for setting the end target computer system as the suspect computer system;

(5) means for comparing the suspect data payload statistical distribution to the data payload statistical distributions associated with connection records of the suspect computer system;

(6) means for determining the previous computer system address associated with the similar data payload statistical distribution, upon finding a data payload statistical distribution that is similar to the suspect data payload statistical distribution in said step (5);

(7) means for setting the computer system associated with the previous computer system address as the suspect computer system; and

(8) means for repeating said steps (5)-(7) until the origin computer system is determined.

17. A computer readable medium carrying instructions executable by a computer for tracing the location of an origin computer system that initially transmits a suspect data payload across a computer network to an end target computer system, said instructions causing said computer to perform the acts of:

(1) creating, at each of a plurality of computer systems within said computer network, a connection record for each transmission received from another computer system through the computer network, wherein each connection records including a previous computer system address, a data payload, and a next computer system address;

(2) generating and storing a statistical distribution for the data payload in each connection record;

(3) identifying the suspect data payload at the end target computer system and generating a statistical distribution of said suspect data payload;

(4) setting the end target computer system as the suspect computer system;

(5) comparing the suspect data payload statistical distribution to the data payload statistical distributions associated with connection records of the suspect computer system;

(6) upon finding a data payload statistical distribution that is similar to the suspect data payload statistical distribution in said step (5), determining the previous computer system address associated with the similar data payload statistical distribution;

(7) setting the computer system associated with the previous computer system address as the suspect computer system; and

(8) repeating said steps (5)-(7) until the origin computer system is determined.