SMPDataFlowAnalysis.cpp

//
// SMPDataFlowAnalysis.cpp
//
// This module performs the fundamental data flow analyses needed for the
//   SMP project (Software Memory Protection).
//

#include <list>
#include <set>
#include <vector>
#include <algorithm>

#include <cstring>

#include <pro.h>
#include <assert.h>
#include <ida.hpp>
#include <idp.hpp>
#include <allins.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <intel.hpp>
#include <loader.hpp>
#include <lines.hpp>
#include <name.hpp>

#include "SMPDataFlowAnalysis.h"
#include "SMPStaticAnalyzer.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
#define SMP_DEBUG_FRAMEFIXUP 0
#define SMP_DEBUG_DATAFLOW 0

// Compute LVA/SSA or not? Turn it off for NICECAP demo on 31-JAN-2008
#define SMP_COMPUTE_LVA_SSA 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;

// Define instruction categories for data flow analysis.
static SMPitype DFACategory[NN_last+1];

static char *RegNames[R_of + 1] =
	{ "EAX", "ECX", "EDX", "EBX", "ESP", "EBP", "ESI", "EDI",
	  "R8", "R9", "R10", "R11", "R12", "R13", "R14", "R15",
	  "AL", "CL", "DL", "BL", "AH", "CH", "DH", "BH",
	  "SPL", "BPL", "SIL", "DIL", "EIP", "ES", "CS", "SS",
	  "DS", "FS", "GS", "CF", "ZF", "SF", "OF" 
	};

// Make the CF_CHG1 .. CF_CHG6 and CF_USE1..CF_USE6 macros more usable
//  by allowing us to pick them up with an array index.
static ulong DefMacros[UA_MAXOP] = {CF_CHG1, CF_CHG2, CF_CHG3, CF_CHG4, CF_CHG5, CF_CHG6};
static ulong UseMacros[UA_MAXOP] = {CF_USE1, CF_USE2, CF_USE3, CF_USE4, CF_USE5, CF_USE6};

// Text to be printed in each optimizing annotation explaining why
//  the annotation was emitted.
static char *OptExplanation[LAST_OPT_CATEGORY + 1] =
	{ "NoOpt", "NoMetaUpdate", "AlwaysNUM", "NUMVia2ndSrcIMMEDNUM",
	  "Always1stSrc", "1stSrcVia2ndSrcIMMEDNUM", "AlwaysPtr",
	  "AlwaysNUM", "AlwaysNUM", "NUMViaFPRegDest"
	};

// We need to make subword registers equal to their containing registers when we
//  do comparisons, so that we will realize that register EAX is killed by a prior DEF
//  of register AL, for example. However, we do not want AL and AH to be equal to each other.
#define FIRST_x86_SUBWORD_REG R_al
#define LAST_x86_SUBWORD_REG R_bh
bool MDLessReg(const ushort Reg1, const ushort Reg2) {
	bool FirstSubword = ((Reg1 >= FIRST_x86_SUBWORD_REG) && (Reg1 <= LAST_x86_SUBWORD_REG));
	bool SecondSubword = ((Reg2 >= FIRST_x86_SUBWORD_REG) && (Reg2 <= LAST_x86_SUBWORD_REG));

	// Only complexity comes when one is subword and the other is not.
	if (FirstSubword == SecondSubword)
		return (Reg1 < Reg2); // simple case
	else {
		if (FirstSubword) {
			// See enumeration RegNo in intel.hpp.
			if (((Reg1 < 20) && ((Reg1 - Reg2) == 16))
				|| ((Reg1 >= 20) && ((Reg1 - Reg2) == 20)))
				return false;  // subword matches enclosing register
			else
				return (Reg1 < Reg2);
		}
		else { // must be SecondSubword
			if (((Reg2 < 20) && ((Reg2 - Reg1) == 16))
				|| ((Reg2 >= 20) && ((Reg2 - Reg1) == 20)))
				return false;  // subword matches enclosing register
			else
				return (Reg1 < Reg2);
		}
	}
} // end of MDLessReg()

// In SSA computations, we are storing the GlobalNames index into the op_t fields
//  n, offb, and offo. This function extracts an unsigned int from these three 8-bit
//  fields.
unsigned int ExtractGlobalIndex(op_t GlobalOp) {
	unsigned int index = (unsigned int) GlobalOp.offo;
	index <<= 16;
	index |= (((unsigned int) GlobalOp.offb) << 8);
	index |= ((unsigned int) GlobalOp.n);
	return index;
}

// *****************************************************************
// Class DefOrUse
// *****************************************************************

// Constructor.
DefOrUse::DefOrUse(op_t Ref, SMPOperandType Type, int SSASub) {
	this->Operand = Ref;
	this->OpType = Type;
	this->SSANumber = SSASub;
	return;
}

// *****************************************************************
// Class DefOrUseList
// *****************************************************************

// Default constructor.
DefOrUseList::DefOrUseList(void) {
	return;
}

// Set a Def or Use into the list, along with its type.
void DefOrUseList::SetRef(op_t Ref, SMPOperandType Type, int SSASub) {
	DefOrUse CurrRef(Ref, Type, SSASub);
	this->Refs.push_back(CurrRef);
	return;
}

// Get a reference by index.
DefOrUse DefOrUseList::GetRef(size_t index) const {
	return Refs[index];
}

// *****************************************************************
// Class SMPPhiFunction
// *****************************************************************

// Constructor
SMPPhiFunction::SMPPhiFunction(int GlobIndex) {
	this->index = GlobIndex;
	return;
}

// Add a phi item to the list
void SMPPhiFunction::PushBack(DefOrUse Ref) {
	this->SubscriptedOps.SetRef(Ref.GetOp(), Ref.GetType(), Ref.GetSSANum());
	return;
}


// *****************************************************************
// Class SMPInstr
// *****************************************************************

// Constructor for instruction.
SMPInstr::SMPInstr(ea_t addr) {
	this->address = addr;
	this->analyzed = false;
	this->JumpTarget = false;
	return;
}

// Is the instruction the type that terminates a basic block?
bool SMPInstr::IsBasicBlockTerminator() const {
	return ((type == JUMP) || (type == COND_BRANCH)
			|| (type == INDIR_JUMP) || (type == RETURN));
}

// Is the destination operand a memory reference?
bool SMPInstr::HasDestMemoryOperand(void) const {
	bool MemDest = false;
	for (size_t index = 0; index < Defs.GetSize(); ++index) {
		optype_t CurrType = Defs.GetRef(index).GetOp().type;
		MemDest = ((CurrType == o_mem) || (CurrType == o_phrase) || (CurrType == o_displ));
		if (MemDest)
			break;
	}
	return MemDest;