EXPLAINING NETWORK ANOMALIES USING DECISION TREES

• US 20160036844A1
• Filed: 10/09/2015
• Published: 02/04/2016
• Est. Priority Date: 07/15/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: PEVNY, TOMAS, KOPP, MARTIN
• Granted Patent: US 10,230,747 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

In an embodiment, the method comprises receiving an identification of an anomaly associated with a false positive identification of a security threat by the intrusion detection system, wherein a first set of feature data identifies features of the anomaly; creating a plurality of training sets each comprising identifications of a plurality of samples of network communications; for the anomaly and each training set of the plurality of training sets, training a decision tree that is stored in digital memory of the security analysis computer; based at least in part on the plurality of trained decision trees, extracting a set of features that distinguish the anomaly from the plurality of samples; generating one or more rules associated with the anomaly from the extracted set of features and causing programming the security analysis computer with the one or more rules.

Claims

1. A method comprising:

using a security analysis computer, receiving, from an intrusion detection system, an identification of an anomaly associated with a false positive identification of a security threat by the intrusion detection system, wherein a first set of feature data identifies features of the anomaly;

using the security analysis computer, creating a plurality of training sets each comprising identifications of a plurality of samples of network communications, wherein a different subset of the first set of feature data respectively identifies each sample of the plurality of samples;

using the security analysis computer, for the anomaly and each training set of the plurality of training sets, training a decision tree that is stored in digital memory of the security analysis computer, resulting in storing in the memory a plurality of trained decision trees that are associated in the memory with the anomaly;

using the security analysis computer, based at least in part on the plurality of trained decision trees, extracting a set of features that distinguish the anomaly from the plurality of samples; and

using the security analysis computer, generating one or more rules associated with the anomaly from the extracted set of features and causing programming the security analysis computer with the one or more rules.

2. The method of claim 1, further comprising aggregating the one or more rules into a set of rules that is used in the security analysis computer as an anomaly specific identifier.

3. The method of claim 1, wherein creating a first training set of the plurality of training sets comprises pseudo-randomly selecting the plurality of samples.

4. The method of claim 1, wherein creating a first training set of the plurality of training sets comprises selecting the k-nearest neighbor samples from among the plurality of samples.

5. The method of claim 1, wherein creating a first training set of the plurality of training sets comprises selecting the plurality of samples from streaming data that has been received from the intrusion detection system.

6. The method of claim 1, wherein creating a first training set of the plurality of training sets comprises selecting the plurality of samples using a short history window.

7. The method of claim 1, wherein training the decision tree comprises:

selecting a feature with a maximal normalized margin;

calculating a threshold based on two feature values of the feature nearest to a feature value of the anomaly;

adding a decision node to the decision tree comparing remaining feature values to the threshold and distinguishing the anomaly from the plurality of samples.

8. The method of claim 1, wherein the feature data specifies one or more of:

information about packet retransmissions, information about active communications connections, information about transmissions of large files, information about email transmissions, information about traffic from a particular domain, information about traffic to a particular domain, a status of a packet retransmission rate, a status of an active connections count, a status of a large files transfer count, a status of an email volume size, a status of a traffic volume size, counts of undelivered communications, access failure information, device failure information.

9. The method of claim 1, wherein each of the trained decision trees is asymmetric and comprises one, two, or three levels.

10. The method of claim 1, further comprising:

receiving a new set of feature data from the intrusion detection system;

applying the one or more rules associated with the anomaly from the extracted set of features to the new set of feature data;

determining that the new set of feature data is a false positive.

11. A system comprising:

one or more processors;

a non-transitory computer-readable medium having instructions stored thereon, the instructions, when executed by the one or more processors, cause;

receiving, from an intrusion detection system, an identification of an anomaly associated with a false positive identification of a security threat by the intrusion detection system, wherein a first set of feature data identifies features of the anomaly;

creating a plurality of training sets each comprising identifications of a plurality of samples of network communications, wherein a different subset of the first set of feature data respectively identifies each sample of the plurality of samples;

using the security analysis computer, for the anomaly and each training set of the plurality of training sets, training a decision tree that is stored in digital memory of the security analysis computer, resulting in storing in the memory a plurality of trained decision trees that are associated in the memory with the anomaly;

based at least in part on the plurality of trained decision trees, extracting a set of features that distinguish the anomaly from the plurality of samples; and

generating one or more rules associated with the anomaly from the extracted set of features and causing programming the security analysis computer with the one or more rules.

12. The system of claim 11, wherein the instructions, when executed by the one or more processors, further cause:

aggregating the one or more rules into a set of rules that is used in the security analysis computer as an anomaly specific identifier.

13. The system of claim 11, wherein creating a first training set of the plurality of training sets comprises pseudo-randomly selecting the plurality of samples.

14. The system of claim 11, wherein creating a first training set of the plurality of training sets comprises selecting the k-nearest neighbor samples from among the plurality of samples.

15. The system of claim 11, wherein creating a first training set of the plurality of training sets comprises selecting the plurality of samples from streaming data that has been received from the intrusion detection system.

16. The system of claim 11, wherein creating a first training set of the plurality of training sets comprises selecting the plurality of samples using a short history window.

17. The system of claim 11, wherein training the decision tree comprises:

selecting a feature with a maximal normalized margin; and

calculating a threshold based on two feature values of the feature nearest to a feature value of the anomaly;

adding a decision node to the decision tree comparing remaining feature values to the threshold and distinguishing the anomaly from the plurality of samples.

18. The system of claim 11, wherein the feature data specifies one or more of:

information about packet retransmissions, information about active communications connections, information about transmissions of large files, information about email transmissions, information about traffic from a particular domain, information about traffic to a particular domain, a status of a packet retransmission rate, a status of an active connections count, a status of a large files transfer count, a status of an email volume size, a status of a traffic volume size, counts of undelivered communications, access failure information, device failure information.

19. The system of claim 11, wherein each of the trained decision trees is asymmetric and comprises one, two, or three levels.

20. The system of claim 11, wherein the instructions, when executed by the one or more processors, further cause:

receiving a new set of feature data from the intrusion detection system;

applying the one or more rules associated with the anomaly from the extracted set of features to the new set of feature data;

determining that the new set of feature data is a false positive.