# LTmatch: A Method to Abstract Pattern from Unstructured Log
## 3 Log Pattern Extraction Algorithm
### Example Procesure of the LTmatch Algorithm  
In this subsection, we will display an example to explain the whole process of the log parsing proceeding. Before feeding the logs to the log parsing algorithm, all the logs will be preprocessed by replaced the frequent signs with a special token surrounded with \"\(<\)\". Assuming there are three logs will be fed into the log parsing algorithm. The original logs and preprocessed logs are shown in the second column and the third column in Table 1.  
First, Log1 comes to the online log classification algorithm, the algorithm will search the **Log warehouse**, then it finds the Log warehouse is empty. So this piece of the log will be inserted into the log warehouse according to the _depth_ parameter in Algorithm 2. Assuming we set the _depth_ to 2. The log will be inserted to the node of \"password\". after that, the log warehouse as shown in Figure 3a.  
Second, the log2 comes, the algorithm will search the log warehouse by the first word and the second word of log2, and then it finds that the \"Failed\" node and \"password\" existed in the log warehouse. So the log2 will calculate the **word matching rate** with all the Log Clusters below the node \"password\" in turn until the result is bigger than the preset threshold. In this example, there is only one Log Cluster below the node \"password\", so Log2 will calculate the word matching rate with the LogCluster in Figure 3a. Assuming the threshold is 0.45 and the weight is 0.4, the first three words and the word \"from\" of the Log1 and Log2 match, and Log1 has eleven words, Log2 has six words. Therefore, according to Formula (3), we can calculate r(log1, log2) = 4/(0.4*11 + 0.6*6) = 0.5 \(>\) 0.45. So the two logs belong to one class. Then, the log cluster will be updated. To clearly the **Log Template Extraction Method**, we display the two logs to be updated below:  
Failed password for invalid user UserNameA from <IP> port <NUM> ssh2  
Failed password for UserNameB from <IP> port <NUM> ssh2  
If we use Algorithm 1, the template of two logs above will be the _Failed password for \(<\)\({}^{*}\)\(>\)\(<\)\({}^{*}\)\(>\)\(<\)\({}^{*}\)\(>\) from <IP> port <NUM> ssh2_. This result is because the variable is too long to make three \(<\)\({}^{*}\)\(>\) add to the template. If we use the algorithm 2, the result of template will be the _Failed password for \(<\)\(+\)\(>\) from <IP> port <NUM> ssh2_. This result will make the template more simple and reasonable. After that, the log warehouse as shown in Figure 3b.  
Third, Log3 comes to the online log classification algorithm, the algorithm will search the Log warehouse, then it finds there is not node \"Starting\" in the log warehouse. So this piece of the log will be inserted into the log warehouse by constructing the node \"Starting\" and node \"Session\". Then the log warehouse as shown in Figure 3c.  
\begin{table}
\begin{tabular}{l l l} \hline \hline
**Log Name** & **Original Logs** & **Preprocessed Logs** \\ \hline Log1 & Failed password for invalid user & Failed password for invalid user \\  & UserNameA from 121.132.1.20 & UserNameA from <IP> port \\  & port 51,469 ssh2 & <NUM> ssh2 \\ Log2 & Failed password for root from & Failed password for UserNameB \\  & 40.127.204.124 port 42488 ssh2 & from <IP> port <NUM> ssh2 \\ Log3 & Starting Session 122985 of user & Starting Session <NUM> of user \\  & UserNameB & UserNameA \\ \hline \hline \end{tabular}
\end{table}
Table 1: The Example logs to be processed.  
Following the process described above, logs are added to the log warehouse one by one. We will prove the advantages of this algorithm through experiments in the next section.