(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(10)申请公布号 CN 104407849 A
(43)申请公布日 2015.03.11
(21)申请号 CN201410599232.3
(22)申请日 2014.10.31
(71)申请人 福建六壬网安股份有限公司
    地址 350012 福建省福州市秀峰路188号闽台AD创意园4幢3层
(72)发明人 王琦 刘坤朋 张木连 张冬青
(74)专利代理机构 福州元创专利商标代理有限公司
    代理人 蔡学俊
(51)Int.CI
      G06F9/44
      G06F21/55
                                                                  权利要求说明书 说明书 幅图
(54)发明名称
      一种带通配符正则表达式的有穷自动机生成方法
(57)摘要
      本发明涉及一种带通配符正则表达式的有穷自动机生成方法，其特征在于，按照如下步骤实现：S1：根据带通配符正则表达式生成抽象语法树，并对该抽象语法树的每个节点编号；S2：根据抽象语法树计算每个节点的nullable(n)和每个节点的三个位置集合；S3：将抽象语法树根节点的firstpos（n0）作为第一个状态，存储到到状态集合中；遍历状态集合，若在遍历过程中产生新的状态，则将新的状态加入到状态集合中，记录转换关系；在遍历每个状态时，计算该状态中的每个字符的跟随状态，并根据条件存放到状态集合中。本发明所提出的一种带通配符正则表达式的有穷自动机生成方法，有效的提高了编译的效率，降低了对内存的消耗。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种带通配符正则表达式的有穷自动机生成方法，其特征在于，按照如下步骤实现：       
正则匹配空字符
S1：根据带通配符正则表达式生成抽象语法树（T），并对该抽象语法树（T）的每个节点编号；       
S2：根据步骤S1中所生成的所述抽象语法树（T）计算每个节点的nullable(n)和每个节点的三个位置集合；其中，nullable(n)表示节点n代表的子表达式是否可以为空；三个位置集合分别表示为：firstpos(n)、lastpos(n)和followpos(p)，且firstpos(n)表示节点n代表的子树的开始字符的位置集合，lastpost(n) 表示节点n代表的子树的结束字符的位置集合，followpos(p)表示节点p之后的可以跟随的节点的位置集合；       
S3：根据步骤S1和步骤S2中得到的结果，生成有穷自动机（DFA），并将输出的有穷自动机（DFA）表示
为D；将所述抽象语法树（T）根节点的firstpos(n0)作为第一个状态，并存储到有穷自动机（DFA）的状态集合（Dstates）中，然后开始遍历状态集合（Dstates），直到状态集合（Dstates）中的所有状态都完成遍历；若在遍历过程中产生新状态，且在状态集合（Dstates）中不存在该新状态，则该新状态存储到状态集合（Dstates）中，若在状态集合（Dstates）中存在该新状态，则不将该新状态存储到状态集合（Dstates）中；在判断该新状态过程中，不论该新状态是否存在于状态集合（Dstates）中，均记录转换关系，并将该转换关系存储到有穷自动机（DFA）的状态之间的转换关系集合（Dtrans）中；其中，在遍历状态集合（Dstates）中每个状态时，计算该状态中的每个字符                                                的跟随状态，并根据条件存放到状态集合（Dstates）中。       
2.根据权利要求1所述的一种带通配符正则表达式的有穷自动机生成方法，其特征在于：在所述步骤S3中，在计算每个状态中的每个字符的跟随状态的过程中，还包括如下步骤：       
S31：判断状态字符是否还有剩余字符计算，若有，则转到步骤S32，否则返回到遍历状态集合中状态；       
S32：将状态中和字符对应的所有位置p的followpos（p）的并集表示为U；       
S33：判断并状态集合（Dstates）是否还有下一状态；若是，则转到步骤S34，否则转到步骤S36；       
S34：取状态集合（Dstates）中的下一个状态；       
S35 ：调用集合比较算法比较状态与并集U，判断状态与并集U是否相等；若相等，则转到步骤S36，否则转到步骤S33；       
S36：将并集U作为未标记的状态存储到状态集合（Dstates）中；       
S37：记录对应的转换关系，将该转换关系存储到转换关系集合（Dtrans）中。       
3.根据权利要求1所述的一种带通配符正则表达式的有穷自动机生成方法，其特征在于：还包括一预设扩展ASCII码表，该预设扩展ASCII码表在基本的ASCII码表中增加整数“256”的通配符“.”、整数“257”的通配符“\w”、整数“258”的通配符“\d”和整数“259”的通配符“\s”。       
说  明  书
<p>技术领域   
本发明涉及网络入侵检测技术领域，特别是一种带通配符正则表达式的有穷自动机生成方法。   
背景技术   
现在网络入侵越来越复杂，在网络应用层的漏洞成为了黑客的重点攻击目标，利用网络应用层的漏洞进行攻击时，攻击者的数据都是隐藏在正常的数据通道中的，传统的基于状态的检测方式对正常的通道是允许通过的，很难检测这种应用层的攻击，所以对于应用层的攻击检测一般都需要检查网络通路中的数据内容，看是否具有攻击特征。由于正则表达式具有很高的灵活性，因此基于内容的检测方法中，攻击的规则大都使用正则表达式来表示。   
通配符是正则表达式中应用非常广泛的一项特性，使得正则表达式可以表现的非常灵活。在正则表达式中，一般的通配符有“.”、“\w”、“\d”、“\s”等。“.”表示所有字符，即256个ASCII字符，“\w”代表单词字符，即字母、数字和下划线，“\d”表示数字，“\s”代表空格字符串，包括空格，tab键等。在网络入侵中，匹配的规则一般使用正则表达式表示，正则中一般都包含有各种通配符，例如可以使用select\scount(*)\sfrom\s\w*正则表达式来判断是否存在某种sql注入的可能。   

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。