1 #include "IndirectControlFlow.h"
2 #include "IndirectASTVisitor.h"
3 #include "debug_parse.h"
5 bool BoundFactsCalculator::CalculateBoundedFacts() {
6 /* We use a dataflow analysis to calculate what registers are bounded
7 * at each node. The key points of the dataflow analysis are how
8 * to calculate the meet and how to calculate the transfer function.
9 * 1. The meet should be simply an intersection of all the bounded facts
11 * 2. To calculate the transfer function, we first get the symbolic expression
12 * of the instrution for the node. Then depending on the instruction operation
13 * and the meet result, we know what are still bounded. For example, loading
14 * memory is always unbounded; doing and operation on a register with a constant
15 * makes the register bounded.
20 queue<Node::Ptr> workingList;
22 NodeIterator nbegin, nend;
23 slice->allNodes(nbegin, nend);
25 for (; nbegin != nend; ++nbegin) {
26 workingList.push(*nbegin);
30 while (!workingList.empty()) {
31 Node::Ptr curNode = workingList.front();
34 BoundFact oldFact = boundFacts[curNode.get()];
36 CalcTransferFunction(curNode);
38 if (defined.find(curNode) == defined.end() || oldFact != boundFacts[curNode.get()]) {
39 curNode->outs(nbegin, nend);
40 for (; nbegin != nend; ++nbegin)
41 workingList.push(*nbegin);
43 defined.insert(curNode);
50 void BoundFactsCalculator::ConditionalJumpBound(BoundFact& curFact, Node::Ptr src, Node::Ptr trg) {
52 /* This function checks whether any potential table guard is between the two nodes
53 * that we are calculating the meet. Essentially, if there is a conditional jump
54 * between the two nodes, we know extra bound information.
57 ParseAPI::Block *srcBlock;
58 if (src == Node::Ptr())
59 srcBlock = func->entry();
61 SliceNode::Ptr srcNode = boost::static_pointer_cast<SliceNode>(src);
62 srcBlock = srcNode->block();
65 SliceNode::Ptr trgNode = boost::static_pointer_cast<SliceNode>(trg);
66 ParseAPI::Block *trgBlock = trgNode->block();
68 for (auto git = guards.begin(); git != guards.end(); ++git) {
69 if (!git->constantBound) continue;
71 ParseAPI::Block *guardBlock = git->block;
72 // Note that the guardBlock and the srcBlock can be the same,
73 // but since the conditional jump will always be the last instruction
74 // in the block, if they are in the same block, the src can reach the guard
75 if (rf.incoming[guardBlock].find(srcBlock) == rf.incoming[guardBlock].end()) continue;
76 bool pred_taken = rf.branch_taken[guardBlock].find(trgBlock) != rf.branch_taken[guardBlock].end();
77 bool pred_ft = rf.branch_ft[guardBlock].find(trgBlock) != rf.branch_ft[guardBlock].end();
78 parsing_printf("pred_taken : %d, pred_ft: %d\n", pred_taken, pred_ft);
79 // If both branches reach the trg node, then this conditional jump
80 // does not bound any variable for the trg node.
81 if (pred_taken ^ pred_ft) {
82 // Here I need to figure out which branch bounds the variable and
83 // check it is the bounded path that reaches the trg node.
85 bool boundedOnTakenBranch = git->varSubtrahend ^ git->jumpWhenNoZF;
86 if ( (boundedOnTakenBranch && pred_taken)
87 // In thic case, we jump when the variable is smaller than the constant.
88 // So the condition taken path is the path that bounds the value.
89 || (!boundedOnTakenBranch && pred_ft) ) {
90 // In thic case, we jump when the variable is larger than the constant.
91 // So the fallthrough path is the path that bounds the value.
93 if (curFact.cmpBoundFactLive == false || git->cmpBound > curFact.cmpBound) {
94 curFact.cmpAST = git->cmpAST;
95 curFact.cmpBound = git->cmpBound;
96 curFact.cmpBoundFactLive = true;
97 curFact.cmpUsedRegs = git->usedRegs;
102 if (!curFact.cmpBoundFactLive && firstBlock) {
103 // If this is indirect jump is in the first block,
104 // it is possible that it is a jump table for a function
105 // with variable number of arguments. Then the convention
106 // is that al contains the number of argument.
107 curFact.cmpAST = VariableAST::create(Variable(Absloc(x86_64::rax)));
108 curFact.cmpBound = 8;
109 curFact.cmpUsedRegs.insert(x86_64::rax);
110 curFact.cmpBoundFactLive = true;
116 void BoundFactsCalculator::Meet(Node::Ptr curNode) {
118 SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
119 parsing_printf("Calculate Meet for %lx\n", node->addr());
121 NodeIterator gbegin, gend;
122 curNode->ins(gbegin, gend);
123 BoundFact &curFact = boundFacts[curNode.get()];
125 if (gbegin != gend) {
127 for (; gbegin != gend; ++gbegin) {
128 SliceNode::Ptr meetSliceNode = boost::static_pointer_cast<SliceNode>(*gbegin);
129 if (defined.find(*gbegin) == defined.end()) {
130 parsing_printf("\tIncoming node %lx has not been calculated yet\n", meetSliceNode->addr());
133 parsing_printf("\tMeet incoming edge from %lx\n", meetSliceNode->addr());
134 BoundFact prevFact = boundFacts[(*gbegin).get()];
135 ConditionalJumpBound(prevFact, *gbegin, curNode);
140 curFact.Intersect(prevFact);
143 ConditionalJumpBound(curFact, Node::Ptr(), curNode);
144 parsing_printf("Meet no incoming nodes\n");
149 void BoundFactsCalculator::CalcTransferFunction(Node::Ptr curNode){
151 SliceNode::Ptr node = boost::static_pointer_cast<SliceNode>(curNode);
152 AbsRegion &ar = node->assign()->out();
154 BoundFact &curFact = boundFacts[curNode.get()];
155 parsing_printf("Expanding assignment %s in instruction at %lx: %s.\n", node->assign()->format().c_str(), node->addr(), node->assign()->insn()->format().c_str());
156 pair<AST::Ptr, bool> expandRet = SymEval::expand(node->assign(), false);
158 if (expandRet.first == NULL) {
159 // If the instruction is outside the set of instrutions we
160 // add instruction semantics. We assume this instruction
161 // kills all bound fact.
162 parsing_printf("\t No semantic support for this instruction. Kill all bound fact\n");
165 parsing_printf("\t AST after expanding (without simplify) %s\n", expandRet.first->format().c_str());
167 AST::Ptr calculation = SimplifyAnAST(expandRet.first, node->assign()->insn()->size());
169 parsing_printf("\t AST after expanding %s\n", calculation->format().c_str());
170 parsing_printf("Calculating transfer function: Input facts\n");
173 BoundCalcVisitor bcv(curFact);
174 calculation->accept(&bcv);
176 if (bcv.IsResultBounded(calculation)) {
177 parsing_printf("Genenerate bound fact for %s\n", ar.absloc().format().c_str());
178 curFact.GenFact(ar.absloc(), bcv.GetResultBound(calculation));
181 parsing_printf("Kill bound fact for %s\n", ar.absloc().format().c_str());
182 curFact.KillFact(ar.absloc());
184 parsing_printf("Calculating transfer function: Output facts\n");