[發明專利]一種基于DCG的圖索引遷移方法及裝置

在審

• 申請號: 202310306279.5
• 申請日: 2023-03-27
• 公開（公告）號: CN116204532A
• 公開（公告）日: 2023-06-02
• 發明（設計）人: 王新根;楊運平;陳偉;魯萍;王剛
• 申請（專利權）人: 浙江邦盛科技股份有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/901;G06F16/23;G06F16/21
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 劉靜

本發明公開了一種基于DCG的圖索引遷移方法及裝置，DCG是動態圖模式匹配算法中一種用于構建索引的方法，索引遷移能將原DCG中的有效索引遷移到查詢圖對應的DCG中，丟棄無效索引。基于DCG的圖索引遷移方法主要分為以下四個部分：查詢樹的生成、匹配順序的確定、構建索引、調整查詢樹并遷移索引。本發明提出的方法主要應用在網絡安全APT攻擊模式識別場景下，并且可以在初始數據較少的情況下使用，因此該方法能長時間的保證其有效性，保證毫秒級的返回結果，節省大量的存儲空間。

技術領域

本發明涉及流式圖數據處理領域，尤其設計一種基于DCG的圖索引遷移方法及裝置。

背景技術

圖模式匹配技術解決的問題是：給定一張模式圖，要求在一張數據圖中找出所有能夠滿足模式圖約束的子圖。早期的圖模式匹配算法僅能夠用在靜態數據圖上，即數據圖的結構和內容都不會隨時間發生改變。

然而，隨著信息科技的快速發展，涉及日常生活各方面的移動應用層出不窮，這些應用持續產生大量的數據。隨著時間流逝，使用這些數據構造的圖在不斷發生變化。在當前一些應用領域中，圖模式匹配算法為了保證圖匹配結果的實時性和有效性，需要在圖的結構和內容都不斷變化的同時，快速給出匹配結果。如何處理不斷變化的圖，并且在較低延時內給出準確匹配結果，是當前研究熱點。

動態圖模式匹配技術是當前用于分析動態圖變化的重要技術,它解決如下問題：給定一張模式圖，在一張動態變化的數據圖中，對每一次數據圖插入，能實時找出和模式圖匹配的新增子圖；對每一次數據圖刪除，能實時找出和模式圖匹配的被刪除子圖。相比于傳統方法，動態圖模式匹配技術更適用于對實時性要求較高的場景。例如在推薦系統中，用戶在瀏覽過一些內容后，應用通常需要根據用戶當前瀏覽內容和之前的瀏覽內容來快速給出推薦內容；在網絡安全檢測領域中，面對不斷新增的訪問請求，算法要能快速且準確地識別出一條新請求是否可能是惡意攻擊，從而快速判斷是否需要攔截訪問。此外，在工業界中，一些大型企業也推出了自己的分布式并行圖處理系統來解決大型動態圖匹配問題。

在網絡安全APT攻擊模式識別里，一些傳統經典的攻擊模式會首先被抽象建模成模式圖的形式，然后針對線上實時接收網絡數據包數據進行解析，從而進行實時的動態圖模式匹配。

DCG(Data-Centric?Graph，數據中心圖)是一種解決動態圖模式匹配問題的算法中的構建索引的方法。其具體定義如下——

DCG(Data-Centric?Graph，數據中心圖)是一個多重圖，在多重圖中，兩個點之間可以存在多條邊。假設存在一張數據圖G＝(V,E,L)、一張模式圖Q＝(V,E,L)以及一張數據中心圖D＝(V,E,L)，D還需要滿足以下條件:

(1)要求v∈VG

(2)要求L(e)∈ID(V)且Type(e)∈{Null,Implicit,Explicit}

(3)要求且v1＝v3,v2＝v4

在上面的第二個條件中，lD(VQ)表示模式圖中所有節點的ID，Type(e)表示數據中心圖的邊對應類型，每一條邊都是上述三種類型中的某一種。

路徑:給定一張圖G＝(V,E,L)，如果從圖中某一個節點v開始遍歷，在經過有限次遍歷后能到達另一個節點v`，則這兩個節點之間的路徑〈v,...,v`〉記為v→v`。此外，如果該路徑的長度大于2，則路徑〈v,...,vp,v`〉還可以記為v→vp.v`。

DCG中邊類型的定義:給定一張數據圖G、一張模式圖Q和一張數據中心圖D，在模式圖轉換為一顆樹之后，將該模式樹的根節點記為us，將數據圖中能和us相匹配的節點記為vs。對于D中的一條邊e＝(v,v`,ID(u`))，判斷以下兩個條件:

(1)該路徑能夠匹配和模式圖中的一條路徑us→Parent(u).u`相匹配