1. Assume signed conditional jumps do not bound registers or memory locations
[dyninst.git] / parseAPI / src / IndirectAnalyzer.C
1 #include "IndirectControlFlow.h"
2 #include "BackwardSlicing.h"
3 #include "debug_parse.h"
4
5 #include "CodeObject.h"
6 #include "Graph.h"
7
8 #include "Instruction.h"
9 #include "InstructionDecoder.h"
10
11 static bool UsePC(Instruction::Ptr insn) {
12     vector<Operand> operands;
13     insn->getOperands(operands);
14     
15     for(unsigned int i=0; i<operands.size();++i) {
16         Operand & op = operands[i];
17         set<RegisterAST::Ptr> regs;
18         op.getReadSet(regs);
19         for (auto rit = regs.begin(); rit != regs.end(); ++rit)
20             if ((*rit)->getID().isPC()) return true;
21
22     }
23     return false;
24 }
25
26 bool IndirectControlFlowAnalyzer::FillInOutEdges(BoundValue &target, 
27                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
28     parsing_printf("\t tableBase = %lx, tableSize = %lu, tableStride = %d, targetOffset = %lx, tableLookup = %d, tableOffset = %d, posi = %d\n", target.tableBase, target.value, target.coe, target.targetBase, target.tableLookup, target.tableOffset, target.posi);
29
30     if (!block->obj()->cs()->isValidAddress(target.tableBase)) {
31         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", target.tableBase);
32         return false;
33     }
34
35     for (uint64_t i = 0; i <= target.value; ++i) {
36         Address tableEntry = target.tableBase;
37         Address targetAddress = 0;
38         if (target.posi) tableEntry += target.coe * i; else tableEntry -= target.coe * i;
39         if (target.tableLookup || target.tableOffset) {
40             targetAddress = *(const Address *) block->obj()->cs()->getPtrToInstruction(tableEntry);
41         }
42         if (target.tableOffset && targetAddress != 0) {
43             targetAddress += target.targetBase;
44         }
45
46 //      if (block->obj()->cs()->isCode(targetAddress)) {
47             outEdges.push_back(make_pair(targetAddress, INDIRECT));
48 //      }
49     }
50     return true;
51 }
52
53 bool IndirectControlFlowAnalyzer::NewJumpTableAnalysis(std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
54     parsing_printf("Apply indirect control flow analysis at %lx\n", block->last());
55     FindAllConditionalGuards();
56     ReachFact rf(guards);
57     parsing_printf("Calculate backward slice\n");
58
59     BackwardSlicer bs(func, block, block->last(), guards, rf);
60     GraphPtr slice =  bs.CalculateBackwardSlicing();
61     parsing_printf("Calculate bound facts\n");     
62     BoundFactsCalculator bfc(guards, func, slice, func->entry() == block, rf);
63     bfc.CalculateBoundedFacts();
64
65     BoundValue target;
66     bool ijt = IsJumpTable(slice, bfc, target);
67     if (ijt) {
68         return FillInOutEdges(target, outEdges);
69     } else return false;
70 }                                                      
71
72
73
74 bool IndirectControlFlowAnalyzer::EndWithConditionalJump(ParseAPI::Block * b) {
75
76     const unsigned char * buf = (const unsigned char*) b->obj()->cs()->getPtrToInstruction(b->last());
77     InstructionDecoder dec(buf, b->end() - b->last(), b->obj()->cs()->getArch());
78     Instruction::Ptr insn = dec.decode();
79     entryID id = insn->getOperation().getID();
80
81     if (id == e_jz || id == e_jnz ||
82         id == e_jb || id == e_jnb ||
83         id == e_jbe || id == e_jnbe) return true;
84    
85 //    for (auto eit = b->targets().begin(); eit != b->targets().end(); ++eit)
86 //        if ((*eit)->type() == COND_TAKEN) return true;
87     return false;
88
89 }
90
91 void IndirectControlFlowAnalyzer::GetAllReachableBlock(set<ParseAPI::Block*> &reachable) {
92     queue<Block*> q;
93     q.push(block);
94     while (!q.empty()) {
95         ParseAPI::Block *cur = q.front();
96         q.pop();
97         if (reachable.find(cur) != reachable.end()) continue;
98         reachable.insert(cur);
99         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
100             if ((*eit)->intraproc()) 
101                 q.push((*eit)->src());
102     }
103
104 }
105
106 void IndirectControlFlowAnalyzer::SaveGuardData(ParseAPI::Block *prev) {
107
108     Address curAddr = prev->start();
109     const unsigned char* buf = (const unsigned char*) prev->obj()->cs()->getPtrToInstruction(prev->start());
110     InstructionDecoder dec(buf, prev->end() - prev->start(), prev->obj()->cs()->getArch());
111     Instruction::Ptr insn;
112     vector<pair<Instruction::Ptr, Address> > insns;
113     
114     while ( (insn = dec.decode()) != NULL ) {
115         insns.push_back(make_pair(insn, curAddr));
116         curAddr += insn->size();
117     }
118     
119     for (auto iit = insns.rbegin(); iit != insns.rend(); ++iit) {
120         insn = iit->first;
121         if (insn->getOperation().getID() == e_cmp || insn->getOperation().getID() == e_test) {
122             guards.insert(GuardData(func, prev, insn, insns.rbegin()->first, iit->second, insns.rbegin()->second));
123             parsing_printf("Find guard and cmp pair: cmp %s, addr %lx, cond jump %s, addr %lx\n", insn->format().c_str(), iit->second, insns.rbegin()->first->format().c_str(), insns.rbegin()->second); 
124             break;
125         }    
126     }
127 }
128
129 void IndirectControlFlowAnalyzer::FindAllConditionalGuards(){
130     set<ParseAPI::Block*> visited, reachable;
131     queue<Block*> q;
132     q.push(block);
133     GetAllReachableBlock(reachable);
134
135     while (!q.empty()) {
136         ParseAPI::Block * cur = q.front();
137         q.pop();
138         if (visited.find(cur) != visited.end()) continue;
139         visited.insert(cur);
140
141         // Since a guard has the condition that one branch must always reach the indirect jump,
142         // if the current block can reach a block that cannot reach the indirect jump, 
143         // then all the sources of the current block is not post-dominated by the indirect jump.
144         bool postDominate = true;
145         for (auto eit = cur->targets().begin(); eit != cur->targets().end(); ++eit) 
146             if ((*eit)->intraproc() && (*eit)->type() != INDIRECT)
147                 if (reachable.find((*eit)->trg()) == reachable.end()) postDominate = false;
148         if (!postDominate) continue;
149
150         for (auto eit = cur->sources().begin(); eit != cur->sources().end(); ++eit)
151             if ((*eit)->intraproc()) {
152                 ParseAPI::Block* prev = (*eit)->src();
153                 if (EndWithConditionalJump(prev)) {                
154                     SaveGuardData(prev);
155                 }
156                 else {
157                     q.push(prev);
158                 }
159             }
160     }
161 }
162
163
164
165 bool IndirectControlFlowAnalyzer::IsJumpTable(GraphPtr slice, 
166                                               BoundFactsCalculator &bfc,
167                                               BoundValue &target) {
168     NodeIterator sbegin, send;
169     slice->exitNodes(sbegin, send);
170     for (; sbegin != send; ++sbegin) {
171         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*sbegin);
172         const Absloc &loc = node->assign()->out().absloc();
173         parsing_printf("Checking bound fact at %lx for %s\n",node->addr(), loc.format().c_str()); 
174         BoundFact *bf = bfc.GetBoundFact(*sbegin);
175         if (bf->IsBounded(loc)) {
176             target = *(bf->GetBound(loc));
177
178             if (target.tableLookup) return true;
179             if (target.tableOffset) return true;
180             if (target.type == LessThan && target.CoeBounded() && target.HasTableBase()) return true;
181         }
182     }
183   
184
185     return false;
186 }
187
188 bool IndirectControlFlowPred::endAtPoint(AssignmentPtr ap) {
189         if (ap->insn()->writesMemory()) return true;
190         if (UsePC(ap->insn())) return true;
191         if (ap->insn()->getCategory() == c_CallInsn) return true;
192         return false;
193 }
194
195 bool IndirectControlFlowPred::followCall(ParseAPI::Function* , CallStack_t & , AbsRegion ) {
196
197 /*        ParseAPI::Block * b = callee->entry();
198         vector<pair<Instruction::Ptr, Address> > insns;
199
200         const unsigned char * buf = (const unsigned char*) b->obj()->cs()->getPtrToInstruction(b->start());
201         InstructionDecoder dec(buf, b->end() - b->start(), b->obj()->cs()->getArch());  
202
203         Instruction::Ptr insn;
204         Address curAddr = b->start();
205         int num = 0;
206         while ((insn = dec.decode()) != NULL) {
207             insns.push_back(make_pair(insn, curAddr));
208             curAddr += insn->size();
209             ++num;
210         }
211
212         if (num != 2) return false;
213
214         if (insns[1].first->getCategory() != c_ReturnInsn) return false;
215         if (insns[0].first->getOperation().getID() != e_mov) return false;
216         printf("followCall to %lx\n", callee->addr());
217 */
218         return false;
219
220 }