Implemented basic memory tracking for stack analysis.
[dyninst.git] / dyninstAPI / src / StackMod / StackAccess.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 <sstream>
32
33 #include "debug.h"
34
35 #include "Instruction.h"
36 #include "InstructionDecoder.h"
37 #include "Expression.h"
38 #include "Register.h"
39 #include "Result.h"
40 #include "Dereference.h"
41 #include "Immediate.h"
42 #include "BinaryFunction.h"
43
44 #include "CFG.h"
45
46 #include "slicing.h"
47 #include "SymEval.h"
48
49 #include "StackAccess.h"
50
51 using namespace Dyninst;
52
53 std::string StackAccess::printStackAccessType(StackAccess::StackAccessType t)
54 {
55     switch(t) {
56         case(StackAccess::READ):
57             return "READ";
58         case(StackAccess::WRITE):
59             return "WRITE";
60         case(StackAccess::SAVED):
61             return "SAVED";
62         case(StackAccess::READWRITE):
63             return "READWRITE";
64         case(StackAccess::REGHEIGHT):
65             return "REGHEIGHT";
66         case(StackAccess::DEBUGINFO_LOCAL):
67             return "DEBUGINFO_LOCAL";
68         case(StackAccess::DEBUGINFO_PARAM):
69             return "DEBUGINFO_PARAM";
70         case(StackAccess::UNKNOWN):
71             return "UNKNOWN";
72         case (StackAccess::MISUNDERSTOOD):
73             return "MISUNDERSTOOD";
74         default:
75             return "NOT RECOGNIZED ACCESS TYPE";
76     }
77 }
78
79 std::string StackAccess::format()
80 {
81     std::stringstream ret;
82     ret << "Access to " << _readHeight.height()
83         << " from " << _reg.name()
84         << " (at " << _regHeight.height() << ")"
85         << ", insn disp = " << _disp
86         << ", is " << printStackAccessType(_type);
87     return ret.str();
88 }
89
90 bool isDebugType(StackAccess::StackAccessType t)
91 {
92     return (t==StackAccess::DEBUGINFO_LOCAL ||
93             t==StackAccess::DEBUGINFO_PARAM);
94 }
95
96 int getAccessSize(InstructionAPI::Instruction::Ptr insn)
97 {
98     std::vector<InstructionAPI::Operand> operands;
99     insn->getOperands(operands);
100     int accessSize = 0;
101     for (unsigned i = 0; i < operands.size(); i++) {
102         InstructionAPI::Expression::Ptr value = operands[i].getValue();
103
104         if (accessSize == 0) {
105             accessSize = value->size();
106         } else {
107             accessSize = min(accessSize, value->size());
108         }
109     }
110
111     return accessSize;
112 }
113
114 bool getAccesses(ParseAPI::Function* func,
115         ParseAPI::Block* block,
116         Address addr,
117         InstructionAPI::Instruction::Ptr insn,
118         Accesses*& accesses)
119 {
120     bool ret = true;
121
122     stackmods_printf("\t\t getAccesses %s, 0x%lx @ 0x%lx: %s\n", func->name().c_str(), block->start(), addr, insn->format().c_str());
123
124     Architecture arch = insn->getArch();
125     StackAnalysis sa(func);
126     std::vector<std::pair<Absloc, StackAnalysis::Height> > heights;
127     sa.findDefinedHeights(block, addr, heights);
128
129     if (insn->getOperation().getID() == e_ret_far || insn->getOperation().getID() == e_ret_near) {
130         return true;
131     }
132
133     for (auto iter = heights.begin(); iter != heights.end(); ++iter) {
134         // Only consider registers, not tracked memory locations
135         if (iter->first.type() != Absloc::Register) continue;
136         MachRegister curReg = iter->first.reg();
137
138         unsigned int gpr;
139         if (arch == Arch_x86) {
140             gpr = x86::GPR;
141         } else if (arch == Arch_x86_64) {
142             gpr = x86_64::GPR;
143         } else {
144             assert(0);
145         }
146
147         // Skip the PC
148         if (curReg == MachRegister::getPC(arch)) {
149             continue;
150         }
151
152         // Skip flags
153         if (curReg.regClass() != gpr) {
154             continue;
155         }
156
157         StackAnalysis::Height curHeight = (*iter).second;
158         StackAccess* access = NULL;
159         if (getMemoryOffset(func,
160                     block,
161                     insn,
162                     addr,
163                     curReg,
164                     curHeight,
165                     access,
166                     arch)) {
167             if (curHeight.isBottom()) {
168                 stackmods_printf("\t\t\t\t INVALID: Found access based on register we don't understand (%s = %s)\n",
169                         curReg.name().c_str(),
170                         curHeight.format().c_str());
171                 // Once we've found a bad access, stop looking!
172                 return false;
173             }
174             else {
175
176                 if (access->readHeight().height() > 20480) {
177                     stackmods_printf("\t\t\t\t Found bogus %s. Skipping.\n", access->format().c_str());
178                     continue;
179                 }
180
181                 accesses->insert(make_pair(curReg, access));
182             }
183         }
184     }
185
186     return ret;
187 }
188
189 using namespace InstructionAPI;
190
191 // Copied and modified from parseAPI/src/IA_x86Details.C
192 class zeroAllGPRegisters : public InstructionAPI::Visitor
193 {
194     public:
195         zeroAllGPRegisters(Address ip, ParseAPI::Function* f, ParseAPI::Block* b, InstructionAPI::Instruction::Ptr i, bool z = false) :
196             defined(true), m_ip(ip), func(f), block(b), insn(i), zero(z) {
197                 if (func) {
198                     StackAnalysis tmp(func);
199                     sa = tmp;
200                 }
201             }
202
203         virtual ~zeroAllGPRegisters() {}
204         bool defined;
205         std::deque<long> results;
206         Address m_ip;
207         ParseAPI::Function* func;
208         ParseAPI::Block* block;
209         InstructionAPI::Instruction::Ptr insn;
210         StackAnalysis sa;
211         bool zero;
212         long getResult() {
213             if(results.empty()) return 0;
214             return results.front();
215         }
216         bool isDefined() {
217             return defined && (results.size() == 1);
218         }
219         virtual void visit(BinaryFunction* b)
220         {
221             if(!defined) return;
222             long arg1 = results.back();
223             results.pop_back();
224             long arg2 = results.back();
225             results.pop_back();
226             if(b->isAdd())
227             {
228                 results.push_back(arg1+arg2);
229             }
230             else if(b->isMultiply())
231             {
232                 results.push_back(arg1*arg2);
233             }
234             else
235             {
236                 defined = false;
237             }
238         }
239         virtual void visit(Immediate* i)
240         {
241             if(!defined) return;
242             results.push_back(i->eval().convert<long>());
243         }
244         virtual void visit(RegisterAST* r)
245         {
246             if(!defined) return;
247             if(r->getID() == x86::eip ||
248                r->getID() == x86_64::eip ||
249                r->getID() == x86_64::rip)
250             {
251                 results.push_back(m_ip);
252                 return;
253             }
254
255             if (!zero) {
256                 if (func) {
257                     StackAnalysis::Height height = sa.find(block, m_ip, r->getID());
258                     if (!height.isBottom() && !height.isTop()) {
259                         stackmods_printf("\t\t\t found %s height = %ld\n", r->getID().name().c_str(), height.height());
260                         results.push_back(height.height());
261                         return;
262                     }
263                 }
264             }
265
266             results.push_back(0);
267         }
268         virtual void visit(Dereference* )
269         {
270             defined = false;
271         }
272
273 };
274
275 bool getMemoryOffset(ParseAPI::Function* func,
276         ParseAPI::Block* block,
277         InstructionAPI::InstructionPtr insn,
278         Address addr,
279         MachRegister reg,
280         StackAnalysis::Height height,
281         StackAccess*& ret,
282         Architecture arch)
283 {
284
285     stackmods_printf("\t\t\t getMemoryOffset for %s; checking reg %s = %s\n", insn->format().c_str(), reg.name().c_str(), height.format().c_str());
286
287     bool skipReg = false;
288     bool multChildrenInDeref = false;
289
290     InstructionAPI::RegisterAST* regAST = new InstructionAPI::RegisterAST(reg);
291     InstructionAPI::RegisterAST::Ptr regASTPtr = InstructionAPI::RegisterAST::Ptr(regAST);
292
293     std::vector<InstructionAPI::Operand> operands;
294     insn->getOperands(operands);
295
296     signed long disp = 0;
297     signed long offset = 0;
298     bool isOffsetSet = false;
299
300     // Determine how memory is accessed
301     StackAccess::StackAccessType type = StackAccess::UNKNOWN;
302     if (insn->readsMemory() && insn->writesMemory()) {
303         type = StackAccess::READWRITE;
304     } else if (insn->readsMemory()) {
305         type = StackAccess::READ;
306     } else if (insn->writesMemory()) {
307         type = StackAccess::WRITE;
308     }
309
310     // If memory is not accessed, no need to find an offset
311     if (type == StackAccess::UNKNOWN) {
312         return false;
313     }
314
315     for (unsigned i = 0; i < operands.size(); i++) {
316
317         stackmods_printf("\t\t\t\t operand[%d] = %s\n", i, operands[i].getValue()->format().c_str());
318
319         // Get the read/written register sets
320         bool match = false;
321         if (reg.isValid()) {
322             std::set<InstructionAPI::RegisterAST::Ptr> regsRead;
323             operands[i].getReadSet(regsRead);
324             for (auto iter = regsRead.begin(); iter != regsRead.end(); ++iter) {
325                 InstructionAPI::RegisterAST::Ptr cur = *iter;
326                 if (*cur == *regASTPtr) {
327                     stackmods_printf("\t\t\t\t\t reads reg\n");
328                     match = true;
329                 }
330             }
331             std::set<InstructionAPI::RegisterAST::Ptr> regsWrite;
332             operands[i].getWriteSet(regsWrite);
333             for (auto iter = regsWrite.begin(); iter != regsWrite.end(); ++iter) {
334                 InstructionAPI::RegisterAST::Ptr cur = *iter;
335                 if (*cur == *regASTPtr) {
336                     stackmods_printf("\t\t\t\t\t writes reg\n");
337                     match = true;
338                }
339             }
340         }
341
342         // If at least one register is read/written...
343         if (match || !reg.isValid()) {
344             InstructionAPI::Expression::Ptr val = operands[i].getValue();
345             if (!val) break;
346
347             // Won't find an offset for an immediate
348             if ( (typeid(*val) == typeid(InstructionAPI::Immediate))) {
349                 continue;
350             }
351
352             // Won't find an offset for a registerAST
353             // However, we do want to record a push (e.g., callee-saved registers)
354             if (!(insn->getOperation().getID() == e_push)) {
355                 if (typeid(*val) == typeid(InstructionAPI::RegisterAST)) {
356                     continue;
357                 }
358             }
359
360             // If we have a dereference, extract the child
361             if (typeid(*val) == typeid(InstructionAPI::Dereference)) {
362                 vector<InstructionAPI::InstructionAST::Ptr> children;
363                 val->getChildren(children);
364                 if (children.size() == 1) {
365                     InstructionAPI::InstructionAST::Ptr child = children.front();
366                     val = boost::dynamic_pointer_cast<InstructionAPI::Expression>(child);
367                 }
368             }
369
370             // Copied from parseAPI/src/IA_x86Details.C IA_x86Details::findTableInsn()
371             zeroAllGPRegisters z(addr, func, block, insn, false);
372             val->apply(&z);
373             if (z.isDefined()) {
374                 zeroAllGPRegisters z2(addr, func, block, insn, true);
375                 val->apply(&z2);
376
377                 isOffsetSet = true;
378                 offset = z.getResult();
379
380                 if ( (z2.isDefined()) &&
381                      ( (z2.getResult()) ||
382                        (z.getResult() == z2.getResult()))) {
383                     disp = z2.getResult();
384                 } else {
385                     disp = 0;
386                 }
387
388                 stackmods_printf("\t\t\t\t found offset %ld, disp = %ld, type = %d\n", offset, disp, type);
389
390                 // Weird check: is there more than one child in the dereference? If not, we may want to skip
391                 vector<InstructionAPI::InstructionAST::Ptr> children2;
392                 val->getChildren(children2);
393                 if (children2.size() > 1) {
394                     stackmods_printf("\t\t\t\t\t Found >1 child in dereference.\n");
395                     multChildrenInDeref = true;
396                 }
397             }
398         }
399     }
400
401     std::stringstream msg;
402     if (isOffsetSet) {
403
404         // Question: Where did this stack height come from?
405         if (reg.isValid() &&
406                 /*!multChildrenInDeref && */
407                 (reg != MachRegister::getStackPointer(arch))) {
408
409
410             bool performSlice = true;
411             if (multChildrenInDeref && (disp==0)) {
412                 // We will never mark this as a skipReg, so avoid slicing
413                 performSlice = false;
414             }
415
416             if (multChildrenInDeref && (type==StackAccess::UNKNOWN)) {
417                 // We will never mark this as a skipReg, so avoid slicing
418                 performSlice = false;
419             }
420
421             if ((insn->getOperation().getID() == e_push)) {
422                 performSlice = false;
423             }
424
425             if (height.isBottom()) {
426                 performSlice = false;
427             }
428
429             if (performSlice) {
430
431                 std::vector<AbsRegion> ins;
432                 ins.push_back(AbsRegion(Absloc(reg)));
433                 Assignment::Ptr assign = Assignment::Ptr(new Assignment(insn,
434                             addr,
435                             func,
436                             block,
437                             ins,
438                             AbsRegion(Absloc(reg))));
439                 Slicer slicer(assign, block, func);
440                 Slicer::Predicates defaultPredicates;
441                 stackmods_printf("\t\t\t\t Using slicing @ 0x%lx for %s\n", addr, reg.name().c_str());
442                 Graph::Ptr graph = slicer.backwardSlice(defaultPredicates);
443
444                 stackmods_printf("\t\t\t\t\t Slicing complete, graph size = %d\n", graph->size());
445
446                 // Graph must have single entry
447                 NodeIterator exitBegin, exitEnd;
448                 graph->exitNodes(exitBegin, exitEnd);
449
450                 if (*exitBegin == NULL) {
451                     assert(0 && "Could not find exit node for backward slice");
452                 }
453
454                 std::set<Address> visited;
455
456                 // Graph must have straight-line path
457                 NodeIterator inBegin, inEnd;
458                 (*exitBegin)->ins(inBegin, inEnd);
459                 NodeIterator prev = inBegin;
460                 while ((*prev)->hasInEdges()) {
461                     NodeIterator tmp = inBegin;
462
463                     if (tmp != inEnd) {
464                         stackmods_printf("\t\t\t\t\t Next level\n");
465                         stackmods_printf("\t\t\t\t\t\t tmp: %s\n", (*tmp)->format().c_str());
466                     }
467
468                     // Check for cycles
469                     if (visited.find((*tmp)->addr()) != visited.end()) {
470                         skipReg = true;
471                         break;
472                     }
473                     visited.insert((*tmp)->addr());
474
475                     while (tmp != inEnd) {
476                         NodeIterator next = tmp;
477                         next++;
478
479                         if (next == inEnd) {
480                             break;
481                         }
482                         stackmods_printf("\t\t\t\t\t\t next: %s\n", (*next)->format().c_str());
483                         if ((*next)->DOTname().compare("<NULL>") == 0) {
484                             tmp++;
485                             continue;
486                         }
487
488                         // Check for cycles
489                         if (visited.find((*next)->addr()) != visited.end()) {
490                             skipReg = true;
491                             break;
492                         }
493                         visited.insert((*next)->addr());
494
495                         if ((*tmp)->addr() != (*next)->addr()) {
496                             skipReg = true;
497                             break;
498                         }
499                         tmp++;
500                     }
501
502                     if (skipReg) break;
503
504                     if (!(*inBegin)->hasInEdges()) {
505                         break;
506                     }
507                     prev = inBegin;
508                     (*inBegin)->ins(inBegin, inEnd);
509                 }
510
511                 stackmods_printf("\t\t\t\t Finished using backward slice to check for skipReg\n");
512
513             }
514         }
515
516         if (skipReg && multChildrenInDeref && disp==0) {
517             stackmods_printf("\t\t\t\t\t\t unset skipReg (multchildren && disp==0)\n");
518             skipReg = false;
519         }
520
521         if (skipReg && multChildrenInDeref && type==StackAccess::UNKNOWN) {
522             stackmods_printf("\t\t\t\t\t\t unset skipReg (multchildren && StackAccess::UNKNOWN\n");
523             skipReg = false;
524         }
525
526         ret = new StackAccess();
527         ret->setRegHeight(height);
528         ret->setReg(reg);
529         ret->setType(type);
530         ret->setDisp(disp);
531         ret->setSkipReg(skipReg);
532
533         if (ret->disp() && arch == Arch_x86) {
534             // Fix the signed issue
535             signed long fixedOffset;
536             Offset MAX = 0xffffffff;
537             if (disp > (long)MAX/2) {
538                 fixedOffset = -1*(MAX - disp + 1);
539                 disp = fixedOffset;
540                 ret->setDisp(disp);
541             }
542         }
543
544         ret->setReadHeight(StackAnalysis::Height(offset));
545
546         // Stackanalysis is reporting the heights at the start of the
547         // instruction, not the end; for push, we want to record the final
548         // state, which is where the value is actually stored
549         if (insn->getOperation().getID() == e_push) {
550             long width;
551             if (arch == Arch_x86) width = 4;
552             else width = 8;
553             ret->setRegHeight(ret->regHeight() - width);
554             ret->setReadHeight(ret->readHeight() - width);
555             ret->setType(StackAccess::SAVED);
556         }
557     }
558
559     return isOffsetSet;
560 }
561