[原创]带你搞懂数据流分析的原理以及实现

2021-5-14 15:50 8998

[原创]带你搞懂数据流分析的原理以及实现

sfftlt

2021-5-14 15:50

8998

带你搞懂数据流分析的原理以及实现

前言

数据流分析是软件分析中静态分析中比较重要的一部分，结合符号执行、污点分析、fuzzing技术可以发挥巨大的效用。本文从原理到实现讲解数据流分析的具体实现。

本文的例子来自https://github.com/petablox/cis573vm,其中还有许多关于软件分析的demo，大家有兴趣的可以去玩一下，对于理解相关技术机理有很大的帮助。

我实验过程中采用的LLVM版本是10.0.0，z3版本是4.8.11-64bit。

实验过程的原理是基本的可达定义(reaching defenition)，b站上的南京大学软件分析原理教学视频有相关内容。

我浅显的理解（纯小白，大佬勿喷）是数据流分析就是先将二进制文件处理成3AC code,然后我们根据自定义规则处理3ac code，生成约束表达式，循环迭代达到不动点，然后用z3求解器求解最终得到结果。

LLVM 3AC code基本指令

首先要知道我们需要处理的基本的3ac code有哪几种

访存指令

load [volatile] <ty>, <ty>* <pointer>
store [volatile] <ty> <value>, <ty>* <pointer>
<result> = getelementptr inbounds <ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}

跳转指令

1 2	`br i1 <cond>, label <iftrue>, label <iffalse> ;条件跳转` `br label <dest> ;无条件跳转`

sdiv指令

1	`<result>` `=` `sdiv i32` `4,` `%var ; yields i32:result` `=` `4` `/` `%var`

call指令

1	`%call` `=` `call i32 (...) @tainted_input()`

自定义关系

实验框架中定义了Def、Use关系，针对Reaching Definition Analysis定义了Kill、Gen、Next、In、Out关系，针对Taint Analysis定义了Taint、Edge、Path、Sanitizer、Div、Alarm关系，其中每个关系的具体含义如下,接下来，需要对这些关系定义相应的规则，并将其添加进Z3求解器中求解。

// Relations for Def and Use
Def(X,Y): Variable X is defined at instruction Y  (define X by Y)
Use(X,Y): Variable X is used at instruction Y  (use X at Y)
 
// Relations for Reaching Definition Analysis
Next(X,Y): Instruction Y is an immediate successor of instruction X  (next X is Y)
Kill(X,Y): Definition X is killed by instruction Y  (kill X by Y) 
Gen(X,Y): Definition Y is generated by instruction X  (define Y by X)
In(X,Y): Instruction Y may reach the program point just before instruction X  (in X is Y)
Out(X, Y) :- Definition Y may reach the program point just after instruction X  (out X is Y)
 
// Relations for Taint Analysis
Taint(X): There exists a function call at instruction X that reads a tainted input
Sanitizer(X): There exists a function call at instruction X that sanitizes a tainted input
Div(X,Y): There exists a division operation at instruction Y whose divisor is variable X  (div X at Y)
Alarm( I ) :- There exists a potential exploitable divide-by-zero error at instruction I  
Path(I, J) :- There exists a transitive tainted data-flow from instruction I to J
Edge(I, J) :- There exists an immediate data-flow from instruction I to J

规则定义

规则定义主要分为两部分，第一部分为Reaching Definition Analysis，第二部分为Taint Analysis。

Reaching Definition Analysis

为Kill定义如下rule，如果变量X在指令Y处被定义，而后又在指令Z处被定义，那么认为定义Y被指令Z Kill，形式化表示如下：

Kill(Y, Z) :- Def(X, Y) & Def(X, Z)

为Out定义如下两条rules，第一条为如果定义Y被指令X生成，那么认为定义Y可以到达指令X后；第二条为如果定义Y可以到达X之前，并且定义Y没有被指令X Kill，那么认为定义Y可以到达指令X之后，形式化表示如下：

Out(X, Y) :- Gen(X, Y)

Out(X, Y) :- In(X, Y) & !Kill(Y,X)

为In定义如下rule，如果定义Y可以到达指令Z之后，并且指令Z的下一条指令为X，那么认为定义Y可以到达指令X之前，形式化表示如下：

In(X, Y) :- Out(Z,Y) & Next(Z, X)

Taint Analysis

为Edge定义如下rule，如果变量X在指令Y处被定义，并且变量X在指令Z处被使用，并且定义Y可以到达指令Z之前，那么认为存在一个从指令Y到Z的直接的数据流，形式化表示如下：

Edge(Y, Z) :- Def(X, Y) & Use(X, Z) & In(Z,Y)

为Path定义如下两条rules，第一条为如果指令I和指令J之间存在直接的数据流，并且在指令I位置处读取了受污染的输入，那么认为指令I和指令J之间传递受污染的数据流；第二条为如果指令I和指令J之间传递受污染的数据流，并且指令J和指令K之间存在直接的数据流，并且在指令J处没有对数据流进行清洗，那么认为指令I和指令K之间传递受污染的数据流，形式化表示如下：

Path(I, J) :- Edge(I,J) & Taint(I)

Path(I, K) :- Path(I,J) & Edge(J,K) & !Sanitizer(J)

为Alarm定义如下rule，如果在指令I和指令Y之间传递受污染的数据流，并且在指令Y处使用变量K作为除数，那么认为指令Y处存在潜在的可利用的除零错误，形式化表示如下：

Alarm( Y ) :- Path(I, Y) & Div(K,Y)

定义rule以及将rule添加进Z3求解器代码实现如下：

z3::expr X = C.bv_const("X", 32);
z3::expr Y = C.bv_const("Y", 32);
z3::expr Z = C.bv_const("Z", 32);
z3::expr kill_rule = z3::forall(X, Y, Z, z3::implies(Def(X, Y) && Def(X, Z), Kill(Y, Z)));
z3::expr out_rule1 = z3::forall(X, Y, z3::implies(Gen(X,Y), Out(X,Y)));
z3::expr out_rule2 = z3::forall(X, Y, z3::implies(In(X,Y) && !Kill(Y,X), Out(X,Y)));
z3::expr in_rule = z3::forall(X, Y, Z, z3::implies(Out(Z,Y) && Next(Z,X), In(X,Y)));
 
 
z3::expr edge_rule = z3::forall(X, Y, Z, z3::implies(Def(X,Y) && Use(X,Z) && In(Z,Y), Edge(Y,Z)));
z3::expr path_rule1 = z3::forall(X, Y, z3::implies(Edge(X,Y) && Taint(X), Path(X,Y)));
z3::expr path_rule2 = z3::forall(X, Y, Z, z3::implies(Path(X,Y) && Edge(Y,Z) && !Sanitizer(Y), Path(X,Z)));
z3::expr alarm_rule = z3::forall(X, Y, Z, z3::implies(Path(X,Y) && Div(Z,Y), Alarm(Y)));
 
Solver->add_rule(kill_rule, C.str_symbol("kill_rule"));
Solver->add_rule(out_rule1, C.str_symbol("out_rule1"));
Solver->add_rule(out_rule2, C.str_symbol("out_rule2"));
Solver->add_rule(in_rule, C.str_symbol("in_rule"));
Solver->add_rule(edge_rule, C.str_symbol("edge_rule"));
Solver->add_rule(path_rule1, C.str_symbol("path_rule1"));
Solver->add_rule(path_rule2, C.str_symbol("path_rule2"));
Solver->add_rule(alarm_rule, C.str_symbol("alarm_rule"));

Fact提取

首先将simple0.c转换为llvm 3AC code如下：

可以看到几个主要的指令为store、load、call、div指令，那么先对这几个指令提取fact。

store指令

store指令格式为store [volatile] <ty> <value>, <ty>* <pointer>，包含Value Operand、Point Operand，利用StoreInst类，根据定义添加Def、Use、Gen关系，具体如下：

if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
    Value *From = SI->getValueOperand();
    Value *To = SI->getPointerOperand();
    std::cout <<"From:"<<toString(From)<<" to:"<<toString(To) << "\n";
    addGen(InstMap, SI, SI);
    addDef(InstMap, To, SI);
    addUse(InstMap, From, SI);
}

load指令

Load指令格式为loadIns: load [volatile] <ty>, <ty>* <pointer>，利用LoadInst类，同样根据定义添加Def、Use、Gen关系，具体如下：

// loadIns: load [volatile] <ty>, <ty>* <pointer>
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
    std::cout << toString(LI->getPointerOperand()) <<"\n";
    std::cout << toString((Value *)&*I) << "\n";
    addDef(InstMap, LI, LI);
    addUse(InstMap, LI->getPointerOperand(), LI);
    addGen(InstMap, LI, LI);
}

call指令

对于call指令，根据函数名称，对于是否行taint函数、Sanitizer函数进行判断，利用CallInst类，根据定义添加Gen、Def关系，实现如下：

if (CallInst *CI = dyn_cast<CallInst>(I)) {
    std::cout << toString(I->getOperand(0)) <<"\n";
    if (isTaintedInput(CI)) {
        addTaint(InstMap, CI);
    }
    if (isSanitizer(CI)) {
        addSanitizer(InstMap, CI);
    }
    if (CI->getCalledFunction()->getName().equals("not_sanitizer")) {
        addTaint(InstMap, CI);
    }
    if (CI->getCalledFunction()->getName().equals("untainted_input")) {
        addSanitizer(InstMap, CI);
    }
    addGen(InstMap, CI, CI);
    addDef(InstMap, CI, CI);
}

sdiv指令

对于sdiv指令，由于没有专门的类处理sdiv指令，所以利用Instruction类中的getOpcodeName()函数根据指令名称进行判断，根据定义添加div、use关系，具体实现如下：

if(!memcmp(I->getOpcodeName() ,"sdiv",4)){
    Value * dividend = I->getOperand(0);
    Value * divisor = I->getOperand(1);
    addDiv(InstMap,divisor,I);
    addUse(InstMap,divisor,I);
    addUse(InstMap,dividend,I);
}

并且我们需要记录下每次处理指令，这样方便添加Next关系，具体实现如下：

if(Pre_Inst != NULL) {
    addNext(InstMap, Pre_Inst, I);
}
Pre_Inst = I;

测试结果

至此我们初步完成了fact的提取，对测试用例进行测试，效果如下：

改进

改进1

上述实现对于loop1.ll、branch2.ll的测试并未通过，branch2.ll代码如下：

经过分析，明确问题所在，具体为如果变量值赋值为常数0时，之前并没有对此添加taint关系，所以更改store指令提取fact如下：

/*store [volatile] <ty> <value>, <ty>* <pointer>*/
if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
    Value *From = SI->getValueOperand();
    Value *To = SI->getPointerOperand();
    std::cout <<"From:"<<toString(From)<<" to:"<<toString(To) << "\n";
    addGen(InstMap, SI, SI);
    addDef(InstMap, To, SI);
    addUse(InstMap, From, SI);
    if(!memcmp(toString(From).data(),"i32 0",5)){  //新增
        addTaint(InstMap,SI);
    }
}

查看Loop1.ll，找出loop1.ll代码未通过测试原因，loop1.ll代码如下：

经过分析，是因为没有对br跳转指令进行处理，进而导致程序分析默认在loop1.ll文件内顺序进行，从而导致错误发生，因此对于br指令进行处理，首先根据当前br指令的后继基本块数目进行遍历操作，将当前br指令每一个后继基本块的第一条指令与当前br指令添加Next关系，利用BranchInst类进行实现，具体如下：

if (BranchInst *BI = dyn_cast<BranchInst>(I)){
    //std::cout <<"getNumSuccessors(): "<< BI->getNumSuccessors()<<"\n";
    for(int i=0;i<BI->getNumSuccessors();i++){
        std::cout <<"successor basic block "<< i<< ": "<<BI->getSuccessor(i)<<"\n";
        Instruction * successor = BI->getSuccessor(i)->getFirstNonPHI();
        std::cout <<"the first instruc : "<< toString(successor)<<"\n";
        addNext(InstMap,I,successor);
    }
}

并且需要对最开始的添加Next关系操作进行改动，如果当前指令的上一个指令为br跳转指令，由于我们已经在br指令处为其添加Next关系，所以不需要再次添加关系，具体如下：

if(Pre_Inst != NULL) {
    if (BranchInst *BI_Pre = dyn_cast<BranchInst>(Pre_Inst)) {
        //do nothing
    } else {
        addNext(InstMap, Pre_Inst, I);
    }
}
Pre_Inst = I;

然后再次对测试集进行测试，可以看到成功通过了全部测试集，效果如下：

改进2

数组测试用例如下

可以看到对数组进行处理时指令为getelementptr，利用对应的GetElementPtrInst类进行处理，我的实现思路是当数组中存在任何一个变量有tainted风险，并且div操作时用到了数组中的任何一个变量时，就发出警报，但我们并不能确定是否是数组中tianted元素作为除数，确保了soundness，允许错报，不允许漏报。

首先是对于store指令进行修改，要分两种情况处理，当处理指令不涉及数组元素时，与之前操作相同；但如果store指令用到数组元素时，那么就利用getPointerOperand()回溯到数组的初始化指令，比如%a = alloca [3 x i32], align 4,然后针对数组初始化指令进行相应的Gen、Def、Use关系添加。并且由于是对数组的初始化指令进行操作，所以为了确保soundness（允许误报、不允许漏报），一旦数组的初始化指令在store中被标记为tainted之后，后续store操作中不再对数组初始化指令添加Use、Gen、Def指令，防止将数组中的tianted关系kill掉。具体实现如下:

/*store [volatile] <ty> <value>, <ty>* <pointer>*/
if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
    Value *From = SI->getValueOperand();
    Value *To = SI->getPointerOperand();
    //std::cout <<"From:"<<toString(From)<<" to:"<<toString(To) << "\n";
    int mark = 0;//judge if it's about array
    while(GetElementPtrInst *Pre_Ins = dyn_cast<GetElementPtrInst>(To)){
        To = Pre_Ins->getPointerOperand();
        mark = 1;
    }
    if(mark == 1 && array_taint==0){ // array and not be tainted
        //std::cout <<"array_begin: "<<toString(To)<<"\n\n";
        if(Instruction*begin=dyn_cast<Instruction>(To)){
            addGen(InstMap,SI,begin);
            addDef(InstMap,begin,SI);
            addUse(InstMap,From,begin);
            if(!memcmp(toString(From).data(),"i32 0",5)){
                addTaint(InstMap,begin);
                array_taint = 1; // if tainted, not kill the relation
            }
        }
    }
    else if(mark == 0){ // not array
        addGen(InstMap, SI, SI);
        addDef(InstMap, To, SI);
        addUse(InstMap, From, SI);
        if(!memcmp(toString(From).data(),"i32 0",5)){
            addTaint(InstMap,SI);
        }
    }
}

对load指令进行同样修改，区分load指令是否涉及数组元素，不涉及数组元素时，操作不变；涉及数组元素时，由于store操作时添加关系均是对于数组的初始化指令，所以load操作添加对应关系时，要将使用到的数组元素变为数组元素的初始化指令，具体如下：

// loadIns: load [volatile] <ty>, <ty>* <pointer>
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
    Value * PointOperand = LI->getPointerOperand();
    int mark = 0; // judge if it's about array
    while(GetElementPtrInst *Pre_Ins = dyn_cast<GetElementPtrInst>(PointOperand)){
        PointOperand = Pre_Ins->getPointerOperand();
        mark = 1;
    }
    if(mark==1){ //array
        //std::cout <<"array_begin: "<<toString(PointOperand)<<"\n\n";
        if(Instruction*tmp=dyn_cast<Instruction>(PointOperand))
        {
            addDef(InstMap,LI,tmp);
            addGen(InstMap,tmp,LI);
            addUse(InstMap,LI,LI);
        }
    }
    else{ //not array
        addDef(InstMap, LI, LI);
        addUse(InstMap, LI->getPointerOperand(), LI);
        addGen(InstMap, LI, LI);
    }
}

对于其余指令的fact提取操作不变，效果如下：

总结

本实验实现了一个基于数据流分析的简单（基本数据类型、只有一个main函数）C程序的除0错漏洞分析器，并支持数组处理，首先利用clang将c文件处理为LLVM 3AC code，然后分别针对数据流分析以及污点分析阶段定义了一系列关系以及规则，再利用LLVM相关函数处理IR，提取fact生成constraint，将constraint交到z3求解器中求解，根据rule判断是否蕴含除零错误的可能。

如果没有太明白的话，可能首先需要掌握清楚reaching definition，然后下载实验代码，观察代码框架，然后在结合本文来看可能会有新的体会。建议大家自己完成，遇到不懂的再来参考借鉴。