1. When we find potential indexing variable with table stride being 1, we need to...
[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     
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->obj()->cs()->getPtrToInstruction(block->last());
77     InstructionDecoder dec(buf, InstructionDecoder::maxInstructionLength, block->obj()->cs()->getArch());
78     Instruction::Ptr 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     JumpTableFormatPred jtfp(func, block, rf, thunks, se);
87     GraphPtr slice = formatSlicer.backwardSlice(jtfp);
88     //parsing_printf("\tJump table format: %s\n", jtfp.format().c_str());
89     // If the jump target expression is not in a form we recognize,
90     // we do not try to resolve it
91     parsing_printf("In function %s, Address %lx, jump target format %s, index loc %s, index variable %s", func->name().c_str(), block->last(), jtfp.format().c_str(), jtfp.indexLoc ? jtfp.indexLoc->format().c_str() : "" , jtfp.index.format().c_str() );
92
93     bool variableArguFormat = false;
94     if (!jtfp.isJumpTableFormat()) {
95         parsing_printf(" not jump table\n");
96         if (jtfp.jumpTargetExpr && func->entry() == block && IsVariableArgumentFormat(jtfp.jumpTargetExpr, jtfp.index)) {
97             parsing_printf("\tVariable number of arguments format, index %s\n", jtfp.index.format().c_str());
98             variableArguFormat = true;
99         } else {
100             return false;
101         }
102     }
103
104     StridedInterval b;
105     if (!variableArguFormat) {
106         Slicer indexSlicer(jtfp.indexLoc, jtfp.indexLoc->block(), func, false, false); 
107         JumpTableIndexPred jtip(func, block, jtfp.index, se);
108         jtip.setSearchForControlFlowDep(true);
109         slice = indexSlicer.backwardSlice(jtip);
110     
111         if (!jtip.findBound && block->obj()->cs()->getArch() != Arch_aarch64) {
112
113             // After the slicing is done, we do one last check to 
114             // see if we can resolve the indirect jump by assuming 
115             // one byte read is in bound [0,255]
116             GraphPtr g = jtip.BuildAnalysisGraph(indexSlicer.visitedEdges);
117             BoundFactsCalculator bfc(func, g, func->entry() == block,  true, se);
118             bfc.CalculateBoundedFacts();
119         
120             StridedInterval target;
121             jtip.IsIndexBounded(g, bfc, target);
122         }
123         if (jtip.findBound) {
124             parsing_printf(" bound %s", jtip.bound.format().c_str());
125             b = jtip.bound;
126         } else {
127             parsing_printf(" Cannot find bound, assume there are at most 256 entries and scan the table\n");
128             b = StridedInterval(1, 0, 255);
129         }
130     } else {
131         b = StridedInterval(1, 0, 8);
132     }
133     std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > > jumpTableOutEdges;
134     ReadTable(jtfp.jumpTargetExpr, 
135               jtfp.index, 
136               b, 
137               GetMemoryReadSize(jtfp.memLoc), 
138               jtfp.constAddr,
139               jumpTableOutEdges);
140     parsing_printf(", find %d edges\n", jumpTableOutEdges.size());            
141     outEdges.insert(outEdges.end(), jumpTableOutEdges.begin(), jumpTableOutEdges.end());
142     return !jumpTableOutEdges.empty();
143 }                                                      
144
145
146
147
148 // Find all blocks that reach the block containing the indirect jump
149 void IndirectControlFlowAnalyzer::GetAllReachableBlock() {
150     reachable.clear();
151     queue<Block*> q;
152     q.push(block);
153     while (!q.empty()) {
154         ParseAPI::Block *cur = q.front();
155         q.pop();
156         if (reachable.find(cur) != reachable.end()) continue;
157         reachable.insert(cur);
158         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
159             if ((*eit)->intraproc()) {
160                 if ((*eit)->src() == NULL) {
161                     fprintf(stderr, "edge type = %d, target block [%lx, %lx)\n", (*eit)->type(), cur->start(), cur->end());
162                 }
163                 q.push((*eit)->src());
164             }
165     }
166
167 }
168
169
170 static Address ThunkAdjustment(Address afterThunk, MachRegister reg, ParseAPI::Block *b) {
171     // After the call to thunk, there is usually
172     // an add insturction like ADD ebx, OFFSET to adjust
173     // the value coming out of thunk.
174    
175     const unsigned char* buf = (const unsigned char*) (b->obj()->cs()->getPtrToInstruction(afterThunk));
176     InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
177     Instruction::Ptr nextInsn = dec.decode();
178     // It has to be an add
179     if (nextInsn->getOperation().getID() != e_add) return 0;
180     vector<Operand> operands;
181     nextInsn->getOperands(operands);
182     RegisterAST::Ptr regAST = boost::dynamic_pointer_cast<RegisterAST>(operands[0].getValue());
183     // The first operand should be a register
184     if (regAST == 0) return 0;
185     if (regAST->getID() != reg) return 0;
186     Result res = operands[1].getValue()->eval();
187     // A not defined result means that
188     // the second operand is not an immediate
189     if (!res.defined) return 0;
190     return res.convert<Address>();
191 }
192
193 void IndirectControlFlowAnalyzer::FindAllThunks() {
194     // Enumuerate every block to find thunk
195     for (auto bit = reachable.begin(); bit != reachable.end(); ++bit) {
196         // We intentional treat a getting PC call as a special case that does not
197         // end a basic block. So, we need to check every instruction to find all thunks
198         ParseAPI::Block *b = *bit;
199         const unsigned char* buf =
200             (const unsigned char*)(b->obj()->cs()->getPtrToInstruction(b->start()));
201         if( buf == NULL ) {
202             parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",FILE__, __LINE__);
203             return;
204         }
205         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
206         InsnAdapter::IA_IAPI* block = InsnAdapter::IA_IAPI::makePlatformIA_IAPI(b->obj()->cs()->getArch(), dec, b->start(), b->obj() , b->region(), b->obj()->cs(), b);
207         Address cur = b->start();
208         while (cur < b->end()) {
209             if (block->getInstruction()->getCategory() == c_CallInsn && block->isThunk()) {
210                 bool valid;
211                 Address addr;
212                 boost::tie(valid, addr) = block->getCFT();
213                 const unsigned char *target = (const unsigned char *) b->obj()->cs()->getPtrToInstruction(addr);
214                 InstructionDecoder targetChecker(target, InstructionDecoder::maxInstructionLength, b->obj()->cs()->getArch());
215                 Instruction::Ptr thunkFirst = targetChecker.decode();
216                 set<RegisterAST::Ptr> thunkTargetRegs;
217                 thunkFirst->getWriteSet(thunkTargetRegs);
218                 
219                 for (auto curReg = thunkTargetRegs.begin(); curReg != thunkTargetRegs.end(); ++curReg) {
220                     ThunkInfo t;
221                     t.reg = (*curReg)->getID();
222                     t.value = block->getAddr() + block->getInstruction()->size();
223                     t.value += ThunkAdjustment(t.value, t.reg, b);
224                     t.block = b;
225                     thunks.insert(make_pair(block->getAddr(), t));
226                     parsing_printf("\tfind thunk at %lx, storing value %lx to %s\n", block->getAddr(), t.value , t.reg.name().c_str());
227                 }
228             }
229             cur += block->getInstruction()->size();
230             if (cur < b->end()) block->advance();
231         }
232         delete block;
233     }
234 }
235
236 void IndirectControlFlowAnalyzer::ReadTable(AST::Ptr jumpTargetExpr, 
237                                             AbsRegion index,
238                                             StridedInterval &indexBound,   
239                                             int memoryReadSize,
240                                             set<Address> &constAddr,
241                                             std::vector<std::pair<Address, Dyninst::ParseAPI::EdgeTypeEnum> > &targetEdges) {
242     CodeSource *cs = block->obj()->cs();                                            
243     set<Address> jumpTargets;
244     for (int v = indexBound.low; v <= indexBound.high; v += indexBound.stride) {
245         // TODO: need to detect whether the memory is a zero extend or a sign extend
246         JumpTableReadVisitor jtrv(index, v, cs, false, memoryReadSize);
247         jumpTargetExpr->accept(&jtrv);
248         if (jtrv.valid && cs->isCode(jtrv.targetAddress)) {
249             bool stop = false;
250             set<Block*> blocks;
251             block->obj()->findCurrentBlocks(block->region(), jtrv.targetAddress, blocks);
252             for (auto bit = blocks.begin(); bit != blocks.end(); ++bit) {
253                 if ((*bit)->start() < jtrv.targetAddress && jtrv.targetAddress <= (*bit)->end()) {
254                     Block::Insns insns;
255                     (*bit)->getInsns(insns);
256                     if (insns.find(jtrv.targetAddress) == insns.end()) {
257                         stop = true;
258                         parsing_printf("WARNING: resolving jump tables leads to address %lx, which causes overlapping instructions in basic blocks [%lx,%lx)\n", jtrv.targetAddress, (*bit)->start(), (*bit)->end());
259                         break;
260                     }
261                 }
262             }
263             // Assume that indirect jump should not jump beyond the function range.
264             // This assumption is shaky in terms of non-contiguous functions.
265             // But non-contiguous blocks tend not be reach by indirect jumps
266             if (func->src() == HINT) {
267                 Hint h(func->addr(), 0 , NULL, "");
268                 auto range = equal_range(cs->hints().begin(), cs->hints().end(), h);
269                 if (range.first != range.second && range.first != cs->hints().end()) {
270                     Address startAddr = range.first->_addr;
271                     int size = range.first->_size;
272                     if (jtrv.targetAddress < startAddr || jtrv.targetAddress >= startAddr + size) {
273                         stop = true;
274                         parsing_printf("WARNING: resolving jump tables leads to address %lx, which is not in the function range specified in the symbol table\n", jtrv.targetAddress);                  
275                         parsing_printf("\tSymbol at %lx, end at %lx\n", startAddr, startAddr + size);
276                     }
277                 }
278             }
279             if (stop) break;
280             jumpTargets.insert(jtrv.targetAddress);
281         } else {
282             // We have a bad entry. We stop here, as we have wrong information
283             // In this case, we keep the good entries
284             parsing_printf("WARNING: resolving jump tables leads to a bad address %lx\n", jtrv.targetAddress);
285             break;
286         }
287         if (indexBound.stride == 0) break;
288     }
289     for (auto ait = constAddr.begin(); ait != constAddr.end(); ++ait) {
290         if (cs->isCode(*ait)) {
291             jumpTargets.insert(*ait);
292         }
293     }
294     for (auto tit = jumpTargets.begin(); tit != jumpTargets.end(); ++tit) {
295         targetEdges.push_back(make_pair(*tit, INDIRECT));
296     }
297 }                                           
298
299 int IndirectControlFlowAnalyzer::GetMemoryReadSize(Assignment::Ptr memLoc) {
300     if (!memLoc) return 0;
301     Instruction::Ptr i = memLoc->insn();
302     std::vector<Operand> ops;
303     i->getOperands(ops);
304     for (auto oit = ops.begin(); oit != ops.end(); ++oit) {
305         Operand o = *oit;
306         if (o.readsMemory()) {
307             Expression::Ptr exp = o.getValue();
308             return exp->size();
309         }
310     }
311     return 0;
312 }