Intrusion detection using robust singular value decomposition
A method for detecting anomalous streaming network traffic data in real time includes: creating an anomaly detection model including a singular value matrix and a data pattern matrix from a matrix of historical network traffic data; storing the singular value matrix and the data pattern matrix of the anomaly detection model; receiving streaming network traffic data; performing a log transform on the streaming network traffic data; applying the anomaly detection model to a matrix of the streaming network traffic data in real time as the streaming network traffic data is received; detecting anomalous patterns in the streaming network traffic data based on patterns identified by the anomaly detection model; and associating the anomalous patterns in the streaming network traffic data with IP addresses.
1. A method comprising:
creating an anomaly detection model including a singular value matrix and a data pattern matrix from a matrix of historical network traffic data, wherein the creating the anomaly detection model comprises:
aggregating volumetric data of the historical network traffic data based on temporal indicators;
performing a log transform of the volumetric data that is aggregated;
performing a low rank approximation of a matrix of aggregated historical network traffic data such that the matrix of aggregated historical network traffic data is decomposed into a low rank matrix and a sparse noise matrix; and
performing a singular value decomposition on the low rank matrix to generate the singular value matrix and the data pattern matrix, wherein the singular value matrix and the data pattern matrix form the anomaly detection model, wherein the temporal indicators comprise at least one of: a timestamp, an internet protocol address, a transmission control protocol flag, a traffic direction, or port and protocol information;
storing the singular value matrix and the data pattern matrix of the anomaly detection model;
receiving streaming network traffic data;
performing a log transform on the streaming network traffic data;
applying the anomaly detection model to a matrix of the streaming network traffic data;
detecting at least one anomalous pattern in the streaming network traffic data based on patterns identified by the anomaly detection model; and
associating the at least one anomalous pattern in the streaming network traffic data with at least one internet protocol address.
2. The method of claim 1 , wherein the low rank approximation is performed using a principal component pursuit methodology.
3. The method of claim 1 , wherein the detecting the at least one anomalous pattern comprises:
calculating a matrix of the streaming network traffic data in a singular value decomposition space using the singular value matrix and the data pattern matrix;
transforming the matrix of the streaming network traffic data from the singular value decomposition space to a data space using the singular value matrix and the data pattern matrix;
performing an error calculation between a row of the matrix of the streaming network traffic data and a corresponding row of the transformed matrix of the streaming network traffic data;
determining whether an error calculation value exceeds a threshold value; and
in response to determining that the error calculation value exceeds the threshold value, identifying a corresponding streaming network traffic data as anomalous.
4. The method of claim 3 , wherein the performing the error calculation comprises:
performing a sum of squared error calculation between the row of the matrix of the streaming network traffic data and the corresponding row of the transformed matrix of the streaming network traffic data.
5. The method of claim 3 , wherein the calculating the matrix of the streaming network traffic data in the singular value decomposition space comprises:
solving a matrix equation Ux=XVΣ −1 ,
where Ux is the matrix of the streaming network traffic data in the singular value decomposition space, X is a matrix of the streaming network traffic data, V is the data pattern matrix of the anomaly detection model, and Σ −1 is an inverse of the singular value matrix of the anomaly detection model.
6. The method of claim 3 , wherein the transforming the matrix of the streaming network traffic data from the singular value decomposition space to the data space comprises:
solving a matrix equation {tilde over (X)}=UxΣV T ,
where {tilde over (X)} is the transformed matrix in the data space, Ux is the matrix of the streaming network traffic data in the singular value decomposition space, Σ is the singular value matrix, and V T is a transpose of the data pattern matrix.
7. The method of claim 1 , further comprising:
scoring a severity of the at least one anomalous pattern in the streaming network traffic data based on the patterns identified by the anomaly detection model.
8. A system comprising:
a memory;
a network interface; and
one or more processors in communication with the memory and the network interface, the one or more processors configured to:
create an anomaly detection model including a singular value matrix and a data pattern matrix from a matrix of historical network traffic data, wherein the one or more processors are configured to create the anomaly detection model by being configured to:
aggregate volumetric data of the historical network traffic data based on temporal indicators;
perform a log transform of the aggregated volumetric data;
perform a low rank approximation of a matrix of aggregated historical network traffic data such that the matrix of aggregated historical network traffic data is decomposed into a low rank matrix and a sparse noise matrix; and
perform a singular value decomposition on the low rank matrix to generate the singular value matrix and the data pattern matrix, wherein the temporal indicators comprise at least one of: a timestamp, an internet protocol address, a transmission control protocol flag, a traffic direction, or port and protocol information;
store the singular value matrix and the data pattern matrix of the anomaly detection model;
receive streaming network traffic data;
perform a log transform on the streaming network traffic data;
apply the anomaly detection model to a matrix of the streaming network traffic data;
detect at least one anomalous pattern in the streaming network traffic data based on patterns identified by the anomaly detection model; and
associate the at least one anomalous pattern in the streaming network traffic data with at least one internet protocol address.
9. The system of claim 8 , wherein the one or more processors are configured to perform the low rank approximation using a principal component pursuit methodology.
10. The system of claim 8 , wherein the detecting the at least one anomalous pattern comprises:
calculate a matrix of the streaming network traffic data in a singular value decomposition space using the singular value matrix and the data pattern matrix;
transform the matrix of the streaming network traffic data from the singular value decomposition space to a data space using the singular value matrix and the data pattern matrix;
perform an error calculation between a row of the matrix of the streaming network traffic data and a corresponding row of the transformed matrix of the streaming network traffic data;
determine whether an error calculation value exceeds a threshold value; and
in response to determining that the error calculation value exceeds the threshold value, identifying a corresponding streaming network traffic data as anomalous.
11. The system of claim 8 , wherein the one or more processors are further configured to:
score a severity of the at least one anomalous pattern in the streaming network traffic data based on the patterns identified by the anomaly detection model.
12. A non-transitory computer-readable storage medium storing instructions which, when executed by a processor, cause the processor to perform operations, the operations comprising:
creating an anomaly detection model including a singular value matrix and a data pattern matrix from a matrix of historical network traffic data, wherein the creating the anomaly detection model comprises:
aggregating volumetric data of the historical network traffic data based on temporal indicators;
performing a log transform of the aggregated volumetric data;
performing a low rank approximation of a matrix of aggregated historical network traffic data such that the matrix of aggregated historical network traffic data is decomposed into a low rank matrix and a sparse noise matrix; and
performing a singular value decomposition on the low rank matrix to generate the singular value matrix and the data pattern matrix, wherein the singular value matrix and the data pattern matrix form the anomaly detection model, wherein the temporal indicators comprise at least one of: a timestamp, an internet protocol address, a transmission control protocol flag, a traffic direction, or port and protocol information;
storing the singular value matrix and the data pattern matrix of the anomaly detection model;
receiving streaming network traffic data;
performing a log transform on the streaming network traffic data;
applying the anomaly detection model to a matrix of the streaming network traffic data;
detecting at least one anomalous pattern in the streaming network traffic data based on patterns identified by the anomaly detection model; and
associating the at least one anomalous pattern in the streaming network traffic data with at least one internet protocol address.
13. The non-transitory computer-readable storage medium of claim 12 , wherein the low rank approximation is performed using a principal component pursuit methodology.
14. The non-transitory computer-readable storage medium of claim 12 , wherein the detecting the at least one anomalous pattern comprises:
calculating a matrix of the streaming network traffic data in a singular value decomposition space using the singular value matrix and the data pattern matrix;
transforming the matrix of the streaming network traffic data from the singular value decomposition space to a data space using the singular value matrix and the data pattern matrix;
performing an error calculation between a row of the matrix of the streaming network traffic data and a corresponding row of the transformed matrix of the streaming network traffic data;
determining whether an error calculation value exceeds a threshold value; and
in response to determining that the error calculation value exceeds the threshold value, identifying a corresponding streaming network traffic data as anomalous.
15. The non-transitory computer-readable storage medium of claim 14 , wherein the performing the error calculation comprises:
performing a sum of squared error calculation between the row of the matrix of the streaming network traffic data and the corresponding row of the transformed matrix of the streaming network traffic data.
16. The non-transitory computer-readable storage medium of claim 14 , wherein the calculating the matrix of the streaming network traffic data in the singular value decomposition space comprises:
solving a matrix equation Ux=XVΣ −1 ,
where Ux is the matrix of the streaming network traffic data in the singular value decomposition space, X is a matrix of the streaming network traffic data, V is the data pattern matrix of the anomaly detection model, and Σ −1 is an inverse of the singular value matrix of the anomaly detection model.
17. The non-transitory computer-readable storage medium of claim 14 , wherein the transforming the matrix of the streaming network traffic data from the singular value decomposition space to the data space comprises:
solving a matrix equation {tilde over (X)}=UxΣV T ,
where {tilde over (X)} is the transformed matrix in the data space, Ux is the matrix of the streaming network traffic data in the singular value decomposition space, Σ is the singular value matrix, and V T is a transpose of the data pattern matrix.
18. The non-transitory computer-readable storage medium of claim 14 , wherein the transforming the matrix of the streaming network traffic data from the singular value decomposition space to the data space comprises:
solving a matrix equation {tilde over (X)}=UxΣV T ,
where {tilde over (X)} is the transformed matrix in the data space, Ux is the matrix of the streaming network traffic data in the singular value decomposition space, Σ is the singular value matrix, and V T is a transpose of the data pattern matrix.
19. The non-transitory computer-readable storage medium of claim 12 , the operations further comprising:
scoring a severity of the at least one anomalous pattern in the streaming network traffic data based on the patterns identified by the anomaly detection model.
20. The non-transitory computer-readable storage medium of claim 12 , wherein the cumulative distribution function is based on shape and scale parameters of an exponentiated Weibull probability distribution function fitted to a plurality of error calculation results.