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