1. Handle the instruction sequence that push a constant and then immediately pop...
[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
21 //    if (block->last() != 0x80a922d) return false;
22 //    parsing_printf("Apply indirect control flow analysis at %lx\n", block->last());
23 //      fprintf(stderr,"Apply indirect control flow analysis at %lx\n", block->last());
24
25 //    parsing_printf("Calculate backward slice\n");
26
27 //    BackwardSlicer bs(func, block, block->last());
28 //    GraphPtr slice =  bs.CalculateBackwardSlicing();
29
30     parsing_printf("Looking for thunk\n");
31 //  Find all blocks that reach the block containing the indirect jump
32 //  This is a prerequisit for finding thunks
33     GetAllReachableBlock();
34 //  Now we try to find all thunks in this function.
35 //  We pass in the slice because we may need to add new ndoes.
36 //    FindAllThunks(slice);
37 //  Calculates all blocks that can reach
38 //  and be reachable from thunk blocks
39     ReachFact rf(thunks);
40
41     
42     const unsigned char * buf = (const unsigned char*) block->obj()->cs()->getPtrToInstruction(block->last());
43     InstructionDecoder dec(buf, InstructionDecoder::maxInstructionLength, block->obj()->cs()->getArch());
44     Instruction::Ptr insn = dec.decode();
45     AssignmentConverter ac(true, false);
46     vector<Assignment::Ptr> assignments;
47     ac.convert(insn, block->last(), func, block, assignments);
48     Slicer s(assignments[0], block, func);
49     
50     JumpTablePred jtp(func, block, rf, thunks, outEdges);
51     GraphPtr slice = s.backwardSlice(jtp);
52
53     return !outEdges.empty();
54 }                                                      
55
56
57
58
59 // Find all blocks that reach the block containing the indirect jump
60 void IndirectControlFlowAnalyzer::GetAllReachableBlock() {
61     reachable.clear();
62     queue<Block*> q;
63     q.push(block);
64     while (!q.empty()) {
65         ParseAPI::Block *cur = q.front();
66         q.pop();
67         if (reachable.find(cur) != reachable.end()) continue;
68         reachable.insert(cur);
69         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
70             if ((*eit)->intraproc()) 
71                 q.push((*eit)->src());
72     }
73
74 }
75
76
77 static Address ThunkAdjustment(Address afterThunk, MachRegister reg, GraphPtr slice, ParseAPI::Block *b) {
78     // After the call to thunk, there is usually
79     // an add insturction like ADD ebx, OFFSET to adjust
80     // the value coming out of thunk.
81     // This add instruction may not be in the slice.
82     // Here assume that if the next instruction after thunk
83     // is to add a constant value to the thunk register,
84     // we then adjust the value.
85     NodeIterator nbegin, nend;
86     slice->allNodes(nbegin, nend);
87     for (; nbegin != nend; ++nbegin) {
88         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(*nbegin);
89         // If the next instruction is already in the slice,
90         // there is no need to adjust
91         if (cur->addr() == afterThunk) return 0;
92     }
93     
94     const unsigned char* buf = (const unsigned char*) (b->obj()->cs()->getPtrToInstruction(afterThunk));
95     InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
96     Instruction::Ptr nextInsn = dec.decode();
97     // It has to be an add
98     if (nextInsn->getOperation().getID() != e_add) return 0;
99     vector<Operand> operands;
100     nextInsn->getOperands(operands);
101     RegisterAST::Ptr regAST = boost::dynamic_pointer_cast<RegisterAST>(operands[0].getValue());
102     // The first operand should be a register
103     if (regAST == 0) return 0;
104     if (regAST->getID() != reg) return 0;
105     Result res = operands[1].getValue()->eval();
106     // A not defined result means that
107     // the second operand is not an immediate
108     if (!res.defined) return 0;
109     return res.convert<Address>();
110 }
111
112 void IndirectControlFlowAnalyzer::FindAllThunks(GraphPtr slice) {
113     // Enumuerate every block to find thunk
114     for (auto bit = reachable.begin(); bit != reachable.end(); ++bit) {
115         // We intentional treat a getting PC call as a special case that does not
116         // end a basic block. So, we need to check every instruction to find all thunks
117         ParseAPI::Block *b = *bit;
118         const unsigned char* buf =
119             (const unsigned char*)(b->obj()->cs()->getPtrToInstruction(b->start()));
120         if( buf == NULL ) {
121             parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",FILE__, __LINE__);
122             return;
123         }
124         parsing_printf("Looking for thunk in block [%lx,%lx).", b->start(), b->end());
125         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());
126         InsnAdapter::IA_IAPI block(dec, b->start(), b->obj() , b->region(), b->obj()->cs(), b);
127         while (block.getAddr() < b->end()) {
128             if (block.getInstruction()->getCategory() == c_CallInsn && block.isThunk()) {
129                 bool valid;
130                 Address addr;
131                 boost::tie(valid, addr) = block.getCFT();
132                 const unsigned char *target = (const unsigned char *) b->obj()->cs()->getPtrToInstruction(addr);
133                 InstructionDecoder targetChecker(target, InstructionDecoder::maxInstructionLength, b->obj()->cs()->getArch());
134                 Instruction::Ptr thunkFirst = targetChecker.decode();
135                 set<RegisterAST::Ptr> thunkTargetRegs;
136                 thunkFirst->getWriteSet(thunkTargetRegs);
137                 
138                 for (auto curReg = thunkTargetRegs.begin(); curReg != thunkTargetRegs.end(); ++curReg) {
139                     ThunkInfo t;
140                     t.reg = (*curReg)->getID();
141                     t.value = block.getAddr() + block.getInstruction()->size();
142                     t.value += ThunkAdjustment(t.value, t.reg, slice, b);
143                     t.block = b;
144                     thunks.insert(make_pair(block.getAddr(), t));
145                     parsing_printf("\tfind thunk at %lx, storing value %lx to %s\n", block.getAddr(), t.value , t.reg.name().c_str());
146                 }
147             }
148             block.advance();
149         }
150     }
151 }
152
153