快速准确的C/C++语法搜索 - Trail of Bits博客
搜索，但带有上下文
Syntex解决了传统模式搜索工具的两个主要问题。
首先，现有工具容易产生假阴性。这些工具通常包含自己的解析器，根据搜索的代码库语言使用。对于C和C++代码库，这些工具通常在未执行宏扩展的情况下解析源代码，搜索非宏扩展代码而不是像Clang这样的真实编译器产生的宏扩展代码。这意味着这些工具无法确保准确的结果。这类工具的客户端无法自信地说"这里是这种模式的所有出现"或"这种模式从未出现"。理论上，这些工具可以匹配非宏扩展代码中宏的使用，但实际上，它们只能匹配顶层的宏使用，这意味着很可能出现假阴性。
这些工具的另一个问题是它们的内部解析器不使用与真实编译器相同的代码表示，并且它们不理解源代码的语义。也就是说，这些工具产生纯文本输出突出显示它们的结果，因此无法提供关于结果出现代码的语义信息。没有这样的信息，很难进一步分析输出，特别是使用其他分析工具。严格来说，访问这些工具内部解析的源代码并非不可能，但在需要访问仅编译器可用的语义信息的多阶段分析管道中，这不会特别有用。所有这些严重限制了这些工具作为使用其他分析工具更深入分析给定代码的基础的有用性。
例如，假设我们试图找到在某个风险函数的参数列表中字符串长度被隐式截断的代码。我们可能让工具搜索模式$func($... $str->len $...)。该工具可能会找到我们实际关心的代码片段的超集。我们应该能够语义过滤这些搜索结果，检查len是否是感兴趣的结构字段，并且它的使用引起了隐式向下转换。然而，我们选择的任何工具都无法进行这种过滤，因为它只理解代码的结构，而不是语义。而且由于缺乏语义理解，更难引入其他分析工具来帮助进一步分析结果。
Syntex通过在实际的Clang AST上操作来解决这两个问题。因为Syntex使用与编译器相同的AST，它消除了典型模式搜索工具的不准确性，并为进一步分析提供语义信息。Syntex产生带有AST节点引用的结果，允许开发人员进行后续语义分析。例如，枚举上述向下转换模式的客户端将能够基于对应于func和str的子匹配的类型和性质做出决策。
Syntex针对索引代码匹配语法模式
解析C和C++代码是一项众所周知的困难任务，因为它需要实现无限制的前瞻和执行图灵完备的模板才能获得解析树。Syntex通过依赖Clang解决解析源代码的问题，但它如何解析Syntex查询本身？
除了包含以$为前缀的元变量的查询外，Syntex查询在语法上是有效的C和C++代码。理想情况下，我们会用Clang解析Syntex查询，然后统一解析的查询和解析的源代码以识别匹配。不幸的是，生活并不那么容易：Syntex查询缺乏允许它们被解析的必要语法/语义上下文。例如，模式foo(0)根据foo的类型产生不同的解析树。
Syntex不直接解决C和C++语法的边缘情况；相反，它在解析查询时考虑所有可能的模糊解释。然而，Syntex不是自己定义模糊语言模式，而是从Clang编译器的AST派生其模式语法。使用这种方法，我们可以保证模式将被接受用于索引源代码中出现的每个构造。
合成语法
在代码构建和索引时，Syntex通过递归遍历Clang AST并记录AST节点之间的关系来创建上下文无关语法。有子节点的节点对应于非终结符；每个这样的节点的出现添加形式为parent -> child_0 ... child_n的产生式规则。没有子节点的节点成为生成语法中的终结符。例如，对应于图1中AST的语法（产生式规则和终结符）如下：
|
|
如果我们将DECL_STMT解释为此语法的"开始符号"，那么语法是确定性的，并且可以使用常用的LR算法生成接受字符串的解析器。然而，在解析搜索查询时，Syntex实际上不知道查询应该归约到的开始符号。例如，如果查询由IDENTIFIER令牌组成，那么Syntex可以将该令牌解析为IDENTIFIER、包含标识符的DECL_REF_EXPR或包含DECL_REF_EXPR的IMPLICIT_CAST_EXPR。这意味着，在实践中，Syntex假设每个符号都可能是开始符号，并根据它们是否覆盖整个输入查询追溯推导哪些规则是开始规则。
解析Syntex查询
从概念上讲，解析查询的第一步是执行令牌化（或词法分析）。Syntex使用手编码的状态机执行令牌化。Syntax的令牌化器与典型编译器中使用的令牌化器的一个区别是，Syntex的令牌化器返回输入字符的所有可能解释，而不仅仅是最贪婪的解释。例如，Syntex会将字符串"«“令牌化为«和两个连续的<符号。这样，令牌化器不必知道在哪种上下文中需要哪种解释。
Syntex使用记忆化图表解析器针对合成模式语法解析查询。记忆化防止解析过程导致（可能）指数运行时间复杂性，并且生成的记忆表用作查询解析森林的内存中表示。匹配器（在下一节中描述）使用此表来找出哪些索引的AST与查询匹配。这种方法意味着Syntex不必为查询的每个可能解释具体化显式树。图2展示了查询字符串”++i"的记忆表。
该表显示索引0处的字符串可以解释为令牌+或++，并且产生式规则UNARY_OPERATOR -> PLUS_PLUS DECL_REF_EXPR在此索引处匹配。为了获得该匹配，解析器在看到上述产生式的左角可以匹配PLUS_PLUS后，递归地获取索引2处的解析。有了这些知识，它可以向前枚举产生式并得出结论，它完全匹配直到索引3。
查找匹配
在查询的解析表填充后，Syntex需要定位索引源代码中查询的所有解释的出现。此过程从表中索引0处且下一个索引是输入长度的所有条目开始；这些条目对应于覆盖整个输入字符串的解析。
Syntex的匹配算法在专有的Clang AST序列化格式上操作。序列化的AST被反序列化为内存中的树。反序列化过程构建树节点类型（对应于语法符号）到反序列化节点的索引，这使得Syntex能够快速发现可能与查询的根语法符号匹配的候选者。递归统一算法成对应用于每个匹配候选者和查询的每个可能解析。算法下降树，检查节点类型和它们出现的顺序，并在实际令牌本身处终止。
对于图2中的查询"++i"，Syntex在具有符号UNARY_OPERATOR的AST节点处开始匹配。在这种情况下，我们知道产生这样的节点的唯一方法是使用规则体PLUS_PLUS DECL_REF_EXPR。首先，匹配器确保上述AST节点具有正确的结构：有两个子节点，一个PLUS_PLUS和一个DECL_REF_EXPR。然后，Syntex递归地对这些节点重复相同的过程。例如，对于PLUS_PLUS子节点，Syntex确保它是一个拼写为"++“的令牌节点。
附加功能和示例用法
Syntex的一个重要功能，在上面长度截断示例中简要显示，是它在查询中支持"元变量”。例如，当指定诸如"++i"的查询时，匹配器将只找到名为i的变量的递增表达式。然而，如果我们指定"++$“作为查询，那么Syntex将找到递增任何内容的表达式。元变量也可以被命名，例如在查询”++$x"中，允许客户端按名称（x）检索匹配的子表达式以进行进一步处理。此外，Syntex允许对元变量应用约束，例如在查询"++$x:DECL_REF_EXPR"中；有了这些约束，Syntex将只匹配对引用声明的表达式x的递增。查询中的约束在表达性上有限，这就是为什么C++ API允许附加任意C++函数作为谓词，决定接受或拒绝可能匹配的候选者。
另一个重要功能，也在上面长度截断示例中显示，是通配操作符"$…"。它允许用户指定诸如"printf($…)“的查询。当想要匹配未知数量的节点时，通配操作符很有用。通配操作符语义既不是贪婪的也不是惰性的。这部分是因为Syntex生成的语法的非传统性质：手编码的语法可能通过递归规则压缩类似列表的重复，而Syntex语法通过不同的规则明确表示每个观察到的列表长度。因此，具有一个参数的printf调用由与具有五个参数的printf调用不同的规则匹配。因为Syntex可以"看到"所有这些不同长度的不同规则，它能够用通配表达有趣的模式，例如"printf($… i $…)"，它将找到在参数列表中某处出现i的所有printf调用。
最后思考
Syntex的方法在传统语法模式搜索工具中是独特的：搜索引擎包含很少的语言特定代码，并且很容易推广到其他编程语言。使用Syntex的唯一要求是它需要能够访问产生每个AST节点的令牌。在我的原型中，C和C++ AST来自PASTA。
Syntex已经超过了开源和/或公开可用替代品的能力，例如Semgrep和weggli。然而，Syntex还没有"完成”。下一步是开发Syntex，使其搜索不完全存在的源代码文本。C++语言最强大的功能之一是它的模板：它们允许程序员描述通用数据结构的形状和涉及它们的计算。这些模板配置有在编译时用具体类型或值替换的参数。这种称为"模板实例化"的替换创建了从未编写过的代码变体。在Syntex的未来版本中，我们计划使C++模板实例化可语法搜索。我们对此功能的愿景依赖于Clang将AST节点漂亮打印回源代码的能力，这将为我们提供语法构建过程所需的代码。
最后但并非最不重要的是，我要感谢Trail of Bits在我实习期间提供处理如此有趣的研究项目的机会。我还要感谢Peter Goodman的项目想法和在整个过程中的指导。