parseAPI/src/IA_IAPI.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 #include "dyntypes.h"
  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 "IA_platformDetails.h"
  41
  42 #include <deque>
  43 #include <map>
  44
  45 using namespace Dyninst;
  46 using namespace InstructionAPI;
  47 using namespace Dyninst::InsnAdapter;
  48 using namespace Dyninst::ParseAPI;
  49
  50 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::framePtr;
  51 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::stackPtr;
  52 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::thePC;
  53
  54 void IA_IAPI::initASTs()
  55 {
  56     if(framePtr.empty())
  57     {
  58         framePtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86)));
  59         framePtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86_64)));
  60         framePtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc32)));
  61         framePtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc64)));
  62     }
  63     if(stackPtr.empty())
  64     {
  65         stackPtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86)));
  66         stackPtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86_64)));
  67         stackPtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc32)));
  68         stackPtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc64)));
  69     }
  70     if(thePC.empty())
  71     {
  72         thePC[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86)));
  73         thePC[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86_64)));
  74         thePC[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc32)));
  75         thePC[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc64)));
  76     }
  77 }
  78
  79 IA_IAPI::IA_IAPI(InstructionDecoder dec_,
  80         Address where_,
  81         CodeObject * o,
  82         CodeRegion * r,
  83         InstructionSource *isrc) :
  84     InstructionAdapter(where_, o, r, isrc),
  85     dec(dec_),
  86     validCFT(false),
  87     cachedCFT(0),
  88     validLinkerStubState(false)
  89 {
  90     hascftstatus.first = false;
  91     tailCall.first = false;
  92     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
  93     initASTs();
  94 }
  95
  96 void IA_IAPI::advance()
  97 {
  98     if(!curInsn()) {
  99         parsing_printf("..... WARNING: failed to advance InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
 100                        allInsns.size());
 101         return;
 102     }
 103     InstructionAdapter::advance();
 104     current += curInsn()->size();
 105     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
 106     if(!curInsn())
 107     {
 108         parsing_printf("......WARNING: after advance at 0x%lx, curInsn() NULL\n", current);
 109     }
 110     validCFT = false;
 111     validLinkerStubState = false;
 112     hascftstatus.first = false;
 113     tailCall.first = false;
 114 }
 115
 116 void IA_IAPI::retreat()
 117 {
 118     if(!curInsn()) {
 119         parsing_printf("..... WARNING: failed to retreat InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
 120                        allInsns.size());
 121         return;
 122     }
 123     InstructionAdapter::retreat();
 124     std::map<Address,Instruction::Ptr>::iterator remove = curInsnIter;
 125     if(curInsnIter != allInsns.begin()) {
 126         --curInsnIter;
 127         allInsns.erase(remove);
 128         current = curInsnIter->first;
 129         if(curInsnIter != allInsns.begin()) {
 130             std::map<Address,Instruction::Ptr>::iterator pit = curInsnIter;
 131             --pit;
 132             previous = curInsnIter->first;
 133         } else {
 134             previous = -1;
 135         }
 136     } else {
 137         parsing_printf("..... WARNING: cowardly refusal to retreat past first instruction at 0x%lx\n", current);
 138     }
 139
 140     /* blind duplication -- nate */
 141     validCFT = false;
 142     validLinkerStubState = false;
 143     hascftstatus.first = false;
 144     tailCall.first = false;
 145 }
 146
 147
 148
 149 size_t IA_IAPI::getSize() const
 150 {
 151     Instruction::Ptr ci = curInsn();
 152     assert(ci);
 153     return ci->size();
 154 }
 155
 156 bool IA_IAPI::hasCFT() const
 157 {
 158     if(hascftstatus.first) return hascftstatus.second;
 159     InsnCategory c = curInsn()->getCategory();
 160     hascftstatus.second = false;
 161     if(c == c_BranchInsn ||
 162        c == c_ReturnInsn)
 163     {
 164         hascftstatus.second = true;
 165     }
 166     if(c == c_CallInsn)
 167     {
 168         if(isRealCall()) {
 169             hascftstatus.second = true;
 170         }
 171         if(isDynamicCall()) {
 172             hascftstatus.second = true;
 173         }
 174         if(simulateJump()) {
 175             hascftstatus.second = true;
 176         }
 177     }
 178     hascftstatus.first = true;
 179     return hascftstatus.second;
 180 }
 181
 182 bool IA_IAPI::isAbortOrInvalidInsn() const
 183 {
 184     entryID e = curInsn()->getOperation().getID();
 185     if(e == e_No_Entry)
 186     {
 187         parsing_printf("...WARNING: un-decoded instruction at 0x%x\n", current);
 188     }
 189     return e == e_No_Entry ||
 190             e == e_int3 ||
 191             e == e_hlt;
 192 }
 193
 194 bool IA_IAPI::isFrameSetupInsn() const
 195 {
 196     return isFrameSetupInsn(curInsn());
 197 }
 198
 199 bool IA_IAPI::isDynamicCall() const
 200 {
 201     Instruction::Ptr ci = curInsn();
 202     if(ci && (ci->getCategory() == c_CallInsn))
 203     {
 204         if(getCFT() == 0)
 205         {
 206             parsing_printf("... Call 0x%lx is indirect\n", current);
 207             return true;
 208         }
 209     }
 210     return false;
 211 }
 212
 213 bool IA_IAPI::isAbsoluteCall() const
 214 {
 215     Instruction::Ptr ci = curInsn();
 216     if(ci->getCategory() == c_CallInsn)
 217     {
 218         Expression::Ptr cft = ci->getControlFlowTarget();
 219         if(cft && dyn_detail::boost::dynamic_pointer_cast<Immediate>(cft))
 220         {
 221             return true;
 222         }
 223     }
 224     return false;
 225 }
 226
 227
 228 bool IA_IAPI::isReturn() const
 229 {
 230     return curInsn()->getCategory() == c_ReturnInsn;
 231 }
 232 bool IA_IAPI::isBranch() const
 233 {
 234     return curInsn()->getCategory() == c_BranchInsn;
 235 }
 236 bool IA_IAPI::isCall() const
 237 {
 238     return curInsn()->getCategory() == c_CallInsn;
 239 }
 240
 241 bool IA_IAPI::isInterruptOrSyscall() const
 242 {
 243     return (isInterrupt() && isSyscall());
 244 }
 245
 246 bool IA_IAPI::isSyscall() const
 247 {
 248     static RegisterAST::Ptr gs(new RegisterAST(x86::gs));
 249
 250     Instruction::Ptr ci = curInsn();
 251
 252     return (((ci->getOperation().getID() == e_call) &&
 253             /*(curInsn()->getOperation().isRead(gs))) ||*/
 254             (ci->getOperand(0).format() == "16")) ||
 255             (ci->getOperation().getID() == e_syscall) ||
 256             (ci->getOperation().getID() == e_int) ||
 257             (ci->getOperation().getID() == power_op_sc));
 258 }
 259
 260
 261 bool IA_IAPI::isInterrupt() const
 262 {
 263     Instruction::Ptr ci = curInsn();
 264     return ((ci->getOperation().getID() == e_int) ||
 265             (ci->getOperation().getID() == e_int3));
 266 }
 267
 268 void IA_IAPI::getNewEdges(
 269         std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges,
 270         Function* context,
 271         Block* currBlk,
 272         unsigned int num_insns,
 273         dyn_hash_map<Address, std::string> *plt_entries) const
 274 {
 275     Instruction::Ptr ci = curInsn();
 276
 277     // Only call this on control flow instructions!
 278     if(ci->getCategory() == c_CallInsn)
 279     {
 280         Address target = getCFT();
 281         if(isRealCall() || isDynamicCall())
 282         {
 283             outEdges.push_back(std::make_pair(target, NOEDGE));
 284         }
 285         else
 286         {
 287             if(_isrc->isValidAddress(target))
 288             {
 289                 if(simulateJump())
 290                 {
 291                     parsing_printf("[%s:%u] call at 0x%lx simulated as "
 292                             "jump to 0x%lx\n",
 293                     FILE__,__LINE__,getAddr(),getCFT());
 294                     outEdges.push_back(std::make_pair(target, DIRECT));
 295                     return;
 296                 }
 297             }
 298         }
 299         outEdges.push_back(std::make_pair(getAddr() + getSize(),
 300                            CALL_FT));
 301         return;
 302     }
 303     else if(ci->getCategory() == c_BranchInsn)
 304     {
 305         Address target;
 306         if(ci->allowsFallThrough())
 307         {
 308             outEdges.push_back(std::make_pair(getCFT(),
 309                                COND_TAKEN));
 310             outEdges.push_back(std::make_pair(getNextAddr(), COND_NOT_TAKEN));
 311             return;
 312         }
 313         // Direct jump
 314         else if((target = getCFT()) != 0)
 315         {
 316             Address catchStart;
 317             if(_cr->findCatchBlock(getNextAddr(),catchStart))
 318             {
 319                 outEdges.push_back(std::make_pair(catchStart, CATCH));
 320             }
 321
 322
 323             if(!isTailCall(context,num_insns))
 324             {
 325                 if(plt_entries->find(target) == plt_entries->end())
 326                 {
 327                     outEdges.push_back(std::make_pair(target,DIRECT));
 328                 }
 329                 else
 330                 {
 331                     parsing_printf("%s[%d]: PLT tail call to %x (%s)\n",
 332                         FILE__, __LINE__, target,
 333                         (*plt_entries)[target].c_str());
 334                     outEdges.push_back(std::make_pair(target, NOEDGE));
 335                     tailCall.second = true;
 336                 }
 337             }
 338             else
 339             {
 340                 parsing_printf("%s[%d]: tail call to %x\n",
 341                     FILE__, __LINE__, target);
 342                 outEdges.push_back(std::make_pair(target, NOEDGE));
 343             }
 344             return;
 345         }
 346         else
 347         {
 348             parsing_printf("... indirect jump at 0x%x\n", current);
 349             if( num_insns == 2 ) {
 350                 parsing_printf("... uninstrumentable due to 0 size\n");
 351                 return;
 352             }
 353             if(isTailCall(context,num_insns)) {
 354                 parsing_printf("%s[%d]: indirect tail call %s at 0x%lx\n", FILE__, __LINE__,
 355                                ci->format().c_str(), current);
 356                 return;
 357             }
 358             parsing_printf("%s[%d]: jump table candidate %s at 0x%lx\n", FILE__, __LINE__,
 359                            ci->format().c_str(), current);
 360             parsedJumpTable = true;
 361             successfullyParsedJumpTable = parseJumpTable(currBlk, outEdges);
 362
 363             if(!successfullyParsedJumpTable || outEdges.empty()) {
 364                 outEdges.push_back(std::make_pair((Address)-1,INDIRECT));
 365             }
 366             return;
 367         }
 368     }
 369     else if(ci->getCategory() == c_ReturnInsn)
 370     {
 371         if(ci->allowsFallThrough())
 372         {
 373             outEdges.push_back(std::make_pair(getNextAddr(), FALLTHROUGH));
 374             return;
 375         }
 376         return;
 377     }
 378     fprintf(stderr, "Unhandled instruction %s\n", ci->format().c_str());
 379     assert(0);
 380 }
 381
 382 bool IA_IAPI::isIPRelativeBranch() const
 383 {
 384             // These don't exist on IA32...
 385 #if !defined(arch_x86_64)
 386     return false;
 387 #endif
 388     Instruction::Ptr ci = curInsn();
 389
 390     if(ci->getCategory() == c_BranchInsn &&
 391         !getCFT())
 392 {
 393     Expression::Ptr cft = ci->getControlFlowTarget();
 394     if(cft->isUsed(thePC[_isrc->getArch()]))
 395     {
 396         parsing_printf("\tIP-relative indirect jump to %s at 0x%lx\n",
 397                        cft->format().c_str(), current);
 398         return true;
 399     }
 400 }
 401     return false;
 402
 403 }
 404
 405 Instruction::Ptr IA_IAPI::curInsn() const
 406 {
 407     return curInsnIter->second;
 408 }
 409
 410 bool IA_IAPI::isLeave() const
 411 {
 412     Instruction::Ptr ci = curInsn();
 413     return ci && (ci->getOperation().getID() == e_leave);
 414 }
 415
 416 bool IA_IAPI::isDelaySlot() const
 417 {
 418 #if defined(arch_sparc)
 419     assert(!"Implement delay slots on SPARC!");
 420 #endif
 421     return false;
 422 }
 423
 424 Instruction::Ptr IA_IAPI::getInstruction()
 425 {
 426     return curInsn();
 427 }
 428
 429 bool IA_IAPI::isRealCall() const
 430 {
 431     if(getCFT() == getNextAddr())
 432     {
 433         parsing_printf("... getting PC\n");
 434         return false;
 435     }
 436     if(!_isrc->isValidAddress(getCFT()))
 437     {
 438         CodeSource *_csrc = dynamic_cast<CodeSource *>(_isrc);
 439         if (!_csrc ||
 440              _csrc->linkage().find(getCFT()) == _csrc->linkage().end()) {
 441             parsing_printf(" isRealCall failed _isrc->isValidAddress(%lx)\n",
 442                            getCFT());
 443             return false;
 444         }
 445     }
 446     if(isThunk()) {
 447         return false;
 448     }
 449     return true;
 450 }
 451
 452 std::map<Address, bool> IA_IAPI::thunkAtTarget;
 453
 454 bool IA_IAPI::isConditional() const
 455 {
 456     return curInsn()->allowsFallThrough();
 457 }
 458
 459 bool IA_IAPI::simulateJump() const
 460 {
 461     // obfuscated programs simulate jumps by calling into a block that
 462     // discards the return address from the stack, we check for these
 463     // fake calls in malware mode
 464     if (_obj->defensiveMode()) {
 465         return isFakeCall();
 466     }
 467     // TODO: we don't simulate jumps on x86 architectures; add logic as we need it.
 468     return false;
 469 }
 470
 471 Address IA_IAPI::getCFT() const
 472 {
 473     if(validCFT) return cachedCFT;
 474     Expression::Ptr callTarget = curInsn()->getControlFlowTarget();
 475         // FIXME: templated bind(),dammit!
 476     callTarget->bind(thePC[_isrc->getArch()].get(), Result(s64, current));
 477     parsing_printf("%s[%d]: binding PC %s in %s to 0x%x...", FILE__, __LINE__,
 478                    thePC[_isrc->getArch()]->format().c_str(), curInsn()->format().c_str(), current);
 479     Result actualTarget = callTarget->eval();
 480     if(actualTarget.defined)
 481     {
 482         cachedCFT = actualTarget.convert<Address>();
 483         parsing_printf("SUCCESS (CFT=0x%x)\n", cachedCFT);
 484     }
 485     else
 486     {
 487         cachedCFT = 0;
 488         parsing_printf("FAIL (CFT=0x%x), callTarget exp: %s\n",
 489                        cachedCFT,callTarget->format().c_str());
 490     }
 491     validCFT = true;
 492
 493     if(isLinkerStub()) {
 494         parsing_printf("Linker stub detected: Correcting CFT.  (CFT=0x%x)\n",
 495                        cachedCFT);
 496     }
 497
 498     return cachedCFT;
 499 }
 500
 501 bool IA_IAPI::isRelocatable(InstrumentableLevel lvl) const
 502 {
 503     Instruction::Ptr ci = curInsn();
 504     if(ci && (ci->getCategory() == c_CallInsn))
 505     {
 506         if(!isDynamicCall())
 507         {
 508             if(!_isrc->isValidAddress(getCFT()))
 509             {
 510                 parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
 511                                getCFT());
 512                 return false;
 513             }
 514         }
 515     }
 516     if(lvl == HAS_BR_INDIR)
 517     {
 518         return false;
 519     }
 520     return true;
 521 }
 522
 523 bool IA_IAPI::parseJumpTable(Dyninst::ParseAPI::Block* currBlk,
 524                     std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) const
 525 {
 526     IA_platformDetails* jumpTableParser = makePlatformDetails(_isrc->getArch(), this);
 527     bool ret = jumpTableParser->parseJumpTable(currBlk, outEdges);
 528     delete jumpTableParser;
 529     return ret;
 530 }
 531
 532
 533
 534 InstrumentableLevel IA_IAPI::getInstLevel(Function * context, unsigned int num_insns) const
 535 {
 536     InstrumentableLevel ret = InstructionAdapter::getInstLevel(context, num_insns);
 537 /*    if(ret == HAS_BR_INDIR && isIPRelativeBranch())
 538     {
 539         return NORMAL;
 540 }*/
 541     return ret;
 542 }