SMPStaticAnalyzer.cpp

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

//
// SMPStaticAnalyzer.cpp
//
// This plugin performs the static analyses needed for the SMP project
//   (Software Memory Protection).
//

using namespace std;

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

#include <string>
#include <ctime>

#include "SMPDBInterface.h"
#include "SMPStaticAnalyzer.h"
#include "SMPDataFlowAnalysis.h"
#include "SMPProgram.h"
#include "SMPFunction.h"
#include "SMPInstr.h"
#include "ProfilerInformation.h"

#define SMP_DEBUG_DELAY 0   // for setting an early breakpoint

// Set to 1 for debugging output
#define SMP_DEBUG 1
#define SMP_DEBUG2 0   // verbose
#define SMP_DEBUG3 0   // verbose
#define SMP_DEBUG_MEM 0 // print memory operands
#define SMP_DEBUG_TYPE0 0 // Output instr info for OptType = 0
#define SMP_DEBUG_CHUNKS 0 // restructuring tail chunks, shared chunks, etc.
#define SMP_DEBUG_DATA_ONLY 0  // Find & fix data addresses in code segments

// Set to 1 when doing a binary search using SMP_DEBUG_COUNT to find
//  which function is causing a problem.
#define SMP_BINARY_DEBUG 0
#define SMP_DEBUG_COUNT 356  // How many funcs to process in problem search
int FuncsProcessed = 0;

#define SMP_FIXUP_IDB 0  // Try to fix the IDA database?
#define SMP_DEBUG_FIXUP_IDB 0  // debugging output for FixupIDB chain
#define SMP_FIND_ORPHANS 1  // find code outside of functions
#define SMP_DEBUG_CODE_ORPHANS 1 // Detect whether we are causing code to be orphaned

#define SMP_IDAP_RUN_DELAY 0  // Delay in IDAP_run() so we can attach debugger to process.

#define STARS_GENERATE_ASM_FILE 1  // Generate ASM file at end of processing?
#define STARS_GENERATE_DIF_FILE STARS_SCCP_CONVERT_UNREACHABLE_BLOCKS  // If we optimize, generate DIF file

static SMPProgram *CurrProg = NULL;
STARS_Interface_t* global_stars_interface=NULL;

#if SMP_DEBUG_CODE_ORPHANS
set<ea_t> CodeOrphans;
#endif

// Lock prefix for x86 code; jumping around this prefix conditionally looks like jumping
//  into the middle of an instruction to IDA Pro, causing it to not collect instructions
//  into a procedure. We replace these bytes with no-op opcodes because none of our analyses
//  care about LOCK prefices. We store the addresses where we have done the replacement in a 
//  set in case we ever care.
#define X86_LOCK_PREFIX 0xF0
set<ea_t> LockPreficesRemoved; // Addresses where x86 LOCK prefix byte was turned into a no-op by STARS_custom_ana() callback.
static unsigned long CustomAnaCallCount = 0;

// Define optimization categories for instructions.
int OptCategory[NN_last + 1];
// Initialize the OptCategory[] array.
void InitOptCategory(void);

// Flag to force reduced analysis so we don't run out of virtual memory
bool STARS_PerformReducedAnalysis;

// Indentation level when emitting SPARK Ada translation of the RTLs.
unsigned short STARS_SPARK_IndentCount;

// Record which opcodes change the stack pointer, and by how many
//  bytes up (reduction in stack size for stacks that grow downward)
//  or down (increase in stack size for stacks that grow downward).
sval_t StackAlteration[NN_last + 1];
// Initialize the StackAlteration[] array.
void InitStackAlteration(void);

// Keep statistics on how many instructions we saw in each optimization
//  category, and how many optimizing annotations were emitted for
//  each category.
int OptCount[LAST_OPT_CATEGORY + 1];
int AnnotationCount[LAST_OPT_CATEGORY + 1];

// Unique data referent number to use in data annotations.
unsigned long DataReferentID;

// Debugging counters for analyzing memory usage.
unsigned long UnusedInstrCount;
unsigned long UnusedBlockCount;
unsigned long UnusedStructCount;
unsigned long UnusedIntCount;

// Counters for dead metadata analysis.
unsigned long DeadMetadataCount;
unsigned long LiveMetadataCount;

// Counters for indirect jump resolution.
unsigned long ResolvedIndirectJumpCount;
unsigned long UnresolvedIndirectJumpCount;

// Counters for measuring SCCP success in finding constant DEFs.
unsigned long ConstantDEFCount;
unsigned long AlwaysTakenBranchCount;
unsigned long NeverTakenBranchCount;

// Counters for accessing less than machine register width.
unsigned long SubwordRegCount;
unsigned long SubwordMemCount;
unsigned long SubwordAddressRegCount;
unsigned long SPARKOperandCount; // total operands printed

#if SMP_COUNT_MEMORY_ALLOCATIONS
// Counters for analyzing memory use for allocated and used objects.
unsigned long SMPInstCount;
unsigned long SMPBlockCount;
unsigned long SMPFuncCount;
unsigned long SMPGlobalVarCount;
unsigned long SMPLocalVarCount;
unsigned long SMPDefUseChainCount;
unsigned long SMPInstBytes;
unsigned long SMPDefUseChainBytes;
#endif

#if SMP_MEASURE_NUMERIC_ANNOTATIONS
unsigned long NumericAnnotationsCount12; // cases 1 and 2
unsigned long NumericAnnotationsCount3;  // case 3
unsigned long TruncationAnnotationsCount; // case 4
unsigned long SignednessWithoutTruncationCount; // case 5
unsigned long LeaInstOverflowCount; // case 6
unsigned long WidthDoublingTruncationCount; // case 7
unsigned long BenignOverflowInstCount;
unsigned long BenignOverflowDefCount;
unsigned long SuppressStackPtrOverflowCount;
unsigned long SuppressLiveFlagsOverflowCount;
unsigned long LiveMultiplyBitsCount;
unsigned long BenignTruncationCount;
unsigned long SuppressTruncationRegPiecesAllUsed;
unsigned long SuppressSignednessOnTruncation;
#endif

#if STARS_SCCP_GATHER_STATISTICS
// Counters for analyzing Sparse Conditional Constant Propagation effectiveness.
unsigned long SCCPFuncsWithArgWriteCount;
unsigned long SCCPFuncsWithConstantArgWriteCount;
unsigned long SCCPOutgoingArgWriteCount;
unsigned long SCCPConstantOutgoingArgWriteCount;
#endif

// Counter for max # of basic blocks seen in one function.
unsigned long STARS_MaxBlockCount;

// Is the binary a 32-bit, 64-bit, etc. instruction set architecture
size_t STARS_ISA_Bitwidth;
size_t STARS_ISA_Bytewidth;
char STARS_ISA_dtyp;
int STARS_MD_LAST_SAVED_REG_NUM;


// The types of data objects based on their first operand flags.
const char *DataTypes[] = { "VOID", "NUMHEX", "NUMDEC", "CHAR",
		"SEG", "OFFSET", "NUMBIN", "NUMOCT", "ENUM", "FORCED", 
		"STRUCTOFFSET", "STACKVAR", "NUMFLOAT", "UNKNOWN", 
		"UNKNOWN", "UNKNOWN", 0};

// Filename (not including path) of executable being analyzed.
char RootFileName[MAXSTR];