Start to split jump table analysis to two different slices.
[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 #include "IndirectASTVisitor.h"
9
10 #include "Instruction.h"
11 #include "InstructionDecoder.h"
12
13 #include "AbslocInterface.h"
14 #include "SymEval.h"
15
16 using namespace Dyninst;
17 using namespace Dyninst::DataflowAPI;
18 using namespace Dyninst::ParseAPI;
19 using namespace Dyninst::InstructionAPI;
20 // Assume the table contain less than this many entries.
21 #define MAX_TABLE_ENTRY 1000000
22
23
24 static void BuildEdgesAux(SliceNode::Ptr srcNode,
25                           ParseAPI::Block* curBlock,
26                           map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
27                           GraphPtr newG,
28                           set<ParseAPI::Block*> &visit,
29                           EdgeTypeEnum t,
30                           set<ParseAPI::Edge*> allowedEdges) {                   
31     if (targetMap.find(curBlock) != targetMap.end()) {
32         // This block contains at least one silce node 
33         // that is reachable from the source DFS node
34         map<AssignmentPtr, SliceNode::Ptr> &candNodes = targetMap[curBlock];
35         Address addr = 0;
36         for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
37             // The node has to be either in a different block from the source node
38             // or in the same block but has a larger address to be considered 
39             // reachable from the source node
40             if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
41                 if (addr == 0 || addr > cit->first->addr()) {
42                     addr = cit->first->addr();
43                 }
44         if (addr != 0) {
45             // There may be several assignments locating 
46             // at the same address. Need to connecting all.
47             if (t == _edgetype_end_) t = FALLTHROUGH;
48             for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
49                 if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
50                     if (addr == cit->first->addr()) {
51                         newG->insertPair(srcNode, cit->second, TypedSliceEdge::create(srcNode, cit->second, t));
52                     }
53             return;
54         }
55     }
56
57     if (visit.find(curBlock) != visit.end()) return;
58     visit.insert(curBlock);
59     for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit) {
60         // Xiaozhu:
61         // Our current slicing code ignores tail calls 
62         // (the slice code only checks if an edge type is CALL or not)
63         // so, I should be consistent here.
64         // If the slice code considers tail calls, need to change
65         // the predicate to (*eit)->interproc()
66         if ((*eit)->type() != CALL && (*eit)->type() != RET && allowedEdges.find(*eit) != allowedEdges.end()) {
67             EdgeTypeEnum newT = t; 
68             if (t == _edgetype_end_) {
69                 if ((*eit)->type() == COND_TAKEN || (*eit)->type() == COND_NOT_TAKEN) 
70                     newT = (*eit)->type();
71                 else 
72                     newT = FALLTHROUGH;
73             } 
74             BuildEdgesAux(srcNode, (*eit)->trg(), targetMap, newG, visit, newT, allowedEdges);     
75         }
76     }
77 }                         
78
79
80 static void BuildEdges(SliceNode::Ptr curNode,
81                        map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
82                        GraphPtr newG,
83                        set<ParseAPI::Edge*> &allowedEdges) {
84     set<ParseAPI::Block*> visit;                     
85     BuildEdgesAux(curNode, curNode->block(), targetMap, newG, visit, _edgetype_end_, allowedEdges);
86 }                      
87
88 static bool AssignIsZF(Assignment::Ptr a) {
89     return a->out().absloc().type() == Absloc::Register &&
90            (a->out().absloc().reg() == MachRegister::getZeroFlag(a->out().absloc().reg().getArchitecture()));
91 }
92
93 static bool IsPushAndChangeSP(Assignment::Ptr a) {
94     entryID id = a->insn()->getOperation().getID();
95     if (id != e_push) return false;
96     Absloc aloc = a->out().absloc();
97     if (aloc.type() == Absloc::Register && aloc.reg().isStackPointer()) return true;
98     return false;;
99
100 }
101
102 static int AdjustGraphEntryAndExit(GraphPtr gp) {
103     int nodeCount = 0;
104     NodeIterator gbegin, gend;
105     gp->allNodes(gbegin, gend);
106     for (; gbegin != gend; ++gbegin) {
107         ++nodeCount;
108         Node::Ptr ptr = *gbegin;
109         if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
110         if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
111     }
112     return nodeCount;
113 }
114
115 GraphPtr JumpTablePred::BuildAnalysisGraph(set<ParseAPI::Edge*> &visitedEdges) {
116     GraphPtr newG = Graph::createGraph();
117     
118     NodeIterator gbegin, gend;
119     parsing_printf("\t\t start to build analysis graph\n");
120
121     // Create a map to help find whether we have reached a node
122     map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
123
124     // Assignments that are at these addresses have flag assignment colocated
125     set<Address> shouldSkip;
126     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
127         if (AssignIsZF(*ait))
128             shouldSkip.insert((*ait)->addr());
129     }
130     parsing_printf("\t\t calculate skipped nodes\n");
131
132     // We only need one assignment from xchg instruction at each address
133     set<Address> xchgCount;
134     set<Assignment::Ptr> xchgAssign;
135     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
136         if ((*ait)->insn()->getOperation().getID() == e_xchg) {
137             if (xchgCount.find( (*ait)->addr() ) != xchgCount.end() ) continue;
138             xchgCount.insert((*ait)->addr());
139             xchgAssign.insert(*ait);
140         }
141     }
142     parsing_printf("\t\t calculate xchg assignments\n");
143    
144     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
145         Assignment::Ptr a = *ait;
146         if (   (AssignIsZF(a) || shouldSkip.find(a->addr()) == shouldSkip.end()) 
147             && !IsPushAndChangeSP(a)
148             && (!a->insn()->writesMemory() || MatchReadAST(a))) {
149             if (a->insn()->getOperation().getID() == e_xchg && xchgAssign.find(a) == xchgAssign.end()) continue;
150             SliceNode::Ptr newNode = SliceNode::create(a, a->block(), a->func());
151             targetMap[a->block()][a] = newNode;
152             newG->addNode(newNode);
153         }
154     }
155     parsing_printf("\t\t calculate nodes in the new graph\n");
156     // Start from each node to do DFS and build edges
157     newG->allNodes(gbegin, gend);
158     for (; gbegin != gend; ++gbegin) {
159         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*gbegin);
160         BuildEdges(node, targetMap, newG, visitedEdges);
161     }
162     parsing_printf("\t\t calculate edges in the new graph\n");
163
164     // Build a virtual exit node
165     SliceNode::Ptr virtualExit = SliceNode::create(Assignment::Ptr(), NULL, NULL);
166     newG->addNode(virtualExit);
167     newG->allNodes(gbegin, gend);
168     for (; gbegin != gend; ++gbegin) {
169         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(*gbegin);
170         if (!cur->hasOutEdges() && cur != virtualExit) {
171             newG->insertPair(cur, virtualExit, TypedSliceEdge::create(cur, virtualExit, FALLTHROUGH));
172         }
173     }
174     parsing_printf("\t\t calculate virtual nodes in the new graph\n");
175
176     AdjustGraphEntryAndExit(newG);
177
178
179     return newG;
180
181 }
182
183
184 bool JumpTablePred::addNodeCallback(AssignmentPtr ap, set<ParseAPI::Edge*> &visitedEdges) {
185     if (!jumpTableFormat) return false;
186     if (unknownInstruction) return false;
187     if (currentAssigns.find(ap) != currentAssigns.end()) return true;
188     if (currentAssigns.size() > 50) return false; 
189     // For flags, we only analyze zf
190     if (ap->out().absloc().type() == Absloc::Register) {
191         MachRegister reg = ap->out().absloc().reg();
192         if (reg.isFlag() && reg != MachRegister::getZeroFlag(reg.getArchitecture())) {
193             return true;
194         }
195     }
196     pair<AST::Ptr, bool> expandRet = ExpandAssignment(ap);
197
198     currentAssigns.insert(ap);
199
200     parsing_printf("Adding assignment %s in instruction %s at %lx, total %d\n", ap->format().c_str(), ap->insn()->format().c_str(), ap->addr(), currentAssigns.size());
201 /*
202     if (ap->insn() && ap->insn()->readsMemory() && firstMemoryRead) {
203         firstMemoryRead = false;
204         parsing_printf("\tThe first memory read, check if format is correct\n");
205         if 
206     }
207 */
208
209     if (!expandRet.second || expandRet.first == NULL) {
210         if (ap && ap->block() && ap->block()->obj()->cs()->getArch() == Arch_aarch64) {
211             unknownInstruction = true;
212         }
213         return true;
214     }
215
216     // If this assignment writes memory,
217     // we only want to analyze it when it writes to 
218     // an AST we have seen before and potentially
219     // can used for aliasing
220     if (ap->insn()->writesMemory()) {
221         if (!MatchReadAST(ap)) return true;
222     }
223
224     // If this assignment reads memory,
225     // we record the AST of the read so
226     // that in the future we can match a
227     // corresponding write to identify aliasing
228     if (ap->insn()->readsMemory() && expandRet.first->getID() == AST::V_RoseAST) {
229         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(expandRet.first);
230         if (roseAST->val().op == ROSEOperation::derefOp) {
231             readAST.push_back(expandRet.first);
232         }
233     }
234     // I really do not want to redo the analysis from scratch,
235     // but it seems like with newly added edges and nodes,
236     // it is necessary to redo.
237
238     // We create the CFG based on the found nodes
239     GraphPtr g = BuildAnalysisGraph(visitedEdges);
240     BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, false, expandCache);
241     bfc.CalculateBoundedFacts();
242
243     BoundValue target;
244     bool ijt = IsJumpTable(g, bfc, target);
245     if (ijt) {
246         bool ret = !FillInOutEdges(target, outEdges) || outEdges.empty();
247         // Now we have stopped slicing in advance, so the cache contents are not complete any more.
248         if (!ret) setClearCache(true);
249         return ret;
250     } else {
251         return true;
252     }   
253
254
255
256 }
257 bool JumpTablePred::FillInOutEdges(BoundValue &target, 
258                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
259     if (target.values != NULL) {
260         outEdges.clear();
261         for (auto tit = target.values->begin(); tit != target.values->end(); ++tit) {
262             outEdges.push_back(make_pair(*tit, INDIRECT));
263         }
264         return true;
265     }
266     set<int64_t> jumpTargets;                                            
267     if (!PerformTableRead(target, jumpTargets, block->obj()->cs())) {
268         jumpTableFormat = false;
269         return false;
270     }
271     outEdges.clear();
272     for (auto tit = jumpTargets.begin(); tit != jumpTargets.end(); ++tit) {
273         outEdges.push_back(make_pair(*tit, INDIRECT));
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     VariableAST::Ptr ip = VariableAST::create(Variable(loc));
290     BoundValue *tarBoundValue = bf->GetBound(ip);
291     if (tarBoundValue != NULL) {
292         target = *(tarBoundValue);
293         uint64_t s;
294         if (target.values == NULL)
295             s = target.interval.size();
296         else
297             s = target.values->size();
298         if (s > 0 && s <= MAX_TABLE_ENTRY) return true;
299     }
300     AST::Ptr ipExp = bf->GetAlias(ip);
301     if (ipExp) {
302         parsing_printf("\t jump target expression %s\n", ipExp->format().c_str());
303         JumpTableFormatVisitor jtfv(block);
304         ipExp->accept(&jtfv);
305         if (!jtfv.format) {
306             parsing_printf("\t Not jump table format!\n");
307             jumpTableFormat = false;
308         }
309     }
310
311     return false;
312 }
313
314 bool JumpTablePred::MatchReadAST(Assignment::Ptr a) {
315     pair<AST::Ptr, bool> expandRet = ExpandAssignment(a);
316     if (!expandRet.second || expandRet.first == NULL) return false;
317     if (a->out().generator() == NULL) return false;
318     AST::Ptr write = SimplifyAnAST(RoseAST::create(ROSEOperation(ROSEOperation::derefOp, a->out().size()), a->out().generator()), 
319                                    PCValue(a->addr(),
320                                            a->insn()->size(),
321                                            a->block()->obj()->cs()->getArch()));
322
323     if (write == NULL) return false;
324     for (auto ait = readAST.begin(); ait != readAST.end(); ++ait) 
325         if (*write == **ait) return true;
326     return false;
327 }
328
329