Back to results
US 11,893,005 B2Granted
Anomaly detection based on an event tree
AssigneeBlackBerry Limited
InventorJohn Raymond Herrema, III
Life of this patent
Estimating the term…
Abstract
Systems, methods, and software can be used for anomaly detection. In some aspect, a number of training events are obtained. A data structure represented by a decision tree is generated based on the number of training events. A to-be-scored event is obtained and a traversed path is determined for the to-be-scored event. An anomaly score is computed based on the traversed path and the to-be-scored event is determined to be an anomalous or normal event based on the anomaly score.
Claims20
A computer-implemented method, comprising:
- obtaining a data structure represented by a decision tree, wherein the data structure represented by the decision tree is generated based on a plurality of training events, wherein each of the plurality of training events has a plurality of attributes, and wherein each of the plurality of attributes has an attribute value, wherein the decision tree comprises a plurality of event nodes comprising a root node, one or more non-leaf nodes, and one or more branches, and one or more leaf nodes, wherein each of the plurality of event nodes represents one of the plurality of attributes and one of a plurality of attribute values, wherein each of the one or more branches below a non-leaf node represents an attribute value of an attribute represented by the non-leaf node, wherein each of the plurality of attributes is associated with an importance level for detecting anomalies, wherein the one or more nodes are arranged in the decision tree based on the importance level of the plurality of attributes, and wherein a first node representing a first attribute having a first importance level is positioned at a higher layer than a second node representing a second attribute having a second importance level when the first importance level is more important than the second importance level;
- obtaining a to-be-scored event, wherein the to-be-scored event has one or more attributes of the plurality of attributes and one or more attribute values;
- determining a traversed path for the to-be-scored event by mapping the one or more attributes and the one or more attribute values of the to-be-scored event to the decision tree, wherein the mapping comprises:
- determining whether the to-be-scored event has a first attribute value for the first attribute having the first importance level;
- in response to determining that the to-be-scored event has the first attribute value for the first attribute having the first importance level, determining whether the first attribute value for the first attribute matches an attribute value of a branch associated with the root node;
- in response to determining that the to-be-scored event has the first attribute value for the first attribute having the first importance level matches the attribute value of a branch associated with the root node, determining a child node associated with the branch as a first child node for the to-be-scored event;
- determining whether the to-be-scored event has a second attribute value for the second attribute having the second importance level;
- determining a second child node for the to-be-scored event based on matching the second attribute value for the second attribute having the second importance level with attribute values of child nodes of the first child node, wherein the second child node is a child node of the first child node;
- determining whether the to-be-scored event has a third attribute value for a third attribute having a third importance level, wherein the second importance level is more important than the third importance level;
- and
- determining a third child node for the to-be-scored event based on matching the third attribute value for the third attribute having the third importance level with attribute values of child nodes of the second child node, wherein the third child node is a child node of the second child node;
- computing an anomaly score of the to-be-scored event based on the traversed path, wherein the computing the anomaly score comprises:
- determining a path length of each node on the traversed path;
- determining a path length of the to-be-scored event by summing the path length of each node on the traversed path;
- and
- determining the anomaly score based on the path length of the to-be-scored event relative to an average path length;
- determining whether the to-be-scored event is an anomalous event based on the anomaly score;
- and
- identifying a compromised device based on the anomaly score.
16 more elements
An electronic device, comprising:
- a memory;
- and
- at least one hardware processor communicatively coupled with the memory and configured to perform operations comprising:
- obtaining a data structure represented by a decision tree, wherein the data structure represented by the decision tree is generated based on a plurality of training events, wherein each of the plurality of training events has a plurality of attributes, and wherein each of the plurality of attributes has an attribute value, wherein the decision tree comprises a plurality of event nodes comprising a root node, one or more non-leaf nodes, and one or more branches, and one or more leaf nodes, wherein each of the plurality of event nodes represents one of the plurality of attributes and one of a plurality of attribute values, wherein each of the one or more branches below a non-leaf node represents an attribute value of an attribute represented by the non-leaf node, wherein each of the plurality of attributes is associated with an importance level for detecting anomalies, wherein the one or more nodes are arranged in the decision tree based on the importance level of the plurality of attributes, and wherein a first node representing a first attribute having a first importance level is positioned at a higher layer than a second node representing a second attribute having a second importance level when the first importance level is more important than the second importance level;
- obtaining a to-be-scored event, wherein the to-be-scored event has one or more attributes of the plurality of attributes and one or more attribute values;
- determining a traversed path for the to-be-scored event by mapping the one or more attributes and the one or more attribute values of the to-be-scored event to the decision tree, wherein the mapping comprises:
- determining whether the to-be-scored event has a first attribute value for the first attribute having the first importance level;
- in response to determining that the to-be-scored event has the first attribute value for the first attribute having the first importance level, determining whether the first attribute value for the first attribute matches an attribute value of a branch associated with the root node;
- in response to determining that the to-be-scored event has the first attribute value for the first attribute having the first importance level matches the attribute value of a branch associated with the root node, determining a child node associated with the branch as a first child node for the to-be-scored event;
- determining whether the to-be-scored event has a second attribute value for the second attribute having the second importance level;
- determining a second child node for the to-be-scored event based on matching the second attribute value for the second attribute having the second importance level with attribute values of child nodes of the first child node, wherein the second child node is a child node of the first child node;
- determining whether the to-be-scored event has a third attribute value for a third attribute having a third importance level, wherein the second importance level is more important than the third importance level;
- and
- determining a third child node for the to-be-scored event based on matching the third attribute value for the third attribute having the third importance level with attribute values of child nodes of the second child node, wherein the third child node is a child node of the second child node;
- computing an anomaly score of the to-be-scored event based on the traversed path, wherein the computing the anomaly score comprises:
- determining a path length of each node on the traversed path;
- determining a path length of the to-be-scored event by summing the path length of each node on the traversed path;
- and
- determining the anomaly score based on the path length of the to-be-scored event relative to an average path length;
- determining whether the to-be-scored event is an anomalous event based on the anomaly score;
- and
- identifying a compromised device based on the anomaly score.
19 more elements
A non-transitory computer-readable medium containing instructions which, when executed, cause a computing device to perform operations comprising:
- obtaining a data structure represented by a decision tree, wherein the data structure represented by the decision tree is generated based on a plurality of training events, wherein each of the plurality of training events has a plurality of attributes, and wherein each of the plurality of attributes has an attribute value, wherein the decision tree comprises a plurality of event nodes comprising a root node, one or more non-leaf nodes, and one or more branches, and one or more leaf nodes, wherein each of the plurality of event nodes represents one of the plurality of attributes and one of a plurality of attribute values, wherein each of the one or more branches below a non-leaf node represents an attribute value of an attribute represented by the non-leaf node, wherein each of the plurality of attributes is associated with an importance level for detecting anomalies, wherein the one or more nodes are arranged in the decision tree based on the importance level of the plurality of attributes, and wherein a first node representing a first attribute having a first importance level is positioned at a higher layer than a second node representing a second attribute having a second importance level when the first importance level is more important than the second importance level;
- obtaining a to-be-scored event, wherein the to-be-scored event has one or more attributes of the plurality of attributes and one or more attribute values;
- determining a traversed path for the to-be-scored event by mapping the one or more attributes and the one or more attribute values of the to-be-scored event to the decision tree, wherein the mapping comprises:
- determining whether the to-be-scored event has a first attribute value for the first attribute having the first importance level;
- in response to determining that the to-be-scored event has the first attribute value for the first attribute having the first importance level, determining whether the first attribute value for the first attribute matches an attribute value of a branch associated with the root node;
- in response to determining that the to-be-scored event has the first attribute value for the first attribute having the first importance level matches the attribute value of a branch associated with the root node, determining a child node associated with the branch as a first child node for the to-be-scored event;
- determining whether the to-be-scored event has a second attribute value for the second attribute having the second importance level;
- determining a second child node for the to-be-scored event based on matching the second attribute value for the second attribute having the second importance level with attribute values of child nodes of the first child node, wherein the second child node is a child node of the first child node;
- determining whether the to-be-scored event has a third attribute value for a third attribute having a third importance level, wherein the second importance level is more important than the third importance level;
- and
- determining a third child node for the to-be-scored event based on matching the third attribute value for the third attribute having the third importance level with attribute values of child nodes of the second child node, wherein the third child node is a child node of the second child node;
- computing an anomaly score of the to-be-scored event based on the traversed path, wherein the computing the anomaly score comprises:
- determining a path length of each node on the traversed path;
- determining a path length of the to-be-scored event by summing the path length of each node on the traversed path;
- and
- determining the anomaly score based on the path length of the to-be-scored event relative to an average path length;
- determining whether the to-be-scored event is an anomalous event based on the anomaly score;
- and
- identifying a compromised device based on the anomaly score.
16 more elements
Dependencies are inferred from the claim text.