5 #include "debug_parse.h"
6 #include "CodeObject.h"
7 #include "JumpTablePred.h"
9 #include "Instruction.h"
10 #include "InstructionDecoder.h"
12 #include "AbslocInterface.h"
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
25 // Assume the table contain less than this many entries.
26 #define MAX_TABLE_ENTRY 1000000
28 static void BuildEdgesAux(SliceNode::Ptr srcNode,
29 ParseAPI::Block* curBlock,
30 map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
32 set<ParseAPI::Block*> &visit,
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];
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();
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));
60 if (visit.find(curBlock) != visit.end()) return;
61 visit.insert(curBlock);
62 for (auto eit = curBlock->targets().begin(); eit != curBlock->targets().end(); ++eit)
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();
77 BuildEdgesAux(srcNode, (*eit)->trg(), targetMap, newG, visit, newT);
82 static void BuildEdges(SliceNode::Ptr curNode,
83 map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > &targetMap,
85 set<ParseAPI::Block*> visit;
86 BuildEdgesAux(curNode, curNode->block(), targetMap, newG, visit, _edgetype_end_);
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);
93 static int AdjustGraphEntryAndExit(GraphPtr gp) {
95 NodeIterator gbegin, gend;
96 gp->allNodes(gbegin, gend);
97 for (; gbegin != gend; ++gbegin) {
99 Node::Ptr ptr = *gbegin;
100 if (!ptr->hasInEdges()) gp->insertEntryNode(ptr);
101 if (!ptr->hasOutEdges()) gp->insertExitNode(ptr);
107 GraphPtr JumpTablePred::BuildAnalysisGraph() {
108 GraphPtr newG = Graph::createGraph();
110 NodeIterator gbegin, gend;
112 // Create a map to help find whether we have reached a node
113 map<ParseAPI::Block*, map<AssignmentPtr, SliceNode::Ptr> > targetMap;
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());
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);
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);
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));
148 AdjustGraphEntryAndExit(newG);
156 bool JumpTablePred::endAtPoint(AssignmentPtr ap) {
157 if (ap->insn()->writesMemory()) return true;
160 bool JumpTablePred::addNodeCallback(AssignmentPtr ap) {
161 if (currentAssigns.find(ap) != currentAssigns.end()) return true;
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) {
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();
173 BoundFactsCalculator bfc(func, g, func->entry() == block, rf, thunks, block->last());
174 bfc.CalculateBoundedFacts();
177 bool ijt = IsJumpTable(g, bfc, target);
178 // if (dyn_debug_parsing) exit(0);
180 bool ret = !FillInOutEdges(target, outEdges);
181 fprintf(stderr, "Return %s\n", ret ? "true" : "false");
184 fprintf(stderr, "Return true\n");
191 bool JumpTablePred::FillInOutEdges(BoundValue &target,
192 vector<pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) {
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;
202 #if defined(os_windows)
203 tableBase -= block->obj()->cs()->loadAddress();
204 tableLastEntry -= block->obj()->cs()->loadAddress();
207 parsing_printf("The final target bound fact:\n");
209 if (!block->obj()->cs()->isValidAddress(tableBase)) {
210 parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
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) {
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) {
223 targetAddress = *(const uint64_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
226 targetAddress = *(const uint32_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
227 if ((arch == Arch_x86_64) && (targetAddress & 0x80000000)) {
228 targetAddress |= SIGNEX_64_32;
232 targetAddress = *(const uint16_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
233 if ((arch == Arch_x86_64) && (targetAddress & 0x8000)) {
234 targetAddress |= SIGNEX_64_16;
236 if ((arch == Arch_x86) && (targetAddress & 0x8000)) {
237 targetAddress |= SIGNEX_32_16;
242 targetAddress = *(const uint8_t *) block->obj()->cs()->getPtrToInstruction(tableEntry);
243 if ((arch == Arch_x86_64) && (targetAddress & 0x80)) {
244 targetAddress |= SIGNEX_64_8;
246 if ((arch == Arch_x86) && (targetAddress & 0x80)) {
247 targetAddress |= SIGNEX_32_8;
253 parsing_printf("Invalid table stride %d\n", target.interval.stride);
256 if (targetAddress != 0) {
257 if (target.isSubReadContent)
258 targetAddress = target.targetBase - targetAddress;
260 targetAddress += target.targetBase;
263 #if defined(os_windows)
264 targetAddress -= block->obj()->cs()->loadAddress();
266 } else targetAddress = tableEntry;
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" );
274 parsing_printf(" not code.\n");
276 // If the jump target is resolved to be a constant,
277 if (target.interval.stride == 0) break;
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);
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;