AST解析安全性:内存和时间

Question

我担心解析恶意代码的AST会产生一个非常大的对象，或者持续很长时间。我的忧虑听起来了吗？当代码本身很小时，是否有一种方法使树变得不合理地大？

Answer 1

AST的大小与被解析程序的长度成正比。所以这不是什么担心。

Python使用PEG解析器，这是一种回溯算法，在代码长度上应该是线性的。如果您遇到一个需要特别长时间来解析短文本的输入，您应该将其报告为bug (情况就是如此)。

但是，请记住，语法树是不平衡的。构建一个AST在代码大小上具有深度线性的程序并不困难。由于执行堆栈的大小非常有限，所以AST的递归遍历可能会使堆栈溢出，即使它们只使用很小的内存百分比。在Python手册中的the documentation for ast.parse中有一个关于这一点的警告：

警告可以使用足够大/复杂的字符串使解释器崩溃，这是因为Python的AST编译器.

中的堆栈深度限制