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

Question

这个问题与 SQL 盲注类似。目标是确定字符串的准确值，唯一可以做的测试是查看 DOS 风格的通配符 (?= 任何字符，* = 任意数量的任意字符）您指定的与字符串匹配。（所以实际上你只能访问 bool DoesWildcardMatch(string wildcard) 功能）。

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

• 搜索 *a*, *b* ETC。确定字符集
• 当比赛进行时 *x* 找到后，执行分而治之（*a*x*, *b*x*, ...)

Answer 1

第一个想法。您可以确定长度 n 中的字符串 O(log2(n)).

• 查看 Z* 在哪里 Z 代表 k 问号从 0 开始，然后是 1，然后每次检查时将问号数量加倍，直到没有匹配项出现。 n 必须介于 k / 2 和 k
• 使用相同的模式变化找到精确的长度 k 与二分查找的方式相同。

知道确切的长度可能有助于在空间域中执行一种分而治之的方法。

更新

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

例子：

    ..X. ..XX (spaces added for readability)

                              + symbol may be X
                              - symbol is not X
                              X symbol is X

    *X*         => MATCH      ++++ ++++
    *X*   ????  => MATCH      ++++ ++++
    *X*?? ????  => NO MATCH   --++ ++++
    ??X?  ????  => MATCH      --X+ ++++
    ??XX  ????  => NO MATCH   --X- ++++
    ??X?  *X*?? => NO MATCH   --X- --++
    ??X?  ??X?  => MATCH      --X- --X+
    ??X?  ??XX  => MATCH      --X- --XX

对于字符串长度 n 和字母大小 m 这将需要大约 O(log2(n)) 找到字符串的长度，大约 O(n • log2(n)) 正确放置 n 符号，以及 O(m) 找到使用过的符号 - 将所有符号加在一起得到 O(n • log2(n) + m).

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

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

Answer 2

至于分而治之，请务必记录您已知不存在的值。我也不会去 a, b, c, ，但具有频率顺序。某种马尔可夫链可能会让它变得更快。

需要注意的一件事是，您不能假设给定的文字始终与输入中的相同位置匹配。对于最后删除通配符，这将特别令人感兴趣。

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

Answer 3

如果有具体数量？作品，您还可以查看“？”、“？？”、“???”等。获取字符串的长度，但我怀疑这会有多大帮助，因为您还可以在每一轮后仅进行一次额外检查而不使用任何通配符来检查是否获得了正确的长度。

我认为之前进行字符集检查的除法几乎是最佳的，还有一些额外的细节，例如如果您匹配 *a*b*, ，你应该检查 *ab* 之后要知道中间是否有字母，当然如上所述，请检查 *ab 并在其后添加“ab”，以了解您是否已完成右侧或完全完成。

Answer 4

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

？A*

变成：

。A。*

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