使用DOS通配符进行字符串暴力破解的最快方法

Question

这个问题类似于盲注攻击。目标是确定一个字符串的确切值，你唯一能做的测试就是看你指定的 DOS 风格通配符（? = 任意字符，* = 任意数量的任意字符）是否与该字符串匹配。（所以实际上你只能访问 bool DoesWildcardMatch(string wildcard) 函数）。

直接的方法是对 a*，b*，c*... 进行测试，直到找到第一个字母，然后重复。我能想到的一些优化方法有：

• 搜索 *a*，*b* 等等，以确定字符集
• 当找到 *x* 的匹配时，执行分治策略（*a*x*，*b*x*，...）

- Vladimir Panteleev

---

关于字符串的一些问题：字符集可以是什么？只能是字母还是其他字符也可以？字符串的长度可以有多长？大小写是否有影响？ - schnaader

我并不真正理解这些信息如何帮助你想出一个高效的算法，但既然你问了 - 在我的特定情况下，该字符串是一个互联网主机名，因此它包含字母数字和一些像.和-这样的符号。 - Vladimir Panteleev

大小写无关紧要 - ?匹配正好一个符号，匹配零个或多个符号，其他每个符号都精确匹配该符号（如果不区分大小写，则可以将小写符号和大写符号视为相等）。字母表也不重要（除了如何处理字母表中的?和可能有所不同）。有趣的是，是否对字母表大小、字符串长度、符号频率或字母表大小与字符串长度的比率有任何假设。 - Daniel Brückner

Answer 1

关于分治策略，确保跟踪已知不存在的值。我不会使用a, b, c，而是使用频率顺序。从中制作一些马尔可夫链可能会使它更快。

要注意的一件事是，您不能假设给定的文字字面上始终匹配输入中的相同位置。这将特别涉及到删除结尾处的通配符。

c a b a
--------
* a *     match
  * b*a*  woops!

- BCS

---

关于频率 - 是的，那很明显，我只是忘了提到。分而治之的观点很好。 - Vladimir Panteleev

Answer 2

第一步，可以用时间复杂度为 O(log2(n)) 的方法计算字符串的长度 n。

• 检查以 0 开头，然后是一个问号，接着是两个问号，以此类推，每次将问号数量加倍，直到没有匹配为止。需要满足 n 在 k / 2 和 k 之间。
• 使用与二分搜索相同的模式通过改变 k 来确定精确长度。

了解确切的长度可能有助于在空间域中执行某种分治策略。

更新

如果知道了长度，可以使用相同的模式正确定位符号。

例子：

    ..X. ..XX (为了方便阅读添加了空格)
+ 可能是 X
                              - 不是 X 的符号
                              X 是 X 的符号
*X*         => 匹配      ++++ ++++
    *X*   ????  => 匹配      ++++ ++++
    *X*?? ????  => 不匹配     --++ ++++
    ??X?  ????  => 匹配      --X+ ++++
    ??XX  ????  => 不匹配     --X- ++++
    ??X?  *X*?? => 不匹配     --X- --++
    ??X?  ??X?  => 匹配      --X- --X+
    ??X?  ??XX  => 匹配      --X- --XX

对于字符串长度为 n，字母表大小为 m，这将花费大约 O(log2(n)) 的时间来查找字符串的长度，大约需要 O(n • log2(n)) 来正确放置 n 个符号，并且需要 O(m) 来查找使用的符号 - 将所有这些加起来总共需要 O(n • log2(n) + m)。

我能想象通过合并几个步骤可能会加快速度 - 可能在确定字符串长度时测试使用的符号，或者同时定位字符串的前半部分和后半部分中的两个（甚至更多？）符号。如果检查失败，则需要单独重新检查已合并的步骤，以确定哪个步骤失败了。但只要合并的检查成功，您就可以获得有关两者的信息。

也许我明天会计算一下，看看它是否真的会加快速度。

- Daniel Brückner

---

让我们来看看。如果我们有一个大小为m的字母表和固定大小为n的字符串，则一个字符串包含n * log(m)位信息。每个查询最多只能获取1位信息。因此，您需要至少O(n log(m))个查询。这可能比O(n log(n) + m)更大。 因此，你的答案一定是错误的。 - Accipitridae

不，我也是这么想的。但我们可以在每次检查中获得多于一个比特。例如，如果 A 失败了，我们知道没有一个符号等于 A，我们用一次检查获得了多于一个比特的信息。 - Daniel Brückner

更准确地说，获取多少信息取决于字符串的长度。失败的A检查将搜索空间从m^n减少到(m-1)^n，因此从n * log2(m)到n * (log2(m-1))位。对于n > 1 / log2(m / m - 1)，我们获得超过一位的信息。在m = 26的情况下，这需要n > 18。 - Daniel Brückner

加快匹配的一个好方法是使用类似于单词列表的东西——你说它是主机名，所以例如搜索后缀如“.com”，“.org”等是可行的。 - schnaader

Answer 3

如果特定数量的通配符可以匹配，你可以使用 "?", "??", "???" 等来获取字符串的长度，但我怀疑这并没有帮助太多，因为你也可以在每轮结束后只进行一次额外的检查来确认长度是否正确，而无需使用任何通配符。

我认为，在字符集检查前使用分割方法是几乎最优的。还有一些其他细节需要注意，例如如果你匹配了 *a*b*，那么你应该在之后检查 *ab* 是否存在字母，并且当然如上所述，在此之后检查 *ab 和 "ab" 来确定是否已经匹配完右侧或者完全匹配。

- schnaader

Answer 4

为什么不将您的DOS风格通配符字符串转换为正则表达式呢？例如：

?a*

变成：

.a.*

然后只需执行一个简单的正则表达式匹配，将其与您的测试字符串进行比较即可。

- Matt Huggins

---

很抱歉，我不明白正则表达式如何帮助解决这个问题。从代码角度来看，想象一下你只能调用一个函数，该函数接受一个DOS通配符并返回一个布尔值，指示我们需要确定的字符串是否与给定的通配符匹配。我们无法对未知字符串进行正则表达式测试。 - Vladimir Panteleev