python_mmdt:從1到2--實作基于KNN的機器學*惡意代碼分類器(三)

機器學習是人工智能的一個分支。人工智能的研究曆史有着一條從以“推理”為重點，到以“知識”為重點，再到以“學習”為重點的自然、清晰的脈絡。顯然，機器學習是實作人工智能的一個途徑，即以機器學習為手段解決人工智能中的問題。機器學習在近30多年已發展為一門多領域交叉學科，涉及機率論、統計學、逼近論、凸分析、計算複雜性理論等多門學科。機器學習理論主要是設計和分析一些讓計算機可以自動“學習”的算法。機器學習算法是一類從資料中自動分析獲得規律，并利用規律對未知資料進行預測的算法。

概述

• python_mmdt:一種基于敏感哈希生成特征向量的python庫(一)我們介紹了一種叫

  mmdthash

  （敏感哈希）生成方法，并對其中的概念做了基本介紹。
• python_mmdt:從0到1--實作簡單惡意代碼分類器(二)我們介紹了基于

  mmdthash

  的一種簡單惡意代碼分類器應用。
• 本篇，我們介紹一種基于

  mmdthash

  的機器學*算法應用--KNN（最鄰*）分類算法

基本概念

首先，我們一起簡單回顧三個基本概念。

什麼是機器學*？

機器學*是人工智能的一個分支。人工智能的研究曆史有着一條從以“推理”為重點，到以“知識”為重點，再到以“學*”為重點的自然、清晰的脈絡。顯然，機器學*是實作人工智能的一個途徑，即以機器學*為手段解決人工智能中的問題。機器學*在*30多年已發展為一門多領域交叉學科，涉及機率論、統計學、逼*論、凸分析、計算複雜性理論等多門學科。機器學*理論主要是設計和分析一些讓計算機可以自動“學*”的算法。機器學*算法是一類從資料中自動分析獲得規律，并利用規律對未知資料進行預測的算法。-- wikipedia

如上所訴，機器學*的本質是一種算法，這種算法由資料分析*得。當資料量充足時，機器學*方法所能得到的結果，可無限逼*于事物的本質面貌。

什麼是監督學*？

監督學*（英語：Supervised learning），又叫有監督學*，監督式學*，是機器學*的一種方法，可以由訓練資料中學到或建立一個模式（函數/learning model），并依此模式推測新的執行個體。訓練資料是由輸入物件（通常是向量）和預期輸出所組成。函數的輸出可以是一個連續的值（稱為回歸分析），或是預測一個分類标簽（稱作分類）。-- wikipedia

如上所訴，監督學*有三要素：（特征向量訓練集，算法/模型，預測）。通過機器學*算法分析處理有标簽的訓練集，生成模型，利用模型處理無标簽資料，輸出預測結果。

什麼是k-NN？

最*鄰居法（k-NN算法，又譯K-*鄰算法）是一種用于分類和回歸的非參數統計方法。在這兩種情況下，輸入包含特征空間（Feature Space）中的k個最接*的訓練樣本。

• 在k-NN分類中，輸出是一個分類族群。一個對象的分類是由其鄰居的“多數表決”确定的，k個最*鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類别。若k=1，則該對象的類别直接由最*的一個節點賦予。
• 在k-NN回歸中，輸出是該對象的屬性值。該值是其k個最*鄰居的值的平均值。

最*鄰居法采用向量空間模型來分類，概念為相同類别的案例，彼此的相似度高，而可以借由計算與已知類别案例之相似度，來評估未知類别案例可能的分類。-- wikipedia

如上所訴，k-NN算法的核心思想是：一個樣本與資料集中的k個樣本最相似，如果這k個樣本中的大多數屬于某一個類别，則該樣本也屬于這個類别。

場景比對

結合上文介紹，要在惡意代碼檢測場景中應用機器學*，至少需要準備兩樣東西：

• 1.有标簽的訓練集
• 2.算法/模型

1. 有标簽的訓練集

利用

python_mmdt

工具，我們處理一批已知标簽的樣本，生成對應的

mmdt_hash

值，

mmdt_hash

的每一個位元組都是特征向量的一個次元。将這些值儲存下來，既可作為

有标簽的訓練集

。（

mmdt_hash

的詳細介紹，見之前兩篇文章）

2. 算法/模型

提到機器學*，自然而然地會讓人想到k-NN算法。k-NN算法具有明确的目标，清晰的流程，可讀的結果，幾乎可以認為是最簡單有效的機器學*算法。k-NN算法通過計算兩個特征向量之間的距離，評估兩個特征向量之間的關聯：距離越小，關聯越大；距離越大，關聯越小。

3.應用

容易得出，

mmdt_hash

+ k-NN = machine_learning，

mmdt_hash

結合k-NN算法可作為某種機器學*應用。

k-NN算法

1. 算法原理

k-NN核心思想：一個樣本與資料集中的k個樣本最相似，如果這k個樣本中的大多數屬于某一個類别，則該樣本也屬于這個類别。其中，通過距離來衡量相似度，距離越小，相似度越高；距離越大，相似度越低。而距離的度量，通常采用歐式距離。

2. 算法流程

k-NN算法流程如下：

1. 計算未知特征向量與訓練集中每個特征向量的距離
2. 對距離的按遠*排序
3. 選取與目前未知特征向量最*的k的已知特征向量，作為該未知特征向量的鄰居
4. 統計這k個鄰居的類别頻率
5. k個鄰居裡頻率最高的類别，即為未知特征向量的類别

基于k-NN的惡意代碼檢測實作

1.特征向量集生成

關鍵點兩個：

1. 将已有的特征庫轉成knn需要的特征向量集形式
2. 儲存knn特征向量集和對應标簽索引集

...

def gen_knn_features(self):
    data_list = []
    label_list = []
    # self.datas是已知特征庫
    for data in self.datas:
        tmp = data.split(':')
        main_hash = tmp[1]
        main_values = []
        # 将字元串類型的mmdt_hash轉成單條特征向量
        for i in range(0, len(main_hash), 2):
            main_values.append(int(main_hash[i:i+2], 16))
        # 儲存knn需要的特征向量及标簽索引
        data_list.append(main_values)
        label_list.append(int(tmp[2]))
    
    return data_list, label_list
...
           

2.k-NN算法實作(python版)

...

def knn_classify(self, md, dlt):
    # 将mmdt_hash轉為特征向量
    def gen_knn_data(data):
        tmp = data.split(':')
        main_hash = tmp[1]
        main_values = []
        for i in range(0, len(main_hash), 2):
            main_values.append(int(main_hash[i:i+2], 16))

        return main_values
    
    # 儲存knn訓練集和對應索引标簽集
    datas = self.build_datas
    labels = self.build_labels
    
    train_datas = np.array(datas)
    t_data = gen_knn_data(md)
    rowSize = train_datas.shape[0]
    # 1.擴充未知特征标簽次元，同時分别計算與knn特征向量集合的每個次元的內插補點，先平方求和再開方，即為歐式距離
    diff = np.tile(t_data, (rowSize, 1)) - train_datas
    sqr_diff = diff ** 2
    sqr_diff_sum = sqr_diff.sum(axis=1)
    distances = sqr_diff_sum ** 0.5
    # 2. 對距離排序
    sort_distance = distances.argsort()
    
    # 3. 使用最*一個鄰居
    matched = sort_distance[0]

    # 4. 使用最*一個鄰居的标簽作為判定标簽
    label_index = labels[matched]
    sim = 1.0 - distances[matched]/1020.0
    # 5. 判定相似度是否滿足指定條件
    if sim > dlt:
        if self.labels:
            label = self.labels[label_index]
        else:
            label = 'match_%d' % label_index
        return sim, label
    return 0.0, 'unknown'
...
           

使用幫助

➜ mmdt-classify -h
usage: python_mmdt malicious file scan tool [-h] [-s SCANS] [-t THRESHOLD]
                                            [-c CLASSIFY_TYPE]

A malicious scanner tool based on mmdt_hash. Version 0.2.1

optional arguments:
  -h, --help            show this help message and exit
  -s SCANS, --scans SCANS
                        set file/path to scan.
  -t THRESHOLD, --threshold THRESHOLD
                        set threshold value to determine whether the file is a
                        malicious file. (default 0.95)
  -c CLASSIFY_TYPE, --classify CLASSIFY_TYPE
                        set classify type.set 1 for simple classify, set 2 for
                        knn classify.(default 1)

Use like:
    1. use simple classify
    mmdt-classify -s $sample_path -t 0.95 -c 1
    2. use knn classify
    mmdt-classify -s $sample_path -t 0.95 -c 2

           

效果截圖