Start to split jump table analysis to two different slices.
[dyninst.git] / parseAPI / src / IndirectAnalyzer.C
1 #include "dyntypes.h"
2 #include "IndirectAnalyzer.h"
3 //#include "BoundFactCalculator.h"
4 #include "JumpTableFormatPred.h"
5 #include "SymbolicExpression.h"
6 #include "IA_IAPI.h"
7 #include "debug_parse.h"
8
9 #include "CodeObject.h"
10 #include "Graph.h"
11
12 #include "Instruction.h"
13 #include "InstructionDecoder.h"
14 #include "Register.h"
15 #include "SymEval.h"
16 using namespace Dyninst::ParseAPI;
17 using namespace Dyninst::InstructionAPI;
18
19
20 bool IndirectControlFlowAnalyzer::NewJumpTableAnalysis(std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
21 //    if (block->last() == 0x3ed4f33e9e) dyn_debug_parsing=1; else dyn_debug_parsing=0;
22     parsing_printf("Apply indirect control flow analysis at %lx\n", block->last());
23     parsing_printf("Looking for thunk\n");
24
25 //  Find all blocks that reach the block containing the indirect jump
26 //  This is a prerequisit for finding thunks
27     GetAllReachableBlock();
28 //  Now we try to find all thunks in this function.
29 //  We pass in the slice because we may need to add new ndoes.
30     FindAllThunks();
31 //  Calculates all blocks that can reach
32 //  and be reachable from thunk blocks
33     ReachFact rf(thunks);
34
35     // Now we start with the indirect jump instruction,
36     // to determine the format of the (potential) jump table
37     const unsigned char * buf = (const unsigned char*) block->obj()->cs()->getPtrToInstruction(block->last());
38     InstructionDecoder dec(buf, InstructionDecoder::maxInstructionLength, block->obj()->cs()->getArch());
39     Instruction::Ptr insn = dec.decode();
40     AssignmentConverter ac(true, false);
41     vector<Assignment::Ptr> assignments;
42     ac.convert(insn, block->last(), func, block, assignments);
43     Slicer formatSlicer(assignments[0], block, func, false, false);
44
45     SymbolicExpression se;
46     JumpTableFormatPred jtfp(func, block, rf, thunks, se);
47     GraphPtr slice = formatSlicer.backwardSlice(jtfp);
48     //parsing_printf("\tJump table format: %s\n", jtfp.format().c_str());
49
50     // If the jump target expression is not in a form we recognize,
51     // we do not try to resolve it
52     if (!jtfp.isJumpTableFormat()) {
53         return false;
54     }
55 /*
56     Slicer indexSlicer(); 
57     JumpTableIndexPred jtip(func, block, jtfp.indexVarible());
58     jtip.setSearchForControlFlowDep(true);
59     GraphPtr slice = indexSlicer.backwardSlice(jtp);
60     
61     if (!jtip.indexBounded() && block->obj()->cs()->getArch() != Arch_aarch64) {
62         // After the slicing is done, we do one last check to 
63         // see if we can resolve the indirect jump by assuming 
64         // one byte read is in bound [0,255]
65         GraphPtr g = jtp.BuildAnalysisGraph(s.visitedEdges);
66         
67         BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, true, jtp.expandCache);
68         bfc.CalculateBoundedFacts();
69         
70         BoundValue target;
71         bool ijt = jtp.IsJumpTable(g, bfc, target);
72         if (ijt) jtp.FillInOutEdges(target, jumpTableOutEdges);
73     }
74
75     
76     if (!jtip.indexBounded()) {
77          indexBound = ScanTable(jtfp);
78     } else {
79          indexBound = jtip.indexBound();
80     }
81
82     std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > > jumpTableOutEdges;
83     ReadTable(jtfp, indexBound);
84
85     outEdges.insert(outEdges.end(), jumpTableOutEdges.begin(), jumpTableOutEdges.end());
86     return !jumpTableOutEdges.empty();
87 */
88     return false;
89 }                                                      
90
91
92
93
94 // Find all blocks that reach the block containing the indirect jump
95 void IndirectControlFlowAnalyzer::GetAllReachableBlock() {
96     reachable.clear();
97     queue<Block*> q;
98     q.push(block);
99     while (!q.empty()) {
100         ParseAPI::Block *cur = q.front();
101         q.pop();
102         if (reachable.find(cur) != reachable.end()) continue;
103         reachable.insert(cur);
104         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
105             if ((*eit)->intraproc()) 
106                 q.push((*eit)->src());
107     }
108
109 }
110
111
112 static Address ThunkAdjustment(Address afterThunk, MachRegister reg, ParseAPI::Block *b) {
113     // After the call to thunk, there is usually
114     // an add insturction like ADD ebx, OFFSET to adjust
115     // the value coming out of thunk.
116    
117     const unsigned char* buf = (const unsigned char*) (b->obj()->cs()->getPtrToInstruction(afterThunk));
118     InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
119     Instruction::Ptr nextInsn = dec.decode();
120     // It has to be an add
121     if (nextInsn->getOperation().getID() != e_add) return 0;
122     vector<Operand> operands;
123     nextInsn->getOperands(operands);
124     RegisterAST::Ptr regAST = boost::dynamic_pointer_cast<RegisterAST>(operands[0].getValue());
125     // The first operand should be a register
126     if (regAST == 0) return 0;
127     if (regAST->getID() != reg) return 0;
128     Result res = operands[1].getValue()->eval();
129     // A not defined result means that
130     // the second operand is not an immediate
131     if (!res.defined) return 0;
132     return res.convert<Address>();
133 }
134
135 void IndirectControlFlowAnalyzer::FindAllThunks() {
136     // Enumuerate every block to find thunk
137     for (auto bit = reachable.begin(); bit != reachable.end(); ++bit) {
138         // We intentional treat a getting PC call as a special case that does not
139         // end a basic block. So, we need to check every instruction to find all thunks
140         ParseAPI::Block *b = *bit;
141         const unsigned char* buf =
142             (const unsigned char*)(b->obj()->cs()->getPtrToInstruction(b->start()));
143         if( buf == NULL ) {
144             parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",FILE__, __LINE__);
145             return;
146         }
147         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
148         InsnAdapter::IA_IAPI block(dec, b->start(), b->obj() , b->region(), b->obj()->cs(), b);
149         Address cur = b->start();
150         while (cur < b->end()) {
151             if (block.getInstruction()->getCategory() == c_CallInsn && block.isThunk()) {
152                 bool valid;
153                 Address addr;
154                 boost::tie(valid, addr) = block.getCFT();
155                 const unsigned char *target = (const unsigned char *) b->obj()->cs()->getPtrToInstruction(addr);
156                 InstructionDecoder targetChecker(target, InstructionDecoder::maxInstructionLength, b->obj()->cs()->getArch());
157                 Instruction::Ptr thunkFirst = targetChecker.decode();
158                 set<RegisterAST::Ptr> thunkTargetRegs;
159                 thunkFirst->getWriteSet(thunkTargetRegs);
160                 
161                 for (auto curReg = thunkTargetRegs.begin(); curReg != thunkTargetRegs.end(); ++curReg) {
162                     ThunkInfo t;
163                     t.reg = (*curReg)->getID();
164                     t.value = block.getAddr() + block.getInstruction()->size();
165                     t.value += ThunkAdjustment(t.value, t.reg, b);
166                     t.block = b;
167                     thunks.insert(make_pair(block.getAddr(), t));
168                     parsing_printf("\tfind thunk at %lx, storing value %lx to %s\n", block.getAddr(), t.value , t.reg.name().c_str());
169                 }
170             }
171             cur += block.getInstruction()->size();
172             if (cur < b->end()) block.advance();
173         }
174     }
175 }
176
177