# 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.3 Diagonal Jump Algorithm  
In this paper, the diagonal jump algorithm is adopted to avoid unnecessary cell value calculation. Different from the vertical traversal shown in Figure 6a, the edit distance matrix is updated using the diagonal traversal shown in Figure 6b.  
Figure 6 shows the process of a diagonal traversal, where the arrows illustrate the order of steps computed in each traversal. In a diagonal traversal, the upper right cell value is computed before the lower left cell value. If \(tra(t)\) is used to represent the value of a diagonal line, then \(tra(t)\) needs to be updated by \(tra(t-1)\) and \(tra(t-2)\), and there is no dependency on the unit value inside \(tra(t)\). When \(tra(t-1)\) and \(tra(t-2)\) are updated, the calculation of unnecessary unit values can be skipped when calculating \(tra(t)\). Jump bitmaps are employed, avoiding multiple iterations during the loop without accessing all elements in the edit distance matrix. Each bit in the skip bitmap is assigned to a column of the edit distance matrix. When the trim bit of the column is set to \"1\", the cell value of the column does not need to be updated in subsequent calculations. The specific steps are shown in Algorithm 3.  
The number of diagonal traversals is proportional to the pattern sequence length \(j\), so the time complexity is \(O(jk)\). Figure 7 depicts the matrix update operation of the original sequence \"catese\" and the query sequence \"catch\", with a threshold \(\tau\) of 2. First, initialize the bit of the leftmost column in the skip bitmap to \"1\" and initialize \(D[i][0]\) and \(D[0][j]\), as shown in Figure 6(a). When the fourth diagonal is updated, the cell value of the second column exceeds 2, as shown in Figure 6(c). When traversing the fifth diagonal, since \(skip\_bitmap(1)=1\), \(D[3][2]\) and \(D[3][1]\) will be used to update \(D[4][2]\), where the insert operation is skipped. Figure 6(d) shows the updated result of the final edit distance matrix. The diagonal skipping method proposed in this paper only needs to access the skip bitmap to determine which steps to skip without relying on previously updated data. In addition, the algorithm can skip the computation of multiple cell values and operations, thereby reducing the time of updating the edit distance matrix.  
Figure 6: Two traversal methods.  
Through the above algorithm, the approximate matching position of the query sequence in the fingerprint sequence can be found, and then the matching score with the fingerprint sequence can be calculated according to Equation (14). The device with the highest matching score in the device fingerprint database is the identification result.  
\[sc=\sum_{i\in match}\frac{100*|l_{i}-r_{i}|}{2} \tag{14}\]  
Among them, match represents the position where the query sequence approximately matches the fingerprint sequence. \(l_{i}\) represents the similarity between the longest extension on the left and the left side of the shard at the \(i\)th matching position. \(r_{i}\) represents the similarity between the longest extension on the right and the right side of the shard at the \(i\)th matching position.  
The device identification in this paper is based on a pattern matching algorithm, and the flow chart is shown in Figure 8. First try to use exact matching for the fingerprints in the device fingerprint database, but there is noise in the industrial control system, so the exact match often fails. In response to this situation, this paper uses the fuzzy pattern matching algorithm to further evaluate the matching degree, and the device with the highest matching degree is the recognition result.  
Figure 7: Update process of diagonal jump algorithm.