Anomaly detection in dynamically evolving data and systems

• US 10,187,409 B1
• Filed: 11/06/2017
• Issued: 01/22/2019
• Est. Priority Date: 11/02/2007
• Status: Active Grant

• Current Assignee: ThetaRay Ltd.
• Original Assignee: ThetaRay Ltd.
• Inventors: Averbuch, Amir, Coifman, Ronald R., David, Gil
• Primary Examiner(s): Chang, Kenneth W
• Assistant Examiner(s): Lane, Gregory A
• Application Number:
  US15/804,287
• Time in Patent Office: 442 Days
• Field of Search: 726 23
• 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: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

Detection of abnormalities in multi-dimensional data is performed by processing the multi-dimensional data to obtain a reduced dimension embedding matrix, using the reduced dimension embedding matrix to form a lower dimension (of at least 2D) embedded space, applying an out-of-sample extension procedure in the embedded space to compute coordinates of a newly arrived data point and using the computed coordinates of the newly arrived data point and Euclidean distances to determine whether the newly arrived data point is normal or abnormal.

Claims

1. A method comprising:

a) obtaining, from a traffic analyzer, data comprising a plurality M of N-dimensional data points, wherein N≥

3 and M»

N;

b) defining a collection Q of N-dimensional data points 1≤

Q«

M as a metadata point with dimension N such that the data includes M/Q metadata points;

c) by the traffic analyzer, generating from the metadata points a metadata statistics matrix of size (M/Q)×

N; and

d) by a computer,

processing the metadata statistics matrix into a Markov kernel matrix, processing the Markov kernel matrix to obtain r eigenvalues and associated eigenvectors, wherein r«

N,

forming a r-dimensional embedded space comprising r-dimensional data points using the r eigenvalues and associate eigenvectors,

receiving Q newly arrived N-dimensional points that include N features that form a respective N-dimensional metadata point,

embedding the newly arrived N-dimensional metadata point into the r-dimensional embedded space to obtain a new r-dimensional data point;

determining that the new r-dimensional data point is an anomaly based on a density value, and

blocking the anomaly,

using the M/Q metadata points instead of M data points when Q>

1, and of r-dimensional data points instead of N-dimensional data points wherein r«

N, to increase significantly a speed of detection rate of anomalies and to enhance significantly performance of the computer, respectively.

2. The method of claim 1, wherein the determining that the new r-dimensional data point is an anomaly is performed without use of a signature.

3. The method of claim 1, wherein the determining that the new r-dimensional data point is an anomaly is performed without use of a threshold.

4. The method of claim 1, wherein the determining that the new r-dimensional data point is an anomaly is performed without use of a rule.

5. The method of claim 1, further comprising, by the computer, generating an alert related to the anomaly.

6. The method of claim 1, further comprising, by the computer, visualizing the anomaly.

7. A system comprising:

a) a traffic analyzer used to provide data comprising a plurality M of Tridimensional data points, wherein N≥

3 and M»

N, wherein a collection Q, 1≤

Q«

M, of data points forms a N-dimensional metadata point such that the data includes M/Q metadata points, the traffic analyzer further used to generate from the metadata points a statistics matrix of size (M/Q)×

N; and

b) a computer for executing a computer program stored on a computer readable medium, the computer program dedicated to,

process the metadata statistics matrix into a Markov kernel matrix, process the Markov kernel matrix to obtain r eigenvalues and associated eigenvectors, wherein r«

N,

form a r-dimensional embedded space comprising r-dimensional data points using the r eigenvalues and associate eigenvectors,

receive Q newly arrived N-dimensional points that include N features that form a respective N-dimensional metadata point,

embed the newly arrived N-dimensional metadata point into the r-dimensional embedded space to obtain a new r-dimensional data point;

determine that the new r-dimensional data point is an anomaly based on a density value, and

block the anomaly,

using the M/Q metadata points instead of M data points when Q>

1, and of r-dimensional data points instead of N-dimensional data points wherein r«

N, to increase significantly a speed of detection rate of anomalies and to enhance significantly performance of the computer, respectively.

8. The system of claim 7, wherein the computer program is dedicated to determine that the new r-dimensional data point is an anomaly without using a signature.

9. The system of claim 7, wherein the computer program is dedicated to determine that the new r-dimensional data point is an anomaly without using a threshold.

10. The system of claim 7, wherein the computer program is dedicated to determine that the new r-dimensional data point is an anomaly without using a rule.

11. The system of claim 7, wherein the computer program is further dedicated to generate an alert related to the anomaly.

12. The system of claim 7, wherein the computer program is further dedicated to visualize the anomaly.