Anomaly detection in dynamically evolving data and systems

• US 10,333,953 B1
• Filed: 12/10/2017
• Issued: 06/25/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/836,876
• Time in Patent Office: 562 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 computer implemented method, comprising steps of:

a) receiving multi-dimensional data with multi-dimensional data points, each data point having n features;

b) choosing a plurality m of data points to form an input matrix of size m×

n;

c) processing input matrix m×

n to obtain a reduced dimension embedding matrix of size m×

r to form an embedded space of dimension r that includes a normal cluster, wherein r<

<

n;

d) applying an out-of-sample extension (OOSE) procedure to a newly arrived multidimensional data point (NAMDP) not belonging to the plurality m of data points to compute coordinates of the NAMDP in the embedded space;

e) generate a histogram of density values of the embedded r dimensional data points and on the computed coordinates of the NAMDP;

f determining, based on the density values whether the NAMDP is normal, belonging to the normal cluster, or abnormal, not belonging to the normal cluster, wherein an abnormal value is mapped to the smallest histogram bin size and normal values consist of the other histogram bin values; and

g if the NAMDP is abnormal, blocking the abnormal data point, whereby the performing of steps (c)-(f) in an embedded space of dimension r wherein r<

<

n significantly reduces computer memory needs and speeds up computing operations for detection of anomalies.

2. The method of claim 1, wherein the multi-dimensional data is received from an entity selected from a group consisting of a service, a process controller, an appliance, a device, an inspection machine, a communication network, a performance monitoring system, an apparatus, a piece of equipment, a resource, an image and a behavioral profile.

3. The method of claim 1, wherein the processing input matrix m×

n includes;

i. obtaining at least one statistical analysis matrix from the multi-dimensional data;

ii. normalizing each statistical analysis matrix to obtain a respective normalized Markov matrix, and

iii. reducing the matrix dimension of each respective normalized Markov matrix to obtain a respective reduced dimension embedding matrix.

4. The method of claim 3, wherein the reducing the matrix dimension of each respective normalized Markov matrix to obtain a respective reduced dimension embedding matrix includes reducing the matrix dimension using diffusion maps.

5. The method of claim 3, wherein the statistical analysis matrix includes statistical information on metadata of communication packets.

6. The method of claim 3, wherein the statistical analysis matrix includes statistical information on payloads of communication packets.

7. The method of claim 1, wherein the multi-dimensional data includes real-time data.

8. The method of claim 1, wherein the multi-dimensional data includes data selected from the group consisting of optical data, electrical data, mechanical data, acoustical data, magnetic data, flow data and heat data and a combination thereof.

9. The method of claim 1, applied to network intrusion detection.

10. The method of claim 1, applied to hyperspectral imaging.

11. The method of claim 1, applied to semiconductor process monitoring.

12. The method of claim 1, wherein the multi-dimensional data includes financial data and wherein the method is applied to financial markets.

13. The method of claim 1, wherein the multi-dimensional data includes financial data and wherein the method is applied to financial transactions monitoring.

14. The method of claim 1, wherein the multi-dimensional data includes physiological data and wherein the method is applied to human health monitoring.

15. An anomaly detection system (ADS), comprising:

a computer program stored on a non-transitory computer readable medium, the computer program dedicated to performing steps of;

a) receiving multi-dimensional data with multi-dimensional data points, each data point having n features;

b) choosing a plurality m of data points to form an input matrix of size m×

n;

c) processing input matrix m×

n to obtain a reduced dimension embedding matrix of size m×

r to form an embedded space of dimension r that includes a normal cluster, wherein r«

n;

d) applying an out-of-sample extension (OOSE) procedure to a newly arrived multidimensional data point (NAMDP) not belonging to the plurality m of data points to compute coordinates of the NAMDP in the embedded space;

e) generate a histogram of density values of the embedded r dimensional data points and on the computed coordinates of the NAMDP;

f) determining, based on the density values whether the NAMDP is normal, belonging to the normal cluster, or abnormal, not belonging to the normal cluster, wherein an abnormal value is mapped to the smallest histogram bin size and normal values consist of the other histogram bin values; and

g) if the NAMDP is abnormal, blocking the abnormal data point,

whereby the performing of steps (c)-(f) in an embedded space of dimension r wherein r«

n significantly reduces computer memory needs and speeds up computing operations for detection of anomalies.

16. The ADS of claim 15, wherein the multi-dimensional data is received from an entity selected from a group consisting of a service, a process controller, an appliance, a device, an inspection machine, a communication network, a performance monitoring system, an apparatus, a piece of equipment, a resource, an image and a behavioral profile.

17. The ADS of claim 15, wherein the processing input matrix m×

n includes;

i. obtaining at least one statistical analysis matrix from the multi-dimensional data;

ii. normalizing each statistical analysis matrix to obtain a respective normalized Markov matrix, and

iii. reducing the matrix dimension of each respective normalized Markov matrix to obtain a respective reduced dimension embedding matrix.

18. The ADS of claim 15, wherein the multi-dimensional data includes semiconductor processing data.

19. The ADS of claim 15, wherein the multi-dimensional data includes financial data and wherein the method is applied to financial markets.

20. The ADS of claim 15, wherein the multi-dimensional data includes financial data and wherein the method is applied to financial transactions monitoring.