Definitions of the register state, memory state and value type for SymEval semantics...
[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 std;
61 using namespace Dyninst;
62 using namespace InstructionAPI;
63 using namespace DataflowAPI;
64 using namespace rose::BinaryAnalysis::InstructionSemantics2;
65
66
67 std::pair<AST::Ptr, bool> SymEval::expand(const Assignment::Ptr &assignment, bool applyVisitors) {
68   // This is a shortcut version for when we only want a
69   // single assignment
70   
71   Result_t res;
72   // Fill it in to mark it as existing
73   res[assignment] = AST::Ptr();
74   std::set<Instruction::Ptr> ignored;
75   bool succ = expand(res, ignored, applyVisitors);
76   return std::make_pair(res[assignment], succ);
77 }
78
79 bool SymEval::expand(Result_t &res, 
80                      std::set<InstructionPtr> &failedInsns,
81                      bool applyVisitors) {
82   // Symbolic evaluation works off an Instruction
83   // so we have something to hand to ROSE. 
84    failedInsns.clear();
85    for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
86       if (i->second != AST::Ptr()) {
87          // Must've already filled it in from a previous instruction crack
88          continue;
89       }
90     Assignment::Ptr ptr = i->first;
91     
92     bool success = expandInsn(ptr->insn(),
93                               ptr->addr(),
94                               res);
95     if (!success) failedInsns.insert(ptr->insn());
96    }
97
98    if (applyVisitors) {
99       // Must apply the visitor to each filled in element
100       for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
101          if (!i->second) continue;
102          AST::Ptr tmp = simplifyStack(i->second, i->first->addr(), i->first->func(), i->first->block());
103          BooleanVisitor b;
104          AST::Ptr tmp2 = tmp->accept(&b);
105          i->second = tmp2;
106       }
107    }
108    return (failedInsns.empty());
109 }
110
111 bool edgeSort(Edge::Ptr ptr1, Edge::Ptr ptr2) {
112     Address addr1 = ptr1->target()->addr();
113     Address addr2 = ptr2->target()->addr();
114
115     return (addr1 < addr2);
116 }
117
118 void dfs(Node::Ptr source,
119          std::map<Node::Ptr, int> &state,
120          std::set<Edge::Ptr> &skipEdges) {
121
122    // DFS from the node given by source
123    // If we meet a node twice without having to backtrack first,
124    // insert that incoming edge into skipEdges.
125    //
126    // A node n has state[n] > 0 if it is on the path currently
127    // being explored.
128
129    EdgeIterator b, e;
130    source->outs(b, e);
131
132     vector<Edge::Ptr> edges;
133     for ( ; b!=e; ++b) {
134         Edge::Ptr edge = *b;
135         edges.push_back(edge);
136     }
137     std::stable_sort(edges.begin(), edges.end(), edgeSort);
138
139    //state[source]++;
140    std::map<Node::Ptr, int>::iterator ssit = state.find(source);
141    if(ssit == state.end())
142     boost::tuples::tie(ssit,boost::tuples::ignore) = 
143         state.insert(make_pair(source,1));
144    else
145     (*ssit).second++;
146
147    vector<Edge::Ptr>::iterator eit = edges.begin();
148    for ( ; eit != edges.end(); ++eit) {
149       Edge::Ptr edge = *eit;
150       Node::Ptr cur = edge->target();
151
152       std::map<Node::Ptr, int>::iterator sit = state.find(cur);
153       bool done = (sit != state.end());
154
155       if(done && (*sit).second > 0)
156         skipEdges.insert(edge);
157
158       if(!done)
159         dfs(cur, state, skipEdges);
160    }
161
162    //state[source]--;
163    (*ssit).second--;
164 }
165
166 /*
167  * Optimal ordering for visiting the slicing
168  * nodes during expansion; this is possible to do
169  * because we have removed loops
170  */
171 class ExpandOrder {
172  public:
173     ExpandOrder() { }
174     ~ExpandOrder() { }
175
176     // remove an element from the next-lowest queue
177     // and return it and its order
178     pair<SliceNode::Ptr,int> pop_next()
179     {
180         SliceNode::Ptr rn = SliceNode::Ptr();
181         int ro = -1;
182
183         map<int,order_queue>::iterator qit = queues.begin();
184         for( ; qit != queues.end(); ++qit) {
185             order_queue & q = (*qit).second;
186             if(!q.nodes.empty()) {
187                 rn = *q.nodes.begin();
188                 ro = q.order; 
189                 remove(rn);
190                 break;
191             }
192         }
193         return make_pair(rn,ro);
194     }
195
196     // removes a node from the structure
197     // returns true if the node was there
198     bool remove(SliceNode::Ptr n) {
199         map<SliceNode::Ptr, int>::iterator it = order_map.find(n);
200         if(it != order_map.end()) {
201             queues[ (*it).second ].nodes.erase(n);
202             order_map.erase(it);
203             return true;
204         } 
205         return false;
206     }
207
208     // places a node in the structure -- its
209     // order is computed
210     void insert(SliceNode::Ptr n, bool force_done = false) {
211         // compute the order of this node --- the number of its parents
212         // not on the skipedges list and not done
213         EdgeIterator begin, end;
214         n->ins(begin,end);
215         int pcnt = 0;
216         for( ; begin != end; ++begin) {
217             Edge::Ptr edge = *begin;
218             if(skip_edges.find(edge) == skip_edges.end()) {
219                 SliceNode::Ptr parent =
220                     boost::static_pointer_cast<SliceNode>(
221                         edge->source());
222                 if(done.find(parent) == done.end())
223                     ++pcnt;
224             }
225         }
226
227         queues[pcnt].nodes.insert(n);
228         queues[pcnt].order = pcnt;
229         order_map[n] = pcnt;
230
231         if(force_done)
232             done.insert(n);
233     }
234
235     // Mark a node complete, updating its children.
236     // Removes the node from the data structure
237     void mark_done(SliceNode::Ptr n) {
238         // First pull all of the children of this node
239         // that are not on the skip list
240
241         set<SliceNode::Ptr> children;
242
243         EdgeIterator begin, end;
244         n->outs(begin, end);
245         for (; begin != end; ++begin) {
246             Edge::Ptr edge = *begin;
247             if(skip_edges.find(edge) == skip_edges.end()) {
248                 SliceNode::Ptr child = 
249                     boost::static_pointer_cast<SliceNode>(
250                         edge->target());
251                 if(remove(child))
252                     children.insert(child);
253             }
254         }
255
256         // remove n and set done
257         remove(n);
258         done.insert(n);
259
260         // put the children back
261         set<SliceNode::Ptr>::iterator cit = children.begin();
262         for( ; cit != children.end(); ++cit) {
263             insert(*cit); 
264         }
265     }
266     
267     bool is_done(SliceNode::Ptr n) const {
268         return done.find(n) == done.end();
269     }
270
271     set<Edge::Ptr> & skipEdges() { return skip_edges; }
272
273  private:
274     struct order_queue {
275         int order;
276         set<SliceNode::Ptr> nodes; 
277     };
278
279     set<Edge::Ptr> skip_edges; 
280     map<int,order_queue> queues;
281     map<SliceNode::Ptr, int> order_map;
282     set<SliceNode::Ptr> done;
283 };
284
285 // implements < , <= causes failures when used to sort Windows vectors
286 bool vectorSort(SliceNode::Ptr ptr1, SliceNode::Ptr ptr2) {
287
288     AssignmentPtr assign1 = ptr1->assign();
289     AssignmentPtr assign2 = ptr2->assign();
290
291     if (!assign2) return false;
292     else if (!assign1) return true;
293
294     Address addr1 = assign1->addr();
295     Address addr2 = assign2->addr();
296
297     if (addr1 == addr2) {
298         AbsRegion &out1 = assign1->out();
299         AbsRegion &out2 = assign2->out();
300         return out1 < out2;
301     } else {
302         return addr1 < addr2;
303     }
304 }
305
306 // Do the previous, but use a Graph as a guide for
307 // performing forward substitution on the AST results
308 SymEval::Retval_t SymEval::expand(Dyninst::Graph::Ptr slice, DataflowAPI::Result_t &res) {
309     bool failedTranslation = false;
310     bool skippedInput = false;
311
312     //cout << "Calling expand" << endl;
313     // Other than the substitution this is pretty similar to the first example.
314     NodeIterator gbegin, gend;
315     slice->allNodes(gbegin, gend);
316
317     // First, we'll sort the nodes in some deterministic order so that the loop removal
318     // is deterministic
319     std::vector<SliceNode::Ptr> sortVector;
320     for ( ; gbegin != gend; ++gbegin) {
321         Node::Ptr ptr = *gbegin;
322                 expand_cerr << "pushing " << (*gbegin)->format() << " to sortVector" << endl;
323         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(ptr);
324         sortVector.push_back(cur);
325     }
326     std::stable_sort(sortVector.begin(), sortVector.end(), vectorSort);
327
328     // Optimal ordering of search
329     ExpandOrder worklist;
330
331     std::queue<Node::Ptr> dfs_worklist;
332     std::vector<SliceNode::Ptr>::iterator vit = sortVector.begin();
333     for ( ; vit != sortVector.end(); ++vit) {
334         SliceNode::Ptr ptr = *vit;
335         Node::Ptr cur = boost::static_pointer_cast<Node>(ptr);
336         dfs_worklist.push(cur);
337     }
338
339     /* First, we'll do DFS to check for circularities in the graph;
340      * if so, mark them so we don't do infinite substitution */
341     std::map<Node::Ptr, int> state;
342     while (!dfs_worklist.empty()) {
343         Node::Ptr ptr = dfs_worklist.front(); dfs_worklist.pop();
344         dfs(ptr, state, worklist.skipEdges());
345     }
346
347     slice->allNodes(gbegin, gend);
348     for (; gbegin != gend; ++gbegin) {
349         expand_cerr << "adding " << (*gbegin)->format() << " to worklist" << endl;
350         Node::Ptr ptr = *gbegin;
351         SliceNode::Ptr sptr = 
352             boost::static_pointer_cast<SliceNode>(ptr);
353         worklist.insert(sptr,false);
354     }
355
356     /* have a list
357      * for each node, process
358      * if processessing succeeded, remove the element
359      * if the size of the list has changed, continue */
360
361     while (1) {
362       SliceNode::Ptr aNode;
363       int order;
364
365       boost::tie(aNode,order) = worklist.pop_next();
366       if (order == -1) // empty
367           break;
368
369       if (!aNode->assign()) {
370           worklist.mark_done(aNode);
371           continue; // Could be a widen point
372       }
373
374       expand_cerr << "Visiting node " << aNode->assign()->format() 
375                   << " order " << order << endl;
376
377       if (order != 0) {
378               cerr << "ERROR: order is non zero: " << order << endl;
379       }
380       assert(order == 0); // there are no loops
381
382       AST::Ptr prev = res[aNode->assign()];
383       Retval_t result = process(aNode, res, worklist.skipEdges()); 
384       AST::Ptr post = res[aNode->assign()];
385       switch (result) {
386          case FAILED:
387             return FAILED;
388             break;
389          case WIDEN_NODE:
390             // Okay...
391             break;
392          case FAILED_TRANSLATION:
393             failedTranslation = true;
394             break;
395          case SKIPPED_INPUT:
396             skippedInput = true;
397             break;
398          case SUCCESS:
399             break;
400       }
401
402       // We've visited this node, freeing its children
403       // to be visited in turn
404       worklist.mark_done(aNode);
405
406       if (post && !(post->equals(prev))) {
407         expand_cerr << "Adding successors to list, as new expansion " << endl
408             << "\t" << post->format() << endl 
409             << " != " << endl
410             << "\t" << (prev ? prev->format() : "<NULL>") << endl;
411         EdgeIterator oB, oE;
412         aNode->outs(oB, oE);
413         for (; oB != oE; ++oB) {
414             if(worklist.skipEdges().find(*oB) == worklist.skipEdges().end()) {
415                 SliceNode::Ptr out =
416                     boost::static_pointer_cast<SliceNode>(
417                         (*oB)->target());
418                 worklist.insert(out);
419             }
420         }
421       }
422     }
423     if (failedTranslation) return FAILED_TRANSLATION;
424     else if (skippedInput) return SKIPPED_INPUT;
425     else return SUCCESS;
426 }
427
428 bool SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
429                          const uint64_t addr,
430                          Result_t &res) {
431
432
433     SgAsmInstruction *roseInsn;
434     switch (insn->getArch()) {
435         case Arch_x86: {
436             SymEvalPolicy policy(res, addr, insn->getArch(), insn);
437             RoseInsnX86Factory fac(Arch_x86);
438             roseInsn = fac.convert(insn, addr);
439
440             SymbolicExpansion exp;
441             exp.expandX86(roseInsn, policy);
442             if (policy.failedTranslate()) {
443                 cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
444                 return false;
445             }
446
447             break;
448         }
449         case Arch_x86_64: {
450             SymEvalPolicy_64 policy(res, addr, insn->getArch(), insn);
451             RoseInsnX86Factory fac(Arch_x86_64);
452             roseInsn = fac.convert(insn, addr);
453
454             SymbolicExpansion exp;
455             exp.expandX86_64(roseInsn, policy);
456             if (policy.failedTranslate()) {
457                 cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
458                 return false;
459             }
460
461             break;
462
463         }
464         case Arch_ppc32: {
465             SymEvalPolicy policy(res, addr, insn->getArch(), insn);
466             RoseInsnPPCFactory fac;
467             roseInsn = fac.convert(insn, addr);
468
469             SymbolicExpansion exp;
470             exp.expandPPC32(roseInsn, policy);
471             if (policy.failedTranslate()) {
472                 cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
473                 return false;
474             }
475
476             break;
477         }
478         case Arch_ppc64: {
479             SymEvalPolicy_64 policy(res, addr, insn->getArch(), insn);
480             RoseInsnPPCFactory fac;
481             roseInsn = fac.convert(insn, addr);
482
483             SymbolicExpansion exp;
484             exp.expandPPC64(roseInsn, policy);
485             if (policy.failedTranslate()) {
486                 cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
487                 return false;
488             }
489
490             break;
491         }
492         case Arch_aarch64: {
493             RoseInsnArmv8Factory fac(Arch_aarch64);
494             roseInsn = fac.convert(insn, addr);
495
496             SymbolicExpansion exp;
497             const RegisterDictionary *reg_dict = RegisterDictionary::dictionary_armv8();
498
499             BaseSemantics::SValuePtr protoval = SymEvalSemantics::SValue::instance(1, 0);
500             BaseSemantics::RegisterStatePtr registerState = SymEvalSemantics::RegisterStateARM64::instance(protoval, reg_dict);
501             BaseSemantics::MemoryStatePtr memoryState = SymEvalSemantics::MemoryStateARM64::instance(protoval, protoval);
502             BaseSemantics::StatePtr state = SymEvalSemantics::StateARM64::instance(res, addr, insn->getArch(), insn, registerState, memoryState);
503             BaseSemantics::RiscOperatorsPtr ops = SymEvalSemantics::RiscOperators::instance(state);
504
505             exp.expandAarch64(roseInsn, ops, insn->format());
506         }
507         break;
508         default:
509             assert(0 && "Unimplemented symbolic expansion architecture");
510             break;
511     }
512
513     return true;
514 }
515
516
517 SymEval::Retval_t SymEval::process(SliceNode::Ptr ptr,
518                                    Result_t &dbase,
519                                    std::set<Edge::Ptr> &skipEdges) {
520    bool failedTranslation;
521    bool skippedEdge = false;
522    bool skippedInput = false;
523    bool success = false;
524
525     std::map<const AbsRegion, std::set<Assignment::Ptr> > inputMap;
526
527     expand_cerr << "Calling process on " << ptr->format() << endl;
528
529     // Don't try an expansion of a widen node...
530     if (!ptr->assign()) return WIDEN_NODE;
531
532     EdgeIterator begin, end;
533     ptr->ins(begin, end);
534
535     for (; begin != end; ++begin) {
536          SliceEdge::Ptr edge = boost::static_pointer_cast<SliceEdge>(*begin);
537          SliceNode::Ptr source = boost::static_pointer_cast<SliceNode>(edge->source());
538
539          // Skip this one to break a cycle.
540          if (skipEdges.find(edge) != skipEdges.end()) {
541                      expand_cerr << "In process, skipping edge from "
542                                  << source->format() << endl;
543              skippedEdge = true;
544                  continue;
545          }
546        
547                  Assignment::Ptr assign = source->assign();
548                  if (!assign) continue; // widen node
549        
550                  expand_cerr << "Assigning input " << edge->data().format()
551                      << " from assignment " << assign->format() << endl;
552                  inputMap[edge->data()].insert(assign);
553     }
554     
555     expand_cerr << "\t Input map has size " << inputMap.size() << endl;
556     
557     // All of the expanded inputs are in the parameter dbase
558     // If not (like this one), add it
559     
560     AST::Ptr ast;
561     boost::tie(ast, failedTranslation) = SymEval::expand(ptr->assign());
562     // expand_cerr << "\t ... resulting in " << dbase.format() << endl;
563
564     // We have an AST. Now substitute in all of its predecessors.
565     for (std::map<const AbsRegion, std::set<Assignment::Ptr> >::iterator iter = inputMap.begin();
566          iter != inputMap.end(); ++iter) {
567                  // If we have multiple secondary definitions, we:
568                  //   if all definitions are equal, use the first
569                  //   otherwise, use nothing
570                  AST::Ptr definition;
571
572                  for (std::set<Assignment::Ptr>::iterator iter2 = iter->second.begin(); 
573                           iter2 != iter->second.end(); ++iter2) {
574                           AST::Ptr newDef = dbase[*iter2];
575                           if (!definition) {
576                                   definition = newDef;
577                                   continue;
578                           } else if (definition->equals(newDef)) {
579                                   continue;
580                           } else {
581                                   // Not equal
582                                   definition = AST::Ptr();
583                                   skippedInput = true;
584                                   break;
585                           }
586                   }
587
588                   // The region used by the current assignment...
589                   const AbsRegion &reg = iter->first;
590       
591                   // Create an AST around this one
592                   VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
593       
594                   if (!definition) {
595                           // Can happen if we're expanding out of order, and is generally harmless.
596                           continue;
597                   }
598                   expand_cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
599
600                   if (!ast) {
601                           expand_cerr << "Skipping substitution because of null AST" << endl;
602                   } else {
603                           ast = AST::substitute(ast, use, definition);
604                           success = true;
605                   }
606                   expand_cerr << "\t result is " << (ast ? ast->format() : "<NULL AST>") << endl;
607     }
608     expand_cerr << "Result of substitution: " << ptr->assign()->format() << " == " 
609                         << (ast ? ast->format() : "<NULL AST>") << endl;
610     
611     // And attempt simplification again
612     ast = simplifyStack(ast, ptr->addr(), ptr->func(), ptr->block());
613     expand_cerr << "Result of post-substitution simplification: " << ptr->assign()->format() << " == " 
614                 << (ast ? ast->format() : "<NULL AST>") << endl;
615     
616     dbase[ptr->assign()] = ast;
617     if (failedTranslation) return FAILED_TRANSLATION;
618     else if (skippedEdge || skippedInput) return SKIPPED_INPUT;
619     else if (success) return SUCCESS;
620     else return FAILED;
621 }
622
623 AST::Ptr SymEval::simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func, ParseAPI::Block *block) {
624   if (!ast) return ast;
625   // Let's experiment with simplification
626   StackAnalysis sA(func);
627   StackAnalysis::Height sp = sA.findSP(block, addr);
628   StackAnalysis::Height fp = sA.find(block, addr, MachRegister::getFramePointer(func->isrc()->getArch()));
629   
630   StackVisitor sv(addr, func, sp, fp);
631
632   AST::Ptr simplified = ast->accept(&sv);
633
634   return simplified;
635 }