x86 fix
[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
41 #include <deque>
42
43 using namespace Dyninst;
44 using namespace InstructionAPI;
45 using namespace Dyninst::InsnAdapter;
46 using namespace Dyninst::ParseAPI;
47
48
49 bool IA_IAPI::isFrameSetupInsn(Instruction::Ptr i) const
50 {
51     if(i->getOperation().getID() == e_mov)
52     {
53         if(i->readsMemory() || i->writesMemory())
54         {
55             parsing_printf("%s[%d]: discarding insn %s as stack frame preamble, not a reg-reg move\n",
56                            FILE__, __LINE__, i->format().c_str());
57             //return false;
58         }
59         if(i->isRead(stackPtr[_isrc->getArch()]) &&
60            i->isWritten(framePtr[_isrc->getArch()]))
61         {
62             if((unsigned) i->getOperand(0).getValue()->size() == _isrc->getAddressWidth())
63             {
64                 return true;
65             }
66             else
67             {
68                 parsing_printf("%s[%d]: discarding insn %s as stack frame preamble, size mismatch for %d-byte addr width\n",
69                                FILE__, __LINE__, i->format().c_str(), _isrc->getAddressWidth());
70             }
71         }
72     }
73     return false;
74 }
75
76 bool IA_IAPI::isNop() const
77 {
78     Instruction::Ptr ci = curInsn();
79
80     // TODO: add LEA no-ops
81     assert(ci);
82     if(ci->getOperation().getID() == e_nop)
83         return true;
84     if(ci->getOperation().getID() == e_lea)
85     {
86         std::set<Expression::Ptr> memReadAddr;
87         ci->getMemoryReadOperands(memReadAddr);
88         std::set<RegisterAST::Ptr> writtenRegs;
89         ci->getWriteSet(writtenRegs);
90         
91         if(memReadAddr.size() == 1 && writtenRegs.size() == 1)
92         {
93             if(**(memReadAddr.begin()) == **(writtenRegs.begin()))
94             {
95                 return true;
96             }
97             // TODO: check for zero displacement--do we want to bind here?
98         }
99     }
100     return false;
101 }
102
103 /*
104  * A `thunk' is a function composed of the following pair of instructions:
105  
106  thunk:
107     mov (%esp), <some register>
108     ret
109  
110  * It has the effect of putting the address following a call to `thunk' into
111  * the register, and is used in position independent code.
112  */
113 namespace {
114     class ThunkVisitor : public InstructionAPI::Visitor {
115      public:
116         ThunkVisitor() : offset_(0) { }
117         virtual void visit(BinaryFunction *) {
118             return;
119         }
120         virtual void visit(Immediate *i) {
121             offset_ = i->eval().convert<Address>();
122         }
123         virtual void visit(RegisterAST*) {
124             return;
125         }
126         virtual void visit(Dereference*) {
127             return;
128         }
129         Address offset() const { return offset_; }
130
131      private:
132         Address offset_;
133     };
134 }
135 bool IA_IAPI::isThunk() const {
136     if (!_isrc->isValidAddress(getCFT()))
137     {
138         parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
139                        getCFT());
140         return false;
141     }
142
143     const unsigned char *target =
144             (const unsigned char *)_isrc->getPtrToInstruction(getCFT());
145     InstructionDecoder targetChecker(target,
146             2*InstructionDecoder::maxInstructionLength, _isrc->getArch());
147     Instruction::Ptr thunkFirst = targetChecker.decode();
148     Instruction::Ptr thunkSecond = targetChecker.decode();
149     if(thunkFirst && thunkSecond && 
150         (thunkFirst->getOperation().getID() == e_mov) &&
151         (thunkSecond->getCategory() == c_ReturnInsn))
152     {
153         if(thunkFirst->isRead(stackPtr[_isrc->getArch()]))
154         {
155             // it is not enough that the stack pointer is read; it must
156             // be a zero-offset read from the stack pointer
157             ThunkVisitor tv;
158             Operand op = thunkFirst->getOperand(1);
159             op.getValue()->apply(&tv); 
160     
161             return tv.offset() == 0; 
162         }
163     }
164     return false;
165 }
166
167 bool IA_IAPI::isTailCall(Function * /*context*/,unsigned int) const
168 {
169     if(tailCall.first) {
170         parsing_printf("\tReturning cached tail call check result: %d\n", tailCall.second);
171         return tailCall.second;
172     }
173     tailCall.first = true;
174
175     if(curInsn()->getCategory() == c_BranchInsn &&
176        _obj->findFuncByEntry(_cr,getCFT()))
177     {
178         parsing_printf("\tjump to 0x%lx, TAIL CALL\n", getCFT());
179         tailCall.second = true;
180         return tailCall.second;
181     }
182
183     if(allInsns.size() < 2) {
184         tailCall.second = false;
185         parsing_printf("\ttoo few insns to detect tail call\n");
186         return tailCall.second;
187     }
188
189     if(curInsn()->getCategory() == c_BranchInsn ||
190        curInsn()->getCategory() == c_CallInsn)
191     {
192         std::map<Address, Instruction::Ptr>::const_iterator prevIter =
193                 allInsns.find(current);
194         --prevIter;
195         Instruction::Ptr prevInsn = prevIter->second;
196         if(prevInsn->getOperation().getID() == e_leave)
197         {
198             parsing_printf("\tprev insn was leave, TAIL CALL\n");
199             tailCall.second = true;
200             return tailCall.second;
201         }
202         if(prevInsn->getOperation().getID() == e_pop)
203         {
204             if(prevInsn->isWritten(framePtr[_isrc->getArch()]))
205             {
206                 parsing_printf("\tprev insn was %s, TAIL CALL\n", prevInsn->format().c_str());
207                 tailCall.second = true;
208                 return tailCall.second;
209             }
210             parsing_printf("\tprev insn was %s, not tail call\n", prevInsn->format().c_str());
211         }
212     }
213     tailCall.second = false;
214     return tailCall.second;
215 }
216
217 bool IA_IAPI::savesFP() const
218 {
219     Instruction::Ptr ci = curInsn();
220     if(ci->getOperation().getID() == e_push)
221     {
222         return(ci->isRead(framePtr[_isrc->getArch()]));
223     }
224     return false;
225 }
226
227 bool IA_IAPI::isStackFramePreamble() const
228 {
229     if(savesFP())
230     {
231         InstructionDecoder tmp(dec);
232         std::vector<Instruction::Ptr> nextTwoInsns;
233         nextTwoInsns.push_back(tmp.decode());
234         nextTwoInsns.push_back(tmp.decode());
235         if(isFrameSetupInsn(nextTwoInsns[0]) ||
236            isFrameSetupInsn(nextTwoInsns[1]))
237         {
238             return true;
239         }
240     }
241     return false;
242 }
243
244 bool IA_IAPI::cleansStack() const
245 {
246     Instruction::Ptr ci = curInsn();
247     return (ci->getCategory() == c_ReturnInsn) &&
248             ci->getOperand(0).getValue();
249
250 }
251
252 bool IA_IAPI::isReturn(Dyninst::ParseAPI::Function * /*context*/, 
253                         Dyninst::ParseAPI::Block* /*currBlk*/) const
254 {
255     // For x86, we check if an instruction is return based on the category. 
256     // However, for powerpc, the return instruction BLR can be a return or
257     // an indirect jump used for jump tables etc. Hence, we need to function and block
258     // to determine if an instruction is a return. But these parameters are unused for x86. 
259     return curInsn()->getCategory() == c_ReturnInsn;
260 }
261
262 bool IA_IAPI::isReturnAddrSave(Dyninst::Address&) const
263 {
264     // not implemented on non-power
265     return false;
266 }
267
268 bool IA_IAPI::isReturnInst(Dyninst::ParseAPI::Function* /*context*/, Dyninst::ParseAPI::Block* /*currBlk*/) const{
269     return curInsn()->getCategory() == c_ReturnInsn;
270 }
271
272 bool IA_IAPI::sliceReturn(ParseAPI::Block* /*bit*/, Address /*ret_addr*/, ParseAPI::Function * /*func*/) const {
273         return true;
274 }
275
276 //class ST_Predicates : public Slicer::Predicates {};
277
278 // returns stackTamper, which is false if parsing should not resume 
279 // after call instructions to this function.  
280 // The function recommends parsing at an alternative address if the stack 
281 // delta is a known absolute or relative value, otherwise we will instrument
282 // this function's return instructions to see if the function returns
283 StackTamper IA_IAPI::tampersStack(ParseAPI::Function *, 
284                                   Address &) const
285 {
286     return TAMPER_NONE;
287
288 #if 0
289
290     using namespace DataflowAPI;
291     if (TAMPER_UNSET != func->stackTamper()) {
292         return func->stackTamper();
293     }
294
295     if ( ! _obj->defensiveMode() ) { 
296         return TAMPER_NONE;
297     }
298
299     Function::blocklist & retblks = func->returnBlocks();
300     if ( retblks.begin() == retblks.end() ) {
301         return TAMPER_NONE;
302     }
303
304     AssignmentConverter converter(true);
305     vector<Assignment::Ptr> assgns;
306     ST_Predicates preds;
307     StackTamper tamper = TAMPER_UNSET;
308     //Absloc stkLoc (MachRegister::getStackPointer(_isrc->getArch()));
309     Function::blocklist::iterator bit;
310     for (bit = retblks.begin(); retblks.end() != bit; bit++) {
311         Address retnAddr = (*bit)->lastInsnAddr();
312         InstructionDecoder retdec( _isrc->getPtrToInstruction( retnAddr ), 
313                                   InstructionDecoder::maxInstructionLength, 
314                                   _cr->getArch() );
315         Instruction::Ptr retn = retdec.decode();
316         converter.convert(retn, retnAddr, func, assgns);
317         vector<Assignment::Ptr>::iterator ait;
318         AST::Ptr sliceAtRet;
319
320         for (ait = assgns.begin(); assgns.end() != ait; ait++) {
321             AbsRegion & outReg = (*ait)->out();
322             if ( outReg.absloc().isPC() ) {
323                 Slicer slicer(*ait,*bit,func);
324                 Graph::Ptr slGraph = slicer.backwardSlice(preds);
325                 SymEval::Result_t slRes;
326                 SymEval::expand(slGraph,slRes);
327                 if (dyn_debug_malware) {
328                     stringstream graphDump;
329                     graphDump << "sliceDump_" << func->name() 
330                               << "_" << retnAddr << ".dot";
331                     slGraph->printDOT(graphDump.str());
332                 }
333                 sliceAtRet = slRes[*ait];
334                 break;
335             }
336         }
337         assert(sliceAtRet != NULL);
338         StackTamperVisitor vis((*ait)->out());
339         tamper = vis.tampersStack(sliceAtRet, tamperAddr);
340         assgns.clear();
341     }
342     return tamper;
343 #endif
344 }
345
346 /* returns true if the call leads to:
347  * -an invalid instruction (or immediately branches/calls to an invalid insn)
348  * -a block not ending in a return instruction that pops the return address 
349  *  off of the stack
350  */
351 bool IA_IAPI::isFakeCall() const
352 {
353     assert(_obj->defensiveMode());
354
355     // get instruction at entry of new func
356     bool tampers = false;
357     Address entry = getCFT();
358     if ( ! _cr->contains(entry) || ! _isrc->isCode(entry) ) {
359         mal_printf("WARNING: found call to function at %lx that "
360                 "redirects to invalid address %lx %s[%d]\n", current, 
361                 entry, FILE__,__LINE__);
362         return false;
363     }
364     const unsigned char* bufPtr =
365      (const unsigned char *)(_isrc->getPtrToInstruction(entry));
366     InstructionDecoder newdec( bufPtr,
367                               _isrc->offset() + _isrc->length() - entry,
368                               _cr->getArch() );
369     IA_IAPI ah(newdec, entry, _obj, _cr, _isrc, _curBlk);
370     Instruction::Ptr insn = ah.curInsn();
371
372     // follow ctrl transfers until you get a block containing non-ctrl 
373     // transfer instructions, or hit a return instruction
374     while (insn->getCategory() == c_CallInsn ||
375            insn->getCategory() == c_BranchInsn) 
376     {
377         Address entry = ah.getCFT();
378         if ( ! _cr->contains(entry) || ! _isrc->isCode(entry) ) {
379             mal_printf("WARNING: found call to function at %lx that "
380                     "redirects to invalid address %lx %s[%d]\n", current, 
381                     entry, FILE__,__LINE__);
382             return false;
383         }
384         bufPtr = (const unsigned char *)(_isrc->getPtrToInstruction(entry));
385         newdec = InstructionDecoder(bufPtr, 
386                                     _isrc->offset() + _isrc->length() - entry, 
387                                     _cr->getArch());
388         ah = IA_IAPI(newdec, entry, _obj, _cr, _isrc, _curBlk);
389         insn = ah.curInsn();
390     }
391
392     // calculate instruction stack deltas for the block, leaving the iterator
393     // at the last ins'n if it's a control transfer, or after calculating the 
394     // last instruction's delta if we run off the end of initialized memory
395     int stackDelta = 0;
396     int addrWidth = _isrc->getAddressWidth();
397     static Expression::Ptr theStackPtr
398         (new RegisterAST(MachRegister::getStackPointer(_isrc->getArch())));
399     Address curAddr = entry;
400
401     while(true) {
402
403         // exit condition 1
404         if (insn->getCategory() == c_CallInsn ||
405             insn->getCategory() == c_ReturnInsn ||
406             insn->getCategory() == c_BranchInsn) 
407         {
408             break;
409         }
410
411         // calculate instruction delta
412         if(insn->isWritten(theStackPtr)) {
413             entryID what = insn->getOperation().getID();
414             int sign = 1;
415             switch(what) 
416             {
417             case e_push:
418                 sign = -1;
419             case e_pop: {
420                 Operand arg = insn->getOperand(0);
421                 if (arg.getValue()->eval().defined) {
422                     stackDelta += sign * addrWidth;
423                 } else {
424                     assert(0);
425                 }
426                 break;
427             }
428             case e_pusha:
429             case e_pushad:
430                 sign = -1;
431             case e_popa:
432             case e_popad:
433                 stackDelta += sign * 8 * addrWidth;
434                 break;
435
436             case e_pushf:
437             case e_pushfd:
438                 sign = -1;
439             case e_popf:
440             case e_popfd:
441                 stackDelta += sign * 4;
442                 break;
443
444             case e_leave:
445             case e_enter:
446                 fprintf(stderr, "WARNING: saw leave or enter instruction "
447                         "at %lx that is not handled by isFakeCall %s[%d]\n",
448                         curAddr, FILE__,__LINE__);//KEVINTODO: unhandled case
449             default:
450                 assert(0);//what stack-writing instruction is this?
451             }
452         }
453
454         if (stackDelta > 0) {
455             tampers=true;
456         }
457
458         // exit condition 2
459         ah.advance();
460         Instruction::Ptr next = ah.curInsn();
461         if (NULL == next) {
462             break;
463         }
464         curAddr += insn->size();
465         insn = next;
466     } 
467
468     // not a fake call if it ends w/ a return instruction
469     if (insn->getCategory() == c_ReturnInsn) {
470         return false;
471     }
472
473     // if the stack delta is positive or the return address has been replaced
474     // with an absolute value, it's a fake call, since in both cases 
475     // the return address is gone and we cannot return to the caller
476     if ( 0 < stackDelta || tampers ) {
477         return true;
478     }
479
480     return tampers;
481 }
482
483 bool IA_IAPI::isIATcall() const
484 {
485     if (!isDynamicCall()) {
486         return false;
487     }
488
489     if (!curInsn()->readsMemory()) {
490         return false;
491     }
492
493     std::set<Expression::Ptr> memReads;
494     curInsn()->getMemoryReadOperands(memReads);
495     if (memReads.size() != 1) {
496         return false;
497     }
498
499     Result memref = (*memReads.begin())->eval();
500     if (!memref.defined) {
501         return false;
502     }
503     Address entryAddr = memref.convert<Address>();
504
505     // convert to a relative address
506     if (_obj->cs()->loadAddress() < entryAddr) {
507         entryAddr -= _obj->cs()->loadAddress();
508     }
509     
510     if (!_obj->cs()->isValidAddress(entryAddr)) {
511         return false;
512     }
513
514     // calculate the address of the ASCII string pointer, 
515     // skip over the IAT entry's two-byte hint
516     Address funcAsciiAddr = 2 + *(Address*) (_obj->cs()->getPtrToData(entryAddr));
517     if (!_obj->cs()->isValidAddress(funcAsciiAddr)) {
518         return false;
519     }
520
521     // see if it's really a string that could be a function name
522     char *funcAsciiPtr = (char*) _obj->cs()->getPtrToData(funcAsciiAddr);
523     char cur = 'a';
524     int count=0;
525     do {
526         cur = funcAsciiPtr[count];
527         count++;
528     }while (count < 100 && 
529             _obj->cs()->isValidAddress(funcAsciiAddr+count) &&
530             ((cur >= 'A' && cur <= 'z') ||
531              (cur >= '0' && cur <= '9')));
532     if (cur != 0 || count <= 1) 
533         return false;
534
535     return true;
536 }
537
538 bool IA_IAPI::isLinkerStub() const
539 {
540     // No need for linker stubs on x86 platforms.
541     return false;
542 }