[發明專利]基于多層局部敏感哈希表的網絡流量異常快速檢測方法

有效

• 申請號: 201710001459.7
• 申請日: 2017-01-03
• 公開（公告）號: CN107070867B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 黃俊;謝鯤;陳宇翔;文吉剛
• 申請（專利權）人: 湖南大學
• 主分類號: H04L29/06
• 分類號: H04L29/06
• 代理公司: 長沙正奇專利事務所有限責任公司 43113
• 代理人: 馬強;王娟

本發明公開了一種基于多層局部敏感哈希表的網絡流量異常快速檢測方法，利用多層局部敏感哈希表，通過局部敏感哈希函數，將OD對向量進行緩沖和重排，使相似的OD對向量映射到相同的哈希桶。在多層局部敏感哈希表的基礎上，設計自適應尋找子空間方法和更新局部敏感哈希表方法，使得網絡流量異常檢測中的低秩矩陣逼近過程時間復雜度大大減少，降低異常檢測整體時間復雜度，從而實現流量異常快速檢測。

技術領域

本發明涉及計算機技術和網絡技術領域，特別是涉及網絡流量產生異常，需要快速定位異常位置的應用，具體是一種基于多層局部敏感哈希表的網絡流量異常快速檢測方法。

背景技術

近年來，隨著計算機技術的不斷發展和網絡應用的不斷深化，網絡不僅在工業、銀行、科研教育等各個領域發揮重要作用，而且早已走向千家萬戶，使得網絡在人們的日常工作和生活中扮演著越來越重要的角色。網絡規模的不斷擴大，計算機技術和網絡技術的迅速發展，網絡出現各種安全、性能問題的可能性也日益增大，而且這些問題對人們日常工作和生活的影響也越來越大。木馬、蠕蟲病毒，分布式拒絕服務攻擊以及網絡濫用、網絡設備異常等是目前互聯網安全的幾個主要威脅。如何及時發現和診斷網絡異常，維護和保證網絡系統的正常運行逐漸成為了人們關注的焦點。因此，設計適用于大規模的網絡流量異常快速檢測方法顯得十分重要。目前，有許多用于網絡流量異常檢測的方法，這些方法主要包括：

·主成分分析(Principal Component Analysis，PCA)

當L為輕微的高斯隨機噪聲時，PCA可以通過一次SVD準確地找到最優的L。但當L被嚴重破壞(即S很大)時，L的估計往往不準確，并且PCA還需要預知子空間維數r。

·魯棒主成分分析(Robust PCA，RPCA)

RPCA克服了PCA在異常檢測過程中的缺點，但是RPCA在求解低秩矩陣L和稀疏矩陣S的過程中采用了松弛技術，影響了異常檢測的精度。

·直接魯棒矩陣分解(direct robust matrix factorization，DRMF)

DRMF在求解低秩矩陣L和稀疏矩陣S的過程中沒有采用松弛技術，提高了異常檢測的精 度。DRMF被證明在視頻活動檢測中十分有效。但是，DRMF用于實際網絡異常檢測也有許多不足之處：①DRMF在求解帶噪聲流量數據的低秩成分時，用到了奇異值分解(singularvalue decomposition，SVD)，而SVD的時間代價非常高；②DRMF在精確得到低秩成分和異常成分過程中需要反復執行SVD。

發明內容

本發明所要解決的技術問題是，針對現有技術不足，提供一種基于多層局部敏感哈希表的網絡流量異常快速檢測方法。

為解決上述技術問題，本發明所采用的技術方案是：一種基于多層局部敏感哈希表的網絡流量異常快速檢測方法，包括以下步驟：

1)輸入帶噪聲流量矩陣X，初始化異常矩陣S；

2)反復迭代(2)式和(3)式，得到(2)式和(3)式的最優解：

其中，C為去噪流量數據矩陣；L為低秩逼近矩陣；e為異常矩陣S非零項的最大值；k為低秩逼近矩陣分解的最大秩；為二范數；

3)輸出低秩逼近矩陣L和異常矩陣S，即得到帶噪聲流量矩陣X的低秩逼近矩陣L和異常矩陣S，完成異常檢測。

所述2)式的求解過程包括以下步驟：

1)將2)式轉化為如下問題：