1. Handle the instruction sequence that push a constant and then immediately pop...
[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
94 static bool IsPushAndChangeSP(Assignment::Ptr a) {
95     entryID id = a->insn()->getOperation().getID();
96     if (id != e_push) return false;
97     Absloc aloc = a->out().absloc();
98     if (aloc.type() == Absloc::Register && aloc.reg().isStackPointer()) return true;
99     return false;;
100
101 }
102
103 static int AdjustGraphEntryAndExit(GraphPtr gp) {
104     int nodeCount = 0;
105     NodeIterator gbegin, gend;
106     gp->allNodes(gbegin, gend);
107     for (; gbegin != gend; ++gbegin) {
108         ++nodeCount;
109         Node::Ptr ptr = *gbegin;
110         if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
111         if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
112     }
113     return nodeCount;
114 }
115
116
117 GraphPtr JumpTablePred::BuildAnalysisGraph() {
118     GraphPtr newG = Graph::createGraph();
119     
120     NodeIterator gbegin, gend;
121     
122     // Create a map to help find whether we have reached a node
123     map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
124
125     // Assignments that are at these addresses have flag assignment colocated
126     set<Address> shouldSkip;
127     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
128         if (AssignIsZF(*ait))
129             shouldSkip.insert((*ait)->addr());
130     }
131     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
132         Assignment::Ptr a = *ait;
133         if ( (AssignIsZF(a) || shouldSkip.find(a->addr()) == shouldSkip.end()) && !IsPushAndChangeSP(a)) {
134             SliceNode::Ptr newNode = SliceNode::create(a, a->block(), a->func());
135             targetMap[a->block()][a] = newNode;
136             newG->addNode(newNode);
137         }
138     }
139
140     // Start from each node to do DFS and build edges
141     newG->allNodes(gbegin, gend);
142     for (; gbegin != gend; ++gbegin) {
143         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*gbegin);
144         BuildEdges(node, targetMap, newG);
145     }
146
147     // Build a virtual exit node
148     SliceNode::Ptr virtualExit = SliceNode::create(Assignment::Ptr(), NULL, NULL);
149     newG->addNode(virtualExit);
150     newG->allNodes(gbegin, gend);
151     for (; gbegin != gend; ++gbegin) {
152         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(*gbegin);
153         if (!cur->hasOutEdges() && cur != virtualExit) {
154             newG->insertPair(cur, virtualExit, TypedSliceEdge::create(cur, virtualExit, FALLTHROUGH));
155         }
156     }
157
158     AdjustGraphEntryAndExit(newG);
159
160
161     return newG;
162
163 }
164
165
166 bool JumpTablePred::endAtPoint(AssignmentPtr ap) {
167         if (ap->insn()->writesMemory()) return true;
168         return false;
169 }
170 bool JumpTablePred::addNodeCallback(AssignmentPtr ap) {
171     if (currentAssigns.find(ap) != currentAssigns.end()) return true;
172     
173     // We only analyze zf
174     if (ap->out().absloc().type() == Absloc::Register && ap->out().absloc().reg().regClass() == x86::FLAG &&
175        ap->out().absloc().reg() != x86::zf && ap->out().absloc().reg() != x86_64::zf) {
176         return true;
177     }
178 //    fprintf(stderr, "Adding assignment %s in instruction %s at %lx\n", ap->format().c_str(), ap->insn()->format().c_str(), ap->addr());
179     currentAssigns.insert(ap);
180 //    if (currentAssigns.size() < 5) return true; 
181     GraphPtr g = BuildAnalysisGraph();
182
183     BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, block->last());
184     bfc.CalculateBoundedFacts();
185
186     BoundValue target;
187     bool ijt = IsJumpTable(g, bfc, target);
188     if (ijt) {
189         bool ret = !FillInOutEdges(target, outEdges);
190 //      fprintf(stderr, "Return %s\n", ret ? "true" : "false");
191 //      if (dyn_debug_parsing) exit(0);
192         return ret;
193     } else {
194 //        fprintf(stderr, "Return true\n");
195 //      if (dyn_debug_parsing) exit(0);
196
197         return true;
198     }   
199
200
201
202 }
203 bool JumpTablePred::FillInOutEdges(BoundValue &target, 
204                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
205     outEdges.clear();
206     Address tableBase = target.interval.low;
207     Address tableLastEntry = target.interval.high;
208     Architecture arch = block->obj()->cs()->getArch();
209     if (arch == Arch_x86) {
210         tableBase &= 0xffffffff;
211         tableLastEntry &= 0xffffffff;
212     }
213
214 #if defined(os_windows)
215     tableBase -= block->obj()->cs()->loadAddress();
216     tableLastEntry -= block->obj()->cs()->loadAddress();
217 #endif
218
219     parsing_printf("The final target bound fact:\n");
220     target.Print();
221     if (!block->obj()->cs()->isValidAddress(tableBase)) {
222         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
223         return false;
224     }
225
226     for (Address tableEntry = tableBase; tableEntry <= tableLastEntry; tableEntry += target.interval.stride) {
227         if (!block->obj()->cs()->isValidAddress(tableEntry)) continue;
228         Address targetAddress = 0;
229         if (target.tableReadSize > 0) {
230             // Assume the table contents are moved in a sign extended way;
231             switch (target.tableReadSize) {
232                 case 8:
233                     targetAddress = *(const uint64_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
234                     break;
235                 case 4:
236                     targetAddress = *(const uint32_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
237                     if ((arch == Arch_x86_64) && (targetAddress & 0x80000000)) {
238                         targetAddress |= SIGNEX_64_32;
239                     }
240                     break;
241                 case 2:
242                     targetAddress = *(const uint16_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
243                     if ((arch == Arch_x86_64) && (targetAddress & 0x8000)) {
244                         targetAddress |= SIGNEX_64_16;
245                     }
246                     if ((arch == Arch_x86) && (targetAddress & 0x8000)) {
247                         targetAddress |= SIGNEX_32_16;
248                     }
249
250                     break;
251                 case 1:
252                     targetAddress = *(const uint8_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
253                     if ((arch == Arch_x86_64) && (targetAddress & 0x80)) {
254                         targetAddress |= SIGNEX_64_8;
255                     }
256                     if ((arch == Arch_x86) && (targetAddress & 0x80)) {
257                         targetAddress |= SIGNEX_32_8;
258                     }
259
260                     break;
261
262                 default:
263                     parsing_printf("Invalid memory read size %d\n", target.tableReadSize);
264                     return false;
265             }
266             if (targetAddress != 0) {
267                 if (target.isSubReadContent) 
268                     targetAddress = target.targetBase - targetAddress;
269                 else 
270                     targetAddress += target.targetBase; 
271
272             }
273 #if defined(os_windows)
274             targetAddress -= block->obj()->cs()->loadAddress();
275 #endif
276         } else targetAddress = tableEntry;
277
278         if (block->obj()->cs()->getArch() == Arch_x86) targetAddress &= 0xffffffff;
279         parsing_printf("Jumping to target %lx,", targetAddress);
280         if (block->obj()->cs()->isCode(targetAddress)) {
281             outEdges.push_back(make_pair(targetAddress, INDIRECT));
282             parsing_printf(" is code.\n" );
283         } else {
284             parsing_printf(" not code.\n");
285         }
286         // If the jump target is resolved to be a constant, 
287         if (target.interval.stride == 0) break;
288     }
289     return true;
290 }
291 bool JumpTablePred::IsJumpTable(GraphPtr slice, 
292                                               BoundFactsCalculator &bfc,
293                                               BoundValue &target) {
294     NodeIterator exitBegin, exitEnd, srcBegin, srcEnd;
295     slice->exitNodes(exitBegin, exitEnd);
296     SliceNode::Ptr virtualExit = boost::static_pointer_cast<SliceNode>(*exitBegin);
297     virtualExit->ins(srcBegin, srcEnd);
298     SliceNode::Ptr jumpNode = boost::static_pointer_cast<SliceNode>(*srcBegin);
299     
300     const Absloc &loc = jumpNode->assign()->out().absloc();
301     parsing_printf("Checking final bound fact for %s\n",loc.format().c_str()); 
302     BoundFact *bf = bfc.GetBoundFactOut(virtualExit);
303     BoundValue *tarBoundValue = bf->GetBound(VariableAST::create(Variable(loc)));
304     if (tarBoundValue != NULL) {
305         target = *(tarBoundValue);
306         uint64_t s = target.interval.size();
307         if (s > 0 && s <= MAX_TABLE_ENTRY) return true;
308     }
309     return false;
310 }