网络教学>第三讲 控制流分析>3.2 程序控制流图

1. 控制流图定义

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

        

         确定基本块的原则:

         1) 遇到程序、子程序的第一条指令或标号语句,结束当前基本块,并将该语句作为一个新块的第一条语句。

         2) 遇到goto语句、分支语句、循环语句,将该语句作为当前块的最后一条语句,并结束当前块。

         3) 遇到其他语句直接将其加入到当前基本块。

          

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

        

         常见控制语句对应的控制流图:

源程序

int fib(int m)

{ int f0=0,f1=1,f2,i;

   if(m<=1){return m;}

   else

    { for(i=2;i<=m;i++)

       { f2=f0+f1;

          f0=f1;

          f1=f2;

       }

       return f2;

    }

}

中间表示

      receive  m

      f0 ← 0

      f1 ← 1

      if m<=1 goto L3

      i ← 2;

L1:if  i<=m goto L2

      return f2

L2:f2 ← f0+f1

      f0 ← f1

      f1 ← f2

      i ← i+1

      goto L1

L3:return  m

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


2. 控制流图构造

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

         1) 基本块识别

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

                   分析由GCC产生的文本文件及构造的抽象语法树,可以发现,以上语句在抽象语法树中的表现形式如下:

源程序语句

抽象语法树语句

if(e)  S1 else S2

@2814   cond_expr  op 0: e    op 1:S1    op 2:S2

while(e)   do  S

@2836   goto_expr    labl: L3

@2837   label_expr       name: L1

@2838   S

@2842   label_expr    name: L3

@2843   cond_expr    op 0: e   op 1:goto L1   op 2: goto L2

@2844   label_expr     name: L2

goto  L

@2836   goto_expr    labl: L

break

@2836   goto_expr    labl: L

continue

@2836   goto_expr    labl: L

return  e

@2816   return_expr      expr: e

cond_expr:表达式e入当前块,结束当前块,两个后继分别是S1S2构成的块。

return_expr:该语句入当前块,结束当前块,后继为exit块。

goto_exprlabel组合:goto_expr结束当前块,label_expr开始新块;块的后继或前驱 由语句中的标号确定。

2) 数据结构说明

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

                   例如采用兄弟孩子链表存储控制流图,则结点结构可以如下定义

                   struct CFGNode{

                            char  *nodeSeq;

                            StmNode *stmPointer;

                            CFGNode *childPointer;

                            CFGNode *brotherPointer;

                            }

数据结构示例

 

 

 

 

 

 

 

 

 

 

 

 


3)算法描述

         输入:抽象语法树;输出:控制流图

         CreateCFG算法的基本过程:

         1)初始化:若该过程为第一次调用,则申请生成整个数据流图的入口结点entry、出口结点exit和空节点cfg_node,设置entry的后继结点为cfg_node,并把cfg_node设为当前块;

         2)初始化:若该过程为第一次调用,则设label栈和goto栈为空;

         3)foreach ASTNode  in  抽象语法树中的所有结点 do

            {   switch(ASTNode)

                    {    goto_expr:

                               {该语句存入当前块,结束当前块;

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

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

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

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

                            break;}

 

label_expr:

         {结束当前块,创建一个空结点作为当前块,并将该语句作为块的第一条语句;

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

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

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

                            若找到:将找到的块的孩子指针指向该块;

                          break;}

                   cond_expr:

                        {将条件放入当前块,结束当前块;

         分别递归调用CreateCFG创建thenelse部分的控制流图,并将创建的两个流图的头指针作为当前块的孩子;

         创建一个空结点作为当前块,并将thenelse部分创建的控制流图中未指定后继的块的孩子指针指向当前块;

                          break;}

return_expr:

                        {该语句存入当前块,结束当前块;

                          将该块的孩子指针指向exit结点;break;}

简单语句(call_expr/modify_expr/preincrement_expr/ postincrement_expr/predecrement_expr/     postdecrement_expr)

                        {直接将该语句加入当前块;break;}

                   范围语句(bind_exprstatement_list):

                        {break;}

                   var_decl:

                        {根据需要决定是否加入控制流图;break;}

               }

   }

4)控制流图中没有后继的结点的孩子指针指向exit结点;

5)释放labelgoto栈;

3.控制流图遍历

                   控制流图是系统后续工作的基础,在检测代码中的安全缺陷等操作时需要遍历控制流图,模拟程序的执行路径,根据操作类型提取相关的变量信息,并依此检测代码中存在的安全缺陷。

                   遍历控制流图最为重要的两种方法是深度优先遍历和广度优先遍历,此外还有先序遍历和后序遍历等。在进行代码检测时需要根据需要采用不同的遍历策略。无论采用哪种遍历方法,在访问控制流图的结点时,都需要提取程序的属性信息(例如指针变量信息)并根据这些信息进行安全检测。