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