Fixes for non-returning functions and tail calls:
[dyninst.git] / parseAPI / src / IA_x86.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
32 #include "IA_IAPI.h"
33 #include "Register.h"
34 #include "Dereference.h"
35 #include "Immediate.h"
36 #include "BinaryFunction.h"
37 #include "debug_parse.h"
38 #include "dataflowAPI/h/slicing.h"
39 #include "dataflowAPI/h/SymEval.h"
40 //#include "StackTamperVisitor.h"
41 #include "instructionAPI/h/Visitor.h"
42
43 #include <deque>
44
45 using namespace Dyninst;
46 using namespace InstructionAPI;
47 using namespace Dyninst::InsnAdapter;
48 using namespace Dyninst::ParseAPI;
49
50
51 bool IA_IAPI::isFrameSetupInsn(Instruction::Ptr i) const
52 {
53     if(i->getOperation().getID() == e_mov)
54     {
55         if(i->readsMemory() || i->writesMemory())
56         {
57             parsing_printf("%s[%d]: discarding insn %s as stack frame preamble, not a reg-reg move\n",
58                            FILE__, __LINE__, i->format().c_str());
59             //return false;
60         }
61         if(i->isRead(stackPtr[_isrc->getArch()]) &&
62            i->isWritten(framePtr[_isrc->getArch()]))
63         {
64             if((unsigned) i->getOperand(0).getValue()->size() == _isrc->getAddressWidth())
65             {
66                 return true;
67             }
68             else
69             {
70                 parsing_printf("%s[%d]: discarding insn %s as stack frame preamble, size mismatch for %d-byte addr width\n",
71                                FILE__, __LINE__, i->format().c_str(), _isrc->getAddressWidth());
72             }
73         }
74     }
75     return false;
76 }
77
78 class nopVisitor : public InstructionAPI::Visitor
79 {
80     public:
81         nopVisitor() : foundReg(false), foundImm(false), foundBin(false), isNop(true) {}
82         virtual ~nopVisitor() {}
83
84         bool foundReg;
85         bool foundImm;
86         bool foundBin;
87         bool isNop;
88
89         virtual void visit(BinaryFunction*)
90         {
91             if (foundBin) isNop = false;
92             if (!foundImm) isNop = false;
93             if (!foundReg) isNop = false;
94             foundBin = true;
95         }
96         virtual void visit(Immediate *imm)
97         {
98             if (imm != 0) isNop = false;
99             foundImm = true;
100         }
101         virtual void visit(RegisterAST *)
102         {
103             foundReg = true;
104         }
105         virtual void visit(Dereference *)
106         {
107             isNop = false;
108         }
109 };
110
111 bool isNopInsn(Instruction::Ptr insn) 
112 {
113     // TODO: add LEA no-ops
114     if(insn->getOperation().getID() == e_nop)
115         return true;
116     if(insn->getOperation().getID() == e_lea)
117     {
118         std::set<Expression::Ptr> memReadAddr;
119         insn->getMemoryReadOperands(memReadAddr);
120         std::set<RegisterAST::Ptr> writtenRegs;
121         insn->getWriteSet(writtenRegs);
122
123         if(memReadAddr.size() == 1 && writtenRegs.size() == 1)
124         {
125             if(**(memReadAddr.begin()) == **(writtenRegs.begin()))
126             {
127                 return true;
128             }
129         }
130         // Check for zero displacement
131         nopVisitor visitor;
132
133         // We need to get the src operand
134         insn->getOperand(1).getValue()->apply(&visitor);
135         if (visitor.isNop) return true; 
136     }
137     return false;
138 }
139
140 bool IA_IAPI::isNop() const
141 {
142     Instruction::Ptr ci = curInsn();
143
144     assert(ci);
145    
146     return isNopInsn(ci);
147
148 }
149
150 /*
151  * A `thunk' is a function composed of the following pair of instructions:
152  
153  thunk:
154     mov (%esp), <some register>
155     ret
156  
157  * It has the effect of putting the address following a call to `thunk' into
158  * the register, and is used in position independent code.
159  */
160 namespace {
161     class ThunkVisitor : public InstructionAPI::Visitor {
162      public:
163         ThunkVisitor() : offset_(0) { }
164         virtual void visit(BinaryFunction *) {
165             return;
166         }
167         virtual void visit(Immediate *i) {
168             offset_ = i->eval().convert<Address>();
169         }
170         virtual void visit(RegisterAST*) {
171             return;
172         }
173         virtual void visit(Dereference*) {
174             return;
175         }
176         Address offset() const { return offset_; }
177
178      private:
179         Address offset_;
180     };
181 }
182 bool IA_IAPI::isThunk() const {
183   // Before we go a-wandering, check the target
184    bool valid; Address addr;
185    boost::tie(valid, addr) = getCFT();
186    if (!valid ||
187        !_isrc->isValidAddress(addr)) {
188         parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
189                        addr);
190         return false;
191     }
192
193     const unsigned char *target =
194        (const unsigned char *)_isrc->getPtrToInstruction(addr);
195     InstructionDecoder targetChecker(target,
196             2*InstructionDecoder::maxInstructionLength, _isrc->getArch());
197     Instruction::Ptr thunkFirst = targetChecker.decode();
198     Instruction::Ptr thunkSecond = targetChecker.decode();
199     if(thunkFirst && thunkSecond && 
200         (thunkFirst->getOperation().getID() == e_mov) &&
201         (thunkSecond->getCategory() == c_ReturnInsn))
202     {
203         if(thunkFirst->isRead(stackPtr[_isrc->getArch()]))
204         {
205             // it is not enough that the stack pointer is read; it must
206             // be a zero-offset read from the stack pointer
207             ThunkVisitor tv;
208             Operand op = thunkFirst->getOperand(1);
209             op.getValue()->apply(&tv); 
210     
211             return tv.offset() == 0; 
212         }
213     }
214     return false;
215 }
216
217 bool IA_IAPI::isTailCall(Function * context, EdgeTypeEnum type, unsigned int, const set<Address>& knownTargets) const
218 {
219    // Collapse down to "branch" or "fallthrough"
220     switch(type) {
221        case COND_TAKEN:
222        case DIRECT:
223        case INDIRECT:
224           type = DIRECT;
225           break;
226        case CALL:
227        case RET:
228        case COND_NOT_TAKEN:
229        case FALLTHROUGH:
230        case CALL_FT:
231        default:
232           return false;
233     }
234
235     parsing_printf("Checking for Tail Call \n");
236     context->obj()->cs()->incrementCounter(PARSE_TAILCALL_COUNT); 
237     if (tailCalls.find(type) != tailCalls.end()) {
238         parsing_printf("\tReturning cached tail call check result: %d\n", tailCalls[type]);
239         if (tailCalls[type]) {
240             context->obj()->cs()->incrementCounter(PARSE_TAILCALL_FAIL);
241             return true;
242         }
243         return false;
244     }
245     
246     bool valid; Address addr;
247     boost::tie(valid, addr) = getCFT();
248
249     Function* callee = _obj->findFuncByEntry(_cr, addr);
250     Block* target = _obj->findBlockByEntry(_cr, addr);
251
252     // check if addr is in a block if it is not entry.
253     if (target == NULL) {
254         std::set<Block*> blocks;
255         _obj->findCurrentBlocks(_cr, addr, blocks);
256         if (blocks.size() == 1) {
257             target = *blocks.begin();
258         }
259     }
260     
261     if(curInsn()->getCategory() == c_BranchInsn &&
262        valid &&
263        callee && 
264        callee != context &&
265        !context->contains(target)
266        )
267     {
268       parsing_printf("\tjump to 0x%lx, TAIL CALL\n", addr);
269       tailCalls[type] = true;
270       return true;
271     }
272
273     if (curInsn()->getCategory() == c_BranchInsn &&
274             valid &&
275             !callee) {
276         if (target) {
277             parsing_printf("\tjump to 0x%lx is known block, but not func entry, NOT TAIL CALL\n", addr);
278             tailCalls[type] = false;
279             return false;
280         } else if (knownTargets.find(addr) != knownTargets.end()) {
281             parsing_printf("\tjump to 0x%lx is known target in this function, NOT TAIL CALL\n", addr);
282             tailCalls[type] = false;
283             return false;
284         }
285     }
286
287     if(allInsns.size() < 2) {
288       if(context->addr() == _curBlk->start() && curInsn()->getCategory() == c_BranchInsn)
289       {
290         parsing_printf("\tjump as only insn in entry block, TAIL CALL\n");
291         tailCalls[type] = true;
292         return true;
293       }
294       else
295       {
296         parsing_printf("\ttoo few insns to detect tail call\n");
297         context->obj()->cs()->incrementCounter(PARSE_TAILCALL_FAIL);
298         tailCalls[type] = false;
299         return false;
300       }
301     }
302
303     if ((curInsn()->getCategory() == c_BranchInsn))
304     {
305         //std::map<Address, Instruction::Ptr>::const_iterator prevIter =
306                 //allInsns.find(current);
307         
308         // Updated: there may be zero or more nops between leave->jmp
309        
310         allInsns_t::const_iterator prevIter = curInsnIter;
311         --prevIter;
312         Instruction::Ptr prevInsn = prevIter->second;
313     
314         while ( isNopInsn(prevInsn) && (prevIter != allInsns.begin()) ) {
315            --prevIter;
316            prevInsn = prevIter->second;
317         }
318         ++prevIter;
319         do {
320         --prevIter;
321         prevInsn = prevIter->second;
322         if(prevInsn->getOperation().getID() == e_leave)
323         {
324            parsing_printf("\tprev insn was leave, TAIL CALL\n");
325            tailCalls[type] = true;
326            return true;
327         }
328         else if(prevInsn->getOperation().getID() == e_pop)
329         {
330             if(prevInsn->isWritten(framePtr[_isrc->getArch()]))
331             {
332                 parsing_printf("\tprev insn was %s, TAIL CALL\n", prevInsn->format().c_str());
333                 tailCalls[type] = true;
334                 return true;
335             }
336         }
337         else if(prevInsn->getOperation().getID() == e_add)
338         {
339             if(prevInsn->isWritten(stackPtr[_isrc->getArch()]))
340             {
341                 parsing_printf("\tprev insn was %s, TAIL CALL\n", prevInsn->format().c_str());
342                 tailCalls[type] = true;
343                 return true;
344             }
345             parsing_printf("\tprev insn was %s, not tail call\n", prevInsn->format().c_str());
346         }
347         } while (allInsns.begin() != prevIter);
348     }
349
350     tailCalls[type] = false;
351     context->obj()->cs()->incrementCounter(PARSE_TAILCALL_FAIL);
352     return false;
353 }
354
355 bool IA_IAPI::savesFP() const
356 {
357         std::vector<Instruction::Ptr> insns;
358         insns.push_back(curInsn());
359 #if defined(os_windows)
360         // Windows functions can start with a noop...
361         InstructionDecoder tmp(dec);
362         insns.push_back(tmp.decode());
363 #endif
364         for (unsigned i = 0; i < insns.size(); ++i) {
365                 InstructionAPI::Instruction::Ptr ci = insns[i];
366             if(ci->getOperation().getID() == e_push)
367                 {
368                         if (ci->isRead(framePtr[_isrc->getArch()])) {
369                                 return true;
370                         }
371                         else return false;
372                 }
373         }       
374         return false;
375 }
376
377 bool IA_IAPI::isStackFramePreamble() const
378 {
379 #if defined(os_windows)
380         // Windows pads with a noop
381         const int limit = 3;
382 #else 
383         const int limit = 2;
384 #endif
385         if (!savesFP()) return false;
386     InstructionDecoder tmp(dec);
387     std::vector<Instruction::Ptr> nextTwoInsns;
388     for (int i = 0; i < limit; ++i) {
389        Instruction::Ptr insn = tmp.decode();
390        if (isFrameSetupInsn(insn)) {
391           return true;
392        }
393     }
394         return false;
395 }
396
397 bool IA_IAPI::cleansStack() const
398 {
399     Instruction::Ptr ci = curInsn();
400         if (ci->getCategory() != c_ReturnInsn) return false;
401     std::vector<Operand> ops;
402         ci->getOperands(ops);
403         return (ops.size() > 1);
404 }
405
406 bool IA_IAPI::isReturn(Dyninst::ParseAPI::Function * /*context*/, 
407                         Dyninst::ParseAPI::Block* /*currBlk*/) const
408 {
409     // For x86, we check if an instruction is return based on the category. 
410     // However, for powerpc, the return instruction BLR can be a return or
411     // an indirect jump used for jump tables etc. Hence, we need to function and block
412     // to determine if an instruction is a return. But these parameters are unused for x86. 
413     return curInsn()->getCategory() == c_ReturnInsn;
414 }
415
416 bool IA_IAPI::isReturnAddrSave(Dyninst::Address&) const
417 {
418     // not implemented on non-power
419     return false;
420 }
421
422 bool IA_IAPI::sliceReturn(ParseAPI::Block* /*bit*/, Address /*ret_addr*/, ParseAPI::Function * /*func*/) const {
423    return true;
424 }
425
426 //class ST_Predicates : public Slicer::Predicates {};
427
428
429 /* returns true if the call leads to:
430  * -an invalid instruction (or immediately branches/calls to an invalid insn)
431  * -a block not ending in a return instruction that pops the return address 
432  *  off of the stack
433  */
434 bool IA_IAPI::isFakeCall() const
435 {
436     assert(_obj->defensiveMode());
437
438     if (isDynamicCall()) {
439         return false;
440     }
441
442     // get func entry
443     bool tampers = false;
444     bool valid; Address entry;
445     boost::tie(valid, entry) = getCFT();
446
447     if (!valid) return false;
448
449     if (! _cr->contains(entry) ) {
450        return false;
451     }
452
453     if ( ! _isrc->isCode(entry) ) {
454         mal_printf("WARNING: found function call at %lx "
455                    "to invalid address %lx %s[%d]\n", current, 
456                    entry, FILE__,__LINE__);
457         return false;
458     }
459
460     // get instruction at func entry
461     const unsigned char* bufPtr =
462      (const unsigned char *)(_cr->getPtrToInstruction(entry));
463     Offset entryOff = entry - _cr->offset();
464     InstructionDecoder newdec( bufPtr,
465                               _cr->length() - entryOff,
466                               _cr->getArch() );
467     IA_IAPI *ah = new IA_IAPI(newdec, entry, _obj, _cr, _isrc, _curBlk);
468     Instruction::Ptr insn = ah->curInsn();
469
470     // follow ctrl transfers until you get a block containing non-ctrl 
471     // transfer instructions, or hit a return instruction
472     while (insn->getCategory() == c_CallInsn ||
473            insn->getCategory() == c_BranchInsn) 
474     {
475        boost::tie(valid, entry) = ah->getCFT();
476        if ( !valid || ! _cr->contains(entry) || ! _isrc->isCode(entry) ) {
477           mal_printf("WARNING: found call to function at %lx that "
478                      "leaves to %lx, out of the code region %s[%d]\n", 
479                      current, entry, FILE__,__LINE__);
480           return false;
481        }
482         bufPtr = (const unsigned char *)(_cr->getPtrToInstruction(entry));
483         entryOff = entry - _cr->offset();
484         delete(ah);
485         newdec = InstructionDecoder(bufPtr, 
486                                     _cr->length() - entryOff, 
487                                     _cr->getArch());
488         ah = new IA_IAPI(newdec, entry, _obj, _cr, _isrc, _curBlk);
489         insn = ah->curInsn();
490     }
491
492     // calculate instruction stack deltas for the block, leaving the iterator
493     // at the last ins'n if it's a control transfer, or after calculating the 
494     // last instruction's delta if we run off the end of initialized memory
495     int stackDelta = 0;
496     int addrWidth = _isrc->getAddressWidth();
497     static Expression::Ptr theStackPtr
498         (new RegisterAST(MachRegister::getStackPointer(_isrc->getArch())));
499     Address curAddr = entry;
500
501     while(true) {
502
503         // exit condition 1
504         if (insn->getCategory() == c_CallInsn ||
505             insn->getCategory() == c_ReturnInsn ||
506             insn->getCategory() == c_BranchInsn) 
507         {
508             break;
509         }
510
511         // calculate instruction delta
512         if(insn->isWritten(theStackPtr)) {
513             entryID what = insn->getOperation().getID();
514             int sign = 1;
515             switch(what) 
516             {
517             case e_push:
518                 sign = -1;
519                 //FALLTHROUGH
520             case e_pop: {
521                 int size = insn->getOperand(0).getValue()->size();
522                 stackDelta += sign * size;
523                 break;
524             }
525             case e_pusha:
526             case e_pushad:
527                 sign = -1;
528                 //FALLTHROUGH
529             case e_popa:
530             case e_popad:
531                 if (1 == sign) {
532                     mal_printf("popad ins'n at %lx in func at %lx changes sp "
533                                "by %d. %s[%d]\n", ah->getAddr(), 
534                                entry, 8 * sign * addrWidth, FILE__, __LINE__);
535                 }
536                 stackDelta += sign * 8 * addrWidth;
537                 break;
538             case e_pushf:
539             case e_pushfd:
540                 sign = -1;
541                 //FALLTHROUGH
542             case e_popf:
543             case e_popfd:
544                 stackDelta += sign * 4;
545                 if (1 == sign) {
546                     mal_printf("popf ins'n at %lx in func at %lx changes sp "
547                                "by %d. %s[%d]\n", ah->getAddr(), entry, 
548                                sign * 4, FILE__, __LINE__);
549                 }
550                 break;
551             case e_enter:
552                 //mal_printf("Saw enter instruction at %lx in isFakeCall, "
553                 //           "quitting early, assuming not fake "
554                 //           "%s[%d]\n",curAddr, FILE__,__LINE__);
555                 // unhandled case, but not essential for correct analysis
556                 delete ah;
557                 return false;
558                 break;
559             case e_leave:
560                 mal_printf("WARNING: saw leave instruction "
561                            "at %lx that is not handled by isFakeCall %s[%d]\n",
562                            curAddr, FILE__,__LINE__);
563                 // unhandled, not essential for correct analysis, would
564                 // be a red flag if there wasn't an enter ins'n first and 
565                 // we didn't end in a return instruction
566                 break;
567                         case e_and:
568                                 // Rounding off the stack pointer. 
569                                 mal_printf("WARNING: saw and instruction at %lx that is not handled by isFakeCall %s[%d]\n",
570                                         curAddr, FILE__, __LINE__);
571                                 delete ah;
572                                 return false;
573                                 break;
574
575             case e_sub:
576                 sign = -1;
577                 //FALLTHROUGH
578             case e_add: {
579                 Operand arg = insn->getOperand(1);
580                 Result delta = arg.getValue()->eval();
581                 if(delta.defined) {
582                     int delta_int = sign;
583                     switch (delta.type) {
584                     case u8:
585                     case s8:
586                         delta_int *= (int)delta.convert<char>();
587                         break;
588                     case u16:
589                     case s16:
590                         delta_int *= (int)delta.convert<short>();
591                         break;
592                     case u32:
593                     case s32:
594                         delta_int *= delta.convert<int>();
595                         break;
596                     default:
597                         assert(0 && "got add/sub operand of unusual size");
598                         break;
599                     }
600                     stackDelta += delta_int;
601                 } else if (sign == -1) {
602                     delete ah;
603                     return false;
604                 } else {
605                     mal_printf("ERROR: in isFakeCall, add ins'n "
606                                "at %lx (in first block of function at "
607                                "%lx) modifies the sp but failed to evaluate "
608                                "its arguments %s[%d]\n", 
609                                ah->getAddr(), entry, FILE__, __LINE__);
610                     delete ah;
611                     return true;
612                 }
613                 break;
614             }
615             default: {
616                 fprintf(stderr,"WARNING: in isFakeCall non-push/pop "
617                         "ins'n at %lx (in first block of function at "
618                         "%lx) modifies the sp by an unknown amount. "
619                         "%s[%d]\n", ah->getAddr(), entry, 
620                         FILE__, __LINE__);
621                 break;
622             } // end default block
623             } // end switch
624         }
625
626         if (stackDelta > 0) {
627             tampers=true;
628         }
629
630         // exit condition 2
631         ah->advance();
632         Instruction::Ptr next = ah->curInsn();
633         if (NULL == next) {
634             break;
635         }
636         curAddr += insn->size();
637         insn = next;
638     } 
639
640     // not a fake call if it ends w/ a return instruction
641     if (insn->getCategory() == c_ReturnInsn) {
642         delete ah;
643         return false;
644     }
645
646     // if the stack delta is positive or the return address has been replaced
647     // with an absolute value, it's a fake call, since in both cases 
648     // the return address is gone and we cannot return to the caller
649     if ( 0 < stackDelta || tampers ) {
650
651         delete ah;
652         return true;
653     }
654
655     delete ah;
656     return false;
657 }
658
659 bool IA_IAPI::isIATcall(std::string &calleeName) const
660 {
661     if (!isDynamicCall()) {
662         return false;
663     }
664
665     if (!curInsn()->readsMemory()) {
666         return false;
667     }
668
669     std::set<Expression::Ptr> memReads;
670     curInsn()->getMemoryReadOperands(memReads);
671     if (memReads.size() != 1) {
672         return false;
673     }
674
675     Result memref = (*memReads.begin())->eval();
676     if (!memref.defined) {
677         return false;
678     }
679     Address entryAddr = memref.convert<Address>();
680
681     // convert to a relative address
682     if (_obj->cs()->loadAddress() < entryAddr) {
683         entryAddr -= _obj->cs()->loadAddress();
684     }
685     
686     if (!_obj->cs()->isValidAddress(entryAddr)) {
687         return false;
688     }
689
690     // calculate the address of the ASCII string pointer, 
691     // skip over the IAT entry's two-byte hint
692     void * asciiPtr = _obj->cs()->getPtrToInstruction(entryAddr);
693     if (!asciiPtr) {
694         return false;
695     }
696     Address funcAsciiAddr = 2 + *(Address*) asciiPtr;
697     if (!_obj->cs()->isValidAddress(funcAsciiAddr)) {
698         return false;
699     }
700
701     // see if it's really a string that could be a function name
702     char *funcAsciiPtr = (char*) _obj->cs()->getPtrToData(funcAsciiAddr);
703     if (!funcAsciiPtr) {
704         return false;
705     }
706     char cur = 'a';
707     int count=0;
708     do {
709         cur = funcAsciiPtr[count];
710         count++;
711     }while (count < 100 && 
712             _obj->cs()->isValidAddress(funcAsciiAddr+count) &&
713             ((cur >= 'A' && cur <= 'z') ||
714              (cur >= '0' && cur <= '9')));
715     if (cur != 0 || count <= 1) 
716         return false;
717
718     mal_printf("found IAT call at %lx to %s\n", current, funcAsciiPtr);
719     calleeName = string(funcAsciiPtr);
720     return true;
721 }
722
723 bool IA_IAPI::isNopJump() const
724 {
725     InsnCategory cat = curInsn()->getCategory();
726     if (c_BranchInsn != cat) {
727         return false;
728     }
729     bool valid; Address addr;
730     boost::tie(valid, addr) = getCFT();
731     if(valid && current+1 == addr) {
732         return true;
733     }
734     return false;
735 }
736
737 bool IA_IAPI::isLinkerStub() const
738 {
739     // No need for linker stubs on x86 platforms.
740     return false;
741 }