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