1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
/* ###
* 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.
*/
/// \file subflow.hh
/// \brief Classes for reducing/splitting Varnodes containing smaller logical values
#ifndef __SUBVARIABLE_FLOW__
#define __SUBVARIABLE_FLOW__
#include "funcdata.hh"
/// \brief Class for shrinking big Varnodes carrying smaller logical values
///
/// Given a root within the syntax tree and dimensions
/// of a logical variable, this class traces the flow of this
/// logical variable through its containing Varnodes. It then
/// creates a subgraph of this flow, where there is a correspondence
/// between nodes in the subgraph and nodes in the original graph
/// containing the logical variable. When doReplacement is called,
/// this subgraph is duplicated as a new separate piece within the
/// syntax tree. Ops are replaced to reflect the manipulation of
/// of the logical variable, rather than the containing variable.
/// Operations in the original graph which pluck out the logical
/// variable from the containing variable, are replaced with copies
/// from the corresponding node in the new section of the graph,
/// which frequently causes the operations on the original container
/// Varnodes to becomes dead code.
class SubvariableFlow {
class ReplaceOp;
/// \brief Placeholder node for Varnode holding a smaller logical value
class ReplaceVarnode {
friend class SubvariableFlow;
Varnode *vn; ///< Varnode being shrunk
Varnode *replacement; ///< The new smaller Varnode
uintb mask; ///< Bits making up the logical sub-variable
uintb val; ///< Value of constant (when vn==NULL)
ReplaceOp *def; ///< Defining op for new Varnode
};
/// \brief Placeholder node for PcodeOp operating on smaller logical values
class ReplaceOp {
friend class SubvariableFlow;
PcodeOp *op; ///< op getting paralleled
PcodeOp *replacement; ///< The new op
OpCode opc; ///< Opcode of the new op
int4 numparams; ///< Number of parameters in (new) op
ReplaceVarnode *output; ///< Varnode output
vector<ReplaceVarnode *> input; ///< Varnode inputs
};
/// \brief Operation with a new logical value as (part of) input, but output Varnode is unchanged
class PatchRecord {
friend class SubvariableFlow;
/// The possible types of patches on ops being performed
enum patchtype {
copy_patch, ///< Turn op into a COPY of the logical value
compare_patch, ///< Turn compare op inputs into logical values
parameter_patch, ///< Convert a CALL/CALLIND/RETURN/BRANCHIND parameter into logical value
extension_patch, ///< Convert op into something that copies/extends logical value, adding zero bits
push_patch ///< Convert an operator output to the logical value
};
patchtype type; ///< The type of \b this patch
PcodeOp *patchOp; ///< Op being affected
ReplaceVarnode *in1; ///< The logical variable input
ReplaceVarnode *in2; ///< (optional second parameter)
int4 slot; ///< slot being affected or other parameter
};
int4 flowsize; ///< Size of the logical data-flow in bytes
int4 bitsize; ///< Number of bits in logical variable
bool returnsTraversed; ///< Have we tried to flow logical value across CPUI_RETURNs
bool aggressive; ///< Do we "know" initial seed point must be a sub variable
bool sextrestrictions; ///< Check for logical variables that are always sign extended into their container
Funcdata *fd; ///< Containing function
map<Varnode *,ReplaceVarnode> varmap; ///< Map from original Varnodes to the overlaying subgraph nodes
list<ReplaceVarnode> newvarlist; ///< Storage for subgraph variable nodes
list<ReplaceOp> oplist; ///< Storage for subgraph op nodes
list<PatchRecord> patchlist; ///< Operations getting patched (but with no flow thru)
vector<ReplaceVarnode *> worklist; ///< Subgraph variable nodes still needing to be traced
int4 pullcount; ///< Number of instructions pulling out the logical value
static int4 doesOrSet(PcodeOp *orop,uintb mask);
static int4 doesAndClear(PcodeOp *andop,uintb mask);
Address getReplacementAddress(ReplaceVarnode *rvn) const;
ReplaceVarnode *setReplacement(Varnode *vn,uintb mask,bool &inworklist);
ReplaceOp *createOp(OpCode opc,int4 numparam,ReplaceVarnode *outrvn);
ReplaceOp *createOpDown(OpCode opc,int4 numparam,PcodeOp *op,ReplaceVarnode *inrvn,int4 slot);
bool tryCallPull(PcodeOp *op,ReplaceVarnode *rvn,int4 slot);
bool tryReturnPull(PcodeOp *op,ReplaceVarnode *rvn,int4 slot);
bool tryCallReturnPush(PcodeOp *op,ReplaceVarnode *rvn);
bool trySwitchPull(PcodeOp *op,ReplaceVarnode *rvn);
bool traceForward(ReplaceVarnode *rvn); ///< Trace the logical data-flow forward for the given subgraph variable
bool traceBackward(ReplaceVarnode *rvn); ///< Trace the logical data-flow backward for the given subgraph variable
bool traceForwardSext(ReplaceVarnode *rvn); ///< Trace logical data-flow forward assuming sign-extensions
bool traceBackwardSext(ReplaceVarnode *rvn); ///< Trace logical data-flow backward assuming sign-extensions
bool createLink(ReplaceOp *rop,uintb mask,int4 slot,Varnode *vn);
bool createCompareBridge(PcodeOp *op,ReplaceVarnode *inrvn,int4 slot,Varnode *othervn);
void addPush(PcodeOp *pushOp,ReplaceVarnode *rvn);
void addTerminalPatch(PcodeOp *pullop,ReplaceVarnode *rvn);
void addTerminalPatchSameOp(PcodeOp *pullop,ReplaceVarnode *rvn,int4 slot);
void addBooleanPatch(PcodeOp *pullop,ReplaceVarnode *rvn,int4 slot);
void addSuggestedPatch(ReplaceVarnode *rvn,PcodeOp *pushop,int4 sa);
void addComparePatch(ReplaceVarnode *in1,ReplaceVarnode *in2,PcodeOp *op);
ReplaceVarnode *addConstant(ReplaceOp *rop,uintb mask,uint4 slot,Varnode *constvn);
ReplaceVarnode *addNewConstant(ReplaceOp *rop,uint4 slot,uintb val);
void createNewOut(ReplaceOp *rop,uintb mask);
void replaceInput(ReplaceVarnode *rvn);
bool useSameAddress(ReplaceVarnode *rvn);
Varnode *getReplaceVarnode(ReplaceVarnode *rvn);
bool processNextWork(void); ///< Extend the subgraph from the next node in the worklist
public:
SubvariableFlow(Funcdata *f,Varnode *root,uintb mask,bool aggr,bool sext,bool big); ///< Constructor
bool doTrace(void); ///< Trace logical value through data-flow, constructing transform
void doReplacement(void); ///< Perform the discovered transform, making logical values explicit
};
/// \brief Class for splitting up Varnodes that hold 2 logical variables
///
/// Starting from a \e root Varnode provided to the constructor, \b this class looks for data-flow
/// that consistently holds 2 logical values in a single Varnode. If doTrace() returns \b true,
/// a consistent view has been created and invoking apply() will split all Varnodes and PcodeOps
/// involved in the data-flow into their logical pieces.
class SplitFlow : public TransformManager {
LaneDescription laneDescription; ///< Description of how to split Varnodes
vector<TransformVar *> worklist; ///< Pending work list of Varnodes to push the split through
TransformVar *setReplacement(Varnode *vn);
bool addOp(PcodeOp *op,TransformVar *rvn,int4 slot);
bool traceForward(TransformVar *rvn);
bool traceBackward(TransformVar *rvn);
bool processNextWork(void); ///< Process the next logical value on the worklist
public:
SplitFlow(Funcdata *f,Varnode *root,int4 lowSize); ///< Constructor
bool doTrace(void); ///< Trace split through data-flow, constructing transform
};
/// \brief Class for tracing changes of precision in floating point variables
///
/// It follows the flow of a logical lower precision value stored in higher precision locations
/// and then rewrites the data-flow in terms of the lower precision, eliminating the
/// precision conversions.
class SubfloatFlow : public TransformManager {
int4 precision; ///< Number of bytes of precision in the logical flow
int4 terminatorCount; ///< Number of terminating nodes reachable via the root
const FloatFormat *format; ///< The floating-point format of the logical value
vector<TransformVar *> worklist; ///< Current list of placeholders that still need to be traced
TransformVar *setReplacement(Varnode *vn);
bool traceForward(TransformVar *rvn);
bool traceBackward(TransformVar *rvn);
bool processNextWork(void);
public:
SubfloatFlow(Funcdata *f,Varnode *root,int4 prec);
virtual bool preserveAddress(Varnode *vn,int4 bitSize,int4 lsbOffset) const;
bool doTrace(void); ///< Trace logical value as far as possible
};
/// \brief Class for splitting data-flow on \e laned registers
///
/// From a root Varnode and a description of its \e lanes, trace data-flow as far as
/// possible through the function, propagating each lane, using the doTrace() method. Then
/// using the apply() method, data-flow can be split, making each lane in every traced
/// register into an explicit Varnode
class LaneDivide : public TransformManager {
/// \brief Description of a large Varnode that needs to be traced (in the worklist)
class WorkNode {
friend class LaneDivide;
TransformVar *lanes; ///< Lane placeholders for underyling Varnode
int4 numLanes; ///< Number of lanes in the particular Varnode
int4 skipLanes; ///< Number of lanes to skip in the global description
};
LaneDescription description; ///< Global description of lanes that need to be split
vector<WorkNode> workList; ///< List of Varnodes still left to trace
bool allowSubpieceTerminator; ///< \b true if we allow lanes to be cast (via SUBPIECE) to a smaller integer size
TransformVar *setReplacement(Varnode *vn,int4 numLanes,int4 skipLanes);
void buildUnaryOp(OpCode opc,PcodeOp *op,TransformVar *inVars,TransformVar *outVars,int4 numLanes);
void buildBinaryOp(OpCode opc,PcodeOp *op,TransformVar *in0Vars,TransformVar *in1Vars,TransformVar *outVars,int4 numLanes);
bool buildPiece(PcodeOp *op,TransformVar *outVars,int4 numLanes,int4 skipLanes);
bool buildMultiequal(PcodeOp *op,TransformVar *outVars,int4 numLanes,int4 skipLanes);
bool buildStore(PcodeOp *op,int4 numLanes,int4 skipLanes);
bool buildLoad(PcodeOp *op,TransformVar *outVars,int4 numLanes,int4 skipLanes);
bool buildRightShift(PcodeOp *op,TransformVar *outVars,int4 numLanes,int4 skipLanes);
bool traceForward(TransformVar *rvn,int4 numLanes,int4 skipLanes);
bool traceBackward(TransformVar *rvn,int4 numLanes,int4 skipLanes);
bool processNextWork(void); ///< Process the next Varnode on the work list
public:
LaneDivide(Funcdata *f,Varnode *root,const LaneDescription &desc,bool allowDowncast); ///< Constructor
bool doTrace(void); ///< Trace lanes as far as possible from the root Varnode
};
#endif