## 1 Introduction
[14] proposed a framework for multi-step attack detection by alert correlation process. The alert clustering is leveraged to reduce the number of alerts, and highlight the intrusion actions. The communication patterns are identified based on the clusters, and then the graph-based alert correlation (GAC) algorithm is applied to realize the alert correlations. In addition, the clusters will be labeled based on the vulnerabilities database, and then correlated together with IP addresses. The irrelevant intrusion actions will mix in the discovered attack scenarios due to the correlation based on IP. In this paper, the backward influence factor (BIF) algorithm is proposed aiming to overcome the problems caused by the disordered, incomplete and noisy IDS logs in a real-time manner. It is a sequence pattern mining algorithm, which is suitable for analyzing the streaming data generated online by IDS or other devices. The BIF algorithm is evaluated in the context of a multi-step attack scenario discovery task. The whole system is based on IDS alert analysis containing five phases: normalizing, intrusion action extraction, intrusion session pruning, correlation discovery, dynamic correlation graph construction. The first three phases are inherited from our previous work [15] because we want to use the data structures and concepts that have been created before. Each phase is summarized as follows:  
In the normalizing phase, it unifies the raw alerts from different types of sensors and converts them into the common data structures that can be solved by the system. After normalizing, the raw alerts are converted into alert objects (alert for short). In the intrusion action extraction phase, it groups alerts by two fields: the source IP address and the destination IP address. Then the intrusion actions are extracted based on the type field and the destination port field of alerts derived from the same group. In this phase, most redundant and repeated alerts are merged. In the intrusion session pruning phase, a long action sequence can be divided into several short sequences (intrusion sessions) by calculating the average time interval of actions. Then a pruning process begins to remove the repeat sub-patterns from the original sequence. The pruning algorithm can significantly reduce the length of the intrusion sessions without destroying the original associations of actions. In the correlation discovery phase, all the pruned sessions will be fed to the correlation discovery module according to the start time of the session. The BIF algorithm is applied to calculate the attraction levels between any two actions of the session. The influence factor (IF) values which express the attraction level will increase or decrease with the incoming data over time, then the real association relations are built. The dynamic correlation graph (DCG) is constructed based on the discovered correlations with higher IF values, the DCG links and nodes are dynamically created or destroyed with the influence factor matrix (IFM) which is the matrix maintaining all IF values and updating them in real-time. In this paper, the proposed BIF algorithm will be introduced in detail, it can be leveraged either as an optimized method for the intrusion scenario discovery task of our former work [15] or a separate intrusion pattern mining system. The proposed algorithm is based on the assumptions: the distance of two actions in a session can be used to measure the association strength of them.