基于MPI的AC串匹配并行算法的磁盘敏感信息扫描系统

摘要

本发明提供一种基于MPI的AC串匹配并行算法的磁盘敏感信息扫描系统，包括：S1、获得模式字符集，指定的扫描目录，文件数据分块和AC算法自动机的信息；S2、在多核处理器架构中的系统主进程建立MPI执行环境，动态查询处理器的工作状态，分配数据块给从进程实现数据敏感信息的并行查找；S3、多核处理器的从进程中并行地执行确定的有限自动机匹配算法，记录敏感信息的位置，并动态报告处理器工作状态。本发明能够通过MPI有效地利用多核处理器的计算资源，提高了AC串匹配算法执行性能，特别适合信息安全领域对大容量的计算机磁盘敏感信息进行快速扫描，以及适用于信息安全检查的防护与预警系统。

说明书

技术领域

本发明涉及数据信息安全技术领域，尤其涉及一种基于MPI的AC串匹配并行算法的磁盘敏感信息扫描系统。

背景技术

随着计算机技术的不断发展，信息技术对人们的日常生活的影响日益密切。作为信息的载体，计算机的磁盘中大量存储着国家机关、企事业单位和个人等的敏感信息，而这些信息一旦泄露或者遭到黑客的攻击，对单位和个人会造成一定程度的损失。因此，管理人员对磁盘敏感信息的定期扫描能够一定程度上预防和警告相关人员保护这些信息，以加强对敏感信息的安全防护意识。

磁盘敏感信息扫描系统是计算机安全管理人员对单位或者个人的计算机进行安全检查的一种安全防护与预警系统。该系统利用一定的计算机模式匹配算法，针对存储在磁盘中的敏感信息进行扫描，并报告在计算机的文件中存储的敏感信息的位置。磁盘敏感信息扫描系统的典型应用列举如下。

案例1，张经理是某公司的一名高管，正在与A公司进行一项商业合同的谈判；张经理把一份公司的重要的有关谈判的内部会议纪要下载到个人手提电脑中进行查阅，而阅后忘记按照保密规定删除会议纪要。在例行的安全检查中，计算机安全管理员利用磁盘敏感信息扫描系统检查张经理的手提电脑时，发现该份会议纪要，并提醒张经理，从而避免了对公司的利益造成损失。

案例2，王女士由于公司业务变化，需要离开母公司长期到外地子公司工作，王女士需要上交本人使用的公司电脑；在王女士的公司电脑中存储着王女士的个人账户信息和密码等个人敏感数据，王女士利用磁盘敏感信息扫描系统扫描了公司电脑中的个人敏感信息，并及时删除了存储在磁盘中的个人敏感信息，从而避免了个人隐私信息的泄露。

此外，2015年美国前国务卿希拉里.克林顿的“邮件门”丑闻被曝光，有关其使用私人电子邮箱，而非官方电子邮箱进行与他人的通信，可能导致美国外交情报的泄密。以上事件更加引起人们对存储在计算机中的数据信息安全的关注。

磁盘敏感信息扫描系统使用计算机的模式匹配算法进行信息的筛选。在计算机的模式匹配算法中，经典的Aho-Corasick算法是多模式串匹配算法，是Alfred V. Aho和Margaret J. Corasick于1975年提出的，因此，习惯上简称为AC算法。AC多模式串匹配算法以模式集合创建模式匹配的自动机，能够实现在线性时间内对输入的文本进行模式匹配过程。

随着计算机硬件技术的飞速发展，计算机处理器步入多核时代，磁盘存储器的容量得到了很大提升。磁盘敏感信息扫描系统主要对磁盘中存储的文件进行扫描，并报告文件包含的敏感信息的位置。由于磁盘的容量的迅速增加，存储在磁盘中的文件数量巨大。因此，快速地处理大量的文件信息是磁盘敏感信息扫描系统的关键。

当计算机进入多核处理器时代，计算机的计算能力和数据处理能力得到了很大的提高。计算机处理器的架构发生了革命性的变革。单独处理器主频的提升达到了极限，一个主要因素是处理器在主频提升之后难以解决芯片的散热问题。因此，多核架构的提出使计算机的计算性能和数据处理能力得到了巨大的提升。简单地说，一个计算机处理的任务可以被分配到两个甚至更多的处理器核心上进行并行的处理，从而加快了任务处理的速度，缩短了处理时间。随着2006年7月英特尔公司酷睿处理器的正式发布，以及随后个人电脑的多核处理器的发布，代表着多核处理器时代的来临。多核处理器相对于单核处理器的优势在于，处理器的性能提升的同时，其功耗大大降低。

计算机硬件技术的发展，对于计算机软件却提出了巨大的挑战。由于传统的计算机算法都设计在单核处理器上，难以实现在多核平台下的多任务处理方式。例如：对AC算法进行数据并行，存在的一个核心的问题是数据块边缘的匹配问题。因此，对传统的计算机算法改进，使其适应多核平台是一项艰巨的任务。

目前流行的并行程序设计的接口分为：Open Multi-Processing （OpenMP）和Message Passing Interface（MPI）。OpenMP是一种面向共享内存的多处理器并行程序接口。消息传递接口（MPI）是一种基于消息传递的并行程序接口。基于MPI的每个进程具有独立的运行空间，每个进程可以独立地执行，进程之间可以通过消息进行数据的交换。MPI不仅可以实现在共享内存的多核处理器中，而且也可以实现在分布式并行系统中。因此，MPI比OpenMP在并行程序设计上具有更大的灵活性。

发明内容

(一) 要解决的技术问题

本发明的目的是提出一种有效地解决AC算法在实现并行化的过程中所存在的数据分块的边缘匹配问题，并实现该方法在磁盘敏感信息扫描系统中。

(二) 技术方案

为了解决上述技术问题，本发明提供了一种基于MPI的AC串匹配并行算法的磁盘敏感信息扫描系统，包括：

Part1、获得模式字符集，指定的扫描目录，文件数据分块和AC算法自动机的信息；

Part2、在多核处理器架构中的系统主进程建立MPI执行环境，动态查询处理器的工作状态，分配数据块给从进程实现数据敏感信息的并行查找；

Part3、多核处理器的从进程中并行地执行确定的有限自动机匹配算法，记录敏感信息的位置，并动态报告处理器工作状态。

在Part 1中，系统初始化步骤包括：

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

第二步，计算模式字符串集合中模式字符串的最大长度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；

第七步，定义Aho-Corasick算法（AC算法）的确定的有限自动机DFA（DeterministicFinite 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队列。

在Part 2中，包括：

建立DFA自动机的过程：

S1、建立DFA自动机的根节点Root；

S2、打开模式集合文件；

S3、读取文件当前行字符串StrLine，并把文件指针移动到下一行；

S4、如果读入的字符串StrLine的长度Len_StrLine的值为0，则转到S8，否则，转到S5；

S5、StateNode_Pre代表自动机中当前状态节点的前一个状态节点，StateNode_Pre的初始值为Root；

S6、假设i为循环变量，代表字符串StrLine的第i个位置，i的取值从1至StrLine的最后一个位置，i的初值设定为1；

S61、创建新的状态节点，记为StateNode_New；

S62、获得StrLine的第i个字符的ASCII码值为Value_i，并把StateNode_Pre的ArrData[Value_i]的NextState 赋值为StateNode_New；

S63、如果i等于Len_StrLine，设定StateNode_New的FoundOut()为真，并输出字符串StrLine；

S64、将StateNode_New赋值给StateNode_Pre；

S65、i的值增加1；

S66、如果i的值小于等于Len_StrLine，转到S61，否则，转到S7；

S7、转到S3；

S8、DFA建立过程结束。

函数BlockPart()的实现过程包括：

S1、获得文件File的长度为Len_File，定义文件当前位置为CurLoc，设定初始值为0，设定数据块信息表Block_Info的N_Block的初始值等于1，初始化数据块信息表Block_Info的数据项FileName，

S2、如果Len_File小于MaxBlock，则设定数据块信息表Block_Info的N_Block=1, 设定数据块数组ArrBlock的第一个元素ArrBlock[1]的开始位置为ArrBlock[1].Begin=0，设定ArrBlock[1].End=Len_File-1，转到S5；

S3、如果(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；

S4、如果(CurLoc+MaxBlock)<Len_File并且(Len_File–CurLoc–MaxBlock)<=MaxBlock，则设定：

ArrBlock[N_Block].Begin=CurLoc，

ArrBlock[N_Block].End= Len_File -1，

S5、结束。

系统主进程为：

S1、MPI运行环境初始化，加载MPI系统函数库，MPI版本信息，系统核心处理器和硬件信息；

S2、获取计算机系统核心处理器数量N_Procs，由系统核心处理器数量设定进程编号，系统核心处理器最低数量限定为二核，核心处理器0号设定为主进程，记为Master，其它核心处理器依次设定为从进程，记为Slave，依次设定进程编号为Slave_1至Slave_(N_Procs-1)；

S3、建立DFA自动机；

S4、Master发送给每个Slave进程DFA自动机；

S5、获得当前队列头Q_File的文件File，当前队列头节点出队；

S6、函数BlockPart()对文件File进行数据块的划分；

S7、设定循环变量i，i的值从1至分块的数量N_Block，i的初始值设定为1；

S8、查询Slave进程的工作状态；

S81、如果Slave有空闲，分配ArrBlock[i]给一个空闲的Slave进行处理；

S82、接收Slave的匹配结果和当前工作状态；

S83、如果Slave无空闲，则转到S8；

S9、i的值增加1；

S10、如果i的值小于等于N_Block，转到S8，否则，转到S11；

S11、文件File匹配过程结束；

S12、如果Q_File的队列为空，则转到S13，否则，转到S5；

S13、汇总Slave的扫描文件的结果，写入结果文件；

S14、MPI结束。

在Part 3中，包括：

DFA_Execute(位置i，数据块的长度)过程：

S1、获得当前数据块的第i个位置的字符的ASCII码值，记为Value_i；

S2、设定CurState为指向DFA自动机中当前状态节点的指针；

S3、查询DFA自动机中Root的数组ArrData的下标为Value_i 的元素ArrData[Value_i]的NextState的值，并把该值赋值给CurState，如果CurState为空，则转向S8，否则，转向S4；

S4、假设j为循环变量，j的初值设定为0；

S5、获得当前数据块的第（i+j）个位置的字符的ASCII码值Value_ij；

S51、如果CurState的ArrData[Value_ij]的FoundOut()为真，则传送当前数据块编号，数据块的起始位置，数据块内位置信息（i+j）和匹配的模式字符串给Master；

S52、如果CurState的ArrData[Value_ij]的NextState为空，则转到S8；

S53、如果CurState的ArrData[Value_ij]的NextState不为空，则把NextState赋值给CurState；

S6、j的值增加1；

S7、如果i+j的值小于等于Len_Block，转到S5，否则，转到S8；

S8、过程结束。

AC_DFA()匹配过程：

S1、设定数据块的长度为Len_Block；

S2、假设i代表数据块的第i个位置，i的值变化从1至Len_Block，i的初值设定为1；

S3、函数DFA_Execute(i, Len_Block)执行在数据块的第i个位置的模式匹配过程；

S4、i的值增加1；

S5、如果i的值小于等于Len_Block，转到S3，否则，转到S6；

S6、结束过程。

Slave从进程包括：

S1、接收Master传送的DFA自动机；

S2、发送给Master本进程编号的工作状态为忙；

S3、接收Master传送的文件的数据块，并记录数据块编号；

S4、执行AC_DFA()串匹配过程；

S5、发送给Master本进程编号的工作状态为空闲。

(三) 有益效果

本发明的有益效果是：采用MPI并行计算技术实现AC串匹配算法，并对数据分块进行了合理的划分，有效地解决了并行AC串匹配算法所遇到的数据块边缘的匹配问题，实现了并行、快速扫描磁盘敏感信息。

附图说明

图1是基于MPI的AC串匹配并行算法的磁盘敏感信息扫描系统流程图。

具体实施方式

下面结合附图和实施例对本发明的实施方式作进一步详细描述。以下实施例用于说明本发明，但不能用来限制发明的范围。

实例1：AC算法数据块边缘的匹配问题。

AC算法的数据并行是把扫描的文本平均分配到N个并行的进程中进行处理。但是，该算法需要解决数据块边缘的匹配问题。假设给定的模式集合为：{de, ef}，给定的文本为：abcdefgh。数据块被划分为2个部分，即，Block_1={abcd}和Block_2={efgh}。两个数据块被分配到并行的进程Thread_1和Thread_2中执行。Thread_1中执行AC算法没有找到模式，Thread_2中执行AC算法找到了模式“ef”。显然，在数据块Block_1和Block_2的边缘的“de”被分配到两个数据块中，而这样的数据划分使得模式“de”被漏掉。因此，AC算法的数据并行存在着严重的“数据块边缘匹配”问题。

实际使用中，由于对AC算法数据块边缘的匹配问题的忽视，往往导致信息匹配的遗漏问题。而对数据分块的过小划分，又会导致AC算法数据块边缘的匹配问题的严重，而对数据分块的过大划分，则导致匹配速度的下降，从而系统性能得不到提高。因此，AC算法的并行化中，数据分块决定着AC算法的并行性能。

实例2：基于MPI的AC串匹配并行算法的磁盘敏感信息扫描系统实例。

假设模式字符串集合文件为ExamplePattern。模式字符串的最大长度MaxPattern=10。用户设定扫描磁盘的目录为UserSetDir。设定扫描文件的数据分块的最大长度MaxBlock=300。当前扫描的文件名称“mydata.txt”，文件数据块总数为N_Block=3；扫描文件遍历队列Q_File，对目录树进行按层次遍历，并把叶子节点插入Q_File队列。

系统主进程为：

MPI运行环境初始化，加载MPI系统函数库，MPI版本信息，假设系统核心处理器等于4，即N_Procs=4。Master为主进程，Slave_1，Slave_2，Slave_3为从进程。

Master打开模式文件ExamplePattern，第1行为第1个模式字符串，建立以Root为根节点的自动机DFA，然后依次读取第2行的模式字符串，并把该模式字符串插入到自动机DFA中。重复上述过程，直到把模式文件ExamplePattern的所有模式插入到DFA中。

Master发送给Slave_1，Slave_2，Slave_3进程DFA自动机。读取由UserSetDir获得的Q_File的文件mydata.txt；

调用函数BlockPart()对文件mydata.txt进行数据块的划分。

设定循环变量i, i的值从1至分块的数量N_Block，i的初始值设定为1。

查询Slave_1，Slave_2，Slave_3进程的工作状态。

如果Slave_1，Slave_2，Slave_3有空闲，分配ArrBlock[i]给一个空闲的Slave进行处理。

接收Slave_1，Slave_2，Slave_3的匹配结果和当前工作状态。

汇总Slave_1，Slave_2，Slave_3的扫描文件的结果，写入结果文件。

Master结束MPI执行过程。

以Slave_1从进程为例说明匹配过程：

接收Master传送的DFA自动机。

发送给Master，Slave_1的工作状态为忙。Master在接收到该消息后，知道Slave_1处于工作状态，因此不会分配任务给它。

接收Master传送的文件的数据块ArrBlock[i]，并记录数据块编号。

执行AC_DFA()串匹配过程。

发送消息给Master，Slave_1的工作状态为空闲，Master在接收到该消息后，知道Slave_1处于空闲状态，因此会分配新的任务给它。

采用MPI并行计算技术实现AC串匹配算法，由于多核处理器的计算资源的有效利用，能够实现并行和快速扫描磁盘敏感信息，缩短扫描的时间，提高磁盘扫描的速度。

实例3：函数BlockPart()实例。

假设文件File的长度为Len_File=100。

BlockPart()的实现过程为如下：

Len_File=100小于MaxBlock，则设定数据块信息表Block_Info的N_Block=1。这样的设计可以使得过小的文件不被分块，避免并行资源的浪费。

假设文件File的长度为Len_File=500，MaxBlock=200，MaxPattern=10。

函数BlockPart()的实现过程为：

定义文件当前位置为CurLoc=0，设定数据块信息表Block_Info的N_Block的初始值等于1，初始化数据块信息表Block_Info的数据项FileName。

在S3步骤，(CurLoc+MaxBlock)<Len_File，由此可得：(0+200)<500;

并且(Len_File–CurLoc–MaxBlock)>MaxBlock，由此可得：(500-0-200)=300>200，因此可得：

ArrBlock[N_Block].Begin=CurLoc，即，ArrBlock[1].Begin=0

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

即，ArrBlock[1].End= 0+200-1=199，

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

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

即，ArrBlock[2].Begin=(0+200-10+1)=191，

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

即，ArrBlock[2].End=0+200+10-2=208，

CurLoc= CurLoc+MaxBlock，即，CurLoc= 0+200=200

N_Block的值增加1，即N_Block =3。

转到S3；

在S3步骤，(CurLoc+MaxBlock)<Len_File，由此可得：(200+200)<500;

并且(Len_File–CurLoc–MaxBlock)>MaxBlock，由此可得：(500-200-200)=100<200，因此，第二个条件不满足。

S4、如果(CurLoc+MaxBlock)<Len_File，即，(200+200)<500,

并且(Len_File–CurLoc–MaxBlock)<=MaxBlock，即，（500-200-200）=100<=200,

则设定：

ArrBlock[N_Block].Begin=CurLoc，即，ArrBlock[3].Begin=200

ArrBlock[N_Block].End= Len_File -1，即，ArrBlock[3].End= 500 -1=499。

S5、结束。

由此可得，数据分块为：

ArrBlock[1].Begin=0

ArrBlock[1].End=199，

ArrBlock[2].Begin=191，

ArrBlock[2].End=208，

ArrBlock[3].Begin=200

ArrBlock[3].End=499。

数据分块2（ArrBlock[2]）有效地覆盖了数据分块1和3之间的边缘地带，解决了AC算法由于并行引起的数据块边缘的匹配问题。函数BlockPart()能够充分利用最大模式长度和用户指定的块的大小，动态划分数据块，避免了AC算法的重复匹配导致的多余时间开销，提高了AC算法的并行执行效率。特别是在大容量的磁盘扫描中，算法性能的显著提高可以大大缩短磁盘扫描的时间。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。