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