# Development of Fingerprint Identification Based on Device Flow in Industrial Control System
## 3 Device Traffic Fingerprint Extraction and Identification
### Fuzzy Matching to Identify Unknown Devices
#### 3.3.2 Similarity Function  
The most widespread way to measure the similarity of two sequences is based on the Levenstein distance, also known as the edit distance. It can achieve fault-tolerant matching of two sequences at the character level, and is also the similarity measure used in this chapter. It represents changing from one sequence to another with a minimum number of operations, including insertion, replacement, and deletion of characters. Given two sequences \(p\) and \(q\), the similarity function based on edit distance is _leven_, \(0\leq leven(p,q)\leq max(p,|q|)\). When \(leven(p,q)\leq\tau\) in the two sequences, where \(\tau\) is the allowable error value above. The edit distance can be calculated by dynamic programming, as shown in Equations (10)-(13). \[D(i,0)=i,(1\leq i\leq|p|) \tag{10}\]  
\[D(0,j)=j,(1\leq j\leq|q|) \tag{11}\]  
\[D(i,j)=\left\{ \begin{aligned} D(i,j-1)+1\\ D(i-1,j)+1\\ D(i-1,j-1)+C(p[i],s[j])\end{aligned} \right. \tag{12}\] \begin{table}
\begin{tabular}{l c c} \hline \hline \multicolumn{2}{c}{**The Uniform Sharding Strategy**} & \multicolumn{2}{c}{**The Optimal Sharding Strategy**} \\ \hline sharding & \(O(\tau)\) & \(O(|q|^{\tau})\) \\ \hline query & \(O(q)\) & \(O(q)\) \\ \hline verification & \(O(\tau|q|W_{E})\) & \(O(\tau|q|W_{B})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Time overhead of sharding strategy. \[C(x,y)= \begin{cases}1,x\
eq y\\ 0,x=y\end{cases}  \tag{13}\]  
Initially, the cell values in the first row and first column of the edit distance matrix are directly obtained by Equations (10) and (11), while other cell values can be obtained iteratively by Equations (12) and (13). For any unit on the edit distance matrix composed of sequence p and sequence \(q\), \(D(i,j)=ed(p[1,i],q[1,j])\), so their edit distances satisfy \(ed(p,q)=D(|p|,|q|)\), the time complexity of calculating the edit distance between two sequences is \(O(|p|*|q|)\). In general, successful matches between sequences are rare. The above equation calculates the value of each column from top to bottom when updating the edit distance matrix. A cell value will soon be greater than \(\tau+1\), where the surface is already mismatched. If the value of a cell is greater than \(\tau+1\), the search results will not depend on this cell. Based on the above conclusions, the algorithm can be further optimized. If the value of a cell in the edit distance matrix is less than or equal to \(\tau\), the cell is called the active cell. When updating the edit distance matrix, it only needs to calculate the last active cell of each column and stop, and the value of its cells below will not be updated. In the process of device recognition, most of the recognition sequences and pattern sequences have a low degree of matching, and the number of updated active units is small, which can improve the recognition efficiency. The reason why this optimization algorithm is established is that the cost of insertion, deletion and replacement operations are all 1, so the difference between adjacent elements in the edit distance matrix is at most 1. This also limits the scalability of the recognition algorithm. In fact, various noises such as redundancy, disorder, and presence of noise in data traffic have different effects on device identification. Simply setting all operation overheads to 1 will reduce the accuracy of identification. In this paper, the generalized edit distance is used to improve the scalability and accuracy of the algorithm, that is, the cost of each operation is not the same, and the specific value is determined by the protocol and function. Although the generalized edit distance can improve the correctness and scalability of the algorithm, it cannot be optimized in time, because the cost of each operation is not a fixed value, and the difference between adjacent unit values cannot be determined. The edit distance matrix needs to be completely updated each time to match with the device, which will waste a lot of time on meaningless calculations.