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     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];
  39         Address addr = 0;
  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                 }
  48         if (addr != 0) {
  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));
  56                     }
  57             return;
  58         }
  59     }
  60
  61     if (visit.find(curBlock) != visit.end()) return;
  62     visit.insert(curBlock);
  63     for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit)
  64         // Xiaozhu:
  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();
  75                 else
  76                     newT = FALLTHROUGH;
  77             }
  78             BuildEdgesAux(srcNode, (*eit)->trg(), targetMap, newG, visit, newT);
  79         }
  80 }
  81
  82
  83 static void BuildEdges(SliceNode::Ptr curNode,
  84                        map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
  85                        GraphPtr newG) {
  86     set<ParseAPI::Block*> visit;
  87     BuildEdgesAux(curNode, curNode->block(), targetMap, newG, visit, _edgetype_end_);
  88 }
  89
  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);
  93 }
  94
  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;
 100     return false;;
 101
 102 }
 103
 104 static int AdjustGraphEntryAndExit(GraphPtr gp) {
 105     int nodeCount = 0;
 106     NodeIterator gbegin, gend;
 107     gp->allNodes(gbegin, gend);
 108     for (; gbegin != gend; ++gbegin) {
 109         ++nodeCount;
 110         Node::Ptr ptr = *gbegin;
 111         if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
 112         if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
 113     }
 114     return nodeCount;
 115 }
 116
 117
 118 GraphPtr JumpTablePred::BuildAnalysisGraph() {
 119     GraphPtr newG = Graph::createGraph();
 120
 121     NodeIterator gbegin, gend;
 122
 123     // Create a map to help find whether we have reached a node
 124     map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
 125
 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());
 131     }
 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);
 140         }
 141     }
 142
 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);
 148     }
 149
 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));
 158         }
 159     }
 160
 161     AdjustGraphEntryAndExit(newG);
 162
 163
 164     return newG;
 165
 166 }
 167
 168
 169 bool JumpTablePred::endAtPoint(AssignmentPtr ap) {
 170         if (ap->insn()->writesMemory()) return true;
 171         return false;
 172 }
 173 bool JumpTablePred::addNodeCallback(AssignmentPtr ap) {
 174     if (currentAssigns.find(ap) != currentAssigns.end()) return true;
 175
 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) {
 179         return true;
 180     }
 181
 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;
 186
 187
 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);
 190
 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;
 197     }
 198
 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);
 207         }
 208     }
 209
 210     // We create the CFG based on the found nodes
 211     GraphPtr g = BuildAnalysisGraph();
 212
 213     BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, block->last(), expandCache);
 214     bfc.CalculateBoundedFacts();
 215
 216     BoundValue target;
 217     bool ijt = IsJumpTable(g, bfc, target);
 218     if (ijt) {
 219         bool ret = !FillInOutEdges(target, outEdges);
 220 //      fprintf(stderr, "Return %s\n", ret ? "true" : "false");
 221 //      if (dyn_debug_parsing) exit(0);
 222         return ret;
 223     } else {
 224 //        fprintf(stderr, "Return true\n");
 225 //      if (dyn_debug_parsing) exit(0);
 226
 227         return true;
 228     }
 229
 230
 231
 232 }
 233 bool JumpTablePred::FillInOutEdges(BoundValue &target,
 234                                                  vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
 235     outEdges.clear();
 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;
 242     }
 243
 244 #if defined(os_windows)
 245     tableBase -= block->obj()->cs()->loadAddress();
 246     tableLastEntry -= block->obj()->cs()->loadAddress();
 247 #endif
 248
 249     parsing_printf("The final target bound fact:\n");
 250     target.Print();
 251     if (!block->obj()->cs()->isValidAddress(tableBase)) {
 252         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
 253         return false;
 254     }
 255
 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) {
 262                 case 8:
 263                     targetAddress = *(const uint64_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 264                     break;
 265                 case 4:
 266                     targetAddress = *(const uint32_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 267                     if ((arch == Arch_x86_64) && (targetAddress & 0x80000000)) {
 268                         targetAddress |= SIGNEX_64_32;
 269                     }
 270                     break;
 271                 case 2:
 272                     targetAddress = *(const uint16_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 273                     if ((arch == Arch_x86_64) && (targetAddress & 0x8000)) {
 274                         targetAddress |= SIGNEX_64_16;
 275                     }
 276                     if ((arch == Arch_x86) && (targetAddress & 0x8000)) {
 277                         targetAddress |= SIGNEX_32_16;
 278                     }
 279
 280                     break;
 281                 case 1:
 282                     targetAddress = *(const uint8_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
 283                     if ((arch == Arch_x86_64) && (targetAddress & 0x80)) {
 284                         targetAddress |= SIGNEX_64_8;
 285                     }
 286                     if ((arch == Arch_x86) && (targetAddress & 0x80)) {
 287                         targetAddress |= SIGNEX_32_8;
 288                     }
 289
 290                     break;
 291
 292                 default:
 293                     parsing_printf("Invalid memory read size %d\n", target.tableReadSize);
 294                     return false;
 295             }
 296             if (targetAddress != 0) {
 297                 if (target.isSubReadContent)
 298                     targetAddress = target.targetBase - targetAddress;
 299                 else
 300                     targetAddress += target.targetBase;
 301
 302             }
 303 #if defined(os_windows)
 304             targetAddress -= block->obj()->cs()->loadAddress();
 305 #endif
 306         } else targetAddress = tableEntry;
 307
 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" );
 313         } else {
 314             parsing_printf(" not code.\n");
 315         }
 316         // If the jump target is resolved to be a constant,
 317         if (target.interval.stride == 0) break;
 318     }
 319     return true;
 320 }
 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);
 329
 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;
 338     }
 339     return false;
 340 }
 341
 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());
 347
 348     if (write == NULL) return false;
 349     for (auto ait = readAST.begin(); ait != readAST.end(); ++ait)
 350         if (*write == **ait) return true;
 351     return false;
 352 }
 353
 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);
 359
 360     } else {
 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;
 366         } else {
 367             expandCache[assign] = AST::Ptr();
 368         }
 369         return make_pair( expandCache[assign], expandRet.second );
 370     }
 371 }
 372