如何使用数百种模式搜索列表中的上万个项目

Question

我正在寻找一个更好（更快）的方法来处理这个问题。我的问题是，当你增加“主机”列表的长度时，程序要花费成倍的时间才能完成，如果“主机”足够长，那么程序完成所需的时间就太长了，以至于它似乎只是在锁定。在

• “主机”是一个包含上万个项目的列表。当迭代“hosts”时，i[0]总是一个IP地址，i[4]总是一个5位数的数字，而i[7]总是一个多行字符串。在
• “searchPatterns”是从CSV文件读取的列表列表，其中元素i[0]到i[3]是regex搜索模式（或字符串“SKIP”），i[6]是用于标识模式匹配的唯一字符串。在

我目前的方法是使用CSV文件中的regex模式搜索“hosts”i[7]元素中包含的每个多行列表项。有100个可能的匹配项，我需要识别与每个IP地址相关联的所有匹配项，并从CSV文件中分配唯一的字符串来标识所有模式匹配项。最后，我需要将这些信息放入“fullMatchList”中以便以后使用。在

注意：即使“searchPatterns”中的每个列表项最多有4个模式，我只需要它来标识找到的第一个模式，然后它就可以转到下一个列表项，继续为该IP查找匹配项。在

for i in hosts:
    if i[4] == "13579" or i[4] == "24680":
        for j in searchPatterns:
            for k in range(4):
                if j[k] == "SKIP":
                    continue
                else:
                    match = re.search(r'%s' % j[k], i[7], flags=re.DOTALL)
                    if match is not None:
                        if tempIP == "":
                            tempIP = i[0]
                            matchListPerIP.append(j[4])
                        elif tempIP == i[0]:
                            matchListPerIP.append(j[4])
                        elif tempIP != i[0]:
                            fullMatchList.append([tempIP, matchListPerIP])
                            tempIP = i[0]
                            matchListPerIP = []
                            matchListPerIP.append(j[4])
                        break
fullMatchList.append([tempIP, matchListPerIP])

以下是来自CSV文件的regex搜索模式示例：
(?!(.*?)\br2\b)cpe:/o:microsoft:windows_server_2008:

该模式旨在标识WindowsServer2008，并包含一个否定的前瞻性，以避免与R2版本匹配。在

我是Python的新手，所以任何建议都将不胜感激！谢谢您！在

Answer 1

NIDS社区已经做了大量的工作，针对一长串regex（防火墙规则）测试相同的字符串（网络包）。在

我还没有读过相关文献，但是Coit等人的“为入侵检测提供更快的字符串匹配或超过Snort的速度”似乎是一个很好的起点。在

引自引言：

The basic string matching task that must be
performed by a NIDS is to match a number of patterns drawn from the NIDS rules to 
each packet or reconstructed TCP stream that the NIDS is analyzing. In Snort, the 
total number of rules available has become quite large, and continues to grow 
rapidly. As of 10/10/2000 there were 854 rules included in the “10102kany.rules” 
ruleset file [5]. 68 of these rules did not require content matching while 786 
relied on content matching to identify harmful packets. Thus, even though not 
every pattern string is applied to every stream, there are a large number of 
patterns being applied to some streams. For example, in traffic inbound to a web 
server, Snort v 1.6.3 with the snort.org ruleset, “10102kany.rules”, checks up to 
3 15 pattern strings against each packet. At the moment, it checks each pattern in 
turn using the Boyer-Moore algorithm. Since the patterns often have something in 
common, it seemed likely that there is considerable scope for efficiency 
improvements here, and so it has proved.