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

Question

我使用 Apache 正则表达式作为库来验证正则表达式。我想知道如何跟踪某些正则表达式是否导致了灾难性的回溯。我想知道的是，是否有一些技巧可以捕获导致灾难性回溯的正则表达式和字符串值？我在类 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) {}
    }

Answer 1

很久以后，但鉴于仍然没有答案，我不妨加入:Google 的 RE2 正则表达式库旨在完全防止灾难性回溯问题，有时会以某种程度的性能为代价: https://github.com/google/re2/wiki/WhyRE2

这不完全是您问题的答案，因为这是关于接受任何 正则表达式并确保它永远不会导致灾难性的回溯挂起，而不是检测那些将使用 Apache 库的，但是希望对于这个问题的部分访问者来说，它仍然是有用的输入。如果您有能力不支持某些正则表达式模式结构，在某些情况下您可以承受性能损失，并且您可以测试和更换您正在使用的库 - 那么您可能已经解决了问题。