1. Fix a bug in determining exit blocks
[dyninst.git] / parseAPI / src / IndirectAnalyzer.C
1 #include "IndirectControlFlow.h"
2 #include "BackwardSlicing.h"
3 #include "IA_IAPI.h"
4 #include "debug_parse.h"
5
6 #include "CodeObject.h"
7 #include "Graph.h"
8
9 #include "Instruction.h"
10 #include "InstructionDecoder.h"
11 #include "Register.h"
12
13 static bool UsePC(Instruction::Ptr insn) {
14     vector<Operand> operands;
15     insn->getOperands(operands);
16     
17     for(unsigned int i=0; i<operands.size();++i) {
18         Operand & op = operands[i];
19         set<RegisterAST::Ptr> regs;
20         op.getReadSet(regs);
21         for (auto rit = regs.begin(); rit != regs.end(); ++rit)
22             if ((*rit)->getID().isPC()) return true;
23
24     }
25     return false;
26 }
27
28 bool IndirectControlFlowAnalyzer::FillInOutEdges(BoundValue &target, 
29                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
30
31     if (block->obj()->cs()->getArch() == Arch_x86) target.tableBase &= 0xffffffff;
32     parsing_printf("The final target bound fact:\n");
33     target.Print();
34
35     if (!block->obj()->cs()->isValidAddress(target.tableBase)) {
36         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", target.tableBase);
37         return false;
38     }
39
40     for (int64_t i = 0; i <= target.value; ++i) {
41         Address tableEntry = target.tableBase;
42         if (target.addIndexing) tableEntry += target.coe * i; else tableEntry -= target.coe * i;
43         Address targetAddress = 0;
44         if (target.tableLookup || target.tableOffset) {
45             if (target.coe == sizeof(Address)) {
46                 targetAddress = *(const Address *) block->obj()->cs()->getPtrToInstruction(tableEntry);
47             } else {
48                 targetAddress = *(const int *) block->obj()->cs()->getPtrToInstruction(tableEntry);
49             }
50             
51             if (target.tableOffset && targetAddress != 0) {
52                 if (target.addOffset) targetAddress += target.targetBase; else targetAddress = target.targetBase - targetAddress;
53             }
54         } else targetAddress = tableEntry;
55
56         if (block->obj()->cs()->getArch() == Arch_x86) targetAddress &= 0xffffffff;
57         parsing_printf("Jumping to target %lx,", targetAddress);
58         if (block->obj()->cs()->isCode(targetAddress)) {
59             outEdges.push_back(make_pair(targetAddress, INDIRECT));
60             parsing_printf(" is code.\n" );
61         } else {
62             parsing_printf(" not code.\n");
63         }
64     }
65     return true;
66 }
67
68 bool IndirectControlFlowAnalyzer::NewJumpTableAnalysis(std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
69     parsing_printf("Apply indirect control flow analysis at %lx\n", block->last());
70     FindAllConditionalGuards();
71     FindAllThunks();
72     ReachFact rf(guards, thunks);
73     parsing_printf("Calculate backward slice\n");
74
75     BackwardSlicer bs(func, block, block->last(), guards, rf);
76     GraphPtr slice =  bs.CalculateBackwardSlicing();
77     parsing_printf("Calculate bound facts\n");     
78     BoundFactsCalculator bfc(guards, func, slice, func->entry() == block, rf, thunks);
79     bfc.CalculateBoundedFacts();
80
81     BoundValue target;
82     bool ijt = IsJumpTable(slice, bfc, target);
83     if (ijt) {
84         return FillInOutEdges(target, outEdges);
85     } else return false;
86 }                                                      
87
88
89
90 bool IndirectControlFlowAnalyzer::EndWithConditionalJump(ParseAPI::Block * b) {
91
92     const unsigned char * buf = (const unsigned char*) b->obj()->cs()->getPtrToInstruction(b->last());
93     InstructionDecoder dec(buf, b->end() - b->last(), b->obj()->cs()->getArch());
94     Instruction::Ptr insn = dec.decode();
95     entryID id = insn->getOperation().getID();
96
97     if (id == e_jz || id == e_jnz ||
98         id == e_jb || id == e_jnb ||
99         id == e_jbe || id == e_jnbe) return true;
100    
101 //    for (auto eit = b->targets().begin(); eit != b->targets().end(); ++eit)
102 //        if ((*eit)->type() == COND_TAKEN) return true;
103     return false;
104
105 }
106
107 void IndirectControlFlowAnalyzer::GetAllReachableBlock() {
108     reachable.clear();
109     queue<Block*> q;
110     q.push(block);
111     while (!q.empty()) {
112         ParseAPI::Block *cur = q.front();
113         q.pop();
114         if (reachable.find(cur) != reachable.end()) continue;
115         reachable.insert(cur);
116         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
117             if ((*eit)->intraproc()) 
118                 q.push((*eit)->src());
119     }
120
121 }
122
123 void IndirectControlFlowAnalyzer::SaveGuardData(ParseAPI::Block *prev) {
124
125     Address curAddr = prev->start();
126     const unsigned char* buf = (const unsigned char*) prev->obj()->cs()->getPtrToInstruction(prev->start());
127     InstructionDecoder dec(buf, prev->end() - prev->start(), prev->obj()->cs()->getArch());
128     Instruction::Ptr insn;
129     vector<pair<Instruction::Ptr, Address> > insns;
130     
131     while ( (insn = dec.decode()) != NULL ) {
132         insns.push_back(make_pair(insn, curAddr));
133         curAddr += insn->size();
134     }
135     
136     for (auto iit = insns.rbegin(); iit != insns.rend(); ++iit) {
137         insn = iit->first;
138         if (insn->getOperation().getID() == e_cmp || insn->getOperation().getID() == e_test) {
139             guards.insert(GuardData(func, prev, insn, insns.rbegin()->first, iit->second, insns.rbegin()->second));
140             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); 
141             break;
142         }    
143     }
144 }
145
146 void IndirectControlFlowAnalyzer::FindAllConditionalGuards(){
147     set<ParseAPI::Block*> visited;
148     queue<Block*> q;
149     q.push(block);
150     GetAllReachableBlock();
151
152     while (!q.empty()) {
153         ParseAPI::Block * cur = q.front();
154         q.pop();
155         if (visited.find(cur) != visited.end()) continue;
156         visited.insert(cur);
157
158         // Since a guard has the condition that one branch must always reach the indirect jump,
159         // if the current block can reach a block that cannot reach the indirect jump, 
160         // then all the sources of the current block is not post-dominated by the indirect jump.
161         bool postDominate = true;
162         for (auto eit = cur->targets().begin(); eit != cur->targets().end(); ++eit) 
163             if ((*eit)->intraproc() && (*eit)->type() != INDIRECT)
164                 if (reachable.find((*eit)->trg()) == reachable.end()) postDominate = false;
165         if (!postDominate) continue;
166
167         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
168             if ((*eit)->intraproc()) {
169                 ParseAPI::Block* prev = (*eit)->src();
170                 if (EndWithConditionalJump(prev)) {                
171                     SaveGuardData(prev);
172                 }
173                 else {
174                     q.push(prev);
175                 }
176             }
177     }
178 }
179
180
181
182 bool IndirectControlFlowAnalyzer::IsJumpTable(GraphPtr slice, 
183                                               BoundFactsCalculator &bfc,
184                                               BoundValue &target) {
185     NodeIterator sbegin, send;
186     slice->exitNodes(sbegin, send);
187     for (; sbegin != send; ++sbegin) {
188         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*sbegin);
189         const Absloc &loc = node->assign()->out().absloc();
190         parsing_printf("Checking bound fact at %lx for %s\n",node->addr(), loc.format().c_str()); 
191         BoundFact *bf = bfc.GetBoundFact(*sbegin);
192         if (bf->IsBounded(loc)) {
193             target = *(bf->GetBound(loc));
194
195             if (target.tableLookup) return true;
196             if (target.tableOffset) return true;
197             if (target.type == LessThan && target.CoeBounded() && target.HasTableBase()) return true;
198         }
199     }
200   
201
202     return false;
203 }
204
205 void IndirectControlFlowAnalyzer::FindAllThunks() {
206     for (auto bit = reachable.begin(); bit != reachable.end(); ++bit) {
207         // We intentional treat a getting PC call as a special case that does not
208         // end a basic block. So, we need to check every instruction to find all thunks
209         ParseAPI::Block *b = *bit;
210         const unsigned char* buf =
211             (const unsigned char*)(b->obj()->cs()->getPtrToInstruction(b->start()));
212         if( buf == NULL ) {
213             parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",FILE__, __LINE__);
214             return;
215         }
216         parsing_printf("Looking for thunk in block [%lx,%lx).", b->start(), b->end());
217         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
218         InsnAdapter::IA_IAPI block(dec, b->start(), b->obj() , b->region(), b->obj()->cs(), b);
219         while (block.getAddr() < b->end()) {
220             if (block.getInstruction()->getCategory() == c_CallInsn && block.isThunk()) {
221                 bool valid;
222                 Address addr;
223                 boost::tie(valid, addr) = block.getCFT();
224                 const unsigned char *target = (const unsigned char *) b->obj()->cs()->getPtrToInstruction(addr);
225                 InstructionDecoder targetChecker(target, InstructionDecoder::maxInstructionLength, b->obj()->cs()->getArch());
226                 Instruction::Ptr thunkFirst = targetChecker.decode();
227                 set<RegisterAST::Ptr> thunkTargetRegs;
228                 thunkFirst->getWriteSet(thunkTargetRegs);
229                 
230                 for (auto curReg = thunkTargetRegs.begin(); curReg != thunkTargetRegs.end(); ++curReg) {
231                     ThunkInfo t;
232                     t.reg = (*curReg)->getID();
233                     t.value = block.getAddr() + block.getInstruction()->size();
234                     t.block = b;
235                     thunks.insert(make_pair(block.getAddr(), t));
236
237                     parsing_printf("\tfind thunk at %lx, storing value %lx to %s\n", block.getAddr(), t.value , t.reg.name().c_str());
238                 }
239             }
240             block.advance();
241         }
242     }
243 }
244
245 bool IndirectControlFlowPred::endAtPoint(AssignmentPtr ap) {
246         if (ap->insn()->writesMemory()) return true;
247         if (UsePC(ap->insn())) return true;
248         if (ap->insn()->getCategory() == c_CallInsn) return true;
249         return false;
250 }
251
252 bool IndirectControlFlowPred::followCall(ParseAPI::Function* , CallStack_t & , AbsRegion ) {
253
254 /*        ParseAPI::Block * b = callee->entry();
255         vector<pair<Instruction::Ptr, Address> > insns;
256
257         const unsigned char * buf = (const unsigned char*) b->obj()->cs()->getPtrToInstruction(b->start());
258         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());  
259
260         Instruction::Ptr insn;
261         Address curAddr = b->start();
262         int num = 0;
263         while ((insn = dec.decode()) != NULL) {
264             insns.push_back(make_pair(insn, curAddr));
265             curAddr += insn->size();
266             ++num;
267         }
268
269         if (num != 2) return false;
270
271         if (insns[1].first->getCategory() != c_ReturnInsn) return false;
272         if (insns[0].first->getOperation().getID() != e_mov) return false;
273         printf("followCall to %lx\n", callee->addr());
274 */
275         return false;
276
277 }