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