Newer
Older
/*
* SMPFunction.cpp - <see below>.
*
* Copyright (c) 2000, 2001, 2010 - University of Virginia
*
* This file is part of the Memory Error Detection System (MEDS) infrastructure.
* This file may be used and modified for non-commercial purposes as long as
* all copyright, permission, and nonwarranty notices are preserved.
* Redistribution is prohibited without prior written consent from the University
* of Virginia.
*
* Please contact the authors for restrictions applying to commercial use.
*
* THIS SOURCE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
* MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*
* Author: University of Virginia
* e-mail: jwd@virginia.com
* URL : http://www.cs.virginia.edu/
*
* Additional copyrights 2010, 2011 by Zephyr Software LLC
* e-mail: {clc,jwd}@zephyr-software.com
* URL : http://www.zephyr-software.com/
*
//
// SMPFunction.cpp
//
// This module performs the fundamental data flow analyses needed for the
// SMP project (Software Memory Protection) at the function level.
//
using namespace std;
#include <utility>
#include <list>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <pro.h>
#include <assert.h>
#include <ida.hpp>
#include <ua.hpp>
#include <idp.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <allins.hpp>
#include <intel.hpp>
#include <name.hpp>
clc5q
committed
#include <struct.hpp>
clc5q
committed
#include "SMPDBInterface.h"
#include "SMPDataFlowAnalysis.h"
#include "SMPStaticAnalyzer.h"
#include "SMPFunction.h"
#include "SMPBasicBlock.h"
#include "SMPInstr.h"
#include "SMPProgram.h"
// Set to 1 for debugging output
#define SMP_DEBUG 1
#define SMP_DEBUG2 0 // verbose
#define SMP_DEBUG3 0 // verbose
#define SMP_DEBUG_CONTROLFLOW 0 // tells what processing stage is entered
#define SMP_DEBUG_XOR 0
#define SMP_DEBUG_CHUNKS 1 // tracking down tail chunks for functions
clc5q
committed
#define SMP_DEBUG_FRAMEFIXUP 1
#define SMP_DEBUG_DATAFLOW 0
#define SMP_DEBUG_DATAFLOW_VERBOSE 0
#define SMP_DEBUG_TYPE_INFERENCE 0
#define SMP_DEBUG_STACK_GRANULARITY 0
#define SMP_DEBUG_BUILD_RTL 1 // leave this on; serious errors reported
#define SMP_DEBUG_UNINITIALIZED_SSA_NAMES 1
clc5q
committed
#define SMP_OPTIMIZE_BLOCK_PROFILING 0
#define SMP_DECLARE_INDIRECT_TARGETS_UNSAFE 1
#define SMP_ANALYZE_STACK_POINTER 0
#define SMP_AUDIT_STACK_POINTER_DELTAS 0
clc5q
committed
#define SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS 1
// Compute LVA/SSA or not? Turn it off for NICECAP demo on 31-JAN-2008
#define SMP_COMPUTE_LVA_SSA 1
// Compute fine-grained stack boundaries?
#define SMP_COMPUTE_STACK_GRANULARITY 1
// Use conditional type propagation on phi functions
#define SMP_CONDITIONAL_TYPE_PROPAGATION 0
// Kludges to fix IDA Pro 5.2 errors in cc1.ncexe
#define SMP_IDAPRO52_WORKAROUND 0
// Basic block number 0 is the top of the CFG lattice.
#define SMP_TOP_BLOCK 0
// Set SharedTailChunks to TRUE for entire printf family
// After we restructure the parent/tail structure of the database, this
// will go away.
#define KLUDGE_VFPRINTF_FAMILY 1
// Used for binary search by function number in SMPStaticAnalyzer.cpp
// to trigger debugging output and find which instruction in which
// function is causing a crash.
bool SMPBinaryDebug = false;
using namespace std;
// helper function to determine if an object is in a vector
template <class T>
clc5q
committed
bool vector_exists(const T &item, const vector<T> &vec) {
for (size_t i = 0; i < vec.size(); ++i) {
if (vec[i] == item)
return true;
}
return false;
}
// Comparison function for sorting.
bool LocalVarCompare(const LocalVar &LV1, const LocalVar &LV2) {
return (LV1.offset < LV2.offset);
}
// *****************************************************************
// Class SMPFunction
// *****************************************************************
// Constructor
SMPFunction::SMPFunction(func_t *Info, SMPProgram* pgm) {
clc5q
committed
this->Program = pgm;
this->FuncInfo = *Info;
clc5q
committed
this->FirstEA = this->FuncInfo.startEA;
clc5q
committed
this->FuncName[0] = '\0';
clc5q
committed
this->BlockCount = 0;
this->FuncProcessed = false;
clc5q
committed
this->UseFP = false;
this->StaticFunc = false;
this->LibFunc = false;
this->IndirectCalls = false;
this->UnresolvedIndirectCalls = false;
this->IndirectJumps = false;
this->UnresolvedIndirectJumps = false;
this->DirectlyRecursive = false;
this->SharedChunks = false;
clc5q
committed
this->AnalyzedSP = false;
clc5q
committed
this->STARSStackPtrAnalysisPerformed = false;
#if 1 // default to unsafe
this->SafeFunc = false;
#else // default to safe
this->SafeFunc = true;
this->SpecSafeFunc = true;
this->SafeCallee = true;
this->SpecSafeCallee = true;
#endif
this->WritesAboveRA = false;
this->HasIndirectWrites = false;
this->PossibleIndirectCallTarget = false;
this->PossibleTailCallTarget = false;
this->OutgoingArgsComputed = false;
this->GoodLocalVarTable = false;
clc5q
committed
this->TypedDefs = 0;
this->UntypedDefs = 0;
this->TypedPhiDefs = 0;
this->UntypedPhiDefs = 0;
this->SafeBlocks = 0;
this->UnsafeBlocks = 0;
this->Size = 0;
this->LocalVarsSize = 0;
this->CalleeSavedRegsSize = 0;
this->RetAddrSize = 0;
this->IncomingArgsSize = 0;
this->OutgoingArgsSize = 0;
this->LocalVarsAllocInstr = BADADDR;
this->LocalVarsDeallocInstr = BADADDR;
this->AllocPointDelta = 0;
this->MinStackDelta = 0;
this->MaxStackDelta = 0;
clc5q
committed
this->NetStackDelta = CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA;
this->PreAllocStackDelta = CALLING_CONVENTION_DEFAULT_PREFRAMEALLOC_STACK_DELTA;
this->FramePointerStackDelta = 0;
clc5q
committed
this->LocalVarOffsetLimit = 0;
this->ReturnAddrStatus = FUNC_UNKNOWN;
this->SetIsSpeculative(false);
this->Blocks.clear();
this->DirectCallTargets.clear();
this->IndirectCallTargets.clear();
this->AllCallTargets.clear();
clc5q
committed
this->AllCallSources.clear();
this->InstBlockMap.clear();
this->RPOBlocks.clear();
this->IDom.clear();
this->DomTree.clear();
this->BlocksDefinedIn.clear();
this->SSACounter.clear();
this->SSAStack.clear();
this->LocalVarTable.clear();
this->StackFrameMap.clear();
this->FineGrainedStackTable.clear();
clc5q
committed
this->SavedRegLoc.clear();
this->ReturnRegTypes.clear();
clc5q
committed
this->LiveInSet.clear();
this->LiveOutSet.clear();
this->KillSet.clear();
this->GlobalDefAddrBySSA.clear();
for (int RegIndex = R_ax; RegIndex <= R_di; ++RegIndex) {
this->SavedRegLoc.push_back(0); // zero offset means reg not saved
this->ReturnRegTypes.push_back(UNINIT);
}
// The sizes of the three regions of the stack frame other than the
// return address are stored in the function structure.
this->LocalVarsSize = this->FuncInfo.frsize;
this->CalleeSavedRegsSize = this->FuncInfo.frregs;
this->IncomingArgsSize = this->FuncInfo.argsize;
// The return address size can be obtained in a machine independent
// way by calling get_frame_retsize().
this->RetAddrSize = get_frame_retsize(this->GetFuncInfo());
} // end of SMPFunction() constructor
SMPFunction::~SMPFunction() {
list<SMPInstr *>::iterator InstIter;
for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
delete CurrInst;
}
list<SMPBasicBlock *>::iterator BlockIter;
for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
SMPBasicBlock *CurrBlock = (*BlockIter);
delete CurrBlock;
}
clc5q
committed
// Get a non-stale pointer to the func_t info for the current function.
func_t *SMPFunction::GetFuncInfo(void) {
clc5q
committed
func_t *myPtr = SMP_get_func(this->FirstEA);
clc5q
committed
assert(NULL != myPtr);
return myPtr;
}
// Reset the Processed flags in all blocks to false.
void SMPFunction::ResetProcessedBlocks(void) {
list<SMPBasicBlock *>::iterator CurrBlock;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
(*CurrBlock)->SetProcessed(false);
}
return;
} // end of SMPFunction::ResetProcessedBlocks()
clc5q
committed
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
// Return an iterator for the beginning of the LiveInSet.
set<op_t, LessOp>::iterator SMPFunction::GetFirstLiveIn(void) {
return this->LiveInSet.begin();
} // end of SMPBasicBlock::GetFirstLiveIn()
// Get termination iterator marker for the LiveIn set, for use by predecessors.
set<op_t, LessOp>::iterator SMPFunction::GetLastLiveIn(void) {
return this->LiveInSet.end();
}
// Get iterator for the start of the LiveOut set.
set<op_t, LessOp>::iterator SMPFunction::GetFirstLiveOut(void) {
return this->LiveOutSet.begin();
}
// Get termination iterator marker for the LiveOut set.
set<op_t, LessOp>::iterator SMPFunction::GetLastLiveOut(void) {
return this->LiveOutSet.end();
}
// Get iterator for the start of the VarKill set.
set<op_t, LessOp>::iterator SMPFunction::GetFirstVarKill(void) {
return this->KillSet.begin();
}
// Get termination iterator marker for the VarKill set.
set<op_t, LessOp>::iterator SMPFunction::GetLastVarKill(void) {
return this->KillSet.end();
}
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
// Four methods to get values from the maps of global reg/SSA to FG info.
// For local names, see corresponding methods in SMPBasicBlock.
unsigned short SMPFunction::GetDefSignMiscInfo(int DefHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
if (MapIter != this->GlobalDefFGInfoBySSA.end())
return MapIter->second.SignMiscInfo;
else
return 0;
} // end of SMPFunction::GetDefSignMiscInfo()
unsigned short SMPFunction::GetUseSignMiscInfo(int UseHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
if (MapIter != this->GlobalUseFGInfoBySSA.end())
return MapIter->second.SignMiscInfo;
else
return 0;
} // end of SMPFunction::GetUseSignMiscInfo()
unsigned short SMPFunction::GetDefWidthTypeInfo(int DefHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
if (MapIter != this->GlobalDefFGInfoBySSA.end())
return MapIter->second.SizeInfo;
else
return 0;
} // end of SMPFunction::GetDefWidthTypeInfo()
unsigned short SMPFunction::GetUseWidthTypeInfo(int UseHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
if (MapIter != this->GlobalUseFGInfoBySSA.end())
return MapIter->second.SizeInfo;
else
return 0;
} // end of SMPFunction::GetUseWidthTypeInfo()
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
struct FineGrainedInfo SMPFunction::GetDefFGInfo(int DefHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
if (MapIter != this->GlobalDefFGInfoBySSA.end())
return MapIter->second;
else {
struct FineGrainedInfo EmptyFG;
EmptyFG.SignMiscInfo = 0;
EmptyFG.SizeInfo = 0;
return EmptyFG;
}
} // end of SMPFunction::GetDefFGInfo()
struct FineGrainedInfo SMPFunction::GetUseFGInfo(int UseHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
if (MapIter != this->GlobalUseFGInfoBySSA.end())
return MapIter->second;
else {
struct FineGrainedInfo EmptyFG;
EmptyFG.SignMiscInfo = 0;
EmptyFG.SizeInfo = 0;
return EmptyFG;
}
} // end of SMPFunction::GetUseFGInfo()
clc5q
committed
// Add a caller to the list of all callers of this function.
void SMPFunction::AddCallSource(ea_t addr) {
// Convert call instruction address to beginning address of the caller.
clc5q
committed
func_t *FuncInfo = SMP_get_func(addr);
clc5q
committed
if (NULL == FuncInfo) {
clc5q
committed
SMP_msg("SERIOUS WARNING: Call location %x not in a function.\n", addr);
clc5q
committed
return;
}
ea_t FirstAddr = FuncInfo->startEA;
assert(BADADDR != FirstAddr);
this->AllCallSources.insert(FirstAddr);
return;
} // end of SMPFunction::AddCallSource()
// Six methods to set values into the maps of global reg/SSA to FG info.
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
// For local names, see corresponding methods in SMPBasicBlock.
void SMPFunction::UpdateDefSignMiscInfo(int DefHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
if (MapIter == this->GlobalDefFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = NewInfo;
NewFGInfo.SizeInfo = 0;
pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFGInfo);
MapResult = this->GlobalDefFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SignMiscInfo |= NewInfo;
}
return;
} // end of SMPFunction::UpdateDefSignMiscInfo()
void SMPFunction::UpdateUseSignMiscInfo(int UseHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
if (MapIter == this->GlobalUseFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = NewInfo;
NewFGInfo.SizeInfo = 0;
pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFGInfo);
MapResult = this->GlobalUseFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SignMiscInfo |= NewInfo;
}
return;
} // end of SMPFunction::UpdateUseSignMiscInfo()
void SMPFunction::UpdateDefWidthTypeInfo(int DefHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
if (MapIter == this->GlobalDefFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = 0;
NewFGInfo.SizeInfo = NewInfo;
pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFGInfo);
MapResult = this->GlobalDefFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SizeInfo |= NewInfo;
}
return;
} // end of SMPFunction::UpdateDefWidthTypeInfo()
void SMPFunction::UpdateUseWidthTypeInfo(int UseHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
if (MapIter == this->GlobalUseFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = 0;
NewFGInfo.SizeInfo = NewInfo;
pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFGInfo);
MapResult = this->GlobalUseFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SizeInfo |= NewInfo;
}
return;
} // end of SMPFunction::UpdateUseWidthTypeInfo()
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
void SMPFunction::UpdateDefFGInfo(int DefHashValue, struct FineGrainedInfo NewFG) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
if (MapIter == this->GlobalDefFGInfoBySSA.end()) {
// Not found; insert it.
pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFG);
MapResult = this->GlobalDefFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just put in the new bits.
MapIter->second.SignMiscInfo |= NewFG.SignMiscInfo;
MapIter->second.SizeInfo |= NewFG.SizeInfo;
}
return;
} // end of SMPFunction::UpdateDefFGInfo()
void SMPFunction::UpdateUseFGInfo(int UseHashValue, struct FineGrainedInfo NewFG) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
if (MapIter == this->GlobalUseFGInfoBySSA.end()) {
// Not found; insert it.
pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFG);
MapResult = this->GlobalUseFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just put in the new bits.
MapIter->second.SignMiscInfo |= NewFG.SignMiscInfo;
MapIter->second.SizeInfo |= NewFG.SizeInfo;
}
return;
} // end of SMPFunction::UpdateUseFGInfo()
// Erase a range of instructions from the Instrs list, usually corresponding
// the the range of a basic block.
void SMPFunction::EraseInstRange(ea_t FirstAddr, ea_t LastAddr) {
list<SMPInstr *>::iterator InstIter = this->Instrs.begin();
SMPInstr *CurrInst;
ea_t InstAddr;
while (InstIter != this->Instrs.end()) {
CurrInst = (*InstIter);
InstAddr = CurrInst->GetAddr();
if ((InstAddr >= FirstAddr) && (InstAddr <= LastAddr)) {
InstIter = this->Instrs.erase(InstIter);
}
else {
++InstIter;
}
}
} // end of SMPFunction::EraseInstRange()
clc5q
committed
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
// Get stack delta from a callee function that is unable to provide the info from
// its own analyses (e.g. analyses failed or have not been performed yet, due to
// a mutually recursive clique in the call graph). We have three approaches in
// this case: Use a default value, consult IDA Pro's analyses, or see if we can
// detect a stack adjustment after the call instruction, from which we could infer
// the stack delta of the callee.
sval_t SMPFunction::GetStackDeltaForCallee(ea_t CallAddr) {
bool success = false;
sval_t CalleeDelta = CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA;
#if 0
#ifdef STARS_IDA_INTERFACE
if (this->FuncInfo.flags & (FUNC_SP_READY | FUNC_PURGED_OK)) {
// FUNC_SP_READY => AnalyzedSP; FUNC_PURGED_OK => analysis of effect on stack succeeded.
if (this->FuncInfo.argsize != 0) {
}
}
#endif // STARS_IDA_INTERFACE
#endif
SMPBasicBlock *CallBlock = this->GetBlockFromInstAddr(CallAddr);
sval_t BlockAnalysisDelta = CallBlock->ComputeStackAdjustmentAfterCall(CallAddr);
if (0 != BlockAnalysisDelta) {
CalleeDelta -= BlockAnalysisDelta;
SMP_msg("INFO: Block analysis produced callee delta of %d bytes after %x\n", CalleeDelta, CallAddr);
}
return CalleeDelta;
} // end of SMPFunction::GetStackDeltaForCallee()
// Use IDA Pro stack pointer deltas instead of doing our own analysis.
bool SMPFunction::UseIDAStackPointerDeltas(void) {
list<SMPInstr *>::iterator InstIter;
SMPInstr *CurrInst;
#if SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS
bool IDATraceFlag = (0 == strcmp("do_length", this->GetFuncName()));
#endif
InstIter = this->Instrs.begin();
#if SMP_USE_SSA_FNOP_MARKER
++InstIter; // skip marker pseudo-instruction
#endif
while (InstIter != this->Instrs.end()) {
CurrInst = *InstIter;
sval_t IDAProDelta = get_spd(this->GetFuncInfo(), CurrInst->GetAddr());
CurrInst->SetStackPtrOffset(IDAProDelta);
++InstIter;
if (IDATraceFlag) {
SMP_msg("INFO: IDA Pro stack delta trace: %d at %x\n", IDAProDelta, CurrInst->GetAddr());
}
}
return true;
} // end of SMPFunction::UseIDAStackPointerDeltas()
// Analyze changes to the stack pointer over all instructions.
bool SMPFunction::AnalyzeStackPointerDeltas(void) {
list<pair<SMPBasicBlock *, sval_t> > WorkList;
clc5q
committed
list<SMPInstr *>::iterator InstIter;
SMPInstr *CurrInst;
clc5q
committed
bool ConsistentNetDelta = true; // Net change to stack pointer is consistent at all RETURN locations
bool ReturnSeen = false;
bool IDAProSucceeded = this->AnalyzedSP;
bool FirstBlockProcessed = false;
bool FPSaved = false; // found save of frame pointer; prelude to initializing it
bool SPintoFP = false; // found move of stack pointer into frame pointer (FP init)
#if SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS
bool DebugFlag = (0 == strcmp("find_derivation", this->GetFuncName()));
bool TraceFlag = (0 == strcmp("_dl_start_profile", this->GetFuncName()));
bool IDATraceFlag = (0 == strcmp("do_length", this->GetFuncName()));
#endif
#if 1
// Temporarily pull the functions that call alloca out of the stack pointer delta computations, so
// that we can focus on solving other problems.
if (this->CallsAlloca) {
if (!this->AnalyzedSP) {
(void) this->UseIDAStackPointerDeltas();
clc5q
committed
return false; // leave it unsolved
}
else {
SMP_msg("INFO: Using IDA Pro stack pointer deltas for alloca-calling function %s .\n", this->GetFuncName());
return this->UseIDAStackPointerDeltas();
clc5q
committed
}
}
#endif
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
// In order to precisely track stack deltas, we need to deal with instruction sequences that save the stack pointer
// and then restore it later. This requires a reaching definitions data flow analysis that includes, at a minimum,
// all stack definitions (normalized by stack delta, so that we do not confuse [esp+20] and [esp+20] where the values
// of esp are not the same). We also need to keep track of stack pointer saves in both registers and in stack locations.
// In order for the information about saved stack pointer copies to be available as soon as we need them in the stack
// delta analysis, we have to perform both stack delta analysis and reaching definitions analysis at the same time. Luckily,
// both analyses are well suited to being performed as forward analyses starting from the entry basic block.
//
// Data structures for the reaching definitions analysis include a ReachesIn and a ReachesOut set for each basic block, a
// VarKill set for each block, and a DownExposedDefs set for each block. The VarKill set is shared with the later Live Variable
// Analysis (LVA), so we compute the VarKill and the UpExposed sets (UpExposed is only used by LVA) on the first pass through
// each block. The VarKill and all other LVA sets are sets of operands. The ReachesIn, ReachesOut, and DownExposedDefs sets
// are sets of definitions, where a definition is a pair<operand, instruction address>. The StackPtrCopySet is a triple of
// <operand, instruction address, stack delta>, arranged as a pair of pairs <operand, <addr, delta> >
//
// Algorithm: We maintain a WorkList of pairs <basic block pointer, incoming stack delta to that block>
//
// All sets are empty at the beginning.
// Add the entry basic block to the WorkList, with IncomingDelta of zero.
// while (WorkList is not empty) do
// de-queue first block from WorkList, obtain IncomingDelta
// Compute ReachesIn as the union of the ReachesOut of all predecesssor blocks
// if (block has not already been processed) then
// mark block as processed
// for each inst in block (forward iteration) do
// for each USE in inst do
// if USE operand not in VarKill set for block then
// add USE operand to UpExposed set for block
// endif
// if USE operand is a stack pointer value AND it will produce DEF that is a stack pointer value then
// if DEF is stack pointer register then { a stack pointer value that was saved is being restored }
// retrieve new stack pointer delta from saved value in StackPtrCopySet, looking it up in
// that set using the reaching definitions for the USE operand. If inconsistent ******
// else { stack pointer value isbeing saved somewhere besides the stack pointer register }
// add stack delta to StackPtrCopySet for DEF that is receiving it in current inst
// endif
// endif
// endfor { each USE }
// for each DEF in inst do
// if register or stack operand then
// add to VarKill set
// update DownExposedDefs set (insert, or replace current def for this operand)
// endif
// endfor { each DEF }
// Store IncomingDelta for current instruction
// Get change in delta for current instruction
// Add current change to IncomingDelta
// endfor { each inst }
// At end of block, make ReachesOut set be (ReachesIn minus VarKill) union DownExposedDefs
// For each successor block, add pairs <block pointer, IncomingDelta> to end of WorkList
// else { block has already been processed at least once}
// if IncomingDelta from WorkList is inconsistent with old IncomingDelta then
// if function calls alloca() then
// if new IncomingDelta makes stack frame look larger than old IncomingDelta then
// ignore new IncomingDelta and just process reaching definitions sets below
// else
// use new IncomingDelta and re-process deltas in this block to converge to
// smallest stack frame, which means we are basically ignoring alloca()'s as much as possible.
// endif
// else
// Set AnalyzedSP to false, emit error message, clear WorkList and bail out of this function.
// endif
// endif { inconsistent IncomingDelta values }
// Recompute ReachesIn as union of ReachesOut of all predecessor blocks
// if ReachesIn set changed then
// recompute ReachesOut without examining instructions unless alloca() case requires iterating through instructions
// endif
// if any change in deltas or reaching definitions sets, then add block to end of WorkList along with all successor blocks.
// endif
// end while
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
// Mark all blocks as unprocessed
this->ResetProcessedBlocks();
this->AnalyzedSP = true;
// Put the entry block on the work list.
assert(0 < this->Blocks.size());
pair<SMPBasicBlock *, sval_t> WorkingPair (this->Blocks.front(), CurrentDelta);
WorkList.push_back(WorkingPair);
// While blocks exist on the work list
// if block already processed, confirm that we are re-entering
// the block with the same stack pointer delta as previously,
// and pop it off the work list
// otherwise declare the stack pointer to be un-analyzeable;
// else
// iterate through all instructions in the block, analyzing
// the stack pointer delta of each inst and accumulating current delta
// At the end of the block, put the successor blocks on the work list.
do {
SMPBasicBlock *CurrBlock = WorkList.front().first;
sval_t IncomingDelta = WorkList.front().second;
if (CurrBlock->IsProcessed()) { // already processed
InstIter = CurrBlock->GetFirstInstr();
sval_t PrevIncomingDelta = (*InstIter)->GetStackPtrOffset();
if (IncomingDelta == PrevIncomingDelta) {
// No error, already processed.
WorkList.pop_front(); // discard already processed block.
}
clc5q
committed
else if (this->CallsAlloca) {
// Calls to alloca() become additional stack allocations, which can produce
// multiple possible stack deltas for an instruction if different paths
// to the instruction do not hit the same alloca() calls, so it is not
// an error to have conflicting deltas in the functions that call alloca().
// We want to converge to the smallest magnitude deltas, which are the greatest
// values because the deltas are negative. This is the opposite of IDA Pro, which
// seems to use the largest stack deltas it has seen.
if (PrevIncomingDelta >= IncomingDelta) {
// Old incoming delta should be retained.
WorkList.pop_front(); // discard already processed block.
}
else {
CurrBlock->SetProcessed(false);
continue; // Make the loop come around and process this block again, using
// the new incoming delta. Because we do this only when it decreases
// the stack size as seen by this block, no infinite loop is possible.
}
}
else {
this->AnalyzedSP = false;
SMP_msg("ERROR: Stack delta: PrevIncoming is %d NewIncoming is %d at %x\n",
PrevIncomingDelta, IncomingDelta, (*InstIter)->GetAddr());
WorkList.clear();
}
}
else { // not already processed
CurrBlock->SetProcessed(true);
WorkList.pop_front();
clc5q
committed
sval_t BlockIncomingDelta = IncomingDelta;
for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
clc5q
committed
CurrInst = (*InstIter);
ea_t InstAddr = CurrInst->GetAddr();
if (InstAddr == this->GetFirstFrameAllocInstAddr()) {
clc5q
committed
// Record the reset point for frame deallocations
this->PreAllocStackDelta = IncomingDelta;
}
#if 0
if (this->CallsAlloca) { // keep deltas in a set; paths can lead to multiple deltas per inst
bool DeltaAlreadyFound = CurrInst->FindStackPtrDelta(IncomingDelta);
clc5q
committed
else {
clc5q
committed
CurrInst->SetStackPtrOffset(IncomingDelta);
#if 0
}
#endif
#if SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS
if (DebugFlag && IDAProSucceeded && !this->CallsAlloca) {
sval_t IDAProDelta = get_spd(this->GetFuncInfo(), InstAddr);
clc5q
committed
if ((IDAProDelta != IncomingDelta) && (!CurrInst->MDIsHaltInstr())) {
// IDA Pro special-cases the HALT instruction to make it appear that the
// incoming stack delta is zero. We do no such special case delta adjudstment,
// so we suppress error messages, as our delta will be non-zero.
SMP_msg("ERROR: At %x IDA Pro has stack pointer delta of %d and we compute %d\n", InstAddr,
clc5q
committed
IDAProDelta, IncomingDelta);
}
}
if (TraceFlag) {
SMP_msg("INFO: Stack delta trace: %d at %x\n", IncomingDelta, InstAddr);
clc5q
committed
}
#endif
if (!FirstBlockProcessed) { // Look for initialization of frame pointer, record its stack delta
FirstBlockProcessed = CurrInst->IsLastInBlock();
if (!FPSaved) { // still looking for "push <framepointerreg>"
if (CurrInst->MDIsPushInstr() && CurrInst->GetCmd().Operands[0].is_reg(MD_FRAME_POINTER_REG)) {
FPSaved = true;
}
}
else if (!SPintoFP) { // found "push <framepointerreg>", looking for "fp := sp"
insn_t CurrCmd = CurrInst->GetCmd();
if ((CurrCmd.itype == MD_MOVE_INSTRUCTION)
&& (CurrInst->GetFirstDef()->GetOp().is_reg(MD_FRAME_POINTER_REG))
&& (CurrInst->GetFirstUse()->GetOp().is_reg(MD_STACK_POINTER_REG))) {
SPintoFP = true;
this->FramePointerStackDelta = IncomingDelta;
FirstBlockProcessed = true; // stop looking
assert(this->UsesFramePointer());
}
}
}
CurrentDelta = CurrInst->AnalyzeStackPointerDelta(IncomingDelta, this->GetFramePtrStackDelta());
if (SMP_STACK_POINTER_BITWISE_AND_CODE == CurrentDelta) {
// For now, we ignore instructions that AND a constant into the stack pointer.
CurrentDelta = 0;
clc5q
committed
SMP_msg("WARNING: Stack pointer bitwise AND ignored at %x\n", CurrInst->GetAddr());
}
else if (SMP_STACK_DELTA_ERROR_CODE == CurrentDelta) {
this->AnalyzedSP = false;
SMP_msg("ERROR: Stack delta unanalyzeable at %x\n", InstAddr);
WorkList.clear();
break;
}
SMPitype FlowType = CurrInst->GetDataFlowType();
// Search for tail calls, defined strictly as having an incoming stack delta of zero and
// being jumps to far chunks.
if ((0 == IncomingDelta) && (CurrInst->IsBranchToFarChunk())) {
CurrInst->SetTailCall();
SMP_msg("Found tail call at %x from %s: %s\n", InstAddr, this->GetFuncName(),
CurrInst->GetDisasm());
}
if ((RETURN == FlowType) && (!CurrInst->IsCondTailCall())) {
clc5q
committed
// We hope to see a consistent outgoing delta from all RETURN points.
// We special-case the conditional jump used as tail call, because it must be followed
// by a real return instruction later. If the jump is taken, it acts as a return, but
// it has not yet popped the stack.
if (ReturnSeen) { // This is not the first RETURN seen.
if (IncomingDelta != this->NetStackDelta) { // Inconsistent
SMP_msg("ERROR: Inconsistent stack deltas at return instruction at %x\n", CurrInst->GetAddr());
ConsistentNetDelta = false;
this->AnalyzedSP = false;
WorkList.clear();
break;
}
}
else { // First RETURN statement seen.
ReturnSeen = true;
this->NetStackDelta = IncomingDelta;
#if SMP_AUDIT_STACK_POINTER_DELTAS
clc5q
committed
if (0 != IncomingDelta) {
SMP_msg("WARNING: Stack delta not zero after return instruction at %x\n", CurrInst->GetAddr());
}
clc5q
committed
}
}
}
// Push the successor blocks onto the work list
clc5q
committed
if (this->AnalyzedSP) { // if we do not have an error already
list<SMPBasicBlock *>::iterator SuccIter;
for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
pair<SMPBasicBlock *, sval_t> SuccPair (*SuccIter, IncomingDelta);
WorkList.push_back(SuccPair);
}
}
}
} while (!WorkList.empty());
clc5q
committed
this->STARSStackPtrAnalysisPerformed = true;
if (this->AnalyzedSP && (CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA != this->NetStackDelta)) {
SMP_msg("WARNING: Non-default stack ptr delta %d for function: %s\n", this->NetStackDelta, this->GetFuncName());
}
if (IDAProSucceeded) {
if (!this->AnalyzedSP) {
SMP_msg("ERROR: Stack Ptr Delta Analysis succeeded in IDA, failed in STARS for %x : %s\n", this->FirstEA,
this->GetFuncName());
}
}
else {
if (this->AnalyzedSP) {
SMP_msg("SUCCESS: Stack Ptr Delta Analysis failed in IDA, succeeded in STARS for %x : %s\n", this->FirstEA,
this->GetFuncName());
}
}
return this->AnalyzedSP;
} // end of SMPFunction::AnalyzeStackPointerDeltas()
clc5q
committed
void SMPFunction::FindAllAllocsAndDeallocs(void) {
bool FoundAllocInstr = false;
bool FoundDeallocInstr = false;
clc5q
committed
DebugFlag |= (0 == strcmp("frame_dummy", this->GetFuncName()));
#endif
// Now, if LocalVarsSize is not zero, we need to find the instruction
// in the function prologue that allocates space on the stack for
// local vars. This code could be made more robust in the future
// by matching LocalVarsSize to the immediate value in the allocation
// instruction. However, IDA Pro is sometimes a little off on this
// number. **!!**
if (0 < this->LocalVarsSize) {
clc5q
committed
if (DebugFlag) SMP_msg("Searching for alloc and dealloc\n");
list<SMPInstr *>::iterator InstIter = this->Instrs.begin();
#if SMP_USE_SSA_FNOP_MARKER
++InstIter; // skip marker instruction
for ( ; InstIter != this->Instrs.end(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
ea_t addr = CurrInst->GetAddr();
// Keep the most recent instruction in the DeallocInstr
// in case we reach the return without seeing a dealloc.
if (!FoundDeallocInstr) {
this->LocalVarsDeallocInstr = addr;
}
if (!FoundAllocInstr
&& CurrInst->MDIsFrameAllocInstr()) {
clc5q
committed
SMP_msg("Returned from MDIsFrameAllocInstr()\n");
this->LocalVarsAllocInstr = addr;
FoundAllocInstr = true;
clc5q
committed
if (DebugFlag) SMP_msg("Found alloc: %s\n", CurrInst->GetDisasm());
// As soon as we have found the local vars allocation,
// we can try to fix incorrect sets of UseFP by IDA.
// NOTE: We might want to extend this in the future to
// handle functions that have no locals. **!!**
bool FixedUseFP = MDFixUseFP();
clc5q
committed
SMP_msg("Returned from MDFixUseFP()\n");
#if SMP_DEBUG_FRAMEFIXUP
if (FixedUseFP) {
clc5q
committed
SMP_msg("Fixed UseFP in %s\n", this->GetFuncName());
}
#endif
}
else if (FoundAllocInstr) {
// We can now start searching for the DeallocInstr.
if (CurrInst->MDIsFrameDeallocInstr(UseFP, this->LocalVarsSize)) {
// Keep saving the most recent addr that looks
// like the DeallocInstr until we reach the
// end of the function. Last one to look like
// it is used as the DeallocInstr.
clc5q
committed
SMP_msg("Returned from MDIsFrameDeallocInstr()\n");
this->LocalVarsDeallocInstr = addr;
FoundDeallocInstr = true;
}
clc5q
committed
if (DebugFlag) SMP_msg("Not dealloc: %s\n", CurrInst->GetDisasm());
} // end for (list<SMPInstr *>::iterator InstIter ... )
if (!FoundAllocInstr) {
// Could not find the frame allocating instruction. Bad.
// See if we can find the point at which the stack allocation reaches
// a total of FuncInfo.frsize+frregs, regardless of whether it happened by push
// instructions or some other means.
this->LocalVarsAllocInstr = this->FindAllocPoint(this->FuncInfo.frsize + this->FuncInfo.frregs);
clc5q
committed
SMP_msg("Returned from FindAllocPoint()\n");
#if SMP_DEBUG_FRAMEFIXUP
if (BADADDR == this->LocalVarsAllocInstr) {
clc5q
committed
SMP_msg("ERROR: Could not find stack frame allocation in %s\n",
clc5q
committed
SMP_msg("LocalVarsSize: %d SavedRegsSize: %d ArgsSize: %d\n",
LocalVarsSize, CalleeSavedRegsSize, IncomingArgsSize);
}
else {
clc5q
committed
SMP_msg("FindAllocPoint found %x for function %s\n",
this->LocalVarsAllocInstr, this->GetFuncName());
}
#endif
}
if (!FoundDeallocInstr) {
// Could not find the frame deallocating instruction. Bad.
// Emit diagnostic and use the last instruction in the
// function.
clc5q
committed
SMP_msg("ERROR: Could not find stack frame deallocation in %s\n",
}
#endif
}
// else LocalVarsSize was zero, meaning that we need to search
// for the end of the function prologue code and emit stack frame
// annotations from that address (i.e. this method returns that
// address). We will approximate this by finding the end of the
// sequence of PUSH instructions at the beginning of the function.
// The last PUSH instruction should be the last callee-save-reg
// instruction. We can make this more robust in the future by