0

语境

在解析 Web 访问日志时，需要将机器人与人类用户代理分开。

我手动构建了它们的列表，提取了类似 bot 的模式（例如包含bot）。然后我有一个模式列表（大约 300 项大），我实时验证传入的访问日志。随着时间的推移，这已经成为一个相当大的瓶颈，因为我的（低效的）算法会寻找任何模式；即使我们忽略了意味着 DoS 漏洞的性能下降。

代码（Java）

String userAgent;
List<Pattern> botPatterns;

    for (Pattern botPattern : botPatterns)
    {
        if (botPattern.matcher(userAgent).find())
        {
            return true;
        }
    }
    return false;

已经探索的答案

使用 WURFL

这可能是一个简单的解决方案，但结果有时不准确。现在想避免使用内置解决方案。

使用用户代理缓存

通过将用户代理字符串存储在哈希图中，可以缓存结果。然而，即使这提高了性能，这也增加了使用随机生成的用户代理字符串进行简单 DoS 攻击的脆弱性。

问题

是否有一种有效的算法可以将大量 (N) 字符串与固定数量的正则表达式模式 (m) 进行匹配？

编辑：基准答案

我使用真实数据以及随机生成的用户代理字符串对@stemm 的答案进行了基准测试。我在 10 秒内运行了测试，并对计算时间进行了平均。缓存是一个大小为 5000 的简单 LFU ehcache

这是我的结果：

模式循环

没有缓存

真实数据：101us

随机数据：193us

带缓存

真实数据：4us

随机数据：203us

单一模式

没有缓存

真实数据：100us

随机数据：160us

带缓存

真实数据：3us

随机数据：154us

结论

  • 对于现实生活中的情况，缓存是最有效的解决方案。
  • 与循环模式相比，具有单一模式可提供 25% 的增益。
  • 缓存不像我想象的那样容易受到 DoS 攻击。

谢谢大家的回答和评论。

4

2 回答 2

1

如果您有固定数量的模式，您可以构建有限状态机来表示您的模式，从而大大提高性能。但是这个解决方案需要对逻辑和表示 FSM 进行额外的开发。

示例您有多种模式 [abc, abd, acd, dab]

有限状态机看起来像：

start -> a -> b -> c -> finish
                -> d -> finish
           -> c -> d -> finish
      -> d -> a -> b -> finish

您可以将 FSM 视为具有有限数量状态的有序图。您想abd在这些模式上匹配字符串。从 start 开始，您遇到 a -> b -> d 并完成。Thta 表示该字符串与您可以从路径恢复的模式匹配。具有类似功能的更复杂的模式，*您?可以通过将状态链接到自身（*）来表示，或者完全跳过此状态（?）。

于 2012-09-03T07:36:54.017 回答
1

主要思想是创建收集模式，其中包含您拥有的所有正则表达式。

例如 - 您想查找与以下任何正则表达式匹配的字符串：^\d+$or^[aA]+$或^[a-z\s]+$. 因此，您可以将它们组合成这样的正则表达式：(^\d+$|^[aA]+$|^[a-z\s]+$)

示例java代码：

public class Test {

    public static Pattern gather( String... patterns ) {
        StringBuilder finalRegexBuilder = new StringBuilder( "(" );
        for ( String ptr : patterns ) {
            finalRegexBuilder.append( ptr ).append( "|" );
        }
        finalRegexBuilder.setLength( finalRegexBuilder.length() - 1 );
        finalRegexBuilder.append( ")" );
        return Pattern.compile( finalRegexBuilder.toString() );
    }

    public static void main( String[] args ) {
        Pattern regex = gather( "^\\d+$", "^[aA]+$", "^[a-z\\s]+$" );

        System.out.println( regex.toString() ); // (^\d+$|^[aA]+$|^[a-z\s]+$)

        System.out.println( regex.matcher( "1235" ).find() ); // true
        System.out.println( regex.matcher( "1235fdjg" ).find() ); // false
        System.out.println( regex.matcher( "AAAaaaAaa" ).find() ); // true
        System.out.println( regex.matcher( "hello world" ).find() ); // true
    }
}

事实上 - 正则表达式的底层机制是一个有限状态机。所以，在上面的代码中，我们得到了@mishadoff 谈到的 FSM。

于 2012-09-03T09:28:59.347 回答