如何追踪正则表达式中的灾难性回溯？

Question

我正在使用Apache Regexp作为正则表达式验证的库。我想知道如何跟踪一些正则表达式是否导致了灾难性回溯。

我想知道是否有一些技巧来捕捉哪个正则表达式和字符串值导致了灾难性回溯？

我尝试在RE.java类中进行了一些修改，但效果不如预期。

这是我的修改:

    public RE(String pattern) throws RESyntaxException
{
    this(pattern, MATCH_NORMAL);
    paramString = pattern;
}


public RE(String pattern, int matchFlags) throws RESyntaxException
{
    this(new RECompiler().compile(pattern), matchFlags);
    paramString = pattern;
}


int callcounterMN = 0;
protected int matchNodes(int firstNode, int lastNode, int idxStart)
{
    callcounterMN++;
    if (callcounterMN == 100) {
        try {
            String pc1 = new Exception().getStackTrace()[5].getClassName();
            if (pc1.indexOf("UpdateWebForm") > 1)     
                System.out.println("regex loop reach "+callcounterMN+"  with regex : "+paramString+" "+this.search.substring(0));
        } catch (Exception e) {}
    }

- tukimin

---

不要试图猜测字符串，而是为可能导致 CA 问题的每个正则表达式调用设置超时。 - Wiktor Stribiżew

是的，那是另一种方法。但我仍然想追踪这个问题，以防我的正则表达式出了问题。 不过，你能给我一些关于为每个正则表达式设置超时的参考资料吗？也许以后会有用。谢谢。 - tukimin

请参见如何取消长时间运行的正则表达式匹配？。 - Wiktor Stribiżew

谢谢你提供的参考。但我仍在寻找跟踪 CA 问题的方法。 - tukimin

Answer 1

很晚之后，但鉴于仍没有答案，我可以参与一下：谷歌的RE2正则表达式库旨在完全避免灾难性回溯问题，有时会以某种程度的性能代价为代价: https://github.com/google/re2/wiki/WhyRE2 这并不完全是对你的问题的回答，因为这是关于接受任何正则表达式并确保它永远不会导致灾难性回溯挂起的问题，而不是使用Apache库检测那些可能会出现这种情况的问题，但希望这对于部分问题的访问者仍然是有用的。如果您可以承担不支持某些正则表达式模式构造的代价，在某些情况下可以承受性能损失，并且可以测试和更换您正在使用的库 - 那么您可能已经解决了这个问题。

- Tao