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

• US 8,239,687 B2
• Filed: 11/12/2004
• Issued: 08/07/2012
• 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.
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): TRUVAN, LEYNNA THANH
• Application Number:
  US10/986,467
• Publication Number:
  US 20050265331A1
• Time in Patent Office: 2,825 Days
• Field of Search: 726 2- 7, 726/13, 726/19, 726 22- 26, 707 1- 3, 707 6- 7, 707100-102, 713/185, 713187-188, 713193-194, 711/100, 711/171, 711/200, 711/205, 711/209, 711212-214, 709223-225, 709227-228, 380/230, 380/233, 380/250
• US Class Current: 713/188
• 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:

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

generating and storing a plurality of statistical distributions, wherein each of the plurality of statistical distributions is a byte frequency distribution of data contained in the data payload in the connection record for each transmission received from another computer system through the computer network;

selecting a model byte value statistical distribution from a plurality of model byte frequency statistical distributions based on the length of the data contained in the data payload, wherein the model byte frequency statistical distribution is representative of normal payloads transmitted through the computer network;

identifying the suspect data payload at the end target computer system based at least in part on differences detected between the statistical distribution associated with the suspect data payload and the selected model byte value statistical distribution and generating a suspect byte frequency distribution of data contained in the suspect data payload;

setting the end target computer system as the suspect computer system;

comparing the suspect byte frequency distribution of the data contained in the suspect data payload to the plurality of statistical distributions associated with the connection records;

upon finding at least one of the plurality of statistical distributions that is similar to the suspect byte frequency distribution of the data contained in the suspect data payload, determining the previous computer system address associated with the at least one of the plurality of statistical distributions;

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

repeating the comparing, the determining, and the setting 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 comparing further comprises:

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:

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 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;

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

generate and store a plurality of statistical distributions, wherein each of the plurality of statistical distributions is a byte frequency distribution of data contained in the data payload in the connection record for each transmission received from another computer system through the computer network;

select a model byte value statistical distribution from a plurality of model byte frequency statistical distributions based on the length of the data contained in the data payload, wherein the model byte frequency statistical distribution is representative of normal payloads transmitted through the computer network;

identify the suspect data payload at the end target computer system based at least in part on differences detected between the statistical distribution associated with the suspect data payload and the selected model byte value statistical distribution and generate a suspect byte frequency distribution of data contained in the suspect data payload;

set the end target computer system as the suspect computer system;

compare the suspect byte frequency distribution of the data contained in the suspect data payload to the plurality of statistical distributions associated with the connection records

upon finding at least one of the plurality of statistical distributions that is similar to the suspect byte frequency distribution of the data contained in the suspect data payload, determine the previous computer system address associated with the at least one of the plurality of statistical distributions;

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

repeat the comparison, the determination, and the setting 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;

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

means for generating and storing a plurality of statistical distributions, wherein each of the plurality of statistical distributions is a byte frequency distribution of data contained in the data payload in the connection record for each transmission received from another computer system through the computer network;

means for selecting a model byte value statistical distribution from a plurality of model byte frequency statistical distributions based on the length of the data contained in the data payload, wherein the model byte frequency statistical distribution is representative of normal payloads transmitted through the computer network;

means for identifying the suspect data payload at the end target computer system based at least in part on differences detected between the statistical distribution associated with the suspect data payload and the selected model byte value statistical distribution and generating a suspect byte frequency distribution of data contained in the suspect data payload;

means for setting the end target computer system as the suspect computer system;

means for comparing the suspect byte frequency distribution of the data contained in the suspect data payload to the plurality of statistical distributions associated with the connection records;

upon finding at least one of the plurality of statistical distributions that is similar to the suspect byte frequency distribution of the data contained in the suspect data payload, means for determining the previous computer system address associated with the at least one of the plurality of statistical distributions;

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

means for repeating the comparison, the determination, and the setting until the origin computer system is determined.

17. A non-transitory 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:

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;

generating and storing a plurality of statistical distributions, wherein each of the plurality of statistical distributions is a byte frequency distribution of data contained in data payload in the connection record for each transmission received from another computer system through the computer network;

selecting a model byte value statistical distribution from a plurality of model byte frequency statistical distributions based on the length of the data contained in the data payload wherein the model byte frequency statistical distribution is representative of normal payloads transmitted through the computer network;

identifying the suspect data payload at the end target computer system based at least in part of differences detected between the statistical distribution associated with the suspect data payload and the selected model byte value statistical distribution and generating a suspect byte frequency distribution of data contained in the suspect data payload

setting the end target computer system as the suspect computer system;

comparing the suspect byte frequency distribution of the data contained in the suspect data payload to the plurality of statistical distributions associated with the connection records;

upon finding at least one of the plurality of statistical distribution that is similar to the suspect byte frequency distribution of the data contained in the suspect data payload, determining the previous computer system address associated with the of the plurality of statistical distribution;

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

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