# 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.1 Sequence Sharding  
The sequence fragmentation is involved in fuzzy pattern matching, and different fragmentation methods will also affect the performance of the algorithm. The most common sharding method is uniform sharding, the specific process is: first determine the length of each subsequence according to the total length of the sequence and the number of shards,  
Figure 5: Basic process of fuzzy matching. and then cut evenly according to the length from the beginning of the sequence, so that the length of each subsequence is as consistent as possible. The advantage of this method is that it is fast, but there are certain shortcomings in slicing accuracy. For the query pattern sequence \(q=issaapp,\tau=2\), if the uniform sharding strategy is adopted, it will be divided into three shard sequences of \(iss,aa,pp\). For \(Trav=mississippi\), shard iss has two exact matching subsequences on Trav, shard pp has one exact matching subsequence on Trav, and shard aa has no exact matching subsequence on Trav, all of which need to be verified. However, if it is divided into \(issa,a,pp\), there is only one fragment sequence pp that exactly matches, and only needs to be verified once. **Definition 1**. : _Optimal \(k\) division: Given a fingerprint sequence \(Trav\), a query sequence \(q\) and division number \(k\), the optimal division of \(q\) is \(P_{B}\), which satisfies Equation (7). \(C(q,k)\) represents all sharding strategies that divide \(q\) into \(k\) shards. \(G(p)\) represents the set of all \(k\) shards of the sharding strategy \(P\). \(w_{s}(p)\) represents the number of shard \(p\) appearing in Trav, that is, the weight of shard \(p\)._  
\[P_{B}=\operatorname*{arg\,min}_{p\in C(q,k)}\sum_{p\in G(P)}w_{s}(p) \tag{7}\]  
Enumerating all sharding schemes can find the optimal solution, but there are \({|q|-1\choose\tau}\) strategies for dividing the query sequence \(q\) into \(\tau+1\) slices, which is extremely inefficient. It will be better to directly divide \(q\) evenly. By observing the division strategy, it can be found that if \(P=\{p_{1},p_{2},...,p_{\tau+1}\}\) is the optimal \(\tau+1\) division of \(q\), then \(P^{\prime}=\{p_{1},p_{2},...,p_{\tau}\}\) must be the optimal \(\tau\) partition of \(q[1,k]\), where \(k=|p_{1}|+|p_{2}|+...+|p_{\tau}|\). Therefore, a dynamic programming algorithm can be used to solve the optimal partition of q. In this paper, \(w[i][j]\) is used to represent the minimum weight for dividing \(q[1,j]\) into i shards. \(w[\tau+1][|q|]\) represents the optimal solution for dividing the sequence \(q\) into \(\tau+1\) slices, that is, the result. \(w[i][j]\) is initialized and updated with Equations (8) and (9). \[w[i][j]=w_{s}(q[1,j]) \tag{8}\]  
\[w[i][j]=\min_{i-1\leq k\leq j-1}w[i-1][k]+w_{s}(q[k+1,j]) \tag{9}\]  
\(w_{s}(q[k+1,j])\) can be calculated using the exact matching algorithm in Section 3.2. The time complexity of calculating \(w_{s}(q[k+1,j])\) is \(O(q[k+1,j])\), the time complexity of computing all subsequence weights of \(q\) is \(O(|q|^{3})\). This process has high time complexity and can be further optimized. After calculating the weight of \(w_{s}(q[k+1,j])\), only \(O(1)\) time complexity is needed to calculate \(w_{s}(q[i,j])\). Therefore, the suffix weight of \(q[i,j]\) can be calculated from right to left, and the time complexity of this process is \(O(j)\). At this time, the overall time complexity will be reduced to \(O(|q|^{2})\), and the time complexity of solving \(W[\tau+1][|q|]\) is \(O(|q|^{2}\tau)\). In addition, an acceleration strategy can be adopted. If \(W[i-1][k]\) and \(W[i-1][k-1]\) have the same weight, then \(W[i][j]\) does not need \(W[i-1][k]\) to be updated. Because \(w_{s}(q[k+1,j])\geq w_{s}(q[k,j])\), there is \(W[i-1][k]+w_{s}(q[k+1,j])\geq W[i-1][k-1]+w_{s}(q[k,j])\), \(W[i-1][k]\) cannot be used to obtain smaller weights. Therefore, judgment conditions can be added in the dynamic programming process.