Enable symbolic evaluation on x86 64-bit binaries
[dyninst.git] / dataflowAPI / src / SymEval.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #include <string>
32 #include <iostream>
33
34 #include "../h/SymEval.h"
35 #include "SymEvalPolicy.h"
36
37 #include "DynAST.h"
38
39 #include "parseAPI/h/CFG.h"
40
41 #include "../rose/x86InstructionSemantics.h"
42 #include "../rose/x86_64InstructionSemantics.h"
43
44 #include "../rose/powerpcInstructionSemantics.h"
45 #include "../rose/SgAsmInstruction.h"
46 #include "../h/stackanalysis.h"
47 #include "SymEvalVisitors.h"
48
49 #include "RoseInsnFactory.h"
50 #include "SymbolicExpansion.h"
51
52 #include "../h/Absloc.h"
53
54 #include "../h/slicing.h" // SliceNode
55
56 #include "debug_dataflow.h"
57
58 #include "boost/tuple/tuple.hpp"
59
60 using namespace Dyninst;
61 using namespace InstructionAPI;
62 using namespace DataflowAPI;
63
64
65 std::pair<AST::Ptr, bool> SymEval::expand(const Assignment::Ptr &assignment, bool applyVisitors) {
66   // This is a shortcut version for when we only want a
67   // single assignment
68   
69   Result_t res;
70   // Fill it in to mark it as existing
71   res[assignment] = AST::Ptr();
72   std::set<Instruction::Ptr> ignored;
73   bool succ = expand(res, ignored, applyVisitors);
74   return std::make_pair(res[assignment], succ);
75 }
76
77 bool SymEval::expand(Result_t &res, 
78                      std::set<InstructionPtr> &failedInsns,
79                      bool applyVisitors) {
80   // Symbolic evaluation works off an Instruction
81   // so we have something to hand to ROSE. 
82    failedInsns.clear();
83    for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
84       if (i->second != AST::Ptr()) {
85          // Must've already filled it in from a previous instruction crack
86          continue;
87       }
88     Assignment::Ptr ptr = i->first;
89     
90     bool success = expandInsn(ptr->insn(),
91                               ptr->addr(),
92                               res);
93     if (!success) failedInsns.insert(ptr->insn());
94    }
95
96    if (applyVisitors) {
97       // Must apply the visitor to each filled in element
98       for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
99          if (!i->second) continue;
100          AST::Ptr tmp = simplifyStack(i->second, i->first->addr(), i->first->func(), i->first->block());
101          BooleanVisitor b;
102          AST::Ptr tmp2 = tmp->accept(&b);
103          i->second = tmp2;
104       }
105    }
106    return (failedInsns.empty());
107 }
108
109 bool edgeSort(Edge::Ptr ptr1, Edge::Ptr ptr2) {
110     Address addr1 = ptr1->target()->addr();
111     Address addr2 = ptr2->target()->addr();
112
113     return (addr1 < addr2);
114 }
115
116 void dfs(Node::Ptr source,
117          std::map<Node::Ptr, int> &state,
118          std::set<Edge::Ptr> &skipEdges) {
119
120    // DFS from the node given by source
121    // If we meet a node twice without having to backtrack first,
122    // insert that incoming edge into skipEdges.
123    //
124    // A node n has state[n] > 0 if it is on the path currently
125    // being explored.
126
127    EdgeIterator b, e;
128    source->outs(b, e);
129
130     vector<Edge::Ptr> edges;
131     for ( ; b!=e; ++b) {
132         Edge::Ptr edge = *b;
133         edges.push_back(edge);
134     }
135     std::stable_sort(edges.begin(), edges.end(), edgeSort);
136
137    //state[source]++;
138    std::map<Node::Ptr, int>::iterator ssit = state.find(source);
139    if(ssit == state.end())
140     boost::tuples::tie(ssit,boost::tuples::ignore) = 
141         state.insert(make_pair(source,1));
142    else
143     (*ssit).second++;
144
145    vector<Edge::Ptr>::iterator eit = edges.begin();
146    for ( ; eit != edges.end(); ++eit) {
147       Edge::Ptr edge = *eit;
148       Node::Ptr cur = edge->target();
149
150       std::map<Node::Ptr, int>::iterator sit = state.find(cur);
151       bool done = (sit != state.end());
152
153       if(done && (*sit).second > 0)
154         skipEdges.insert(edge);
155
156       if(!done)
157         dfs(cur, state, skipEdges);
158    }
159
160    //state[source]--;
161    (*ssit).second--;
162 }
163
164 /*
165  * Optimal ordering for visiting the slicing
166  * nodes during expansion; this is possible to do
167  * because we have removed loops
168  */
169 class ExpandOrder {
170  public:
171     ExpandOrder() { }
172     ~ExpandOrder() { }
173
174     // remove an element from the next-lowest queue
175     // and return it and its order
176     pair<SliceNode::Ptr,int> pop_next()
177     {
178         SliceNode::Ptr rn = SliceNode::Ptr();
179         int ro = -1;
180
181         map<int,order_queue>::iterator qit = queues.begin();
182         for( ; qit != queues.end(); ++qit) {
183             order_queue & q = (*qit).second;
184             if(!q.nodes.empty()) {
185                 rn = *q.nodes.begin();
186                 ro = q.order; 
187                 remove(rn);
188                 break;
189             }
190         }
191         return make_pair(rn,ro);
192     }
193
194     // removes a node from the structure
195     // returns true if the node was there
196     bool remove(SliceNode::Ptr n) {
197         map<SliceNode::Ptr, int>::iterator it = order_map.find(n);
198         if(it != order_map.end()) {
199             queues[ (*it).second ].nodes.erase(n);
200             order_map.erase(it);
201             return true;
202         } 
203         return false;
204     }
205
206     // places a node in the structure -- its
207     // order is computed
208     void insert(SliceNode::Ptr n, bool force_done = false) {
209         // compute the order of this node --- the number of its parents
210         // not on the skipedges list and not done
211         EdgeIterator begin, end;
212         n->ins(begin,end);
213         int pcnt = 0;
214         for( ; begin != end; ++begin) {
215             Edge::Ptr edge = *begin;
216             if(skip_edges.find(edge) == skip_edges.end()) {
217                 SliceNode::Ptr parent =
218                     boost::static_pointer_cast<SliceNode>(
219                         edge->source());
220                 if(done.find(parent) == done.end())
221                     ++pcnt;
222             }
223         }
224
225         queues[pcnt].nodes.insert(n);
226         queues[pcnt].order = pcnt;
227         order_map[n] = pcnt;
228
229         if(force_done)
230             done.insert(n);
231     }
232
233     // Mark a node complete, updating its children.
234     // Removes the node from the data structure
235     void mark_done(SliceNode::Ptr n) {
236         // First pull all of the children of this node
237         // that are not on the skip list
238
239         set<SliceNode::Ptr> children;
240
241         EdgeIterator begin, end;
242         n->outs(begin, end);
243         for (; begin != end; ++begin) {
244             Edge::Ptr edge = *begin;
245             if(skip_edges.find(edge) == skip_edges.end()) {
246                 SliceNode::Ptr child = 
247                     boost::static_pointer_cast<SliceNode>(
248                         edge->target());
249                 if(remove(child))
250                     children.insert(child);
251             }
252         }
253
254         // remove n and set done
255         remove(n);
256         done.insert(n);
257
258         // put the children back
259         set<SliceNode::Ptr>::iterator cit = children.begin();
260         for( ; cit != children.end(); ++cit) {
261             insert(*cit); 
262         }
263     }
264     
265     bool is_done(SliceNode::Ptr n) const {
266         return done.find(n) == done.end();
267     }
268
269     set<Edge::Ptr> & skipEdges() { return skip_edges; }
270
271  private:
272     struct order_queue {
273         int order;
274         set<SliceNode::Ptr> nodes; 
275     };
276
277     set<Edge::Ptr> skip_edges; 
278     map<int,order_queue> queues;
279     map<SliceNode::Ptr, int> order_map;
280     set<SliceNode::Ptr> done;
281 };
282
283 // implements < , <= causes failures when used to sort Windows vectors
284 bool vectorSort(SliceNode::Ptr ptr1, SliceNode::Ptr ptr2) {
285
286     AssignmentPtr assign1 = ptr1->assign();
287     AssignmentPtr assign2 = ptr2->assign();
288
289     if (!assign2) return false;
290     else if (!assign1) return true;
291
292     Address addr1 = assign1->addr();
293     Address addr2 = assign2->addr();
294
295     if (addr1 == addr2) {
296         AbsRegion &out1 = assign1->out();
297         AbsRegion &out2 = assign2->out();
298         return out1 < out2;
299     } else {
300         return addr1 < addr2;
301     }
302 }
303
304 // Do the previous, but use a Graph as a guide for
305 // performing forward substitution on the AST results
306 SymEval::Retval_t SymEval::expand(Dyninst::Graph::Ptr slice, DataflowAPI::Result_t &res) {
307     bool failedTranslation = false;
308     bool skippedInput = false;
309
310     //cout << "Calling expand" << endl;
311     // Other than the substitution this is pretty similar to the first example.
312     NodeIterator gbegin, gend;
313     slice->allNodes(gbegin, gend);
314
315     // First, we'll sort the nodes in some deterministic order so that the loop removal
316     // is deterministic
317     std::vector<SliceNode::Ptr> sortVector;
318     for ( ; gbegin != gend; ++gbegin) {
319         Node::Ptr ptr = *gbegin;
320                 expand_cerr << "pushing " << (*gbegin)->format() << " to sortVector" << endl;
321         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(ptr);
322         sortVector.push_back(cur);
323     }
324     std::stable_sort(sortVector.begin(), sortVector.end(), vectorSort);
325
326     // Optimal ordering of search
327     ExpandOrder worklist;
328
329     std::queue<Node::Ptr> dfs_worklist;
330     std::vector<SliceNode::Ptr>::iterator vit = sortVector.begin();
331     for ( ; vit != sortVector.end(); ++vit) {
332         SliceNode::Ptr ptr = *vit;
333         Node::Ptr cur = boost::static_pointer_cast<Node>(ptr);
334         dfs_worklist.push(cur);
335     }
336
337     /* First, we'll do DFS to check for circularities in the graph;
338      * if so, mark them so we don't do infinite substitution */
339     std::map<Node::Ptr, int> state;
340     while (!dfs_worklist.empty()) {
341         Node::Ptr ptr = dfs_worklist.front(); dfs_worklist.pop();
342         dfs(ptr, state, worklist.skipEdges());
343     }
344
345     slice->allNodes(gbegin, gend);
346     for (; gbegin != gend; ++gbegin) {
347         expand_cerr << "adding " << (*gbegin)->format() << " to worklist" << endl;
348         Node::Ptr ptr = *gbegin;
349         SliceNode::Ptr sptr = 
350             boost::static_pointer_cast<SliceNode>(ptr);
351         worklist.insert(sptr,false);
352     }
353
354     /* have a list
355      * for each node, process
356      * if processessing succeeded, remove the element
357      * if the size of the list has changed, continue */
358
359     while (1) {
360       SliceNode::Ptr aNode;
361       int order;
362
363       boost::tie(aNode,order) = worklist.pop_next();
364       if (order == -1) // empty
365           break;
366
367       if (!aNode->assign()) {
368           worklist.mark_done(aNode);
369           continue; // Could be a widen point
370       }
371
372       expand_cerr << "Visiting node " << aNode->assign()->format() 
373                   << " order " << order << endl;
374
375       if (order != 0) {
376               cerr << "ERROR: order is non zero: " << order << endl;
377       }
378       assert(order == 0); // there are no loops
379
380       AST::Ptr prev = res[aNode->assign()];
381       Retval_t result = process(aNode, res, worklist.skipEdges()); 
382       AST::Ptr post = res[aNode->assign()];
383       switch (result) {
384          case FAILED:
385             return FAILED;
386             break;
387          case WIDEN_NODE:
388             // Okay...
389             break;
390          case FAILED_TRANSLATION:
391             failedTranslation = true;
392             break;
393          case SKIPPED_INPUT:
394             skippedInput = true;
395             break;
396          case SUCCESS:
397             break;
398       }
399
400       // We've visited this node, freeing its children
401       // to be visited in turn
402       worklist.mark_done(aNode);
403
404       if (post && !(post->equals(prev))) {
405         expand_cerr << "Adding successors to list, as new expansion " << endl
406             << "\t" << post->format() << endl 
407             << " != " << endl
408             << "\t" << (prev ? prev->format() : "<NULL>") << endl;
409         EdgeIterator oB, oE;
410         aNode->outs(oB, oE);
411         for (; oB != oE; ++oB) {
412             if(worklist.skipEdges().find(*oB) == worklist.skipEdges().end()) {
413                 SliceNode::Ptr out =
414                     boost::static_pointer_cast<SliceNode>(
415                         (*oB)->target());
416                 worklist.insert(out);
417             }
418         }
419       }
420     }
421     if (failedTranslation) return FAILED_TRANSLATION;
422     else if (skippedInput) return SKIPPED_INPUT;
423     else return SUCCESS;
424 }
425
426 bool SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
427                          const uint64_t addr,
428                          Result_t &res)
429 {
430
431   
432   SgAsmInstruction *roseInsn;
433   switch(insn->getArch()) {
434   case Arch_x86:  {
435     SymEvalPolicy policy(res, addr, insn->getArch(), insn);
436     RoseInsnX86Factory fac(Arch_x86);
437     roseInsn = fac.convert(insn, addr);
438     
439     SymbolicExpansion exp;
440     exp.expandX86(roseInsn, policy);
441   if (policy.failedTranslate()) {
442      cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
443      return false;
444   }
445
446     break;
447   }
448   case Arch_x86_64: {
449     SymEvalPolicy_64 policy(res, addr, insn->getArch(), insn);
450     RoseInsnX86Factory fac(Arch_x86_64);
451     roseInsn = fac.convert(insn, addr);
452     
453     SymbolicExpansion exp;
454     exp.expandX86_64(roseInsn, policy);
455   if (policy.failedTranslate()) {
456      cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
457      return false;
458   }
459
460     break;
461
462   }
463   case Arch_ppc32: {
464     SymEvalPolicy policy(res, addr, insn->getArch(), insn);
465     RoseInsnPPCFactory fac;
466     roseInsn = fac.convert(insn, addr);
467
468     SymbolicExpansion exp;
469     exp.expandPPC(roseInsn, policy);
470   if (policy.failedTranslate()) {
471      cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
472      return false;
473   }
474
475     break;
476   }
477   default:
478     assert(0 && "Unimplemented symbolic expansion architecture");
479     break;
480   }
481
482   return true;
483 }
484
485
486 SymEval::Retval_t SymEval::process(SliceNode::Ptr ptr,
487                                    Result_t &dbase,
488                                    std::set<Edge::Ptr> &skipEdges) {
489    bool failedTranslation;
490    bool skippedEdge = false;
491    bool skippedInput = false;
492    bool success = false;
493
494     std::map<const AbsRegion, std::set<Assignment::Ptr> > inputMap;
495
496     expand_cerr << "Calling process on " << ptr->format() << endl;
497
498     // Don't try an expansion of a widen node...
499     if (!ptr->assign()) return WIDEN_NODE;
500
501     EdgeIterator begin, end;
502     ptr->ins(begin, end);
503
504     for (; begin != end; ++begin) {
505          SliceEdge::Ptr edge = boost::static_pointer_cast<SliceEdge>(*begin);
506          SliceNode::Ptr source = boost::static_pointer_cast<SliceNode>(edge->source());
507
508          // Skip this one to break a cycle.
509          if (skipEdges.find(edge) != skipEdges.end()) {
510                      expand_cerr << "In process, skipping edge from "
511                                  << source->format() << endl;
512              skippedEdge = true;
513                  continue;
514          }
515        
516                  Assignment::Ptr assign = source->assign();
517                  if (!assign) continue; // widen node
518        
519                  expand_cerr << "Assigning input " << edge->data().format()
520                      << " from assignment " << assign->format() << endl;
521                  inputMap[edge->data()].insert(assign);
522     }
523     
524     expand_cerr << "\t Input map has size " << inputMap.size() << endl;
525     
526     // All of the expanded inputs are in the parameter dbase
527     // If not (like this one), add it
528     
529     AST::Ptr ast;
530     boost::tie(ast, failedTranslation) = SymEval::expand(ptr->assign());
531     // expand_cerr << "\t ... resulting in " << dbase.format() << endl;
532
533     // We have an AST. Now substitute in all of its predecessors.
534     for (std::map<const AbsRegion, std::set<Assignment::Ptr> >::iterator iter = inputMap.begin();
535          iter != inputMap.end(); ++iter) {
536                  // If we have multiple secondary definitions, we:
537                  //   if all definitions are equal, use the first
538                  //   otherwise, use nothing
539                  AST::Ptr definition;
540
541                  for (std::set<Assignment::Ptr>::iterator iter2 = iter->second.begin(); 
542                           iter2 != iter->second.end(); ++iter2) {
543                           AST::Ptr newDef = dbase[*iter2];
544                           if (!definition) {
545                                   definition = newDef;
546                                   continue;
547                           } else if (definition->equals(newDef)) {
548                                   continue;
549                           } else {
550                                   // Not equal
551                                   definition = AST::Ptr();
552                                   skippedInput = true;
553                                   break;
554                           }
555                   }
556
557                   // The region used by the current assignment...
558                   const AbsRegion &reg = iter->first;
559       
560                   // Create an AST around this one
561                   VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
562       
563                   if (!definition) {
564                           // Can happen if we're expanding out of order, and is generally harmless.
565                           continue;
566                   }
567
568                   expand_cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
569
570                   if (!ast) {
571                           expand_cerr << "Skipping substitution because of null AST" << endl;
572                   } else {
573                           ast = AST::substitute(ast, use, definition);
574                           success = true;
575                   }
576                   expand_cerr << "\t result is " << (ast ? ast->format() : "<NULL AST>") << endl;
577     }
578     expand_cerr << "Result of substitution: " << ptr->assign()->format() << " == " 
579                         << (ast ? ast->format() : "<NULL AST>") << endl;
580     
581     // And attempt simplification again
582     ast = simplifyStack(ast, ptr->addr(), ptr->func(), ptr->block());
583     expand_cerr << "Result of post-substitution simplification: " << ptr->assign()->format() << " == " 
584                 << (ast ? ast->format() : "<NULL AST>") << endl;
585     
586     dbase[ptr->assign()] = ast;
587     if (failedTranslation) return FAILED_TRANSLATION;
588     else if (skippedEdge || skippedInput) return SKIPPED_INPUT;
589     else if (success) return SUCCESS;
590     else return FAILED;
591 }
592
593 AST::Ptr SymEval::simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func, ParseAPI::Block *block) {
594   if (!ast) return ast;
595   // Let's experiment with simplification
596   StackAnalysis sA(func);
597   StackAnalysis::Height sp = sA.findSP(block, addr);
598   StackAnalysis::Height fp = sA.find(block, addr, MachRegister::getFramePointer(func->isrc()->getArch()));
599   
600   StackVisitor sv(addr, func, sp, fp);
601
602   AST::Ptr simplified = ast->accept(&sv);
603
604   return simplified;
605 }