# Combined kNN Classification and Hierarchical Similarity Hash for Fast Malware Detection
## 1 Introduction  
Every day, hundreds of thousands of new malicious files are created. [1] Existing pattern-based antivirus solutions have difficulty detecting these new malicious files because they do not contain patterns [2]. To solve these problems, artificial intelligence (AI)-based malware detection methods have been investigated [2; 3; 4; 5; 6; 7; 8; 9]. AI-based malware detection consists of two phases. In the first phase, features are extracted from malicious files; in the second phase, a deep-learning model is trained using training data and tested using test data. Two methods are used to extract features from malicious files. The first is a static method that extracts opcodes from malicious files [3; 4]. The second is a dynamic method that obtains application program interface (API) system-call sequences by running the malicious files in a sandbox [5; 6; 7]. Deep-learning models for malware detection include a convolutional neural network (CNN)-based model, a long short-term memory (LSTM)-based model, and a model using a CNN and LSTM together [9; 10]. Deep-learning models have a high detection rate for malware detection. However, it takes a long time to determine whether or not files are malicious. Other studies have investigated detecting malicious files using a similarity hash [7; 11; 12]. Trend Micro proposed Trend Micro locality-sensitive hashing (TLSH), which is a type of similarity hash. If a bit is changed in a file, its cryptographic hash, e.g., MD5, is completely different from the original hash. However, its similarity hash is quite similar to the original. Thus, when two similarity hashes are similar, the two files are similar. Similarity hash-based malware detection is faster than deep learning-based malware detection. However, its detection rate is lower. In this paper, we propose two methods to solve these problems, as shown in Figure 1: k-nearest-neighbor (kNN) classification for malware detection and a vantage point (VP) tree using a similarity hash. First, using kNN classification for malware detection, we classify the training data into three groups, as follows. {Normal group, malicious group, undecided group}  
kNN classification is used for malware detection to increase the detection rate of similarity hash-based malware detection and increase the speed of deep learning-based malware detection. In the normal group, each file and its kNN are normal files. In the malicious group, each file and its kNN are malicious files. The remaining files are in the undecided group. Thus, if a file in the undecided group is a normal file, its kNN is a malicious file, and if a file in the undecided group is a malicious file, its kNN is a normal file. If the kNN of a new file is in the normal group, we can determine that it is a normal file. If its kNN is in the malicious group, we can determine that it is a malicious file by using a similarity hash. However, if its kNN is in the undecided group, we should determine whether or not the new file is malicious by using deep learning-based malware detection. When a new file's kNN is in the normal group or the malicious group, we can determine its type using only a similarity hash. Thus, we can reduce the malware-detection time compared to using only the deep learning-based method. Meanwhile, when a new file's kNN is in the undecided group, we determine it using a deep learning-based model. Therefore, we can increase the detection rate compared to using only a similarity hash. The second proposed method is a VP tree using a similarity hash. Even if similarity hash-based detection is faster than a deep learning-based method, it still takes a long time for many malicious files. At present, there are about 1 billion malicious files. [1] Therefore, we need to increase the speed of similarity-hash searches. Using a VP tree can accomplish this. The proposed system works as follows. If training files are given, we compute similarity hashes, e.g., TLSH. Then, we generate a VP tree using the similarity hash and conduct a kNN classification.