限制 C++ 目标的递归

Question

在对使用 antlr 编写的语言进行模糊测试时，模糊器报告了一个使用大量括号的缓慢测试用例。

语法中的规则之一有点像：

paren_expression: '(' expression ')';

即使它被报告为一个缓慢的单元，它也是一个更大的问题，即在使用了足够多的括号的情况下，它很容易使应用程序崩溃（而且它在 windows 上确实如此，默认情况下堆栈大小较小).

根据我的搜索，没有选项可以生成检查堆栈深度并在合理深度后退出的代码，并且在 C++ 中从堆栈溢出中恢复并不是一件好事或可移植的事情。

那么，在这种情况下可以做什么？从错误的输入中崩溃不是很好。

Answer 1

您可以添加一个 predicate 来检查嵌套表达式的深度，如果超过一定数量则让谓词失败。

例如，您最多允许 3 个嵌套表达式，您可以这样做：

grammar T;

@members {
  private int depth = 0;
}

parse
 : expr EOF
 ;

expr
 : '(' expr ')' {++depth <= 3}?
 | INT
 ;

INT
 : [0-9]+
 ;

代码：

TLexer lexer = new TLexer(CharStreams.fromString("(((42)))"));
TParser parser = new TParser(new CommonTokenStream(lexer));
parser.parse();

可以正常解析，但代码：

TLexer lexer = new TLexer(CharStreams.fromString("((((42))))"));
TParser parser = new TParser(new CommonTokenStream(lexer));
parser.parse();

会抛出异常。

谓词 ({...}?) 和 @members 块内的部分是目标特定代码（在本例中为 Java）。你必须用 C++ 编写它。

Answer 2

这不是错误，而是一项功能。递归体面的解析器没有内置措施来防止堆栈溢出。可能是您真的想解析深层嵌套的结构，并且您能够在该问题上投入足够的内存。如果解析器生成器不知道您要解决的问题，为什么要为您设置任意递归深度？

使用您的 OS 方法设置线程的堆栈深度，您将能够解析深层嵌套的表达式。我有一个包含 > 700 个嵌套括号的测试用例，并且可以很好地解析：

此输出来自 macOS 测试应用。在 XCode 项目中，我将“其他链接器标志”条目中的堆栈限制设置为：-Wl,-stack_size,0x10000000。其他 platforms/build 工具也有类似的设置。但是，这是应用程序主线程的设置。对于辅助线程，事情变得棘手，因为 C++ 线程不允许在创建期间指定堆栈大小。

限制 C++ 目标的递归

Limit recursion on C++ target

c++

antlr

antlr4