CN104123448B - Multi-data-stream anomaly detection method based on context - Google Patents

Abstract

The present invention provides a context-based multi-data stream anomaly detection method, comprising the following steps: step 1, multi-data stream acquisition and snapshot generation; step 2, multi-data stream snapshot anomaly quantification; step 3, data stream anomaly quantification; step 4 , data stream anomaly identification. The purpose of the detection method provided by the present invention is to take the node anomaly detection of the isomorphic distributed computing system as the research background, and take the data flow monitored by the computing node as the research object, to provide a context information and single data comprehensively considering multiple data flows An anomaly detection method for historical behavior information of streams, with a high detection rate.

Description

Context-based anomaly detection method for multiple data streams

technical field

The invention belongs to anomaly detection technology, in particular to an anomaly detection method that integrates context information of multiple data streams and historical behavior information of a single data stream.

Background technique

Data stream anomaly detection is an important direction in data stream mining research. Anomalies refer to data that are out of the ordinary in a data set, that are not due to random bias, but are generated by an entirely different mechanism. Since finding anomalies in data streams has a wide range of applications in the fields of network attack monitoring, credit card fraud, and computing system performance analysis, data stream anomaly detection methods are one of the current research hotspots. The detection and mining of abnormal behaviors on data streams The research has attracted the attention of academia and industry.

In real-world applications such as distributed computing, the data stream management system needs to receive multiple data streams at the same time, and the data streams are often not completely independent, but correlated, for example, in the securities trading system, in the same market Stocks often have the same or similar ups and downs. In the road traffic network, the traffic flow of different road sections will also have a certain correlation. For interrelated data streams, once the correlation between them is found to be destroyed, it can be concluded that there are abnormalities in these data streams. Based on this idea, the researchers explore the method of detecting anomalies by monitoring the correlation between multiple data streams. Existing data flow anomaly detection methods can be roughly divided into grid-based data flow anomaly detection, density-based anomaly detection and distance-based anomaly detection.

Grid-based data flow anomaly detection is to divide the entire data space into many grids that are independent of each other and of the same size, and artificially set a support degree. When the support degree of the data elements contained in the grid exceeds or is equal to the prior When the support degree is set, one dimension is selected from all dimensions, and the grid is dynamically divided into two completely independent sub-grids according to this dimension. When the support of the sub-grid also reaches or exceeds the threshold, the same segmentation operation will also be performed on the sub-grid. Park and Lee et al. proposed a real-time data flow anomaly detection method. The grid clustering method does not need to calculate the distance between data objects, but only needs to directly put the data into the corresponding grid according to the grid size determined in advance. grid, so real-time incremental clustering can be achieved. After each clustering is completed, only the feature information of each class needs to be saved, and the abnormality of all classes is calculated, sorted in descending order, and the top-k class with the largest abnormality is divided into the final abnormal class. (Park N H, Lee W S. Statistical grid-based clustering over datastreams[J]. ACM SIGMOD Record, 2004, 33(1): 32-37.) The above anomaly detection methods either use the top-p method to maximize the anomaly quantification value The p data streams are regarded as abnormal, or the data stream whose abnormal quantitative value exceeds the predefined threshold is regarded as abnormal. These methods have problems in the actual application process: 1) The threshold is difficult to set. Reasonable setting of the threshold needs to be very familiar with the underlying mechanism of the application, which is too difficult for ordinary users; 2) The number of exceptions is always changing. It is abnormal that there may be more than p data streams at a certain moment, and these real abnormalities will be missed by using the top-p method. Therefore, an unguided learning method is adopted in the present invention to automatically acquire dynamically changing anomaly detection thresholds, which can better adapt to scenes with frequently changing anomalies.

The basic idea of density-based anomaly detection is to use the density of samples in a certain neighborhood to identify anomalies. The LOF algorithm is a representative algorithm for density-based anomaly detection (Breunig M M, Kriegel HP, Ng R T, et al. LOF: identifying density-based local outliers [C] // ACM Sigmod Record. ACM, 2000, 29 (2): 93-104.). This algorithm is an anomaly detection algorithm based on local density, which can accurately find abnormal data objects in data sets with uneven density distribution. However, the LOF algorithm is not suitable for direct use in anomaly detection of data streams, because of its large time complexity. If every time a new data object is obtained, the anomaly degree of all data objects needs to be recalculated, and the cost is intolerable. . Therefore, Pokrajac and Lazarevic et al. improved the existing static LOF algorithm and proposed a dynamic incremental LOF algorithm (Pokrajac D, Lazarevic A, LateckiL J.Incremental local outlier detection for data streams[C]//ComputationalIntelligence and Data Mining, 2007. CIDM2007. IEEE Symposium on. IEEE, 2007:504-515.). The core idea of the incremental LOF algorithm is that when a new data object arrives, it does not recalculate the value of the characteristic information of all data objects, but only calculates the value of each characteristic information of the part of the data object affected by the new input data object. to update. When the incremental LOF algorithm receives a new input data object, its main operation is divided into two steps: for the newly input data object, calculate the required feature information value; for the density change affected by the new input object Neighbor nodes update their characteristic information values one by one, and do not recalculate for unaffected data objects. After adopting this strategy, the dynamic incremental LOF algorithm can achieve the same effect as the repeated execution of the static LOF algorithm, but it greatly reduces the time complexity of algorithm execution, making it suitable for anomaly detection for data streams. However, the LOF algorithm does not consider the difference in the value range of different dimensions, which may cause the influence of some dimensions to be significantly greater than others; in addition, its time complexity is acceptable for offline detection, but not for real-time detection. practical. The present invention aims at the above two limitations of the LOF algorithm, and the time complexity of the proposed algorithm is O(n), which is linearly increasing with the number of data streams, and can meet the needs of real-time applications.

Distance-based anomaly detection was proposed by Knorr and Ng (Knorr E M, Ng R T, TucakovV. Distance-based outliers: algorithms and applications[J]. The VLDB Journal—The International Journal on Very Large Data Bases, 2000,8 (3-4):237-253.). Distance-based anomaly definition: An object O in a data set S is called DB(p, D)-outlier if it satisfies the following properties: at least p*100% of the objects in the data set S are farther than the distance D from O. Simply put, distance-based outliers are objects that do not have "enough" neighbors. Angiulli et al. also proposed a distance-based data flow anomaly detection algorithm Storm, including exact-storm and approx-Storm, the former is an accurate algorithm, and the latter is an approximate algorithm guaranteed by the central limit theorem (Angiulli F, Fassetti F .Detecting distance-based outliers in streams of data[C]//Proceedings of the sixteenth ACM conference on Conference on information and knowledge management. ACM,2007:811-820.). The Storm algorithm adopts a count-based sliding window model, and divides the neighbors of a specific data object into predecessor neighbors and follow-up neighbors according to the chronological order in which data objects arrive in the data stream. Two thresholds K and R are defined in advance, which represent the number of neighbors and the distance respectively. If the number of neighbors of an input data object in the data stream is less than K within the distance range of R, the object is abnormal data. A special class of data objects safe inliers is defined in the algorithm. No matter how the data flow evolves over time, this type of data objects will not become abnormal data objects in the entire data window, that is, the number of neighbors is always greater than K. Based on this assumption, the algorithm uses R-Tree to find the neighbors of each data object for all non-safe inliers data objects, so as to improve the retrieval efficiency. The above algorithm only considers the historical information of the data stream, and ignores the context information of the data stream. For example, in an isomorphic computing system, the data streams of the computing nodes often show similarity. The present invention comprehensively considers the context information of multiple data streams Using historical information on a single data flow to determine whether a certain data flow is an abnormal data flow has higher accuracy.

Contents of the invention

In order to overcome the shortcomings of the existing technology, the present invention provides a node anomaly detection method using an isomorphic distributed computing system, which takes the data stream monitored by the computing node as the research object and comprehensively considers the context information of multiple data streams and single data stream An anomaly detection method for historical behavior information.

A context-based multi-data stream anomaly detection method, comprising the following steps:

Step 1, multi-stream acquisition and snapshot generation, the process is as follows:

Given a distributed computing system composed of n isomorphic computing nodes, the observation value of each computing node is obtained synchronously at recording time t, and the data flow of each computing node is calculated according to the observation value. The data flow is recorded as a snapshot;

Step 2, abnormal quantification of multi-stream snapshots, the process is as follows:

Use the snapshot matrix M at time t to describe the instantaneous behavior of each computing node at time t; use 0-1 normalization method to calculate the normalized value for each column vector of matrix M one by one, and obtain a new matrix M'; Calculate the mean value of each column vector after normalization to obtain the deviation matrix M″; calculate the abnormal quantization value of the data flow snapshot generated by each computing node at time t;

Step 3, data flow abnormal quantification, the process is as follows:

Given any data stream, calculate the influence of all snapshot abnormal quantization values before time t on the current time t, and comprehensively consider the influence of multi-data stream snapshot abnormal quantification results and historical data in a single data stream on abnormal quantification results, and get The abnormal quantization result value of the outgoing data stream;

Step 4, data flow abnormal identification, the process is as follows:

Sort the results of abnormal quantification in ascending order; calculate the median value, maximum value, minimum value, and maximum deviation value of the sorted abnormal quantified values, and detect the data flow.

Compared with the prior art, the present invention has the advantages of: (1) comprehensively considering the context information of multiple data streams and the historical information of a single data stream to quantify the abnormality of the data stream, and improving the detection accuracy; The guided learning method is automatically obtained, without the need to calculate the domain knowledge of node abnormalities, which reduces the difficulty of identifying parameter settings; (3) The algorithm has a low time complexity, which has a linear growth relationship with the number n of data streams.

The present invention will be described in further detail below in conjunction with the accompanying drawings.

Description of drawings

Fig. 1 is the flow chart of a kind of context-based multi-data flow anomaly detection method of the present invention;

Fig. 2 is a schematic diagram of context and snapshot generation of multiple data streams;

Fig. 3 is a flow chart of abnormal quantification of data flow snapshot;

Fig. 4 is a flow chart of data stream anomaly detection;

detailed description

Combined with Figure 1, a context-based multi-data stream anomaly detection method includes the following steps:

Step 1, multi-stream acquisition and snapshot generation, the process is as follows:

Step 1.1, given a distributed computing system composed of n isomorphic computing nodes;

Step 1.2, synchronously record the observation value of the i-th computing node at time t in Indicates the component of the i-th computing node on the m-th observation dimension of the observed value at time t, 1≤i≤n, each component represents a node metric of interest, and the metrics of isomorphic computing nodes are exactly the same , the value of m is determined by the total number of metrics;

Step 1.3, construct the data flow S _i corresponding to computing node i = {s _i1 , s _i2 , s _i3 ,..., s _it }, S _i is an ordered but infinite data observation sequence;

Step 1.4, the data streams of n computing nodes form a data stream set S={S ₁ , S ₂ ,...S ₃ ,...S _i ,...,S _n };

Step 1.5, record the snapshot S t of the data flow set S at time ^t = [s _it |s _it ∈ S _i , S _i ∈ S, 1≤i≤n], the snapshot S ^t of the data flow set S is determined by the time t It is composed of observations obtained on each computing node; therefore, according to the definition of snapshot, the data flow set S can be expressed as a snapshot set, that is, S={S ¹ ,S ² ,...,S ^t ,... }.

Step 2, abnormal quantification of multi-stream snapshots, the process is as follows:

Step 2.1, given the snapshot S ^t at time t, construct an n×m matrix Used to describe the instantaneous behavior of each computing node at time t;

Step 2.2, for any column vector of matrix M _t 1≤d≤m, Indicates the observation value of the i-th computing node at time t, calculated by 0-1 normalization in Indicates the minimum value of the dth observation metric among n observations, Indicates the maximum value of the dth observation metric among the n observations, and then a new matrix is obtained

Step 2.3, for any column vector of matrix M _t ' compute an arbitrary column vector mean of get the bias matrix in

Step 2.4, calculate the abnormal quantitative value N _it of the data flow snapshot generated by each computing node at time t, the specific steps are:

Step 2.4.1, initialize the column vector For any observation dimension k, 1≤k≤m, calculate the square of the deviation Then the variance of the kth observation dimension at time t

Step 2.4.2, initialize the column vector used to store the abnormal quantization value of each observation dimension in Indicates the entropy of the kth observation dimension at time t, means take-and-leave variance The entropy of the kth observation dimension in the case, M _t ″(f, k) is the value of the fth row and kth column of the matrix M _t ″; therefore,

Step 2.4.3, calculate the abnormal quantitative value of the data flow snapshot of the ith computing node at time t

Step 3: Quantify data flow anomalies. Due to the common phenomenon of instantaneous fluctuations and phase transitions in data flow, identifying computing node anomalies only through data flow snapshots will lead to a high false alarm rate; in order to alleviate this problem, in the data flow On the basis of snapshot anomaly quantification, consider the collective behavior displayed in the historical data stream data to further quantify the candidate anomalous data streams, and integrate the abnormal quantification results of data stream snapshots and the influence of historical data in a single data stream on the abnormal quantification results. Generate the final anomaly quantification result, the specific process is as follows:

Step 3.1, given any data stream S _i , record all snapshot anomaly quantization values {N _i0 , N _i1 ,...,N _i(t-1) } before time t, and calculate the t snapshot anomaly quantization values For the influence I _it at the current moment t, Among them, U _t represents the influence decay function. In the present invention, an exponential decay function is selected to control the degree of influence decay, that is, U _t =e ^-λkt , where λ>0 is the decay speed threshold, so there are:

I _it ＝N _i(t-1) e ^-λ +N _i(t-2) e ^-2λ +N _i(t-1) e ^-3λ +...

=e ^-λ (N _i ( _t-1 )+e ^-λ (N _i(t-2) +e ^-λ (N _i(t-3) +...;

＝e ^-λ (N _i(t-1) +I _i(t-1) )

In step 3.2, comprehensively consider the abnormal quantization results of multiple data stream snapshots and the influence of historical data in a single data stream on the abnormal quantification results, and obtain the abnormal quantization result value N _i =N _it +I _it of the data stream S _i .

Step 4, data flow abnormal identification, the process is as follows:

Step 4.1, given the abnormal quantization result sequence N={N ₁ ,N ₂ ,...,N _n } corresponding to the data stream set S={S ₁ ,S ₂ ,...,S _n }, quantify the abnormal The result sequence N is sorted from small to large, and a new sequence N'={N' ₁ ,N' ₂ ,...,N' _n } is obtained, and the subscript mapping relationship v=R(u) is recorded, 1≤u, v≤n, indicating that the uth abnormal quantization result of the new sequence corresponds to the vth abnormal quantization result of the original sequence;

Step 4.2, set the subscript of the median value of the abnormal quantization result as mIdx, and have Calculate the median value N _median =N' _mIdx of the abnormal quantization result, the minimum value N _min =N' ₁ of the abnormal quantization result, the maximum value N _max =N' _n of the abnormal quantization result and the maximum abnormal quantization value component d _upper ;

Step 4.3, set idx=mIdx+1;

Step 4.4, if N′ _idx >max(2(N _median -N _min ),N _min +d _upper ), where max represents the function to find the maximum value of 2 numbers, when the data flow is normal, N _median -N _min It should be approximately equal to half of N _max -N _min , so if it is greater than 2(N _median -N _min ), it means that the data flow S _R(idx) is an abnormal data flow, and an abnormal alarm is generated; otherwise, the data flow S _{R(idx )} is a normal data stream;

like Indicates that in the case of data flow jitter, there is the maximum deviation value of abnormal quantization between the jitter data flow and the non-jitter data flow. When there is jitter in the data flow and the abnormal quantization result of the data flow is greater than N _min +d _upper , the data flow S _R(idx) is an abnormal data flow, which generates an abnormal alarm; otherwise, the data flow S _R(idx) is a normal data flow;

Step 4.5, if idx<n, then idx←idx+1, jump to step 4.4, otherwise, end step 4.

Comparing the data calculated by the method of the present invention with the existing Storm algorithm and the LOF algorithm, it can be concluded that the algorithm of the present invention is superior to the comparison algorithm in terms of accuracy, recall and comprehensive evaluation indicators. The experimental data comes from the monitoring data of 16 computing nodes. The observation dimension of each computing node is 10 dimensions, which are CPU usage rate, memory usage rate, memory page swapping times, memory page swapping times, Disk read times, and Disk write times. The number of times, the number of bytes read by Disk, the number of bytes written by Disk, the number of bytes received by the NIC, the number of bytes sent by the NIC, etc. In the experiment, two types of exceptions were injected, namely memory leak and CPU leak results, and the injection duration was 1000s, the experimental results are shown in Table 1.

Table 1 Comparison of experimental results of different algorithms

.

Claims (4)

1. a kind of multiple data stream method for detecting abnormality based on context, it is characterised in that comprise the following steps：

Step 1, multiple data stream is obtained and snapshot is generated, and process is as follows：

A distributed computing system being made up of the calculate node of n isomorphism is given, record moment t synchronously obtains each calculating The observation of node, according to observation the data flow of each calculate node is calculated, and all calculate nodes are remembered in the data flow of t For snapshot；

Step 2, multiple data stream snapshot quantifies extremely, and process is as follows：

The snapshot structural matrix M of moment t is used to describe the transient behavior of each calculate node of moment t；Each row to matrix M Vector calculates normalized value using 0-1 normalization mode one by one, obtains new matrix M'；Calculate each column vector after normalization Average, obtain deviation matrix M "；Calculate the abnormal quantized value of the data flow snapshot that each calculate node is produced in moment t；

Step 3, data flow anomaly quantifies, and process is as follows：

Arbitrary data flow is given, all snapshots exception quantized value before moment t is calculated for the influence power of current time t, Consider multiple data stream snapshot exception quantized result and individual traffic in historical data for the impact of abnormal quantized result Power, show that the abnormal of data flow quantifies end value；

Step 4, data flow anomaly identification, process is as follows：

Result obtained by abnormal quantization is ranked up according to mode from small to large；Calculate the middle position of abnormal quantized value after sequence Value, maximum, minimum of a value and maximum deflection difference value, and detection data stream, specially：

Step 4.1, data-oriented adfluxion S={ S₁,S₂,...,S_nCorresponding abnormal quantized result sequence N₁,N₂,...,N_n, it is right Abnormal quantized result sequence is ranked up according to mode from small to large, obtains new sequence N '₁,N'₂,...,N'_n, and record Subscript mapping relations v=R (u), 1≤u, v≤n represent the v of u-th abnormal quantized result corresponding to former sequence of new sequence Individual abnormal quantized result；

Step 4.2, if being designated as mIdx under the median of abnormal quantized result, hasCalculate abnormal quantized result Median N_median=N'_mIdx, minimum of a value N of abnormal quantized result_min=N '₁, maximum N of abnormal quantized result_max=N'_n With maximum exception quantized value component d_upper；

Step 4.3, sets idx=mIdx+1；

Step 4.4, if N '_idx＞ max (2 (N_median-N_min),N_min+d_upper), represent data flow S_R(idx)It is an abnormal data Stream, produces abnormality alarming；IfRepresent in the case of data dither flow there is shake data flow and non-jitter number According to the maximum deflection difference value quantified extremely between stream, shake when data flow is present, the abnormal quantized result of data flow is more than N_min+ d_upperWhen, then data flow S_R(idx)It is an abnormal data stream, produces abnormality alarming；

Step 4.5, if idx is ＜ n, idx=idx+1, jumps to step 4.4, and otherwise, step 4 terminates.

2. the multiple data stream method for detecting abnormality based on context according to claim 1, it is characterised in that step 1 is most Obtain and comprising the following steps that snapshot is generated according to stream：

Step 1.1, gives a distributed computing system being made up of the calculate node of n isomorphism, and each calculate node has h Identical tolerance；

Step 1.2, the observation of i-th calculate node of synchronous recording tWhereinRepresent i-th Component of the calculate node in m-th observation dimension of the observation of moment t, 1≤i≤n, 1≤m≤h；

Step 1.3, constitutes corresponding data flow S of calculate node i_i={ s_i1,s_i2,s_i3,...,s_it}；

Step 1.4, the data flow of n calculate node constitutes data adfluxion S={ S₁,S₂,...S₃,...S_i,...,S_n}；

Step 1.5, records the snapshot S of data adfluxion S of t^t=[s_it|s_it∈S_i,S_i∈S,1≤i≤n]。

3. the multiple data stream method for detecting abnormality based on context according to claim 1, it is characterised in that step 2 is most According to comprising the following steps that stream snapshot quantifies extremely：

Step 2.1, the snapshot S of given time t^t, construct n × m matrixes

Step 2.2, to matrix M_tAny column vector1≤d≤m, is calculated using 0-1 normalization modeAnd then obtain new matrix

Step 2.3, calculates any column vectorAverageObtain deviation matrixWherein

Step 2.4, calculates the abnormal quantized value N of the data flow snapshot that each calculate node is produced in moment t_it, concretely comprise the following steps：

Step 2.4.1, initializes column vectorWherein1≤k≤m, calculates k-th observation dimension Variance

Step 2.4.2, calculates the data flow snapshot exception quantized value component of each calculate nodeWherein1≤f≤n, M_t" (f, k) be matrix The value of M " f rows kth row；

Step 2.4.3, calculates the data flow snapshot exception quantized value of i-th calculate node of moment t

4. the multiple data stream method for detecting abnormality based on context according to claim 3, it is characterised in that the number of step 3 Quantify according to throat floater, step is as follows：

Step 3.1, gives arbitrary data flow S_i, record all snapshots exception quantized value { N before moment t_i0,N_i1,..., N_i(t-1), this t snapshot exception quantized value is calculated for influence power I of current time t_it,Wherein U_t =e^-λktFor influence power attenuation function, wherein λ ＞ 0 are decay speed threshold values；

Step 3.2, consider multiple data stream snapshot exception quantized result and individual traffic in historical data for abnormal amount Change the influence power of result, draw data flow S_iAbnormal quantify end value N_i=N_it+I_it。