If the destination operand is a memory location, we need to use the generator of...
[dyninst.git] / parseAPI / src / JumpTablePred.C
1 #include "dyntypes.h"
2 #include "Node.h"
3 #include "Graph.h"
4
5 #include "debug_parse.h"
6 #include "CodeObject.h"
7 #include "JumpTablePred.h"
8
9 #include "Instruction.h"
10 #include "InstructionDecoder.h"
11
12 #include "AbslocInterface.h"
13 #include "SymEval.h"
14
15 using namespace Dyninst;
16 using namespace Dyninst::DataflowAPI;
17 using namespace Dyninst::ParseAPI;
18 using namespace Dyninst::InstructionAPI;
19 #define SIGNEX_64_32 0xffffffff00000000LL
20 #define SIGNEX_64_16 0xffffffffffff0000LL
21 #define SIGNEX_64_8  0xffffffffffffff00LL
22 #define SIGNEX_32_16 0xffff0000
23 #define SIGNEX_32_8 0xffffff00
24
25 // Assume the table contain less than this many entries.
26 #define MAX_TABLE_ENTRY 1000000
27
28 static void BuildEdgesAux(SliceNode::Ptr srcNode,
29                           ParseAPI::Block* curBlock,
30                           map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
31                           GraphPtr newG,
32                           set<ParseAPI::Block*> &visit,
33                           EdgeTypeEnum t) {                      
34     if (targetMap.find(curBlock) != targetMap.end()) {
35         // This block contains at least one silce node 
36         // that is reachable from the source DFS node
37         map<AssignmentPtr, SliceNode::Ptr> &candNodes = targetMap[curBlock];
38         Address addr = 0;
39         for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
40             // The node has to be either in a different block from the source node
41             // or in the same block but has a larger address to be considered 
42             // reachable from the source node
43             if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
44                 if (addr == 0 || addr > cit->first->addr()) {
45                     addr = cit->first->addr();
46                 }
47         if (addr != 0) {
48             // There may be several assignments locating 
49             // at the same address. Need to connecting all.
50             if (t == _edgetype_end_) t = FALLTHROUGH;
51             for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
52                 if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
53                     if (addr == cit->first->addr()) {
54                         newG->insertPair(srcNode, cit->second, TypedSliceEdge::create(srcNode, cit->second, t));
55                     }
56             return;
57         }
58     }
59
60     if (visit.find(curBlock) != visit.end()) return;
61     visit.insert(curBlock);
62     for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit)
63         // Xiaozhu:
64         // Our current slicing code ignores tail calls 
65         // (the slice code only checks if an edge type is CALL or not)
66         // so, I should be consistent here.
67         // If the slice code considers tail calls, need to change
68         // the predicate to (*eit)->interproc()
69         if ((*eit)->type() != CALL && (*eit)->type() != RET) {
70             EdgeTypeEnum newT = t; 
71             if (t == _edgetype_end_) {
72                 if ((*eit)->type() == COND_TAKEN || (*eit)->type() == COND_NOT_TAKEN) 
73                     newT = (*eit)->type();
74                 else 
75                     newT = FALLTHROUGH;
76             } 
77             BuildEdgesAux(srcNode, (*eit)->trg(), targetMap, newG, visit, newT);           
78         }
79 }                         
80
81
82 static void BuildEdges(SliceNode::Ptr curNode,
83                        map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
84                        GraphPtr newG) {
85     set<ParseAPI::Block*> visit;                     
86     BuildEdgesAux(curNode, curNode->block(), targetMap, newG, visit, _edgetype_end_);
87 }                      
88
89 static bool AssignIsZF(Assignment::Ptr a) {
90     return a->out().absloc().type() == Absloc::Register &&
91            (a->out().absloc().reg() == x86::zf || a->out().absloc().reg() == x86_64::zf);
92 }
93 static int AdjustGraphEntryAndExit(GraphPtr gp) {
94     int nodeCount = 0;
95     NodeIterator gbegin, gend;
96     gp->allNodes(gbegin, gend);
97     for (; gbegin != gend; ++gbegin) {
98         ++nodeCount;
99         Node::Ptr ptr = *gbegin;
100         if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
101         if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
102     }
103     return nodeCount;
104 }
105
106
107 GraphPtr JumpTablePred::BuildAnalysisGraph() {
108     GraphPtr newG = Graph::createGraph();
109     
110     NodeIterator gbegin, gend;
111     
112     // Create a map to help find whether we have reached a node
113     map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
114
115     // Assignments that are at these addresses have flag assignment colocated
116     set<Address> shouldSkip;
117     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
118         if (AssignIsZF(*ait))
119             shouldSkip.insert((*ait)->addr());
120     }
121     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
122         Assignment::Ptr a = *ait;
123         if (AssignIsZF(a) || shouldSkip.find(a->addr()) == shouldSkip.end()) {
124             SliceNode::Ptr newNode = SliceNode::create(a, a->block(), a->func());
125             targetMap[a->block()][a] = newNode;
126             newG->addNode(newNode);
127         }
128     }
129
130     // Start from each node to do DFS and build edges
131     newG->allNodes(gbegin, gend);
132     for (; gbegin != gend; ++gbegin) {
133         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*gbegin);
134         BuildEdges(node, targetMap, newG);
135     }
136
137     // Build a virtual exit node
138     SliceNode::Ptr virtualExit = SliceNode::create(Assignment::Ptr(), NULL, NULL);
139     newG->addNode(virtualExit);
140     newG->allNodes(gbegin, gend);
141     for (; gbegin != gend; ++gbegin) {
142         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(*gbegin);
143         if (!cur->hasOutEdges() && cur != virtualExit) {
144             newG->insertPair(cur, virtualExit, TypedSliceEdge::create(cur, virtualExit, FALLTHROUGH));
145         }
146     }
147
148     AdjustGraphEntryAndExit(newG);
149
150
151     return newG;
152
153 }
154
155
156 bool JumpTablePred::endAtPoint(AssignmentPtr ap) {
157         if (ap->insn()->writesMemory()) return true;
158         return false;
159 }
160 bool JumpTablePred::addNodeCallback(AssignmentPtr ap) {
161     if (currentAssigns.find(ap) != currentAssigns.end()) return true;
162     
163     // We only analyze zf
164     if (ap->out().absloc().type() == Absloc::Register && ap->out().absloc().reg().regClass() == x86::FLAG &&
165        ap->out().absloc().reg() != x86::zf && ap->out().absloc().reg() != x86_64::zf) {
166         return true;
167     }
168     fprintf(stderr, "Adding assignment %s in instruction %s at %lx\n", ap->format().c_str(), ap->insn()->format().c_str(), ap->addr());
169     currentAssigns.insert(ap);
170     if (currentAssigns.size() < 5) return true; 
171     GraphPtr g = BuildAnalysisGraph();
172
173     BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, block->last());
174     bfc.CalculateBoundedFacts();
175
176     BoundValue target;
177     bool ijt = IsJumpTable(g, bfc, target);
178 //    if (dyn_debug_parsing) exit(0);
179     if (ijt) {
180         bool ret = !FillInOutEdges(target, outEdges);
181         fprintf(stderr, "Return %s\n", ret ? "true" : "false");
182         return ret;
183     } else {
184         fprintf(stderr, "Return true\n");
185         return true;
186     }   
187
188
189
190 }
191 bool JumpTablePred::FillInOutEdges(BoundValue &target, 
192                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
193     outEdges.clear();
194     Address tableBase = target.interval.low;
195     Address tableLastEntry = target.interval.high;
196     Architecture arch = block->obj()->cs()->getArch();
197     if (arch == Arch_x86) {
198         tableBase &= 0xffffffff;
199         tableLastEntry &= 0xffffffff;
200     }
201
202 #if defined(os_windows)
203     tableBase -= block->obj()->cs()->loadAddress();
204     tableLastEntry -= block->obj()->cs()->loadAddress();
205 #endif
206
207     parsing_printf("The final target bound fact:\n");
208     target.Print();
209     if (!block->obj()->cs()->isValidAddress(tableBase)) {
210         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
211         return false;
212     }
213
214     for (Address tableEntry = tableBase; tableEntry <= tableLastEntry; tableEntry += target.interval.stride) {
215         if (!block->obj()->cs()->isValidAddress(tableEntry)) continue;
216         Address targetAddress = 0;
217         if (target.isTableRead) {
218             // Two assumptions:
219             // 1. Assume the table contents are moved in a sign extended way;
220             // 2. Assume memory access size is the same as the table stride
221             switch (target.interval.stride) {
222                 case 8:
223                     targetAddress = *(const uint64_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
224                     break;
225                 case 4:
226                     targetAddress = *(const uint32_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
227                     if ((arch == Arch_x86_64) && (targetAddress & 0x80000000)) {
228                         targetAddress |= SIGNEX_64_32;
229                     }
230                     break;
231                 case 2:
232                     targetAddress = *(const uint16_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
233                     if ((arch == Arch_x86_64) && (targetAddress & 0x8000)) {
234                         targetAddress |= SIGNEX_64_16;
235                     }
236                     if ((arch == Arch_x86) && (targetAddress & 0x8000)) {
237                         targetAddress |= SIGNEX_32_16;
238                     }
239
240                     break;
241                 case 1:
242                     targetAddress = *(const uint8_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
243                     if ((arch == Arch_x86_64) && (targetAddress & 0x80)) {
244                         targetAddress |= SIGNEX_64_8;
245                     }
246                     if ((arch == Arch_x86) && (targetAddress & 0x80)) {
247                         targetAddress |= SIGNEX_32_8;
248                     }
249
250                     break;
251
252                 default:
253                     parsing_printf("Invalid table stride %d\n", target.interval.stride);
254                     return false;
255             }
256             if (targetAddress != 0) {
257                 if (target.isSubReadContent) 
258                     targetAddress = target.targetBase - targetAddress;
259                 else 
260                     targetAddress += target.targetBase; 
261
262             }
263 #if defined(os_windows)
264             targetAddress -= block->obj()->cs()->loadAddress();
265 #endif
266         } else targetAddress = tableEntry;
267
268         if (block->obj()->cs()->getArch() == Arch_x86) targetAddress &= 0xffffffff;
269         parsing_printf("Jumping to target %lx,", targetAddress);
270         if (block->obj()->cs()->isCode(targetAddress)) {
271             outEdges.push_back(make_pair(targetAddress, INDIRECT));
272             parsing_printf(" is code.\n" );
273         } else {
274             parsing_printf(" not code.\n");
275         }
276         // If the jump target is resolved to be a constant, 
277         if (target.interval.stride == 0) break;
278     }
279     return true;
280 }
281 bool JumpTablePred::IsJumpTable(GraphPtr slice, 
282                                               BoundFactsCalculator &bfc,
283                                               BoundValue &target) {
284     NodeIterator exitBegin, exitEnd, srcBegin, srcEnd;
285     slice->exitNodes(exitBegin, exitEnd);
286     SliceNode::Ptr virtualExit = boost::static_pointer_cast<SliceNode>(*exitBegin);
287     virtualExit->ins(srcBegin, srcEnd);
288     SliceNode::Ptr jumpNode = boost::static_pointer_cast<SliceNode>(*srcBegin);
289     
290     const Absloc &loc = jumpNode->assign()->out().absloc();
291     parsing_printf("Checking final bound fact for %s\n",loc.format().c_str()); 
292     BoundFact *bf = bfc.GetBoundFactOut(virtualExit);
293     BoundValue *tarBoundValue = bf->GetBound(VariableAST::create(Variable(loc)));
294     if (tarBoundValue != NULL) {
295         target = *(tarBoundValue);
296         uint64_t s = target.interval.size();
297         if (s > 0 && s <= MAX_TABLE_ENTRY) return true;
298     }
299     return false;
300 }