Bayesian tree aggregation in decision forests to increase detection of rare malware

Patent metadata

Field	Value
Publication number	US-10356117-B2
Application number	US-201715648563-A
Country	US
Kind code	B2
Filing date	Jul 13, 2017
Priority date	Jul 13, 2017
Publication date	Jul 16, 2019
Grant date	Jul 16, 2019

Abstract

In one embodiment, a computing device provides a feature vector as input to a random decision forest comprising a plurality of decision trees trained using a training dataset, each decision tree being configured to output a classification label prediction for the input feature vector. For each of the decision trees, the computing device determines a conditional probability of the decision tree based on a true classification label and the classification label prediction from the decision tree for the input feature vector. The computing device generates weightings for the classification label predictions from the decision trees based on the determined conditional probabilities. The computing device applies a final classification label to the feature vector based on the weightings for the classification label predictions from the decision trees.

First claim

What is claimed is:

1. A method comprising:
providing, by a computing device, a feature vector as input to a random decision forest comprising a plurality of decision trees trained using a training dataset, each decision tree being configured to output a classification label prediction for the input feature vector;
determining, by the computing device and for each of the decision trees, a conditional probability of the decision tree based on a true classification label and the classification label prediction from the decision tree for the input feature vector, wherein determining includes:
performing, by the computing device, a lookup of the conditional probabilities from a lookup table, wherein the conditional probabilities were calculated by using as input, for each decision tree, a portion of the training dataset that was not used to train that decision tree, and
calculating the conditional probabilities by using as input, for each decision tree, a portion of the training dataset that was not used to train that decision tree;

generating, by the computing device, weightings for the classification label predictions from the decision trees based on the determined conditional probabilities; and
applying, by the computing device, a final classification label to the feature vector based on the weightings for the classification label predictions from the decision trees.

2. The method as in claim 1 , wherein the feature vector comprises one or more characteristics of observed traffic in a network, and wherein the final classification label indicates the presence of malware in the network.

3. The method as in claim 1 , wherein generating weightings for the classification label predictions from the decision trees based on the determined conditional probabilities comprises:
computing, by the computing device and for each classification label in the classification label predictions, a product of the corresponding determined conditional probabilities.

4. The method as in claim 1 , wherein generating weightings for the classification label predictions from the decision trees based on the determined conditional probabilities comprises:
computing, by the computing device and for each classification label in the classification label predictions, a sum of logarithms of the corresponding determined conditional probabilities.

5. The method as in claim 1 , further comprising:
randomly selecting samples from the training dataset; and
using the randomly selected samples to train the decision trees.

6. An apparatus, comprising:
one or more network interfaces to communicate with a network;
a processor coupled to the network interfaces and configured to execute one or more processes; and
a memory configured to store a process executable by the processor, the process when executed configured to:
provide a feature vector as input to a random decision forest comprising a plurality of decision trees trained using a training dataset, each decision tree being configured to output a classification label prediction for the input feature vector;
determine, for each of the decision trees, a conditional probability of the decision tree based on a true classification label and the classification label prediction from the decision tree for the input feature vector, wherein the determination includes:
performing a lookup of the conditional probabilities from a lookup table, wherein the conditional probabilities were calculated by using as input, for each decision tree, a portion of the training dataset that was not used to train that decision tree, and
calculating the conditional probabilities by using as input, for each decision tree, a portion of the training dataset that was not used to train that decision tree;

generate weightings for the classification label predictions from the decision trees based on the determined conditional probabilities; and
apply a final classification label to the feature vector based on the weightings for the classification label predictions from the decision trees.

7. The apparatus as in claim 6 , wherein the feature vector comprises one or more characteristics of observed traffic in a network, and wherein the final classification label indicates the presence of malware in the network.

8. The apparatus as in claim 6 , wherein the apparatus generates the weightings for the classification label predictions from the decision trees based on the determined conditional probabilities by:
computing, for each classification label in the classification label predictions, a product of the corresponding determined conditional probabilities.

9. The apparatus as in claim 6 , wherein the apparatus generates the weightings for the classification label predictions from the decision trees based on the determined conditional probabilities by:
computing, for each classification label in the classification label predictions, a sum of logarithms of the corresponding determined conditional probabilities.

10. The apparatus as in claim 6 , wherein the process when executed is further configured to:
randomly select samples from the training dataset; and
use the randomly selected samples to train the decision trees.

11. A tangible, non-transitory, computer-readable medium storing program instructions that cause a computing device to execute a process comprising:
providing, by the computing device, a feature vector as input to a random decision forest comprising a plurality of decision trees trained using a training dataset, each decision tree being configured to output a classification label prediction for the input feature vector;
determining, by the computing device and for each of the decision trees, a conditional probability of the decision tree based on a true classification label and the classification label prediction from the decision tree for the input feature vector, wherein determining includes:
performing, by the computing device, a lookup of the conditional probabilities from a lookup table, wherein the conditional probabilities were calculated by using as input, for each decision tree, a portion of the training dataset that was not used to train that decision tree, and
calculating the conditional probabilities by using as input, for each decision tree, a portion of the training dataset that was not used to train that decision tree;

generating, by the computing device, weightings for the classification label predictions from the decision trees based on the determined conditional probabilities; and
applying, by the computing device, a final classification label to the feature vector based on the weightings for the classification label predictions from the decision trees.

12. The computer-readable medium as in claim 11 , wherein the feature vector comprises one or more characteristics of observed traffic in a network, and wherein the final classification label indicates the presence of malware in the network.

13. The computer-readable medium as in claim 11 , wherein generating weightings for the classification label predictions from the decision trees based on the determined conditional probabilities comprises:
computing, by the computing device and for each classification label in the classification label predictions, a product of the corresponding determined conditional probabilities.

14. The computer-readable medium as in claim 11 , wherein generating weightings for the classification label predictions from the decision trees based on the determined conditional probabilities comprises:
computing, by the computing device and for each classification label in the classification label predictions, a sum of logarithms

Assignees

• Cisco Tech Inc

Inventors

• Brabec Jan
• Machlica Lukas

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• H04L63/1458

  Denial of Service · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• G06N20/20

  Ensemble learning · CPC title