佛山建设局网站国外网站设计参考

当前位置： 首页 > news >正文

佛山建设局网站,国外网站设计参考,国外酷网站,宁波比较好的外贸公司cpg 是一个跨语言代码属性图解析工具#xff0c;它目前支持C/C (C17), Java (Java 13)并且对Go, LLVM, python, TypeScript也有支持#xff0c;在这个项目的根目录下: cpg-core为cpg解析模块的核心功能#xff0c;主要包括将代码解析为图#xff0c;core模块只包括对C/C/Ja…cpg 是一个跨语言代码属性图解析工具它目前支持C/C (C17), Java (Java 13)并且对Go, LLVM, python, TypeScript也有支持在这个项目的根目录下: cpg-core为cpg解析模块的核心功能主要包括将代码解析为图core模块只包括对C/C/Java的支持。 cpg-analysis为基于代码属性图的代码分析规则比如ValueEvaluator主要基于DFG的回溯遍历计算某一表达式的值。 cpg-neo4j将解析结果导入到neo4j数据库。 cpg-language-xxx为对xxx语言的支持。 cpg-console包含针对用户端的功能比如bug检测:OutOfBoundsCheck,NullPointerCheck。
cpg将编程语言抽象为1个特性(Trait)集合语言特性是一组编程语言所共有的特性或特性。任何支持它们的语言都应该实现所需的trait接口。示例可以是对指针的支持、对模板或泛型的支持。 1.Graph Structure 这一部分主要介绍cpg提供的图结构这些结构旨在提供大多数面向对象语言如C、Java或Go中的语言特性的超集。这包括结构元素例如函数、方法、类以及表达式/语句例如调用、运算符、文本或条件。 1.1.Abstract Syntax Tree 树的根是TranslationUnitDeclaration节点它表示一个文件中包含的代码。树中存在不同类型的AST子节点每个子节点表示程序中的不同语义 Structural Entities 表示为代码提供其结构的实体。比如代表 namespaces, classes, structs 的结点。 Value Declarations 用于建模局部变量、参数、函数、方法和构造函数。 Nodes of Program Execution 它为语句和表达式建模。 语句是按顺序执行的语法单元因此构成命令式程序的程序逻辑。 相比之下表达式是计算值的语法单位属于特定的值类型。表达式可以是嵌套的也可以是语句的子级。
1.2.Control Flow and Evaluation Order cpg将控制流图CFG的概念改编为评估顺序图evaluation order graph, EOG它按照语句和表达式被求值的顺序相互连接以在更细粒度级别上表示控制流。这对于正确捕获来自表达式内部执行顺序的副作用是必要的。可以说EOG是expression-level CFG。 比如对下面代码: int a 2 3; a 0; a 1;EOG为: 绿框为3个语句对应的AST根节点蓝框为其下AST子结点。 蓝线连接同一语句下的AST结点绿线连接不同语句的AST结点。
可以看出 EOG的连接顺序为AST结点后序遍历顺序 连接的结点都是对应的表达式或者语句访问顺序。
通常EOG的构造对应后序遍历当然也存在一些例外情况 显式更改程序控制流的构造函数如 if 或其他条件表达式。 表示不按代码出现的顺序执行的代码的节点例如在 for (initializer; condition; iteration) body(); 中 body(); 在 initializer 之后执行在 iteration 之前执行。
分支语句的根节点在分支表达式例如条件或选择器之后和分支目标之前连接以允许已经遍历分支表达式的算法在必须处理分支之前获得关于语义根的信息。 对于下面分支代码: if (a 4)a 2; elsea 3; return 0;其EOG如下: 1.3.Data Flow 处理数据的操作或实体在CPG内的数据流图DFG中表示。要对程序中的数据流进行建模以下DFG边连接节点 (1).如果父结点的值取决于子结点的值则子对象包含其父结点的边。比如 BinaryOperator:2 3 指向其父结点 VariableDeclaration:a 2 3。 (2).如果语句对被引用变量进行写入那么被引用变量是DF edge的起始结点如果语句读取被引用变量那么被引用变量是DF edge的开始。比如 a 1; if (a 4) xxx 中存在从 DeclaredReferenceExpression: a(a 1; 中的 a) 指向 BinaryOperator: a 4 的DF edge。 (3).函数调用时会建立从 CallExpression 对应的被引用变量到被调用参数之间的DF edge以及被调用者定义和该 CallExpression 之间也会建立DF edge如下面示例所示: DeclaredReferenceExpression 和 ParamVariableDeclaration 之间有数据流FunctionDeclaration 和 CallExpression 之间也有数据流。 绿边为data flow edge 蓝边为普通AST edge这里只包含了部分AST信息 (4).如果控制流敏感control-flow-sensitive的数据流分析被执行那么对于一个变量 (DeclaredReferenceExpression)在它最后一次被写入的地方和对应引用的位置会有1条数据流 (5).对于控制流不敏感的数据流分析变量引用 (DeclaredReferenceExpression)和变量定义VariableDeclaration之间存在数据流。
对于具体DFG建立规则可以参考cpg DFG 1.4.Additional program semantics 程序和所用语言的类型系统是通过添加其复杂的层次结构作为节点和边来建模的形成一个类型子图这有助于通过允许根据细微差别的语言语义进行区分对语言级语义进行建模以提高精度。 REFERS_TO 连接引用和定义。(每个 DeclaredReferenceExpression 都有1个成员变量refersTo指向对应变量定义的位置) INVOKES 连接调用语句和调用对象。每个 CallExpression 都有成员变量invokeEdges指向其可能的调用对象。
2.核心架构和实现 CPG项目由围绕一个库构建的多个工具组成用于以基于Java/Kotlin的开源实现3的形式对源代码进行迭代图形构建。图1描述了将源代码转换为图形表示的工作流以及用户对其进行的可视化和分析。 代码解析的核心部分由 cpg-core 完成用户输入由 cpg-console 完成。 2.1.语言前端(Language Frontends) 源代码文件通过其文件扩展名发送到特定语言的前端。然后前端可以使用针对特定语言的AST解析库解析源代码(针对C/C使用eclipse CDT针对Java采用Java Parser)。语言前端应执行以下任务: 特定语言的AST被转换为独立于语言的cpg AST结构以方便建立独立于特定语言的图结构 隐式存在但未位于源代码中的实体将显式添加到图中例如隐式 this 字段和缺少的返回语句(void 函数比如下面代码片段中 swap 函数在解析后补充了 ReturnStatement:return;)
void swap(int *p, int *q) {int t *p;*p *q;*q t; }int main() {int a 2, b 1;swap(a, b);int c a 1;return 0; }标识符被收集在scope tree中以便以后以模糊的方式解析对名称的访问。在cpg AST的每个结点中都有一个局部变量scope指向一个Scope对象每个 scope 对象会用1个ASTNode来标识。以上面代码为例: 整个代码对应的TranslationUnitDeclaration 会对应到一个GlobalScope(记作 globalScope)对象中该 GlobalScope 对象对应的ASTNode就是该 TranslationUnitDeclaration swap 和 main 函数对应的 FunctionDeclaration 的 scope 域指向 globalScope swap 和 main 函数定义下的 CompoundStatement(函数体) 的 scope 域分别指向2个FunctionScope(分别记作 functionScope1, functionScope2)functionScope1, functionScope2 对应的ASTNode分别为2个 FunctionDeclaration 结点 int t *p;, int c a 1; 的 scope 域分别指向2个BlockScope这2个 BlockScope 对应的ASTNode分别为2个函数定义下的 CompoundStatement
在 cpg-core 中已经实现了针对C/C/Java的前端而 cpg-language-xxx 实现了针对xxx语言的前端。 2.2.ScopeManager 在大多数编程语言中名称的声明不是全局有效的但其有效性仅限于与语言构造相关的区域例如类或函数。这个有效区域被称为作用域(scope)。当前端遍历AST节点时作用域管理器跟踪当前活动的作用域堆栈。这允许按绝对或相对名称跟踪和解析声明并管理绑定到封闭语言功能例如循环、try 语句范围的控制流跳转。在语言前端构建作用域之后作用域管理器持有多个作用域树。 在全局存在一个ScopeManager对象通过 HashMap 的方式将ASTNode映射为 Scope 2.3.Passes cpg前端产生部分连接的AST树。然后通过隐式执行信息和程序语义如使用引用、数据流和求值顺序使用Passes来丰富cpg。 比如: DFGPass负责生成DFG。 ControlFlowSensitiveDFGPass负责生成control-flow sensitive DFG。 EvaluationOrderGraphPass负责生成EOG。
这些语义是在独立于语言的AST节点之间构建的并且它们本身独立于特定编程语言。然而它们仍然允许特定语言的定制。 当需要graph中的语义时某些 Pass 取决于其他 Pass 的先前执行。比如 ControlFlowSensitiveDFGPass 依赖于 DFGPass, EvaluationOrderGraphPass。后2者只遍历了AST而 ControlFlowSensitiveDFGPass 还需遍历EOG。 最后Pass 也支持推理。对于在源代码中不直接可见的实体节点将被添加并标记为 IMPLICIT如果缺少源代码则为 INFERRED 3.程序分析 cpg在 cpg-analysis 下定义了一些程序分析规则包括计算表达式的值、不可达代码分析等等。基本是通过图的遍历实现的这里就介绍以下表达式求值。 表达式求值有点类似于常量传播不过区别在于这里是通过Data Flow Graph的遍历实现对应的代码为 ValueEvaluator.evaluate具体规则参考evaluateInternal函数(还有1个更高级的版本MultiValueEvaluator): 返回值主要为常量值或者 canNotResolve如果不能确定值的变量那么返回的可能就是 canNotResolve。 如果访问的AST结点为 Literal类型那么直接返回其值。 如果是 DeclaredReferenceExpression那么沿着DFG回溯这里需要注意的是data flow必须唯一如果有多个DFG边指向该变量引用也就是该变量可能值有多个那么返回 canNotResolve。 对于算术运算表达式则先分别计算其左右值如果不是 canNotResolve那么直接计算其值。
4.Bug检测 这一部分为cpg的部分用户功能放在 cpg-console 模块中。 cpg目前支持2种类型的bug检测,out of bound和空指针访问这2种bug clang static analyzer(CSA)已有实现不过CSA基于符号执行cpg基于data flow graph的反向遍历。 4.1.Out of Bound Check CSA中的实现可参考知乎介绍clang对应的代码为ArrayBoundCheckerArrayBoundCheckerV2。 可以检查出由数组访问造成的溢出读写比如 array[idx] 1;但是数组访问必须满足以下条件 idx 必须是常量表达式索引可以用变量但是其值必须是常量 数组长度必须是常量且长度通过 new Type[n]; 定义n 为常量表达式
首先给出以下示例: #include iostream using namespace std;int main() {int *a new int[9 1];int i 10;int idx i 1;a[idx] 13;return 0; }其中有几个比较重要的AST结点类型: ArrayCreationExpression: 表示由 new Type[n] 组成的AST结点比如: ArraySubscriptionExpression:表示数组访问语句 array[index], array 和 index 都属于 Expression 类通常为 DeclaredReferenceExpression VariableDeclaration: 变量定义结点在图1中已有示例 DeclaredReferenceExpression: 变量引用结点表示对变量的使用每个 DeclaredReferenceExpression 都会有一个成员变量 refersTo 指向定义该变量的 VariableDeclaration 结点。比如图2中的 DeclaredReferenceStatement: a 指向图1中的 VariableDeclaration: *a new int[9 1];
检查数组越界访问按以下方式进行检查对象为 ArraySubscriptionExpression 结点对于某一个 ArraySubscriptionExpression: 取出改数组表达式的索引示例中为图2 DeclaredReferenceStatement:idx计算其值示例中值为 11如果不是常量则退出。 找到表达式数组对应的 DeclaredStatementExpression示例中为图2 DeclaredStatementExpression:a找到其对应的 VariableDeclaration示例中为图1 VariableDeclaration: *a new int[9 1];查找有没有 ArrayCreationExpression没有则退出int a[100]; 这种语句都不行。 Type[n] 中的 n 对应着数组长度表达式计算其值示例中为 10不是常量则退出。 比较索引和长度的值如果索引 长度则报出越界访问。
参考第3部分表达式的计算核心是回溯DFG对于计算索引 idx 的值上述示例比较重要的DFG包括下面4个计算的过程是从最后1个data flow往前回溯 VariableDeclaration:i 10 ——– DeclaredReferenceExpression:i其中 VariableDeclaration:i 10 对应的 initializer 为 Literal: 10因此 DeclaredReferenceExpression:i 的结果为 10 VariableDeclaration:idx i 1 ——– DeclaredReferenceExpression:idx (从语句 int idx i 1; 指向 a[idx] 13;)计算idx时追溯到 VariableDeclaration:int idx i 1对应的 initializer 为 BinaryOperator: i 1左值为 DeclaredReferenceExpression:i右值为 Literal:1递归回溯后左值结果为 10因此 DeclaredReferenceExpression:idx 的值为 11
没有用到的data flow包括: Literal:10 ——– VariableDeclaration:i 10 BinaryOperator:i 1 ——– VariableDeclaration:idx i 1
同理可以计算出 a 的长度为 10因此存在越界访问。 4.2.Null Pointer Check CSA中的实现可参考NullabilityChecker GoSSIP团队也在CSA的基础上实现了新的空指针解引用检测算法NewDereferenceChecker。 在cpg中空指针的检测规则比较简单如果出现指针访问数组成员变量成员方法对其对应指针变量 base 进行求解如果可能为 nullptr必须由 nullptr 初始化NULL 和默认初始化都不行。 求解是对 base 变量所有的DFG前驱进行求解下面示例也会检测出 s-i 1; 存在空指针访问这是由于存在错误数据流 VariableDeclaration:*s nullptr ——– DeclaredReferenceExpression:s(line 11) struct S1 {char c1; //1个字节int i; //4个字节char c2; // 1个字节 };int main() {struct S1 *s nullptr; // 可以识别nullptr关键字,NULL不行s new S1();s-i 1;return 0; }5.参考文献 paper地址 article{Weiss_A_Language-Independent_Analysis_2022,author {Weiss, Konrad and Banse, Christian},doi {10.48550/arXiv.2203.08424},title {{A Language-Independent Analysis Platform for Source Code}},year {2022} }