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