Conservative fix for the stack pointer passing problem.
[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 "InstructionCategories.h"
37 #include "InstructionDecoder.h"
38 #include "Expression.h"
39 #include "Register.h"
40 #include "Result.h"
41 #include "Dereference.h"
42 #include "Immediate.h"
43 #include "BinaryFunction.h"
44
45 #include "CFG.h"
46
47 #include "ABI.h"
48 #include "slicing.h"
49 #include "SymEval.h"
50
51 #include "StackAccess.h"
52
53 using namespace std;
54 using namespace Dyninst;
55
56 std::string StackAccess::printStackAccessType(StackAccess::StackAccessType t)
57 {
58     switch(t) {
59         case(StackAccess::READ):
60             return "READ";
61         case(StackAccess::WRITE):
62             return "WRITE";
63         case(StackAccess::SAVED):
64             return "SAVED";
65         case(StackAccess::READWRITE):
66             return "READWRITE";
67         case(StackAccess::REGHEIGHT):
68             return "REGHEIGHT";
69         case(StackAccess::DEBUGINFO_LOCAL):
70             return "DEBUGINFO_LOCAL";
71         case(StackAccess::DEBUGINFO_PARAM):
72             return "DEBUGINFO_PARAM";
73         case(StackAccess::UNKNOWN):
74             return "UNKNOWN";
75         case (StackAccess::MISUNDERSTOOD):
76             return "MISUNDERSTOOD";
77         default:
78             return "NOT RECOGNIZED ACCESS TYPE";
79     }
80 }
81
82 std::string StackAccess::format()
83 {
84     std::stringstream ret;
85     ret << "Access to " << _readHeight.height()
86         << " from " << _reg.name()
87         << " (at " << _regHeight.height() << ")"
88         << ", insn disp = " << _disp
89         << ", is " << printStackAccessType(_type);
90     return ret.str();
91 }
92
93 bool isDebugType(StackAccess::StackAccessType t)
94 {
95     return (t==StackAccess::DEBUGINFO_LOCAL ||
96             t==StackAccess::DEBUGINFO_PARAM);
97 }
98
99 int getAccessSize(InstructionAPI::Instruction::Ptr insn)
100 {
101     std::vector<InstructionAPI::Operand> operands;
102     insn->getOperands(operands);
103     int accessSize = 0;
104     for (unsigned i = 0; i < operands.size(); i++) {
105         InstructionAPI::Expression::Ptr value = operands[i].getValue();
106
107         if (accessSize == 0) {
108             accessSize = value->size();
109         } else {
110             accessSize = min(accessSize, value->size());
111         }
112     }
113
114     return accessSize;
115 }
116
117 // FreeBSD is missing a MINLONG and MAXLONG
118 #if defined(os_freebsd)
119 #if defined(arch_64bit)
120 #define MINLONG INT64_MIN
121 #define MAXLONG INT64_MAX
122 #else
123 #define MINLONG INT32_MIN
124 #define MAXLONG INT32_MAX
125 #endif
126 #endif
127 class detectToppedLoc : public InstructionAPI::Visitor {
128 private:
129     typedef std::vector<std::pair<Absloc, StackAnalysis::Height>> Heights;
130     bool defined;
131     bool containsToppedReg;
132     Heights heights;
133
134     std::deque<long> results;  // Stack for calculations
135
136     // Values used for calculations in results
137     static const long top = MAXLONG;
138     static const long bottom = MINLONG;
139     static const long determinable = 0;
140
141 public:
142     detectToppedLoc(Heights &h) : defined(true), containsToppedReg(false),
143         heights(h) {}
144
145     bool isDefined() {
146         return defined && results.size() == 1;
147     }
148
149     bool isBottomed() {
150         assert(isDefined());
151         return containsToppedReg && results.back() == bottom;
152     }
153
154     bool isTopped() {
155         assert(isDefined());
156         return containsToppedReg && results.back() != bottom;
157     }
158
159     virtual void visit(InstructionAPI::BinaryFunction *bf) {
160         if (!defined) return;
161
162         long arg1 = results.back();
163         results.pop_back();
164         long arg2 = results.back();
165         results.pop_back();
166
167         if (bf->isAdd()) {
168             if (arg1 == bottom || arg2 == bottom) {
169                 results.push_back((long) bottom);
170             } else {
171                 results.push_back((long) top);
172             }
173         } else if (bf->isMultiply()) {
174             if (arg1 == bottom) {
175                 if (arg2 != top && arg2 != bottom && arg2 != 1) {
176                     results.push_back((long) top);
177                 } else {
178                     results.push_back((long) bottom);
179                 }
180             } else if (arg2 == bottom) {
181                 if (arg1 != top && arg1 != bottom && arg1 != 1) {
182                     results.push_back((long) top);
183                 } else {
184                     results.push_back((long) bottom);
185                 }
186             } else {
187                 results.push_back((long) top);
188             }
189         } else {
190             defined = false;
191         }
192     }
193
194     virtual void visit(InstructionAPI::Immediate *imm) {
195         if (!defined) return;
196
197         results.push_back(imm->eval().convert<long>());
198     }
199
200     virtual void visit(InstructionAPI::RegisterAST *r) {
201         if (!defined) return;
202
203         MachRegister reg = r->getID();
204         if (reg == x86::eip || reg == x86_64::eip || reg == x86_64::rip) {
205             results.push_back((long) determinable);
206             return;
207         }
208
209         Absloc regLoc(reg);
210         for (auto iter = heights.begin(); iter != heights.end(); iter++) {
211             if (regLoc == iter->first) {
212                 if (iter->second.isTop()) {
213                     containsToppedReg = true;
214                     results.push_back((long) top);
215                 } else {
216                     results.push_back((long) bottom);
217                 }
218                 return;
219             }
220         }
221         // If reg isn't in heights, its height is TOP
222         containsToppedReg = true;
223         results.push_back((long) top);
224     }
225
226     virtual void visit(InstructionAPI::Dereference *) {
227         defined = false;
228     }
229 };
230
231
232
233 bool getAccesses(ParseAPI::Function* func,
234         ParseAPI::Block* block,
235         Address addr,
236         InstructionAPI::Instruction::Ptr insn,
237         Accesses*& accesses)
238 {
239     bool ret = true;
240
241     stackmods_printf("\t\t getAccesses %s, 0x%lx @ 0x%lx: %s\n",
242         func->name().c_str(), block->start(), addr, insn->format().c_str());
243
244     Architecture arch = insn->getArch();
245     std::set<InstructionAPI::RegisterAST::Ptr> readRegs;
246     insn->getReadSet(readRegs);
247     StackAnalysis sa(func);
248     std::vector<std::pair<Absloc, StackAnalysis::Height> > heights;
249     sa.findDefinedHeights(block, addr, heights);
250
251     if (insn->getOperation().getID() == e_ret_far ||
252         insn->getOperation().getID() == e_ret_near) {
253         return true;
254     }
255
256     unsigned int gpr;
257     if (arch == Arch_x86) {
258         gpr = x86::GPR;
259     } else if (arch == Arch_x86_64) {
260         gpr = x86_64::GPR;
261     } else {
262         assert(0);
263     }
264
265     int word_size = func->isrc()->getAddressWidth();
266
267     // If this instruction is a call, check if any stack pointers are possibly
268     // being passed as parameters.  If so, we don't know what the callee will
269     // access through that pointer and need to return false.
270     if (insn->getCategory() == InstructionAPI::c_CallInsn) {
271         // Check parameter registers for stack pointers
272         ABI *abi = ABI::getABI(word_size);
273         const bitArray &callParamRegs = abi->getParameterRegisters();
274         for (auto iter = abi->getIndexMap()->begin();
275             iter != abi->getIndexMap()->end(); iter++) {
276             const MachRegister &reg = iter->first;
277             if (reg.regClass() == gpr && callParamRegs.test(iter->second)) {
278                 // This register is used as a parameter. Check if it contains a
279                 // stack pointer.
280                 const StackAnalysis::Height &h = sa.find(block, addr,
281                     Absloc(reg));
282                 if (!h.isTop()) {
283                     return false;
284                 }
285             }
286         }
287
288         // Check parameters passed on stack for stack pointers
289         const StackAnalysis::Height &sp = sa.findSP(block, addr);
290         if (!sp.isTop() && !sp.isBottom()) {
291             // Check most recent words on stack for stack pointers.  We check
292             // last 7 words as a reasonable medium between conservatism and
293             // liberalism.
294             long lb = sp.height();
295             long ub = sp.height() + word_size * 7;
296             for (auto iter = heights.begin(); iter != heights.end(); iter++) {
297                 const Absloc &loc = iter->first;
298                 const StackAnalysis::Height &h = iter->second;
299
300                 if (loc.type() != Absloc::Stack) continue;
301                 long stackOff = loc.off();
302
303                 if (stackOff < ub && stackOff >= lb && !h.isTop()) {
304                     return false;
305                 }
306             }
307         } else {
308             // Check all stack locations for stack pointers since we don't know
309             // where RSP is pointing on the stack.
310             for (auto iter = heights.begin(); iter != heights.end(); iter++) {
311                 const Absloc &loc = iter->first;
312                 const StackAnalysis::Height &h = iter->second;
313                 if (loc.type() == Absloc::Stack && !h.isTop()) {
314                     return false;
315                 }
316             }
317         }
318     }
319
320     for (auto iter = heights.begin(); iter != heights.end(); ++iter) {
321         // Only consider registers, not tracked memory locations
322         if (iter->first.type() != Absloc::Register) continue;
323         MachRegister curReg = iter->first.reg();
324
325         // Skip the PC
326         if (curReg == MachRegister::getPC(arch)) {
327             continue;
328         }
329
330         // Skip flags
331         if (curReg.regClass() != gpr) {
332             continue;
333         }
334
335         StackAnalysis::Height curHeight = (*iter).second;
336         StackAccess* access = NULL;
337         if (getMemoryOffset(func,
338                     block,
339                     insn,
340                     addr,
341                     curReg,
342                     curHeight,
343                     access,
344                     arch)) {
345             if (curHeight.isBottom()) {
346                 stackmods_printf("\t\t\t\t INVALID: Found access based on "
347                     "register we don't understand (%s = %s)\n",
348                     curReg.name().c_str(), curHeight.format().c_str());
349                 // Once we've found a bad access, stop looking!
350                 return false;
351             } else {
352                 if (access->readHeight().height() > 20480) {
353                     stackmods_printf("\t\t\t\t Found bogus %s. Skipping.\n",
354                         access->format().c_str());
355                     continue;
356                 }
357                 accesses->insert(make_pair(curReg, access));
358             }
359         }
360     }
361
362     // Fail if any stack heights are being written out to topped locations.
363     // Since StackAnalysis tops loads from unresolved locations, we have to
364     // fail if we write out stack heights to unresolved locations. We also fail
365     // if an accessed location has a stack height base and an unknown offset.
366     if (insn->writesMemory()) {
367         std::set<InstructionAPI::Expression::Ptr> writeOperands;
368         insn->getMemoryWriteOperands(writeOperands);
369         assert(writeOperands.size() == 1);
370
371         detectToppedLoc dtl(heights);
372         (*writeOperands.begin())->apply(&dtl);
373         if (dtl.isTopped()) {
374             // We are writing to a topped location.
375             // Check if any of the registers involved in the write contain
376             // stack heights.
377             for (auto regIter = readRegs.begin(); regIter != readRegs.end();
378                 regIter++) {
379                 Absloc regLoc((*regIter)->getID());
380
381                 for (auto hIter = heights.begin(); hIter != heights.end();
382                     hIter++) {
383                     if (hIter->first == regLoc && !hIter->second.isTop()) {
384                         stackmods_printf("\t\t\t\tINVALID: Writing stack "
385                             "height to topped location\n");
386                         return false;
387                     }
388                 }
389             }
390         } else if (dtl.isBottomed()) {
391             stackmods_printf("\t\t\t\tINVALID: Writing to unknown stack "
392                 "location\n");
393             return false;
394         }
395     } else if (insn->readsMemory()) {
396         std::set<InstructionAPI::Expression::Ptr> readOperands;
397         insn->getMemoryReadOperands(readOperands);
398         for (auto rIter = readOperands.begin(); rIter != readOperands.end();
399             rIter++) {
400             detectToppedLoc dtl(heights);
401             (*rIter)->apply(&dtl);
402             if (dtl.isBottomed()) {
403                 stackmods_printf("\t\t\t\tINVALID: Reading unknown stack "
404                     "location\n");
405                 return false;
406             }
407         }
408     }
409
410     return ret;
411 }
412
413 using namespace InstructionAPI;
414
415 // Copied and modified from parseAPI/src/IA_x86Details.C
416 class zeroAllGPRegisters : public InstructionAPI::Visitor
417 {
418     public:
419         zeroAllGPRegisters(Address ip, ParseAPI::Function* f, ParseAPI::Block* b, InstructionAPI::Instruction::Ptr i, bool z = false) :
420             defined(true), m_ip(ip), func(f), block(b), insn(i), zero(z) {
421                 if (func) {
422                     StackAnalysis tmp(func);
423                     sa = tmp;
424                 }
425             }
426
427         virtual ~zeroAllGPRegisters() {}
428         bool defined;
429         std::deque<long> results;
430         Address m_ip;
431         ParseAPI::Function* func;
432         ParseAPI::Block* block;
433         InstructionAPI::Instruction::Ptr insn;
434         StackAnalysis sa;
435         bool zero;
436         long getResult() {
437             if(results.empty()) return 0;
438             return results.front();
439         }
440         bool isDefined() {
441             return defined && (results.size() == 1);
442         }
443         virtual void visit(BinaryFunction* b)
444         {
445             if(!defined) return;
446             long arg1 = results.back();
447             results.pop_back();
448             long arg2 = results.back();
449             results.pop_back();
450             if(b->isAdd())
451             {
452                 results.push_back(arg1+arg2);
453             }
454             else if(b->isMultiply())
455             {
456                 results.push_back(arg1*arg2);
457             }
458             else
459             {
460                 defined = false;
461             }
462         }
463         virtual void visit(Immediate* i)
464         {
465             if(!defined) return;
466             results.push_back(i->eval().convert<long>());
467         }
468         virtual void visit(RegisterAST* r)
469         {
470             if(!defined) return;
471             if(r->getID() == x86::eip ||
472                r->getID() == x86_64::eip ||
473                r->getID() == x86_64::rip)
474             {
475                 results.push_back(m_ip);
476                 return;
477             }
478
479             if (!zero) {
480                 if (func) {
481                     StackAnalysis::Height height = sa.find(block, m_ip,
482                         Absloc(r->getID()));
483                     if (!height.isBottom() && !height.isTop()) {
484                         stackmods_printf("\t\t\t found %s height = %ld\n",
485                             r->getID().name().c_str(), height.height());
486                         results.push_back(height.height());
487                         return;
488                     }
489                 }
490             }
491
492             results.push_back(0);
493         }
494         virtual void visit(Dereference* )
495         {
496             defined = false;
497         }
498
499 };
500
501 bool getMemoryOffset(ParseAPI::Function* func,
502         ParseAPI::Block* block,
503         InstructionAPI::InstructionPtr insn,
504         Address addr,
505         MachRegister reg,
506         StackAnalysis::Height height,
507         StackAccess*& ret,
508         Architecture arch)
509 {
510     stackmods_printf("\t\t\t getMemoryOffset for %s; checking reg %s = %s\n",
511         insn->format().c_str(), reg.name().c_str(), height.format().c_str());
512
513     InstructionAPI::RegisterAST* regAST = new InstructionAPI::RegisterAST(reg);
514     InstructionAPI::RegisterAST::Ptr regASTPtr = InstructionAPI::RegisterAST::Ptr(regAST);
515
516     std::vector<InstructionAPI::Operand> operands;
517     insn->getOperands(operands);
518
519     signed long disp = 0;  // Stack height of access
520     signed long offset = 0;  // Offset from the base register used in the access
521     bool isOffsetSet = false;
522
523     // Determine how memory is accessed
524     StackAccess::StackAccessType type = StackAccess::UNKNOWN;
525     if (insn->readsMemory() && insn->writesMemory()) {
526         type = StackAccess::READWRITE;
527     } else if (insn->readsMemory()) {
528         type = StackAccess::READ;
529     } else if (insn->writesMemory()) {
530         type = StackAccess::WRITE;
531     }
532
533     // If memory is not accessed, no need to find an offset
534     if (type == StackAccess::UNKNOWN) {
535         return false;
536     }
537
538     for (unsigned i = 0; i < operands.size(); i++) {
539         stackmods_printf("\t\t\t\t operand[%d] = %s\n", i,
540             operands[i].getValue()->format().c_str());
541
542         // Set match if reg is read or written
543         bool match = false;
544         if (reg.isValid()) {
545             std::set<InstructionAPI::RegisterAST::Ptr> regsRead;
546             operands[i].getReadSet(regsRead);
547             for (auto iter = regsRead.begin(); iter != regsRead.end(); ++iter) {
548                 InstructionAPI::RegisterAST::Ptr cur = *iter;
549                 if (*cur == *regASTPtr) {
550                     stackmods_printf("\t\t\t\t\t reads reg\n");
551                     match = true;
552                 }
553             }
554             std::set<InstructionAPI::RegisterAST::Ptr> regsWrite;
555             operands[i].getWriteSet(regsWrite);
556             for (auto iter = regsWrite.begin(); iter != regsWrite.end();
557                 ++iter) {
558                 InstructionAPI::RegisterAST::Ptr cur = *iter;
559                 if (*cur == *regASTPtr) {
560                     stackmods_printf("\t\t\t\t\t writes reg\n");
561                     match = true;
562                 }
563             }
564         }
565
566         // If the passed-in register is read/written...
567         if (match || !reg.isValid()) {
568             InstructionAPI::Expression::Ptr val = operands[i].getValue();
569             if (!val) break;
570
571             // Won't find an offset for an immediate
572             if (dynamic_cast<InstructionAPI::Immediate*>(val.get())) {
573                 continue;
574             }
575
576             // Won't find an offset for a registerAST.  However, we do want to
577             // record a push (e.g., callee-saved registers).
578             if (dynamic_cast<InstructionAPI::RegisterAST*>(val.get()) &&
579                 insn->getOperation().getID() != e_push) {
580                 continue;
581             }
582
583             // If we have a dereference, extract the child
584             if (dynamic_cast<InstructionAPI::Dereference*>(val.get())) {
585                 vector<InstructionAPI::InstructionAST::Ptr> children;
586                 val->getChildren(children);
587                 if (children.size() == 1) {
588                     InstructionAPI::InstructionAST::Ptr child =
589                         children.front();
590                     val = boost::dynamic_pointer_cast<InstructionAPI::
591                         Expression>(child);
592                 }
593             }
594
595             // Copied from parseAPI/src/IA_x86Details.C
596             // IA_x86Details::findTableInsn()
597             zeroAllGPRegisters z(addr, func, block, insn, false);
598             val->apply(&z);
599             if (z.isDefined()) {
600                 // At this point, z.getResult() contains the exact stack height
601                 // being accessed.
602                 zeroAllGPRegisters z2(addr, func, block, insn, true);
603                 val->apply(&z2);
604
605                 isOffsetSet = true;
606                 offset = z.getResult();
607
608                 if (z2.isDefined()) {
609                     // At this point, z2.getResult() contains the difference
610                     // between the stack height being accessed and the height of
611                     // the base register used in the address calculation.
612                     disp = z2.getResult();
613                 } else {
614                     disp = 0;
615                 }
616
617                 stackmods_printf("\t\t\t\t found offset %ld, disp = %ld, "
618                     "type = %d\n", offset, disp, type);
619             }
620         }
621     }
622
623     std::stringstream msg;
624     if (isOffsetSet) {
625         ret = new StackAccess();
626         ret->setRegHeight(height);
627         ret->setReg(reg);
628         ret->setType(type);
629         ret->setDisp(disp);
630
631         if (ret->disp() != 0 && arch == Arch_x86) {
632             // Fix the signed issue
633             signed long fixedOffset;
634             Offset MAX = 0xffffffff;
635             if (disp > (long)MAX/2) {
636                 fixedOffset = -1*(MAX - disp + 1);
637                 disp = fixedOffset;
638                 ret->setDisp(disp);
639             }
640         }
641
642         ret->setReadHeight(StackAnalysis::Height(offset));
643
644         // Stackanalysis is reporting the heights at the start of the
645         // instruction, not the end; for push, we want to record the final
646         // state, which is where the value is actually stored
647         if (insn->getOperation().getID() == e_push) {
648             long width;
649             if (arch == Arch_x86) width = 4;
650             else width = 8;
651             ret->setRegHeight(ret->regHeight() - width);
652             ret->setReadHeight(ret->readHeight() - width);
653             ret->setType(StackAccess::SAVED);
654         }
655     }
656
657     return isOffsetSet;
658 }
659