What？构造的查询语句会导致堆栈溢出

2022 年 5 月 05 日
本文字数：2558 字
阅读完需：约 8 分钟

本文分享自华为云社区《巧妙构造的查询语句会导致堆栈溢出？从两个开源图数据库PR看查询执行时的编码设计问题》，作者：蜉蝣与海。

导读 &简介

查询语言（Query Language）的出现方便了用户在计算引擎上执行各种操作，就图数据库而言，neo4j 支持查询语言 cypher，nebula 有其独有的查询语言 nGQL。由于查询语言规则依赖语言自身文法，用户使用查询语言自由度较大，输入灵活，一般测试手段难以覆盖到所有情况，所以在某种程度上复杂的查询语句是各类计算产品健壮性的试金石，本文归纳了两个开源产品 pr（pull request）时修复的堆栈溢出问题，并试着写写通过阅读 pr 中的问题而得到的一些启发。

先上链接，如果你更喜欢读代码而不是听我叨叨：

StackOverFlowError occurs when reducing a List（neo4j）：

issue：https://github.com/neo4j/neo4j/issues/12683

pr：https://github.com/neo4j/neo4j/commit/8336c2f75f4baa4283babe31293899020092d5d1

fix crash when the expression exceed the depth（nebula）：https://github.com/vesoft-inc/nebula/pull/3606

代码分析

在这两个 PR 中都提到了 StackOverFlow。我们先试着描述一下问题，Nebula 的 pr 要稍微好懂一点：可以试着打开测试用例来看之前有问题的语句，是一堆 1+1+1+…+1+1

as result, 当+1+1 这样的语法要素出现的次数太多时，会报栈溢出。通过阅读 parser.yy 可以看到，对于每个加法符号，都会生成一个表达式对象：

// parser.yyexpression_internal：constant_expression {       $$ = $1;   } ...   | expression_internal PLUS expression_internal {       $$ = ArithmeticExpression::makeAdd(qctx->objPool(), $1, $3);   } static ArithmeticExpression* makeAdd(ObjectPool* pool,                                      Expression* lhs = nullptr,                                      Expression* rhs = nullptr) {   return pool->add(new ArithmeticExpression(pool, Expression::Kind::kAdd, lhs, rhs)); }

复制代码

对于像“1+1+1+1+1”这样的表达式，调用栈就会成这样：

当用户输入的+1 的数目比较多时，头部 expression 下就会链式挂载若干个子 expression，如果在语法解析层和语法执行层没有对表达式做特殊的处理，这些子链会被递归调用（即父 expression 会调用子 expression），递归的深度取决于子链的数目。

neo4j 的 issue 有些小众，其关注的是对这样自定义聚集操作的语句：

unwind range(0,15000) as xxxwith collect([xxx]) as set1with reduce(c = [], x in set1| c + x) as fromNodesunwind fromNodes as x return x

复制代码

其中 range(0,15000)会生成一个列表，共 15000 个元素，如[0,1,2,…,14998,14999]这样。unwind 会对这个链表进行展开，通过 collect([xxx])对每个元素生成一个独立的列表并打包成 set1([0],[1],…[14998],[14999])，然后通过 reduce 操作对这些独立的元素进行拼接。问题就是出在拼接的时候：reduce 看起来是不断在进行 foreach（x in set1）{c = c + x}这样的操作，然而实际代码实现时，对 15000 个元素进行了展开，生成的是 c=x0+x1+x2+…+x14999。并没有使用一个变量去缓存 c 的中间状态，而是试图通过不断的二元计算直接算出 c 的结果。代码如下：

// CypherMath.Addif ( lhsIsListValue && rhs instanceof ListValue ){    return VirtualValues.concat( (ListValue) lhs, (ListValue) rhs );}// VirtualValues.concatpublic static ListValue concat( ListValue... lists ){    return new ListValue.ConcatList( lists );}

复制代码

这样会有 15000 个 ConcatList 链式连接，实际计算时 15000 个 ConcatList 被递归调用，生成了一个深为 15000 的函数调用栈。

上述代码的问题和 PR 中的解决方案

可以看到，不管是 C++的 nebula，还是 java 写的 neo4j，通过巧妙地构造查询语句，都可以使得内部执行时生成深度较深的函数调用栈。而函数调用栈的深度，在不同编程语言下都是有限制的（大部分查询语言栈空间是 M 级的，参见附录[1]和附录[2]）。超过这个限制，轻则直接导致语句崩溃，如果系统的异常处理机制不够完善，也可能导致更严重的问题。

nebula 和 neo4j 对这个问题采用了两种不同的解决方案。在 nebula 中，通过在 parser.yy 中调用 checkExprDepth 方法，去检查最大递归调用深度，超出则报错；而在 neo4j 中，通过构建一个 list 来缓存 concat 的元素列表，进而消除了递归调用。

// neo4j更新list的代码，解析语句阶段，原始list调用add方法，会生成一个包含value元素的新的list，这个新list会替换调原始的listpublic ListValue add( ListValue value ){    var newSize = lists.length + 1;    var newArray = new ListValue[newSize];    System.arraycopy( lists, 0, newArray, 0, lists.length );    newArray[lists.length] = value;    return new ConcatList( newArray);}

复制代码

容易发现 nebula 的解决方案更直接一点，过深的调用栈一律拒绝；而 neo4j 则是通过一些容器（如 List，Stack）等消除了递归调用，对用户更加友好，但是如果其他地方也出现类似情况，可能需要做针对性修改。

PR 带来的启示

在查询语言的解析和计划执行的编码设计阶段，为查询语句中的某个语法成分（如表达式、函数、子句）编写执行逻辑的代码往往是相对直观且易于理解的。比如加法操作可以直接构造一个 ArithmeticExpression 对象，List 拼接可以直接构造一个 ConcatList 对象。然而由于用户输入的不确定性，需要考虑多个语法成分联动，或者某几个语法成分批量出现时带来的问题（例如深度过深的递归）。要么像 nebula 一样在量上做限制，量太大直接报错；要么像 neo4j 一样针对每个会因为批量联动带来问题的点给出不会出错的编码设计。通过这两种手段，可以减少极端语句对系统的影响，提高系统的健壮性。