//
// SMPDataFlowAnalysis.cpp
//
// This module contains common types an helper classes 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
// Define instruction categories for data flow analysis.
SMPitype DFACategory[NN_last+1];
// 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;
}
// Initialize the DFACategory[] array to define instruction classes
// for the purposes of data flow analysis.
void InitDFACategory(void) {
// Default category is 0, not the start or end of a basic block.
(void) memset(DFACategory, 0, sizeof(DFACategory));
DFACategory[NN_call] = CALL; // Call Procedure
DFACategory[NN_callfi] = INDIR_CALL; // Indirect Call Far Procedure
DFACategory[NN_callni] = INDIR_CALL; // Indirect Call Near Procedure
DFACategory[NN_hlt] = HALT; // Halt
DFACategory[NN_int] = CALL; // Call to Interrupt Procedure
DFACategory[NN_into] = CALL; // Call to Interrupt Procedure if Overflow Flag = 1
DFACategory[NN_int3] = CALL; // Trap to Debugger
DFACategory[NN_iretw] = RETURN; // Interrupt Return
DFACategory[NN_iret] = RETURN; // Interrupt Return
DFACategory[NN_iretd] = RETURN; // Interrupt Return (use32)
DFACategory[NN_iretq] = RETURN; // Interrupt Return (use64)
DFACategory[NN_ja] = COND_BRANCH; // Jump if Above (CF=0 & ZF=0)
DFACategory[NN_jae] = COND_BRANCH; // Jump if Above or Equal (CF=0)
DFACategory[NN_jb] = COND_BRANCH; // Jump if Below (CF=1)
DFACategory[NN_jbe] = COND_BRANCH; // Jump if Below or Equal (CF=1 | ZF=1)
DFACategory[NN_jc] = COND_BRANCH; // Jump if Carry (CF=1)
DFACategory[NN_jcxz] = COND_BRANCH; // Jump if CX is 0
DFACategory[NN_jecxz] = COND_BRANCH; // Jump if ECX is 0
DFACategory[NN_jrcxz] = COND_BRANCH; // Jump if RCX is 0
DFACategory[NN_je] = COND_BRANCH; // Jump if Equal (ZF=1)
DFACategory[NN_jg] = COND_BRANCH; // Jump if Greater (ZF=0 & SF=OF)
DFACategory[NN_jge] = COND_BRANCH; // Jump if Greater or Equal (SF=OF)
DFACategory[NN_jl] = COND_BRANCH; // Jump if Less (SF!=OF)
DFACategory[NN_jle] = COND_BRANCH; // Jump if Less or Equal (ZF=1 | SF!=OF)
DFACategory[NN_jna] = COND_BRANCH; // Jump if Not Above (CF=1 | ZF=1)
DFACategory[NN_jnae] = COND_BRANCH; // Jump if Not Above or Equal (CF=1)
DFACategory[NN_jnb] = COND_BRANCH; // Jump if Not Below (CF=0)
DFACategory[NN_jnbe] = COND_BRANCH; // Jump if Not Below or Equal (CF=0 & ZF=0)
DFACategory[NN_jnc] = COND_BRANCH; // Jump if Not Carry (CF=0)
DFACategory[NN_jne] = COND_BRANCH; // Jump if Not Equal (ZF=0)
DFACategory[NN_jng] = COND_BRANCH; // Jump if Not Greater (ZF=1 | SF!=OF)
DFACategory[NN_jnge] = COND_BRANCH; // Jump if Not Greater or Equal (ZF=1)
DFACategory[NN_jnl] = COND_BRANCH; // Jump if Not Less (SF=OF)
DFACategory[NN_jnle] = COND_BRANCH; // Jump if Not Less or Equal (ZF=0 & SF=OF)
DFACategory[NN_jno] = COND_BRANCH; // Jump if Not Overflow (OF=0)
DFACategory[NN_jnp] = COND_BRANCH; // Jump if Not Parity (PF=0)
DFACategory[NN_jns] = COND_BRANCH; // Jump if Not Sign (SF=0)
DFACategory[NN_jnz] = COND_BRANCH; // Jump if Not Zero (ZF=0)
DFACategory[NN_jo] = COND_BRANCH; // Jump if Overflow (OF=1)
DFACategory[NN_jp] = COND_BRANCH; // Jump if Parity (PF=1)
DFACategory[NN_jpe] = COND_BRANCH; // Jump if Parity Even (PF=1)
DFACategory[NN_jpo] = COND_BRANCH; // Jump if Parity Odd (PF=0)
DFACategory[NN_js] = COND_BRANCH; // Jump if Sign (SF=1)
DFACategory[NN_jz] = COND_BRANCH; // Jump if Zero (ZF=1)
DFACategory[NN_jmp] = JUMP; // Jump
DFACategory[NN_jmpfi] = INDIR_JUMP; // Indirect Far Jump
DFACategory[NN_jmpni] = INDIR_JUMP; // Indirect Near Jump
DFACategory[NN_jmpshort] = JUMP; // Jump Short (only in 64-bit mode)
DFACategory[NN_loopw] = COND_BRANCH; // Loop while ECX != 0
DFACategory[NN_loop] = COND_BRANCH; // Loop while CX != 0
DFACategory[NN_loopd] = COND_BRANCH; // Loop while ECX != 0
DFACategory[NN_loopq] = COND_BRANCH; // Loop while RCX != 0
DFACategory[NN_loopwe] = COND_BRANCH; // Loop while CX != 0 and ZF=1
DFACategory[NN_loope] = COND_BRANCH; // Loop while rCX != 0 and ZF=1
DFACategory[NN_loopde] = COND_BRANCH; // Loop while ECX != 0 and ZF=1
DFACategory[NN_loopqe] = COND_BRANCH; // Loop while RCX != 0 and ZF=1
DFACategory[NN_loopwne] = COND_BRANCH; // Loop while CX != 0 and ZF=0
DFACategory[NN_loopne] = COND_BRANCH; // Loop while rCX != 0 and ZF=0
DFACategory[NN_loopdne] = COND_BRANCH; // Loop while ECX != 0 and ZF=0
DFACategory[NN_loopqne] = COND_BRANCH; // Loop while RCX != 0 and ZF=0
DFACategory[NN_retn] = RETURN; // Return Near from Procedure
DFACategory[NN_retf] = RETURN; // Return Far from Procedure
//
// Pentium instructions
//
DFACategory[NN_rsm] = HALT; // Resume from System Management Mode
// Pentium II instructions
DFACategory[NN_sysenter] = CALL; // Fast Transition to System Call Entry Point
DFACategory[NN_sysexit] = CALL; // Fast Transition from System Call Entry Point
// AMD syscall/sysret instructions NOTE: not AMD, found in Intel manual
DFACategory[NN_syscall] = CALL; // Low latency system call
DFACategory[NN_sysret] = CALL; // Return from system call
// VMX instructions
DFACategory[NN_vmcall] = INDIR_CALL; // Call to VM Monitor
return;
} // end InitDFACategory()