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 #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
  25
  26 // Assume the table contain less than this many entries.
  27 #define MAX_TABLE_ENTRY 1000000
  28
  29 static void BuildEdgesAux(SliceNode::Ptr srcNode,
  30                           ParseAPI::Block* curBlock,
  31                           map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
  32                           GraphPtr newG,
  33                           set<ParseAPI::Block*> &visit,
  34                           EdgeTypeEnum t,
  35                           set<ParseAPI::Edge*> allowedEdges) {
  36     if (targetMap.find(curBlock) != targetMap.end()) {
  37         // This block contains at least one silce node
  38         // that is reachable from the source DFS node
  39         map<AssignmentPtr, SliceNode::Ptr> &candNodes = targetMap[curBlock];
  40         Address addr = 0;
  41         for (auto cit = candNodes.begin(); cit != candNodes.end(); ++cit)
  42             // The node has to be either in a different block from the source node
  43             // or in the same block but has a larger address to be considered
  44             // reachable from the source node
  45             if (cit->first->addr() > srcNode->addr() || curBlock != srcNode->block())
  46                 if (addr == 0 || addr > cit->first->addr()) {
  47                     addr = cit->first->addr();
  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 && allowedEdges.find(*eit) != allowedEdges.end()) {
  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, allowedEdges);
  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::Edge*> &allowedEdges) {
  88     set<ParseAPI::Block*> visit;
  89     BuildEdgesAux(curNode, curNode->block(), targetMap, newG, visit, _edgetype_end_, allowedEdges);
  90 }
  91
  92 static bool AssignIsZF(Assignment::Ptr a) {
  93     return a->out().absloc().type() == Absloc::Register &&
  94            (a->out().absloc().reg() == x86::zf || a->out().absloc().reg() == x86_64::zf);
  95 }
  96
  97 static bool IsPushAndChangeSP(Assignment::Ptr a) {
  98     entryID id = a->insn()->getOperation().getID();
  99     if (id != e_push) return false;
 100     Absloc aloc = a->out().absloc();
 101     if (aloc.type() == Absloc::Register && aloc.reg().isStackPointer()) return true;
 102     return false;;
 103
 104 }
 105
 106 static int AdjustGraphEntryAndExit(GraphPtr gp) {
 107     int nodeCount = 0;
 108     NodeIterator gbegin, gend;
 109     gp->allNodes(gbegin, gend);
 110     for (; gbegin != gend; ++gbegin) {
 111         ++nodeCount;
 112         Node::Ptr ptr = *gbegin;
 113         if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
 114         if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
 115     }
 116     return nodeCount;
 117 }
 118
 119
 120 GraphPtr JumpTablePred::BuildAnalysisGraph(set<ParseAPI::Edge*> &visitedEdges) {
 121     GraphPtr newG = Graph::createGraph();
 122
 123     NodeIterator gbegin, gend;
 124
 125     // Create a map to help find whether we have reached a node
 126     map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
 127
 128     // Assignments that are at these addresses have flag assignment colocated
 129     set<Address> shouldSkip;
 130     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
 131         if (AssignIsZF(*ait))
 132             shouldSkip.insert((*ait)->addr());
 133     }
 134     // We only need one assignment from xchg instruction at each address
 135     set<Address> xchgCount;
 136     set<Assignment::Ptr> xchgAssign;
 137     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
 138         if ((*ait)->insn()->getOperation().getID() == e_xchg) {
 139             if (xchgCount.find( (*ait)->addr() ) != xchgCount.end() ) continue;
 140             xchgCount.insert((*ait)->addr());
 141             xchgAssign.insert(*ait);
 142         }
 143     }
 144
 145     for (auto ait = currentAssigns.begin(); ait != currentAssigns.end(); ++ait) {
 146         Assignment::Ptr a = *ait;
 147         if (   (AssignIsZF(a) || shouldSkip.find(a->addr()) == shouldSkip.end())
 148             && !IsPushAndChangeSP(a)
 149             && (!a->insn()->writesMemory() || MatchReadAST(a))) {
 150             if (a->insn()->getOperation().getID() == e_xchg && xchgAssign.find(a) == xchgAssign.end()) continue;
 151             SliceNode::Ptr newNode = SliceNode::create(a, a->block(), a->func());
 152             targetMap[a->block()][a] = newNode;
 153             newG->addNode(newNode);
 154         }
 155     }
 156
 157     // Start from each node to do DFS and build edges
 158     newG->allNodes(gbegin, gend);
 159     for (; gbegin != gend; ++gbegin) {
 160         SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(*gbegin);
 161         BuildEdges(node, targetMap, newG, visitedEdges);
 162     }
 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
 175     AdjustGraphEntryAndExit(newG);
 176
 177
 178     return newG;
 179
 180 }
 181
 182
 183 bool JumpTablePred::endAtPoint(AssignmentPtr ap) {
 184 //        if (ap->insn()->writesMemory()) return true;
 185         return false;
 186 }
 187 bool JumpTablePred::addNodeCallback(AssignmentPtr ap, set<ParseAPI::Edge*> &visitedEdges) {
 188     if (currentAssigns.find(ap) != currentAssigns.end()) return true;
 189     if (currentAssigns.size() > 30) return false;
 190     // For flags, we only analyze zf
 191     if (ap->out().absloc().type() == Absloc::Register && ap->out().absloc().reg().regClass() == x86::FLAG &&
 192        ap->out().absloc().reg() != x86::zf && ap->out().absloc().reg() != x86_64::zf) {
 193         return true;
 194     }
 195
 196     pair<AST::Ptr, bool> expandRet = ExpandAssignment(ap);
 197
 198     currentAssigns.insert(ap);
 199
 200     //fprintf(stderr, "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 (!expandRet.second || expandRet.first == NULL) return true;
 203
 204     // If this assignment writes memory,
 205     // we only want to analyze it when it writes to
 206     // an AST we have seen before and potentially
 207     // can used for aliasing
 208     if (ap->insn()->writesMemory()) {
 209         if (!MatchReadAST(ap)) return true;
 210     }
 211
 212     // If this assignment reads memory,
 213     // we record the AST of the read so
 214     // that in the future we can match a
 215     // corresponding write to identify aliasing
 216     if (ap->insn()->readsMemory() && expandRet.first->getID() == AST::V_RoseAST) {
 217         RoseAST::Ptr roseAST = boost::static_pointer_cast<RoseAST>(expandRet.first);
 218         if (roseAST->val().op == ROSEOperation::derefOp) {
 219             readAST.push_back(expandRet.first);
 220         }
 221     }
 222
 223     // We create the CFG based on the found nodes
 224     GraphPtr g = BuildAnalysisGraph(visitedEdges);
 225
 226     BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, block->last(), false, expandCache);
 227     bfc.CalculateBoundedFacts();
 228
 229     BoundValue target;
 230     bool ijt = IsJumpTable(g, bfc, target);
 231     if (ijt) {
 232         bool ret = !FillInOutEdges(target, outEdges) || outEdges.empty();
 233         if (!ret) setCache(false);
 234         //      fprintf(stderr, "Return %s\n", ret ? "true" : "false");
 235 //      if (dyn_debug_parsing) exit(0);
 236         return ret;
 237     } else {
 238 //        fprintf(stderr, "Return true\n");
 239 //      if (dyn_debug_parsing) exit(0);
 240
 241         return true;
 242     }
 243
 244
 245
 246 }
 247 bool JumpTablePred::FillInOutEdges(BoundValue &target,
 248                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
 249     outEdges.clear();
 250     Address tableBase = target.interval.low;
 251     Address tableLastEntry = target.interval.high;
 252     Architecture arch = block->obj()->cs()->getArch();
 253     if (arch == Arch_x86) {
 254         tableBase &= 0xffffffff;
 255         tableLastEntry &= 0xffffffff;
 256     }
 257
 258 #if defined(os_windows)
 259     tableBase -= block->obj()->cs()->loadAddress();
 260     tableLastEntry -= block->obj()->cs()->loadAddress();
 261 #endif
 262
 263     parsing_printf("The final target bound fact:\n");
 264     target.Print();
 265     if (!block->obj()->cs()->isValidAddress(tableBase)) {
 266         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
 267         return false;
 268     }
 269
 270     for (Address tableEntry = tableBase; tableEntry <= tableLastEntry; tableEntry += target.interval.stride) {
 271         if (!block->obj()->cs()->isValidAddress(tableEntry)) continue;
 272         Address targetAddress = 0;
 273         if (target.tableReadSize > 0) {
 274             // Assume the table contents are moved in a sign extended way;
 275             switch (target.tableReadSize) {
 276                 case 8:
 277                     targetAddress = *(const uint64_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 278                     break;
 279                 case 4:
 280                     targetAddress = *(const uint32_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 281                     if ((arch == Arch_x86_64) && (targetAddress & 0x80000000)) {
 282                         targetAddress |= SIGNEX_64_32;
 283                     }
 284                     break;
 285                 case 2:
 286                     targetAddress = *(const uint16_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 287                     if ((arch == Arch_x86_64) && (targetAddress & 0x8000)) {
 288                         targetAddress |= SIGNEX_64_16;
 289                     }
 290                     if ((arch == Arch_x86) && (targetAddress & 0x8000)) {
 291                         targetAddress |= SIGNEX_32_16;
 292                     }
 293
 294                     break;
 295                 case 1:
 296                     targetAddress = *(const uint8_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 297                     if ((arch == Arch_x86_64) && (targetAddress & 0x80)) {
 298                         targetAddress |= SIGNEX_64_8;
 299                     }
 300                     if ((arch == Arch_x86) && (targetAddress & 0x80)) {
 301                         targetAddress |= SIGNEX_32_8;
 302                     }
 303
 304                     break;
 305
 306                 default:
 307                     parsing_printf("Invalid memory read size %d\n", target.tableReadSize);
 308                     return false;
 309             }
 310             if (targetAddress != 0) {
 311                 if (target.isSubReadContent)
 312                     targetAddress = target.targetBase - targetAddress;
 313                 else
 314                     targetAddress += target.targetBase;
 315
 316             }
 317 #if defined(os_windows)
 318             targetAddress -= block->obj()->cs()->loadAddress();
 319 #endif
 320         } else targetAddress = tableEntry;
 321
 322         if (block->obj()->cs()->getArch() == Arch_x86) targetAddress &= 0xffffffff;
 323         parsing_printf("Jumping to target %lx,", targetAddress);
 324         if (block->obj()->cs()->isCode(targetAddress)) {
 325             outEdges.push_back(make_pair(targetAddress, INDIRECT));
 326             parsing_printf(" is code.\n" );
 327         } else {
 328             parsing_printf(" not code.\n");
 329         }
 330         // If the jump target is resolved to be a constant,
 331         if (target.interval.stride == 0) break;
 332     }
 333     return true;
 334 }
 335 bool JumpTablePred::IsJumpTable(GraphPtr slice,
 336                                               BoundFactsCalculator &bfc,
 337                                               BoundValue &target) {
 338     NodeIterator exitBegin, exitEnd, srcBegin, srcEnd;
 339     slice->exitNodes(exitBegin, exitEnd);
 340     SliceNode::Ptr virtualExit = boost::static_pointer_cast<SliceNode>(*exitBegin);
 341     virtualExit->ins(srcBegin, srcEnd);
 342     SliceNode::Ptr jumpNode = boost::static_pointer_cast<SliceNode>(*srcBegin);
 343
 344     const Absloc &loc = jumpNode->assign()->out().absloc();
 345     parsing_printf("Checking final bound fact for %s\n",loc.format().c_str());
 346     BoundFact *bf = bfc.GetBoundFactOut(virtualExit);
 347     BoundValue *tarBoundValue = bf->GetBound(VariableAST::create(Variable(loc)));
 348     if (tarBoundValue != NULL) {
 349         target = *(tarBoundValue);
 350         uint64_t s = target.interval.size();
 351         if (s > 0 && s <= MAX_TABLE_ENTRY) return true;
 352     }
 353     return false;
 354 }
 355
 356 bool JumpTablePred::MatchReadAST(Assignment::Ptr a) {
 357     pair<AST::Ptr, bool> expandRet = ExpandAssignment(a);
 358     if (!expandRet.second || expandRet.first == NULL) return false;
 359     if (a->out().generator() == NULL) return false;
 360     AST::Ptr write = SimplifyAnAST(RoseAST::create(ROSEOperation(ROSEOperation::derefOp, a->out().size()), a->out().generator()), a->insn()->size());
 361
 362     if (write == NULL) return false;
 363     for (auto ait = readAST.begin(); ait != readAST.end(); ++ait)
 364         if (*write == **ait) return true;
 365     return false;
 366 }
 367
 368 pair<AST::Ptr, bool> JumpTablePred::ExpandAssignment(Assignment::Ptr assign) {
 369     if (expandCache.find(assign) != expandCache.end()) {
 370         AST::Ptr ast = expandCache[assign];
 371 //      if (ast) return make_pair(DeepCopyAnAST(ast), true); else return make_pair(ast, false);
 372         if (ast) return make_pair(ast, true); else return make_pair(ast, false);
 373
 374     } else {
 375         pair<AST::Ptr, bool> expandRet = SymEval::expand(assign, false);
 376         if (expandRet.second && expandRet.first) {
 377 parsing_printf("Original expand: %s\n", expandRet.first->format().c_str());
 378
 379             AST::Ptr calculation = SimplifyAnAST(expandRet.first, assign->insn()->size());
 380             //expandCache[assign] = DeepCopyAnAST(expandRet.first);
 381             expandCache[assign] = calculation;
 382         } else {
 383             expandCache[assign] = AST::Ptr();
 384         }
 385         return make_pair( expandCache[assign], expandRet.second );
 386     }
 387 }
 388