面向网络安全的多维正则表达式匹配算法分析

王晓雨

（荆楚理工学院信息管理与信息系统教研室，荆门 448000）

近年来，全球信息化进程不断推进，计算机技术也得到了飞速发展，互联网如今已是人们生活中不可缺少的存在。相关研究资料显示，我国网民规模数量已经高达7.56亿左右。但是，在各国网络覆盖规模不断扩大的背景下，很多现实企业纷纷看到了互联网的各种优势，将现实中的业务一步步的转移到网络世界里。部分企业和银行以及政府机关组织奖互联网作为重点基础建设项目。而网络购物，网络社交，电子商务等各种行业都在逐步扩大普及，有研究资料统计，2017年，我国网络购物用户多达4.12亿，电子商务交易规模数量高达12.26亿。但是，网络是把双刃剑。计算机网络的开放性也使得其受侵方式也逐渐增多，网络安全问题层出不穷。随着网络黑客攻击事件的数量呈现逐年上升发展趋势，攻击行为也出现诸多新花样。根据数据研究资料统计显示，截止到2017年为止，我国有近6亿网民遭遇过信息安全事件，国内知名网站的几百万用户信息遭到黑客攻击，个人信息被大量窃取。

1 网络安全发展现状以及正则匹配表达式算法的由来

网络安全问题不仅仅会影响到人们正常使用计算机，正常使用互联网，而且会给社会，国家，政府造成不小的麻烦。比如，2017年，伊朗的核电站被网络病毒侵入，在启用后连续发生故障，导致放射性物质被泄露，五分之一的离心机报废。在此之后，该病毒在全世界范围内开始扩散，之后震网病毒开始感染全世界58%左右网民的电脑，在多个行业中均带来巨大冲击。斯诺登引爆的棱镜门事件将网络安全问题提高到国家战略层面上来，在全世界各个国家均高度重视网络安全建设的历史条件下，我国成立了网络信息安全小组，由习近平同志担任小组组长。习近平同志明确提出：“没有网络安全就谈不上国家安全”。基于此，加强网络的安全成为人们现阶段最为广泛关注的课题之一，安全业务也已经成为各大研究者的关注重点之一。目前最为广泛熟知的网络安全防护及时有：其一，防火墙；其二，入侵检测系统。防火墙能够简单构成一道计算机防护工序，但是若病毒绕过防火墙，对计算机内部进行强烈攻击，计算机将毫无还手之力。入侵检测系统相对于防火墙而言，是一种更为主动地防护手段。入侵检测系统是针对防火墙技术的高度补充，入侵检测系统虽然能够需要分布在网络中的各个关键点，在不影响网络正常运行，网络正常使用的情况下能够实时监控网络流量，能够针对网络攻击，提供相应保护措施。入侵检测系统有两种检测技术：异常检测方法与误用检测方法，异常检测方法又包含：（1）基于贝叶斯推理检测法：能够在任何给定的时间内，测量变量值，从而推断是否发生网络入侵事件；（2）基于特征选择检测法：能够从一组度量中挑选能够用于检测网络侵入的度量，从而预测网络入侵行为或是将网络侵入进行分类；（3）基于贝叶斯网络检测法：使用图形表现随机变量与随机变量之间的关系，通过指定的或是与邻接节点有关的一个概率集计算变量患者联接概率分布情况，为其他变量提供计算框架图；（4）基于模式预测的检测法：能够通过事件序列，并遵照某种能够辨别网络侵入的模式进行检测，能够考虑到事件序列与事件的相关联系，能够检出小范围发生的网络入侵现象；除此之外，还有基于统计的异常检测法，基于机器学习检测法，数据挖掘检测法，基于应用模式的异常检测法，基于文本分类的异常检测法。误用检测方法又含有模式匹配法，专家系统法及基于状态转移分析的检测法。通过这些检测方法能够检测出大部分的网络入侵，能够提高网络安全性。

随着网络入侵方式的多样化发展，网络的防范措施也逐渐多样化。我国越发重视网络安全这一块，网络安全维护技术也不断发展完善。但是现在基于字符串特征的提出方式变得越来越具有难度。正则表达式由于具备超强的描述能力而成为新一代的描述语言，采用正则表达式方法来描述通常可以显示无限个字符串。

正则表达式匹配技术如今在网络安全系统中应用，能够充分的发挥其价值。尤其是在商业领域中，Cisco网络安全系统已经普及使用正则表达式匹配技术。以Snort入侵检测系统为例，正则表达式匹配技术已经成为全世界各个国家安全行业的入侵检测系统代名词，所表现出的特征语法成为行业金标准。

2 简要分析正则表达式匹配算法

模式匹配有四种模式，精确串匹配；扩展串匹配；近似串匹配以及正则表达式匹配。但从现阶段来看，则能够发现，四种模式匹配法在网络安全领域中应用最广的只有正则表达式匹配，正则表达式匹配拥有非常强大的描述能力，因此在不断取代精确率匹配的地位。正则表达式匹配被广泛应用在商业入侵检测系统的规则描述之中。正则表达式最早由神经生理学家所提出，后来由数学家正式提出正则表达式概念。正则表达式目前在语法分析，文本检索中应用较多，也可以说是计算机领域中应用较多，比较重要的网络安全防御工具之一了。正则表达式又被称为规则表达式，是计算机学的一个概念，其许多程序设计语言都支持利用正则表达式进行字符串操作。同时，正则表达式也是一种对字符串操作的逻辑公式，就是通过一些特定的字符，与组合的特定字符，组成一个比较骨折的字符串，从而利用字符串表达对字符串的一种过滤逻辑。正则表达式的表达方式有表达式描述方式和有限自动机描述方式，不同语言描述方式在不同的场合中有不同的作用。从自动机理论研究来看，正则表达式与有限自动机是等价的。有限自动机是正则语言的具体描述形式，正则表达式是代数的描述形式，适合在计算机上应用的描述形式。但是正则表达式通常是使用有限性，确定性自动机与非确定性有限自动机来加以实现。简而言之，正则表达式较为直观明了，符合人类的基本思维习惯。

有学者提出，将正则表达式分组进行处理，按照联合编译后会不会出现包扎行为从而进行分组（将不发生爆炸的正则表达式分为一组，将发生爆炸的正则表达式分为一组）。还有学者提出将正则表达式联合编译时出现的爆炸情况进行量化处理分析。通过SI-DFA算法，分析爆炸发生时，爆炸发生前，爆炸发生后的各个特征，并使用正则表达式将结果转化为分子表达式，并得出DFA，最终有效减少联合编译时DFA爆炸情况的发生。