python - 如何使用数百种模式在列表列表中搜索数万个项目

Question

我正在寻找更好(更快)的方法来解决这个问题。我的问题是，当你增加“主机”列表的长度时，程序需要以指数方式增长才能完成，如果“主机”足够长，程序完成所需的时间就会很长，以至于它似乎只是锁定了。

• “hosts”是一个包含数万个项目的列表列表。当遍历“主机”时，i[0] 将始终是一个 IP 地址，i[4] 将始终是一个 5 位数字，而 i[7] 将始终是一个多行字符串。
• “searchPatterns”是从 CSV 文件中读取的列表列表，其中元素 i[0] 到 i[3] 是正则表达式搜索模式(或字符串“SKIP”)，i[6] 是使用的唯一字符串识别模式匹配。

我目前的方法是使用 CSV 文件中的正则表达式模式来搜索“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 文件中的正则表达式搜索模式示例:
(?!(.*?)\br2\b)cpe:/o:microsoft:windows_server_2008:

该模式旨在识别 Windows Server 2008，并包含一个否定前瞻以避免匹配 R2 版本。

我是 Python 的新手，所以非常感谢任何建议!谢谢!

Answer 1

NIDS 社区在针对一长串正则表达式(防火墙规则)测试相同字符串(网络数据包)方面做了大量工作。

我没有读过文献，但 Coit 等人的“Towards faster string matching for intrusion detection or exceeding the speed of 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.