# Development of Fingerprint Identification Based on Device Flow in Industrial Control System
## 3 Device Traffic Fingerprint Extraction and Identification
### Device Fingerprint Extraction
When traversing to \(SA^{\prime}[i]\), if \(Suffix[Trav,SA^{\prime}[i]-1]\) is S model, then \(SA^{\prime}[i]-1\) is put into the end of S bucket corresponding to the \(SA^{\prime}[i]-1\). (5) It is assumed that the original LMS sequence can be written as \(R_{1},R_{2},...,R_{m}\) in sequence, where m is the number of LMS subsequences. Assuming w is the number of different LMS subsequences, \(V[1,...,m]\) can be renamed for each LMS subsequence. The naming rules are sorted lexicographically from low to high, so that when \(R_{i}<R_{j}\), \(V_{i}<V_{j}\), when \(R_{i}=R_{j}\), \(V_{i}=V_{j}\), a new pattern sequence \(Trav_{1}=V_{1}V_{2}V_{3}...V_{m}\) is generated. The lexicographical relationship of suffixes in \(Trav_{1}\) is the lexicographical relationship of LMS suffixes in \(Trav\). (6) If the same pattern exists in \(Trav_{1}\), the induction operation is performed recursively until there is no same pattern in the newly generated pattern sequence. Swap the name of the LMS subsequence with its current position in \(Trav_{1}\) to generate \(SA_{1}\). After obtaining the suffix array \(SA_{1}\) of the LMS subsequence, L suffix and S suffix are induced successively through \(SA_{1}\). The specific process is as follows:  
(1) Request an empty suffix array \(SA\) of length \(n\). (2) Determine the starting position of the S-barrel in each barrel. The number of L suffixes and S suffixes and the number of each pattern can be obtained when the suffix types are counted in Algorithm 1. According to the characteristics of the suffix array, \(SA_{1}\) can directly obtain the sorting of the original LMS suffix. Put all the LMS suffix numbers in the S bucket of the corresponding mode, and the relative order remains unchanged. (3) Determine the starting position of the L-barrel in each barrel. Traverse \(SA\) from front to back. When traversing to \(SA[i]\), if \(Suffix[Trav,SA[i]-1]\) is L model, then \(SA[i]-1\) is put into L bucket corresponding to the \(suffixA[i]-1\). (4) Re-determine the starting position of the S-barrels in each barrel. \(SA\) is traversed from back to front to ensure that each LMS suffix is properly ordered. When traversing to \(SA[i]\), if \(Suffix[Trav,SA[i]-1]\) is S model, then \(SA[i]-1\) is put into the end of S bucket corresponding to the \(suffixSA[i]-1\). So far, the linear time sorting and the naming calculation \(SA_{1}\) are completed first, and then the sorted \(SA_{1}\) induces the production of a complete suffix array \(SA\), the process of the \(SA-IS\) algorithm ends. In the subsequent identification process, a matching operation is required, and the following intermediate variables as shown in Table 2 can be recorded when running the \(SA-IS\) algorithm to improve the matching efficiency. **Theorem 1**. : _When the length of the pattern sequence is \(n\), the time complexity of the \(SA-IS\) algorithm is \(O(n)\), and the space complexity is \(O(n|logn|)\) bits._  
Proof. : Each step of the \(SA-IS\) algorithm is computed in linear time. In the worst case, it is necessary to recursively solve the same problem up to half the original size, so the time complexity formula is \(T(n)=T(n/2)+O(n)\). That is, the \(|log_{n}|\) layers are recursively \begin{table}
\begin{tabular}{c c} \hline \(f\) sequence & Sorted sequence of suffixes preceding a pattern \\ \hline \(l\) sequence & A sequence of sorted suffix first patterns \\ \hline _count_ array & The number of occurrences of each pattern if the f sequence \\ \hline _position_ array & The starting position of the occurrence of each pattern in the f sequence \\ \hline \(l2f\) array & Map the elements of the l sequence into the f sequence \\ \hline \end{tabular}
\end{table} 
Table 2: Intermediate variables. calculated, and the problem of each layer is sorted from small to large as \(2^{0},2^{1},2^{2},...,2^{|log_{n}|}\). The final time complexity is calculated by Equation (2) and the result is \(O(n)\).