# Combined kNN Classification and Hierarchical Similarity Hash for Fast Malware Detection
## 4 Proposed Method
### kNN Classification Method for Fast Malware Detection  
The disadvantage of similarity hash-based malware detection is its low detection rate. This means that the first nearest neighbor (1 NN) of a normal file can be a malicious file or the 1 NN of a malicious file can be a normal file. Therefore, we classify the training data into three groups in Figure 5: Normal, malicious, and undecided. In the normal group, each file is normal and its 1 NN is also normal. In the malicious group, each file is malicious and its 1 NN is also malicious. In the undecided group, if a file is normal, its 1 NN is malicious and if a file is malicious, its 1 NN is normal. The purpose of 1 NN classification is to improve the malware detection speed and increase the detection rate. Given a test file \(Q_{1}\), if its 1 NN is in the normal group, we determine that \(Q_{1}\) is normal. If the 1 NN of \(Q_{2}\) is in the malicious group, we determine that it is malicious. However, because the 1 NN of \(Q_{3}\) is in the undecided group, we cannot determine whether it is malicious. Therefore, to determine if it is malicious, we use a deep learning-based malware detection method. When the 1 NN of a test file is in the undecided group, we can increase the detection rate by using a deep learning-based method. When the 1 NN of a test file is in the normal group or malicious group, we can speed up the malware detection because we can determine whether or not the file is malicious without using a deep learning-based method. Figure 5: kNN classification for fast malware detection. The kNN classification method is composed of a training phase and a test phase. The training phase proceeds as follows. 1. We find the 1 NN of each file in the training data. 2. If a file is normal and its 1 NN is also normal, it is assigned to the normal group. If a file is malicious and its 1 NN is also malicious, it is assigned to the malicious group. Otherwise, it is assigned to the undecided group. The test phase proceeds as follows. 3. We find the 1 NN of each test file. 4. If the 1 NN is normal, we determine that the test file is normal and if the 1 NN is malicious, we determine that the test file is malicious. 5. Otherwise, we determine whether or not the test file is malicious by using the deep-learning method to be introduced in the next section. For example, in Figure 5, the training data include three normal files, \(n_{1}\), \(n_{2}\), and \(n_{3}\), and three malicious files, \(m_{1}\), \(m_{2}\), and \(m_{3}\). In the training phase, we find the 1 NN of each file, as follows. \[1\text{NN}(n_{1})=n_{2},\ 1\text{NN}(n_{2})=n_{1},\ 1\text{NN}(n_{3})=m_{3}\]  
\[1\text{NN}(m_{1})=m_{2},\ 1\text{NN}(m_{2})=m_{1},\ 1\text{NN}(m_{3})=n_{3}\]  
Then, we classify the training data into three groups, as follows. \[\text{Normal group}=\{n_{1}\,\ n_{2}\}\]  
\[\text{Malicious group}=\{m_{1}\,\ m_{2}\}\]  
\[\text{Undecided group}=\{n_{3}\,\ m_{3}\}\]  
Next, the test phase is performed. First, we find the 1 NN of each test file, as follows. \[1\text{NN}(Q_{1})=n_{2},\ 1\text{NN}(Q_{2})=m_{2},\ 1\text{NN}(Q_{3})=m_{3}\]  
Second, we determine which group each test file is assigned to, as follows. \[1\text{NN}(Q_{1})\ \subset\ \text{Normal group},\ 1\text{NN}(Q_{2})\ \text{Malicious group},\ 1\text{NN}(Q_{3})\ \subset\ \text{Undecided group}\]  
Finally, because the 1 NN of \(Q_{1}\) is in the normal group, \(Q_{1}\) is normal, and because the 1 NN of \(Q_{2}\) is in the malicious group, \(Q_{2}\) is malicious. However, because the 1 NN of \(Q_{3}\) is in the undecided group, we must determine whether it is malicious by using a deep learning-based detection method. Therefore, if the 1 NN of each test file is in the normal group or malicious group, we can quickly determine whether or not it is malicious using only the kNN classification. In addition, when the 1 NN of each test file is in the undecided group, we can increase the detection rate because we determine whether it is malicious by using the deep learning-based method.