[go: up one dir, main page]

CN104519056A - 一种基于双跳跃的单模式匹配方法 - Google Patents

一种基于双跳跃的单模式匹配方法 Download PDF

Info

Publication number
CN104519056A
CN104519056A CN201410769572.6A CN201410769572A CN104519056A CN 104519056 A CN104519056 A CN 104519056A CN 201410769572 A CN201410769572 A CN 201410769572A CN 104519056 A CN104519056 A CN 104519056A
Authority
CN
China
Prior art keywords
string
jump
character
pos
pattern
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201410769572.6A
Other languages
English (en)
Other versions
CN104519056B (zh
Inventor
杨忠明
申林
秦勇
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Guangdong Institute of Science and Technology
Original Assignee
Guangdong Institute of Science and Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Guangdong Institute of Science and Technology filed Critical Guangdong Institute of Science and Technology
Priority to CN201410769572.6A priority Critical patent/CN104519056B/zh
Publication of CN104519056A publication Critical patent/CN104519056A/zh
Application granted granted Critical
Publication of CN104519056B publication Critical patent/CN104519056B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/14—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic
    • H04L63/1408—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic by monitoring network traffic
    • H04L63/1416—Event detection, e.g. attack signature detection

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Hardware Design (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本发明公开一种基于双跳跃的单模式匹配方法，采用改进Sunday算法完成其中的入侵模式串的匹配，在字符匹配过程中若出现字符不相等，则先连续跳跃两步，再进行匹配。本发明大大提高了入侵检测系统的匹配效率，提高了检测系统的检测速度，并间接提高了检测系统的实时性，本发明的一种基于双跳跃的单模式匹配方法用途广泛，可应用在自适应免疫网络入侵检测系统和网络内容审计等方面。

Description

一种基于双跳跃的单模式匹配方法
技术领域
本发明涉及计算机网络安全领域，具体涉及一种基于双跳跃的单模式匹配方法。
背景技术
入侵检测系统是防火墙的合理补充，通过主动防御来帮助系统对付网络攻击，扩展了系统管理员的安全管理能力，提高了信息安全基础结构的完整性。它从计算机网络系统中的若干关键点收集并分析信息，查看网络中是否有违反安全策略的行为和遭到袭击的迹象。入侵检测系统在不影响网络性能的情况下能对网络进行监测，提供对内部攻击、外部攻击和误操作的实时保护 。
模式匹配是入侵检测系统的核心，其影响着系统的检测效率，而业内著名的snort系统中sp_pattern_match检测引擎插件对规则选项的content和uricontent内容进行模式匹配所使用的是BM算法，但采用Sunday算法在实际应用中效率要优于BM算法。
Sunday算法是Danile M.Sunday在1990年提出的一种单模式匹配算法，其核心思想是一旦发生字符不匹配，则跳跃尽可能多的字符。Sunday有一个next数组存储跳跃步长，匹配过程中出现字符不相等时，检测主串中模式串尾端对齐 字符的下一个字符在模式串中的相同字符，并将最右端的一个和它对齐，当该字符不存在于模式串中的时候则直接全部跳过，长度为m的模式串跳跃步长为m+1。
但是Sunday算法在模式匹配的过程中仍然会出现较多冗余的匹配，匹配效率、检测速度和检测实时性仍然有待提高。
发明内容
为了克服现有技术的不足，本发明提供一种基于双跳跃的单模式匹配方法，它能够解决现有技术在模式匹配的过程中仍然会出现较多冗余的匹配，匹配效率、检测速度和检测实时性等问题。
本发明采用的技术方案如下：
一种基于双跳跃的单模式匹配方法，采用改进Sunday算法完成其中的入侵模式串的匹配，在字符匹配过程中若出现字符不相等，则先连续跳跃两步，再进行匹配。
本发明采用Sunday算法完成其中的入侵模式串的匹配，并对Sunday算法作了改进。基于传统Sunday算法匹配方法只有一个跳跃数组，而本发明的一种基于双跳跃的单模式匹配方法在此基础上增加了一个跳跃数组，当匹配过程中有字符不匹配时连续跳跃两步，更大程度地减少了冗余匹配。
进一步的，本发明的一种基于双跳跃的单模式匹配方法，包括以下步骤：
S21初始化跳跃数组next1和next2；
S22开始匹配；
S23若匹配成功则将将模式串P[0…m-1]整体向右移一位，若匹配失败则按跳跃数组next1向右跳跃S1个字符，然后按next2进行第二步跳跃，跳过S2个字符；
S24判断移动后的模式串是否到达或超出主串尾，若否则返回S22，若是则结束匹配，输出所有和模式串相匹配的字符串的位置。
本发明提出了连续两步跳跃的思想，对P[0…m-1] 和M[0…n-1] 从左往右逐位比较，当比较过程中有字符不相等时，先使用传统Sunday算法的思想根据当前P[m-1]在M[0…n-1]中的对齐位的后一位计算P[0…m-1]向右的跳跃步长S1，再根据S1并运用next2数组向右跳跃S2位，即在字符不相等的时候一次向右跳跃了S1+S2位。这种匹配方法在基于传统Sunday算法的匹配方法的基础上进一步减少了冗余匹配次数，效率要高于基于传统Sunday算法的匹配方法。
进一步的，所述跳跃数组next1的初始化规则为：当模式串P[0,1…m-1]中存在和主串M[pos+m]位相同的字符，则将模式串P[0,1…m-1]中的这些字符最右边一个和M[pos+m]位对齐，若不存在相同字符，则直接跳过，将M[pos+m+1]位和P[0]位对齐，其中pos表示每次匹配开始时模式串P起始位在主串M中的对齐位下标，m表示模式串的长度。
进一步的，所述跳跃数组next2的初始化规则为：第一步跳跃完毕后，若模式串中存在与M[pos+m+S1-1]位相同的字符，则把这些字符最右边一个与M[pos+m+S1-1]位对齐，若M[pos+m+S1-1]= P[m-1]，则第二步跳跃为0，若不存在与M[pos+m+S1-1]位相同的字符，则直接跳过，将M[pos+m+S1-1]位和P[0]位对齐。
模式串P[0…m-1] 和主串M[0…n-1]匹配的时候，当有字符不相等时，第一步的跳跃S1一定是大于0的，第二步跳跃S2大于或等于0，出现等于0的情况 是由于在第一步跳跃之后模式串P[0…m-1] 的尾字符和主串M[0…n-1]就已经匹配成功。
在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，为了方便描述，本发明是按从左向右的比较顺序进行描述，但同样适用于从右向左的匹配过程。
本发明的有益效果：本发明采用改进的Sunday算法完成入侵模式串的匹配，从而大大提高了匹配效率，提高了检测系统的检测速度，并间接提高了检测系统的实时性 ，本发明的一种基于双跳跃的单模式匹配方法用途广泛，可应用在自适应免疫网络入侵检测系统和网络内容审计等方面。
附图说明
图1是本发明实施例1的匹配过程流程图；
图2是本发明实施例1模式串和主串开始匹配前的初始位置示意图；
图3是本发明实施例1完成第一次第一步跳跃后模式串和主串的位置示意图；
图4是本发明实施例1完成第一次第二步跳跃后模式串和主串的位置示意图；
图5是本发明实施例1完成第二次第一步跳跃后模式串和主串的位置示意图；
图6是本发明实施例1完成第二次第二步跳跃后模式串和主串的位置示意图；
图7是本发明实施例2使用本发明的匹配方法和基于传统Sunday算法的匹配方法的匹配次数和匹配成功次数对比图；
图8是本发明实施例3使用本发明的匹配方法和基于传统Sunday算法的匹配方法对模式串进行匹配的用时对比图。
具体实施方式
下面结合附图和具体实施方式对本发明作进一步的详细说明。
实施例1：
如图1所示可以清楚了解本发明的一种基于双跳跃的单模式匹配方法的匹配过程：
S21初始化跳跃数组next1和next2；
S22开始匹配；
S23若匹配成功则将将模式串P[0…m-1]整体向右移一位，若匹配失败则分别按跳跃数组next1向右跳跃S1个字符，然后按next2进行第二步跳跃，跳过S2个字符；
S24判断移动后的模式串是否到达或超出主串尾，若否则返回S22，若是则结束匹配，输出所有和模式串相匹配的字符串的位置。
进一步的，所述跳跃数组next1的初始化规则为：当模式串P[0,1…m-1]中存在和主串M[pos+m]位相同的字符，则将模式串P[0,1…m-1]中的这些字符最右边一个和M[pos+m]位对齐，若不存在相同字符，则直接跳过，将M[pos+m+1]位和P[0]位对齐，其中pos表示每次匹配开始时模式串P起始位在主串M中的对齐位下标，m表示模式串的长度。
进一步的，所述跳跃数组next2的初始化规则为：第一步跳跃完毕后，若模式串中存在与M[pos+m+S1-1]位相同的字符，则把这些字符最右边一个与M[pos+m+S1-1]位对齐，若M[pos+m+S1-1]= P[m-1]，则第二步跳跃为0，若不存在与M[pos+m+S1-1]位相同的字符，则直接跳过，将M[pos+m+S1-1]位和P[0]位对齐。
如图2所示本实施例取模式串P=“bcdeafk”，主串M=“abcdefaemkfgabcdeafkmw”，由图2可以看出，模式串 P在匹配过程当中出现字符不相等的情况，而模式串P[0,1…m-1]中存在和主串M[pos+m]位相同的字符，即e,于是将最右边的一个e移到M[pos+m]位，完成第一次第一步跳跃。完成第一次第一步跳跃后模式串和主串的位置如图3所示。
完成第一次第一步跳跃后并不进行匹配，而是继续进行第一次的第二步跳跃。由图3可以看出模式串中存在与M[pos+m+S1-1]位相同的字符，即f，于是将模式串中最右边的f移动S2个字符到与M[pos+m+S1-1]位对齐。完成第一次第二步跳跃后模式串和主串的位置如图4所示。
完成两步跳跃后开始匹配，由图4可见看出出现字符不相等，继续开始连续的连续两步的跳跃。由图4中可以看出，模式串P[0,1…m-1]中存在和主串M[pos+m]位相同的字符，即a，于是将最右边的一个a移到M[pos+m]位，完成第二次第一步跳跃。此次跳跃后模式串和主串的位置如图5所示。
 从图5中可以看出，模式串中存在与M[pos+m+S1-1]位相同的字符，即c，于是将模式串中最右边的c移动S2个字符到与M[pos+m+S1-1]位对齐。完成第二次第二步跳跃后模式串和主串的位置如图6所示。
从图6中可以看出完成第二次第二步跳跃后模式串与主串已经匹配成功，此时只有一次冗余匹配。而通过对基于传统Sunday算法的匹配方法的分析，要模式串P=“bcdeafk”和主串M=“abcdefaemkfgabcdeafkmw”匹配成功需要经过三次冗余的匹配。
实施例2：
随机选取以下一段文字作为主串：but in a larger sense, we can not dedicate, we cannot consecrate, we can not hallow this ground. the brave ten, living and dead, who struggled here,have consecrated it far above our power to add or detract. the world will little note nor long retetber what we say here, but it can never forget whatthey did here. it is for us, the living, rather to be dedicated to thegreat task retaining before us; that frot these honored dead, we take increased devotion to that cause for which they gave the last full teasureof devotion; that this nation, under god, shall have a new birth of freedot;and that governtent of the people by the people and for the people shall notperish frot the earth. 从中选取ground、the、here、cause、earth作为模式串 (实验实际过程中未包括空格和标点符号)。针对每一个模式串，记录使用本发明的匹配方法和基于传统Sunday算法的匹配方法的比较次数和匹配成功次数，验证本发明的匹配方法的有效性和正确性。此次试验环境为，Intel Core i3 CPU,主频为2.53GHz。实验结果如图7所示。其中YC是本发明的匹配方法的代号，S是基于传统Sunday算法的匹配方法的代号。由实验结果可以看出，通过连续两步的跳跃，本发明的匹配方法大大的减少了冗余匹配次数，节省了匹配时间，比基于传统Sunday算法的匹配方法高效。
实施例3：
硬件及操作系统的资源分配机制等因素会使得每次匹配用的时间不同，匹配用时会处在一个时间域之内，本实施例生成1000000长度的随机字符串作为主串M，并生成长度分别为1，10，20,30,40,50,60,70,80,90长度的随机字符串作为模式串。分别使用本发明的匹配方法和基于传统Sunday算法的匹配方法在主串中匹配模式串，每个模式串匹配10000次，分别记录每个模式串在两种方法下用时的时间域，并且求平均值。试验环境为Intel(R) Core(TM) i3 CPU,主频为2.93GHz，实验数据如图8所示，其中YC是本发明的匹配方法的代号，S是基于传统Sunday算法的匹配方法的代号。
 从图8中可以看出，本发明的匹配方法大大降低了匹配用时，提高了检测系统的检测速度。

Claims (3)

1.一种基于双跳跃的单模式匹配方法，采用改进Sunday算法完成其中的入侵模式串的匹配，其特征在于，在字符匹配过程中若出现字符不相等，则先连续跳跃两步，再进行匹配，具体包括以下步骤：
S21初始化跳跃数组next1和next2；
S22开始匹配；
S23若匹配成功则将将模式串P[0…m-1]整体向右移一位，若匹配失败则按跳跃数组next1向右跳跃S1个字符，然后按next2进行第二步跳跃，跳过S2个字符；
S24判断移动后的模式串是否到达或超出主串尾，若否则返回S22，若是则结束匹配，输出所有和模式串相匹配的字符串的位置。
2.根据权利要求1所述的一种基于双跳跃的单模式匹配方法，其特征在于，所述跳跃数组next1的初始化规则为：当模式串P[0,1…m-1]中存在和主串M[pos+m]位相同的字符，则将模式串P[0,1…m-1]中的这些字符最右边一个和M[pos+m]位对齐，若不存在相同字符，则直接跳过，将M[pos+m+1]位和P[0]位对齐，其中pos表示每次匹配开始时模式串P起始位在主串M中的对齐位下标，m表示模式串的长度。
3.根据权利要求1或2所述的一种基于双跳跃的单模式匹配方法，其特征在于，所述跳跃数组next2的初始化规则为：第一步跳跃完毕后，若模式串中存在与M[pos+m+S1-1]位相同的字符，则把这些字符最右边一个与M[pos+m+S1-1]位对齐，若M[pos+m+S1-1]= P[m-1]，则第二步跳跃为0，若不存在与M[pos+m+S1-1]位相同的字符，则直接跳过，将M[pos+m+S1-1]位和P[0]位对齐。
CN201410769572.6A 2014-12-15 2014-12-15 一种基于双跳跃的单模式匹配方法 Active CN104519056B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201410769572.6A CN104519056B (zh) 2014-12-15 2014-12-15 一种基于双跳跃的单模式匹配方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201410769572.6A CN104519056B (zh) 2014-12-15 2014-12-15 一种基于双跳跃的单模式匹配方法

Publications (2)

Publication Number Publication Date
CN104519056A true CN104519056A (zh) 2015-04-15
CN104519056B CN104519056B (zh) 2017-09-08

Family

ID=52793778

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201410769572.6A Active CN104519056B (zh) 2014-12-15 2014-12-15 一种基于双跳跃的单模式匹配方法

Country Status (1)

Country Link
CN (1) CN104519056B (zh)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105809038A (zh) * 2016-03-01 2016-07-27 江苏大学 一种面向监测日志的构件异常信息查找方法
CN107220333A (zh) * 2017-05-24 2017-09-29 电子科技大学 一种基于Sunday算法的字符搜索方法
CN111814009A (zh) * 2020-06-28 2020-10-23 四川长虹电器股份有限公司 一种基于搜索引擎检索信息模式匹配的bf改进算法
CN112069303A (zh) * 2020-09-17 2020-12-11 四川长虹电器股份有限公司 字符串的匹配查找方法、装置及终端
CN113836367A (zh) * 2021-09-26 2021-12-24 杭州迪普科技股份有限公司 一种字符反向匹配的方法及装置

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040190506A1 (en) * 2003-03-24 2004-09-30 International Business Machines Corp. Method and apparatus for performing complex pattern matching in a data stream within a computer network
CN103577598A (zh) * 2013-11-15 2014-02-12 曙光信息产业(北京)有限公司 模式串与文本串的匹配方法和装置
CN103873317A (zh) * 2012-12-18 2014-06-18 中国科学院空间科学与应用研究中心 一种ccsds空间链路协议检测方法及系统

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040190506A1 (en) * 2003-03-24 2004-09-30 International Business Machines Corp. Method and apparatus for performing complex pattern matching in a data stream within a computer network
CN103873317A (zh) * 2012-12-18 2014-06-18 中国科学院空间科学与应用研究中心 一种ccsds空间链路协议检测方法及系统
CN103577598A (zh) * 2013-11-15 2014-02-12 曙光信息产业(北京)有限公司 模式串与文本串的匹配方法和装置

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105809038A (zh) * 2016-03-01 2016-07-27 江苏大学 一种面向监测日志的构件异常信息查找方法
CN105809038B (zh) * 2016-03-01 2018-08-10 江苏大学 一种面向监测日志的构件异常信息查找方法
CN107220333A (zh) * 2017-05-24 2017-09-29 电子科技大学 一种基于Sunday算法的字符搜索方法
CN107220333B (zh) * 2017-05-24 2020-01-31 电子科技大学 一种基于Sunday算法的字符搜索方法
CN111814009A (zh) * 2020-06-28 2020-10-23 四川长虹电器股份有限公司 一种基于搜索引擎检索信息模式匹配的bf改进算法
CN111814009B (zh) * 2020-06-28 2022-03-01 四川长虹电器股份有限公司 一种基于搜索引擎检索信息的模式匹配方法
CN112069303A (zh) * 2020-09-17 2020-12-11 四川长虹电器股份有限公司 字符串的匹配查找方法、装置及终端
CN113836367A (zh) * 2021-09-26 2021-12-24 杭州迪普科技股份有限公司 一种字符反向匹配的方法及装置
CN113836367B (zh) * 2021-09-26 2023-04-28 杭州迪普科技股份有限公司 一种字符反向匹配的方法及装置

Also Published As

Publication number Publication date
CN104519056B (zh) 2017-09-08

Similar Documents

Publication Publication Date Title
CN104519056B (zh) 一种基于双跳跃的单模式匹配方法
US20220029816A1 (en) Optimizations for verification of interactions system and method
CN109104413B (zh) 用于安全多方计算的私有数据求交集的方法及验证方法
CN109450845B (zh) 一种基于深度神经网络的算法生成恶意域名检测方法
CN106612172A (zh) 云存储中一种可验证还原数据真实性的数据篡改恢复算法
CN102663618B (zh) 一种无纸化彩票电子凭证实施方法
KR20220152167A (ko) 도메인 네임 시스템(dns) 레코드들의 세트에서 피싱-도메인들을 검출하기 위한 시스템 및 방법
JP2009542092A5 (zh)
CN103455965A (zh) 一种基于验证图片的验证方法、装置及服务器
CN105824825A (zh) 一种敏感数据识别方法和装置
CN108400979A (zh) 应用于客户端和服务器的通信方法及电子设备
CN101741845B (zh) 一种基于分片的内容认证方法
CN107220333B (zh) 一种基于Sunday算法的字符搜索方法
CN103500178B (zh) 一种fs算法最差情况下的快速多模式匹配方法
CN116150392A (zh) 威胁情报知识图谱处理方法、装置、设备及存储介质
CN101425898A (zh) 数字签名和验证数字签名的方法、系统、设备和生成器
CN103927325A (zh) 一种对url进行分类的方法及装置
CN112019354B (zh) 一种基于生成式对抗网络的口令遍历装置及方法
CN118709203A (zh) 故障注入攻击方法、装置以及设备
CN110752928B (zh) 基于混淆激励设计的apuf及其实现抗机器学习攻击的方法
CN103401652B (zh) 一种可容错的rs码码长起点识别方法
CN104468570B (zh) 一种制造物联网中感知层的安全认证方法
Zhang et al. Mahalanobis distance similarity measure based distinguisher for template attack
CN109039590A (zh) 存储器、电子设备及其防止侧信道攻击的加解密方法
Xiao Passrvae: Improved trawling attacks via recurrent variational autoencoder

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
CB02 Change of applicant information

Address after: Zhuhai Avenue, Guangdong city of Zhuhai Province, the 519000 Bay area near No. 65

Applicant after: Guangdong Science & Technology Vocational College

Address before: 510640 No. 351 KELONG street, Guangzhou, Guangdong, Tianhe District

Applicant before: Guangdong Science & Technology Vocational College

COR Change of bibliographic data
GR01 Patent grant
GR01 Patent grant