Add new indirect control flow analysis code. The code is still using ParseAPI level...
[dyninst.git] / parseAPI / src / IndirectAnalyzer.C
1 #include "IndirectControlFlow.h"
2 #include "BackwardSlicing.h"
3 #include "debug_parse.h"
4
5 #include "CodeObject.h"
6 #include "Graph.h"
7
8 #include "Instruction.h"
9 #include "InstructionDecoder.h"
10
11 static bool UsePC(Instruction::Ptr insn) {
12     vector<Operand> operands;
13     insn->getOperands(operands);
14     
15     for(unsigned int i=0; i<operands.size();++i) {
16         Operand & op = operands[i];
17         set<RegisterAST::Ptr> regs;
18         op.getReadSet(regs);
19         for (auto rit = regs.begin(); rit != regs.end(); ++rit)
20             if ((*rit)->getID().isPC()) return true;
21
22     }
23     return false;
24 }
25 bool IndirectControlFlowAnalyzer::NewJumpTableAnalysis() {
26     parsing_printf("Apply indirect control flow analysis at %lx\n", block->last());
27     FindAllConditionalGuards();
28     ReachFact rf(guards);
29     parsing_printf("Calculate backward slice\n");
30
31     BackwardSlicer bs(func, block, block->last(), guards, rf);
32     GraphPtr slice =  bs.CalculateBackwardSlicing();
33     
34     parsing_printf("Calculate bound facts\n");     
35     BoundFactsCalculator bfc(guards, func, slice, func->entry() == block, rf);
36     bfc.CalculateBoundedFacts();
37
38     bool ijt = IsJumpTable(slice, bfc);
39     return ijt;
40 }                                                      
41
42
43
44 bool IndirectControlFlowAnalyzer::EndWithConditionalJump(ParseAPI::Block * b) {
45 /*
46     const unsigned char * buf = (const unsigned char*) b->obj()->cs()->getPtrToInstruction(b->last());
47     InstructionDecoder dec(buf, b->end() - b->last(), b->obj()->cs()->getArch());
48     Instruction::Ptr insn = dec.decode();
49     entryID id = insn->getOperation().getID();
50 */    
51     for (auto eit = b->targets().begin(); eit != b->targets().end(); ++eit)
52         if ((*eit)->type() == COND_TAKEN) return true;
53     return false;
54
55 }
56
57 void IndirectControlFlowAnalyzer::GetAllReachableBlock(set<ParseAPI::Block*> &reachable) {
58     queue<Block*> q;
59     q.push(block);
60     while (!q.empty()) {
61         ParseAPI::Block *cur = q.front();
62         q.pop();
63         if (reachable.find(cur) != reachable.end()) continue;
64         reachable.insert(cur);
65         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
66             if ((*eit)->intraproc()) 
67                 q.push((*eit)->src());
68     }
69
70 }
71
72 void IndirectControlFlowAnalyzer::SaveGuardData(ParseAPI::Block *prev) {
73
74     Address curAddr = prev->start();
75     const unsigned char* buf = (const unsigned char*) prev->obj()->cs()->getPtrToInstruction(prev->start());
76     InstructionDecoder dec(buf, prev->end() - prev->start(), prev->obj()->cs()->getArch());
77     Instruction::Ptr insn;
78     vector<pair<Instruction::Ptr, Address> > insns;
79     
80     while ( (insn = dec.decode()) != NULL ) {
81         insns.push_back(make_pair(insn, curAddr));
82         curAddr += insn->size();
83     }
84     
85     for (auto iit = insns.rbegin(); iit != insns.rend(); ++iit) {
86         insn = iit->first;
87         if (insn->getOperation().getID() == e_cmp || insn->getOperation().getID() == e_test) {
88             guards.insert(GuardData(func, prev, insn, insns.rbegin()->first, iit->second, insns.rbegin()->second));
89             parsing_printf("Find guard and cmp pair: cmp %s, addr %lx, cond jump %s, addr %lx\n", insn->format().c_str(), iit->second, insns.rbegin()->first->format().c_str(), insns.rbegin()->second); 
90             break;
91         }    
92     }
93 }
94
95 void IndirectControlFlowAnalyzer::FindAllConditionalGuards(){
96     set<ParseAPI::Block*> visited, reachable;
97     queue<Block*> q;
98     q.push(block);
99     GetAllReachableBlock(reachable);
100
101     while (!q.empty()) {
102         ParseAPI::Block * cur = q.front();
103         q.pop();
104         if (visited.find(cur) != visited.end()) continue;
105         visited.insert(cur);
106
107         // Since a guard has the condition that one branch must always reach the indirect jump,
108         // if the current block can reach a block that cannot reach the indirect jump, 
109         // then all the sources of the current block is not post-dominated by the indirect jump.
110         bool postDominate = true;
111         for (auto eit = cur->targets().begin(); eit != cur->targets().end(); ++eit) 
112             if ((*eit)->intraproc() && (*eit)->type() != INDIRECT)
113                 if (reachable.find((*eit)->trg()) == reachable.end()) postDominate = false;
114         if (!postDominate) continue;
115
116         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
117             if ((*eit)->intraproc()) {
118                 ParseAPI::Block* prev = (*eit)->src();
119                 if (EndWithConditionalJump(prev)) {                
120                     SaveGuardData(prev);
121                 }
122                 else {
123                     q.push(prev);
124                 }
125             }
126     }
127 }
128
129
130
131 bool IndirectControlFlowAnalyzer::IsJumpTable(GraphPtr slice, 
132                                               BoundFactsCalculator &bfc) {
133     NodeIterator sbegin, send;
134     slice->exitNodes(sbegin, send);
135     for (; sbegin != send; ++sbegin) {
136         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*sbegin);
137         const Absloc &loc = node->assign()->out().absloc();
138         parsing_printf("Checking bound fact at %lx for %s\n",node->addr(), loc.format().c_str()); 
139         BoundFact &bf = bfc.GetBoundFact(*sbegin);
140         if (bf.IsBounded(loc)) {
141             BoundValue val = bf.GetBound(loc);
142             if (val.tableLookup) return true;
143             if (val.tableOffset) return true;
144             if (val.type == LessThan && val.CoeBounded() && val.HasTableBase()) return true;
145         }
146     }
147   
148
149     return false;
150 }
151
152 bool IndirectControlFlowPred::endAtPoint(AssignmentPtr ap) {
153         if (ap->insn()->writesMemory()) return true;
154         if (UsePC(ap->insn())) return true;
155         if (ap->insn()->getCategory() == c_CallInsn) return true;
156         return false;
157 }
158
159 bool IndirectControlFlowPred::followCall(ParseAPI::Function* , CallStack_t & , AbsRegion ) {
160
161 /*        ParseAPI::Block * b = callee->entry();
162         vector<pair<Instruction::Ptr, Address> > insns;
163
164         const unsigned char * buf = (const unsigned char*) b->obj()->cs()->getPtrToInstruction(b->start());
165         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());  
166
167         Instruction::Ptr insn;
168         Address curAddr = b->start();
169         int num = 0;
170         while ((insn = dec.decode()) != NULL) {
171             insns.push_back(make_pair(insn, curAddr));
172             curAddr += insn->size();
173             ++num;
174         }
175
176         if (num != 2) return false;
177
178         if (insns[1].first->getCategory() != c_ReturnInsn) return false;
179         if (insns[0].first->getOperation().getID() != e_mov) return false;
180         printf("followCall to %lx\n", callee->addr());
181 */
182         return false;
183
184 }