## 2 Materials and Methods
### Definitions  
The problem domain can be formalized as follows. An intrusion action \(a_{i}\in A\) consists of a group of alerts, where A denotes the set of all unique actions, and \(|\)A\(|\) denotes the size of A. An intrusion  
Figure 1: The illustration of the real intrusion sessions. S1, S2, and S3 are three intrusion sessions; A-H is intrusion actions that composed an intrusion scenario; S1 denotes the original session state; S2 is disordered and some irrelevant actions engaged; B is lost in S3; B-C in S4 is repeated due to the intrusion detection system (IDS). session which is a sequence of actions ordered by their time field, \(s_{i}^{(xy)}=\left\{a_{i1}^{(xy)},a_{i2}^{(xy)},\ldots,a_{in}^{(xy)}\right\}\) where x and y denote the two hosts from which the session is extracted. It is assumed that an intrusion action has an attraction effect on the subsequent actions, and a particular action happens due to the attractions of one or more other actions which happened in different sessions. The degree of influence can be calculated and used to measure the association strength between actions. For a given session \(s_{i}^{(xy)}=\left\{a_{i1}^{(xy)},a_{i2}^{(xy)},\ldots,a_{in}^{(xy)}\right\}\), \(a_{i1}^{(xy)}\) has a direct influence on \(a_{i2}^{(xy)}\), and indirect influence on \(a_{i3}^{(xy)}\), the degree of influence will get lower with the longer distance between \(a_{i1}^{(xy)}\) and \(a_{in}^{(xy)}\). The influence range is \(1\leq\omega\leq w\), where \(w\) is the number of actions influenced. For a given \(\omega\), if an intrusion action B falls in the influence range of A, A influents B (A attracts B) which can be denoted as \(A\mapsto B\). The algorithm will calculate the influences on the actions that fall in the influence range of specified action in the session. The influence range is shown in Figure 2.  
The influence degree of \(a_{i}\) on \(a_{j}\) can be calculated using Equation (1):  
\[F(a_{i}\mapsto a_{j})=\frac{2}{j-i+1}\quad(j>i), \tag{1}\]  
where \(a_{i}\) and \(a_{j}\) denotes the \(i\)th and jth action of the session, respectively, \(\omega\) is the influence range, and \(|\)s\(|\) denotes the length of the session. The more actions exist between two actions, the lower their influence is and the lower their association strength is. The influence of each pair of actions will update the old values recorded in the influence matrix shown in Figure 3. In the matrix, the values in a row express the attraction strengths of the particular action on other actions, and the values in a column express the attraction strengths of other actions on the particular action. With the continuous arrival of the intrusion sessions, the two actions A and B may have different influence values in different sessions, the old influence in the matrix should be updated with the new values using Equation (2):  
\[F_{o}=F_{o}+\alpha(F_{n}-F_{o})\quad(0<\alpha<1), \tag{2}\]  
Figure 3: The influence matrix. a\({}_{1}\)–a\({}_{8}\) indicates intrusion actions. The IF value of a\({}_{1}\) on a\({}_{2}\) is 0.26. Figure 2: The influence range of A and B in a session when \(\omega=3\). where \(\alpha\) indicates the refreshing rate, \(F_{o}\) denotes the original value of influence recorded in the matrix, \(F_{n}\) denotes the newly calculated influence value. Note that, the calculated \(F_{o}\) may increase or decrease. The number of sessions contains \(A\mapsto B\) can be denoted as \(f(A\mapsto B)\), and the total number of sessions in an analyzing period can be denoted as \(|S|\). The probability of \(A\mapsto B\) can be calculated using Equation (3):  
\[P(A\mapsto B)=\frac{f(A\mapsto B)}{|S|}, \tag{3}\]  
The comprehensive influence of intrusion action A on B can be calculated using Equation (4):  
\[CF(A\mapsto B)=F(A\mapsto B)\times P(A\mapsto B), \tag{4}\]  
where with Equation (4), the influence strength of A on B can be calculated based on the historical observation. For a given intrusion action A, what predictions will the algorithm make?