基础概念

我在记录调试分析joern源码的过程中，学到了一些关于java的新知识，为了能够方便自己后面回顾，所以先记录下一些基础概念：

  1. 重载overload：重载是在一个类里面，方法名字相同，而参数不同。返回类型可以相同也可以不同。每个重载的方法（或者构造函数）都必须有一个独一无二的参数类型列表。最常用的地方就是构造器的重载。

  2. 重写override：重写是子类对父类的允许访问的方法的实现过程进行重新编写, 返回值和形参都不能改变。即外壳不变，核心重写！重写方法不能抛出新的检查异常或者比被重写方法申明更加宽泛的异常。例如： 父类的一个方法申明了一个检查异常 IOException，但是在重写这个方法的时候不能抛出 Exception 异常，因为 Exception 是 IOException 的父类，只能抛出 IOException 的子类异常。

  3. Statement：statement的例子有（for循环，if条件句）

  4. Expression：expression的例子有（函数调用，变量之间的运算）

如果你能将一串代码作为参数传递，那么这就能被称为expression。

  1. Statement和Expression之间的关系：所有的expression都是Statement，反之则不成立。expression可以作为右值，但是statement不可以。简单来说，expression是可以用eval来求值的东西，statement则不一定。可以参考这篇问答：https://stackoverflow.com/questions/4728073/what-is-the-difference-between-an-expression-and-a-statement-in-python 。
1
2
3
4
>function foo(expression)
   {
   	statement;
   }

条件句基本结构

最常见的条件句就是if（或者是if-else）条件语句。

官方手册

if条件句官方手册：https://www.php.net/manual/zh/control-structures.if.php

官方中给出的最常见的if条件句结构：

1

一个最简单的例子，下面的php代码if_normal.php表示，如果firstName不为空，那么$name就设为$firstName，否则就设为Guest：

1
2
3
4
5
6
<?php
if (!empty($firstName)) 
    $name = $firstName;
else
    $name = "Guest";
?>

生成的代码属性图为：

2

从中抽取出CFG为：

3

程序的控制流一共有两条路径（数字表示id）：

1
2
2 -> 7 -> 11 -> 22 -> 3
2 -> 7 -> 18 -> 22 -> 3

我们知道，在控制流图中，有CFG_FUNC_ENTRY和CFG_FUNC_EXIT，其中，CFG_FUNC_EXIT结点的前一个node通常是一个null结点，控制流会汇聚在null node，最后通过null node流向CFG出口结点CFG_FUNC_EXIT。

上图中id=7的结点它的type = AST_UNARY_OP，说明了这是一个一元操作运算符，flags = UNARY_BOOL_NOT，说明该一元操作运算符是!。

在joern/projects/extensions/joern-php/src/main/java/inputModules/csv/PHPCSVNodeTypes.java的PHPCSVNodeTypes类中，就定义了几种flags来区分不同的操作运算符：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class PHPCSVNodeTypes
{
	// flags for TYPE_UNARY_OP nodes (exclusive)
    // 一元操作运算符 !
	public static final String FLAG_UNARY_BOOL_NOT = "UNARY_BOOL_NOT";
    // 一元操作运算符 ~
	public static final String FLAG_UNARY_BITWISE_NOT = "UNARY_BITWISE_NOT";
    // 一元操作运算符 +
	public static final String FLAG_UNARY_MINUS = "UNARY_MINUS"; // since version 20 of php-ast
    // 一元操作运算符 -
	public static final String FLAG_UNARY_PLUS = "UNARY_PLUS"; // since version 20 of php-ast
	// 一元操作运算符 @
    public static final String FLAG_UNARY_SILENCE = "UNARY_SILENCE"; // since version 20 of php-ast
}

nodes.csv

8

rels.csv

7

cpg_edges.csv

根据nodes.csv和rels.csv生成的对应的cpg_edges.csv为：

0

根据rels.csv得到的ast结构为，严格来说，[0]号结点类型是Artificial，并不是AST类型的：

10

根据该AST树转成的CFG图为：

24

if条件句解析流程分析

Main.java

首先，从AST树的id=1的结点开始，调用ASTToCFGConverter.convert将AST对象转化为CFG对象：

9

因为是PHP源码，所以ASTToCFGConverter.setFactory会将ASTToCFGConverter.factory设置为PHPCFGFactory，那么第23行调用的就是PHPCFGFactory.convert()：

11

并且传入的参数node对象的类型为FunctionDef，但上面第21行的node类型是FUnctionDefBase，因为后者是前者的父类：

12

我们可以看到，无论是子类FunctionDef还是父类FunctionDefBase，其实归根结底都是一种ASTNode。

PHPCFGFactory & CFGFactory

PHPCFGFactory类中有重载（overload）方法 newInstance()来处理不同的statement：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package cfg;

import ...

public class PHPCFGFactory extends CFGFactory {
	
	// node id offsets for entry and exit nodes of function definitions
	private static final int CFG_ENTRY_OFFSET = 1;
	private static final int CFG_EXIT_OFFSET = 2;
	
	static {
		structuredFlowVisitior = new PHPStructuredFlowVisitor();
	}

	public PHPCFGFactory() {
		structuredFlowVisitior = new PHPStructuredFlowVisitor();
	}
	
    // 处理FunctionDef node结点
	@Override
	public CFG newInstance(FunctionDefBase functionDefinition) { ... }
	
    // 处理if条件语句
	public static CFG newInstance(IfStatementBase ifStatement) { ... }

    // 处理if条件句内的元素结点
	private static CFG convertIfElem(Iterator<IfElement> iterator) { ... }

    // 处理switch语句
	public static CFG newInstance(SwitchStatement switchStatement) { ... }
	
    // 处理foreach语句
	public static CFG newInstance(ForEachStatement forEachStatement) { ... }

    // 处理try...catch语句
	public static CFG newInstance(TryStatement tryStatement) { ... }
}

其中newInstance(FunctionDefBase functionDefinition)重写了父类CFGFactory的CFGFactory.newInstance(FunctionDefBase functionDefinition)，区别在于，在返回父类CFGFactory生成的cfg之后，还需要设置entry node和exit node的id，分为设置为2和3，并将entry node的类型转为CFGEntryNode，exit node的类型转为CFGExitNode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class PHPCFGFactory extends CFGFactory {
	
    ......
        
	@Override
	public CFG newInstance(FunctionDefBase functionDefinition)
	{
        // 调用父类CFGFactory.newInstance(FunctionDefBase functionDefinition)生成CFG
		CFG cfg = super.newInstance(functionDefinition);
		
		// for PHP, we additionally set the node ids for the function entry and exit nodes:
		// their ids match the ids of the entry and exit nodes output by the PHP AST parser
		Long id = functionDefinition.getNodeId();	// 获取func的rootnode id，为1
        // 为entry node和exit node设置id，分别为2和3，同时将其类型转化为CFGEntryNode和CFGExitNode
		((CFGEntryNode)cfg.getEntryNode()).setNodeId( id + CFG_ENTRY_OFFSET);
		((CFGExitNode)cfg.getExitNode()).setNodeId( id + CFG_EXIT_OFFSET);
		
		return cfg;
	}
}

和PHPCFGFactory一样，CFGFactory也存在对cfg实例化方法newInstance()的重载（overload）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package cfg;

import ...

public class CFGFactory
{
	protected static StructuredFlowVisitor structuredFlowVisitior;

	public CFG newInstance(FunctionDefBase functionDefinition) { ... }

	public static CFG newInstance(ASTNode... nodes) { ... }

	public static CFG newErrorInstance() n{ ... }


	public static CFG newInstance(WhileStatement whileStatement) { ... }

	public static CFG newInstance(ForStatement forStatement) { ... }

	public static CFG newInstance(DoStatement doStatement) { ... }

	public static CFG newInstance(TryStatement tryStatement) { ... }

	public static CFG newInstance(SwitchStatement switchStatement) { ... }

	public static CFG newInstance(ParameterList paramList) { ... }

	public static CFG newInstance(CompoundStatement content) { ... }

	public static CFG newInstance(ReturnStatement returnStatement) { ... }

	public static CFG newInstance(GotoStatement gotoStatement) { ... }

	public static CFG newInstance(Label labelStatement) { ... }

	public static CFG newInstance(ContinueStatement continueStatement) { ... }

	public static CFG newInstance(BreakStatement breakStatement) { ... }

	public static CFG newInstance(ThrowStatement throwStatement) { ... }

	public static CFG convert(ASTNode node) { ... }

	public static void fixBreakStatements(CFG thisCFG, CFGNode target) { ... }

	public static void fixContinueStatement(CFG thisCFG, CFGNode target) { ... }

	private static void fixBreakOrContinueStatements(CFG thisCFG, CFGNode target, Iterator<CFGNode> it) { ... }

	public static void fixGotoStatements(CFG thisCFG) { ... }

	public static void fixReturnStatements(CFG thisCFG) { ... }
}

CFGFactory.newInstance(FunctionDefBase functionDefinition)

我们跟入到CFGFactory.newInstance(FunctionDefBase functionDefinition)：

13

上图中第44行的断点处：

1
CFG function = newInstance();

它的作用是生成一个最小单位的CFG，一个最小单位的CFG只包含两个结点，一个entry node，一个exit node，表示为：

1
2
[ENTRY] { [ENTRY] ==[]==> [EXIT] , }
[EXIT] {  }

前面我们说到，无论是子类FunctionDef对象，还是它的父类FunctionDefBase对象，其实它们都是一种ASTNode。一般来说，下面几种类型的ASTNode会成为FunctionDefBase functionDefinition：

1
2
3
4
5
6
7
8
public class PHPCSVNodeTypes
{
	// declaration nodes
	public static final String TYPE_TOPLEVEL = "AST_TOPLEVEL"; // artificial
	public static final String TYPE_FUNC_DECL = "AST_FUNC_DECL";
	public static final String TYPE_METHOD = "AST_METHOD";
	public static final String TYPE_CLOSURE = "AST_CLOSURE";
}

在单php文件中，只要存在多个函数定义，就有可能存在多个FunctionDefBase类型结点，因为该类型就是用来区分函数块的。

FunctionDefBase

接着继续分析，程序执行到下一行，此时已经执行了functionDefinition.getParameterList()，但未执行convert()函数：

15

functionDefinition.getParameterList()返回的结果是null。

这是什么意思？

我们来看一下FunctionDefBase类，它有两个成员变量：

1
2
3
4
5
public abstract class FunctionDefBase extends ASTNode
{
	protected ParameterList parameterList = null;
	protected CompoundStatement content = null;
}

分别为类ParameterList和类CompoundStatement。

FunctionDeBase.ParameterList

其中ParameterList是一种ASTNode List：

16

ParameterList类有一个成员变量parameters，是一个LinkedList，它用来存储类型为ParameterBase的结点：

1
2
3
4
public class ParameterList extends ASTNode implements Iterable<ParameterBase>
{
	private LinkedList<ParameterBase> parameters = new LinkedList<ParameterBase>();
}

ParameterBase类是Parameter的父类，一般函数中的参数类型就是ParameterBase（更具象来说是Parameter），那ParameterList的作用主要维护一个函数中的类型为ParameterBase的函数参数。它们的关系如下图所示：

18

FunctionDefBase.CompoundStatement

然后是CompoundStatement，简单来说就是一种复合类型的Statement。CompoundStatement通常包含更小的CompoundStatement。

用一个最简单的例子来描述ParamterList和CompoundStatement：

17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public CFG newInstance(FunctionDefBase functionDefinition)
{
    try
    {
        // function是最小的CFG，也是CFG的起始
        CFG function = newInstance();
        // 若functionDefinition对应的代码是非函数式的，那么functionDefinition.getParameterList()最后返回的是null，parameterBlock最后也是一个仅包含entry node和exit node的最小CFG
        CFG parameterBlock = convert(
            functionDefinition.getParameterList());
        // 处理函数体里的语句内容，对于非函数PHP文件，则是处理从<?php后面的语句内容
        CFG functionBody = convert(functionDefinition.getContent());
        parameterBlock.appendCFG(functionBody);
        function.appendCFG(parameterBlock);
        fixGotoStatements(function);
        fixReturnStatements(function);
        if (!function.getBreakStatements().isEmpty())
        {
            System.err.println("warning: unresolved break statement");
            fixBreakStatements(function, function.getErrorNode());
        }
        if (!function.getContinueStatements().isEmpty())
        {
            System.err.println("warning: unresolved continue statement");
            fixContinueStatement(function, function.getErrorNode());
        }
        if (function.hasExceptionNode())
        {
            function.addEdge(function.getExceptionNode(),
                             function.getExitNode(), CFGEdge.UNHANDLED_EXCEPT_LABEL);
        }

        return function;
    }
    catch (Exception e)
    {
        // e.printStackTrace();
        return newErrorInstance();
    }
}

functionBody生成

接着开始处理最主要的内容，我们可以较为简单的理解为开始处理函数里面的语句，对于无函数的php文件，就是<?php后面对应的语句。

19

其中id=4的结点就是type = AST_STMT_LIST的结点，它通常是很多结点的父结点。

跟进CFGFactory.convert函数，我们会发现这一步主要是根据传进convert函数的node类型来决定StructuredFlowVisitor。

前面我们已经知道，CFG图是由CFGFactory或是PHPCFGFactory类中的重载方法newInstance来决定的，但是不同的结点类型，它们的处理过程也有不同， 那么如何确定某个结点使用哪个newInstance函数来生成该结点对应的CFG呢？这是由StructuredFlowVisitor决定的。这里稍微提一下StructuredFlowVisitor，它是PHPStructuredFlowVistor的父类：

21

StructuredFlowVisitor只处理两种类型的结点，CompoundStatement和其他：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package cfg;

import ...

public class StructuredFlowVisitor extends ASTNodeVisitor
{

	protected CFG returnCFG;

	public CFG getCFG()
	{
		return returnCFG;
	}

	public void visit(CompoundStatement content)
	{
		returnCFG = CFGFactory.newInstance(content);
	}

	public void visit(ASTNode expression)
	{
		returnCFG = CFGFactory.newInstance(expression);
	}
	
}

而在PHPStructuredFlowVisitor中，对StructuredFlowVisitor.visit(ASTNode expression)进行了多次重写，进行了更加细致的处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package cfg;

import ...

public class PHPStructuredFlowVisitor extends StructuredFlowVisitor  {

	@Override
	public void visit(ParameterList paramList)
	{
		returnCFG = CFGFactory.newInstance(paramList);
	}

	@Override
	public void visit(ParameterBase param)
	{
		returnCFG = CFGFactory.newInstance(param);

		for (CFGNode node : returnCFG.getVertices())
		{
			if (!(node instanceof ASTNodeContainer))
				continue;
			returnCFG.registerParameter(node);
		}

	}

	@Override
	public void visit(IfStatementBase node)
	{
		returnCFG = PHPCFGFactory.newInstance(node);
	}

	@Override
	public void visit(Label node)
	{
		returnCFG = CFGFactory.newInstance(node);
	}

	@Override
	public void visit(WhileStatement node)
	{
		returnCFG = CFGFactory.newInstance(node);
	}

	@Override
	public void visit(DoStatement node)
	{
		returnCFG = CFGFactory.newInstance(node);
	}

	@Override
	public void visit(ForStatement node)
	{
		returnCFG = CFGFactory.newInstance(node);
	}

	@Override
	public void visit(ForEachStatement node)
	{
		returnCFG = PHPCFGFactory.newInstance(node);
	}

	@Override
	public void visit(ReturnStatement expression)
	{
		returnCFG = CFGFactory.newInstance(expression);
	}

	@Override
	public void visit(GotoStatement expression)
	{
		returnCFG = CFGFactory.newInstance(expression);
	}

	@Override
	public void visit(SwitchStatement node)
	{
		returnCFG = PHPCFGFactory.newInstance(node);
	}

	@Override
	public void visit(ContinueStatement expression)
	{
		returnCFG = CFGFactory.newInstance(expression);
	}

	@Override
	public void visit(BreakStatement expression)
	{
		returnCFG = CFGFactory.newInstance(expression);
	}

	@Override
	public void visit(TryStatement node)
	{
		returnCFG = PHPCFGFactory.newInstance(node);
	}

	@Override
	public void visit(ThrowStatement node)
	{
		returnCFG = CFGFactory.newInstance(node);
	}

}

这段的执行流程为：

20

id=4, type=AST_STMT_LIST的结点，它有一个id=5, type=AST_IF的子结点，子结点类型为IfStatement，在403行的代码由两部分组成：

1
2
CFG tmp_CFG = convert(statement);
compoundBlock.appendCFG(tmp_CFG);

convert()函数的作用和流程还和之前一样，不一样的地方只是PHPStructuredFlowVistitor.visit会根据传入的结点类型进行不同的处理，目的就是找到正确的PHPCFGFactory.newInstance()来处理结点：

22

PHPCFGFactory.newInstance(IfStatement ifStatement)

对于类型为IfStatement的结点，对应的PHPCFGFactory.newInstance()为newInstance(IfStatement ifStatement)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class PHPCFGFactory extends CFGFactory {
    
    ......
        
	public static CFG newInstance(IfStatementBase ifStatement)
	{
		try
		{
            // IfStatementBase是IfStatement的父类
			IfStatement phpIfStatement = (IfStatement)ifStatement;
			
            // IfStatement对应的AST结点属性有type=AST_IF，而其IfStatement.iterator()会返回子结点，也就是AST结点属性为type=AST_IF_ELEM的子结点
			Iterator<IfElement> iterator = phpIfStatement.iterator();
			if(!iterator.hasNext())
				return newErrorInstance();

            // type=AST_IF_ELEM的结点是交由convertIfElem来处理的
			CFG ifElemCFG = convertIfElem(iterator);
			return ifElemCFG;
		}
		catch (Exception e)
		{
			// e.printStackTrace();
			return newErrorInstance();
		}
	}
    
    ......
    
}

我们知道，在关系图中，type=AST_IF的结点会根据分支语句的数量，有对应数量的type=AST_IF_ELEM的子结点，而IfStatement.iterator()会返回type=AST_IF（结点类型为IfStatement）对应个数的子结点，该子结点type=AST_IF_ELEM，类型为IfElement：

23

与普通结点不一样，IfElment结点转化为CFG不是由PHPCFGFactory.convert来处理，而是PHPCFGFactory.convertIfElem来说处理。

PHPCFGFactory.convertIfElem: if-block

跟入PHPCFGFactory.convertIfElem(Iterator<IfElement> iterator)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
public class PHPCFGFactory extends CFGFactory 
{    
    ......
        
	private static CFG convertIfElem(Iterator<IfElement> iterator)
	{
        // 新建一个仅包含entry node和exit node最小的CFG块
		CFG block = new CFG();
		
        // 取出IfElement结点
		IfElement ifElem = iterator.next();
        /*
		获取下列if条件句
		if (expression) {
			statement1;
		} else {
			statement2;
		}
		中的expression
		 */
		Expression condition = ifElem.getCondition();
        /*
		获取下列if条件句
		if (expression) {
			statement1;
		} else {
			statement2;
		}
		中的statement1
		 */
		Statement statement = ifElem.getStatement();
        // 将statement1对应的结点转为CFG
		CFG ifBlock = convert(statement);


		if(condition == null)
		{
			// this is the 'else' case
            // [My Annotation]:
            /* condition对应的是下面if else-if
            if (expression1) {
            	statement1;
            } else if (expression2) {
            	statement2;
            } else {
            	statement3;
            }
            中的expression1和expression2
            如果是else block,那自然能就变成了null
            所以是null就说明这是一个else block
            */
			return ifBlock;
		}

		CFGNode conditionContainer = new ASTNodeContainer(
				condition);

        /*
        CFGFactory.newInstance(ASTNode... nodes)
        public static CFG newInstance(ASTNode... nodes)
        {
            try
            {
                CFG block = new CFG();
                CFGNode last = block.getEntryNode();
                for (ASTNode node : nodes)
                {
                    CFGNode container = new ASTNodeContainer(node);
                    block.addVertex(container);
                    block.addEdge(last, container);
                    last = container;
                }
                block.addEdge(last, block.getExitNode());
                return block;
            }
            catch (Exception e)
            {
                // e.printStackTrace();
                return newErrorInstance();
            }
        }
        给某个结点生成CFG的步骤就是
        1. new ASTNodeContainer
        2. addVertex
        3. addEdge
        */
		block.addVertex(conditionContainer);
		block.addEdge(block.getEntryNode(), conditionContainer);

		block.mountCFG(conditionContainer, block.getExitNode(), ifBlock,
				CFGEdge.TRUE_LABEL);

		if(iterator.hasNext())
		{
			CFG elseBlock = convertIfElem(iterator);
			block.mountCFG(conditionContainer, block.getExitNode(),
					elseBlock, CFGEdge.FALSE_LABEL);
		}
		else
		{
			block.addEdge(conditionContainer, block.getExitNode(),
					CFGEdge.FALSE_LABEL);
		}

		return block;
	}
}

ifElem.getCondition()和ifElem.getStatement()分别会获取下面if条件句中的expr和statement：

1
2
3
4
<?php
if (expr)
  statement
?>

对应我们的例子为：

1
2
3
4
5
6
<?php
if (!empty($firstName))  // [(7) UnaryOperationExpression] => 对应 type = AST_IF的node
    $name = $firstName;	 // [(11) ExpressionStatement] => 对应 type = AST_ASSIGN的node
else
    $name = "Guest";
?>

如果$name = $firstName;是更复杂一点的复合语句，比如：

1
2
$name = $firstName;
echo $name;

那么[(11) ExpressionStatment]就会变成CompoundStatement，因为无论是CompoundStatement还是ExpressionStatement都是继承自Statement：

25

接着将该[(11) ExpressionStatement]转变成CFG对象：

26

对应的ifBlock为：

1
2
3
[ENTRY] { [ENTRY] ==[]==> [(11) ExpressionStatement] , }
[EXIT] {  }
[(11) ExpressionStatement] { [(11) ExpressionStatement] ==[]==> [EXIT] , }

然后将type=AST_IF的结点也转为CFG对象：

27

对应的block为：

1
2
3
[ENTRY] { [ENTRY] ==[]==> [(7) UnaryOperationExpression] , }
[EXIT] {  }
[(7) UnaryOperationExpression] {  }

接着block块调用CFG.mountCFG()将AST_IF和AST_IF_ELEM等分支结点连接起来：

block：代表AST_IF结点对应的CFG对象

conditionContainer：代表AST_IF结点，是一个ASTNode对象

ifBlock：代表AST_IF_ELEM（是if分支语句中的一支）结点对应的CFG对象

28

CFG.mountCFG

跟入CFG.mountCFG，注意调用该函数的是AST_IF结点对应的CFG对象（下面注释中，我就称其为main if block）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Control Flow Graph. Consider this to be the target format of CFGFactories.
 * Please place language specific attributes of the CFG into a sub-class.
 */

public class CFG extends IncidenceListGraph<CFGNode, CFGEdge>
{
    ...
        
	public void mountCFG(CFGNode branchNode, CFGNode mergeNode, CFG cfg,
			String label)
	{
		if (!cfg.isEmpty())
		{
            // 将cfg添加进main if block，但是CFG.addCFG仅仅是将vertex和edge加入，并不会进行连接操作
			addCFG(cfg);
			for (CFGEdge edge : cfg.outgoingEdges(cfg.getEntryNode()))
			{
				addEdge(branchNode, edge.getDestination(), label);
			}
			for (CFGEdge edge : cfg.incomingEdges(cfg.getExitNode()))
			{
				addEdge(edge.getSource(), mergeNode, edge.getLabel());
			}
		}
		else
		{
			addEdge(branchNode, mergeNode, label);
		}
	}
    
    public void addCFG(CFG otherCFG)
	{
        // 将othercfg的vertex加入到main if block中
		addVertices(otherCFG);
        // 将othercfg的edge加入到main if block中
		addEdges(otherCFG);
        
		// 将othercfg中的parameter，breakStatement，continueStatement，returnStatement，gotoStatement和lable都加入到main if block中
		getParameters().addAll(otherCFG.getParameters());
		getBreakStatements().addAll(otherCFG.getBreakStatements());
 		getContinueStatements().addAll(otherCFG.getContinueStatements());
		getReturnStatements().addAll(otherCFG.getReturnStatements());
		getGotoStatements().putAll(otherCFG.getGotoStatements());
		getLabels().putAll(otherCFG.getLabels());
		if (this.hasExceptionNode() && otherCFG.hasExceptionNode())
		{
			CFGExceptionNode oldExceptionNode = getExceptionNode();
			CFGExceptionNode newExceptionNode = new CFGExceptionNode();
			setExceptionNode(newExceptionNode);
			addEdge(oldExceptionNode, newExceptionNode,
					CFGEdge.UNHANDLED_EXCEPT_LABEL);
			addEdge(otherCFG.getExceptionNode(), newExceptionNode,
					CFGEdge.UNHANDLED_EXCEPT_LABEL);
		} else if (otherCFG.hasExceptionNode())
		{
			setExceptionNode(otherCFG.getExceptionNode());
		}
	
	}
    
    private void addEdges(CFG cfg)
	{
		for (CFGNode vertex : cfg.getVertices())
		{
			for (CFGEdge edge : cfg.outgoingEdges(vertex))
			{
				if (!(edge.getSource().equals(cfg.getEntryNode())
						|| edge.getDestination().equals(cfg.getExitNode())))
				{
					addEdge(edge);
				}
			}
		}
	}

	public void addEdge(CFGNode srcBlock, CFGNode dstBlock)
	{
		addEdge(srcBlock, dstBlock, CFGEdge.EMPTY_LABEL);
	}

	public void addEdge(CFGNode srcBlock, CFGNode dstBlock, String label)
	{
		CFGEdge edge = new CFGEdge(srcBlock, dstBlock, label);
		addEdge(edge);
	}
    
    ...
}

29

经过CFG.addCFG()之后，block（即this对象，因为是block对象调用的mountCFG（block.mountCFG()））所代表的AST_IF结点为变成了：

30

然后对block(this)进行连边：

32

它是这样处理的：

31

最后得到的block(this)为：

1
2
3
4
[ENTRY] { [ENTRY] ==[]==> [(7) UnaryOperationExpression] , }
[EXIT] {  }
[(7) UnaryOperationExpression] { [(7) UnaryOperationExpression] ==[True]==> [(11) ExpressionStatement] , }
[(11) ExpressionStatement] { [(11) ExpressionStatement] ==[]==> [EXIT] , }

PHPCFGFactory.convertIfElem: else-block

到上面这一步为止，源码中的下面部分的CFG已经处理了：

1
2
if (!empty($firstName)) 
    $name = $firstName;

但是还有else部分没有处理：

1
2
else
    $name = "Guest";

我们继续跟下去，else对应的type=AST_IF_ELEM结点的类型为IfElement，id为16。对于该else block，也是通过convertIfElement(iterator)来处理的，所以我们看到在101行，调用了convertIfElem(iterator)：

33

递归跟入convertIfElem()，我们知道elseBlock并没有对应的condition，所以condition对象的值肯定为null：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static CFG convertIfElem(Iterator<IfElement> iterator)
{
    CFG block = new CFG();

    IfElement ifElem = iterator.next();
    Expression condition = ifElem.getCondition();
    Statement statement = ifElem.getStatement();
    // 将else block中statement对应的语句转为cfg
    CFG ifBlock = convert(statement);

	// else 语句对应的condition是null
    if(condition == null)
    {
        // this is the 'else' case
        return ifBlock;
    }
    ......
}

因为condition==null，所以直接将ifBlock返回给elseBlock，然后调用block.mountCFG()将elseBlock拼接到main if block中，并且将边标记为CFGEdge.FalseLabel：

34

经过block.mountCFG()得到的CFG为：

1
2
3
4
5
[ENTRY] { [ENTRY] ==[]==> [(7) UnaryOperationExpression] , }
[EXIT] {  }
[(7) UnaryOperationExpression] { [(7) UnaryOperationExpression] ==[True]==> [(11) ExpressionStatement] ,[(7) UnaryOperationExpression] ==[False]==> [(18) ExpressionStatement] , }
[(11) ExpressionStatement] { [(11) ExpressionStatement] ==[]==> [EXIT] , }
[(18) ExpressionStatement] { [(18) ExpressionStatement] ==[]==> [EXIT] , }

return to PHPCFGFactory.newInstance

现在if语句中的主要结点对应的CFG都已经形成了，所以接下来就是进行返回之前的递归调用，可进行收尾处理。

将PHPCFGFactory.convertIfElem(Iterator<IfElement> iterator)的结果返回给PHPCFGFactory.newInstance(IfStatementBase ifStatement)：

35

然后返回到处理id=4的结点（这个结点type=AST_STMT_LIST，是其他AST结点的父亲节点）：

36

type=4的结点即compoundBlock对象，它是最小的CFG单位，将if block（[(5) IfStatement]）添加上去后，还有CFG的汇流点，CFG_FUNC_EXIT的父亲结点，[(22) NullNode]需要处理：

37

利用compoundBlock.appendCFG()将[(5) IFStatement]对应的子CFG和[(22) NullNode]对应的子CFG加入后，得到的CFG结构为：

1
2
3
4
5
6
[ENTRY] { [ENTRY] ==[]==> [(7) UnaryOperationExpression] , }
[EXIT] {  }
[(7) UnaryOperationExpression] { [(7) UnaryOperationExpression] ==[True]==> [(11) ExpressionStatement] ,[(7) UnaryOperationExpression] ==[False]==> [(18) ExpressionStatement] , }
[(11) ExpressionStatement] { [(11) ExpressionStatement] ==[]==> [(22) NullNode] , }
[(18) ExpressionStatement] { [(18) ExpressionStatement] ==[]==> [(22) NullNode] , }
[(22) NullNode] { [(22) NullNode] ==[]==> [EXIT] , }

到这一步，functionBody，也就是函数体的内容语句部分对应的CFG就已经生成了：

38

然后后面还需要处理函数的parameter，因为此次解析的代码并不是函数式的，所以parameterBlock其实也是仅包含enrty node和exit node的最小的CFG块，然后将functionBody加到parameterBlock上，最后将parameterBlock用同样的方式添加到CFG起始块function上。

最后，还需要为entry node和exit node分配id，并将它们的类型转为对应的CFGEntryNode和CFGExitNode（这两个类型都是继承自CFGNode），这样，cfg就生成了。

39

现在得到的cfg为：

1
2
3
4
5
6
[(2) ENTRY] { [(2) ENTRY] ==[]==> [(7) UnaryOperationExpression] , }
[(3) EXIT] {  }
[(7) UnaryOperationExpression] { [(7) UnaryOperationExpression] ==[True]==> [(11) ExpressionStatement] ,[(7) UnaryOperationExpression] ==[False]==> [(18) ExpressionStatement] , }
[(11) ExpressionStatement] { [(11) ExpressionStatement] ==[]==> [(22) NullNode] , }
[(18) ExpressionStatement] { [(18) ExpressionStatement] ==[]==> [(22) NullNode] , }
[(22) NullNode] { [(22) NullNode] ==[]==> [(3) EXIT] , }

最后就是调用csvCFGExporter.writeCFGEdges(cfg)将生成的cfg写入到cfg_edges.csv中：
40

CFG生成小结

从上面的分析流程，其实我们可以看出在生成CFG的过程中，是通过前序遍历的方式来访问每一个AST结点，并将符合要求的结点转为CFGNode对象，添加到CFG中。

画一个比较粗略的执行流程：

if-CFG_generate

后续问题

当然这是最简单的if条件语句，在很多情况下，if条件句可能会被其他运算符替代，比如php中唯一的三元运算符?:和null合并运算符??。

三元运算符 ?:

三元运算符可以用一行代码进行逻辑判断，从而代替常见的if-else变量赋值判断。

null合并运算符 ??

null合并运算符又称为空值合并运算符，它是用于执行isset()检测的三元运算符的快捷方式。NULL 合并运算符会判断变量是否存在且值不为NULL，如果是，它就会返回自身的值，否则返回它的第二个操作数。

这两种特殊的条件语句，它们生成的CPG，其实我们可以猜到，因为缺少if关键字，所以如果joern没有对其进行特殊的处理，是非常有可能无法生成正确的CPG的。这个在后续的学习中会进行测试。