Start to split jump table analysis to two different slices.
[dyninst.git] / parseAPI / src / JumpTableFormatPred.C
1 #include "JumpTableFormatPred.h"
2 #include "SymbolicExpression.h"
3 #include "IndirectASTVisitor.h"
4 #include "SymEval.h"
5 #include "debug_parse.h"
6 using namespace Dyninst;
7 using namespace Dyninst::DataflowAPI;
8 using namespace Dyninst::ParseAPI;
9 using namespace Dyninst::InstructionAPI;
10
11 bool JumpTableFormatPred::modifyCurrentFrame(Slicer::SliceFrame &frame, Graph::Ptr g) {
12     if (!jumpTableFormat) return false;
13     if (unknownInstruction) return false;
14
15     /* We start to inspect the current slice graph.
16      * 1. If we have determined the jump table format, we can stop this slice.
17      * 2. If we have determined the index variable, we can remove the variable 
18      *    from the current slice and only keep slicing on other variables.
19      * 3. If we have determined that this is not a known jump table, 
20      *    we also stop slicing.
21      */
22
23     queue<SliceNode::Ptr> working_list;
24     unordered_set<Assignment::Ptr, Assignment::AssignmentPtrHasher> inQueue;
25     NodeIterator nbegin, nend; 
26
27     g->adjustEntryAndExitNodes();
28     g->entryNodes(nbegin, nend);
29
30     // This map trakcs the expanded and substituted ASTs for each assignment in the current slice
31     std::unordered_map<Assignment::Ptr, AST::Ptr, Assignment::AssignmentPtrHasher> exprs;
32
33     for (; nbegin != nend; ++nbegin) {
34         SliceNode::Ptr n = boost::static_pointer_cast<SliceNode>(*nbegin);
35         working_list.push(n);
36         inQueue.insert(n->assign());
37     }
38     AST::Ptr jumpTarget;
39     while (!working_list.empty()) {
40         SliceNode::Ptr n = working_list.front();
41         working_list.pop();
42         if (!n->assign()) {
43             parsing_printf("\tWARNING: Encountering a slice node with no assignment!\n");
44             continue;
45         }
46         if (exprs.find(n->assign()) != exprs.end()) {
47             parsing_printf("\tWARNING: Jump table format slice contains cycle!\n");
48             jumpTableFormat = false;
49             return false;
50         }
51
52         /* We expand this assignment.
53          * The jump table format should only involve basic instructions
54          * such as mov, arithmetic, loading addresses.
55          * If we encounter an instruction that we do not have semantics,
56          * we should inspect this case.
57          */
58         pair<AST::Ptr, bool> expandRet = se.ExpandAssignment(n->assign());
59         if (!expandRet.second || expandRet.first == NULL) {
60             parsing_printf("\tWARNING: Jump table format slice contains unknown instructions: %s\n", n->assign()->insn()->format().c_str());
61             unknownInstruction = true;
62             jumpTableFormat = false;
63             return false;
64         }
65         if (n->assign()->out().generator() != NULL) {
66             parsing_printf("\tWARNING: Jump table format slice contains writes to memory\n");
67             jumpTableFormat = false;
68             return false;
69         }
70
71         // We make a deep copy of the AST because the AST from ExpandAssignment 
72         // may be used later. So, we do not want to destroy the AST of the assignment
73         AST::Ptr exp = SymbolicExpression::DeepCopyAnAST(expandRet.first);
74         // We start plug in ASTs from predecessors
75         n->ins(nbegin, nend);
76         map<AST::Ptr, AST::Ptr> inputs;
77         for (; nbegin != nend; ++nbegin) {
78             SliceNode::Ptr p = boost::static_pointer_cast<SliceNode>(*nbegin);
79             if (exprs.find(p->assign()) == exprs.end()) {
80                 parsing_printf("\tWARNING: predecessor does not have an expression\n");
81                 jumpTableFormat = false;
82                 return false;
83             }
84             AST::Ptr rhs = exprs[p->assign()];      
85             AST::Ptr lhs = VariableAST::create(Variable(p->assign()->out())); 
86             
87             // TODO: there may be more than one expression for a single variable
88             inputs[lhs] = rhs;
89         }
90         // TODO: need to consider thunk
91         exp = SymbolicExpression::SubstituteAnAST(exp, inputs);
92         exprs[n->assign()] = exp;
93         // Enumerate every successor and add them to the working list
94         n->outs(nbegin, nend);
95         for (; nbegin != nend; ++nbegin) {
96             SliceNode::Ptr p = boost::static_pointer_cast<SliceNode>(*nbegin);
97             if (inQueue.find(p->assign()) == inQueue.end()) {
98                 inQueue.insert(p->assign());
99                 working_list.push(p);
100             }
101         }
102
103         // The last expression should be the jump target
104         jumpTarget = exp;
105     }
106     JumpTableFormatVisitor jtfv(block);
107     jumpTarget->accept(&jtfv);
108     if (jtfv.findIncorrectFormat) {
109         jumpTableFormat = false;
110         return false;
111     }
112     
113     // We do not try to slice on the heap absregion,
114     // as it will not help us determine the jump table format.
115     for (auto rit = frame.active.begin(); rit != frame.active.end(); ++rit)
116         if (rit->first.type() == Absloc::Heap) {
117             frame.active.erase(rit);
118             break;
119         }
120
121     if (!findIndex && jtfv.findIndex) {
122         if (frame.active.find(jtfv.index) == frame.active.end()) {
123             parsing_printf("\tWARNING: found index variable %s, but it is not in the active map of the slice frame!\n", index.format().c_str());
124             jumpTableFormat = false;
125             return false;
126         }
127
128         // We have found the index variable.
129         // Now we leave it alone and let the jump table index slice to find its bound
130         frame.active.erase(jtfv.index);
131         index = jtfv.index;
132         findIndex = true;
133     }
134     if (jtfv.findIndex && jtfv.findTableBase) { 
135         jumpTargetExpr = jumpTarget;
136         return false;
137     }
138
139     // We have not found all elements of the jump table,
140     // and we have not rejected this indirect jump as a jump table.
141     // Let's continue slicing.
142     return true;
143 }
144
145 string JumpTableFormatPred::format() {
146     if (jumpTargetExpr) return jumpTargetExpr->format();
147     return string("");
148 }