java.lang.Object | |
↳ | com.pnfsoftware.jeb.core.units.code.android.controlflow.CFG<InsnType extends com.pnfsoftware.jeb.core.units.code.ILocatedInstruction> |
This class represents a Control Flow Graph for a method, or more generally, any body of
code. The CFG can be typed to handle specific instructions
. It is used by
the Android plugins specifically, including dexdec
. (The native code analysis pipeline,
including gendec
, use another class of CFG components.)
This class provides Data Flow Analysis support. A client can request simple and full def-use- and use-def chains. Full chains contain more precise cross-block information. Reach-chains are also available.
There are two ways to build a CFG:
pre-basic blocks
.CFG(List, List)
constructor and passing a flat
list of instructions.NOTE: This class is to be used exclusively by the Android components.
Fields | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
public static final AtomicInteger | cfgfwccnt | Performance counter reserved for internal use. |
Public Constructors | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
CFG(Collection<BasicBlockBuilder<InsnType>> builders)
Create a CFG using a pre-computed list of partial basic block.
| |||||||||||
CFG(List<InsnType> insns, List<IrregularFlowData> irrdata)
Create a CFG by recursively parsing a list of instructions.
| |||||||||||
CFG(CFG<InsnType> cfg)
Shallow duplication of the current CFG.
|
Public Methods | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
void |
addBlock(BasicBlock<InsnType> b)
Add a block, does nothing else.
| ||||||||||
void |
addBlock(int index, BasicBlock<InsnType> b)
Insert a block, does nothing else.
| ||||||||||
boolean |
addEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Append an out-edge.
| ||||||||||
int |
addEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int index)
Add an out-edge.
| ||||||||||
int |
addIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int index)
Connect (irregularly) a source block to destination block.
| ||||||||||
boolean |
addIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Connect (irregularly) a source block to destination block.
| ||||||||||
Iterable<AddressableInstruction<InsnType>> |
addressableInstructions()
Get an instruction-with-address iterator.
| ||||||||||
IDFA3<InsnType, BasicBlock<InsnType>> |
createDataFlowAnalysisHelperObject()
Create an unmanaged data flow analysis object initialized with this CFG's DFA settings.
| ||||||||||
int |
deleteEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos)
Delete an edge x->y.
| ||||||||||
boolean |
deleteEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Delete an edge x->y.
| ||||||||||
int | deleteEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y) | ||||||||||
boolean |
deleteIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Delete an irregular edge x->y.
| ||||||||||
int |
deleteIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, int xToYPos)
Delete an irregular edge x->y.
| ||||||||||
int | deleteIrregularEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y) | ||||||||||
void |
deleteIrregularOutEdges(BasicBlock<InsnType> b)
Delete all irregular output edges for the provided block.
| ||||||||||
void |
deleteOutEdges(BasicBlock<InsnType> b)
Delete all regular output edges for the provided block.
| ||||||||||
IDFA3<InsnType, BasicBlock<InsnType>> |
doDataFlowAnalysis()
Create or retrieve a DFA object with current settings.
| ||||||||||
IDFA3<InsnType, BasicBlock<InsnType>> |
doDataFlowAnalysis(boolean redo)
Create or retrieve a DFA object with current settings.
| ||||||||||
IDFA3<InsnType, BasicBlock<InsnType>> |
doDataFlowAnalysis(boolean redo, int varCollectionFlags, boolean integrateCalculatedInputRegisters)
Create or retrieve a DFA object.
| ||||||||||
String |
format(boolean format_addresses, boolean format_edgelists, Object context)
Format the CFG into a printable string.
| ||||||||||
String |
format()
Format the CFG into a printable string.
| ||||||||||
String |
formatEdges()
Format the edges of this CFG to a string.
| ||||||||||
List<IrregularFlowData> |
generateIrregularFlowDataObjects()
(Re-)generate the irregular control flow information present in this CFG.
| ||||||||||
BasicBlock<InsnType> |
get(int index)
Retrieve a basic block.
| ||||||||||
TreeMap<Long, BasicBlock<InsnType>> |
getAddressBlockMap()
Get a complete map of the basic blocks and their addresses in the CFG.
| ||||||||||
BasicBlock<InsnType> | getBlock(int index) | ||||||||||
BasicBlock<InsnType> |
getBlockAt(long address)
Get the basic block that starts at the provided address or offset.
| ||||||||||
BasicBlock<InsnType> |
getBlockContaining(long address)
Get the basic block that contains the provided address.
| ||||||||||
BasicBlock<InsnType> |
getBlockEndingAt(long address)
Get the basic block that ends on the provided address.
| ||||||||||
BasicBlock<InsnType> | getBlockFor(InsnType insn) | ||||||||||
int | getBlockIndex(long address) | ||||||||||
List<BasicBlock<InsnType>> |
getBlocks()
Get a copy of the block list of the CFG.
| ||||||||||
List<BasicBlock<InsnType>> |
getBlocksView()
Get a read-only view of the list of blocks for this CFG.
| ||||||||||
List<IDFA3<InsnType, BasicBlock<InsnType>>> |
getCurrentDFAs()
Retrieve a list of all managed data flow analysis objects.
| ||||||||||
int |
getDFADefaultCollectionFlags()
Note that the initial value is set to
STANDARD_COLLECTION_FLAGS . | ||||||||||
IDFA3<InsnType, BasicBlock<InsnType>> |
getDataFlowAnalysis()
Retrieve a valid DFA object done with standard parameters (conservative, with inputs, no
copies).
| ||||||||||
IDFA3<InsnType, BasicBlock<InsnType>> |
getDataFlowAnalysis(int varCollectionFlags, boolean integrateCalculatedInputRegisters)
Retrieve a valid DFA object matching the provided parameters.
| ||||||||||
int |
getEffectiveSize()
Calculate the 'effective' size of this CFG, that is, the sum of the size of each basic block.
| ||||||||||
long |
getEndAddress()
Routine highest address (exclusive).
| ||||||||||
long |
getEntryAddress()
Routine entry-point address.
| ||||||||||
BasicBlock<InsnType> |
getEntryBlock()
Get the entry block.
| ||||||||||
List<BasicBlock<InsnType>> |
getExitBlocks()
Get the ordered list of exit blocks.
| ||||||||||
long |
getFirstAddress()
Routine lowest address (inclusive).
| ||||||||||
void |
getGraphRepresentation(List<int[]> edges, List<int[]> irregularEdges)
Get the a graph representation of the CFG.
| ||||||||||
InsnType |
getInstruction(long address)
Get the instruction located at the exact address.
| ||||||||||
InsnType | getInstructionAt(long address) | ||||||||||
int |
getInstructionCount()
Get the total number of instructions in the CFG.
| ||||||||||
Couple<BasicBlock<InsnType>, Integer> |
getInstructionLocation(long address)
Locate an instruction.
| ||||||||||
Couple<BasicBlock<InsnType>, Integer> |
getInstructionLocation(long address, boolean precise)
Locate an instruction.
| ||||||||||
TreeMap<Long, InsnType> |
getInstructionSet()
Retrieve an ordered dictionary of instructions.
| ||||||||||
List<InsnType> |
getInstructions()
Get the instruction list of this CFG by aggregating each instruction of every block.
| ||||||||||
BasicBlock<InsnType> | getLast() | ||||||||||
long |
getLastAddress()
Routine highest address (inclusive).
| ||||||||||
synchronized IVariableInformationProvider | getVariableInformationProvider() | ||||||||||
boolean |
hasExit()
Determine if this CFG has exit blocks, that is, blocks without out-edges.
| ||||||||||
boolean |
hasNoExit()
Determine if this CFG does not have any exit block.
| ||||||||||
int | indexOf(BasicBlock<InsnType> b) | ||||||||||
Iterable<InsnType> |
instructions(long fromAddress)
Iterate over a range of instructions of this CFG.
| ||||||||||
Iterable<InsnType> |
instructions()
Iterate over all the instructions of this CFG.
| ||||||||||
void |
invalidateDataFlowAnalysis(long addressOfInstructionChange)
Partially invalidate data flow analyses.
| ||||||||||
void |
invalidateDataFlowAnalysis()
Invalidate all previously performed data flow analyses.
| ||||||||||
boolean |
isDFADefaultIntegrateInputs()
Note that the initial value is set to
STANDARD_INTEGRATE_INPUTS . | ||||||||||
Iterator<BasicBlock<InsnType>> | iterator() | ||||||||||
int |
reconnectEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z, Integer xToYPos)
This method reconnects a block x from y to z, i.e.
| ||||||||||
int |
reconnectEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)
This method reconnects a block x from y to z, i.e.
| ||||||||||
int | reconnectEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z) | ||||||||||
int |
reconnectIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z, Integer xToYPos)
This method irregularly reconnects a block x from y to z, i.e.
| ||||||||||
int |
reconnectIrregularEdge(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z)
This method irregularly reconnects a block x from y to z, i.e.
| ||||||||||
int | reconnectIrregularEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y, BasicBlock<InsnType> z) | ||||||||||
void |
removeBlock(BasicBlock<InsnType> b)
Remove a block, and update the fixtures.
| ||||||||||
int |
removeDuplicateEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Remove duplicate edges (regular) from a source block to a destination block.
| ||||||||||
int |
removeDuplicateIrregularEdges(BasicBlock<InsnType> x, BasicBlock<InsnType> y)
Remove duplicate irregular edges from a source block to a destination block.
| ||||||||||
int |
reorganizeInputs()
Reorganize the input block list so that the fallthrough input block, if any, is placed first.
| ||||||||||
void |
resetDFA()
This method is deprecated.
use
invalidateDataFlowAnalysis()
| ||||||||||
void |
resetDataFlowAnalysis()
This method is deprecated.
use
invalidateDataFlowAnalysis()
| ||||||||||
int |
setDFADefaultCollectionFlags(int collectionFlags)
Note that the initial value is set to
STANDARD_COLLECTION_FLAGS . | ||||||||||
boolean |
setDFADefaultIntegrateInputs(boolean integrateInputs)
Note that the initial value is set to
STANDARD_INTEGRATE_INPUTS . | ||||||||||
synchronized IVariableInformationProvider | setVariableInformationProvider(IVariableInformationProvider prv) | ||||||||||
int |
simplify()
Merge the blocks that can be merged, without changing the flow of the graph.
| ||||||||||
int |
simplifyIrregularFlows()
Merge blocks that can be merged, taking into accounts irregular flows.
| ||||||||||
int |
size()
Get the number of blocks.
| ||||||||||
BasicBlock<InsnType> |
splitBlock(BasicBlock<InsnType> b, int index)
Split a block into two blocks.
| ||||||||||
String | toString() |
[Expand]
Inherited Methods | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
![]() | |||||||||||
![]() | |||||||||||
![]() |
Performance counter reserved for internal use.
Create a CFG using a pre-computed list of partial basic block.
Create a CFG by recursively parsing a list of instructions.
insns | list of instructions to be processed |
---|---|
irrdata | (optional) irregular flow information, used for exception support |
Shallow duplication of the current CFG. The graph is reconstructed; the instructions are not duplicated.
cfg | source graph |
---|
Add a block, does nothing else. The block is not connected, it is up to client code to connect it.
Insert a block, does nothing else. The block is not connected, it is up to client code to connect it.
Append an out-edge. Duplicates are not allowed.
x | source block |
---|---|
y | destination block |
Add an out-edge. Duplicates are allowed.
x | source block |
---|---|
y | destination block |
index | position (negative index is allowed, e.g. -1 means append last) |
Connect (irregularly) a source block to destination block. This method allows the addition of duplicate connections.
x | source block |
---|---|
y | destination |
index | out-irr.edge index (negative indices can be used; e.g. -1 means append) |
Connect (irregularly) a source block to destination block. This method does NOT allow the addition of duplicate connections.
This method should not be used. Use addIrregularEdge(BasicBlock, BasicBlock, int)
instead.
x | source block |
---|---|
y | destination block |
Get an instruction-with-address iterator. Also see instructions()
.
remove
)
Create an unmanaged data flow analysis object initialized with this CFG's DFA settings. These
objects are not managed by this CFG object. For managed DFA objects, clients should use
doDataFlowAnalysis()
or #getDataFlowAnalysis()
.
Delete an edge x->y.
Delete an edge x->y. If duplicates exist, the first one in the list of out-edges is deleted.
x | source block |
---|---|
y | destination block |
Delete an irregular edge x->y. If duplicates exist, the first one in the list of irrout-edges is deleted.
x | source block |
---|---|
y | destination block |
Delete an irregular edge x->y.
Delete all irregular output edges for the provided block.
b | block |
---|
Delete all regular output edges for the provided block.
b | block |
---|
Create or retrieve a DFA object with current settings.
Create or retrieve a DFA object with current settings.
redo | if true, force a new analysis even if one is not required |
---|
Create or retrieve a DFA object.
redo | if true, force a new analysis even if one is not required |
---|---|
varCollectionFlags | variable collection flags |
integrateCalculatedInputRegisters | if true, the live registers determined after analysis will be integrated in the use-def chains |
Format the CFG into a printable string.
format_addresses | true to prepend instructions by their addresses |
---|---|
format_edgelists | true to append the explicit list of edges to the CFG |
context | optional formatting context |
Format the CFG into a printable string. Instruction addresses are included, edges are appended to the CFG.
Format the edges of this CFG to a string.
(Re-)generate the irregular control flow information present in this CFG.
Get a complete map of the basic blocks and their addresses in the CFG. This method is recommended for use when multiple, repeated invocations of #getBlockAt(int) are to be made.
Get the basic block that starts at the provided address or offset.
address | the block address/offset |
---|
Get the basic block that contains the provided address.
Note that the address just needs to be in the block address range; it does not need to point to the beginning of an instruction within the block
address | an address within the block |
---|
Get the basic block that ends on the provided address.
address | wanted block end address (exclusive) |
---|
Get a copy of the block list of the CFG. The list is ordered by ascending block address. Modifying the list does not impact the CFG.
Get a read-only view of the list of blocks for this CFG. The list is ordered by ascending block address.
Retrieve a list of all managed data flow analysis objects.
Note that the initial value is set to STANDARD_COLLECTION_FLAGS
.
Retrieve a valid DFA object done with standard parameters (conservative, with inputs, no copies).
Retrieve a valid DFA object matching the provided parameters.
varCollectionFlags | variable collection flags |
---|---|
integrateCalculatedInputRegisters | if true, the live registers determined after analysis will be integrated in the use-def chains |
Calculate the 'effective' size of this CFG, that is, the sum of the size of each basic block.
Routine highest address (exclusive).
Routine entry-point address. Note that this address may not be the lowest one in the CFG.
Get the entry block. The entry block is unique.
Get the ordered list of exit blocks. A CFG may have zero or more exit blocks; CFG representing standard routines will have at least one (generally one) exit block.
Routine lowest address (inclusive). Note that this address may not be the entry-point address for this routine.
Get the a graph representation of the CFG. The list of edges return use a 1-based node numbering scheme.
edges | (output) array of regular edges, eg: {{1,2},{1,3},{2,3}} |
---|---|
irregularEdges | (output) array of irregular edges |
Get the instruction located at the exact address.
Get the total number of instructions in the CFG. This method sums the number of instructions of each block of the CFG.
Locate an instruction.
address | instruction address |
---|
Locate an instruction.
address | instruction address |
---|---|
precise | if true, the instruction is expected to start at the provided address; else, the provided address may address any byte of the instruction |
Retrieve an ordered dictionary of instructions.
Get the instruction list of this CFG by aggregating each instruction of every block. The list is ordered by ascending address/offset.
Routine highest address (inclusive).
Determine if this CFG has exit blocks, that is, blocks without out-edges.
Determine if this CFG does not have any exit block.
Iterate over a range of instructions of this CFG.
fromAddress | exact address of the first instruction to be iterated over |
---|
Iterate over all the instructions of this CFG.
remove
)
Partially invalidate data flow analyses. This method can be used after modifying an instruction of the CFG.
addressOfInstructionChange | address |
---|
Invalidate all previously performed data flow analyses. This method can be used after a CFG modification that would render DFA objects obsoletes.
Note that the initial value is set to STANDARD_INTEGRATE_INPUTS
.
This method reconnects a block x from y to z, i.e. x->y becomes x->z. If z is null, this method deletes the edge x>y.
x | source block |
---|---|
y | original destination block |
z | new destination block; null to indicate that the edge x>y should be deleted |
xToYPos | optional index specifying which x>y edge (if there are more than one) should be picked (this index is not an index into the full out-list of x); if null, this method will fail on duplicate edges (see return codes) |
This method reconnects a block x from y to z, i.e. x->y becomes x->z. Duplicates edges are forbidden.
See reconnectEdge(BasicBlock, BasicBlock, BasicBlock, Integer)
.
This method irregularly reconnects a block x from y to z, i.e. x->y becomes x->z. If z is null, this method deletes the irregular edge x>y.
x | source block |
---|---|
y | original destination block |
z | new destination block; null to indicate that the irregular edge x>y should be deleted |
xToYPos | optional index specifying which x>y irregular edge (if there are more than one) should be picked (this index is not an index into the full irrout-list of x); if null, this method will fail on duplicate irregular edges (see return codes) |
This method irregularly reconnects a block x from y to z, i.e. x->y becomes x->z. Duplicates edges are forbidden.
See reconnectIrregularEdge(BasicBlock, BasicBlock, BasicBlock, Integer)
.
Remove a block, and update the fixtures. This method is content-agnostic.
A CFG should never contain empty blocks. However, when the CFG is optimized, instructions are removed, and some nodes might end up empty. This transient, stale state is fine AS LONG AS the client knows what it is doing and removes the empty block as soon as they're done, before passing it down the processing chain. This method removes empty blocks and updates the edges of connected and connecting blocks.
1st caveat: the empty block's out-degree or in-degree MUST be one. (Otherwise, stitching up the edges would not be possible.)
2nd caveat: duplicate edges can be introduced. The client should remove them if it doesn't like that.
3rd caveat: the fixtures update is instruction-agnostic. This means that the client is solely responsible regarding the decision to remove an empty block. For instance, the last instruction of the predecessor block should be checked and the client should make sure that removing the block and updating the fixtures is an operation compatible with the semantics of that last instruction.
b | block to be removed |
---|
Remove duplicate edges (regular) from a source block to a destination block.
x | src block |
---|---|
y | dst block |
Remove duplicate irregular edges from a source block to a destination block.
x | src block |
---|---|
y | dst block |
Reorganize the input block list so that the fallthrough input block, if any, is placed first.
Note that the initial value is set to STANDARD_COLLECTION_FLAGS
.
Note that the initial value is set to STANDARD_INTEGRATE_INPUTS
.
Merge the blocks that can be merged, without changing the flow of the graph.
Necessary conditions include: adjacent blocks, first block falls-through the second one, no block shall have irregular outputs, only the first block may have irregular inputs.
Merge blocks that can be merged, taking into accounts irregular flows.
A follow through may be merged with a block inside a try (with irregular outedges) if no
instruction within the block can raise.
Get the number of blocks.
Split a block into two blocks. Note that the newly-created block will be set up to have the same irregular outputs as the original block.
b | block to split |
---|---|
index | index of the "split instruction" in the block; that instruction will be the first instruction of the newly-created block |