fixing stuff
[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
43 #include <deque>
44
45 using namespace Dyninst;
46 using namespace InstructionAPI;
47 using namespace Dyninst::InsnAdapter;
48 using namespace Dyninst::ParseAPI;
49
50 class zeroAllGPRegisters : public InstructionAPI::Visitor
51 {
52     public:
53     zeroAllGPRegisters(Address ip) : defined(true), m_ip(ip) {}
54     virtual ~zeroAllGPRegisters() {}
55     bool defined;
56     std::deque<long> results;
57     Address m_ip;
58     long getResult() {
59         if(results.empty()) return 0;
60         return results.front();
61     }
62     bool isDefined() {
63         return defined && (results.size() == 1);
64     }
65     virtual void visit(BinaryFunction* b)
66     {
67         if(!defined) return;
68         long arg1 = results.back();
69         results.pop_back();
70         long arg2 = results.back();
71         results.pop_back();
72         if(b->isAdd())
73         {
74             results.push_back(arg1+arg2);
75         }
76         else if(b->isMultiply())
77         {
78             results.push_back(arg1*arg2);
79         }
80         else
81         {
82             defined = false;
83         }
84     }
85     virtual void visit(Immediate* i)
86     {
87         if(!defined) return;
88         results.push_back(i->eval().convert<long>());
89     }
90     virtual void visit(RegisterAST* r)
91     {
92         if(!defined) return;
93         if(r->getID() == x86::eip ||
94            r->getID() == x86_64::eip ||
95            r->getID() == x86_64::rip)
96         {
97             results.push_back(m_ip);
98             return;
99         }
100         results.push_back(0);
101     }
102     virtual void visit(Dereference* )
103     {
104         defined = false;
105     }
106     
107 };
108
109 bool IA_IAPI::isFrameSetupInsn(Instruction::Ptr i) const
110 {
111     if(i->getOperation().getID() == e_mov)
112     {
113         if(i->isRead(stackPtr[_isrc->getArch()]) &&
114            i->isWritten(framePtr[_isrc->getArch()]))
115         {
116             return true;
117         }
118     }
119     return false;
120 }
121
122 bool IA_IAPI::isNop() const
123 {
124     Instruction::Ptr ci = curInsn();
125
126     // TODO: add LEA no-ops
127     assert(ci);
128     if(ci->getOperation().getID() == e_nop)
129         return true;
130     if(ci->getOperation().getID() == e_lea)
131     {
132         std::set<Expression::Ptr> memReadAddr;
133         ci->getMemoryReadOperands(memReadAddr);
134         std::set<RegisterAST::Ptr> writtenRegs;
135         ci->getWriteSet(writtenRegs);
136         
137         if(memReadAddr.size() == 1 && writtenRegs.size() == 1)
138         {
139             if(**(memReadAddr.begin()) == **(writtenRegs.begin()))
140             {
141                 return true;
142             }
143             // TODO: check for zero displacement--do we want to bind here?
144         }
145     }
146     return false;
147 }
148
149 bool IA_IAPI::isMovAPSTable(std::vector<std::pair< Address, EdgeTypeEnum > >& outEdges) const
150 {
151     /**
152     * AMD-64 gcc emits a re-accuring idiom of:
153      *         jmpq   *%r8
154      *         movaps %xmm7,-0xf(%rax)
155      *         movaps %xmm6,-0x1f(%rax)
156      *         movaps %xmm5,-0x2f(%rax)
157      *         movaps %xmm4,-0x3f(%rax)
158      *         movaps %xmm3,-0x4f(%rax)
159      *         movaps %xmm2,-0x5f(%rax)
160      *         movaps %xmm1,-0x6f(%rax)
161      *         movaps %xmm0,-0x7f(%rax)
162      *         <other>
163      *
164      * The jump register is calculated in such a way that it'll be difficult
165      * for our analysis to figure it out.  Instead we'll recognize the pattern
166      * of the 'movaps'.  Note that the following instruction is also a valid jump
167      * target
168      **/
169     parsing_printf("\tChecking for movaps table at 0x%lx...\n", current);
170     std::set<Address> found;
171     const unsigned char *bufferBegin =
172             (const unsigned char *)_isrc->getPtrToInstruction(current);
173     if( bufferBegin == NULL ) {
174         parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",
175                        FILE__, __LINE__);
176         return false;
177     }
178
179     unsigned int size = (_cr->offset() + _cr->length()) - current;
180     InstructionDecoder d(bufferBegin, size, _isrc->getArch());
181     Address cur = current;
182     unsigned last_insn_size = 0;
183     InstructionAPI::Instruction::Ptr i = d.decode();
184     cur += i->size();
185     InstructionAPI::Instruction::Ptr insn;
186     while (NULL != (insn = d.decode())) {
187         //All insns in sequence are movaps
188         parsing_printf("\t\tChecking instruction %s\n", insn->format().c_str());
189         if (insn->getOperation().getID() != e_movapd &&
190             insn->getOperation().getID() != e_movaps)
191         {
192             break;
193         }
194         //All insns are same size
195         if (last_insn_size == 0)
196             last_insn_size = insn->size();
197         else if (last_insn_size != insn->size())
198             break;
199
200         found.insert(cur);
201
202         cur += insn->size();
203     }
204     if (found.size() == 8) {
205         found.insert(cur);
206         //It's a match
207         for (std::set<Address>::iterator i=found.begin(); i != found.end(); i++) {
208             outEdges.push_back(std::make_pair(*i, INDIRECT));
209         }
210         parsing_printf("\tfound\n");
211         return true;
212     }
213     parsing_printf("\tnot found (%d insns)\n", found.size());
214     return false;
215 }
216
217 bool IA_IAPI::isTableInsn(Instruction::Ptr i) const
218 {
219     if(i->getOperation().getID() == e_mov && i->readsMemory() && !i->writesMemory())
220     {
221         return true;
222     }
223     if(i->getOperation().getID() == e_lea)
224     {
225         return true;
226     }
227     return false;
228 }
229         
230 std::map<Address, Instruction::Ptr>::const_iterator IA_IAPI::findTableInsn() const
231 {
232     // Check whether the jump is our table insn!
233     Expression::Ptr cft = curInsn()->getControlFlowTarget();
234     if(cft)
235     {
236         std::vector<InstructionAST::Ptr> tmp;
237         cft->getChildren(tmp);
238         if(tmp.size() == 1)
239         {
240             Expression::Ptr cftAddr = dyn_detail::boost::dynamic_pointer_cast<Expression>(tmp[0]);
241             zeroAllGPRegisters z(current);
242             cftAddr->apply(&z);
243             parsing_printf("\tChecking indirect jump %s for table insn\n", curInsn()->format().c_str());
244             if(z.isDefined() && z.getResult())
245             {
246                 parsing_printf("\tAddress in jump\n");
247                 return allInsns.find(current);
248             }
249         }
250     }
251     else {
252       parsing_cerr << "\t Current insn " << curInsn()->format() << " has no CFT!" << endl;
253     }
254     std::map<Address, Instruction::Ptr>::const_iterator c =
255             allInsns.find(current);
256     while(!isTableInsn(c->second) && c != allInsns.begin())
257     {
258         --c;
259     }
260     if(isTableInsn(c->second))
261     {
262         return c;
263     }
264     return allInsns.end();
265 }
266         
267 // This should only be called on a known indirect branch...
268 bool IA_IAPI::parseJumpTable(Block* currBlk,
269     std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges) const
270 {
271     if(isIPRelativeBranch())
272     {
273         return false;
274     }
275
276     if(isMovAPSTable(outEdges))
277     {
278         return true;
279     }
280     bool foundJCCAlongTaken = false;
281     Instruction::Ptr tableInsn;
282     Address tableInsnAddr;
283     std::map<Address, Instruction::Ptr>::const_iterator tableLoc = findTableInsn();
284     if(tableLoc == allInsns.end())
285     {
286         parsing_printf("\tunable to find table insn\n");
287         return false;
288     }
289     tableInsnAddr = tableLoc->first;
290     tableInsn = tableLoc->second;
291     Instruction::Ptr maxSwitchInsn, branchInsn;
292     boost::tie(maxSwitchInsn, branchInsn, foundJCCAlongTaken) = findMaxSwitchInsn(currBlk);
293     if(!maxSwitchInsn || !branchInsn)
294     {
295         parsing_printf("\tunable to fix max switch size\n");
296         return false;
297     }
298     Address thunkOffset;
299     Address thunkInsnAddr;
300     boost::tie(thunkInsnAddr, thunkOffset) = findThunkAndOffset(currBlk);
301     if(thunkInsnAddr != 0)
302     {
303         std::map<Address, Instruction::Ptr>::const_iterator thunkLoc =
304                 allInsns.find(thunkInsnAddr);
305         if(thunkLoc != allInsns.end())
306         {
307             tableLoc = thunkLoc;
308             tableInsnAddr = thunkInsnAddr;
309             tableInsn = thunkLoc->second;
310         }
311     }
312     parsing_printf("\ttableInsn %s at 0x%lx\n",tableInsn->format().c_str(), tableInsnAddr);
313     if(thunkOffset) {
314         parsing_printf("\tThunk-calculated table base address: 0x%lx\n",
315                        thunkOffset);
316     }
317     unsigned tableSize = 0, tableStride = 0;
318     bool ok = computeTableBounds(maxSwitchInsn, branchInsn, tableInsn, foundJCCAlongTaken,
319                                  tableSize, tableStride);
320     if(!ok)
321     {
322         return false;
323     }
324     std::map<Address, Instruction::Ptr>::const_iterator cur = allInsns.find(current);
325     
326     while(tableLoc != cur)
327     {
328         tableLoc++;
329         if(tableLoc->second->getOperation().getID() == e_lea)
330         {
331             parsing_printf("\tchecking instruction %s at 0x%lx for IP-relative LEA\n", tableLoc->second->format().c_str(),
332                            tableLoc->first);
333             Expression::Ptr IPRelAddr = tableLoc->second->getOperand(1).getValue();
334             IPRelAddr->bind(thePC[_isrc->getArch()].get(), Result(s64, tableLoc->first + tableLoc->second->size()));
335             Result iprel = IPRelAddr->eval();
336             if(iprel.defined)
337             {
338                 parsing_printf("\trevising tableInsn to %s at 0x%lx\n",tableLoc->second->format().c_str(), tableLoc->first);
339                 tableInsn = tableLoc->second;
340                 tableInsnAddr = tableLoc->first;
341             }
342
343         }
344         else
345         {
346             parsing_printf("\tChecking for sign-extending mov at 0x%lx...\n", tableLoc->first);
347             if(tableLoc->second->getOperation().getID() == e_movsxd ||
348                tableLoc->second->getOperation().getID() == e_movsx)
349             {
350                 std::set<Expression::Ptr> movsxReadAddr;
351                 tableLoc->second->getMemoryReadOperands(movsxReadAddr);
352
353                 if(movsxReadAddr.empty()) {
354                     // should be a register-register movsx[d]
355                     // from either 16- or 32-bit source operand
356                     Expression::Ptr op1 = 
357                         tableLoc->second->getOperand(0).getValue(); 
358                     Expression::Ptr op2 = 
359                         tableLoc->second->getOperand(1).getValue();
360             
361                     if(op1 && op2) {
362                         int sz1 = op1->eval().size();
363                         int sz2 = op2->eval().size();
364                         parsing_printf("\t\tfound %d-byte to %d-byte move, revised stride to %d\n",
365                         
366                             sz2,sz1,sz2);
367                         tableStride = sz2;
368                     }
369                 }
370
371                 static Immediate::Ptr four(new Immediate(Result(u8, 4)));
372                 static Expression::Ptr dummy4(new DummyExpr());
373                 static Expression::Ptr dummy2(new DummyExpr());
374                 static Immediate::Ptr two(new Immediate(Result(u8, 2)));
375                 static BinaryFunction::funcT::Ptr multiplier(new BinaryFunction::multResult());
376                 static BinaryFunction::Ptr scaleCheck4(new BinaryFunction(four, dummy4, (tableStride == 8) ? u64: u32,
377                         multiplier));
378                 static BinaryFunction::Ptr scaleCheck2(new BinaryFunction(two, dummy2, (tableStride == 8) ? u64: u32,
379                         multiplier));
380                 for(std::set<Expression::Ptr>::const_iterator readExp =
381                     movsxReadAddr.begin();
382                     readExp != movsxReadAddr.end();
383                     ++readExp)
384                 {
385                     if((*readExp)->isUsed(scaleCheck4))
386                     {
387                         parsing_printf("\tFound sign-extending mov, revising table stride to scale (4)\n");
388                         tableStride = 4;
389                     }
390                     else if((*readExp)->isUsed(scaleCheck2))
391                     {
392                         parsing_printf("\tFound sign-extending mov, revising table stride to scale (2)\n");
393                         tableStride = 2;
394                     }
395                     else
396                     {
397                         parsing_printf("\tFound sign-extending mov insn %s, readExp %s\n",
398                                        tableLoc->second->format().c_str(), (*readExp)->format().c_str());
399                         parsing_printf("\tcouldn't match stride expression %s or %s--HELP!\n",
400                                        scaleCheck2->format().c_str(), scaleCheck4->format().c_str());
401                     }
402                 }
403                 break;
404             }
405         }
406     }
407     Address tableBase = getTableAddress(tableInsn, tableInsnAddr, thunkOffset);
408     return fillTableEntries(thunkOffset, tableBase,
409                             tableSize, tableStride, outEdges);
410 }
411 namespace detail
412 {
413     bool isNonCallEdge(ParseAPI::Edge* e)
414     {
415         return e->type() != CALL;
416     }
417     bool leadsToVisitedBlock(ParseAPI::Edge* e, const std::set<Block*>& visited)
418     {
419         Block* src = e->src();
420         return visited.find(src) != visited.end();
421     }
422 };
423
424
425 Address IA_IAPI::findThunkInBlock(Block* curBlock, Address& thunkOffset) const
426 {
427     const unsigned char* buf =
428             (const unsigned char*)(_isrc->getPtrToInstruction(curBlock->start()));
429     if( buf == NULL ) {
430         parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",
431                        FILE__, __LINE__);
432         return false;
433     }
434     
435     InstructionDecoder dec(buf,curBlock->size() + InstructionDecoder::maxInstructionLength,
436                            _isrc->getArch());
437     IA_IAPI * blockptr = NULL;
438     blockptr = new IA_IAPI(dec,curBlock->start(),_obj,_cr,_isrc);
439     IA_IAPI & block = *blockptr;
440
441     parsing_printf("\tchecking block at 0x%lx for thunk\n", curBlock->start());
442     while(block.getAddr() < curBlock->end())
443     {
444         if(block.getInstruction()->getCategory() == c_CallInsn)
445         {
446             parsing_printf("\tchecking call at 0x%lx for thunk\n", block.getAddr());
447             if(!block.isRealCall())
448             {
449                 parsing_printf("\tthunk found at 0x%lx, checking for add\n", block.getAddr());
450                 block.advance();
451                 thunkOffset = block.getAddr();
452                 Instruction::Ptr addInsn = block.getInstruction();
453                 if(addInsn)
454                     parsing_printf("\tinsn after thunk: %s\n", addInsn->format().c_str());
455                 else
456                     parsing_printf("\tNO INSN after thunk at 0x%lx\n", thunkOffset);
457                 if(addInsn && (addInsn->getOperation().getID() == e_add))
458                 {
459                     Result imm = addInsn->getOperand(1).getValue()->eval();
460                     Result imm2 = addInsn->getOperand(0).getValue()->eval();
461                     if(imm.defined)
462                     {
463                         Address thunkDiff = imm.convert<Address>();
464                         parsing_printf("\tsetting thunkOffset to 0x%lx (0x%lx + 0x%lx)\n",
465                                        thunkOffset+thunkDiff, thunkOffset, thunkDiff);
466                         Address ret = block.getPrevAddr();
467                         thunkOffset = thunkOffset + thunkDiff;
468                         delete blockptr;
469                         return ret;
470                     }
471                     else if(imm2.defined)
472                     {
473                         Address thunkDiff = imm2.convert<Address>();
474                         parsing_printf("\tsetting thunkOffset to 0x%lx (0x%lx + 0x%lx)\n",
475                                        thunkOffset+thunkDiff, thunkOffset, thunkDiff);
476                         Address ret = block.getPrevAddr();
477                         thunkOffset = thunkOffset + thunkDiff;
478                         delete blockptr;
479                         return ret;
480                     }
481                     else
482                     {
483                         parsing_printf("\tadd insn %s found following thunk at 0x%lx, couldn't bind operands!\n",
484                                        addInsn->format().c_str(), thunkOffset);
485                     }
486                 }
487                 thunkOffset = 0;
488             }
489         }
490         else if(block.getInstruction()->getOperation().getID() == e_lea)
491             // Look for an AMD64 IP-relative LEA.  If we find one, it should point to the start of a
492         {    // relative jump table.
493             parsing_printf("\tchecking instruction %s at 0x%lx for IP-relative LEA\n", block.getInstruction()->format().c_str(),
494                            block.getAddr());
495             Expression::Ptr IPRelAddr = block.getInstruction()->getOperand(1).getValue();
496             IPRelAddr->bind(thePC[_isrc->getArch()].get(), Result(s64, block.getNextAddr()));
497             Result iprel = IPRelAddr->eval();
498             if(iprel.defined)
499             {
500                 thunkOffset = iprel.convert<Address>();
501                 parsing_printf("\tsetting thunkOffset to 0x%lx at 0x%lx\n",thunkOffset, block.getAddr());
502                 Address ret = block.getAddr();
503                 delete blockptr;
504                 return ret;
505             }
506         }
507         block.advance();
508     }
509     delete blockptr;
510     return 0;
511 }
512
513
514 std::pair<Address, Address> IA_IAPI::findThunkAndOffset(Block* start) const
515 {
516     std::set<Block*> visited;
517     std::deque<Block*> worklist;
518     Block* curBlock;
519     worklist.insert(worklist.begin(), start);
520     visited.insert(start);
521     Address thunkOffset = 0;
522
523     // traverse only intraprocedural edges
524     Intraproc epred;
525
526     while(!worklist.empty())
527     {
528         curBlock = worklist.front();
529         worklist.pop_front();
530         // If the only thunk we can find within this function that precedes the
531         // indirect jump in control flow (we think) is after it in the address space,
532         // it may be a jump table but it's not one our heuristics should expect to
533         // handle well.  Better to bail out than try to parse something that will be garbage.
534         if(curBlock->start() > start->start()) continue;
535         Address tableInsnAddr = findThunkInBlock(curBlock, thunkOffset);
536         if(tableInsnAddr != 0)
537         {
538             return std::make_pair(tableInsnAddr, thunkOffset);
539         }
540
541         Block::edgelist::iterator sit = curBlock->sources().begin(&epred);
542         for( ; sit != curBlock->sources().end(); ++sit) {
543             ParseAPI::Edge *e = *sit;
544
545             // FIXME debugging assert
546             assert(detail::isNonCallEdge(e));
547
548             // FIXME check this algorithm... O(log n) lookup in visited
549             if(!detail::leadsToVisitedBlock(e, visited))
550             {
551                 worklist.push_back(e->src());
552                 visited.insert(e->src());
553             }
554         }
555     }
556     return std::make_pair(0, 0);
557
558 }
559
560 boost::tuple<Instruction::Ptr,
561  Instruction::Ptr,
562  bool> IA_IAPI::findMaxSwitchInsn(Block *start) const
563 {
564     std::set<Block *> visited;
565     std::vector<Block *> WL;
566     Block *curBlk;
567     int depth = 0;
568
569     bool foundMaxSwitch = false;
570     bool foundCondBranch = false;
571     Address maxSwitchAddr = 0;
572
573     WL.push_back(start);
574     Instruction::Ptr compareInsn, condBranchInsn;
575     bool compareOnTakenBranch = false;
576     for(unsigned j=0;j < WL.size(); j++)
577     {
578         curBlk = WL[j];
579         visited.insert(curBlk);
580
581         foundMaxSwitch = false;
582         foundCondBranch = false;
583         const unsigned char* buf =
584                 (const unsigned char*)(_isrc->getPtrToInstruction(curBlk->start()));
585         if( buf == NULL ) {
586             parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",
587                            FILE__, __LINE__);
588             return boost::make_tuple(Instruction::Ptr(), Instruction::Ptr(), false);
589         }
590         InstructionDecoder dec(buf, curBlk->size(), _isrc->getArch());
591         Instruction::Ptr i;
592         Address curAdr = curBlk->start();
593         while(i = dec.decode())
594         {
595             if(i->getCategory() == c_CompareInsn)
596             // check for cmp
597             {
598                 parsing_printf("\tFound jmp table cmp instruction %s at 0x%lx\n",
599                                i->format().c_str(), curAdr);
600                 compareInsn = i;
601                 maxSwitchAddr = curAdr;
602                 foundMaxSwitch = true;
603             }
604             if(i->getCategory() == c_BranchInsn &&
605                i->allowsFallThrough())
606             {
607                 parsing_printf("\tFound jmp table cond br instruction %s at 0x%lx\n",
608                                i->format().c_str(), curAdr);
609                 condBranchInsn = i;
610                 foundCondBranch = true;
611
612                 Block::edgelist::iterator tit = curBlk->targets().begin();
613                 bool taken_hit = false;
614                 bool fallthrough_hit = false;
615                 for ( ; tit != curBlk->targets().end(); ++tit) {
616                     ParseAPI::Edge *t = *tit;
617                     if (t->type() == COND_TAKEN &&
618                         (visited.find(t->trg()) != visited.end()))
619                     {
620                         taken_hit = true;
621                     }
622                     if ((t->type() == COND_NOT_TAKEN ||
623                          t->type() == FALLTHROUGH) &&
624                          (visited.find(t->trg()) != visited.end()))
625                     {
626                         fallthrough_hit = true;
627                     }
628                 }
629                 parsing_printf("\tfindMaxSwitchInsn: taken_hit: %d, fallthrough_hit: %d\n", taken_hit, fallthrough_hit);
630                 compareOnTakenBranch = taken_hit && !fallthrough_hit;
631                 break;
632             }
633             curAdr += i->size();
634         }
635
636         if(foundMaxSwitch && foundCondBranch)
637             break; // done
638
639             // look further back
640         Block::edgelist::iterator sit = curBlk->sources().begin();
641         depth++;
642             // We've seen depth 2 in libc et al
643         if(depth > 2) return boost::make_tuple(Instruction::Ptr(), Instruction::Ptr(), false);
644            
645         for( ; sit != curBlk->sources().end(); ++sit) 
646         {
647             ParseAPI::Edge * s = *sit;
648
649             // ignore return edges
650             if(s->type() == RET)
651                 continue;
652
653             if(s->type() == CALL)
654                 return boost::make_tuple(Instruction::Ptr(), Instruction::Ptr(), false);
655
656             Block * src = s->src();
657             if( (visited.find( src ) == visited.end())) {
658                 WL.push_back(src);
659             }
660         }
661     }
662     WL.clear();
663     parsing_printf("\tfindMaxSwitchInsn: table on taken branch: %d, returning: %d\n", compareOnTakenBranch, foundMaxSwitch &&
664             foundCondBranch);
665     
666     return boost::make_tuple(compareInsn, condBranchInsn, compareOnTakenBranch);
667 }
668  
669 Address IA_IAPI::getTableAddress(Instruction::Ptr tableInsn, 
670     Address tableInsnAddr,
671     Address thunkOffset) const
672 {
673     // Extract displacement from table insn
674     Expression::Ptr displacementSrc;
675     if(tableInsn->getCategory() == c_BranchInsn)
676     {
677         Expression::Ptr op = tableInsn->getOperand(0).getValue();
678         std::vector<InstructionAST::Ptr> tmp;
679         op->getChildren(tmp);
680         if(tmp.empty())
681         {
682             displacementSrc = op;
683         }
684         else
685         {
686             displacementSrc = dyn_detail::boost::dynamic_pointer_cast<Expression>(tmp[0]);
687         }
688     }
689     else
690     {
691         parsing_printf("\tcracking table instruction %s\n", tableInsn->format().c_str());
692         std::vector<InstructionAST::Ptr> tmp;
693         Expression::Ptr op = tableInsn->getOperand(1).getValue();
694         if(!op)
695         {
696             parsing_printf("\ttable insn BAD! (no second operand)\n");
697             return 0;
698         }
699         if(tableInsn->getOperation().getID() != e_lea)
700         {
701             op->getChildren(tmp);
702             if(tmp.empty())
703             {
704                 parsing_printf("\ttable insn BAD! (not LEA, second operand not a deref)\n");
705                 return 0;
706             }
707             displacementSrc = dyn_detail::boost::dynamic_pointer_cast<Expression>(tmp[0]);
708         }
709         else
710         {
711             displacementSrc = op;
712         }
713     }
714     
715     zeroAllGPRegisters z(tableInsnAddr + tableInsn->size());
716     displacementSrc->apply(&z);
717     
718     Address jumpTable = 0;
719     //if(!disp.defined)
720     if(!z.isDefined())
721     {
722         if(!thunkOffset)
723         {
724             parsing_printf("\ttable insn: %s, displacement %s, bind of all GPRs FAILED\n",
725                            tableInsn->format().c_str(), displacementSrc->format().c_str());
726             return 0;
727         }
728     }
729     else
730     {
731 //        jumpTable = disp.convert<Address>();
732         jumpTable = z.getResult();
733     }
734     parsing_printf("\tjumpTable set to 0x%lx\n",jumpTable);
735
736     if(!jumpTable && !thunkOffset)
737     {
738         return 0;
739     }
740
741     // in AMD64 rip-relative LEA case, jumpTable and thunkOffset are
742     // calculated from the same instruction (FIXME this indicates
743     // a flaw in the overall logic which is corrected here)
744     if(jumpTable != thunkOffset) {
745         jumpTable += thunkOffset;
746         parsing_printf("\tjumpTable revised to 0x%lx\n",jumpTable);
747     }
748     // On Windows, all of our other addresses have had the base address
749     // of their module subtracted off before we ever use them.  We need to fix this up
750     // to conform to that standard so that Symtab actually believes that there's code
751     // at the table's destination.
752 #if defined(os_windows)
753         jumpTable -= _obj->cs()->loadAddress();
754 #endif
755     if( !_isrc->isValidAddress(jumpTable) )
756 {
757         // If the "jump table" has a start address that is outside
758         // of the valid range of the binary, we can say with high
759         // probability that we have misinterpreted some other
760         // construct (such as a function pointer comparison & tail
761         // call, for example) as a jump table. Give up now.
762     return 0;
763 }
764     return jumpTable;
765 }
766
767 bool IA_IAPI::fillTableEntries(Address thunkOffset,
768                                Address tableBase,
769                                unsigned tableSize,
770                                unsigned tableStride,
771                                std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges) const
772 {
773     if( !_isrc->isValidAddress(tableBase) )
774     {
775         parsing_printf("\ttableBase 0x%lx invalid, returning false\n", tableBase);
776         return false;
777     }
778           
779     for(unsigned int i=0; i < tableSize; i++)
780     {
781         Address tableEntry = tableBase + (i * tableStride);
782         Address jumpAddress = 0;
783                 
784         if(_isrc->isValidAddress(tableEntry))
785         {
786             if(tableStride == sizeof(Address)) {
787                                         // Unparseable jump table
788                 jumpAddress = *(const Address *)
789                     _isrc->getPtrToInstruction(tableEntry);
790                 if( 0 == jumpAddress ) {
791                     parsing_printf("%s[%d]: failed to get pointer to instruction by offset\n",
792                                    FILE__, __LINE__);
793                     return false;
794                 }
795             }
796             else {
797                 jumpAddress = *(const int *)
798                     _isrc->getPtrToInstruction(tableEntry);
799                 if( 0 == jumpAddress ) {
800                     parsing_printf("%s[%d]: failed to get pointer to "
801                         "instruction by offset\n", FILE__, __LINE__);
802                     return false;
803                 }
804             }
805         }
806 #if defined(os_windows)
807         jumpAddress -= _obj->cs()->loadAddress();
808 #endif
809         if(thunkOffset && _isrc->isCode(jumpAddress + thunkOffset))
810         {
811             // XXX We assume that if thunkOffset is set that
812             //     entries in the table are relative, but only
813             //     if the absolute address would be valid
814             jumpAddress += thunkOffset;
815         }
816         else if(!(_isrc->isCode(jumpAddress))) {
817             parsing_printf("\tentry %d [0x%lx] -> 0x%lx, invalid, skipping\n",
818                                    i, tableEntry, jumpAddress);
819                     continue;
820         }
821         parsing_printf("\tentry %d [0x%lx] -> 0x%lx\n",i,tableEntry,jumpAddress);
822                 outEdges.push_back(std::make_pair(jumpAddress, INDIRECT));
823                 
824     }
825     if(outEdges.empty()) parsing_printf("\tno valid table entries, ret false\n");
826     return !outEdges.empty();    
827 }
828
829
830 bool IA_IAPI::computeTableBounds(Instruction::Ptr maxSwitchInsn,
831                                  Instruction::Ptr branchInsn,
832                                  Instruction::Ptr tableInsn,
833                                  bool foundJCCAlongTaken,
834                                  unsigned& tableSize,
835                                  unsigned& tableStride) const
836 {
837     assert(maxSwitchInsn && branchInsn);
838     Result compareBound = maxSwitchInsn->getOperand(1).getValue()->eval();
839     if(!compareBound.defined) return false;
840     tableSize = compareBound.convert<unsigned>();
841     // Sanity check the bounds; 32k tables would be an oddity, and larger is almost certainly
842     // a misparse
843     static const unsigned int maxTableSize = 32768;
844     if(tableSize > maxTableSize)
845     {
846         parsing_printf("\tmaxSwitch of %d above %d, BAILING OUT\n", tableSize, maxTableSize);
847         return false;
848     }
849     if(foundJCCAlongTaken)
850     {
851         if(branchInsn->getOperation().getID() == e_jbe ||
852            branchInsn->getOperation().getID() == e_jle)
853         {
854             tableSize++;
855         }
856     }
857     else
858     {
859         if(branchInsn->getOperation().getID() == e_jnbe ||
860            branchInsn->getOperation().getID() == e_jnle)
861         {
862             tableSize++;
863         }
864     }
865     parsing_printf("\tmaxSwitch set to %d\n", tableSize);
866     tableStride = _isrc->getAddressWidth();
867     std::set<Expression::Ptr> tableInsnReadAddr;
868     tableInsn->getMemoryReadOperands(tableInsnReadAddr);
869     if(tableStride == 8)
870     {
871         static Immediate::Ptr four(new Immediate(Result(u8, 4)));
872         static BinaryFunction::funcT::Ptr multiplier(new BinaryFunction::multResult());
873         static Expression::Ptr dummy(new DummyExpr());
874         static BinaryFunction::Ptr scaleCheck(new BinaryFunction(four, dummy, u64, multiplier));
875         for(std::set<Expression::Ptr>::const_iterator curExpr = tableInsnReadAddr.begin();
876             curExpr != tableInsnReadAddr.end();
877             ++curExpr)
878         {
879             if((*curExpr)->isUsed(scaleCheck))
880             {
881                 tableSize = tableSize >> 1;
882                 parsing_printf("\tmaxSwitch revised to %d\n",tableSize);
883             }
884         }
885     }
886     return true;
887 }
888
889 bool IA_IAPI::isThunk() const {
890   // Before we go a-wandering, check the target
891     if (!_isrc->isValidAddress(getCFT()))
892     {
893         parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
894                        getCFT());
895         return false;
896     }
897
898     const unsigned char *target =
899             (const unsigned char *)_isrc->getPtrToInstruction(getCFT());
900   // We're decoding two instructions: possible move and possible return.
901   // Check for move from the stack pointer followed by a return.
902     InstructionDecoder targetChecker(target, 
903             2*InstructionDecoder::maxInstructionLength, _isrc->getArch());
904     Instruction::Ptr thunkFirst = targetChecker.decode();
905     Instruction::Ptr thunkSecond = targetChecker.decode();
906     parsing_printf("... checking call target for thunk, insns are %s, %s\n", thunkFirst->format().c_str(),
907                    thunkSecond->format().c_str());
908     if(thunkFirst && (thunkFirst->getOperation().getID() == e_mov))
909     {
910         if(thunkFirst->isRead(stackPtr[_isrc->getArch()]))
911         {
912             parsing_printf("... checking second insn\n");
913             if(!thunkSecond) {
914                 parsing_printf("...no second insn\n");
915                 return false;
916             }
917             if(thunkSecond->getCategory() != c_ReturnInsn)
918             {
919                 parsing_printf("...insn %s not a return\n", thunkSecond->format().c_str());
920                 return false;
921             }
922             return true;
923         }
924     }
925     parsing_printf("... real call found\n");
926     return false;
927 }
928
929 #if 0
930 // Replaced by Kevin's version in IA_IAPI.C
931 bool IA_IAPI::simulateJump() const
932 {
933   // We conclude that a call is a jump if the basic block it targets
934   // contains a pop of the return address. 
935   // 
936   // For example: 
937   // 2958:       83 ec 04                sub    $0x4,%esp
938   // 295b:       e8 00 00 00 00          call   2960 <_fini+0xc>
939   // 2960:       5b                      pop    %ebx
940   // 2961:       81 c3 ac 07 00 00       add    $0x7ac,%ebx
941   // 2967:       e8 a4 e5 ff ff          call   f10 <exit@plt+0x40>
942
943   // The first call (call 0) is considered a jump because its immediate target
944   // is a pop.
945   
946   if (!_isrc->isValidAddress(getCFT())) {
947     return false;
948   }
949
950   const unsigned char *target =
951     (const unsigned char *)_isrc->getPtrToInstruction(getCFT());
952
953   // Arbitrarily try four instructions. 
954   int maxInsns = 4;
955
956   InstructionDecoder targetChecker(target, 
957                                    maxInsns*InstructionDecoder::maxInstructionLength, _isrc->getArch());
958   bool isGetPC = false;
959   for (int i = 0; i < maxInsns; ++i) {
960     Instruction::Ptr insn = targetChecker.decode();
961     if (!insn) break;
962
963     if (insn->getOperation().getID() == e_pop) {
964       // Nifty...
965       isGetPC = true;
966       break;
967     }
968     // Any other write of the stack pointer == baaaaad
969     if (insn->isWritten(stackPtr[_isrc->getArch()])) {
970       break;
971     }
972   }
973
974   return isGetPC;
975 }
976 #endif
977
978 bool IA_IAPI::isTailCall(Function * /*context*/,unsigned int) const
979 {
980     if(tailCall.first) {
981         parsing_printf("\tReturning cached tail call check result: %d\n", tailCall.second);
982         return tailCall.second;
983     }
984     tailCall.first = true;
985
986     if(curInsn()->getCategory() == c_BranchInsn &&
987        _obj->findFuncByEntry(_cr,getCFT()))
988     {
989         parsing_printf("\tjump to 0x%lx, TAIL CALL\n", getCFT());
990         tailCall.second = true;
991         return tailCall.second;
992     }
993
994     if(allInsns.size() < 2) {
995         tailCall.second = false;
996         parsing_printf("\ttoo few insns to detect tail call\n");
997         return tailCall.second;
998     }
999
1000     if(curInsn()->getCategory() == c_BranchInsn ||
1001        curInsn()->getCategory() == c_CallInsn)
1002     {
1003         std::map<Address, Instruction::Ptr>::const_iterator prevIter =
1004                 allInsns.find(current);
1005         --prevIter;
1006         Instruction::Ptr prevInsn = prevIter->second;
1007         if(prevInsn->getOperation().getID() == e_leave)
1008         {
1009             parsing_printf("\tprev insn was leave, TAIL CALL\n");
1010             tailCall.second = true;
1011             return tailCall.second;
1012         }
1013         if(prevInsn->getOperation().getID() == e_pop)
1014         {
1015             if(prevInsn->isWritten(framePtr[_isrc->getArch()]))
1016             {
1017                 parsing_printf("\tprev insn was %s, TAIL CALL\n", prevInsn->format().c_str());
1018                 tailCall.second = true;
1019                 return tailCall.second;
1020             }
1021             parsing_printf("\tprev insn was %s, not tail call\n", prevInsn->format().c_str());
1022         }
1023     }
1024     tailCall.second = false;
1025     return tailCall.second;
1026 }
1027
1028 bool IA_IAPI::savesFP() const
1029 {
1030     Instruction::Ptr ci = curInsn();
1031     if(ci->getOperation().getID() == e_push)
1032     {
1033         return(ci->isRead(framePtr[_isrc->getArch()]));
1034     }
1035     return false;
1036 }
1037
1038 bool IA_IAPI::isStackFramePreamble() const
1039 {
1040     if(savesFP())
1041     {
1042         InstructionDecoder tmp(dec);
1043         std::vector<Instruction::Ptr> nextTwoInsns;
1044         nextTwoInsns.push_back(tmp.decode());
1045         nextTwoInsns.push_back(tmp.decode());
1046         if(isFrameSetupInsn(nextTwoInsns[0]) ||
1047            isFrameSetupInsn(nextTwoInsns[1]))
1048         {
1049             return true;
1050         }
1051     }
1052     return false;
1053 }
1054
1055 bool IA_IAPI::cleansStack() const
1056 {
1057     Instruction::Ptr ci = curInsn();
1058     return (ci->getCategory() == c_ReturnInsn) &&
1059             ci->getOperand(0).getValue();
1060
1061 }
1062
1063 bool IA_IAPI::isReturnAddrSave() const
1064 {
1065     // not implemented on non-power
1066     return false;
1067 }
1068
1069 class ST_Predicates : public Slicer::Predicates {};
1070
1071 // returns stackTamper, which is false if parsing should not resume 
1072 // after call instructions to this function.  
1073 // The function recommends parsing at an alternative address if the stack 
1074 // delta is a known absolute or relative value, otherwise we will instrument
1075 // this function's return instructions to see if the function returns
1076 StackTamper IA_IAPI::tampersStack(ParseAPI::Function *func, 
1077                                   Address &tamperAddr) const
1078 {
1079     using namespace SymbolicEvaluation;
1080     if (TAMPER_UNSET != func->stackTamper()) {
1081         return func->stackTamper();
1082     }
1083
1084     if ( ! func->obj()->defensiveMode() ) { 
1085         return TAMPER_NONE;
1086     }
1087
1088     Function::blocklist & retblks = func->returnBlocks();
1089     if ( retblks.begin() == retblks.end() ) {
1090         return TAMPER_NONE;
1091     }
1092
1093     AssignmentConverter converter(true);
1094     vector<Assignment::Ptr> assgns;
1095     ST_Predicates preds;
1096     StackTamper tamper = TAMPER_UNSET;
1097     Function::blocklist::iterator bit;
1098     for (bit = retblks.begin(); retblks.end() != bit; bit++) {
1099         Address retnAddr = (*bit)->lastInsnAddr();
1100         InstructionDecoder retdec(func->isrc()->getPtrToInstruction( retnAddr ), 
1101                                   InstructionDecoder::maxInstructionLength, 
1102                                   func->region()->getArch() );
1103         Instruction::Ptr retn = retdec.decode();
1104         converter.convert(retn, retnAddr, func, assgns);
1105         vector<Assignment::Ptr>::iterator ait;
1106         AST::Ptr sliceAtRet;
1107
1108         for (ait = assgns.begin(); assgns.end() != ait; ait++) {
1109             AbsRegion & outReg = (*ait)->out();
1110             if ( outReg.absloc().isPC() ) {
1111                 Slicer slicer(*ait,*bit,func);
1112                 Graph::Ptr slGraph = slicer.backwardSlice(preds);
1113                 DataflowAPI::Result_t slRes;
1114                 DataflowAPI::SymEval::expand(slGraph,slRes);
1115                 if (dyn_debug_malware) {
1116                     stringstream graphDump;
1117                     graphDump << "sliceDump_" << func->name() 
1118                               << "_" << retnAddr << ".dot";
1119                     slGraph->printDOT(graphDump.str());
1120                 }
1121                 sliceAtRet = slRes[*ait];
1122                 break;
1123             }
1124         }
1125         assert(sliceAtRet != NULL);
1126 #if 0
1127         StackTamperVisitor vis((*ait)->out());
1128         tamper = vis.tampersStack(sliceAtRet, tamperAddr);
1129 #endif
1130         assert(0 && "KEVINTODO: remove previous ifdef");
1131         assgns.clear();
1132     }
1133     return tamper;
1134 }
1135
1136 /* returns true if the call leads to:
1137  * -an invalid instruction (or immediately branches/calls to an invalid insn)
1138  * -a block not ending in a return instruction that pops the return address 
1139  *  off of the stack
1140  */
1141 bool IA_IAPI::isFakeCall() const
1142 {
1143     assert(_obj->defensiveMode());
1144
1145     // get instruction at entry of new func
1146     bool tampers = false;
1147     Address entry = getCFT();
1148     if ( ! _cr->contains(entry) || ! _isrc->isCode(entry) ) {
1149         mal_printf("WARNING: found call to function at %lx that "
1150                 "redirects to invalid address %lx %s[%d]\n", current, 
1151                 entry, FILE__,__LINE__);
1152         return false;
1153     }
1154     const unsigned char* bufPtr =
1155      (const unsigned char *)(_isrc->getPtrToInstruction(entry));
1156     InstructionDecoder newdec( bufPtr,
1157                               _isrc->offset() + _isrc->length() - entry,
1158                               _cr->getArch() );
1159     IA_IAPI ah(newdec, entry, _obj, _cr, _isrc);
1160     Instruction::Ptr insn = ah.curInsn();
1161
1162     // follow ctrl transfers until you get a block containing non-ctrl 
1163     // transfer instructions, or hit a return instruction
1164     while (insn->getCategory() == c_CallInsn ||
1165            insn->getCategory() == c_BranchInsn) 
1166     {
1167         Address entry = ah.getCFT();
1168         if ( ! _cr->contains(entry) || ! _isrc->isCode(entry) ) {
1169             mal_printf("WARNING: found call to function at %lx that "
1170                     "redirects to invalid address %lx %s[%d]\n", current, 
1171                     entry, FILE__,__LINE__);
1172             return false;
1173         }
1174         bufPtr = (const unsigned char *)(_isrc->getPtrToInstruction(entry));
1175         newdec = InstructionDecoder(bufPtr, 
1176                                     _isrc->offset() + _isrc->length() - entry, 
1177                                     _cr->getArch());
1178         ah = IA_IAPI(newdec, entry, _obj, _cr, _isrc);
1179         insn = ah.curInsn();
1180     }
1181
1182     // calculate instruction stack deltas for the block, leaving the iterator
1183     // at the last ins'n if it's a control transfer, or after calculating the 
1184     // last instruction's delta if we run off the end of initialized memory
1185     int stackDelta = 0;
1186     int addrWidth = _isrc->getAddressWidth();
1187     static Expression::Ptr theStackPtr
1188         (new RegisterAST(MachRegister::getStackPointer(_isrc->getArch())));
1189     Address curAddr = entry;
1190
1191     while(true) {
1192
1193         // exit condition 1
1194         if (insn->getCategory() == c_CallInsn ||
1195             insn->getCategory() == c_ReturnInsn ||
1196             insn->getCategory() == c_BranchInsn) 
1197         {
1198             break;
1199         }
1200
1201         // calculate instruction delta
1202         if(insn->isWritten(theStackPtr)) {
1203             entryID what = insn->getOperation().getID();
1204             int sign = 1;
1205             switch(what) 
1206             {
1207             case e_push:
1208                 sign = -1;
1209             case e_pop: {
1210                 Operand arg = insn->getOperand(0);
1211                 if (arg.getValue()->eval().defined) {
1212                     stackDelta += sign * addrWidth;
1213                 } else {
1214                     assert(0);
1215                 }
1216                 break;
1217             }
1218             case e_pusha:
1219             case e_pushad:
1220                 sign = -1;
1221             case e_popa:
1222             case e_popad:
1223                 stackDelta += sign * 8 * addrWidth;
1224                 break;
1225
1226             case e_pushf:
1227             case e_pushfd:
1228                 sign = -1;
1229             case e_popf:
1230             case e_popfd:
1231                 stackDelta += sign * 4;
1232                 break;
1233
1234             case e_leave:
1235             case e_enter:
1236                 fprintf(stderr, "WARNING: saw leave or enter instruction "
1237                         "at %lx that is not handled by isFakeCall %s[%d]\n",
1238                         curAddr, FILE__,__LINE__);//KEVINTODO: unhandled case
1239             default:
1240                 assert(0);//what stack-writing instruction is this?
1241             }
1242         }
1243
1244         if (stackDelta > 0) {
1245             tampers=true;
1246         }
1247
1248         // exit condition 2
1249         ah.advance();
1250         Instruction::Ptr next = ah.curInsn();
1251         if (NULL == next) {
1252             break;
1253         }
1254         curAddr += insn->size();
1255         insn = next;
1256     } 
1257
1258     // not a fake call if it ends w/ a return instruction
1259     if (insn->getCategory() == c_ReturnInsn) {
1260         return false;
1261     }
1262
1263     // if the stack delta is positive or the return address has been replaced
1264     // with an absolute value, it's a fake call, since in both cases 
1265     // the return address is gone and we cannot return to the caller
1266     if ( 0 < stackDelta || tampers ) {
1267         return true;
1268     }
1269
1270     return tampers;
1271 }
1272
1273 bool IA_IAPI::isIATcall() const
1274 {
1275     if (!isDynamicCall()) {
1276         return false;
1277     }
1278
1279     if (!curInsn()->readsMemory()) {
1280         return false;
1281     }
1282
1283     std::set<Expression::Ptr> memReads;
1284     curInsn()->getMemoryReadOperands(memReads);
1285     if (memReads.size() != 1) {
1286         return false;
1287     }
1288
1289     Result memref = (*memReads.begin())->eval();
1290     if (!memref.defined) {
1291         return false;
1292     }
1293     Address entryAddr = memref.convert<Address>();
1294
1295     // convert to a relative address
1296     if (_obj->cs()->loadAddress() < entryAddr) {
1297         entryAddr -= _obj->cs()->loadAddress();
1298     }
1299     
1300     if (!_obj->cs()->isValidAddress(entryAddr)) {
1301         return false;
1302     }
1303
1304     // calculate the address of the ASCII string pointer, 
1305     // skip over the IAT entry's two-byte hint
1306     Address funcAsciiAddr = 2 + *(Address*) (_obj->cs()->getPtrToData(entryAddr));
1307     if (!_obj->cs()->isValidAddress(funcAsciiAddr)) {
1308         return false;
1309     }
1310
1311     // see if it's really a string that could be a function name
1312     char *funcAsciiPtr = (char*) _obj->cs()->getPtrToData(funcAsciiAddr);
1313     char cur = 'a';
1314     int count=0;
1315     do {
1316         cur = funcAsciiPtr[count];
1317         count++;
1318     }while (count < 100 && 
1319             _obj->cs()->isValidAddress(funcAsciiAddr+count) &&
1320             ((cur >= 'A' && cur <= 'z') ||
1321              (cur >= '0' && cur <= '9')));
1322     if (cur != 0 || count <= 1) 
1323         return false;
1324
1325     return true;
1326 }