1. Replace springboards prioriy "OffLimits" and "Required" with "FuncEntry" and ...
[dyninst.git] / parseAPI / src / IndirectAnalyzer.C
1 #include "dyntypes.h"
2 #include "IndirectAnalyzer.h"
3 #include "BoundFactCalculator.h"
4 #include "JumpTableFormatPred.h"
5 #include "JumpTableIndexPred.h"
6 #include "SymbolicExpression.h"
7 #include "IndirectASTVisitor.h"
8 #include "IA_IAPI.h"
9 #include "debug_parse.h"
10
11 #include "CodeObject.h"
12 #include "Graph.h"
13
14 #include "Instruction.h"
15 #include "InstructionDecoder.h"
16 #include "Register.h"
17 #include "SymEval.h"
18 using namespace Dyninst::ParseAPI;
19 using namespace Dyninst::InstructionAPI;
20
21 static bool IsIndexing(AST::Ptr node, AbsRegion &index) {
22     RoseAST::Ptr n = boost::static_pointer_cast<RoseAST>(node);
23     if (n->val().op != ROSEOperation::sMultOp &&
24         n->val().op != ROSEOperation::uMultOp &&
25         n->val().op != ROSEOperation::shiftLOp &&
26         n->val().op != ROSEOperation::rotateLOp) return false;
27     if (n->child(0)->getID() != AST::V_VariableAST) return false;
28     if (n->child(1)->getID() != AST::V_ConstantAST) return false;
29     VariableAST::Ptr var = boost::static_pointer_cast<VariableAST>(n->child(0));
30     index = var->val().reg;
31     return true;
32 }
33
34 static bool IsVariableArgumentFormat(AST::Ptr t, AbsRegion &index) {
35     if (t->getID() != AST::V_RoseAST) {
36         return false;
37     }
38     RoseAST::Ptr rt = boost::static_pointer_cast<RoseAST>(t);
39     if (rt->val().op != ROSEOperation::addOp) {
40         return false;
41     }
42     if (rt->child(0)->getID() != AST::V_ConstantAST || rt->child(1)->getID() != AST::V_RoseAST) {
43         return false;
44     }
45     RoseAST::Ptr c1 = boost::static_pointer_cast<RoseAST>(rt->child(1));
46     if (c1->val().op == ROSEOperation::addOp) {
47         if (c1->child(0)->getID() == AST::V_RoseAST && c1->child(1)->getID() == AST::V_ConstantAST) {
48             RoseAST::Ptr lc = boost::static_pointer_cast<RoseAST>(c1->child(0));
49             ConstantAST::Ptr rc = boost::static_pointer_cast<ConstantAST>(c1->child(1));
50             if (lc->val().op == ROSEOperation::invertOp && rc->val().val == 1) {
51                 return IsIndexing(lc->child(0), index);
52             }
53         }
54         return false;
55     }
56     return IsIndexing(rt->child(1), index);
57
58 }
59
60 bool IndirectControlFlowAnalyzer::NewJumpTableAnalysis(std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
61     parsing_printf("Apply indirect control flow analysis at %lx\n", block->last());
62     parsing_printf("Looking for thunk\n");
63 boost::make_lock_guard(*func);
64 //  Find all blocks that reach the block containing the indirect jump
65 //  This is a prerequisit for finding thunks
66     GetAllReachableBlock();
67 //  Now we try to find all thunks in this function.
68 //  We pass in the slice because we may need to add new ndoes.
69     FindAllThunks();
70 //  Calculates all blocks that can reach
71 //  and be reachable from thunk blocks
72     ReachFact rf(thunks);
73
74     // Now we start with the indirect jump instruction,
75     // to determine the format of the (potential) jump table
76     const unsigned char * buf = (const unsigned char*) block->region()->getPtrToInstruction(block->last());
77     InstructionDecoder dec(buf, InstructionDecoder::maxInstructionLength, block->obj()->cs()->getArch());
78     Instruction insn = dec.decode();
79     AssignmentConverter ac(true, false);
80     vector<Assignment::Ptr> assignments;
81     ac.convert(insn, block->last(), func, block, assignments);
82     Slicer formatSlicer(assignments[0], block, func, false, false);
83
84     SymbolicExpression se;
85     se.cs = block->obj()->cs();
86     se.cr = block->region();
87     JumpTableFormatPred jtfp(func, block, rf, thunks, se);
88     GraphPtr slice = formatSlicer.backwardSlice(jtfp);
89     //parsing_printf("\tJump table format: %s\n", jtfp.format().c_str());
90     // If the jump target expression is not in a form we recognize,
91     // we do not try to resolve it
92     parsing_printf("In function %s, Address %lx, jump target format %s, index loc %s, index variable %s, memory read loc %s, isJumpTableFormat %d\n", 
93             func->name().c_str(), 
94             block->last(), 
95             jtfp.format().c_str(), 
96             jtfp.indexLoc ? jtfp.indexLoc->format().c_str() : "null" , 
97             jtfp.index.format().c_str(),
98             jtfp.memLoc ? jtfp.memLoc->format().c_str() : "null",
99             jtfp.isJumpTableFormat());
100
101     bool variableArguFormat = false;
102     if (!jtfp.isJumpTableFormat()) {
103         if (jtfp.jumpTargetExpr && func->entry() == block && IsVariableArgumentFormat(jtfp.jumpTargetExpr, jtfp.index)) {
104             parsing_printf("\tVariable number of arguments format, index %s\n", jtfp.index.format().c_str());
105             variableArguFormat = true;
106         } else {
107             return false;
108         }
109     }
110
111     StridedInterval b;
112     bool scanTable = false;
113     if (!variableArguFormat) {
114         Slicer indexSlicer(jtfp.indexLoc, jtfp.indexLoc->block(), func, false, false);
115         JumpTableIndexPred jtip(func, block, jtfp.index, se);
116         jtip.setSearchForControlFlowDep(true);
117         slice = indexSlicer.backwardSlice(jtip);
118
119         if (!jtip.findBound && block->obj()->cs()->getArch() != Arch_aarch64) {
120
121             // After the slicing is done, we do one last check to
122             // see if we can resolve the indirect jump by assuming
123             // one byte read is in bound [0,255]
124             GraphPtr g = jtip.BuildAnalysisGraph(indexSlicer.visitedEdges);
125             BoundFactsCalculator bfc(func, g, func->entry() == block,  true, se);
126             bfc.CalculateBoundedFacts();
127         
128             StridedInterval target;
129             jtip.IsIndexBounded(g, bfc, target);
130         }
131         if (jtip.findBound) {
132             parsing_printf(" find bound %s for %lx\n", jtip.bound.format().c_str(), block->last());
133             b = jtip.bound;
134         } else {
135             parsing_printf(" Cannot find bound, assume there are at most 256 entries and scan the table for indirect jump at %lx\n", block->last());
136             b = StridedInterval(1, 0, 255);
137             scanTable = true;
138         }
139     } else {
140         b = StridedInterval(1, 0, 8);
141     }
142     std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > > jumpTableOutEdges;
143     ReadTable(jtfp.jumpTargetExpr,
144               jtfp.index,
145               b,
146               GetMemoryReadSize(jtfp.memLoc),
147               IsZeroExtend(jtfp.memLoc),
148               scanTable,
149               jtfp.constAddr,
150               jumpTableOutEdges);
151     parsing_printf(", find %d edges\n", jumpTableOutEdges.size());
152     outEdges.insert(outEdges.end(), jumpTableOutEdges.begin(), jumpTableOutEdges.end());
153     return !jumpTableOutEdges.empty();
154 }                                                      
155
156
157
158
159 // Find all blocks that reach the block containing the indirect jump
160 void IndirectControlFlowAnalyzer::GetAllReachableBlock() {
161     reachable.clear();
162     queue<Block*> q;
163     q.push(block);
164     while (!q.empty()) {
165         ParseAPI::Block *cur = q.front();
166         q.pop();
167         if (reachable.find(cur) != reachable.end()) continue;
168         reachable.insert(cur);
169     boost::lock_guard<Block> g(*cur);
170         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
171             if ((*eit)->intraproc()) {
172                 if ((*eit)->src() == NULL) {
173                     fprintf(stderr, "edge type = %d, target block [%lx, %lx)\n", (*eit)->type(), cur->start(), cur->end());
174                 }
175                 q.push((*eit)->src());
176             }
177     }
178
179 }
180
181
182 static Address ThunkAdjustment(Address afterThunk, MachRegister reg, ParseAPI::Block *b) {
183     // After the call to thunk, there is usually
184     // an add insturction like ADD ebx, OFFSET to adjust
185     // the value coming out of thunk.
186    
187     const unsigned char* buf = (const unsigned char*) (b->region()->getPtrToInstruction(afterThunk));
188     InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
189     Instruction nextInsn = dec.decode();
190     // It has to be an add
191     if (nextInsn.getOperation().getID() != e_add) return 0;
192     vector<Operand> operands;
193     nextInsn.getOperands(operands);
194     RegisterAST::Ptr regAST = boost::dynamic_pointer_cast<RegisterAST>(operands[0].getValue());
195     // The first operand should be a register
196     if (regAST == 0) return 0;
197     if (regAST->getID() != reg) return 0;
198     Result res = operands[1].getValue()->eval();
199     // A not defined result means that
200     // the second operand is not an immediate
201     if (!res.defined) return 0;
202     return res.convert<Address>();
203 }
204
205 void IndirectControlFlowAnalyzer::FindAllThunks() {
206     // Enumuerate every block to find thunk
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->region()->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         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
218         InsnAdapter::IA_IAPI* block = InsnAdapter::IA_IAPI::makePlatformIA_IAPI(b->obj()->cs()->getArch(), dec, b->start(), b->obj() , b->region(), b->obj()->cs(), b);
219         Address cur = b->start();
220         while (cur < 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->region()->getPtrToInstruction(addr);
226                 InstructionDecoder targetChecker(target, InstructionDecoder::maxInstructionLength, b->obj()->cs()->getArch());
227                 Instruction 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.value += ThunkAdjustment(t.value, t.reg, b);
236                     t.block = b;
237                     thunks.insert(make_pair(block->getAddr(), t));
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             cur += block->getInstruction().size();
242             if (cur < b->end()) block->advance();
243         }
244         delete block;
245     }
246 }
247
248 void IndirectControlFlowAnalyzer::ReadTable(AST::Ptr jumpTargetExpr,
249                                             AbsRegion index,
250                                             StridedInterval &indexBound,
251                                             int memoryReadSize,
252                                             bool isZeroExtend,
253                                             bool scanTable,
254                                             set<Address> &constAddr,
255                                             std::vector<std::pair<Address, Dyninst::ParseAPI::EdgeTypeEnum> > &targetEdges) {
256     CodeSource *cs = block->obj()->cs();
257     set<Address> jumpTargets;
258     int start = 0;
259     if (indexBound.low > 0) start = indexBound.low = start;
260     for (int v = start; v <= indexBound.high; v += indexBound.stride) {
261         JumpTableReadVisitor jtrv(index, v, cs, block->region(), isZeroExtend, memoryReadSize);
262         jumpTargetExpr->accept(&jtrv);
263         if (jtrv.valid && cs->isCode(jtrv.targetAddress)) {
264         if (cs->getArch() == Arch_x86_64 && FindJunkInstruction(jtrv.targetAddress)) {
265             parsing_printf("WARNING: resolving jump tables leads to junk instruction from %lx\n", jtrv.targetAddress);
266             break;
267         }
268         parsing_printf("\t index %d, target %lx\n", v, jtrv.targetAddress);
269             jumpTargets.insert(jtrv.targetAddress);
270         } else {
271             // We have a bad entry. We stop here, as we have wrong information
272             // In this case, we keep the good entries
273             parsing_printf("WARNING: resolving jump tables leads to a bad address %lx\n", jtrv.targetAddress);
274             break;
275         }
276         if (indexBound.stride == 0) break;
277     }
278     for (auto ait = constAddr.begin(); ait != constAddr.end(); ++ait) {
279         if (block->region()->isCode(*ait)) {
280             jumpTargets.insert(*ait);
281         }
282     }
283     for (auto tit = jumpTargets.begin(); tit != jumpTargets.end(); ++tit) {
284         targetEdges.push_back(make_pair(*tit, INDIRECT));
285     }
286 }
287
288 int IndirectControlFlowAnalyzer::GetMemoryReadSize(Assignment::Ptr memLoc) {
289     if (!memLoc) {
290         parsing_printf("\tmemLoc is null\n");
291         return 0;
292     }
293     Instruction i = memLoc->insn();
294     std::vector<Operand> ops;
295     i.getOperands(ops);
296     parsing_printf("\t there are %d operands\n", ops.size());
297     for (auto oit = ops.begin(); oit != ops.end(); ++oit) {
298         Operand o = *oit;
299         if (o.readsMemory()) {
300             Expression::Ptr exp = o.getValue();
301             return exp->size();
302         }
303     }
304     return 0;
305 }
306
307 bool IndirectControlFlowAnalyzer::IsZeroExtend(Assignment::Ptr memLoc) {
308     if (!memLoc) {
309         parsing_printf("\tmemLoc is null\n");
310         return false;
311     }
312     Instruction i = memLoc->insn();
313     parsing_printf("check zero extend %s\n", i.format().c_str());
314     if (i.format().find("movz") != string::npos) return true;
315     return false;
316 }
317
318 bool IndirectControlFlowAnalyzer::FindJunkInstruction(Address addr) {
319     unsigned size = block->region()->offset() + block->region()->length() - addr; 
320     const unsigned char* buffer = (const unsigned char *)(func->isrc()->getPtrToInstruction(addr));
321     InstructionDecoder dec(buffer,size,block->region()->getArch());
322     Dyninst::InsnAdapter::IA_IAPI* ahPtr = Dyninst::InsnAdapter::IA_IAPI::makePlatformIA_IAPI(func->obj()->cs()->getArch(), dec, addr, func->obj(), block->region(), func->isrc(), NULL);
323
324     while (!ahPtr->hasCFT()) {
325         Instruction i = ahPtr->current_instruction();
326         if (i.getOperation().getID() == e_No_Entry) {
327             return true;
328         }
329         if (i.size() == 2 && i.rawByte(0) == 0x00 && i.rawByte(1) == 0x00) {
330             return true;
331         }
332         ahPtr->advance();
333     }
334     return false;
335 }