5 #include "debug_parse.h"
6 #include "CodeObject.h"
7 #include "JumpTablePred.h"
8 #include "IndirectASTVisitor.h"
10 #include "Instruction.h"
11 #include "InstructionDecoder.h"
13 #include "AbslocInterface.h"
16 using namespace Dyninst;
17 using namespace Dyninst::DataflowAPI;
18 using namespace Dyninst::ParseAPI;
19 using namespace Dyninst::InstructionAPI;
20 #define SIGNEX_64_32 0xffffffff00000000LL
21 #define SIGNEX_64_16 0xffffffffffff0000LL
22 #define SIGNEX_64_8 0xffffffffffffff00LL
23 #define SIGNEX_32_16 0xffff0000
24 #define SIGNEX_32_8 0xffffff00
26 // Assume the table contain less than this many entries.
27 #define MAX_TABLE_ENTRY 1000000
29 static void BuildEdgesAux(SliceNode::Ptr srcNode,
30 ParseAPI::Block* curBlock,
31 map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
33 set<ParseAPI::Block*> &visit,
35 if (targetMap.find(curBlock) != targetMap.end()) {
36 // This block contains at least one silce node
37 // that is reachable from the source DFS node
38 map<AssignmentPtr, SliceNode::Ptr> &candNodes = targetMap[curBlock];
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();
49 // There may be several assignments locating
50 // at the same address. Need to connecting all.
51 if (t == _edgetype_end_) t = FALLTHROUGH;
52 for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
53 if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
54 if (addr == cit->first->addr()) {
55 newG->insertPair(srcNode, cit->second, TypedSliceEdge::create(srcNode, cit->second, t));
61 if (visit.find(curBlock) != visit.end()) return;
62 visit.insert(curBlock);
63 for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit)
65 // Our current slicing code ignores tail calls
66 // (the slice code only checks if an edge type is CALL or not)
67 // so, I should be consistent here.
68 // If the slice code considers tail calls, need to change
69 // the predicate to (*eit)->interproc()
70 if ((*eit)->type() != CALL && (*eit)->type() != RET) {
71 EdgeTypeEnum newT = t;
72 if (t == _edgetype_end_) {
73 if ((*eit)->type() == COND_TAKEN || (*eit)->type() == COND_NOT_TAKEN)
74 newT = (*eit)->type();
78 BuildEdgesAux(srcNode, (*eit)->trg(), targetMap, newG, visit, newT);
83 static void BuildEdges(SliceNode::Ptr curNode,
84 map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
86 set<ParseAPI::Block*> visit;
87 BuildEdgesAux(curNode, curNode->block(), targetMap, newG, visit, _edgetype_end_);
90 static bool AssignIsZF(Assignment::Ptr a) {
91 return a->out().absloc().type() == Absloc::Register &&
92 (a->out().absloc().reg() == x86::zf || a->out().absloc().reg() == x86_64::zf);
95 static bool IsPushAndChangeSP(Assignment::Ptr a) {
96 entryID id = a->insn()->getOperation().getID();
97 if (id != e_push) return false;
98 Absloc aloc = a->out().absloc();
99 if (aloc.type() == Absloc::Register && aloc.reg().isStackPointer()) return true;
104 static int AdjustGraphEntryAndExit(GraphPtr gp) {
106 NodeIterator gbegin, gend;
107 gp->allNodes(gbegin, gend);
108 for (; gbegin != gend; ++gbegin) {
110 Node::Ptr ptr = *gbegin;
111 if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
112 if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
118 GraphPtr JumpTablePred::BuildAnalysisGraph() {
119 GraphPtr newG = Graph::createGraph();
121 NodeIterator gbegin, gend;
123 // Create a map to help find whether we have reached a node
124 map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
126 // Assignments that are at these addresses have flag assignment colocated
127 set<Address> shouldSkip;
128 for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
129 if (AssignIsZF(*ait))
130 shouldSkip.insert((*ait)->addr());
132 for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
133 Assignment::Ptr a = *ait;
134 if ( (AssignIsZF(a) || shouldSkip.find(a->addr()) == shouldSkip.end())
135 && !IsPushAndChangeSP(a)
136 && (!a->insn()->writesMemory() || MatchReadAST(a))) {
137 SliceNode::Ptr newNode = SliceNode::create(a, a->block(), a->func());
138 targetMap[a->block()][a] = newNode;
139 newG->addNode(newNode);
143 // Start from each node to do DFS and build edges
144 newG->allNodes(gbegin, gend);
145 for (; gbegin != gend; ++gbegin) {
146 SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*gbegin);
147 BuildEdges(node, targetMap, newG);
150 // Build a virtual exit node
151 SliceNode::Ptr virtualExit = SliceNode::create(Assignment::Ptr(), NULL, NULL);
152 newG->addNode(virtualExit);
153 newG->allNodes(gbegin, gend);
154 for (; gbegin != gend; ++gbegin) {
155 SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(*gbegin);
156 if (!cur->hasOutEdges() && cur != virtualExit) {
157 newG->insertPair(cur, virtualExit, TypedSliceEdge::create(cur, virtualExit, FALLTHROUGH));
161 AdjustGraphEntryAndExit(newG);
169 bool JumpTablePred::endAtPoint(AssignmentPtr ap) {
170 if (ap->insn()->writesMemory()) return true;
173 bool JumpTablePred::addNodeCallback(AssignmentPtr ap) {
174 if (currentAssigns.find(ap) != currentAssigns.end()) return true;
176 // For flags, we only analyze zf
177 if (ap->out().absloc().type() == Absloc::Register && ap->out().absloc().reg().regClass() == x86::FLAG &&
178 ap->out().absloc().reg() != x86::zf && ap->out().absloc().reg() != x86_64::zf) {
182 pair<AST::Ptr, bool> expandRet = ExpandAssignment(ap);
183 // If we do not have semantics for this instruction,
184 // we assume it does not influence the calculation of jump targets
185 if (!expandRet.second || expandRet.first == NULL) return true;
188 // fprintf(stderr, "Adding assignment %s in instruction %s at %lx\n", ap->format().c_str(), ap->insn()->format().c_str(), ap->addr());
189 currentAssigns.insert(ap);
191 // If this assignment writes memory,
192 // we only want to analyze it when it writes to
193 // an AST we have seen before and potentially
194 // can used for aliasing
195 if (ap->insn()->writesMemory()) {
196 if (!MatchReadAST(ap)) return true;
199 // If this assignment reads memory,
200 // we record the AST of the read so
201 // that in the future we can match a
202 // corresponding write to identify aliasing
203 if (ap->insn()->readsMemory() && expandRet.first->getID() == AST::V_RoseAST) {
204 RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(expandRet.first);
205 if (roseAST->val().op == ROSEOperation::derefOp) {
206 readAST.push_back(expandRet.first);
210 // We create the CFG based on the found nodes
211 GraphPtr g = BuildAnalysisGraph();
213 BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, block->last(), expandCache);
214 bfc.CalculateBoundedFacts();
217 bool ijt = IsJumpTable(g, bfc, target);
219 bool ret = !FillInOutEdges(target, outEdges);
220 // fprintf(stderr, "Return %s\n", ret ? "true" : "false");
221 // if (dyn_debug_parsing) exit(0);
224 // fprintf(stderr, "Return true\n");
225 // if (dyn_debug_parsing) exit(0);
233 bool JumpTablePred::FillInOutEdges(BoundValue &target,
234 vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
236 Address tableBase = target.interval.low;
237 Address tableLastEntry = target.interval.high;
238 Architecture arch = block->obj()->cs()->getArch();
239 if (arch == Arch_x86) {
240 tableBase &= 0xffffffff;
241 tableLastEntry &= 0xffffffff;
244 #if defined(os_windows)
245 tableBase -= block->obj()->cs()->loadAddress();
246 tableLastEntry -= block->obj()->cs()->loadAddress();
249 parsing_printf("The final target bound fact:\n");
251 if (!block->obj()->cs()->isValidAddress(tableBase)) {
252 parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
256 for (Address tableEntry = tableBase; tableEntry <= tableLastEntry; tableEntry += target.interval.stride) {
257 if (!block->obj()->cs()->isValidAddress(tableEntry)) continue;
258 Address targetAddress = 0;
259 if (target.tableReadSize > 0) {
260 // Assume the table contents are moved in a sign extended way;
261 switch (target.tableReadSize) {
263 targetAddress = *(const uint64_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
266 targetAddress = *(const uint32_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
267 if ((arch == Arch_x86_64) && (targetAddress & 0x80000000)) {
268 targetAddress |= SIGNEX_64_32;
272 targetAddress = *(const uint16_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
273 if ((arch == Arch_x86_64) && (targetAddress & 0x8000)) {
274 targetAddress |= SIGNEX_64_16;
276 if ((arch == Arch_x86) && (targetAddress & 0x8000)) {
277 targetAddress |= SIGNEX_32_16;
282 targetAddress = *(const uint8_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
283 if ((arch == Arch_x86_64) && (targetAddress & 0x80)) {
284 targetAddress |= SIGNEX_64_8;
286 if ((arch == Arch_x86) && (targetAddress & 0x80)) {
287 targetAddress |= SIGNEX_32_8;
293 parsing_printf("Invalid memory read size %d\n", target.tableReadSize);
296 if (targetAddress != 0) {
297 if (target.isSubReadContent)
298 targetAddress = target.targetBase - targetAddress;
300 targetAddress += target.targetBase;
303 #if defined(os_windows)
304 targetAddress -= block->obj()->cs()->loadAddress();
306 } else targetAddress = tableEntry;
308 if (block->obj()->cs()->getArch() == Arch_x86) targetAddress &= 0xffffffff;
309 parsing_printf("Jumping to target %lx,", targetAddress);
310 if (block->obj()->cs()->isCode(targetAddress)) {
311 outEdges.push_back(make_pair(targetAddress, INDIRECT));
312 parsing_printf(" is code.\n" );
314 parsing_printf(" not code.\n");
316 // If the jump target is resolved to be a constant,
317 if (target.interval.stride == 0) break;
321 bool JumpTablePred::IsJumpTable(GraphPtr slice,
322 BoundFactsCalculator &bfc,
323 BoundValue &target) {
324 NodeIterator exitBegin, exitEnd, srcBegin, srcEnd;
325 slice->exitNodes(exitBegin, exitEnd);
326 SliceNode::Ptr virtualExit = boost::static_pointer_cast<SliceNode>(*exitBegin);
327 virtualExit->ins(srcBegin, srcEnd);
328 SliceNode::Ptr jumpNode = boost::static_pointer_cast<SliceNode>(*srcBegin);
330 const Absloc &loc = jumpNode->assign()->out().absloc();
331 parsing_printf("Checking final bound fact for %s\n",loc.format().c_str());
332 BoundFact *bf = bfc.GetBoundFactOut(virtualExit);
333 BoundValue *tarBoundValue = bf->GetBound(VariableAST::create(Variable(loc)));
334 if (tarBoundValue != NULL) {
335 target = *(tarBoundValue);
336 uint64_t s = target.interval.size();
337 if (s > 0 && s <= MAX_TABLE_ENTRY) return true;
342 bool JumpTablePred::MatchReadAST(Assignment::Ptr a) {
343 pair<AST::Ptr, bool> expandRet = ExpandAssignment(a);
344 if (!expandRet.second || expandRet.first == NULL) return false;
345 if (a->out().generator() == NULL) return false;
346 AST::Ptr write = SimplifyAnAST(RoseAST::create(ROSEOperation(ROSEOperation::derefOp, a->out().size()), a->out().generator()), a->insn()->size());
348 if (write == NULL) return false;
349 for (auto ait = readAST.begin(); ait != readAST.end(); ++ait)
350 if (*write == **ait) return true;
354 pair<AST::Ptr, bool> JumpTablePred::ExpandAssignment(Assignment::Ptr assign) {
355 if (expandCache.find(assign) != expandCache.end()) {
356 AST::Ptr ast = expandCache[assign];
357 // if (ast) return make_pair(DeepCopyAnAST(ast), true); else return make_pair(ast, false);
358 if (ast) return make_pair(ast, true); else return make_pair(ast, false);
361 pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
362 if (expandRet.second && expandRet.first) {
363 AST::Ptr calculation = SimplifyAnAST(expandRet.first, assign->insn()->size());
364 //expandCache[assign] = DeepCopyAnAST(expandRet.first);
365 expandCache[assign] = calculation;
367 expandCache[assign] = AST::Ptr();
369 return make_pair( expandCache[assign], expandRet.second );