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/
 *
 * Additional copyrights 2010, 2011, 2012, 2013, 2014, 2015 by Zephyr Software LLC
 * e-mail: {clc,jwd}@zephyr-software.com
 * URL   : http://www.zephyr-software.com/
 *
 */

//
// 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 <string>

#include <cstdlib>
#include <cstring>
#include <cassert>

#include "interfaces/SMPDBInterface.h"
#include "base/SMPDataFlowAnalysis.h"
#include "base/SMPInstr.h"
#include "base/SMPBasicBlock.h"
#include "base/SMPFunction.h"

using namespace std;

// Set these to 1 for debugging output
#define SMP_DEBUG_CONTROLFLOW 0  // tells what processing stage is entered
#define SMP_DEBUG_CHUNKS 1  // tracking down tail chunks for functions
#define SMP_DEBUG_FRAMEFIXUP 0  // Fixing up stack frame info the way we want the offsets
#define SMP_DEBUG_OPERAND_TYPES 1  // leave on; warnings that should never happen
#define STARS_DEBUG_DUMP_IDENTIFY_HIDDEN_OPERANDS 0 // print HIDDEN if operand.showed() is false

#define MAX_IDA_REG STARS_x86_R_last

// return true if Item is in IntList
bool IsIntInList(const std::list<int> &IntList, int Item) {
	bool Found = false;
	for (list<int>::const_iterator ListIter = IntList.cbegin(); ListIter != IntList.cend(); ++ListIter) {
		if ((*ListIter) == Item) {
			Found = true;
			break;
		}
	}
	return Found;
}

// Bit masks for extracting bits from a STARSBitSet unsigned char.
const uint8_t STARSBitMasks[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };

const char *RegNames[MAX_IDA_REG + 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", "PF",
	  "AF", "TF", "IF", "DF", "EFLAGS", "FPU_ST0", "FPU_ST1", "FPU_ST2",
	  "FPU_ST3", "FPU_ST4", "FPU_ST5", "FPU_ST6", "FPU_ST7", "FPU_CTRL", "FPU_STAT", "FPU_TAGS",
	  "MMX0", "MMX1", "MMX2", "MMX3", "MMX4", "MMX5", "MMX6", "MMX7",
	  "XMM0", "XMM1", "XMM2", "XMM3", "XMM4", "XMM5", "XMM6", "XMM7",
	  "XMM8", "XMM9", "XMM10", "XMM11", "XMM12", "XMM13", "XMM14", "XMM15",
	  "MXCSR",
	  "YMM0", "YMM1", "YMM2", "YMM3", "YMM4", "YMM5", "YMM6", "YMM7",
	  "YMM8", "YMM9", "YMM10", "YMM11", "YMM12", "YMM13", "YMM14", "YMM15",
	  "BND0", "BND1", "BND2", "BND3",
	  "XMM16", "XMM17", "XMM18", "XMM19", "XMM20", "XMM21", "XMM22", "XMM23",
	  "XMM24", "XMM25", "XMM26", "XMM27", "XMM28", "XMM29", "XMM30", "XMM31",
	  "YMM16", "YMM17", "YMM18", "YMM19", "YMM20", "YMM21", "YMM22", "YMM23",
	  "YMM24", "YMM25", "YMM26", "YMM27", "YMM28", "YMM29", "YMM30", "YMM31",
	  "XMM0", "XMM1", "XMM2", "XMM3", "XMM4", "XMM5", "XMM6", "XMM7",
	  "XMM8", "XMM9", "XMM10", "XMM11", "XMM12", "XMM13", "XMM14", "XMM15",
	  "ZMM16", "ZMM17", "ZMM18", "ZMM19", "ZMM20", "ZMM21", "ZMM22", "ZMM23",
	  "ZMM24", "ZMM25", "ZMM26", "ZMM27", "ZMM28", "ZMM29", "ZMM30", "ZMM31",
	  "K0", "K1", "K2", "K3", "K4", "K5", "K6", "K7",
	  "REG_ERROR"
	};

// NOTE: Review these sizes. Alter when annotation diffs can be isolated to the change.
//   !!!!****!!!! FP reg stack should be 10-byte registers, right?
const unsigned char RegSizes[MAX_IDA_REG + 1] =
	{ 4, 4, 4, 4, 4, 4, 4, 4,
	  8, 8, 8, 8, 8, 8, 8, 8,
	  1, 1, 1, 1, 1, 1, 1, 1,
	  1, 1, 1, 1, 4, 2, 2, 2,
	  2, 2, 2, 4, 4, 4, 4, 4,
	  4, 4, 4, 4, 4, 10, 10, 10,
	  10, 10, 10, 10, 10, 4, 4, 4,
	  16, 16, 16, 16, 16, 16, 16, 16,
	  16, 16, 16, 16, 16, 16, 16, 16,
	  16, 16, 16, 16, 16, 16, 16, 16,
	  4,
	  32, 32, 32, 32, 32, 32, 32, 32,
	  32, 32, 32, 32, 32, 32, 32, 32,
	  4
	};

unsigned char GetRegSize(STARS_regnum_t RegNum) {
	assert(RegNum != ((STARS_regnum_t) STARS_x86_R_none));
	return RegSizes[RegNum];
}

const char RegDtyps[MAX_IDA_REG + 1] =
{ STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword,
STARS_dt_qword, STARS_dt_qword, STARS_dt_qword, STARS_dt_qword, STARS_dt_qword, STARS_dt_qword, STARS_dt_qword, STARS_dt_qword,
STARS_dt_byte, STARS_dt_byte, STARS_dt_byte, STARS_dt_byte, STARS_dt_byte, STARS_dt_byte, STARS_dt_byte, STARS_dt_byte,
STARS_dt_byte, STARS_dt_byte, STARS_dt_byte, STARS_dt_byte, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword,
STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword,
STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_dword, STARS_dt_tbyte, STARS_dt_tbyte, STARS_dt_tbyte,
STARS_dt_tbyte, STARS_dt_tbyte, STARS_dt_tbyte, STARS_dt_tbyte, STARS_dt_tbyte, STARS_dt_word, STARS_dt_word, STARS_dt_word,
STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16,
STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16,
STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16, STARS_dt_byte16,
STARS_dt_word,
STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32,
STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32, STARS_dt_byte32,
STARS_dt_word 
};

const char *ErrorStrings[1] = { "ERROR_REG" };

const char *WordRegStrings[8] = { "AX", "CX", "DX", "BX", "SP", "BP", "SI", "DI" };

const char *QWordRegStrings[8] = { "RAX", "RCX", "RDX", "RBX", "RSP", "RBP", "RSI", "RDI" };

const char *QDWordRegStrings[8] = { "R8D", "R9D", "R10D", "R11D", "R12D", "R13D", "R14D", "R15D" };

const char *QWWordRegStrings[8] = { "R8W", "R9W", "R10W", "R11W", "R12W", "R13W", "R14W", "R15W" };

const char *QByteRegStrings[8] = { "R8L", "R9L", "R10L", "R11L", "R12L", "R13L", "R14L", "R15L" };

const char *SignednessStrings[4] = { "UNKNOWNSIGN", "SIGNED", "UNSIGNED", "UNKNOWNSIGN" };

const char *LeaSignednessStrings[4] = { "NOFLAGUNKNOWNSIGN", "NOFLAGSIGNED", "NOFLAGUNSIGNED", "NOFLAGUNKNOWNSIGN" };

const char *SPARKFloatingPointStackRegNames[8] = { "FloatingPointStackDummy", "FloatingPointStackDummy1", "FloatingPointStackDummy1", "FloatingPointStackDummy1",
"FloatingPointStackDummy1", "FloatingPointStackDummy1", "FloatingPointStackDummy1", "FloatingPointStackDummy1" };

const char *CFTTypeStrings[20] = { "FALL_THROUGH", "BRANCH_IF_THEN", "BRANCH_IF_THEN_ELSE", "JUMP_BEFORE_ELSE",
"LOOP_BACK", "LOOP_EXIT", "LOOP_CONTINUE", "JUMP_INTO_LOOP_TEST", "JUMP_TO_DEFAULT_CASE", "CASE_BREAK_TO_FOLLOW_NODE",
"JUMP_TO_SWITCH_INDIR_JUMP", "SHORT_CIRCUIT_BRANCH", "SHORT_CIRCUIT_LOOP_EXIT", "INVERTED_LOOP_EXIT", 
"INVERTED_LOOP_BACK", "SHORT_CIRCUIT_INVERTED_LOOP_EXIT", "", "", "", ""
};

// Distinguishes subword regs from their parent regs
const char *MDGetRegNumName(STARS_regnum_t RegNum, uint16_t ByteWidth) {
	if ((STARS_x86_R_none == RegNum) || (MAX_IDA_REG < RegNum))
		return ErrorStrings[0];
	else if ((ByteWidth == 2) && (RegNum >= STARS_x86_R_ax) && (RegNum <= STARS_x86_R_di)) {
		// 16-bit registers
		return WordRegStrings[RegNum];
	}
	else if ((ByteWidth == 8) && (RegNum >= STARS_x86_R_ax) && (RegNum <= STARS_x86_R_di)) {
		// 64-bit registers
		return QWordRegStrings[RegNum];
	}
	else if ((ByteWidth < 8) && (RegNum >= STARS_x86_R_r8) && (RegNum <= STARS_x86_R_r15)) {
		if (ByteWidth == 4)
			return QDWordRegStrings[RegNum - STARS_x86_R_r8];
		else if (ByteWidth == 2)
			return QWWordRegStrings[RegNum - STARS_x86_R_r8];
		else if (ByteWidth == 1)
			return QByteRegStrings[RegNum - STARS_x86_R_r8];
		else
			return ErrorStrings[0];
	}
	else {
		return RegNames[RegNum];
	}
} // end of MDGetRegNumName()

// Distinguishes subword regs from their parent regs, uses SPARK dummy names for FP stack.
const char *MDGetSPARKRegNumName(STARS_regnum_t RegNum, uint16_t ByteWidth) {
	if ((RegNum >= STARS_x86_R_st0) && (RegNum <= STARS_x86_R_st7))
		return SPARKFloatingPointStackRegNames[RegNum - STARS_x86_R_st0];