白盒分析利器-代码属性图CPG-评估顺序图EOG详解

引言

语言前端在对源码进行转换后，生成AST，然后转换为一种初步的CPG格式数据，这种初步的CPG数据在Pass阶段经过一系列的操作，丰富CPG的节点及边的信息，我们本文要讲的EOG（Evaluation Order Graph）评估顺序图就是Pass阶段的一环，EOG在Pass阶段处于相对靠前的位置，之前讲到的ControlFlowSensitiveDFGPass（数据流图构建）、以及日后要讲的ControlDependenceGraphPass（控制依赖图构建）都要依赖于EOG去做。

一、EOG概念

The Evaluation Order Graph (EOG) is built as edges between AST nodes after the initial translation of the code to the CPG. Its purpose is to follow the order in which code is executed, similar to a CFG, and additionally differentiate on a finer level of granularity in which order expressions and subexpressions are evaluated. Every node points to a set of previously evaluated nodes (prevEOG) and nodes that are evaluated after (nextEOG). The EOG edges are intra-procedural and thus differentiate from INVOKES edges. In the following, we summarize in which order the root node representing a language construct and its descendants in the AST tree are connected.

解释如下：

评估顺序图（EOG）是在将代码初步转换为 CPG 之后，在 AST 节点之间建立的边。其目的是遵循代码执行的顺序，类似于 CFG，此外还能以更细的粒度区分表达式和子表达式的评估顺序。每个节点都指向一组之前边：preEOG和nextEOG（这与之前讲的DFG结构类似）。EOG 是方法内的概念，不涉及方法调用。

EOG会针对以下类型及其所有子类节点构建

• NamespaceDeclaration

• TranslationUnitDeclaration

• RecordDeclaration

• FunctionDeclaration

二、EOG与CFG的区别

• diff1：对于没有显式return语句的方法，EOG 将会构建一条虚拟边，这条边指向行号为 -1 的虚拟返回节点；CFG 则以最后一条reachable（可达）语句结束，不会插入虚拟返回语句

• diff2：EOG 会将代码块 Block 作为一个单独的节点；CFG 则会使用代码块中的第一条实际可执行语句作为起点

• diff3：对于 if 语句，EOG 将 if 关键字和condition（条件）视为单独的节点；CFG 则将其视为同一个 if statement

• diff4：EOG 将method header（方法头）视为节点；CFG 将把方法的第一条可执行语句视为节点

tips: EOG 在我们真正使用过程中很少直接用他去做分析，其更多的是为其他图的构建做基础（如：DFG、PDG等），再加上EOG与CFG（控制流图）很类似，只有一些特殊节点的处理有差异。

因此，关于EOG的分析不会像DFG那样将所有类型的节点都展开做详细分析，我只挑其与CFG的差异化处理部分、以及常见使用场景做讲解。

对CFG（控制流图）的构建不熟悉的同学可以参考这篇文章：

SAST-数据流分析方法-理论

三、EOG的构建

tips: 以下测试过程均采用图数据库Neo4j，通过浏览器可视化生成的效果，对Neo4j不熟悉的同学建议阅读：

Neo4j（待修改，加链接）

在分类讨论之前，不妨先验证一下其是否是方法内的概念

测试代码：

`package com.test;      public class TestFunCall {       public static void main(String[] args) {           test("SASTing");       }       public static void test(String a) {           System.out.println("Hello " + a);       }   }   `

以上代码转换后的CPG如下：

• EOG做了红色加粗渲染

• DFG做了蓝色渲染

• 黄色节点是方法声明

img

仔细观察其实可以发现，两个方法声明test、main之间是没有EOG边的，找不到一条从test出发能够到达main的EOG边，反之亦然，这也证明了EOG确实是一个方法内的概念，其并不涉及方法间的边传递。

1.FunctionDeclaration

EOG构建规则：

• parameters: List<ParameterDeclaration>: 方法参数

• defaultValue: Expression: 参数的默认值（可选）

• body: Statement: 方法体

img

测试代码：

`package com.test;      public class TestFunctionDecl {          public void nonReturn(String a, int b) {          }   }   `

生成的CPG如下：

img

黄色节点就是方法声明nonReturn

上面的那个空白节点就是一个虚拟节点，isImplicit=true，节点属性如下：

img

Java中不支持给方法的参数赋默认值的操作，所以其他边暂时就看不到啦，这种处理是为了处理支持参数默认值的语言。

2.IfStatement

EOG的构建如下图（各节点见名知意，就不详细展开说明了）：

img

测试代码：

`public boolean check(String str) {       if (str.contains("SASTing")) {           return true;       }       else {           return false;       }   }   `

转换后的CPG如下：

img

通过转换后的效果可以看到，以下边均可得到验证：

• initializerStatement --> condition|conditionDeclaration

• condition|conditionDeclaration  -> IfStatement

• IfStatement --> thenStatement

• IfStatement --> elseStatement

3.CallExpression

EOG构建规则如下：

• callee：被调方法

img

测试代码：

`public class TestCallExpression {          public static void main(String[] args) {           Caller caller = new Caller();           caller.callee(args[0]); // CallExpression       }   }      class Caller {       public void callee(String name) {          }   }   `

生成的CPG如下：

img

通过观察上文提到的EOG构建规则图，可以发现，其实就是生成了这样一条边（为了看起来直观，我们此处只讨论一个传参的情况）：

• callee --> argument --> CallExpression

再对比生成的可视化CPG图，可以直观地看到CallExpression的caller、callee及argument之间的EOG边的构建方式，是满足上述规则描述的

4.ForStatement

EOG构建方式：

• initializerStatement  循环开始前的初始化语句 （第一个分号前的初始化语句）

• condition  循环条件 (第一个分好后的条件语句)

• conditionDeclaration  条件声明

• statement  循环体

• iterationStatement  每次循环完后要执行的语句（最后一个分号后的语句）

img

测试代码：

`public class TestForStatement {       public void test() {           int a = 0;           int i;           for(i=0; i<10; i++) {               a += i;           }       }   }   `

生成的CPG如下（部分节点已隐藏）：

img

这张图看起来挺复杂，但莫慌，让笔者带你拆解他！

我们先把这张图划分一下：

img

这么看是不是就清晰多了

我们再看其EOG的构建规则，其有以下几条边：

• iterationStatement --> condition  （对应上图的  ++节点 --> i节点）

• initializerStatement --> condition  （对应上图的  =节点 --> i节点）

• condition --> ForStatement  （对应上图中的 <节点 --> ForStatement节点）

• 其余从ForStatement出去的两条边也存在，为了不影响整体的观看效果，笔者已将其隐藏，大家可自行验证

5.TryStatement

EOG构建规则如下图：

• resources:Listtry块中需要的值

• tryBlock:Block try代码块

• finallyBlock:Block finally代码块

• catchBlocks:List<Block> catch代码块

img

测试代码：

`public class TestTry {       public void test() {           try {               throwExceptionMethod();           } catch (IllegalArgumentException e) {               e.printStackTrace();           } finally {               System.out.println("finished");           }       }          private void throwExceptionMethod() throws IllegalArgumentException {          }   }   `

生成的CPG如下（已隐藏部分节点及边）：

img

现在来拆分这张图：

img

划分模块后，可以很直观地看到以下几条边：

• try --> finally

• catch --> finally

• resources --> try

推荐阅读

代码属性图CPG系列文章（白盒/静态代码分析方向）：超万字的详细讲解，文章理论与实践相结合，示例代码可拿来即用，通俗易懂，这样的文章你爱了吗！ 

• 抽丝剥茧代码属性图CPG-第一弹：CPG介绍

• 抽丝剥茧代码属性图CPG-第四弹：CPG中的DFG-3

• SAST-短小精悍的Benchmark

能够看到这篇文章，就是我们的缘分，坚持输出优质内容是笔者一直在做的事情。若文章对你有帮助，感谢点个免费的 点赞、在看，大家的鼓励是我最大的动力

点个关注，不后悔