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