SMPDataFlowAnalysis.cpp

/*
 * SMPDataFlowAnalysis.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/
 *
 */

//
// 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"
#include "SMPInstr.h"
#include "SMPBasicBlock.h"
#include "SMPFunction.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
#define SMP_DEBUG_OPERAND_TYPES 1  // leave on; should never happen

const 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" 
	};

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

// Define which instructions define and use the CPU flags.
bool SMPDefsFlags[NN_last + 1];
bool SMPUsesFlags[NN_last + 1];

// Get the size in bytes of the data type of an operand.
size_t GetOpDataSize(op_t DataOp) {
	size_t DataSize;
	switch (DataOp.dtyp) {
		case dt_byte:
			DataSize = 1;
			break;
		case dt_word:
			DataSize = 2;
			break;
		case dt_dword:
		case dt_float:
		case dt_code:
		case dt_unicode:
		case dt_string:
			DataSize = 4;
			break;
		case dt_double:
		case dt_qword:
			DataSize = 8;
			break;
		case dt_packreal:
			DataSize = 12;
			break;
		case dt_byte16:
			DataSize = 16;
			break;
		case dt_fword:
			DataSize = 6;
			break;
		case dt_3byte:
			DataSize = 3;
			break;
		default:
			msg("WARNING: unexpected data type %d in GetOpDataSize() :", DataOp.dtyp);
			PrintOperand(DataOp);
			msg("\n");
			DataSize = 4;
			break;
	}
	return DataSize;
} // end of GetOpDataSize()

// 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, and vice versa. To keep sets ordered strictly,
//  we also have to make AL and AH be equal to each other as well as equal to EAX.
#define FIRST_x86_SUBWORD_REG R_al
#define LAST_x86_SUBWORD_REG R_bh
bool MDLessReg(const ushort Reg1, const ushort Reg2) {
	ushort SReg1 = MDCanonicalizeSubReg(Reg1);
	ushort SReg2 = MDCanonicalizeSubReg(Reg2);
	return (SReg1 < SReg2);
} // end of MDLessReg()

ushort MDCanonicalizeSubReg(const ushort Reg1) {
	bool Subword = ((Reg1 >= FIRST_x86_SUBWORD_REG) && (Reg1 <= LAST_x86_SUBWORD_REG));
	ushort SReg1 = Reg1;

	if (Subword) {
		// See enumeration RegNo in intel.hpp.
		if (SReg1 < 20)  // AL, CL, DL or BL
			SReg1 -= 16;
		else             // AH, CH, DH or BH
			SReg1 -= 20;
	}
	return SReg1;
} // end of MDCanonicalizeSubReg()

// 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 = 0;
	index |= (((unsigned int) GlobalOp.offo) & 0x000000ff);
	index <<= 8;
	index |= (((unsigned int) GlobalOp.offb) & 0x000000ff);
	index <<= 8;
	index |= (((unsigned int) GlobalOp.n) & 0x000000ff);
	return index;
}

void SetGlobalIndex(op_t *TempOp, size_t index) {
	TempOp->n = (char) (index & 0x000000ff);
	TempOp->offb = (char) ((index & 0x0000ff00) >> 8);
	TempOp->offo = (char) ((index & 0x00ff0000) >> 16);
	return;
}

// Return true if CurrOp could be an indirect memory reference.
bool MDIsIndirectMemoryOpnd(op_t CurrOp, bool UseFP) {
	bool indirect = false;
	if ((CurrOp.type != o_mem) && (CurrOp.type != o_phrase) && (CurrOp.type != o_displ))
		return false;

	if (CurrOp.hasSIB) {
		int BaseReg = sib_base(CurrOp);
		short IndexReg = sib_index(CurrOp);
		if ((R_none != IndexReg) && (R_sp != IndexReg)) { 
			if ((R_bp == IndexReg) && UseFP)
				;
			else
				indirect = true;
		}
		if (0 != sib_scale(CurrOp))
			indirect = true;
		if (R_none != BaseReg) {
			if ((BaseReg == R_bp) && (CurrOp.type == o_mem)) {
				; // EBP ==> no base register for o_mem type
			}
			else if ((BaseReg == R_bp) && UseFP) 
				;  // EBP used as frame pointer for direct access
			else if (BaseReg == R_sp)
				;  // ESP used as stack pointer for direct access
			else
				indirect = true; // conservative; some register used for addressing