# Quantitative Assessment and Grading of Hardware Trojan Threat Based on Rough Set Theory
## 4 Case Study
### Clustering Results and Optimal Cluster Selection  
We used the k-means++ algorithm [25], equidistant division (ED) [26], and EFD to select the initial clustering center. The results of our analysis of 10,000 clusterings is shown in Table 3.  
Figure 1: Threat-grading results for the 94 HTs found on Trust-hub.  
Figure 2: Instability analysis of k-means clustering results for different values of \(k\).  
The 'running time' in the table refers to the time spent executing the clustering algorithm 10,000 times with MATLAB, and was recorded using the 'tic toc' function.  
It can be seen from the table that when \(k>3\), the error proportion of both the k-means++ algorithm and the ED-based k-means is higher than 20%. Hence, when the number of clusters is high, the traditional methods demonstrate poor stability in the clustering of HT threat data. Using EFD to select the initial clustering center can reduce the number of errors to zero. When \(2\leq k\leq 9\), the number of errors is zero, and thus the clustering results are highly stable. In terms of running time, EFD-based k-means has the shortest time at of 245.99 s. Obviously, in the discretization of HT threat data, the EFD-based method is much better than the other two clustering algorithms and has ideal results with regards to both stability and operation time.  
We used the BWP index to characterize the effectiveness of clustering and determine the optimal number of clusters. For \(2\leq k\leq 9\), the BWP indices of the EFD-based clustering are as shown in Figure 3. When \(k=9\), the BWP index is the largest, which is much higher than for the other cases. This indicates that the separation between clusters and the tightness within clusters are the best. It is worth noting that, according to Figure 3, when \(k\geq 6\) the BWP index increases with the increment of \(k\). However, according to the empirical rule in [24], \(k\leq 9\). The higher \(k\) is, the better the clustering effect; however, this means that there is more detailed information on HT threats is, which is not conducive to the defender being able to prepare fast and effective countermeasures. Therefore, when discretizeing the HT threat we divided it into nine grades, as shown in Figure 1.  
The improved k-means algorithm clearly classifies the threat from high to low, and the separation degree of each level is rather high. The Effect of the five HTs with the highest threat is denial of service, and their activation mechanism is _Always On_, which is consistent  
Figure 3: Cluster Validity Analysis of the proposed method with different values of k.  
\begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline \multirow{2}{*}{**Category**} & \multicolumn{8}{c}{**Number of Errors**} & \multirow{2}{*}{**Running Time (s)**} \\ \cline{2-2} \cline{4-10}  & **K = 2** & **K = 3** & **K = 4** & **K = 5** & **K = 6** & **K = 7** & **K = 8** & **K = 9** \\ \hline k-means & 4986 & 3706 & 5840 & 6220 & 8197 & 9214 & 9497 & 9632 & 259.355 \\ \hline k-means++ & 0 & 244 & 7546 & 8204 & 7976 & 7816 & 4971 & 6229 & 303.718 \\ \hline ED-based k-means & 0 & 446 & 2974 & 3842 & 5538 & 5134 & 4984 & 5211 & 283.319 \\ \hline EFD-based k-means & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 245.997 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Comparison of the effects of four clustering methods on the number of errors and the running time.  
with the actual situation. The thirteen HTs posing the lowest threat level are all activated by physical conditions. Thus, it can be seen that the \(Effect\) and \(Activation\)\(Mechanism\) are the main factors affecting HT threat, which is consistent with the weight calculation results; the correctness of the proposed method is thus verified.