程序安全第三讲控制流分析

2023/9/261第三讲控制流分析3.1抽象语法树基本结构3.2程序控制流图控制流图定义控制流图构造控制流图遍历2023/9/2623.1抽象语法树基本结构1.源程序示例#include<stdio.h>intmain(){ intf0,f1,f2,i； intm,r; f0=0;f1=1;m=5; if(m<1){r=m;} else { i=2; while(i<=m){f2=f0+f1;f1=f2;i++;} r=f2; } printf(“%d”,r) return0;}2023/9/2632.文本抽象语法树（.tu文件）

@2786function_declname:@2791type:@2792srcp:b.c:2body:@2793 @2793bind_exprtype:@107vars:@2797body:@2798 @2797var_declname:@2803type:@3scpe:@2786srcp:b.c:4chan:@2804 @2804var_declname:@2818type:@3scpe:@2786srcp:b.c:4chan:@2819 @2819var_declname:@2832type:@3scpe:@2786srcp:b.c:4chan:@2833 @2833var_declname:@2851type:@3scpe:@2786srcp:b.c:4chan:@2820 @2820var_declname:@2834type:@3scpe:@2786srcp:b.c:5chan:@2827 @2827var_declname:@2848type:@3scpe:@2786srcp:b.c:5 @2798statement_list0:@28051:@28062:@28073:@28084:@28095:@2810 6:@28117:@28128:@28139:@281410:@2815 @2811modify_exprtype:@3op0:@2797op1:@1783 @2812modify_exprtype:@3op0:@2804op1:@1795 @2813modify_exprtype:@3op0:@2820op1:@2821 @2814cond_exprtype:@107op0:@2822op1:@2823

op2:@2824 @2815call_exprtype:@3fn:@28250:@2826

1:@2827 @2822le_exprtype:@3op0:@2820op1:@1783 @2823modify_exprtype:@3op0:@2827op1:@2820 @2824statement_list0:@28351:@28362:@2837

3:@28384:@28395:@2840 6:@28417:@28428:@28439:@284410:@2845 @2835modify_exprtype:@3op0:@2833op1:@2852 @2836goto_exprtype:@107labl:@2853 @2837label_exprtype:@107name:@2854 @2838modify_exprtype:@3op0:@2819op1:@2855 @2839modify_exprtype:@3op0:@2797op1:@2804 @2840modify_exprtype:@3op0:@2804op1:@2819 @2841postincrement_exprtype:@3op0:@2833op1:@1795 @2842label_exprtype:@107name:@2853 @2843cond_exprtype:@107op0:@2856op1:@2857op2:@2858 @2844label_exprtype:@107name:@2859 @2845modify_exprtype:@3op0:@2827op1:@2819 @2856le_exprtype:@3op0:@2833op1:@2820 @2857goto_exprtype:@107labl:@2854 @2858goto_exprtype:@107labl:@28592023/9/2643.抽象语法树

对文本形式的抽象语法树进行化简解析形成以某种数据结构存储的内存中的抽象语法树。

具体抽象语法树参见文件“抽象语法树.doc”。2023/9/2653.2程序控制流图

2023/9/266

在众多的程序安全的静态检测中，分析程序首要的任务是发现程序的控制结构。程序的控制结构在源程序中是显而易见的，而在抽象语法树（或其他中间表示）中就不是那么明显了。这时，控制流分析的作用就凸现出来了，而控制流分析的前提就是构造程序的控制流图。

下面介绍如何生成待检测程序的控制流图，根据程序的控制流图模拟出程序运行时的执行路径，从而为准确确定程序的上下文执行环境、检测代码中存在的安全问题打下基础。1.控制流图定义

定义基本块：是一个最大化的指令序列，程序执行只能从这个序列的第一条指令进入，从这个序列的最后一条指令退出。

确定基本块的原则： 1)遇到程序、子程序的第一条指令或标号语句，结束当前基本块，并将该语句作为一个新块的第一条语句。 2)遇到goto语句、分支语句、循环语句，将该语句作为当前块的最后一条语句，并结束当前块。 3)遇到其他语句直接将其加入到当前基本块。

2023/9/267

定义控制流图CFG(ControlFlowGraph)：是以基本块为结点的有向图G=(N,E)，其中N是结点集合，表示程序中的基本块；E是边的集合，如果从块U的出口转向块V，则从U到V有一条有向边UV，表示从结点U到V存在一条可执行路径，称U为V的前驱结点，V为U的后继结点。也就代表在执行完结点U中的代码语句后，有可能顺序执行结点V中的代码语句。

常见控制语句对应的控制流图：2023/9/2682023/9/269源程序intfib(intm){intf0=0,f1=1,f2,i;if(m<=1){returnm;}else{for(i=2;i<=m;i++){f2=f0+f1;f0=f1;f1=f2;}returnf2;}}中间表示receivemf0←0f1←1ifm<=1gotoL3i←2;L1:ifi<=mgotoL2returnf2L2:f2←f0+f1f0←f1f1←f2i←i+1gotoL1L3:returnm控制流图2.控制流图构造

根据构造的抽象语法树，生成对应的程序控制流图。

1)基本块识别

根据基本块的定义，基本块中语句只能有一条执行路径，因此识别基本块的首要任务是判断那些语句会产生多条路经。而程序中引起多条执行路径的语句包括：分支语句、循环语句、goto语句、break语句、continue语句和return语句。

分析由GCC产生的文本文件及构造的抽象语法树，可以发现，以上语句在抽象语法树中的表现形式如下：2023/9/2610cond_expr:表达式e入当前块，结束当前块，两个后继分别是S1和S2构成的块。return_expr:该语句入当前块，结束当前块，后继为exit块。goto_expr和label组合：goto_expr结束当前块，label_expr开始新块；块的后继或前驱由语句中的标号确定。2023/9/2611源程序语句抽象语法树语句if(e)S1elseS2@2814cond_exprop0:eop1:S1op2:S2while(e)doS@2836goto_exprlabl:L3@2837label_exprname:L1@2838S@2842label_exprname:L3@2843cond_exprop0:eop1:gotoL1op2:gotoL2@2844label_exprname:L2gotoL@2836goto_exprlabl:Lbreak@2836goto_exprlabl:Lcontinue@2836goto_exprlabl:Lreturne@2816return_exprexpr:e

2)数据结构说明

构造的控制流图可以用多叉树或链表等数据结构存储。无论哪种存储方式，控制流图结点中存放的语句序列都不是源程序形式的，而是抽象语法树形式的中间表示。

例如采用兄弟孩子链表存储控制流图，则结点结构可以如下定义 structCFGNode{ char*nodeSeq; StmNode*stmPointer; CFGNode*childPointer; CFGNode*brotherPointer; }

2023/9/26122023/9/2613数据结构示例 3)算法描述

输入：抽象语法树；输出：控制流图 CreateCFG算法的基本过程： 1)初始化：若该过程为第一次调用，则申请生成整个数据流图的入口结点entry、出口结点exit和空节点cfg_node，设置entry的后继结点为cfg_node，并把cfg_node设为当前块； 2)初始化：若该过程为第一次调用，则设label栈和goto栈为空； 3)foreachASTNodein抽象语法树中的所有结点do { switch(ASTNode) {goto_expr: {该语句存入当前块，结束当前块；

在label栈中查找该goto语句的目标标号:

若找到：将当前块的孩子指针指向找到的label所在块；

若找不到：将当前块的指针及goto语句的目标标号存入

goto栈；

创建一个空结点作为当前块; break;}

2023/9/2614 label_expr: {结束当前块，创建一个空结点作为当前块，并将该语句作为块的第一条语句；

将前一块的孩子指针指向该块；

在goto栈中查找label语句的标号：

若找不到：将该块的指针及label标号存入label栈；

若找到：将找到的块的孩子指针指向该块； break;} cond_expr: {将条件放入当前块，结束当前块；

分别递归调用CreateCFG创建then和else部分的控制流图，并将创建的两个流图的头指针作为当前块的孩子；

创建一个空结点作为当前块，并将then和else部分创建的控制流图中未指定后继的块的孩子指针指向当前块； break;}

2023/9/2615

return_expr: {该语句存入当前块，结束当前块；

将该块的孩子指针指向exit结点；break;}简单语句(call