Collected Windows fixes
[dyninst.git] / parseAPI / src / IA_x86.C
1 /*
2  * Copyright (c) 1996-2011 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32
33 #include "IA_IAPI.h"
34
35 #include "Register.h"
36 #include "Dereference.h"
37 #include "Immediate.h"
38 #include "BinaryFunction.h"
39 #include "debug_parse.h"
40 #include "dataflowAPI/h/slicing.h"
41 #include "dataflowAPI/h/SymEval.h"
42 //#include "StackTamperVisitor.h"
43
44 #include <deque>
45
46 using namespace Dyninst;
47 using namespace InstructionAPI;
48 using namespace Dyninst::InsnAdapter;
49 using namespace Dyninst::ParseAPI;
50
51
52 bool IA_IAPI::isFrameSetupInsn(Instruction::Ptr i) const
53 {
54     if(i->getOperation().getID() == e_mov)
55     {
56         if(i->readsMemory() || i->writesMemory())
57         {
58             parsing_printf("%s[%d]: discarding insn %s as stack frame preamble, not a reg-reg move\n",
59                            FILE__, __LINE__, i->format().c_str());
60             //return false;
61         }
62         if(i->isRead(stackPtr[_isrc->getArch()]) &&
63            i->isWritten(framePtr[_isrc->getArch()]))
64         {
65             if((unsigned) i->getOperand(0).getValue()->size() == _isrc->getAddressWidth())
66             {
67                 return true;
68             }
69             else
70             {
71                 parsing_printf("%s[%d]: discarding insn %s as stack frame preamble, size mismatch for %d-byte addr width\n",
72                                FILE__, __LINE__, i->format().c_str(), _isrc->getAddressWidth());
73             }
74         }
75     }
76     return false;
77 }
78
79 bool IA_IAPI::isNop() const
80 {
81     Instruction::Ptr ci = curInsn();
82
83     // TODO: add LEA no-ops
84     assert(ci);
85     if(ci->getOperation().getID() == e_nop)
86         return true;
87     if(ci->getOperation().getID() == e_lea)
88     {
89         std::set<Expression::Ptr> memReadAddr;
90         ci->getMemoryReadOperands(memReadAddr);
91         std::set<RegisterAST::Ptr> writtenRegs;
92         ci->getWriteSet(writtenRegs);
93         
94         if(memReadAddr.size() == 1 && writtenRegs.size() == 1)
95         {
96             if(**(memReadAddr.begin()) == **(writtenRegs.begin()))
97             {
98                 return true;
99             }
100             // TODO: check for zero displacement--do we want to bind here?
101         }
102     }
103     return false;
104 }
105
106 /*
107  * A `thunk' is a function composed of the following pair of instructions:
108  
109  thunk:
110     mov (%esp), <some register>
111     ret
112  
113  * It has the effect of putting the address following a call to `thunk' into
114  * the register, and is used in position independent code.
115  */
116 namespace {
117     class ThunkVisitor : public InstructionAPI::Visitor {
118      public:
119         ThunkVisitor() : offset_(0) { }
120         virtual void visit(BinaryFunction *) {
121             return;
122         }
123         virtual void visit(Immediate *i) {
124             offset_ = i->eval().convert<Address>();
125         }
126         virtual void visit(RegisterAST*) {
127             return;
128         }
129         virtual void visit(Dereference*) {
130             return;
131         }
132         Address offset() const { return offset_; }
133
134      private:
135         Address offset_;
136     };
137 }
138 bool IA_IAPI::isThunk() const {
139   // Before we go a-wandering, check the target
140    bool valid; Address addr;
141    boost::tie(valid, addr) = getCFT();
142    if (!valid ||
143        !_isrc->isValidAddress(addr)) {
144         parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
145                        addr);
146         return false;
147     }
148
149     const unsigned char *target =
150        (const unsigned char *)_isrc->getPtrToInstruction(addr);
151     InstructionDecoder targetChecker(target,
152             2*InstructionDecoder::maxInstructionLength, _isrc->getArch());
153     Instruction::Ptr thunkFirst = targetChecker.decode();
154     Instruction::Ptr thunkSecond = targetChecker.decode();
155     if(thunkFirst && thunkSecond && 
156         (thunkFirst->getOperation().getID() == e_mov) &&
157         (thunkSecond->getCategory() == c_ReturnInsn))
158     {
159         if(thunkFirst->isRead(stackPtr[_isrc->getArch()]))
160         {
161             // it is not enough that the stack pointer is read; it must
162             // be a zero-offset read from the stack pointer
163             ThunkVisitor tv;
164             Operand op = thunkFirst->getOperand(1);
165             op.getValue()->apply(&tv); 
166     
167             return tv.offset() == 0; 
168         }
169     }
170     return false;
171 }
172
173 bool IA_IAPI::isTailCall(Function * context,unsigned int) const
174 {
175     
176     parsing_printf("Checking for Tail Call \n");
177     context->obj()->cs()->incrementCounter(PARSE_TAILCALL_COUNT); 
178
179     if(tailCall.first) {
180         parsing_printf("\tReturning cached tail call check result: %d\n", tailCall.second);
181         if (tailCall.second) {
182             context->obj()->cs()->incrementCounter(PARSE_TAILCALL_FAIL);
183         }
184         return tailCall.second;
185     }
186     tailCall.first = true;
187
188     bool valid; Address addr;
189     boost::tie(valid, addr) = getCFT();
190     if(curInsn()->getCategory() == c_BranchInsn &&
191        valid &&
192        _obj->findFuncByEntry(_cr,addr))
193     {
194        parsing_printf("\tjump to 0x%lx, TAIL CALL\n", addr);
195         tailCall.second = true;
196         return tailCall.second;
197     }
198
199     if(allInsns.size() < 2) {
200         tailCall.second = false;
201         parsing_printf("\ttoo few insns to detect tail call\n");
202         context->obj()->cs()->incrementCounter(PARSE_TAILCALL_FAIL);
203         return tailCall.second;
204     }
205
206     if(curInsn()->getCategory() == c_BranchInsn ||
207        curInsn()->getCategory() == c_CallInsn)
208     {
209         //std::map<Address, Instruction::Ptr>::const_iterator prevIter =
210                 //allInsns.find(current);
211         allInsns_t::const_iterator prevIter = curInsnIter;
212         --prevIter;
213         Instruction::Ptr prevInsn = prevIter->second;
214         if(prevInsn->getOperation().getID() == e_leave)
215         {
216             parsing_printf("\tprev insn was leave, TAIL CALL\n");
217             tailCall.second = true;
218             return tailCall.second;
219         }
220         if(prevInsn->getOperation().getID() == e_pop)
221         {
222             if(prevInsn->isWritten(framePtr[_isrc->getArch()]))
223             {
224                 parsing_printf("\tprev insn was %s, TAIL CALL\n", prevInsn->format().c_str());
225                 tailCall.second = true;
226                 return tailCall.second;
227             }
228             parsing_printf("\tprev insn was %s, not tail call\n", prevInsn->format().c_str());
229         }
230     }
231     tailCall.second = false;
232     context->obj()->cs()->incrementCounter(PARSE_TAILCALL_FAIL);
233     return tailCall.second;
234 }
235
236 bool IA_IAPI::savesFP() const
237 {
238     InstructionDecoder tmp(dec);
239 #if defined(os_windows)
240         const int limit = 2;
241 #else
242         const int limit = 1;
243 #endif
244         for (unsigned i = 0; i < limit; ++i) {
245                 InstructionAPI::Instruction::Ptr ci = tmp.decode();
246             if(ci->getOperation().getID() == e_push)
247                 {
248                         return(ci->isRead(framePtr[_isrc->getArch()]));
249                 }
250         }       
251         return false;
252 }
253
254 bool IA_IAPI::isStackFramePreamble() const
255 {
256     if(savesFP())
257     {
258         InstructionDecoder tmp(dec);
259         std::vector<Instruction::Ptr> nextTwoInsns;
260         nextTwoInsns.push_back(tmp.decode());
261         nextTwoInsns.push_back(tmp.decode());
262         if(isFrameSetupInsn(nextTwoInsns[0]) ||
263            isFrameSetupInsn(nextTwoInsns[1]))
264         {
265             return true;
266         }
267 #if defined(os_windows)
268                 // Windows commonly uses the following:
269                 // mov edi, edi
270                 // push ebp
271                 // mov esp, ebp
272                 // where the mov edi,edi is for runtime patching
273                 nextTwoInsns.push_back(tmp.decode());
274                 if (isFrameSetupInsn(nextTwoInsns[2])) 
275                 {
276                         return true;
277                 }
278 #endif  
279         }
280     return false;
281 }
282
283 bool IA_IAPI::cleansStack() const
284 {
285     Instruction::Ptr ci = curInsn();
286         if (ci->getCategory() != c_ReturnInsn) return false;
287     std::vector<Operand> ops;
288         ci->getOperands(ops);
289         return (ops.size() > 1);
290 }
291
292 bool IA_IAPI::isReturn(Dyninst::ParseAPI::Function * /*context*/, 
293                         Dyninst::ParseAPI::Block* /*currBlk*/) const
294 {
295     // For x86, we check if an instruction is return based on the category. 
296     // However, for powerpc, the return instruction BLR can be a return or
297     // an indirect jump used for jump tables etc. Hence, we need to function and block
298     // to determine if an instruction is a return. But these parameters are unused for x86. 
299     return curInsn()->getCategory() == c_ReturnInsn;
300 }
301
302 bool IA_IAPI::isReturnAddrSave(Dyninst::Address&) const
303 {
304     // not implemented on non-power
305     return false;
306 }
307
308 bool IA_IAPI::sliceReturn(ParseAPI::Block* /*bit*/, Address /*ret_addr*/, ParseAPI::Function * /*func*/) const {
309    return true;
310 }
311
312 //class ST_Predicates : public Slicer::Predicates {};
313
314
315 /* returns true if the call leads to:
316  * -an invalid instruction (or immediately branches/calls to an invalid insn)
317  * -a block not ending in a return instruction that pops the return address 
318  *  off of the stack
319  */
320 bool IA_IAPI::isFakeCall() const
321 {
322     assert(_obj->defensiveMode());
323
324     if (isDynamicCall()) {
325         return false;
326     }
327
328     // get func entry
329     bool tampers = false;
330     bool valid; Address entry;
331     boost::tie(valid, entry) = getCFT();
332
333     if (!valid) return false;
334
335     if (! _cr->contains(entry) ) {
336        return false;
337     }
338
339     if ( ! _isrc->isCode(entry) ) {
340         mal_printf("WARNING: found function call at %lx "
341                    "to invalid address %lx %s[%d]\n", current, 
342                    entry, FILE__,__LINE__);
343         return false;
344     }
345
346     // get instruction at func entry
347     const unsigned char* bufPtr =
348      (const unsigned char *)(_cr->getPtrToInstruction(entry));
349     Offset entryOff = entry - _cr->offset();
350     InstructionDecoder newdec( bufPtr,
351                               _cr->length() - entryOff,
352                               _cr->getArch() );
353     IA_IAPI *ah = new IA_IAPI(newdec, entry, _obj, _cr, _isrc, _curBlk);
354     Instruction::Ptr insn = ah->curInsn();
355
356     // follow ctrl transfers until you get a block containing non-ctrl 
357     // transfer instructions, or hit a return instruction
358     while (insn->getCategory() == c_CallInsn ||
359            insn->getCategory() == c_BranchInsn) 
360     {
361        boost::tie(valid, entry) = ah->getCFT();
362        if ( !valid || ! _cr->contains(entry) || ! _isrc->isCode(entry) ) {
363           mal_printf("WARNING: found call to function at %lx that "
364                      "leaves to %lx, out of the code region %s[%d]\n", 
365                      current, entry, FILE__,__LINE__);
366           return false;
367        }
368         bufPtr = (const unsigned char *)(_cr->getPtrToInstruction(entry));
369         entryOff = entry - _cr->offset();
370         delete(ah);
371         newdec = InstructionDecoder(bufPtr, 
372                                     _cr->length() - entryOff, 
373                                     _cr->getArch());
374         ah = new IA_IAPI(newdec, entry, _obj, _cr, _isrc, _curBlk);
375         insn = ah->curInsn();
376     }
377
378     // calculate instruction stack deltas for the block, leaving the iterator
379     // at the last ins'n if it's a control transfer, or after calculating the 
380     // last instruction's delta if we run off the end of initialized memory
381     int stackDelta = 0;
382     int addrWidth = _isrc->getAddressWidth();
383     static Expression::Ptr theStackPtr
384         (new RegisterAST(MachRegister::getStackPointer(_isrc->getArch())));
385     Address curAddr = entry;
386
387     while(true) {
388
389         // exit condition 1
390         if (insn->getCategory() == c_CallInsn ||
391             insn->getCategory() == c_ReturnInsn ||
392             insn->getCategory() == c_BranchInsn) 
393         {
394             break;
395         }
396
397         // calculate instruction delta
398         if(insn->isWritten(theStackPtr)) {
399             entryID what = insn->getOperation().getID();
400             int sign = 1;
401             switch(what) 
402             {
403             case e_push:
404                 sign = -1;
405             case e_pop: {
406                 int size = insn->getOperand(0).getValue()->size();
407                 stackDelta += sign * size;
408                 break;
409             }
410             case e_pusha:
411             case e_pushad:
412                 sign = -1;
413             case e_popa:
414             case e_popad:
415                 if (1 == sign) {
416                     mal_printf("popad ins'n at %lx in func at %lx changes sp "
417                                "by %d. %s[%d]\n", ah->getAddr(), 
418                                entry, 8 * sign * addrWidth, FILE__, __LINE__);
419                 }
420                 stackDelta += sign * 8 * addrWidth;
421                 break;
422             case e_pushf:
423             case e_pushfd:
424                 sign = -1;
425             case e_popf:
426             case e_popfd:
427                 stackDelta += sign * 4;
428                 if (1 == sign) {
429                     mal_printf("popf ins'n at %lx in func at %lx changes sp "
430                                "by %d. %s[%d]\n", ah->getAddr(), entry, 
431                                sign * 4, FILE__, __LINE__);
432                 }
433                 break;
434             case e_enter:
435                 //mal_printf("Saw enter instruction at %lx in isFakeCall, "
436                 //           "quitting early, assuming not fake "
437                 //           "%s[%d]\n",curAddr, FILE__,__LINE__);
438                 // unhandled case, but not essential for correct analysis
439                 delete ah;
440                 return false;
441                 break;
442             case e_leave:
443                 mal_printf("WARNING: saw leave instruction "
444                            "at %lx that is not handled by isFakeCall %s[%d]\n",
445                            curAddr, FILE__,__LINE__);
446                 // unhandled, not essential for correct analysis, would
447                 // be a red flag if there wasn't an enter ins'n first and 
448                 // we didn't end in a return instruction
449                 break;
450                         case e_and:
451                                 // Rounding off the stack pointer. 
452                                 mal_printf("WARNING: saw and instruction at %lx that is not handled by isFakeCall %s[%d]\n",
453                                         curAddr, FILE__, __LINE__);
454                                 delete ah;
455                                 return false;
456                                 break;
457
458             case e_sub:
459                 sign = -1;
460             case e_add: {
461                 Operand arg = insn->getOperand(1);
462                 Result delta = arg.getValue()->eval();
463                 if(delta.defined) {
464                     int delta_int = sign;
465                     switch (delta.type) {
466                     case u8:
467                     case s8:
468                         delta_int *= (int)delta.convert<char>();
469                         break;
470                     case u16:
471                     case s16:
472                         delta_int *= (int)delta.convert<short>();
473                         break;
474                     case u32:
475                     case s32:
476                         delta_int *= delta.convert<int>();
477                         break;
478                     default:
479                         assert(0 && "got add/sub operand of unusual size");
480                         break;
481                     }
482                     stackDelta += delta_int;
483                 } else if (sign == -1) {
484                     delete ah;
485                     return false;
486                 } else {
487                     mal_printf("ERROR: in isFakeCall, add ins'n "
488                                "at %lx (in first block of function at "
489                                "%lx) modifies the sp but failed to evaluate "
490                                "its arguments %s[%d]\n", 
491                                ah->getAddr(), entry, FILE__, __LINE__);
492                     delete ah;
493                     return true;
494                 }
495                 break;
496             }
497             default: {
498                 fprintf(stderr,"WARNING: in isFakeCall non-push/pop "
499                         "ins'n at %lx (in first block of function at "
500                         "%lx) modifies the sp by an unknown amount. "
501                         "%s[%d]\n", ah->getAddr(), entry, 
502                         FILE__, __LINE__);
503                 break;
504             } // end default block
505             } // end switch
506         }
507
508         if (stackDelta > 0) {
509             tampers=true;
510         }
511
512         // exit condition 2
513         ah->advance();
514         Instruction::Ptr next = ah->curInsn();
515         if (NULL == next) {
516             break;
517         }
518         curAddr += insn->size();
519         insn = next;
520     } 
521
522     // not a fake call if it ends w/ a return instruction
523     if (insn->getCategory() == c_ReturnInsn) {
524         delete ah;
525         return false;
526     }
527
528     // if the stack delta is positive or the return address has been replaced
529     // with an absolute value, it's a fake call, since in both cases 
530     // the return address is gone and we cannot return to the caller
531     if ( 0 < stackDelta || tampers ) {
532
533         delete ah;
534         return true;
535     }
536
537     delete ah;
538     return false;
539 }
540
541 bool IA_IAPI::isIATcall(std::string &calleeName) const
542 {
543     if (!isDynamicCall()) {
544         return false;
545     }
546
547     if (!curInsn()->readsMemory()) {
548         return false;
549     }
550
551     std::set<Expression::Ptr> memReads;
552     curInsn()->getMemoryReadOperands(memReads);
553     if (memReads.size() != 1) {
554         return false;
555     }
556
557     Result memref = (*memReads.begin())->eval();
558     if (!memref.defined) {
559         return false;
560     }
561     Address entryAddr = memref.convert<Address>();
562
563     // convert to a relative address
564     if (_obj->cs()->loadAddress() < entryAddr) {
565         entryAddr -= _obj->cs()->loadAddress();
566     }
567     
568     if (!_obj->cs()->isValidAddress(entryAddr)) {
569         return false;
570     }
571
572     // calculate the address of the ASCII string pointer, 
573     // skip over the IAT entry's two-byte hint
574     void * asciiPtr = _obj->cs()->getPtrToInstruction(entryAddr);
575     if (!asciiPtr) {
576         return false;
577     }
578     Address funcAsciiAddr = 2 + *(Address*) asciiPtr;
579     if (!_obj->cs()->isValidAddress(funcAsciiAddr)) {
580         return false;
581     }
582
583     // see if it's really a string that could be a function name
584     char *funcAsciiPtr = (char*) _obj->cs()->getPtrToData(funcAsciiAddr);
585     if (!funcAsciiPtr) {
586         return false;
587     }
588     char cur = 'a';
589     int count=0;
590     do {
591         cur = funcAsciiPtr[count];
592         count++;
593     }while (count < 100 && 
594             _obj->cs()->isValidAddress(funcAsciiAddr+count) &&
595             ((cur >= 'A' && cur <= 'z') ||
596              (cur >= '0' && cur <= '9')));
597     if (cur != 0 || count <= 1) 
598         return false;
599
600     mal_printf("found IAT call at %lx to %s\n", current, funcAsciiPtr);
601     calleeName = string(funcAsciiPtr);
602     return true;
603 }
604
605 bool IA_IAPI::isNopJump() const
606 {
607     InsnCategory cat = curInsn()->getCategory();
608     if (c_BranchInsn != cat) {
609         return false;
610     }
611     bool valid; Address addr;
612     boost::tie(valid, addr) = getCFT();
613     if(valid && current+1 == addr) {
614         return true;
615     }
616     return false;
617 }
618
619 bool IA_IAPI::isLinkerStub() const
620 {
621     // No need for linker stubs on x86 platforms.
622     return false;
623 }