# Fine-Grained High-Utility Dynamic Fingerprinting Extraction for Network Traffic Analysis
## 4 Fine-Grained High-Utility Dynamic Fingerprinting Extraction
### Constructing N-gram Huf-Tree of Huf Algorithm
\[\text{The confidence degree of the candidate }k\text{-item set }FIS^{k}=\left(FI^{k}_{1},FI^{k}_{2}, \cdots,FI^{k}_{l}\right)\text{ is calculated and pruned to remove the item set that does not meet the confidence degree.
3. Repeat the above steps to generate a new item set until there is only one item in the item set, then stop the loop.  
One of the most important features of network data flow is the continuous generation of data packets, which is an incremental process. Many existing kinds of literature carry outfeature extraction on static datasets after obtaining datasets, and these methods obviously cannot realize the online dynamic processing and analysis of data packets. Dynamic analysis can extract new features in time and monitor network data in real-time, so the method proposed in this paper can extract features dynamically. Above, the communication process between the client and server is extracted by establishing a sequential transaction database of data flow. In this section, the method of processing dynamic data flow by constructing the Huf-Tree is mainly proposed. A threshold \(\varepsilon\) is first set to determine whether to retain a candidate, as defined below.  
The minimum threshold of average utility determines whether to join the Huf-Tree, which is expressed in proportion:  
\[mau=\frac{\varepsilon\times SDU}{TID} \tag{19}\]  
Assuming that the threshold \"\(\varepsilon\) = 50%\" is selected, Table 6 is used as an example:  
\[mau=\frac{\varepsilon\times SDU}{TID}=\frac{1}{8}\times 50\%\times(0+0+0+0.212+0.2 54+0.236+0.236+0.236+0.288+0.821)=0.157\]  
The target data to be processed in this paper are network data flow, which can be regarded as an incremental process \(InP=(SDB_{1},SDB_{2},\cdots,SDB_{n},\cdots)\). The process of constructing the Huf-Tree is shown in Figure 8.  
The process shown in Figure 8 is the process of generating an application fingerprint, high-utility sequence, which can be divided into four phases:  
* The data are preprocessed and the incremental representation \(InP=(SDB_{1},SDB_{2},\cdots,SDB_{n},\cdots)\) of data flow is generated;
* The initial Huf-Tree is built, which takes \(SDB_{1}\) as the initial database;
* When a new \(SDB_{n}\) is generated, each item is gradually added to update the Huf-Tree;
* New application fingerprints are generated based on the threshold at intervals. The utility list is used to store the data related to the Huf-Tree. In essence, it is an array used to retrieve fingerprint \(s=<p_{1},p_{2},\cdots,p_{n}>\). The construction process of Huf-Tree is briefly introduced according to Table 7.  
Figure 8: The construction of Huf-Tree. 2. Add each application fingerprint step by step. If there are duplicate fingerprints, some paths need to be merged, as shown in Figure 10. \begin{table}
\begin{tabular}{c c c c} \hline Item & Utility & Sum & Link \\ \hline
11:01 & 0 & 1 & - \\
11:02 & 0 & 7 & - \\
11:03 & 0 & 1 & - \\
11:03 & 0.212 & 1 & - \\
23:2 & 0.254 & 1 & - \\
23:3 & 0.236 & 1 & - \\
23:5 & 0.236 & 1 & - \\
23:8 & 0.236 & 1 & - \\
23:10 & 0.288 & 1 & - \\
23:12 & 0.236 & - \\
24: & 0.821 & - \\ \hline \end{tabular}
\end{table} 
Table 7: Utility list. Figure 10: _Cont._  
Figure 9: Huf-Tree. 3. Every once in a while, according to the preset threshold, the application fingerprint that meets the condition is extracted and the messages need to be sorted, as shown in Table 8:  
Based on the transaction database information shown in Table 8, find the paths where 24: is located: <23:3, 23:5, 23:8, 11:02, 23:10, 11:02, 21:; 24:->, <11:02, 24:-, 24:-, 11:02, 24:-, 24:->, and<21:, 11:02, 24:-, 11:02, 24:-, 24:->. Then, calculate the average utility for each path, 0.249, 0.154, and 0.479, and keep <23:3, 23:5, 23:8, 11:02, 21:-, 24:-> and <21:, 11:02, 23:-, 11:02, 24:-, 11:02, 24:->. It can be seen from Figure 10d that the structure of the Huf-Tree is very complex, which is only a Huf-Tree of a small section of the data stream.