[發明專利]基于MPI的AC串匹配并行算法的磁盤敏感信息掃描系統

有效

• 申請號: 201710291208.7
• 申請日: 2017-04-28
• 公開（公告）號: CN107103253B
• 公開（公告）日: 2020-03-31
• 發明（設計）人: 劉嘉輝;馬翠平;宋大華
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于MPI的AC串匹配并行算法的磁盤敏感信息掃描系統，其特征在于，包括：

Part1、獲得模式字符集，指定的掃描目錄，文件數據分塊和Aho-Corasick算法（AC算法）自動機的信息；

Part2、在多核處理器架構中的系統主進程建立MPI執行環境，動態查詢處理器的工作狀態，分配數據塊給從進程實現數據敏感信息的并行查找；

Part3、多核處理器的從進程中并行地執行確定的有限自動機匹配算法，記錄敏感信息的位置，并動態報告處理器工作狀態；

在上述步驟Part1中，系統初始化步驟包括：

第一步，建立模式字符串集合文件；

第二步，計算模式字符串集合中模式字符串的最大長度MaxPattern；

第三步，用戶設定掃描磁盤的目錄；

第四步，設定掃描文件的數據分塊的最大長度MaxBlock，MaxBlock的值需要滿足：

MaxBlock > 3*MaxPattern 并且 MaxBlock >= 用戶設定的數值，默認值為200；

第五步，定義數據塊信息表Block_Info，包括如下數據項：

數據項1，掃描文件的名稱，記為FileName；

數據項2，掃描文件被劃分的數據塊的總數，記為N_Block；

數據項3，數據塊數組，記為ArrBlock，數組的起始下標為1，最大值為N_Block；

數據塊數組ArrBlock包含的數據項為：

數據項1，數據塊在文件中開始的位置，記為Begin，Begin的開始值設定為0；

數據項2，數據塊在文件中結束的位置，記為End；

第六步，定義數據塊i的長度，記為Len_Block，

Len_Block = ArrBlock[i].End - ArrBlock[i].Begin+1；

第七步，定義AC算法的確定的有限自動機DFA（Deterministic Finite Automaton）的狀態節點StateNode，StateNode的結構為包含256個元素的數組ArrData[256]，數組ArrData的起始下標為0，最大值為255，數組ArrData的每個元素結構包含2個數據項：

數據項1，匹配模式函數FoundOut()，如果FoundOut()為真，則該函數輸出匹配的模式字符串，函數初始值設定為假；

數據項2，指向自動機下一個狀態節點的指針NextState，NextState的初始值為空；

定義自動機的第一個狀態節點為根節點Root；

第八步，讀取當前磁盤目錄下的子文件夾和文件，并建立目錄樹，對目錄樹中不包含文件的空文件夾進行刪除，使得目錄樹中的葉子節點均為文件；目錄樹的根定義為第0層，葉子節點從第1層開始，目錄樹的深度定義為目錄樹中包含的最大層數，如果目錄樹的深度等于0，定義為目錄樹不包含任何文件；對目錄樹的按層次遍歷定義為從第1層開始，遍歷第一層的每個葉子節點，以此類推，直到目錄樹的最后一層；

定義掃描文件遍歷隊列Q_File，對目錄樹進行按層次遍歷，并把葉子節點插入Q_File隊列；

在上述步驟Part2中，包括：

建立DFA自動機的過程：

S1_part2_pro1、建立DFA自動機的根節點Root；

S2_part2_pro1、打開模式字符串集合文件；

S3_part2_pro1、讀取文件當前行字符串StrLine，并把文件指針移動到下一行；

S4_part2_pro1、如果讀入的字符串StrLine的長度Len_StrLine的值為0，則轉到S8_part2_pro1，否則，轉到S5_part2_pro1；

S5_part2_pro1、StateNode_Pre代表自動機中當前狀態節點的前一個狀態節點，StateNode_Pre的初始值為Root；

S6_part2_pro1、假設i為循環變量，代表字符串StrLine的第i個位置，i的取值從1至StrLine的最后一個位置，i的初值設定為1；

S61_part2_pro1、創建新的狀態節點，記為StateNode_New；

S62_part2_pro1、獲得StrLine的第i個字符的ASCII碼值為Value_i，并把StateNode_Pre的ArrData[Value_i]的NextState 賦值為StateNode_New；

S63_part2_pro1、如果i等于Len_StrLine，設定StateNode_New的FoundOut()為真，并輸出字符串StrLine；

S64_part2_pro1、將StateNode_New賦值給StateNode_Pre；

S65_part2_pro1、i的值增加1；

S66_part2_pro1、如果i的值小于等于Len_StrLine，轉到S61_part2_pro1，否則，轉到S7_part2_pro1；

S7_part2_pro1、轉到S3_part2_pro1；

S8_part2_pro1、DFA建立過程結束；

系統主進程為：

S1_part2_pro2、MPI運行環境初始化，加載MPI系統函數庫，MPI版本信息，系統核心處理器和硬件信息；

S2_part2_pro2、獲取計算機系統核心處理器數量N_Procs，由系統核心處理器數量設定進程編號，系統核心處理器最低數量限定為二核，核心處理器0號設定為主進程，記為Master，其它核心處理器依次設定為從進程，記為Slave，依次設定進程編號為Slave_1至Slave_(N_Procs-1)；

S3_part2_pro2、建立DFA自動機；

S4_part2_pro2、Master發送給每個Slave進程DFA自動機；

S5_part2_pro2、獲得當前隊列頭Q_File的文件File，當前隊列頭節點出隊；

S6_part2_pro2、函數BlockPart()對文件File進行數據塊的劃分；

S7_part2_pro2、設定循環變量i，i的值從1至分塊的數量N_Block，i的初始值設定為1；

S8_part2_pro2、查詢Slave進程的工作狀態；

S81_part2_pro2、如果Slave有空閑，分配ArrBlock[i]給一個空閑的Slave進行處理；

S82_part2_pro2、接收Slave的匹配結果和當前工作狀態；

S83_part2_pro2、如果Slave無空閑，則轉到S8_part2_pro2；

S9_part2_pro2、i的值增加1；

S10_part2_pro2、如果i的值小于等于N_Block，轉到S8_part2_pro2，否則，轉到S11_part2_pro2；

S11_part2_pro2、文件File匹配過程結束；

S12_part2_pro2、如果Q_File的隊列為空，則轉到S13_part2_pro2，否則，轉到S5_part2_pro2；

S13_part2_pro2、匯總Slave的掃描文件的結果，寫入結果文件；

S14_part2_pro2、MPI結束；

在上述步驟Part3中，包括：

DFA_Execute(位置i，數據塊的長度)過程：

S1_part3_pro1、獲得當前數據塊的第i個位置的字符的ASCII碼值，記為Value_i；

S2_part3_pro1、設定CurState為指向DFA自動機中當前狀態節點的指針；

S3_part3_pro1、查詢DFA自動機中Root的數組ArrData的下標為Value_i 的元素ArrData[Value_i]的NextState的值，并把該值賦值給CurState，如果CurState為空，則轉向S8_part3_pro1，否則，轉向S4_part3_pro1；

S4_part3_pro1、假設j為循環變量，j的初值設定為0；

S5_part3_pro1、獲得當前數據塊的第（i+j）個位置的字符的ASCII碼值Value_ij；

S51_part3_pro1、如果CurState的ArrData[Value_ij]的FoundOut()為真，則傳送當前數據塊編號，數據塊的起始位置，數據塊內位置信息（i+j）和匹配的模式字符串給Master；

S52_part3_pro1、如果CurState的ArrData[Value_ij]的NextState為空，則轉到S8_part3_pro1；

S53_part3_pro1、如果CurState的ArrData[Value_ij]的NextState不為空，則把NextState賦值給CurState；

S6_part3_pro1、j的值增加1；

S7_part3_pro1、如果i+j的值小于等于Len_Block，轉到S5_part3_pro1，否則，轉到S8_part3_pro1；

S8_part3_pro1、過程結束；

AC_DFA()匹配過程：

S1_part3_pro2、設定數據塊的長度為Len_Block；

S2_part3_pro2、假設i代表數據塊的第i個位置，i的值變化從1至Len_Block，i的初值設定為1；

S3_part3_pro2、函數DFA_Execute(i，Len_Block)執行在數據塊的第i個位置的模式匹配過程；

S4_part3_pro2、i的值增加1；

S5_part3_pro2、如果i的值小于等于Len_Block，轉到S3_part3_pro2，否則，轉到S6_part3_pro2；

S6_part3_pro2、AC_DFA匹配過程結束；

Slave從進程包括：

S1_part3_pro3、接收Master傳送的DFA自動機；

S2_part3_pro3、發送給Master本進程編號的工作狀態為忙；

S3_part3_pro3、接收Master傳送的文件的數據塊，并記錄數據塊編號；

S4_part3_pro3、執行AC_DFA()匹配過程；

S5_part3_pro3、發送給Master本進程編號的工作狀態為空閑；

一種基于MPI的AC串匹配并行算法的磁盤敏感信息掃描系統中，函數BlockPart()的實現過程包括：

S1_BlockPart、獲得文件File的長度為Len_File，定義文件當前位置為CurLoc，設定初始值為0，設定數據塊信息表Block_Info的N_Block的初始值等于1，初始化數據塊信息表Block_Info的數據項FileName，

S2_BlockPart、如果Len_File小于MaxBlock，則設定數據塊信息表Block_Info的N_Block=1, 設定數據塊數組ArrBlock的第一個元素ArrBlock[1]的開始位置為ArrBlock[1].Begin=0，設定ArrBlock[1].End=Len_File-1，轉到S5_BlockPart；

S3_BlockPart、如果(CurLoc+MaxBlock)<Len_File并且(Len_File–CurLoc–MaxBlock)> MaxBlock，則設定：

ArrBlock[N_Block].Begin=CurLoc，

ArrBlock[N_Block].End= CurLoc+MaxBlock-1，

N_Block的值增加1，即N_Block = N_Block+1，

ArrBlock[N_Block].Begin=(CurLoc+MaxBlock-MaxPattern+1)，

ArrBlock[N_Block].End= CurLoc+MaxBlock+ MaxPattern-2，

CurLoc=CurLoc+MaxBlock，

N_Block的值增加1，即N_Block = N_Block+1，轉到S3_BlockPart；

S4_BlockPart、如果(CurLoc+MaxBlock)<Len_File并且(Len_File–CurLoc–MaxBlock)<= MaxBlock，則設定：

ArrBlock[N_Block].Begin=CurLoc，

ArrBlock[N_Block].End= Len_File -1，

S5_BlockPart、結束。