Merge branch 'master' into NewInstpoint
[dyninst.git] / parseAPI / src / IA_x86.C
1 /*
2  * Copyright (c) 1996-2009 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     if(tailCall.first) {
176         parsing_printf("\tReturning cached tail call check result: %d\n", tailCall.second);
177         return tailCall.second;
178     }
179     tailCall.first = true;
180
181     bool valid; Address addr;
182     boost::tie(valid, addr) = getCFT();
183     if(curInsn()->getCategory() == c_BranchInsn &&
184        valid &&
185        _obj->findFuncByEntry(_cr,addr))
186     {
187        parsing_printf("\tjump to 0x%lx, TAIL CALL\n", addr);
188         tailCall.second = true;
189         return tailCall.second;
190     }
191
192     if(allInsns.size() < 2) {
193         tailCall.second = false;
194         parsing_printf("\ttoo few insns to detect tail call\n");
195         return tailCall.second;
196     }
197
198     if(curInsn()->getCategory() == c_BranchInsn ||
199        curInsn()->getCategory() == c_CallInsn)
200     {
201         //std::map<Address, Instruction::Ptr>::const_iterator prevIter =
202                 //allInsns.find(current);
203         allInsns_t::const_iterator prevIter = curInsnIter;
204         --prevIter;
205         Instruction::Ptr prevInsn = prevIter->second;
206         if(prevInsn->getOperation().getID() == e_leave)
207         {
208             parsing_printf("\tprev insn was leave, TAIL CALL\n");
209             tailCall.second = true;
210             return tailCall.second;
211         }
212         if(prevInsn->getOperation().getID() == e_pop)
213         {
214             if(prevInsn->isWritten(framePtr[_isrc->getArch()]))
215             {
216                 parsing_printf("\tprev insn was %s, TAIL CALL\n", prevInsn->format().c_str());
217                 tailCall.second = true;
218                 return tailCall.second;
219             }
220             parsing_printf("\tprev insn was %s, not tail call\n", prevInsn->format().c_str());
221         }
222     }
223     tailCall.second = false;
224     return tailCall.second;
225 }
226
227 bool IA_IAPI::savesFP() const
228 {
229     Instruction::Ptr ci = curInsn();
230     if(ci->getOperation().getID() == e_push)
231     {
232         return(ci->isRead(framePtr[_isrc->getArch()]));
233     }
234     return false;
235 }
236
237 bool IA_IAPI::isStackFramePreamble() const
238 {
239     if(savesFP())
240     {
241         InstructionDecoder tmp(dec);
242         std::vector<Instruction::Ptr> nextTwoInsns;
243         nextTwoInsns.push_back(tmp.decode());
244         nextTwoInsns.push_back(tmp.decode());
245         if(isFrameSetupInsn(nextTwoInsns[0]) ||
246            isFrameSetupInsn(nextTwoInsns[1]))
247         {
248             return true;
249         }
250     }
251     return false;
252 }
253
254 bool IA_IAPI::cleansStack() const
255 {
256     Instruction::Ptr ci = curInsn();
257     return (ci->getCategory() == c_ReturnInsn) &&
258             ci->getOperand(0).getValue();
259
260 }
261
262 bool IA_IAPI::isReturn(Dyninst::ParseAPI::Function * /*context*/, 
263                         Dyninst::ParseAPI::Block* /*currBlk*/) const
264 {
265     // For x86, we check if an instruction is return based on the category. 
266     // However, for powerpc, the return instruction BLR can be a return or
267     // an indirect jump used for jump tables etc. Hence, we need to function and block
268     // to determine if an instruction is a return. But these parameters are unused for x86. 
269     return curInsn()->getCategory() == c_ReturnInsn;
270 }
271
272 bool IA_IAPI::isReturnAddrSave(Dyninst::Address&) const
273 {
274     // not implemented on non-power
275     return false;
276 }
277
278 bool IA_IAPI::sliceReturn(ParseAPI::Block* /*bit*/, Address /*ret_addr*/, ParseAPI::Function * /*func*/) const {
279    return true;
280 }
281
282 //class ST_Predicates : public Slicer::Predicates {};
283
284
285 /* returns true if the call leads to:
286  * -an invalid instruction (or immediately branches/calls to an invalid insn)
287  * -a block not ending in a return instruction that pops the return address 
288  *  off of the stack
289  */
290 bool IA_IAPI::isFakeCall() const
291 {
292     assert(_obj->defensiveMode());
293
294     if (isDynamicCall()) {
295         return false;
296     }
297
298     // get func entry
299     bool tampers = false;
300     bool valid; Address entry;
301     boost::tie(valid, entry) = getCFT();
302
303     if (!valid) return false;
304
305     if (! _cr->contains(entry) ) {
306        return false;
307     }
308
309     if ( ! _isrc->isCode(entry) ) {
310         mal_printf("WARNING: found function call at %lx "
311                    "to invalid address %lx %s[%d]\n", current, 
312                    entry, FILE__,__LINE__);
313         return false;
314     }
315
316     // get instruction at func entry
317     const unsigned char* bufPtr =
318      (const unsigned char *)(_cr->getPtrToInstruction(entry));
319     Offset entryOff = entry - _cr->offset();
320     InstructionDecoder newdec( bufPtr,
321                               _cr->length() - entryOff,
322                               _cr->getArch() );
323     IA_IAPI *ah = new IA_IAPI(newdec, entry, _obj, _cr, _isrc, _curBlk);
324     Instruction::Ptr insn = ah->curInsn();
325
326     // follow ctrl transfers until you get a block containing non-ctrl 
327     // transfer instructions, or hit a return instruction
328     while (insn->getCategory() == c_CallInsn ||
329            insn->getCategory() == c_BranchInsn) 
330     {
331        boost::tie(valid, entry) = ah->getCFT();
332        if ( !valid || ! _cr->contains(entry) || ! _isrc->isCode(entry) ) {
333           mal_printf("WARNING: found call to function at %lx that "
334                      "leaves to %lx, out of the code region %s[%d]\n", 
335                      current, entry, FILE__,__LINE__);
336           return false;
337        }
338         bufPtr = (const unsigned char *)(_cr->getPtrToInstruction(entry));
339         entryOff = entry - _cr->offset();
340         delete(ah);
341         newdec = InstructionDecoder(bufPtr, 
342                                     _cr->length() - entryOff, 
343                                     _cr->getArch());
344         ah = new IA_IAPI(newdec, entry, _obj, _cr, _isrc, _curBlk);
345         insn = ah->curInsn();
346     }
347
348     // calculate instruction stack deltas for the block, leaving the iterator
349     // at the last ins'n if it's a control transfer, or after calculating the 
350     // last instruction's delta if we run off the end of initialized memory
351     int stackDelta = 0;
352     int addrWidth = _isrc->getAddressWidth();
353     static Expression::Ptr theStackPtr
354         (new RegisterAST(MachRegister::getStackPointer(_isrc->getArch())));
355     Address curAddr = entry;
356
357     while(true) {
358
359         // exit condition 1
360         if (insn->getCategory() == c_CallInsn ||
361             insn->getCategory() == c_ReturnInsn ||
362             insn->getCategory() == c_BranchInsn) 
363         {
364             break;
365         }
366
367         // calculate instruction delta
368         if(insn->isWritten(theStackPtr)) {
369             entryID what = insn->getOperation().getID();
370             int sign = 1;
371             switch(what) 
372             {
373             case e_push:
374                 sign = -1;
375             case e_pop: {
376                 int size = insn->getOperand(0).getValue()->size();
377                 stackDelta += sign * size;
378                 break;
379             }
380             case e_pusha:
381             case e_pushad:
382                 sign = -1;
383             case e_popa:
384             case e_popad:
385                 if (1 == sign) {
386                     mal_printf("popad ins'n at %lx in func at %lx changes sp "
387                                "by %d. %s[%d]\n", ah->getAddr(), 
388                                entry, 8 * sign * addrWidth, FILE__, __LINE__);
389                 }
390                 stackDelta += sign * 8 * addrWidth;
391                 break;
392             case e_pushf:
393             case e_pushfd:
394                 sign = -1;
395             case e_popf:
396             case e_popfd:
397                 stackDelta += sign * 4;
398                 if (1 == sign) {
399                     mal_printf("popf ins'n at %lx in func at %lx changes sp "
400                                "by %d. %s[%d]\n", ah->getAddr(), entry, 
401                                sign * 4, FILE__, __LINE__);
402                 }
403                 break;
404             case e_enter:
405                 //mal_printf("Saw enter instruction at %lx in isFakeCall, "
406                 //           "quitting early, assuming not fake "
407                 //           "%s[%d]\n",curAddr, FILE__,__LINE__);
408                 //KEVIN: unhandled case, but not essential for correct analysis
409                 delete ah;
410                 return false;
411                 break;
412             case e_leave:
413                 mal_printf("WARNING: saw leave instruction "
414                            "at %lx that is not handled by isFakeCall %s[%d]\n",
415                            curAddr, FILE__,__LINE__);
416                 //KEVIN: unhandled, not essential for correct analysis, would
417                 // be a red flag if there wasn't an enter ins'n first and 
418                 // we didn't end in a return instruction
419                 break;
420                         case e_and:
421                                 // Rounding off the stack pointer. 
422                                 mal_printf("WARNING: saw and instruction at %lx that is not handled by isFakeCall %s[%d]\n",
423                                         curAddr, FILE__, __LINE__);
424                                 delete ah;
425                                 return false;
426                                 break;
427
428             case e_sub:
429                 sign = -1;
430             case e_add: {
431                 Operand arg = insn->getOperand(1);
432                 Result delta = arg.getValue()->eval();
433                 if(delta.defined) {
434                     int delta_int = sign;
435                     switch (delta.type) {
436                     case u8:
437                     case s8:
438                         delta_int *= (int)delta.convert<char>();
439                         break;
440                     case u16:
441                     case s16:
442                         delta_int *= (int)delta.convert<short>();
443                         break;
444                     case u32:
445                     case s32:
446                         delta_int *= delta.convert<int>();
447                         break;
448                     default:
449                         assert(0 && "got add/sub operand of unusual size");
450                         break;
451                     }
452                     stackDelta += delta_int;
453                 } else if (sign == -1) {
454                     delete ah;
455                     return false;
456                 } else {
457                     mal_printf("ERROR: in isFakeCall, add ins'n "
458                                "at %lx (in first block of function at "
459                                "%lx) modifies the sp but failed to evaluate "
460                                "its arguments %s[%d]\n", 
461                                ah->getAddr(), entry, FILE__, __LINE__);
462                     delete ah;
463                     return true;
464                 }
465                 break;
466             }
467             default: {
468                 //KEVINTODO: remove this assert
469                 fprintf(stderr,"WARNING: in isFakeCall non-push/pop "
470                         "ins'n at %lx (in first block of function at "
471                         "%lx) modifies the sp by an unknown amount. "
472                         "%s[%d]\n", ah->getAddr(), entry, 
473                         FILE__, __LINE__);
474                 assert(0); // what stack-altering instruction is this?
475                 break;
476             } // end default block
477             } // end switch
478         }
479
480         if (stackDelta > 0) {
481             tampers=true;
482         }
483
484         // exit condition 2
485         ah->advance();
486         Instruction::Ptr next = ah->curInsn();
487         if (NULL == next) {
488             break;
489         }
490         curAddr += insn->size();
491         insn = next;
492     } 
493
494     // not a fake call if it ends w/ a return instruction
495     if (insn->getCategory() == c_ReturnInsn) {
496         delete ah;
497         return false;
498     }
499
500     // if the stack delta is positive or the return address has been replaced
501     // with an absolute value, it's a fake call, since in both cases 
502     // the return address is gone and we cannot return to the caller
503     if ( 0 < stackDelta || tampers ) {
504
505         delete ah;
506         return true;
507     }
508
509     delete ah;
510     return false;
511 }
512
513 const char* IA_IAPI::isIATcall() const
514 {
515     if (!isDynamicCall()) {
516         return NULL;
517     }
518
519     if (!curInsn()->readsMemory()) {
520         return NULL;
521     }
522
523     std::set<Expression::Ptr> memReads;
524     curInsn()->getMemoryReadOperands(memReads);
525     if (memReads.size() != 1) {
526         return NULL;
527     }
528
529     Result memref = (*memReads.begin())->eval();
530     if (!memref.defined) {
531         return NULL;
532     }
533     Address entryAddr = memref.convert<Address>();
534
535     // convert to a relative address
536     if (_obj->cs()->loadAddress() < entryAddr) {
537         entryAddr -= _obj->cs()->loadAddress();
538     }
539     
540     if (!_obj->cs()->isValidAddress(entryAddr)) {
541         return NULL;
542     }
543
544     // calculate the address of the ASCII string pointer, 
545     // skip over the IAT entry's two-byte hint
546     void * asciiPtr = _obj->cs()->getPtrToInstruction(entryAddr);
547     if (!asciiPtr) {
548         return NULL;
549     }
550     Address funcAsciiAddr = 2 + *(Address*) asciiPtr;
551     if (!_obj->cs()->isValidAddress(funcAsciiAddr)) {
552         return NULL;
553     }
554
555     // see if it's really a string that could be a function name
556     char *funcAsciiPtr = (char*) _obj->cs()->getPtrToData(funcAsciiAddr);
557     if (!funcAsciiPtr) {
558         return NULL;
559     }
560     char cur = 'a';
561     int count=0;
562     do {
563         cur = funcAsciiPtr[count];
564         count++;
565     }while (count < 100 && 
566             _obj->cs()->isValidAddress(funcAsciiAddr+count) &&
567             ((cur >= 'A' && cur <= 'z') ||
568              (cur >= '0' && cur <= '9')));
569     if (cur != 0 || count <= 1) 
570         return NULL;
571
572     mal_printf("found IAT call at %lx to %s\n", current, funcAsciiPtr);
573     return funcAsciiPtr;
574 }
575
576 bool IA_IAPI::isNopJump() const
577 {
578     InsnCategory cat = curInsn()->getCategory();
579     if (c_BranchInsn != cat) {
580         return false;
581     }
582     bool valid; Address addr;
583     boost::tie(valid, addr) = getCFT();
584     if(valid && current+1 == addr) {
585         return true;
586     }
587     return false;
588 }
589
590 bool IA_IAPI::isLinkerStub() const
591 {
592     // No need for linker stubs on x86 platforms.
593     return false;
594 }