Intrusion detection using MDL clustering

• US 9,106,689 B2
• Filed: 05/06/2011
• Issued: 08/11/2015
• Est. Priority Date: 05/06/2011
• Status: Active Grant

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Steinbrecher, Eric, Impson, Jeremy, Barnett, Bruce, Evans, Scott Charles, Scholz, Bernhard, Yan, Weizhong, Markham, Thomas, Dill, Stephen J.
• Primary Examiner(s): Hirl, Joseph P
• Assistant Examiner(s): GYORFI, THOMAS A
• Application Number:
  US13/102,899
• Publication Number:
  US 20120284793A1
• Time in Patent Office: 1,558 Days
• Field of Search: 726/23
• US Class Current: 1/1
• 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: H04L 63/14 for detecting or protecting against malicious traffic
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

An intrusion detection method, system and computer-readable media are disclosed. The system can include a processor programmed to perform computer network intrusion detection. The intrusion detection can include an identification module and a detection module. The identification module can be adapted to perform semi-supervised machine learning to identify key components of a network attack and develop MDL models representing those attack components. The detection module can cluster the MDL models and use the clustered MDL models to classify network activity and detect polymorphic or zero-day attacks.

Claims

1. A network intrusion detection system comprising:

a processor coupled to a nontransitory computer readable medium bearing software instructions that, when executed by the processor, cause the processor to perform operations including;

clustering raw network traffic files into a plurality of natural clusters based on minimum description length (MDL) similarity;

building an MDL model for each natural cluster;

calculating distances from each traffic file to each MDL model to obtain a distance vector for each traffic file, each distance vector having a distance from a corresponding traffic file to each MDL model;

clustering labeled network traffic data into a plurality of trained clusters;

selecting features of the plurality of natural clusters and the plurality of trained clusters for use in classification of network traffic;

building a decision model based on the distance vectors and the selected features of the plurality of natural clusters and the plurality of trained clusters;

analyzing network traffic using the decision model;

generating an output based on the analyzing, the output indicating potential matches between network traffic and an MDL model corresponding to malicious activity; and

displaying on a display, a visualization plot based on the output, the plot showing a graphical representation of network traffic distance from the plurality of natural clusters.

2. The system of claim 1, wherein the network traffic files include data corresponding to normal network behaviors.

3. The system of claim 1, wherein the network traffic files include data corresponding to both normal and malicious network behaviors.

4. The system of claim 1, wherein building the MDL model for each cluster includes concatenating all files in the cluster into a single string.

5. The system of claim 1, wherein the decision model is a minimum-distance classifier.

6. The system of claim 1, wherein the decision model is a support vector machine.

7. The system of claim 1, wherein the clustering raw network traffic files includes:

generating a pair-wise similarity matrix using MDL models to calculate a distance value between pairs of traffic files;

applying hierarchical clustering to the similarity matrix to generate a set of clusters;

refining the set of clusters; and

pruning the set of clusters.

8. The system of claim 7, wherein the clustering raw network traffic files includes iteratively performing the applying, refining and pruning steps.

9. A computerized method for computer network intrusion detection, the method comprising:

clustering, with a processor programmed to perform network intrusion detection, raw network traffic files into a plurality of natural clusters based on minimum description length (MDL) similarity;

building, with the processor, an MDL model for each natural cluster;

calculating, with the processor, distances from each traffic file to each MDL model to obtain a distance vector for each traffic file, each distance vector having a distance from a corresponding traffic file to each MDL model;

clustering labeled network traffic data into a plurality of trained clusters;

selecting features of the plurality of natural clusters and the plurality of trained clusters for use in classification of network traffic; and

building, with the processor, a decision model based on the distance vectors and the selected features of the plurality of natural clusters and the plurality of trained clusters.

10. The method of claim 9, further comprising:

analyzing, with the processor, network traffic using the decision model; and

generating, with the processor, an output based on the analyzing, the output indicating potential matches between network traffic and an MDL model corresponding to malicious activity.

11. The method of claim 9, wherein the clustering raw network traffic files includes:

generating a pair-wise similarity matrix using MDL models to calculate a distance value between pairs of traffic files;

applying hierarchical clustering to the similarity matrix to generate a set of clusters;

refining the set of clusters; and

pruning the set of clusters.

12. The method of claim 9, wherein the network traffic files include data corresponding to normal network behaviors.

13. The method of claim 9, wherein the network traffic files include data corresponding to both normal and malicious network behaviors.

14. The method of claim 9, wherein building the MDL model for each natural cluster includes concatenating all files in the natural cluster into a single string.

15. The method of claim 9, further comprising displaying on a display, a visualization plot based on the output, the plot showing a graphical representation of network traffic distance from the plurality of natural clusters.

16. A nontransitory computer-readable medium having software instructions stored thereon that, when executed by a processor, cause the processor to perform operations comprising:

clustering raw network traffic files into a plurality of natural clusters based on minimum description length (MDL) similarity;

building an MDL model for each natural cluster;

calculating distances from each traffic file to each MDL model to obtain a distance vector for each traffic file, each distance vector having a distance from a corresponding traffic file to each MDL model;

clustering labeled network traffic data into a plurality of trained clusters;

selecting features of the plurality of natural clusters and the plurality of trained clusters for use in classification of network traffic; and

building a decision model based on the distance vectors and the selected features of the plurality of natural clusters and the plurality of trained clusters.

17. The nontransitory computer-readable medium of claim 16, wherein the operations further comprise:

analyzing network traffic using the decision model; and

generating an output based on the analyzing, the output indicating potential matches between network traffic and an MDL model corresponding to malicious activity.

18. The nontransitory computer-readable medium of claim 16, wherein the clustering raw network traffic files includes:

generating a pair-wise similarity matrix using MDL models to calculate a distance value between pairs of traffic files;

applying hierarchical clustering to the similarity matrix to generate a set of clusters;

refining the set of clusters; and

pruning the set of clusters.

19. The nontransitory computer-readable medium of claim 16, wherein the network traffic files include data corresponding to normal network behaviors.

20. The nontransitory computer-readable medium of claim 16, wherein the network traffic files include data corresponding to both normal and malicious network behaviors.

21. The nontransitory computer-readable medium of claim 16, wherein building the MDL model for each natural cluster includes concatenating all files in the natural cluster into a single string.

22. The nontransitory computer-readable medium of claim 16, wherein the operations further comprise:

displaying on a display, a visualization plot based on the output, the plot showing a graphical representation of network traffic distance from the plurality of natural clusters.

23. A computerized method for computer network intrusion detection, the method comprising:

analyzing, with a processor programmed to perform network intrusion detection, network traffic using a decision model, the decision model having been built by;

clustering raw network traffic files into a plurality of natural clusters based on minimum description length (MDL) similarity;

building an MDL model for each natural cluster;

calculating distances from each traffic file to each MDL model to obtain a distance vector for each traffic file, each distance vector having a distance from a corresponding traffic file to each MDL model;

clustering labeled network traffic data into a plurality of trained clusters;

selecting features of the plurality of natural clusters and the plurality of trained clusters for use in classification of network traffic; and

building a decision model based on the distance vectors and the selected features of the plurality of natural clusters and the plurality of trained clusters; and

generating, with the processor, an output based on the analyzing, the output indicating potential matches between network traffic and an MDL model corresponding to malicious activity.

24. The method of claim 23, further comprising displaying on a display, a visualization plot based on the output, the plot showing a graphical representation of network traffic distance from the plurality of natural clusters.