Add new indirect control flow analysis code. The code is still using ParseAPI level...
[dyninst.git] / parseAPI / src / TableGuardData.C
1 #include "TableGuardData.h"
2 #include "IndirectASTVisitor.h"
3 #include "CFG.h"
4 #include "Absloc.h"
5 #include "AbslocInterface.h"
6 #include "debug_parse.h"
7
8 using namespace std;
9 using namespace Dyninst;
10 using namespace Dyninst::DataflowAPI;
11 using namespace Dyninst::ParseAPI;
12
13 static void GetUsedRegisters(set<MachRegister> &regs, AST::Ptr ast) {
14     unsigned totalChildren = ast->numChildren();
15     for (unsigned i = 0 ; i < totalChildren; ++i) {
16         GetUsedRegisters(regs, ast->child(i));
17     }
18     if (ast->getID() == AST::V_VariableAST) {
19         VariableAST::Ptr varAST = boost::static_pointer_cast<VariableAST>(ast);
20         const Absloc & loc = varAST->val().reg.absloc();
21         if (loc.type() == Absloc::Register)
22             regs.insert(loc.reg());
23     }
24 }
25
26 GuardData::GuardData(ParseAPI::Function *f,
27                      ParseAPI::Block* b, 
28                      Instruction::Ptr c, 
29                      Instruction::Ptr j, 
30                      Address ca, 
31                      Address ja):
32         func(f), block(b), cmpInsn(c), jmpInsn(j), cmpInsnAddr(ca), jmpInsnAddr(ja) {
33
34     Result_t res;
35     AssignmentConverter ac(true, false);
36     vector<Assignment::Ptr> assignments;
37     parsing_printf("cmpInsn %s at %lx\n", cmpInsn->format().c_str(), cmpInsnAddr);
38
39
40     ac.convert(cmpInsn, cmpInsnAddr, func, block, assignments);    
41
42     for (auto ait = assignments.begin(); ait != assignments.end(); ++ait) {
43         res[*ait] = AST::Ptr();
44     }
45     set<Instruction::Ptr> failedInsns;
46     SymEval::expand(res, failedInsns, false);
47
48     // Extract variable and bound from the symbolic expression of zf
49     AST::Ptr cmp;
50     for (auto ait = assignments.begin(); ait != assignments.end(); ++ait) {
51         Absloc loc = (*ait)->out().absloc();
52         if (loc.type() == Absloc::Register && (loc.reg() == x86::zf || loc.reg() == x86_64::zf)) {
53             cmp = res[*ait];
54             break;
55         }
56     }
57    
58
59     ComparisonVisitor cv;
60     cmp->accept(&cv);
61     parsing_printf("jumpInsn %s at %lx\n", jmpInsn->format().c_str(), jmpInsnAddr);
62
63     res.clear();
64     ac.convert(jmpInsn, jmpInsnAddr, func, block, assignments);
65     for (auto ait = assignments.begin(); ait != assignments.end(); ++ait)
66         res[*ait] = AST::Ptr();
67     SymEval::expand(res, failedInsns, false);
68
69     JumpCondVisitor jcv;
70     res.begin()->second->accept(&jcv);
71
72     constantBound = (cv.minuend->getID() == AST::V_ConstantAST) || (cv.subtrahend->getID() == AST::V_ConstantAST);
73     if (!constantBound) return;
74
75     jumpWhenNoZF = jcv.invertFlag;
76    
77     if (cv.minuend->getID() == AST::V_ConstantAST) {
78         ConstantAST::Ptr minuendAST = boost::static_pointer_cast<ConstantAST>(cv.minuend);
79         cmpBound = minuendAST->val().val;
80         cmpAST = SimplifyAnAST(cv.subtrahend, cmpInsn->size());
81         varSubtrahend = true;
82     } else {
83         ConstantAST::Ptr subtrahendAST = boost::static_pointer_cast<ConstantAST>(cv.subtrahend);
84         cmpBound = subtrahendAST->val().val;
85         cmpAST = SimplifyAnAST(cv.minuend, cmpInsn->size());
86         varSubtrahend = false;
87
88     }
89
90     GetUsedRegisters(usedRegs, cmpAST);
91     
92     parsing_printf("constantBound = %d, JumpWhenNoZF = %d, varSubtrahend = %d\n", constantBound, jumpWhenNoZF, varSubtrahend);
93     parsing_printf("subtrahend AST %s\n", cv.subtrahend->format().c_str());
94     parsing_printf("minuend AST %s\n", cv.minuend->format().c_str());
95
96 }       
97 void ReachFact::ReverseDFS(ParseAPI::Block *cur, set<ParseAPI::Block*> &visited) {
98     if (visited.find(cur) != visited.end()) return;
99     visited.insert(cur);
100
101     for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit) 
102         if ((*eit)->intraproc() && (*eit)->type() != INDIRECT) ReverseDFS((*eit)->src(), visited);
103 }
104
105 void ReachFact::NaturalDFS(ParseAPI::Block *cur, set<ParseAPI::Block*> &visited) {
106     if (forbid.find(cur) != forbid.end()) return;
107     if (visited.find(cur) != visited.end()) return;
108     visited.insert(cur);
109
110     for (auto eit = cur->targets().begin(); eit != cur->targets().end(); ++eit) 
111         if ((*eit)->intraproc() && (*eit)->type() != INDIRECT) NaturalDFS((*eit)->trg(), visited);
112 }
113
114
115
116 void ReachFact::ReachBlocks() {
117     for (auto git = guards.begin(); git != guards.end(); ++git)
118         forbid.insert(git->block);
119     for (auto git = guards.begin(); git != guards.end(); ++git) {
120         ParseAPI::Block * jmpBlock = git->block;
121         ReverseDFS(jmpBlock, incoming[jmpBlock]);
122         
123         ParseAPI::Block *condTakenBlock, *condFTBlock;
124         for (auto eit = jmpBlock->targets().begin(); eit != jmpBlock->targets().end(); ++eit)
125             if ((*eit)->type() == COND_TAKEN) condTakenBlock = (*eit)->trg();
126             else condFTBlock = (*eit)->trg(); 
127         
128         NaturalDFS(condTakenBlock, branch_taken[jmpBlock]);
129         NaturalDFS(condFTBlock, branch_ft[jmpBlock]);
130     }
131 }
132
133 ReachFact::ReachFact(GuardSet &g): guards(g) {
134     ReachBlocks();
135 }
136