Skip to content
Permalink
eaf6ab250d
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Go to file
 
 
Cannot retrieve contributors at this time
5019 lines (4639 sloc) 171 KB
/* ###
* IP: GHIDRA
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "coreaction.hh"
#include "condexe.hh"
#include "double.hh"
#include "subflow.hh"
/// \brief A stack equation
struct StackEqn {
int4 var1; ///< Variable with 1 coefficient
int4 var2; ///< Variable with -1 coefficient
int4 rhs; ///< Right hand side of the equation
static bool compare(const StackEqn &a,const StackEqn &b); ///< Order two equations
};
/// \brief A class that solves for stack-pointer changes across unknown sub-functions
class StackSolver {
vector<StackEqn> eqs; ///< Known equations based on operations that explicitly change the stack-pointer
vector<StackEqn> guess; ///< Guessed equations for underdetermined systems
vector<Varnode *> vnlist; ///< The indexed set of variables, one for each reference to the stack-pointer
vector<int4> companion; ///< Index of companion input for variable produced by CPUI_INDIRECT
Address spacebase; ///< Starting address of the stack-pointer
vector<int4> soln; ///< Collected solutions (corresponding to array of variables)
int4 missedvariables; ///< Number of variables for which we are missing an equation
void duplicate(void); ///< Duplicate each equation, multiplying by -1
void propagate(int4 varnum,int4 val); ///< Propagate solution for one variable to other variables
public:
void solve(void); ///< Solve the system of equations
void build(const Funcdata &data,AddrSpace *id,int4 spcbase); ///< Build the system of equations
int4 getNumVariables(void) const { return vnlist.size(); } ///< Get the number of variables in the system
Varnode *getVariable(int4 i) const { return vnlist[i]; } ///< Get the i-th Varnode variable
int4 getCompanion(int4 i) const { return companion[i]; } ///< Get the i-th variable's companion index
int4 getSolution(int4 i) const { return soln[i]; } ///< Get the i-th variable's solution
};
/// \param a is the first equation to compare
/// \param b is the second
/// \return true if the first equation comes before the second
bool StackEqn::compare(const StackEqn &a,const StackEqn &b)
{
return (a.var1<b.var1);
}
/// Given a solution for one variable, look for equations containing the variable
/// and attempt to solve for the other variable. Continue propagating new
/// solutions to other equations to find even more solutions. Populate
/// the \b soln array with the solutions.
/// \param varnum is the index of the initial variable
/// \param val is the solution for the variable
void StackSolver::propagate(int4 varnum,int4 val)
{
if (soln[varnum] != 65535) return; // This variable already specified
soln[varnum] = val;
StackEqn eqn;
vector<int4> workstack;
workstack.reserve(soln.size());
workstack.push_back(varnum);
vector<StackEqn>::iterator top;
while(!workstack.empty()) {
varnum = workstack.back();
workstack.pop_back();
eqn.var1 = varnum;
top = lower_bound(eqs.begin(),eqs.end(),eqn,StackEqn::compare);
while((top!=eqs.end())&&((*top).var1 == varnum)) {
int4 var2 = (*top).var2;
if (soln[var2] == 65535) {
soln[var2] = soln[varnum]-(*top).rhs;
workstack.push_back(var2);
}
++top;
}
}
}
void StackSolver::duplicate(void)
{
int4 size,i;
StackEqn eqn;
size = eqs.size();
for(i=0;i<size;++i) {
eqn.var1 = eqs[i].var2;
eqn.var2 = eqs[i].var1;
eqn.rhs = -eqs[i].rhs;
eqs.push_back(eqn);
}
stable_sort(eqs.begin(),eqs.end(),StackEqn::compare);
}
void StackSolver::solve(void)
{
// Use guesses to resolve subsystems not uniquely determined
int4 i,size,var1,var2,count,lastcount;
soln.clear();
soln.resize(vnlist.size(),65535); // Initialize solutions vector
duplicate(); // Duplicate and sort the equations
propagate(0,0); // We know one variable
size = guess.size();
lastcount = size+2;
do {
count = 0;
for(i=0;i<size;++i) {
var1 = guess[i].var1;
var2 = guess[i].var2;
if ((soln[var1]!=65535)&&(soln[var2]==65535))
propagate(var2,soln[var1]-guess[i].rhs);
else if ((soln[var1]==65535)&&(soln[var2]!=65535))
propagate(var1,soln[var2]+guess[i].rhs);
else if ((soln[var1]==65535)&&(soln[var2]==65535))
count += 1;
}
if (count == lastcount) break;
lastcount = count;
} while(count > 0);
}
/// Collect references to the stack-pointer as variables, and examine their defining PcodeOps
/// to determine equations and coefficient.
/// \param data is the function being analyzed
/// \param id is the \e stack address space
/// \param spcbase is the index, relative to the stack space, of the stack pointer
void StackSolver::build(const Funcdata &data,AddrSpace *id,int4 spcbase)
{
const VarnodeData &spacebasedata(id->getSpacebase(spcbase));
spacebase = Address(spacebasedata.space,spacebasedata.offset);
VarnodeLocSet::const_iterator begiter,enditer;
begiter = data.beginLoc(spacebasedata.size,spacebase);
enditer = data.endLoc(spacebasedata.size,spacebase);
while(begiter != enditer) { // All instances of the spacebase
if ((*begiter)->isFree()) break;
vnlist.push_back(*begiter);
companion.push_back(-1);
++begiter;
}
missedvariables = 0;
if (vnlist.empty()) return;
if (!vnlist[0]->isInput())
throw LowlevelError("Input value of stackpointer is not used");
vector<Varnode *>::iterator iter;
StackEqn eqn;
for(int4 i=1;i<vnlist.size();++i) {
Varnode *vn = vnlist[i];
Varnode *othervn,*constvn;
PcodeOp *op = vn->getDef();
if (op->code() == CPUI_INT_ADD) {
othervn = op->getIn(0);
constvn = op->getIn(1);
if (othervn->isConstant()) {
constvn = othervn;
othervn = op->getIn(1);
}
if (!constvn->isConstant()) { missedvariables+=1; continue; }
if (othervn->getAddr() != spacebase) { missedvariables+=1; continue; }
iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
eqn.var1 = i;
eqn.var2 = iter-vnlist.begin();
eqn.rhs = constvn->getOffset();
eqs.push_back(eqn);
}
else if (op->code() == CPUI_COPY) {
othervn = op->getIn(0);
if (othervn->getAddr() != spacebase) { missedvariables+=1; continue; }
iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
eqn.var1 = i;
eqn.var2 = iter-vnlist.begin();
eqn.rhs = 0;
eqs.push_back(eqn);
}
else if (op->code() == CPUI_INDIRECT) {
othervn = op->getIn(0);
if (othervn->getAddr() != spacebase) { missedvariables += 1; continue; }
iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
eqn.var1 = i;
eqn.var2 = iter-vnlist.begin();
companion[i] = eqn.var2;
Varnode *iopvn = op->getIn(1);
if (iopvn->getSpace()->getType()==IPTR_IOP) { // If INDIRECT is due call
PcodeOp *iop = PcodeOp::getOpFromConst(iopvn->getAddr());
FuncCallSpecs *fc = data.getCallSpecs(iop); // Look up function proto
if (fc != (FuncCallSpecs *)0) {
if (fc->getExtraPop() != ProtoModel::extrapop_unknown) { // Double check that extrapop is unknown
eqn.rhs = fc->getExtraPop(); // As the deindirect process may have filled it in
eqs.push_back(eqn);
continue;
}
}
}
eqn.rhs = 4; // Otherwise make a guess
guess.push_back(eqn);
}
else if (op->code() == CPUI_MULTIEQUAL) {
for(int4 j=0;j<op->numInput();++j) {
othervn = op->getIn(j);
if (othervn->getAddr() != spacebase) { missedvariables += 1; continue; }
iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
eqn.var1 = i;
eqn.var2 = iter-vnlist.begin();
eqn.rhs = 0;
eqs.push_back(eqn);
}
}
else if (op->code() == CPUI_INT_AND) {
// This can occur if a function aligns its stack pointer
othervn = op->getIn(0);
constvn = op->getIn(1);
if (othervn->isConstant()) {
constvn = othervn;
othervn = op->getIn(1);
}
if (!constvn->isConstant()) { missedvariables+=1; continue; }
if (othervn->getAddr() != spacebase) { missedvariables+=1; continue; }
iter = lower_bound(vnlist.begin(),vnlist.end(),othervn,Varnode::comparePointers);
eqn.var1 = i;
eqn.var2 = iter-vnlist.begin();
eqn.rhs = 0; // Treat this as a copy
eqs.push_back(eqn);
}
else
missedvariables += 1;
}
}
/// \brief Calculate stack-pointer change across \e undetermined sub-functions
///
/// If there are sub-functions for which \e extra \e pop is not explicit,
/// do full linear analysis to (attempt to) recover the values.
/// \param data is the function to analyze
/// \param stackspace is the space associated with the stack-pointer
/// \param spcbase is the index (relative to the stackspace) of the stack-pointer
void ActionStackPtrFlow::analyzeExtraPop(Funcdata &data,AddrSpace *stackspace,int4 spcbase)
{
ProtoModel *myfp = data.getArch()->evalfp_called;
if (myfp == (ProtoModel *)0)
myfp = data.getArch()->defaultfp;
if (myfp->getExtraPop()!=ProtoModel::extrapop_unknown) return;
StackSolver solver;
try {
solver.build(data,stackspace,spcbase);
} catch(LowlevelError &err) {
ostringstream s;
s << "Stack frame is not setup normally: " << err.explain;
data.warningHeader(s.str());
return;
}
if (solver.getNumVariables() == 0) return;
solver.solve(); // Solve the equations
Varnode *invn = solver.getVariable(0);
bool warningprinted = false;
for(int4 i=1;i<solver.getNumVariables();++i) {
Varnode *vn = solver.getVariable(i);
int4 soln = solver.getSolution(i);
if (soln == 65535) {
if (!warningprinted) {
data.warningHeader("Unable to track spacebase fully for "+stackspace->getName());
warningprinted = true;
}
continue;
}
PcodeOp *op = vn->getDef();
if (op->code() == CPUI_INDIRECT) {
Varnode *iopvn = op->getIn(1);
if (iopvn->getSpace()->getType()==IPTR_IOP) {
PcodeOp *iop = PcodeOp::getOpFromConst(iopvn->getAddr());
FuncCallSpecs *fc = data.getCallSpecs(iop);
if (fc != (FuncCallSpecs *)0) {
int4 soln2 = 0;
int4 comp = solver.getCompanion(i);
if (comp >= 0)
soln2 = solver.getSolution(comp);
fc->setEffectiveExtraPop(soln-soln2);
}
}
}
vector<Varnode *> paramlist;
paramlist.push_back(invn);
int4 sz = invn->getSize();
paramlist.push_back(data.newConstant(sz,soln&calc_mask(sz)));
data.opSetOpcode(op,CPUI_INT_ADD);
data.opSetAllInput(op,paramlist);
}
return;
}
/// \brief Is the given Varnode defined as a pointer relative to the stack-pointer?
///
/// Return true if -vn- is defined as the stackpointer input plus a constant (or zero)
/// This works through the general case and the special case when the constant is zero.
/// The constant value is passed-back to the caller.
/// \param spcbasein is the Varnode holding the \e input value of the stack-pointer
/// \param vn is the Varnode to check for relativeness
/// \param constval is a reference for passing back the constant offset
/// \return true if \b vn is stack relative
bool ActionStackPtrFlow::isStackRelative(Varnode *spcbasein,Varnode *vn,uintb &constval)
{
if (spcbasein == vn) {
constval = 0;
return true;
}
if (!vn->isWritten()) return false;
PcodeOp *addop = vn->getDef();
if (addop->code() != CPUI_INT_ADD) return false;
if (addop->getIn(0) != spcbasein) return false;
Varnode *constvn = addop->getIn(1);
if (!constvn->isConstant()) return false;
constval = constvn->getOffset();
return true;
}
/// \brief Adjust the LOAD where the stack-pointer alias has been recovered.
///
/// We've matched a LOAD with its matching store, now convert the LOAD op to a COPY of what was stored.
/// \param data is the function being analyzed
/// \param loadop is the LOAD op to adjust
/// \param storeop is the matching STORE op
/// \return true if the adjustment is successful
bool ActionStackPtrFlow::adjustLoad(Funcdata &data,PcodeOp *loadop,PcodeOp *storeop)
{
Varnode *vn = storeop->getIn(2);
if (vn->isConstant())
vn = data.newConstant(vn->getSize(),vn->getOffset());
else if (vn->isFree())
return false;
data.opRemoveInput(loadop,1);
data.opSetOpcode(loadop,CPUI_COPY);
data.opSetInput(loadop,vn,0);
return true;
}
/// \brief Link LOAD to matching STORE of a constant
///
/// Try to find STORE op using same stack relative pointer as a given LOAD op.
/// If we find it and the STORE stores a constant, change the LOAD to a COPY.
/// \param data is the function owning the LOAD
/// \param id is the stackspace
/// \param spcbasein is the stack-pointer
/// \param loadop is the given LOAD op
/// \param constz is the stack relative offset of the LOAD pointer
/// \return 1 if we successfully change LOAD to COPY, 0 otherwise
int4 ActionStackPtrFlow::repair(Funcdata &data,AddrSpace *id,Varnode *spcbasein,PcodeOp *loadop,uintb constz)
{
int4 loadsize = loadop->getOut()->getSize();
BlockBasic *curblock = loadop->getParent();
list<PcodeOp *>::iterator begiter = curblock->beginOp();
list<PcodeOp *>::iterator iter = loadop->getBasicIter();
for(;;) {
if (iter == begiter) {
if (curblock->sizeIn() != 1) return 0; // Can trace back to next basic block if only one path
curblock = (BlockBasic *)curblock->getIn(0);
begiter = curblock->beginOp();
iter = curblock->endOp();
continue;
}
else {
--iter;
}
PcodeOp *curop = *iter;
if (curop->isCall()) return 0; // Don't try to trace aliasing through a call
if (curop->code() == CPUI_STORE) {
Varnode *ptrvn = curop->getIn(1);
Varnode *datavn = curop->getIn(2);
uintb constnew;
if (isStackRelative(spcbasein,ptrvn,constnew)) {
if ((constnew == constz)&&(loadsize == datavn->getSize())) {
// We found the matching store
if (adjustLoad(data,loadop,curop))
return 1;
return 0;
}
else if ((constnew <= constz + (loadsize-1))&&(constnew+(datavn->getSize()-1)>=constz))
return 0;
}
else
return 0; // Any other kind of STORE we can't solve aliasing
}
else {
Varnode *outvn = curop->getOut();
if (outvn != (Varnode *)0) {
if (outvn->getSpace() == id) return 0; // Stack already traced, too late
}
}
}
}
/// \brief Find any stack pointer clogs and pass it on to the repair routines
///
/// A stack pointer \b clog is a constant addition to the stack-pointer,
/// but where the constant comes from the stack.
/// \param data is the function to analyze
/// \param id is the stack space
/// \param spcbase is the index of the stack-pointer relative to the stack space
/// \return the number of clogs that were repaired
int4 ActionStackPtrFlow::checkClog(Funcdata &data,AddrSpace *id,int4 spcbase)
{
const VarnodeData &spacebasedata(id->getSpacebase(spcbase));
Address spacebase = Address(spacebasedata.space,spacebasedata.offset);
VarnodeLocSet::const_iterator begiter,enditer;
int4 clogcount = 0;
begiter = data.beginLoc(spacebasedata.size,spacebase);
enditer = data.endLoc(spacebasedata.size,spacebase);
Varnode *spcbasein;
if (begiter == enditer) return clogcount;
spcbasein = *begiter;
++begiter;
if (!spcbasein->isInput()) return clogcount;
while(begiter != enditer) {
Varnode *outvn = *begiter;
++begiter;
if (!outvn->isWritten()) continue;
PcodeOp *addop = outvn->getDef();
if (addop->code() != CPUI_INT_ADD) continue;
Varnode *y = addop->getIn(1);
if (!y->isWritten()) continue; // y must not be a constant
Varnode *x = addop->getIn(0); // is y is not constant than x (in position 0) isn't either
uintb constx;
if (!isStackRelative(spcbasein,x,constx)) { // If x is not stack relative
x = y; // Swap x and y
y = addop->getIn(0);
if (!isStackRelative(spcbasein,x,constx)) continue; // Now maybe the new x is stack relative
}
PcodeOp *loadop = y->getDef();
if (loadop->code() == CPUI_INT_MULT) { // If we multiply
Varnode *constvn = loadop->getIn(1);
if (!constvn->isConstant()) continue;
if (constvn->getOffset() != calc_mask(constvn->getSize())) continue; // Must multiply by -1
y = loadop->getIn(0);
if (!y->isWritten()) continue;
loadop = y->getDef();
}
if (loadop->code() != CPUI_LOAD) continue;
Varnode *ptrvn = loadop->getIn(1);
uintb constz;
if (!isStackRelative(spcbasein,ptrvn,constz)) continue;
clogcount += repair(data,id,spcbasein,loadop,constz);
}
return clogcount;
}
int4 ActionStackPtrFlow::apply(Funcdata &data)
{
if (analysis_finished)
return 0;
if (stackspace == (AddrSpace *)0) {
analysis_finished = true; // No stack to do analysis on
return 0;
}
int4 numchange = checkClog(data,stackspace,0);
if (numchange > 0) {
count += 1;
}
if (numchange == 0) {
analyzeExtraPop(data,stackspace,0);
analysis_finished = true;
}
return 0;
}
/// \brief Examine the PcodeOps using the given Varnode to determine possible lane sizes
///
/// Run through the defining op and any descendant ops of the given Varnode, looking for
/// CPUI_PIECE and CPUI_SUBPIECE. Use these to determine possible lane sizes and
/// register them with the given LanedRegister object.
/// \param vn is the given Varnode
/// \param allowedLanes is used to determine if a putative lane size is allowed
/// \param checkLanes collects the possible lane sizes
void ActionLaneDivide::collectLaneSizes(Varnode *vn,const LanedRegister &allowedLanes,LanedRegister &checkLanes)
{
list<PcodeOp *>::const_iterator iter = vn->beginDescend();
int4 step = 0; // 0 = descendants, 1 = def, 2 = done
if (iter == vn->endDescend()) {
step = 1;
}
while(step < 2) {
int4 curSize; // Putative lane size
if (step == 0) {
PcodeOp *op = *iter;
++iter;
if (iter == vn->endDescend())
step = 1;
if (op->code() != CPUI_SUBPIECE) continue; // Is the big register split into pieces
curSize = op->getOut()->getSize();
}
else {
step = 2;
if (!vn->isWritten()) continue;
PcodeOp *op = vn->getDef();
if (op->code() != CPUI_PIECE) continue; // Is the big register formed from smaller pieces
curSize = op->getIn(0)->getSize();
int4 tmpSize = op->getIn(1)->getSize();
if (tmpSize < curSize)
curSize = tmpSize;
}
if (allowedLanes.allowedLane(curSize))
checkLanes.addLaneSize(curSize); // Register this possible size
}
}
/// \brief Search for a likely lane size and try to divide a single Varnode into these lanes
///
/// There are different ways to search for a lane size:
///
/// Mode 0: Collect putative lane sizes based on the local ops using the Varnode. Attempt
/// to divide based on each of those lane sizes in turn.
///
/// Mode 1: Similar to mode 0, except we allow for SUBPIECE operations that truncate to
/// variables that are smaller than the lane size.
///
/// Mode 2: Attempt to divide based on a default lane size.
/// \param data is the function being transformed
/// \param vn is the given single Varnode
/// \param lanedRegister is acceptable set of lane sizes for the Varnode
/// \param mode is the lane size search mode (0, 1, or 2)
/// \return \b true if the Varnode (and its data-flow) was successfully split
bool ActionLaneDivide::processVarnode(Funcdata &data,Varnode *vn,const LanedRegister &lanedRegister,int4 mode)
{
LanedRegister checkLanes; // Lanes we are going to try, initialized to no lanes
bool allowDowncast = (mode > 0);
if (mode < 2)
collectLaneSizes(vn,lanedRegister,checkLanes);
else {
checkLanes.addLaneSize(4); // Default lane size
}
LanedRegister::const_iterator enditer = checkLanes.end();
for(LanedRegister::const_iterator iter=checkLanes.begin();iter!=enditer;++iter) {
int4 curSize = *iter;
LaneDescription description(lanedRegister.getWholeSize(),curSize); // Lane scheme dictated by curSize
LaneDivide laneDivide(&data,vn,description,allowDowncast);
if (laneDivide.doTrace()) {
laneDivide.apply();
count += 1; // Indicate a change was made
return true;
}
}
return false;
}
int4 ActionLaneDivide::apply(Funcdata &data)
{
map<VarnodeData,const LanedRegister *>::const_iterator iter;
for(int4 mode=0;mode<3;++mode) {
bool allStorageProcessed = true;
for(iter=data.beginLaneAccess();iter!=data.endLaneAccess();++iter) {
const LanedRegister *lanedReg = (*iter).second;
Address addr = (*iter).first.getAddr();
int4 sz = (*iter).first.size;
VarnodeLocSet::const_iterator viter = data.beginLoc(sz,addr);
VarnodeLocSet::const_iterator venditer = data.endLoc(sz,addr);
bool allVarnodesProcessed = true;
while(viter != venditer) {
Varnode *vn = *viter;
if (processVarnode(data, vn, *lanedReg, mode)) {
viter = data.beginLoc(sz,addr);
venditer = data.endLoc(sz, addr); // Recalculate bounds
allVarnodesProcessed = true;
}
else {
++viter;
allVarnodesProcessed = false;
}
}
if (!allVarnodesProcessed)
allStorageProcessed = false;
}
if (allStorageProcessed) break;
}
data.clearLanedAccessMap();
return 0;
}
int4 ActionSegmentize::apply(Funcdata &data)
{
int4 numops = data.getArch()->userops.numSegmentOps();
if (numops==0) return 0;
if (localcount>0) return 0; // Only perform once
localcount = 1; // Mark as having performed once
vector<Varnode *> bindlist;
bindlist.push_back((Varnode *)0);
bindlist.push_back((Varnode *)0);
for(int4 i=0;i<numops;++i) {
SegmentOp *segdef = data.getArch()->userops.getSegmentOp(i);
if (segdef == (SegmentOp *)0) continue;
AddrSpace *spc = segdef->getSpace();
list<PcodeOp *>::const_iterator iter,enditer;
iter = data.beginOp(CPUI_CALLOTHER);
enditer = data.endOp(CPUI_CALLOTHER);
int4 uindex = segdef->getIndex();
while(iter != enditer) {
PcodeOp *segroot = *iter++;
if (segroot->isDead()) continue;
if (segroot->getIn(0)->getOffset() != uindex) continue;
if (!segdef->unify(data,segroot,bindlist)) {
ostringstream err;
err << "Segment op in wrong form at ";
segroot->getAddr().printRaw(err);
throw LowlevelError(err.str());
}
if (segdef->getNumVariableTerms()==1)
bindlist[1] = data.newConstant(4,0);
// Redefine the op as a segmentop
data.opSetOpcode(segroot,CPUI_SEGMENTOP);
data.opSetInput(segroot,data.newVarnodeSpace(spc),0);
data.opSetInput(segroot,bindlist[1],1);
data.opSetInput(segroot,bindlist[0],2);
for(int4 j=segroot->numInput()-1;j>2;--j) // Remove anything else
data.opRemoveInput(segroot,j);
count += 1;
}
}
return 0;
}
int4 ActionForceGoto::apply(Funcdata &data)
{
data.getOverride().applyForceGoto(data);
return 0;
}
int4 ActionConstbase::apply(Funcdata &data)
{
if (data.getBasicBlocks().getSize()==0) return 0; // No blocks
// Get start block, which is constructed to have nothing
// falling into it
BlockBasic *bb = (BlockBasic *)data.getBasicBlocks().getBlock(0);
int4 injectid = data.getFuncProto().getInjectUponEntry();
if (injectid >= 0) {
InjectPayload *payload = data.getArch()->pcodeinjectlib->getPayload(injectid);
data.doLiveInject(payload,bb->getStart(),bb,bb->beginOp());
}
const TrackedSet trackset( data.getArch()->context->getTrackedSet(data.getAddress()));
for(int4 i=0;i<trackset.size();++i) {
const TrackedContext &ctx(trackset[i]);
Address addr(ctx.loc.space,ctx.loc.offset);
PcodeOp *op = data.newOp(1,bb->getStart());
data.newVarnodeOut(ctx.loc.size,addr,op);
Varnode *vnin = data.newConstant(ctx.loc.size,ctx.val);
data.opSetOpcode(op,CPUI_COPY);
data.opSetInput(op,vnin,0);
data.opInsertBegin(op,bb);
}
return 0;
}
// int4 ActionCse::apply(Funcdata &data)
// {
// vector< pair<uintm,PcodeOp *> > list;
// vector<Varnode *> vlist;
// PcodeOp *op;
// list<PcodeOp *>::const_iterator iter;
// uintm hash;
// for(iter=data.op_alive_begin();iter!=data.op_alive_end();++iter) {
// op = *iter;
// hash = op->getCseHash();
// if (hash == 0) continue;
// list.push_back(pair<uintm,PcodeOp *>(hash,op));
// }
// if (list.empty()) return 0;
// cseEliminateList(data,list,vlist);
// while(!vlist.empty()) {
// count += 1; // Indicate that changes have been made
// list.clear();
// cse_build_fromvarnode(list,vlist);
// vlist.clear();
// cseEliminateList(data,list,vlist);
// }
// return 0;
// }
/// We are substituting either -out1- for -out2- OR -out2- for -out1-
/// Return true if we prefer substituting -out2- for -out1-
/// \param out1 is one output
/// \param out2 is the other output
/// \return preference
bool ActionMultiCse::preferredOutput(Varnode *out1,Varnode *out2)
{
// Prefer the output that is used in a CPUI_RETURN
list<PcodeOp *>::const_iterator iter,enditer;
enditer = out1->endDescend();
for(iter=out1->beginDescend();iter!=enditer;++iter) {
PcodeOp *op = *iter;
if (op->code() == CPUI_RETURN)
return false;
}
enditer = out2->endDescend();
for(iter=out2->beginDescend();iter!=enditer;++iter) {
PcodeOp *op = *iter;
if (op->code() == CPUI_RETURN)
return true;
}
// Prefer addrtied over register over unique
if (!out1->isAddrTied()) {
if (out2->isAddrTied())
return true;
else {
if (out1->getSpace()->getType()==IPTR_INTERNAL) {
if (out2->getSpace()->getType()!=IPTR_INTERNAL)
return true;
}
}
}
return false;
}
/// Find any matching CPUI_MULTIEQUAL that occurs before \b target that has \b in as an input.
/// Then test to see if the \b target and the recovered op are functionally equivalent.
/// \param bl is the parent block
/// \param target is the given target CPUI_MULTIEQUAL
/// \param in is the specific input Varnode
PcodeOp *ActionMultiCse::findMatch(BlockBasic *bl,PcodeOp *target,Varnode *in)
{
list<PcodeOp *>::iterator iter = bl->beginOp();
for(;;) {
PcodeOp *op = *iter;
++iter;
if (op == target) // Caught up with target, nothing else before it
break;
int4 i,numinput;
numinput = op->numInput();
for(i=0;i<numinput;++i) {
Varnode *vn = op->getIn(i);
if (vn->isWritten() && (vn->getDef()->code() == CPUI_COPY))
vn = vn->getDef()->getIn(0); // Allow for differences in copy propagation
if (vn == in) break;
}
if (i < numinput) {
int4 j;
Varnode *buf1[2];
Varnode *buf2[2];
for(j=0;j<numinput;++j) {
Varnode *in1 = op->getIn(j);
if (in1->isWritten() && (in1->getDef()->code() == CPUI_COPY))
in1 = in1->getDef()->getIn(0); // Allow for differences in copy propagation
Varnode *in2 = target->getIn(j);
if (in2->isWritten() && (in2->getDef()->code() == CPUI_COPY))
in2 = in2->getDef()->getIn(0);
if (in1 == in2) continue;
if (0!=functionalEqualityLevel(in1,in2,buf1,buf2))
break;
}
if (j==numinput) // We have found a redundancy
return op;
}
}
return (PcodeOp *)0;
}
/// Search for pairs of CPUI_MULTIEQUAL ops in \b bl that share an input.
/// If the pairs found are functionally equivalent, delete one of the two.
/// \param data is the function owning the block
/// \param bl is the specific basic block
/// return \b true if a CPUI_MULTIEQUAL was (successfully) deleted
bool ActionMultiCse::processBlock(Funcdata &data,BlockBasic *bl)
{
vector<Varnode *> vnlist;
PcodeOp *targetop = (PcodeOp *)0;
PcodeOp *pairop;
list<PcodeOp *>::iterator iter = bl->beginOp();
list<PcodeOp *>::iterator enditer = bl->endOp();
while(iter != enditer) {
PcodeOp *op = *iter;
++iter;
OpCode opc = op->code();
if (opc == CPUI_COPY) continue;
if (opc != CPUI_MULTIEQUAL) break;
int4 vnpos = vnlist.size();
int4 i;
int4 numinput = op->numInput();
for(i=0;i<numinput;++i) {
Varnode *vn = op->getIn(i);
if (vn->isWritten() && (vn->getDef()->code() == CPUI_COPY)) // Some copies may not propagate into MULTIEQUAL
vn = vn->getDef()->getIn(0); // Allow for differences in copy propagation
vnlist.push_back(vn);
if (vn->isMark()) { // If we've seen this varnode before
pairop = findMatch(bl,op,vn);
if (pairop != (PcodeOp *)0)
break;
}
}
if (i<numinput) {
targetop = op;
break;
}
for(i=vnpos;i<vnlist.size();++i)
vnlist[i]->setMark(); // Mark that we have seen this varnode
}
// Clear out any of the marks we put down
for(int4 i=0;i<vnlist.size();++i)
vnlist[i]->clearMark();
if (targetop != (PcodeOp *)0) {
Varnode *out1 = pairop->getOut();
Varnode *out2 = targetop->getOut();
if (preferredOutput(out1,out2)) {
data.totalReplace(out1,out2); // Replace pairop and out1 in favor of targetop and out2
data.opDestroy(pairop);
}
else {
data.totalReplace(out2,out1);
data.opDestroy(targetop);
}
count += 1; // Indicate that a change has taken place
return true;
}
return false;
}
int4 ActionMultiCse::apply(Funcdata &data)
{
const BlockGraph &bblocks( data.getBasicBlocks() );
int4 sz = bblocks.getSize();
for(int4 i=0;i<sz;++i) {
BlockBasic *bl = (BlockBasic *)bblocks.getBlock(i);
while(processBlock(data,bl)) {
}
}
return 0;
}
int4 ActionShadowVar::apply(Funcdata &data)
{
const BlockGraph &bblocks(data.getBasicBlocks());
BlockBasic *bl;
PcodeOp *op;
Varnode *vn;
vector<Varnode *> vnlist;
list<PcodeOp *> oplist;
uintb startoffset;
for(int4 i=0;i<bblocks.getSize();++i) {
vnlist.clear();
bl = (BlockBasic *)bblocks.getBlock(i);
// Iterator over all MULTIEQUALs in the block
// We have to check all ops in the first address
// We cannot stop at first non-MULTIEQUAL because
// other ops creep in because of multi_collapse
startoffset = bl->getStart().getOffset();
list<PcodeOp *>::iterator iter = bl->beginOp();
while(iter != bl->endOp()) {
op = *iter++;
if (op->getAddr().getOffset() != startoffset) break;
if (op->code() != CPUI_MULTIEQUAL) continue;
vn = op->getIn(0);
if (vn->isMark())
oplist.push_back(op);
else {
vn->setMark();
vnlist.push_back(vn);
}
}
for(int4 j=0;j<vnlist.size();++j)
vnlist[j]->clearMark();
}
list<PcodeOp *>::iterator oiter;
for(oiter=oplist.begin();oiter!=oplist.end();++oiter) {
op = *oiter;
PcodeOp *op2;
for(op2=op->previousOp();op2!=(PcodeOp *)0;op2=op2->previousOp()) {
if (op2->code() != CPUI_MULTIEQUAL) continue;
int4 i;
for(i=0;i<op->numInput();++i) // Check for match in each branch
if (op->getIn(i) != op2->getIn(i)) break;
if (i != op->numInput()) continue; // All branches did not match
vector<Varnode *> plist;
plist.push_back(op2->getOut());
data.opSetOpcode(op,CPUI_COPY);
data.opSetAllInput(op,plist);
count += 1;
}
}
return 0;
}
/// \brief Make a limited search from a constant for a LOAD or STORE so we can see the AddrSpace being accessed
///
/// We traverse forward through the op reading the constant, through INT_ADD, INDIRECT, COPY, and MULTIEQUAL
/// until we hit a LOAD or STORE.
/// \param vn is the constant we are searching from
/// \param op is the PcodeOp reading the constant
/// \return the discovered AddrSpace or null
AddrSpace *ActionConstantPtr::searchForLoadStore(Varnode *vn,PcodeOp *op)
{
for(int4 i=0;i<3;++i) {
switch(op->code()) {
case CPUI_INT_ADD:
case CPUI_COPY:
case CPUI_INDIRECT:
case CPUI_MULTIEQUAL:
vn = op->getOut();
op = vn->loneDescend();
break;
case CPUI_LOAD:
return Address::getSpaceFromConst(op->getIn(0)->getAddr());
case CPUI_STORE:
if (op->getIn(1) == vn)
return Address::getSpaceFromConst(op->getIn(0)->getAddr());
return (AddrSpace *)0;
default:
return (AddrSpace *)0;
}
if (op == (PcodeOp *)0) break;
}
for(list<PcodeOp *>::const_iterator iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
op = *iter;
OpCode opc = op->code();
if (opc == CPUI_LOAD)
return Address::getSpaceFromConst(op->getIn(0)->getAddr());
else if (opc == CPUI_STORE && op->getIn(1) == vn)
return Address::getSpaceFromConst(op->getIn(0)->getAddr());
}
return (AddrSpace *)0;
}
/// \brief Select the AddrSpace in which we infer with the given constant is a pointer
///
/// The constant must match the AddrSpace address size. If there is more than one possible match,
/// search for more information in the syntax tree.
/// \param vn is the given constant Varnode
/// \param op is the PcodeOp which uses the constant
/// \param spaceList is the list of address spaces to select from
/// \return the selected address space or null
AddrSpace *ActionConstantPtr::selectInferSpace(Varnode *vn,PcodeOp *op,const vector<AddrSpace *> &spaceList)
{
AddrSpace *resSpace = (AddrSpace *)0;
for(int4 i=0;i<spaceList.size();++i) {
AddrSpace *spc = spaceList[i];
int4 minSize = spc->getMinimumPtrSize();
if (minSize == 0) {
if (vn->getSize() != spc->getAddrSize())
continue;
}
else if (vn->getSize() < minSize)
continue;
if (resSpace != (AddrSpace *)0) {
AddrSpace *searchSpc = searchForLoadStore(vn,op);
if (searchSpc != (AddrSpace *)0)
resSpace = searchSpc;
break;
}
resSpace = spc;
}
return resSpace;
}
/// \brief Determine if given Varnode might be a pointer constant.
///
/// If it is a pointer, return the symbol it points to, or NULL otherwise. If it is determined
/// that the Varnode is a pointer to a specific symbol, the encoding of the full pointer is passed back.
/// Usually this is just the constant value of the Varnode, but in this case of partial pointers
/// (like \e near pointers) the full pointer may contain additional information.
/// \param spc is the address space being pointed to
/// \param vn is the given Varnode
/// \param op is the lone descendant of the Varnode
/// \param slot is the slot index of the Varnode
/// \param rampoint will hold the Address of the resolved symbol
/// \param fullEncoding will hold the full pointer encoding being passed back
/// \param data is the function being analyzed
/// \return the recovered symbol or NULL
SymbolEntry *ActionConstantPtr::isPointer(AddrSpace *spc,Varnode *vn,PcodeOp *op,int4 slot,
Address &rampoint,uintb &fullEncoding,Funcdata &data)
{
bool needexacthit;
Architecture *glb = data.getArch();
Varnode *outvn;
if (vn->getType()->getMetatype() == TYPE_PTR) { // Are we explicitly marked as a pointer
rampoint = glb->resolveConstant(spc,vn->getOffset(),vn->getSize(),op->getAddr(),fullEncoding);
needexacthit = false;
}
else {
if (vn->isTypeLock()) return (SymbolEntry *)0; // Locked as NOT a pointer
needexacthit = true;
// Check if the constant is involved in a potential pointer expression
// as the base
switch(op->code()) {
case CPUI_RETURN:
case CPUI_CALL:
case CPUI_CALLIND:
// A constant parameter or return value could be a pointer
if (!glb->infer_pointers)
return (SymbolEntry *)0;
if (slot==0)
return (SymbolEntry *)0;
break;
case CPUI_COPY:
case CPUI_INT_EQUAL:
case CPUI_INT_NOTEQUAL:
case CPUI_INT_LESS:
case CPUI_INT_LESSEQUAL:
// A comparison with a constant could be a pointer
break;
case CPUI_INT_ADD:
outvn = op->getOut();
if (outvn->getType()->getMetatype()==TYPE_PTR) {
// Is there another pointer base in this expression
if (op->getIn(1-slot)->getType()->getMetatype()==TYPE_PTR)
return (SymbolEntry *)0; // If so, we are not a pointer
// FIXME: need to fully explore additive tree
needexacthit = false;
}
else if (!glb->infer_pointers)
return (SymbolEntry *)0;
break;
case CPUI_STORE:
if (slot != 2)
return (SymbolEntry *)0;
break;
default:
return (SymbolEntry *)0;
}
// Make sure the constant is in the expected range for a pointer
if (spc->getPointerLowerBound() > vn->getOffset())
return (SymbolEntry *)0;
// Check if the constant looks like a single bit or mask
if (bit_transitions(vn->getOffset(),vn->getSize()) < 3)
return (SymbolEntry *)0;
rampoint = glb->resolveConstant(spc,vn->getOffset(),vn->getSize(),op->getAddr(),fullEncoding);
}
if (rampoint.isInvalid()) return (SymbolEntry *)0;
// Since we are looking for a global address
// Assume it is address tied and use empty usepoint
SymbolEntry *entry = data.getScopeLocal()->getParent()->queryContainer(rampoint,1,Address());
if (needexacthit&&(entry != (SymbolEntry *)0)) {
if (entry->getAddr() != rampoint)
return (SymbolEntry *)0;
}
return entry;
}
int4 ActionConstantPtr::apply(Funcdata &data)
{
if (!data.isTypeRecoveryOn()) return 0;
if (localcount >= 4) // At most 4 passes (once type recovery starts)
return 0;
localcount += 1;
VarnodeLocSet::const_iterator begiter,enditer;
Architecture *glb = data.getArch();
AddrSpace *cspc = glb->getConstantSpace();
SymbolEntry *entry;
Varnode *vn;
begiter = data.beginLoc(cspc);
enditer = data.endLoc(cspc);
while(begiter!=enditer) {
vn = *begiter++;
if (!vn->isConstant()) break; // New varnodes may get inserted between begiter and enditer
if (vn->getOffset() == 0) continue; // Never make constant 0 into spacebase
if (vn->isPtrCheck()) continue; // Have we checked this variable before
if (vn->hasNoDescend()) continue;
if (vn->isSpacebase()) continue; // Don't use constant 0 which is already spacebase
// if (vn->getSize() != rspc->getAddrSize()) continue; // Must be size of pointer
PcodeOp *op = vn->loneDescend();
if (op == (PcodeOp *)0) continue;
AddrSpace *rspc = selectInferSpace(vn, op, glb->inferPtrSpaces);
if (rspc == (AddrSpace *)0) continue;
int4 slot = op->getSlot(vn);
OpCode opc = op->code();
if (opc == CPUI_INT_ADD) {
if (op->getIn(1-slot)->isSpacebase()) continue; // Make sure other side is not a spacebase already
}
else if ((opc == CPUI_PTRSUB)||(opc==CPUI_PTRADD))
continue;
Address rampoint;
uintb fullEncoding;
entry = isPointer(rspc,vn,op,slot,rampoint,fullEncoding,data);
vn->setPtrCheck(); // Set check flag AFTER searching for symbol
if (entry != (SymbolEntry *)0) {
data.spacebaseConstant(op,slot,entry,rampoint,fullEncoding,vn->getSize());
if ((opc == CPUI_INT_ADD)&&(slot==1))
data.opSwapInput(op,0,1);
count += 1;
}
}
return 0;
}
int4 ActionDeindirect::apply(Funcdata &data)
{
FuncCallSpecs *fc;
PcodeOp *op;
Varnode *vn;
for(int4 i=0;i<data.numCalls();++i) {
fc = data.getCallSpecs(i);
op = fc->getOp();
if (op->code() != CPUI_CALLIND) continue;
vn = op->getIn(0);
while(vn->isWritten()&&(vn->getDef()->code()==CPUI_COPY))
vn = vn->getDef()->getIn(0);
if (vn->isPersist() && vn->isExternalRef()) { // Check for possible external reference
Funcdata *newfd = data.getScopeLocal()->getParent()->queryExternalRefFunction(vn->getAddr());
if (newfd != (Funcdata *)0) {
fc->deindirect(data,newfd);
count += 1;
continue;
}
}
else if (vn->isConstant()) {
AddrSpace *sp = data.getAddress().getSpace(); // Assume function is in same space as calling function
// Convert constant to a byte address in this space
uintb offset = AddrSpace::addressToByte(vn->getOffset(),sp->getWordSize());
int4 align = data.getArch()->funcptr_align;
if (align != 0) { // If we know function pointer should be aligned
offset >>= align; // Remove any encoding bits before querying for the function
offset <<= align;
}
Address codeaddr(sp,offset);
Funcdata *newfd = data.getScopeLocal()->getParent()->queryFunction(codeaddr);
if (newfd != (Funcdata *)0) {
fc->deindirect(data,newfd);
count += 1;
continue;
}
}
if (data.isTypeRecoveryOn()) {
// Check for a function pointer that has an attached prototype
Datatype *ct = op->getIn(0)->getType();
if ((ct->getMetatype()==TYPE_PTR)&&
(((TypePointer *)ct)->getPtrTo()->getMetatype()==TYPE_CODE)) {
TypeCode *tc = (TypeCode *)((TypePointer *)ct)->getPtrTo();
const FuncProto *fp = tc->getPrototype();
if (fp!=(const FuncProto *)0) {
if (!fc->isInputLocked()) {
// We use isInputLocked as a test of whether the
// function pointer prototype has been applied before
fc->forceSet(data,*fp);
data.updateOpFromSpec(fc);
count += 1;
}
}
// FIXME: If fc's input IS locked presumably this means
// that this prototype is already set, but it MIGHT mean
// we have conflicting locked prototypes
}
}
}
return 0;
}
/// Check if the given Varnode has a matching LanedRegister record. If so, add its
/// storage location to the given function's laned access list.
/// \param data is the given function
/// \param vn is the given Varnode
void ActionVarnodeProps::markLanedVarnode(Funcdata &data,Varnode *vn)
{
if (vn->isConstant()) return;
Architecture *glb = data.getArch();
const LanedRegister *lanedRegister = glb->getLanedRegister(vn->getAddr(),vn->getSize());
if (lanedRegister != (const LanedRegister *)0)
data.markLanedVarnode(vn,lanedRegister);
}
int4 ActionVarnodeProps::apply(Funcdata &data)
{
Architecture *glb = data.getArch();
bool cachereadonly = glb->readonlypropagate;
int4 minLanedSize = 1000000; // Default size meant to filter no Varnodes
if (!data.isLanedRegComplete()) {
int4 sz = glb->getMinimumLanedRegisterSize();
if (sz > 0)
minLanedSize = sz;
}
VarnodeLocSet::const_iterator iter;
Varnode *vn;
iter = data.beginLoc();
while(iter != data.endLoc()) {
vn = *iter++; // Advance iterator in case vn is deleted
if (vn->isAnnotation()) continue;
int4 vnSize = vn->getSize();
if (vnSize >= minLanedSize)
markLanedVarnode(data, vn);
if (vn->hasActionProperty()) {
if (cachereadonly&&vn->isReadOnly()) {
if (data.fillinReadOnly(vn)) // Try to replace vn with its lookup in LoadImage
count += 1;
}
else if (vn->isVolatile())
if (data.replaceVolatile(vn))
count += 1; // Try to replace vn with pcode op
}
else if (((vn->getNZMask() & vn->getConsume())==0)&&(vnSize<=sizeof(uintb))) {
// FIXME: uintb should be arbitrary precision
if (vn->isConstant()) continue; // Don't replace a constant
if (vn->isWritten()) {
if (vn->getDef()->code() == CPUI_COPY) {
if (vn->getDef()->getIn(0)->isConstant()) {
// Don't replace a COPY 0, with a zero, let
// constant propagation do that. This prevents
// an infinite recursion
if (vn->getDef()->getIn(0)->getOffset() == 0)
continue;
}
}
}
if (!vn->hasNoDescend()) {
data.totalReplaceConstant(vn,0);
count += 1;
}
}
}
data.setLanedRegGenerated();
return 0;
}
int4 ActionDirectWrite::apply(Funcdata &data)
{
VarnodeLocSet::const_iterator iter;
list<PcodeOp *>::const_iterator oiter;
Varnode *vn,*dvn;
PcodeOp *op;
vector<Varnode *> worklist;
// Collect legal inputs and other auto direct writes
for(iter=data.beginLoc();iter!=data.endLoc();++iter) {
vn = *iter;
vn->clearDirectWrite();
if (vn->isInput()) {
if (vn->isPersist()||vn->isSpacebase()) {
vn->setDirectWrite();
worklist.push_back(vn);
}
else if (data.getFuncProto().possibleInputParam(vn->getAddr(),vn->getSize())) {
vn->setDirectWrite();
worklist.push_back(vn);
}
}
else if (vn->isWritten()) {
op = vn->getDef();
if (!op->isMarker()) {
if (vn->isPersist()) {
// Anything that writes to a global variable (in a real way) is considered a direct write
vn->setDirectWrite();
worklist.push_back(vn);
}
else if (op->code() == CPUI_COPY) { // For most COPYs, do not consider it a direct write
if (vn->isStackStore()) { // But, if the original operation was really a CPUI_STORE
Varnode *invn = op->getIn(0); // Trace COPY source
if (invn->isWritten()) { // Through possible multiple COPYs
PcodeOp *curop = invn->getDef();
if (curop->code() == CPUI_COPY)
invn = curop->getIn(0);
}
if (invn->isWritten() && invn->getDef()->isMarker()) { // if source is from an INDIRECT
vn->setDirectWrite(); // then treat this as a direct write
worklist.push_back(vn);
}
}
}
else if ((op->code()!=CPUI_PIECE)&&(op->code()!=CPUI_SUBPIECE)) {
// Anything that writes to a variable in a way that isn't some form of COPY is a direct write
vn->setDirectWrite();
worklist.push_back(vn);
}
}
else if (!propagateIndirect && op->code() == CPUI_INDIRECT) {
Varnode *outvn = op->getOut();
if (op->getIn(0)->getAddr() != outvn->getAddr()) // Check if storage address changes from input to output
vn->setDirectWrite(); // Indicates an active COPY, which is a direct write
else if (outvn->isPersist()) // Value must be present at global storage at point call is made
vn->setDirectWrite(); // so treat as direct write
// We do NOT add vn to worklist as INDIRECT otherwise does not propagate
}
}
else if (vn->isConstant()) {
if (!vn->isIndirectZero()) {
vn->setDirectWrite();
worklist.push_back(vn);
}
}
}
// Let legalness taint
while(!worklist.empty()) {
vn = worklist.back();
worklist.pop_back();
for(oiter=vn->beginDescend();oiter!=vn->endDescend();++oiter) {
op = *oiter;
if (!op->isAssignment()) continue;
dvn = op->getOut();
if (!dvn->isDirectWrite()) {
dvn->setDirectWrite();
// For call based INDIRECTs, output is marked, but does not propagate depending on setting
if (propagateIndirect || op->code() != CPUI_INDIRECT || op->isIndirectStore())
worklist.push_back(dvn);
}
}
}
return 0;
}
int4 ActionExtraPopSetup::apply(Funcdata &data)
{
FuncCallSpecs *fc;
PcodeOp *op;
if (stackspace == (AddrSpace *)0) return 0; // No stack to speak of
const VarnodeData &point(stackspace->getSpacebase(0));
Address sb_addr(point.space,point.offset);
int4 sb_size = point.size;
for(int4 i=0;i<data.numCalls();++i) {
fc = data.getCallSpecs(i);
if (fc->getExtraPop() == 0) continue; // Stack pointer is undisturbed
op = data.newOp(2,fc->getOp()->getAddr());
data.newVarnodeOut(sb_size,sb_addr,op);
data.opSetInput(op,data.newVarnode(sb_size,sb_addr),0);
if (fc->getExtraPop() != ProtoModel::extrapop_unknown) { // We know exactly how stack pointer is changed
fc->setEffectiveExtraPop(fc->getExtraPop());
data.opSetOpcode(op,CPUI_INT_ADD);
data.opSetInput(op,data.newConstant(sb_size,fc->getExtraPop()),1);
data.opInsertAfter(op,fc->getOp());
}
else { // We don't know exactly, so we create INDIRECT
data.opSetOpcode(op,CPUI_INDIRECT);
data.opSetInput(op,data.newVarnodeIop(fc->getOp()),1);
data.opInsertBefore(op,fc->getOp());
}
}
return 0;
}
/// \brief Set up the parameter recovery process for a single sub-function call
///
/// If the prototype is known (locked), insert stub Varnodes
/// If the prototype is varargs (dotdotdot), set up recovery of variable Varnodes
/// \param fc is the given sub-function
/// \param data is the function being analyzed
void ActionFuncLink::funcLinkInput(FuncCallSpecs *fc,Funcdata &data)
{
bool inputlocked = fc->isInputLocked();
bool varargs = fc->isDotdotdot();
AddrSpace *spacebase = fc->getSpacebase(); // Non-zero spacebase indicates we need a stackplaceholder
ParamActive *active = fc->getActiveInput();
if ((!inputlocked)||varargs)
fc->initActiveInput();
if (inputlocked) {
PcodeOp *op = fc->getOp();
int4 numparam = fc->numParams();
bool setplaceholder = varargs;
for(int4 i=0;i<numparam;++i) {
ProtoParameter *param = fc->getParam(i);
active->registerTrial(param->getAddress(),param->getSize());
active->getTrial(i).markActive(); // Parameter is not optional
AddrSpace *spc = param->getAddress().getSpace();
uintb off = param->getAddress().getOffset();
int4 sz = param->getSize();
if (spc->getType() == IPTR_SPACEBASE) { // Param is stack relative
Varnode *loadval = data.opStackLoad(spc,off,sz,op,(Varnode *)0,false);
data.opInsertInput(op,loadval,op->numInput());
if (!setplaceholder) {
setplaceholder = true;
loadval->setSpacebasePlaceholder();
spacebase = (AddrSpace *)0; // With a locked stack parameter, we don't need a stackplaceholder
}
}
else
data.opInsertInput(op,data.newVarnode(param->getSize(),param->getAddress()),op->numInput());
}
}
if (spacebase != (AddrSpace *)0) { // If we need it, create the stackplaceholder
PcodeOp *op = fc->getOp();
int4 slot = op->numInput();
Varnode *loadval = data.opStackLoad(spacebase,0,1,op,(Varnode *)0,false);
data.opInsertInput(op,loadval,slot);
fc->setStackPlaceholderSlot(slot);
loadval->setSpacebasePlaceholder();
}
}
/// \brief Set up the return value recovery process for a single sub-function call
///
/// If the prototype is known(locked), insert an output Varnode on the call
/// If the prototype is unknown set-up the ParamActive, so that outputs will be "gathered"
/// \param fc is the given sub-function
/// \param data is the function being analyzed
void ActionFuncLink::funcLinkOutput(FuncCallSpecs *fc,Funcdata &data)
{
if (fc->isOutputLocked()) {
ProtoParameter *outparam = fc->getOutput();
Datatype *outtype = outparam->getType();
if (outtype->getMetatype() != TYPE_VOID) {
int4 sz = outparam->getSize();
Address addr = outparam->getAddress();
data.newVarnodeOut(sz,addr,fc->getOp());
VarnodeData vdata;
OpCode res = fc->assumedOutputExtension(addr,sz,vdata);
if (res == CPUI_PIECE) { // Pick an extension based on type
if (outtype->getMetatype() == TYPE_INT)
res = CPUI_INT_SEXT;
else
res = CPUI_INT_ZEXT;
}
if (res != CPUI_COPY) { // We assume the (smallsize) output is extended to a full register
PcodeOp *callop = fc->getOp();
// Create the extension operation to eliminate artifact
PcodeOp *op = data.newOp(1,callop->getAddr());
data.newVarnodeOut(vdata.size,vdata.getAddr(),op);
Varnode *invn = data.newVarnode(sz,addr);
data.opSetInput(op,invn,0);
data.opSetOpcode(op,res);
data.opInsertAfter(op,callop); // Insert immediately after the call
}
}
}
else
fc->initActiveOutput();
}
int4 ActionFuncLink::apply(Funcdata &data)
{
int4 i,size;
size = data.numCalls();
for(i=0;i<size;++i) {
funcLinkInput(data.getCallSpecs(i),data);
funcLinkOutput(data.getCallSpecs(i),data);
}
return 0;
}
int4 ActionFuncLinkOutOnly::apply(Funcdata &data)
{
int4 size = data.numCalls();
for(int4 i=0;i<size;++i)
ActionFuncLink::funcLinkOutput(data.getCallSpecs(i),data);
return 0;
}
int4 ActionParamDouble::apply(Funcdata &data)
{
for(int4 i=0;i<data.numCalls();++i) {
FuncCallSpecs *fc = data.getCallSpecs(i);
PcodeOp *op = fc->getOp();
if (fc->isInputActive()) {
ParamActive *active = fc->getActiveInput();
for(int4 j=0;j<active->getNumTrials();++j) {
const ParamTrial &paramtrial( active->getTrial(j) );
if (paramtrial.isChecked()) continue;
if (paramtrial.isUnref()) continue;
AddrSpace *spc = paramtrial.getAddress().getSpace();
if (spc->getType() != IPTR_SPACEBASE) continue;
int4 slot = paramtrial.getSlot();
Varnode *vn = op->getIn(slot);
if (!vn->isWritten()) continue;
PcodeOp *concatop = vn->getDef();
if (concatop->code() != CPUI_PIECE) continue;
if (!fc->hasModel()) continue;
Varnode *mostvn = concatop->getIn(0);
Varnode *leastvn = concatop->getIn(1);
int4 splitsize = spc->isBigEndian() ? mostvn->getSize() : leastvn->getSize();
if (fc->checkInputSplit(paramtrial.getAddress(),paramtrial.getSize(),splitsize)) {
active->splitTrial(j,splitsize);
if (spc->isBigEndian()) {
data.opInsertInput(op,mostvn,slot);
data.opSetInput(op,leastvn,slot+1);
}
else {
data.opInsertInput(op,leastvn,slot);
data.opSetInput(op,mostvn,slot+1);
}
count += 1; // Indicate that a change was made
j -= 1; // Note we decrement j here, so that we can check nested CONCATs
}
}
}
else if ((!fc->isInputLocked())&&(data.isDoublePrecisOn())) {
// Search for double precision objects that might become params
int4 max = op->numInput() - 1;
// Look for adjacent slots that form pieces of a double precision whole
for(int4 j=1;j<max;++j) {
Varnode *vn1 = op->getIn(j);
Varnode *vn2 = op->getIn(j+1);
SplitVarnode whole;
bool isslothi;
if (whole.inHandHi(vn1)) {
if (whole.getLo() != vn2) continue;
isslothi = true;
}
else if (whole.inHandLo(vn1)) {
if (whole.getHi() != vn2) continue;
isslothi = false;
}
else
continue;
if (fc->checkInputJoin(j,isslothi,vn1,vn2)) {
data.opSetInput(op,whole.getWhole(),j);
data.opRemoveInput(op,j+1);
fc->doInputJoin(j,isslothi);
max = op->numInput() - 1;
count += 1;
}
}
}
}
const FuncProto &fp( data.getFuncProto() );
if (fp.isInputLocked() && data.isDoublePrecisOn()) {
// Search for locked parameters that are being split into hi and lo components
vector<Varnode *> lovec;
vector<Varnode *> hivec;
int4 minDoubleSize = data.getArch()->getDefaultSize(); // Minimum size to consider
int4 numparams = fp.numParams();
for(int4 i=0;i<numparams;++i) {
ProtoParameter *param = fp.getParam(i);
Datatype *tp = param->getType();
type_metatype mt = tp->getMetatype();
if ((mt==TYPE_ARRAY)||(mt==TYPE_STRUCT)) continue; // Not double precision objects
Varnode *vn = data.findVarnodeInput(tp->getSize(),param->getAddress());
if (vn == (Varnode *)0) continue;
if (vn->getSize() < minDoubleSize) continue;
int4 halfSize = vn->getSize() / 2;
lovec.clear();
hivec.clear();
bool otherUse = false; // Have we seen use other than splitting into hi and lo
list<PcodeOp *>::const_iterator iter,enditer;
iter = vn->beginDescend();
enditer = vn->endDescend();
while(iter != enditer) {
PcodeOp *subop = *iter;
++iter;
if (subop->code() != CPUI_SUBPIECE) continue;
Varnode *outvn = subop->getOut();
if (outvn->getSize() != halfSize) continue;
if (subop->getIn(1)->getOffset() == 0) // Possible lo precision piece
lovec.push_back(outvn);
else if (subop->getIn(1)->getOffset() == halfSize) // Possible hi precision piece
hivec.push_back(outvn);
else {
otherUse = true;
break;
}
}
if ((!otherUse)&&(!lovec.empty())&&(!hivec.empty())) { // Seen (only) hi and lo uses
for(int4 j=0;j<lovec.size();++j) {
Varnode *piecevn = lovec[j];
if (!piecevn->isPrecisLo()) {
piecevn->setPrecisLo();
count += 1; // Indicate we made change
}
}
for(int4 j=0;j<hivec.size();++j) {
Varnode *piecevn = hivec[j];
if (!piecevn->isPrecisHi()) {
piecevn->setPrecisHi();
count += 1;
}
}
}
}
}
return 0;
}
int4 ActionActiveParam::apply(Funcdata &data)
{
int4 i;
FuncCallSpecs *fc;
AliasChecker aliascheck;
aliascheck.gather(&data,data.getArch()->getStackSpace(),true);
for(i=0;i<data.numCalls();++i) {
fc = data.getCallSpecs(i);
// An indirect function is not trimmable until
// there has been at least one simplification pass
// there has been a change to deindirect
try {
if (fc->isInputActive()) {
ParamActive *activeinput = fc->getActiveInput();
bool trimmable = ((activeinput->getNumPasses()>0)||(fc->getOp()->code() != CPUI_CALLIND));
if (!activeinput->isFullyChecked())
fc->checkInputTrialUse(data,aliascheck);
activeinput->finishPass();
if (activeinput->getNumPasses() > activeinput->getMaxPass())
activeinput->markFullyChecked();
else
count += 1; // Count a change, to indicate we still have work to do
if (trimmable && activeinput->isFullyChecked()) {
if (activeinput->needsFinalCheck())
fc->finalInputCheck();
fc->resolveModel(activeinput);
fc->deriveInputMap(activeinput);
fc->buildInputFromTrials(data);
fc->clearActiveInput();
count += 1;
}
}
}
catch(LowlevelError &err) {
ostringstream s;
s << "Error processing " << fc->getName();
PcodeOp *op = fc->getOp();
if (op != (PcodeOp *)0)
s << " called at " << op->getSeqNum();
s << ": " << err.explain;
throw LowlevelError(s.str());
}
}
return 0;
}
int4 ActionActiveReturn::apply(Funcdata &data)
{
int4 i;
FuncCallSpecs *fc;
for(i=0;i<data.numCalls();++i) {
fc = data.getCallSpecs(i);
if (fc->isOutputActive()) {
ParamActive *activeoutput = fc->getActiveOutput();
vector<Varnode *> trialvn;
fc->checkOutputTrialUse(data,trialvn);
fc->deriveOutputMap(activeoutput);
fc->buildOutputFromTrials(data,trialvn);
fc->clearActiveOutput();
count += 1;
}
}
return 0;
}
// int4 ActionParamShiftStart::apply(Funcdata &data)
// {
// int4 i;
// FuncCallSpecs *fc;
// for(i=0;i<data.numCalls();++i) {
// fc = data.getCallSpecs(i);
// fc->paramshiftModifyStart();
// }
// return 0;
// }
// int4 ActionParamShiftStop::apply(Funcdata &data)
// {
// int4 i;
// FuncCallSpecs *fc;
// if (!paramshiftsleft) return 0;
// paramshiftsleft = false;
// for(i=0;i<data.numCalls();++i) {
// fc = data.getCallSpecs(i);
// if (fc->getParamshift() != 0) {
// if (!fc->isInputActive()) {
// if (fc->paramshiftModifyStop(data))
// count += 1;
// }
// else
// paramshiftsleft = true;
// }
// }
// return 0;
// }
/// \brief Rewrite a CPUI_RETURN op to reflect a recovered output parameter.
///
/// Add a second input Varnode to the given CPUI_RETURN PcodeOp holding the return value
/// for the function at that point. Construct concatentations if there are multiple pieces
/// \param active is the output parameter description
/// \param retop is the given CPUI_RETURN
/// \param data is the function being analyzed
void ActionReturnRecovery::buildReturnOutput(ParamActive *active,PcodeOp *retop,Funcdata &data)
{
vector<Varnode *> newparam;
newparam.push_back(retop->getIn(0)); // Keep the first param (the return indirect reference)
for(int4 i=0;i<active->getNumTrials();++i) { // Gather all the used varnodes to this return in proper order
ParamTrial &curtrial(active->getTrial(i));
if (!curtrial.isUsed()) break;
if (curtrial.getSlot() >= retop->numInput()) break;
newparam.push_back(retop->getIn(curtrial.getSlot()));
}
if (newparam.size()<=2) // Easy zero or one return varnode case
data.opSetAllInput(retop,newparam);
else if (newparam.size()==3) { // Two piece concatenation case
Varnode *lovn = newparam[1];
Varnode *hivn = newparam[2];
ParamTrial &triallo( active->getTrial(0) );
ParamTrial &trialhi( active->getTrial(1) );
Address joinaddr = data.getArch()->constructJoinAddress(data.getArch()->translate,
trialhi.getAddress(),trialhi.getSize(),
triallo.getAddress(),triallo.getSize());
PcodeOp *newop = data.newOp(2,retop->getAddr());
data.opSetOpcode(newop,CPUI_PIECE);
Varnode *newwhole = data.newVarnodeOut(trialhi.getSize()+triallo.getSize(),joinaddr,newop);
data.opInsertBefore(newop,retop);
newparam.pop_back();
newparam.back() = newwhole;
data.opSetAllInput(retop,newparam);
data.opSetInput(newop,hivn,0);
data.opSetInput(newop,lovn,1);
}
else { // We may have several varnodes from a single container
// Concatenate them into a single result
newparam.clear();
newparam.push_back(retop->getIn(0));
int4 offmatch = 0;
Varnode *preexist = (Varnode *)0;
for(int4 i=0;i<active->getNumTrials();++i) {
ParamTrial &curtrial(active->getTrial(i));
if (!curtrial.isUsed()) break;
if (curtrial.getSlot() >= retop->numInput()) break;
if (preexist == (Varnode *)0) {
preexist = retop->getIn(curtrial.getSlot());
offmatch = curtrial.getOffset() + curtrial.getSize();
}
else if (offmatch == curtrial.getOffset()) {
offmatch += curtrial.getSize();
Varnode *vn = retop->getIn(curtrial.getSlot());
// Concatenate the preexisting pieces with this new piece
PcodeOp *newop = data.newOp(2,retop->getAddr());
data.opSetOpcode(newop,CPUI_PIECE);
Address addr = preexist->getAddr();
if (vn->getAddr() < addr)
addr = vn->getAddr();
Varnode *newout = data.newVarnodeOut(preexist->getSize()+vn->getSize(),addr,newop);
data.opSetInput(newop,vn,0); // Most sig part
data.opSetInput(newop,preexist,1);
data.opInsertBefore(newop,retop);
preexist = newout;
}
else
break;
}
if (preexist != (Varnode *)0)
newparam.push_back(preexist);
data.opSetAllInput(retop,newparam);
}
}
int4 ActionReturnRecovery::apply(Funcdata &data)
{
ParamActive *active = data.getActiveOutput();
if (active != (ParamActive *)0) {
PcodeOp *op;
Varnode *vn;
list<PcodeOp *>::const_iterator iter,iterend;
int4 i;
int4 maxancestor = data.getArch()->trim_recurse_max;
iterend = data.endOp(CPUI_RETURN);
AncestorRealistic ancestorReal;
for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
op = *iter;
if (op->isDead()) continue;
if (op->getHaltType() != 0) continue; // Don't evaluate special halts
for(i=0;i<active->getNumTrials();++i) {
ParamTrial &trial(active->getTrial(i));
if (trial.isChecked()) continue; // Already checked
int4 slot = trial.getSlot();
vn = op->getIn(slot);
if (ancestorReal.execute(op,slot,&trial,false))
if (data.ancestorOpUse(maxancestor,vn,op,trial))
trial.markActive(); // This varnode sees active use as a parameter
count += 1;
}
}
active->finishPass();
if (active->getNumPasses() > active->getMaxPass())
active->markFullyChecked();
if (active->isFullyChecked()) {
data.getFuncProto().deriveOutputMap(active);
iterend = data.endOp(CPUI_RETURN);
for(iter=data.beginOp(CPUI_RETURN);iter!=iterend;++iter) {
op = *iter;
if (op->isDead()) continue;
if (op->getHaltType() != 0) continue;
buildReturnOutput(active,op,data);
}
data.clearActiveOutput();
count += 1;
}
}
return 0;
}
int4 ActionRestrictLocal::apply(Funcdata &data)
{
FuncCallSpecs *fc;
list<PcodeOp *>::const_iterator iter;
PcodeOp *op;
Varnode *vn;
int4 i;
vector<EffectRecord>::const_iterator eiter,endeiter;
for(i=0;i<data.numCalls();++i) {
fc = data.getCallSpecs(i);
op = fc->getOp();
if (!fc->isInputLocked()) continue;
if (fc->getSpacebaseOffset() == FuncCallSpecs::offset_unknown) continue;
int4 numparam = fc->numParams();
for(int4 i=0;i<numparam;++i) {
ProtoParameter *param = fc->getParam(i);
Address addr = param->getAddress();
if (addr.getSpace()->getType() != IPTR_SPACEBASE) continue;
uintb off = addr.getSpace()->wrapOffset(fc->getSpacebaseOffset() + addr.getOffset());
data.getScopeLocal()->markNotMapped(addr.getSpace(),off,param->getSize(),true);
}
}
eiter = data.getFuncProto().effectBegin();
endeiter = data.getFuncProto().effectEnd();
for(;eiter!=endeiter;++eiter) { // Iterate through saved registers
if ((*eiter).getType() == EffectRecord::killedbycall) continue; // Not saved
vn = data.findVarnodeInput((*eiter).getSize(),(*eiter).getAddress());
if ((vn != (Varnode *)0)&&(vn->isUnaffected())) {
// Mark storage locations for saved registers as not mapped
// This should pickup unaffected, reload, and return_address effecttypes
for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
op = *iter;
if (op->code() != CPUI_COPY) continue;
Varnode *outvn = op->getOut();
if (!data.getScopeLocal()->isUnaffectedStorage(outvn)) // Is this where unaffected values get saved
continue;
data.getScopeLocal()->markNotMapped(outvn->getSpace(),outvn->getOffset(),outvn->getSize(),false);
}
}
}
return 0;
}
/// Count the number of inputs to \b op which have their mark set
/// \param op is the PcodeOp to count
/// \return the number of marks set
uint4 ActionLikelyTrash::countMarks(PcodeOp *op)
{
uint4 res = 0;
for(int4 i=0;i<op->numInput();++i) {
Varnode *vn = op->getIn(i);
for(;;) {
if (vn->isMark()) {
res += 1;
break;
}
if (!vn->isWritten()) break;
PcodeOp *defOp = vn->getDef();
if (defOp == op) { // We have looped all the way around
res += 1;
break;
}
else if (defOp->code() != CPUI_INDIRECT) // Chain up through INDIRECTs
break;
vn = vn->getDef()->getIn(0);
}
}
return res;
}
/// \brief Decide if the given Varnode only ever flows into CPUI_INDIRECT
///
/// Return all the CPUI_INDIRECT ops that the Varnode hits in a list.
/// Trace forward down all paths from -vn-, if we hit
/// - CPUI_INDIRECT -> trim that path and store that op in the resulting -indlist-
/// - CPUI_SUBPIECE
/// - CPUI_MULTIEQUAL
/// - CPUI_PIECE
/// - CPUI_AND -> follow through to output
/// - anything else -> consider -vn- to NOT be trash
///
/// For any CPUI_MULTIEQUAL and CPUI_PIECE that are hit, all the other inputs must be hit as well
/// \param vn is the given Varnode
/// \param indlist is the list to populate with CPUI_INDIRECT ops
/// \return \b true if all flows look like trash
bool ActionLikelyTrash::traceTrash(Varnode *vn,vector<PcodeOp *> &indlist)
{
vector<PcodeOp *> allroutes; // Keep track of merging ops (with more than 1 input)
vector<Varnode *> markedlist; // All varnodes we have visited on paths from -vn-
list<PcodeOp *>::const_iterator iter,enditer;
Varnode *outvn;
uintb val;
uint4 traced = 0;
vn->setMark();
markedlist.push_back(vn);
bool istrash = true;
while(traced < markedlist.size()) {
Varnode *curvn = markedlist[traced++];
iter = curvn->beginDescend();
enditer = curvn->endDescend();
for(;iter!=enditer;++iter) {
PcodeOp *op = *iter;
outvn = op->getOut();
switch(op->code()) {
case CPUI_INDIRECT:
if (outvn->isPersist())
istrash = false;
else if (op->isIndirectStore()) {
if (!outvn->isMark()) {
outvn->setMark();
markedlist.push_back(outvn);
}
}
else
indlist.push_back(op);
break;
case CPUI_SUBPIECE:
if (outvn->isPersist())
istrash = false;
else {
if (!outvn->isMark()) {
outvn->setMark();
markedlist.push_back(outvn);
}
}
break;
case CPUI_MULTIEQUAL:
case CPUI_PIECE:
if (outvn->isPersist())
istrash = false;
else {
if (!op->isMark()) {
op->setMark();
allroutes.push_back(op);
}
uint4 nummark = countMarks(op);
if (nummark == op->numInput()) {
if (!outvn->isMark()) {
outvn->setMark();
markedlist.push_back(outvn);
}
}
}
break;
case CPUI_INT_AND:
// If the AND is using only the topmost significant bytes then it is likely trash
if (op->getIn(1)->isConstant()) {
val = op->getIn(1)->getOffset();
uintb mask = calc_mask(op->getIn(1)->getSize());
if ((val == ((mask<<8)&mask))||(val == ((mask<<16)&mask))||(val==((mask<<32)&mask))) {
indlist.push_back(op);
break;
}
}
istrash = false;
break;
default:
istrash = false;
break;
}
if (!istrash) break;
}
if (!istrash) break;
}
for(uint4 i=0;i<allroutes.size();++i) {
if (!allroutes[i]->getOut()->isMark())
istrash = false; // Didn't see all inputs
allroutes[i]->clearMark();
}
for(uint4 i=0;i<markedlist.size();++i)
markedlist[i]->clearMark();
return istrash;
}
int4 ActionLikelyTrash::apply(Funcdata &data)
{
vector<PcodeOp *> indlist;
int4 num = data.getFuncProto().numLikelyTrash();
for(int4 j=0;j<num;++j) {
const VarnodeData &vdata( data.getFuncProto().getLikelyTrash(j) );
Varnode *vn = data.findCoveredInput(vdata.size,vdata.getAddr());
if (vn == (Varnode *)0) continue;
if (vn->isTypeLock()||vn->isNameLock()) continue;
indlist.clear();
if (!traceTrash(vn,indlist)) continue;
for(uint4 i=0;i<indlist.size();++i) {
PcodeOp *op = indlist[i];
if (op->code() == CPUI_INDIRECT) {
// Trucate data-flow through INDIRECT, turning it into indirect creation
data.opSetInput(op,data.newConstant(op->getOut()->getSize(), 0),0);
data.markIndirectCreation(op,false);
}
else if (op->code() == CPUI_INT_AND) {
data.opSetInput(op,data.newConstant(op->getIn(1)->getSize(),0),1);
}
count += 1; // Indicate we made a change
}
}
return 0;
}
int4 ActionRestructureVarnode::apply(Funcdata &data)
{
ScopeLocal *l1 = data.getScopeLocal();
bool aliasyes = data.isJumptableRecoveryOn() ? false : (numpass != 0);
l1->restructureVarnode(aliasyes);
// Note the alias calculation, may not be very good on the first pass
if (data.syncVarnodesWithSymbols(l1,false))
count += 1;
numpass += 1;
#ifdef OPACTION_DEBUG
if ((flags&rule_debug)==0) return 0;
ostringstream s;
data.getScopeLocal()->printEntries(s);
data.getArch()->printDebug(s.str());
#endif
return 0;
}
int4 ActionRestructureHigh::apply(Funcdata &data)
{
if (!data.isHighOn()) return 0;
ScopeLocal *l1 = data.getScopeLocal();
#ifdef OPACTION_DEBUG
if ((flags&rule_debug)!=0)
l1->turnOnDebug();
#endif
l1->restructureHigh();
if (data.syncVarnodesWithSymbols(l1,true))
count += 1;
#ifdef OPACTION_DEBUG
if ((flags&rule_debug)==0) return 0;
l1->turnOffDebug();
ostringstream s;
data.getScopeLocal()->printEntries(s);
data.getArch()->printDebug(s.str());
#endif
return 0;
}
int4 ActionDefaultParams::apply(Funcdata &data)
{
int4 i,size;
FuncCallSpecs *fc;
ProtoModel *evalfp = data.getArch()->evalfp_called; // Special model used when evaluating called funcs
if (evalfp == (ProtoModel *)0) // If no special evaluation
evalfp = data.getArch()->defaultfp; // Use the default model
size = data.numCalls();
for(i=0;i<size;++i) {
fc = data.getCallSpecs(i);
if (!fc->hasModel()) {
Funcdata *otherfunc = fc->getFuncdata();
if (otherfunc != (Funcdata *)0) {
fc->copy(otherfunc->getFuncProto());
if ((!fc->isModelLocked())&&(!fc->hasMatchingModel(evalfp)))
fc->setModel(evalfp);
}
else
fc->setInternal(evalfp,data.getArch()->types->getTypeVoid());
}
fc->insertPcode(data); // Insert any necessary pcode
data.updateOpFromSpec(fc);
}
return 0; // Indicate success
}
/// \brief Insert cast to output Varnode type after given PcodeOp if it is necessary
///
/// \param op is the given PcodeOp
/// \param data is the function being analyzed
/// \param castStrategy is used to determine if the cast is necessary
/// \return 1 if a cast inserted, 0 otherwise
int4 ActionSetCasts::castOutput(PcodeOp *op,Funcdata &data,CastStrategy *castStrategy)
{
Datatype *outct,*ct,*tokenct;
Varnode *vn,*outvn;
PcodeOp *newop;
bool force=false;
tokenct = op->getOpcode()->getOutputToken(op,castStrategy);
outvn = op->getOut();
if (outvn->isImplied()) {
// implied varnode must have parse type
if (outvn->getType()->getMetatype() != TYPE_PTR) // If implied varnode has an atomic (non-pointer) type
outvn->updateType(tokenct,false,false); // Ignore it in favor of the token type
else if (tokenct->getMetatype() == TYPE_PTR) { // If the token is a pointer AND implied varnode is pointer
outct = ((TypePointer *)outvn->getType())->getPtrTo();
type_metatype meta = outct->getMetatype();
// Preserve implied pointer if it points to a composite
if ((meta!=TYPE_ARRAY)&&(meta!=TYPE_STRUCT))
outvn->updateType(tokenct,false,false); // Otherwise ignore it in favor of the token type
}
if (outvn->getType() != tokenct)
force=true; // Make sure not to drop pointer type
}
if (!force) {
outct = outvn->getHigh()->getType(); // Type of result
ct = castStrategy->castStandard(outct,tokenct,false,true);
if (ct == (Datatype *)0) return 0;
}
// Generate the cast op
vn = data.newUnique(op->getOut()->getSize());
vn->updateType(tokenct,false,false);
vn->setImplied();
newop = data.newOp(1,op->getAddr());
#ifdef CPUI_STATISTICS
data.getArch()->stats->countCast();
#endif
data.opSetOpcode(newop,CPUI_CAST);
data.opSetOutput(newop,op->getOut());
data.opSetInput(newop,vn,0);
data.opSetOutput(op,vn);
data.opInsertAfter(newop,op); // Cast comes AFTER this operation
return 1;
}
/// \brief Insert cast to produce the input Varnode to a given PcodeOp if necessary
///
/// This method can also mark a Varnode as an explicit integer constant.
/// Guard against chains of casts.
/// \param op is the given PcodeOp
/// \param slot is the slot of the input Varnode
/// \param data is the function being analyzed
/// \param castStrategy is used to determine if a cast is necessary
/// \return 1 if a change is made, 0 otherwise
int4 ActionSetCasts::castInput(PcodeOp *op,int4 slot,Funcdata &data,CastStrategy *castStrategy)
{
Datatype *ct;
Varnode *vn;
PcodeOp *newop;
ct = op->getOpcode()->getInputCast(op,slot,castStrategy); // Input type expected by this operation
if (ct == (Datatype *)0) {
if (op->markExplicitUnsigned(slot)) // Decide if this input should be explicitly printed as unsigned constant
return 1;
return 0;
}
vn = op->getIn(slot);
// Check to make sure we don't have a double cast
if (vn->isWritten() && (vn->getDef()->code() == CPUI_CAST)) {
if (vn->isImplied() && (vn->loneDescend() == op)) {
vn->updateType(ct,false,false);
if (vn->getType()==ct)
return 1;
}
}
else if (vn->isConstant()) {
vn->updateType(ct,false,false);
if (vn->getType() == ct)
return 1;
}
newop = data.newOp(1,op->getAddr());
vn = data.newUniqueOut(op->getIn(slot)->getSize(),newop);
vn->updateType(ct,false,false);
vn->setImplied();
#ifdef CPUI_STATISTICS
data.getArch()->stats->countCast();
#endif
data.opSetOpcode(newop,CPUI_CAST);
data.opSetInput(newop,op->getIn(slot),0);
data.opSetInput(op,vn,slot);
data.opInsertBefore(newop,op); // Cast comes AFTER operation
return 1;
}
int4 ActionSetCasts::apply(Funcdata &data)
{
list<PcodeOp *>::const_iterator iter;
PcodeOp *op;
data.startCastPhase();
CastStrategy *castStrategy = data.getArch()->print->getCastStrategy();
// We follow data flow, doing basic blocks in dominance order
// Doing operations in basic block order
const BlockGraph &basicblocks( data.getBasicBlocks() );
for(int4 j=0;j<basicblocks.getSize();++j) {
BlockBasic *bb = (BlockBasic *)basicblocks.getBlock(j);
for(iter=bb->beginOp();iter!=bb->endOp();++iter) {
op = *iter;
if (op->notPrinted()) continue;
OpCode opc = op->code();
if (opc == CPUI_CAST) continue;
if (opc == CPUI_PTRADD) { // Check for PTRADD that no longer fits its pointer
int4 sz = (int4)op->getIn(2)->getOffset();
TypePointer *ct = (TypePointer *)op->getIn(0)->getHigh()->getType();
if ((ct->getMetatype() != TYPE_PTR)||(ct->getPtrTo()->getSize() != AddrSpace::addressToByteInt(sz, ct->getWordSize())))
data.opUndoPtradd(op,true);
}
for(int4 i=0;i<op->numInput();++i) // Do input casts first, as output may depend on input
count += castInput(op,i,data,castStrategy);
if (opc == CPUI_LOAD) {
TypePointer *ptrtype = (TypePointer *)op->getIn(1)->getHigh()->getType();
int4 valsize = op->getOut()->getSize();
if ((ptrtype->getMetatype()!=TYPE_PTR)||
(ptrtype->getPtrTo()->getSize() != valsize))
data.warning("Load size is inaccurate",op->getAddr());
}
else if (opc == CPUI_STORE) {
TypePointer *ptrtype = (TypePointer *)op->getIn(1)->getHigh()->getType();
int4 valsize = op->getIn(2)->getSize();
if ((ptrtype->getMetatype()!=TYPE_PTR)||
(ptrtype->getPtrTo()->getSize() != valsize))
data.warning("Store size is inaccurate",op->getAddr());
}
Varnode *vn = op->getOut();
if (vn == (Varnode *)0) continue;
count += castOutput(op,data,castStrategy);
}
}
return 0; // Indicate full completion
}
/// Name the Varnode which seems to be the putative switch variable for an
/// unrecovered jump-table with a special name.
/// \param data is the function being analyzed
void ActionNameVars::lookForBadJumpTables(Funcdata &data)
{
int4 numfunc = data.numCalls();
ScopeLocal *localmap = data.getScopeLocal();
for(int4 i=0;i<numfunc;++i) {
FuncCallSpecs *fc = data.getCallSpecs(i);
if (fc->isBadJumpTable()) {
PcodeOp *op = fc->getOp();
Varnode *vn = op->getIn(0);
if (vn->isImplied()&&vn->isWritten()) { // Skip any cast into the function
PcodeOp *castop = vn->getDef();
if (castop->code() == CPUI_CAST)
vn = castop->getIn(0);
}
if (vn->isFree()) continue;
Symbol *sym = vn->getHigh()->getSymbol();
if (sym == (Symbol *)0) continue;
if (sym->isNameLocked()) continue; // Override any unlocked name
if (sym->getScope() != localmap) continue; // Only name this in the local scope
string newname = "UNRECOVERED_JUMPTABLE";
sym->getScope()->renameSymbol(sym,localmap->makeNameUnique(newname));
}
}
}
/// \brief Add a recommendation to the database based on a particular sub-function parameter.
///
/// We know \b vn holds data-flow for parameter \b param, try to attach its name to \b vn's symbol.
/// We update map from \b vn to a name recommendation record.
/// If \b vn is input to multiple functions, the one whose parameter has the most specified type
/// will be preferred. If \b vn is passed to the function via a cast, this name will only be used
/// if there is no other function that takes \b vn as a parameter.
/// \param param is function prototype symbol
/// \param vn is the Varnode associated with the parameter
/// \param recmap is the recommendation map
void ActionNameVars::makeRec(ProtoParameter *param,Varnode *vn,map<HighVariable *,OpRecommend> &recmap)
{
if (!param->isNameLocked()) return;
if (param->isNameUndefined()) return;
if (vn->getSize() != param->getSize()) return;
Datatype *ct = param->getType();
if (vn->isImplied()&&vn->isWritten()) { // Skip any cast into the function
PcodeOp *castop = vn->getDef();
if (castop->code() == CPUI_CAST) {
vn = castop->getIn(0);
ct = (Datatype *)0; // Indicate that this is a less preferred name
}
}
HighVariable *high = vn->getHigh();
if (high->isAddrTied()) return; // Don't propagate parameter name to address tied variable
if (param->getName().compare(0,6,"param_")==0) return;
map<HighVariable *,OpRecommend>::iterator iter = recmap.find(high);
if (iter != recmap.end()) { // We have seen this varnode before
if (ct == (Datatype *)0) return; // Cannot override with null (casted) type
Datatype *oldtype = (*iter).second.ct;
if (oldtype != (Datatype *)0) {
if (oldtype->typeOrder(*ct) <= 0) return; // oldtype is more specified
}
(*iter).second.ct = ct;
(*iter).second.namerec = param->getName();
}
else {
OpRecommend oprec;
oprec.ct = ct;
oprec.namerec = param->getName();
recmap[high] = oprec;
}
}
/// \brief Collect potential variable names from sub-function parameters.
///
/// Run through all sub-functions with a known prototype and collect potential
/// names for current Varnodes used to pass the parameters. For these Varnodes,
/// select from among these names.
/// \param data is the function being analyzed
/// \param varlist is a list of Varnodes representing HighVariables that need names
void ActionNameVars::lookForFuncParamNames(Funcdata &data,const vector<Varnode *> &varlist)
{
int4 numfunc = data.numCalls();
if (numfunc == 0) return;
map<HighVariable *,OpRecommend> recmap;
ScopeLocal *localmap = data.getScopeLocal();
for(int4 i=0;i<numfunc;++i) { // Run through all calls to functions
FuncCallSpecs *fc = data.getCallSpecs(i);
if (!fc->isInputLocked()) continue;
PcodeOp *op = fc->getOp();
int4 numparam = fc->numParams();
if (numparam >= op->numInput())
numparam = op->numInput()-1;
for(int4 j=0;j<numparam;++j) {
ProtoParameter *param = fc->getParam(j); // Looking for a parameter
Varnode *vn = op->getIn(j+1);
makeRec(param,vn,recmap);
}
}
if (recmap.empty()) return;
map<HighVariable *,OpRecommend>::iterator iter;
for(uint4 i=0;i<varlist.size();++i) { // Do the actual naming in the original (address based) order
Varnode *vn = varlist[i];
if (vn->isFree()) continue;
if (vn->isInput()) continue; // Don't override unaffected or input naming strategy
HighVariable *high = vn->getHigh();
if (high->getNumMergeClasses() > 1) continue; // Don't inherit a name if speculatively merged
Symbol *sym = high->getSymbol();
if (sym == (Symbol *)0) continue;
if (!sym->isNameUndefined()) continue;
iter = recmap.find(high);
if (iter != recmap.end()) {
Symbol *sym = high->getSymbol();
sym->getScope()->renameSymbol(sym,localmap->makeNameUnique((*iter).second.namerec));
}
}
}
/// \brief Link symbols associated with a given \e spacebase Varnode
///
/// Look for PTRSUB ops which indicate a symbol reference within the address space
/// referred to by the \e spacebase Varnode. Decode any symbol reference and link it
/// to the appropriate HighVariable
/// \param vn is the given \e spacebase Varnode
/// \param data is the function containing the Varnode
/// \param namerec is used to store any recovered Symbol without a name
void ActionNameVars::linkSpacebaseSymbol(Varnode *vn,Funcdata &data,vector<Varnode *> &namerec)
{
if (!vn->isConstant() && !vn->isInput()) return;
list<PcodeOp *>::const_iterator iter;
for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
PcodeOp *op = *iter;
if (op->code() != CPUI_PTRSUB) continue;
Varnode *offVn = op->getIn(1);
Symbol *sym = data.linkSymbolReference(offVn);
if ((sym != (Symbol *)0) && sym->isNameUndefined())
namerec.push_back(offVn);
}
}
/// \brief Link formal Symbols to their HighVariable representative in the given Function
///
/// Run through all HighVariables for the given function and set up the explicit mapping with
/// existing Symbol objects. If there is no matching Symbol for a given HighVariable, a new
/// Symbol is created. Any Symbol that does not have a name is added to a list for further
/// name resolution.
/// \param data is the given function
/// \param namerec is the container for collecting Symbols with a name
void ActionNameVars::linkSymbols(Funcdata &data,vector<Varnode *> &namerec)
{
const AddrSpaceManager *manage = data.getArch();
VarnodeLocSet::const_iterator iter,enditer;
AddrSpace *spc;
AddrSpace *constSpace = manage->getConstantSpace();
enditer = data.endLoc(constSpace);
for(iter=data.beginLoc(constSpace);iter!=enditer;++iter) {
Varnode *curvn = *iter;
if (curvn->getSymbolEntry() != (SymbolEntry *)0)
data.linkSymbol(curvn); // Special equate symbol
else if (curvn->isSpacebase())
linkSpacebaseSymbol(curvn, data, namerec);
}
for(int4 i=0;i<manage->numSpaces();++i) { // Build a list of nameable highs
spc = manage->getSpace(i);
if (spc == (AddrSpace *)0) continue;
if (spc == constSpace) continue;
enditer = data.endLoc(spc);
for(iter=data.beginLoc(spc);iter!=enditer;++iter) {
Varnode *curvn = *iter;
if (curvn->isFree()) {
continue;
}
if (curvn->isSpacebase())
linkSpacebaseSymbol(curvn, data, namerec);
Varnode *vn = curvn->getHigh()->getNameRepresentative();
if (vn != curvn) continue; // Hit each high only once
HighVariable *high = vn->getHigh();
if (!high->hasName()) continue;
Symbol *sym = data.linkSymbol(vn);
if (sym != (Symbol *)0) { // Can we associate high with a nameable symbol
if (sym->isNameUndefined() && high->getSymbolOffset() < 0)
namerec.push_back(vn); // Add if no name, and we have a high representing the whole
if (sym->isSizeTypeLocked()) {
if (vn->getSize() == sym->getType()->getSize())
sym->getScope()->overrideSizeLockType(sym,high->getType());
}
}
}
}
}
int4 ActionNameVars::apply(Funcdata &data)
{
vector<Varnode *> namerec;
linkSymbols(data, namerec);
data.getScopeLocal()->recoverNameRecommendationsForSymbols(); // Make sure recommended names hit before subfunc
lookForBadJumpTables(data);
lookForFuncParamNames(data,namerec);
int4 base = 1;
for(uint4 i=0;i<namerec.size();++i) {
Varnode *vn = namerec[i];
Symbol *sym = vn->getHigh()->getSymbol();
if (sym->isNameUndefined()) {
Scope *scope = sym->getScope();
string newname = scope->buildDefaultName(sym, base, vn);
scope->renameSymbol(sym,newname);
}
}
data.getScopeLocal()->assignDefaultNames(base);
return 0;
}
/// If the given Varnode is defined by CPUI_NEW, return -2 indicating it should be explicit
/// and that it needs special printing.
/// \param vn is the given Varnode
/// \param maxref is the maximum number of references to consider before forcing explicitness
/// \return -1 if given Varnode should be marked explicit, the number of descendants otherwise
int4 ActionMarkExplicit::baseExplicit(Varnode *vn,int4 maxref)
{
list<PcodeOp *>::const_iterator iter;
PcodeOp *def = vn->getDef();
if (def == (PcodeOp *)0) return -1;
if (def->isMarker()) return -1;
if (def->isCall()) {
if ((def->code() == CPUI_NEW)&&(def->numInput() == 1))
return -2; // Explicit, but may need special printing
return -1;
}
HighVariable *high = vn->getHigh();
if ((high!=(HighVariable *)0)&&(high->numInstances()>1)) return -1; // Must not be merged at all
if (vn->isAddrTied()) { // We need to see addrtied as explicit because pointers may reference it
if (def->code() == CPUI_SUBPIECE) {
Varnode *vin = def->getIn(0);
if (vin->isAddrTied()) {
if (vn->overlap(*vin) == def->getIn(1)->getOffset())
return -1; // Should be explicit, will be a copymarker and not printed
}
}
// (Part of) an addrtied location into itself is hopefully implicit
bool shouldbeimplicit = true;
for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
PcodeOp *op = *iter;
if ((op->code()!=CPUI_INT_ZEXT)&&(op->code()!=CPUI_PIECE)) {
shouldbeimplicit = false;
break;
}
Varnode *vnout = op->getOut();
if ((!vnout->isAddrTied())||(0!=vnout->contains(*vn))) {
shouldbeimplicit = false;
break;
}
}
if (!shouldbeimplicit) return -1;
}
else if (vn->isMapped()) {
// If NOT addrtied but is still mapped, there must be either a first use (register) mapping
// or a dynamic mapping causing the bit to be set. In either case, it should probably be explicit
return -1;
}
if (vn->hasNoDescend()) return -1; // Must have at least one descendant
if (def->code() == CPUI_PTRSUB) { // A dereference
Varnode *basevn = def->getIn(0);
if (basevn->isSpacebase()) { // of a spacebase
if (basevn->isConstant() || basevn->isInput())
maxref = 1000000; // Should always be implicit, so remove limit on max references
}
}
int4 desccount = 0;
for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
PcodeOp *op = *iter;
if (op->isMarker()) return -1;
desccount += 1;
if (desccount > maxref) return -1; // Must not exceed max descendants
}
return desccount;
}
/// Look for certain situations where one Varnode with multiple descendants has one descendant who also has
/// multiple descendants. This routine is handed the list of Varnodes with multiple descendants;
/// These all must already have their mark set.
/// For the situations we can find with one flowing into another, mark the top Varnode
/// as \e explicit.
/// \param multlist is the list Varnodes with multiple descendants
/// \return the number Varnodes that were marked as explicit
int4 ActionMarkExplicit::multipleInteraction(vector<Varnode *> &multlist)
{
vector<Varnode *> purgelist;
for(int4 i=0;i<multlist.size();++i) {
Varnode *vn = multlist[i]; // All elements in this list should have a defining op
PcodeOp *op = vn->getDef();
OpCode opc = op->code();
if (op->isBoolOutput() || (opc == CPUI_INT_ZEXT) || (opc == CPUI_INT_SEXT) || (opc == CPUI_PTRADD)) {
int4 maxparam = 2;
if (op->numInput() < maxparam)
maxparam = op->numInput();
Varnode *topvn = (Varnode *)0;
for(int4 j=0;j<maxparam;++j) {
topvn = op->getIn(j);
if (topvn->isMark()) { // We have a "multiple" interaction between -topvn- and -vn-
OpCode topopc = CPUI_COPY;
if (topvn->isWritten()) {
if (topvn->getDef()->isBoolOutput())
continue; // Try not to make boolean outputs explicit
topopc = topvn->getDef()->code();
}
if (opc == CPUI_PTRADD) {
if (topopc == CPUI_PTRADD)
purgelist.push_back(topvn);
}
else
purgelist.push_back(topvn);
}
}
}
}
for(int4 i=0;i<purgelist.size();++i) {
Varnode *vn = purgelist[i];
vn->setExplicit();
vn->clearImplied();
vn->clearMark();
}
return purgelist.size();
}
/// Record the Varnode just encountered and set-up the next (backward) edges to traverse.
/// \param v is the Varnode just encountered
ActionMarkExplicit::OpStackElement::OpStackElement(Varnode *v)
{
vn = v;
slot = 0;
slotback = 0;
if (v->isWritten()) {
OpCode opc = v->getDef()->code();
if (opc == CPUI_LOAD) {
slot = 1;
slotback = 2;
}
else if (opc == CPUI_PTRADD)
slotback = 1; // Don't traverse the multiplier slot
else
slotback = v->getDef()->numInput();
}
}
/// Count the number of terms in the expression making up \b vn. If
/// there are more than \b max terms, mark \b vn as \e explicit.
/// The given Varnode is already assumed to have multiple descendants.
/// We do a depth first traversal along op inputs, to recursively
/// calculate the number of explicit terms in an expression.
/// \param vn is the given Varnode
/// \param max is the maximum number of terms to allow
void ActionMarkExplicit::processMultiplier(Varnode *vn,int4 max)
{
vector<OpStackElement> opstack;
Varnode *vncur;
int4 finalcount = 0;
opstack.push_back(vn);
do {
vncur = opstack.back().vn;
bool isaterm = vncur->isExplicit() || (!vncur->isWritten());
if (isaterm || (opstack.back().slotback<=opstack.back().slot)) { // Trimming condition
if (isaterm) {
if (!vncur->isSpacebase()) // Don't count space base
finalcount += 1;
}
if (finalcount > max) {
vn->setExplicit(); // Make this variable explicit
vn->clearImplied();
return;
}
opstack.pop_back();
}
else {
PcodeOp *op = vncur->getDef();
Varnode *newvn = op->getIn(opstack.back().slot++);
if (newvn->isMark()) { // If an ancestor is marked(also possible implied with multiple descendants)
vn->setExplicit(); // then automatically consider this to be explicit
vn->clearImplied();
}
opstack.push_back(newvn);
}
} while(!opstack.empty());
}
/// Assume \b vn is produced via a CPUI_NEW operation. If it is immediately fed to a constructor,
/// set special printing flags on the Varnode.
/// \param data is the function being analyzed
/// \param vn is the given Varnode
void ActionMarkExplicit::checkNewToConstructor(Funcdata &data,Varnode *vn)
{ PcodeOp *op = vn->getDef();
BlockBasic *bb = op->getParent();
PcodeOp *firstuse = (PcodeOp *)0;
list<PcodeOp *>::const_iterator iter;
for(iter=vn->beginDescend();iter!=vn->endDescend();++iter) {
PcodeOp *curop = *iter;
if (curop->getParent() != bb) continue;
if (firstuse == (PcodeOp *)0)
firstuse = curop;
else if (curop->getSeqNum().getOrder() < firstuse->getSeqNum().getOrder())
firstuse = curop;
else if (curop->code() == CPUI_CALLIND) {
Varnode *ptr = curop->getIn(0);
if (ptr->isWritten()) {
if (ptr->getDef() == firstuse)
firstuse = curop;
}
}
}
if (firstuse == (PcodeOp *)0) return;
if (!firstuse->isCall()) return;
if (firstuse->getOut() != (Varnode *)0) return;
if (firstuse->numInput() < 2) return; // Must have at least 1 parameter (plus destination varnode)
if (firstuse->getIn(1) != vn) return; // First parameter must result of new
// if (!fc->isConstructor()) return; // Function must be a constructor
data.opMarkSpecialPrint(firstuse); // Mark call to print the new operator as well
data.opMarkNonPrinting(op); // Don't print the new operator as stand-alone operation
}
int4 ActionMarkExplicit::apply(Funcdata &data)
{
VarnodeDefSet::const_iterator viter,enditer;
vector<Varnode *> multlist; // implied varnodes with >1 descendants
int4 maxref;
maxref = data.getArch()->max_implied_ref;
enditer = data.beginDef(0); // Cut out free varnodes
for(viter=data.beginDef();viter!=enditer;++viter) {
Varnode *vn = *viter;
int4 desccount = baseExplicit(vn,maxref);
if (desccount < 0) {
vn->setExplicit();
count += 1;
if (desccount < -1)
checkNewToConstructor(data,vn);
}
else if (desccount > 1) { // Keep track of possible implieds with more than one descendant
vn->setMark();
multlist.push_back(vn);
}
}
count += multipleInteraction(multlist);
int4 maxdup = data.getArch()->max_term_duplication;
for(int4 i=0;i<multlist.size();++i) {
Varnode *vn = multlist[i];
if (vn->isMark()) // Mark may have been cleared by multipleInteraction
processMultiplier(vn,maxdup);
}
for(int4 i=0;i<multlist.size();++i)
multlist[i]->clearMark();
return 0;
}
/// Return false only if one Varnode is obtained by adding non-zero thing to another Varnode.
/// The order of the Varnodes is not important.
/// \param vn1 is the first Varnode
/// \param vn2 is the second Varnode
/// \return false if the additive relationship holds
bool ActionMarkImplied::isPossibleAliasStep(Varnode *vn1,Varnode *vn2)
{
Varnode *var[2];
var[0] = vn1;
var[1] = vn2;
for(int4 i=0;i<2;++i) {
Varnode *vncur = var[i];
if (!vncur->isWritten()) continue;
PcodeOp *op = vncur->getDef();
OpCode opc = op->code();
if ((opc!=CPUI_INT_ADD)&&(opc!=CPUI_PTRSUB)&&(opc!=CPUI_PTRADD)&&(opc!=CPUI_INT_XOR)) continue;
if (var[1-i] != op->getIn(0)) continue;
if (op->getIn(1)->isConstant()) return false;
}
return true;
}
/// Return false \b only if we can guarantee two Varnodes have different values.
/// \param vn1 is the first Varnode
/// \param vn2 is the second Varnode
/// \param depth is the maximum level to recurse
/// \return true if its possible the Varnodes hold the same value
bool ActionMarkImplied::isPossibleAlias(Varnode *vn1,Varnode *vn2,int4 depth)
{
if (vn1 == vn2) return true; // Definite alias
if ((!vn1->isWritten())||(!vn2->isWritten())) {
if (vn1->isConstant() && vn2->isConstant())
return (vn1->getOffset()==vn2->getOffset()); // FIXME: these could be NEAR each other and still have an alias
return isPossibleAliasStep(vn1,vn2);
}
if (!isPossibleAliasStep(vn1,vn2))
return false;
Varnode *cvn1,*cvn2;
PcodeOp *op1 = vn1->getDef();
PcodeOp *op2 = vn2->getDef();
OpCode opc1 = op1->code();
OpCode opc2 = op2->code();
int4 mult1 = 1;
int4 mult2 = 1;
if (opc1 == CPUI_PTRSUB)
opc1 = CPUI_INT_ADD;
else if (opc1 == CPUI_PTRADD) {
opc1 = CPUI_INT_ADD;
mult1 = (int4) op1->getIn(2)->getOffset();
}
if (opc2 == CPUI_PTRSUB)
opc2 = CPUI_INT_ADD;
else if (opc2 == CPUI_PTRADD) {
opc2 = CPUI_INT_ADD;
mult2 = (int4) op2->getIn(2)->getOffset();
}
if (opc1 != opc2) return true;
if (depth == 0) return true; // Couldn't find absolute difference
depth -= 1;
switch(opc1) {
case CPUI_COPY:
case CPUI_INT_ZEXT:
case CPUI_INT_SEXT:
case CPUI_INT_2COMP:
case CPUI_INT_NEGATE:
return isPossibleAlias(op1->getIn(0),op2->getIn(0),depth);
case CPUI_INT_ADD:
cvn1 = op1->getIn(1);
cvn2 = op2->getIn(1);
if (cvn1->isConstant() && cvn2->isConstant()) {
uintb val1 = mult1 * cvn1->getOffset();
uintb val2 = mult2 * cvn2->getOffset();
if (val1 == val2)
return isPossibleAlias(op1->getIn(0),op2->getIn(0),depth);
return !functionalEquality(op1->getIn(0),op2->getIn(0));
}
if (mult1 != mult2) return true;
if (functionalEquality(op1->getIn(0),op2->getIn(0)))
return isPossibleAlias(op1->getIn(1),op2->getIn(1),depth);
if (functionalEquality(op1->getIn(1),op2->getIn(1)))
return isPossibleAlias(op1->getIn(0),op2->getIn(0),depth);
if (functionalEquality(op1->getIn(0),op2->getIn(1)))
return isPossibleAlias(op1->getIn(1),op2->getIn(0),depth);
if (functionalEquality(op1->getIn(1),op2->getIn(0)))
return isPossibleAlias(op1->getIn(0),op2->getIn(1),depth);
break;
default:
break;
}
return true;
}
/// Marking a Varnode as \e implied causes the input Varnodes to its defining op to propagate farther
/// in the output. This may cause eventual variables to hold different values at the same
/// point in the code. Any input must test that its propagated Cover doesn't intersect its current Cover.
/// \param data is the function being analyzed
/// \param vn is the given Varnode
/// \return \b true if there is a Cover violation
bool ActionMarkImplied::checkImpliedCover(Funcdata &data,Varnode *vn)
{
PcodeOp *op,*storeop,*callop;
Varnode *defvn;
int4 i;
op = vn->getDef();
if (op->code() == CPUI_LOAD) { // Check for loads crossing stores
list<PcodeOp *>::const_iterator oiter,iterend;
iterend = data.endOp(CPUI_STORE);
for(oiter=data.beginOp(CPUI_STORE);oiter!=iterend;++oiter) {
storeop = *oiter;
if (storeop->isDead()) continue;
if (vn->getCover()->contain(storeop,2)) {
// The LOAD crosses a STORE. We are cavalier
// and let it through unless we can verify
// that the pointers are actually the same
if (storeop->getIn(0)->getOffset() == op->getIn(0)->getOffset()) {
// if (!functionalDifference(storeop->getIn(1),op->getIn(1),2)) return false;
if (isPossibleAlias(storeop->getIn(1),op->getIn(1),2)) return false;
}
}
}
}
if (op->isCall() || (op->code() == CPUI_LOAD)) { // loads crossing calls
for(i=0;i<data.numCalls();++i) {
callop = data.getCallSpecs(i)->getOp();
if (vn->getCover()->contain(callop,2)) return false;
}
}
for(i=0;i<op->numInput();++i) {
defvn = op->getIn(i);
if (defvn->isConstant()) continue;
if (data.getMerge().inflateTest(defvn,vn->getHigh())) // Test for intersection
return false;
}
return true;
}
int4 ActionMarkImplied::apply(Funcdata &data)
{
VarnodeLocSet::const_iterator viter;
list<PcodeOp *>::const_iterator oiter;
Varnode *vn,*vncur,*defvn,*outvn;
PcodeOp *op;
vector<DescTreeElement> varstack; // Depth first varnode traversal stack
for(viter=data.beginLoc();viter!=data.endLoc();++viter) {
vn = *viter;
if (vn->isFree()) continue;
if (vn->isExplicit()) continue;
if (vn->isImplied()) continue;
varstack.push_back(vn);
do {
vncur = varstack.back().vn;
if (varstack.back().desciter == vncur->endDescend()) {
// All descendants are traced first, try to make vncur implied
count += 1; // Will be marked either explicit or implied
if (!checkImpliedCover(data,vncur)) // Can this variable be implied
vncur->setExplicit(); // if not, mark explicit
else {
vncur->setImplied(); // Mark as implied
op = vncur->getDef();
// setting the implied type is now taken care of by ActionSetCasts
// vn->updatetype(op->outputtype_token(),false,false); // implied must have parsed type
// Back propagate varnode's cover to inputs of defining op
for(int4 i=0;i<op->numInput();++i) {
defvn = op->getIn(i);
if (!defvn->hasCover()) continue;
data.getMerge().inflate(defvn,vncur->getHigh());
}
}
varstack.pop_back();
}
else {
outvn = (*varstack.back().desciter++)->getOut();
if (outvn != (Varnode *)0) {
if ((!outvn->isExplicit())&&(!outvn->isImplied()))
varstack.push_back(outvn);
}
}
} while(!varstack.empty());
}
return 0;
}
int4 ActionUnreachable::apply(Funcdata &data)
{ // Detect unreachable blocks and remove
if (data.removeUnreachableBlocks(