public class

DUtil

extends Object
java.lang.Object
   ↳ com.pnfsoftware.jeb.core.units.code.android.ir.DUtil

Class Overview

dexdec IR access and manipulation utility methods.

Summary

Public Constructors
DUtil()
Public Methods
static int calculateComplexity(IDExpression e)
Calculate the trivial complexity metric for the provided IR expression.
static boolean canHandlerCatchException(IDMethodContext ctx, IDExceptionHandler h, String exceptionSig)
static boolean checkBlock(BasicBlock<IDInstruction> b, DOpcodeType... opcodes)
Check for instruction matching in the provided block.
static int checkSequence(CFG<IDInstruction> cfg, int blkindex, DOpcodeType... opcodes)
Check for instruction matching in a sequence of blocks.
static int cleanGraph(IDMethodContext ctx)
Clean the graph of an IR method context.
static Set<Integer> collectUniqueVarIds(IDExpression e)
Collect the unique list of variable ids making up this expression, including the expression itself if is an IDVar.
static List<IDVar> collectVars(IDExpression e)
Collect all the variables making up this expression, including the expression itself if is a variable.
static CFG<IDInstruction> copyGraph(CFG<IDInstruction> cfg, boolean deepCopy, IDMethodContext newContext)
Copy an IR-CFG.
static int countVariable(IDExpression e, IDVar var)
Count the number of occurrences of a given variable in the provided IR expression.
static int createRegisterVarId(int registerBase, boolean dualSlot)
Create the primary variable mapping to a register or couple of registers.
static void dump(CFG<IDInstruction> cfg, String filename, String title)
Dump an IR-CFG to a Graphviz dot file in the user's temporary folder.
static void dump(CFG<IDInstruction> cfg, String filename)
Dump an IR-CFG to a Graphviz dot file in the user's temporary folder.
static String formatVarId(int varid)
Generate the standard variable name associated with the provided variable id.
static String formatVarIds(Collection<Integer> varids)
A convenience method to format a collection of variable ids into a comma-separated string.
static SortedMap<Integer, Integer> generateBlockOffsetMap(IDMethodContext ctx)
Generate an offset IR-to-native offset conversion map.
static String generateNativeAddress(IDMethodContext ctx, IDExpression elt)
static ICodeCoordinates generateNativeCoordinates(IDMethodContext ctx, IDExpression elt)
static ContextAccessType getCAT(IDInstruction insn, boolean inclAssigDst)
Determine the aggregated context type of an instruction.
static String getExceptionSignature(IDMethodContext ctx, IDExceptionHandler h)
static Collection<BasicBlock<IDInstruction>> getReachableBlocks(CFG<IDInstruction> cfg)
Get the list of reachable blocks of the provided IR-CFG.
static boolean hasInvokeInfo(IDExpression e)
Determine whether the IR expression makes invocations (general invocations, new, new-array).
static boolean hasVariable(IDExpression e, int varid)
Determine whether the provided expression is or contains the provided variable.
static boolean hasVariables(IDExpression e)
Determine whether the provided expression contains variables.
static void insertHeaderBlock(IDMethodContext ctx, int reqInsnCount, int reqInsnSize)
Insert a header block filled with NOP instructions.
static boolean isDoubleSlotVarId(int varid)
static boolean isImmNonZero(IDExpression exp)
Determine if an expression is an IR immediate not holding the value 0.
static boolean isImmValue(IDExpression exp, long value)
Determine if an expression is an IR immediate holding the provided value.
static boolean isImmZero(IDExpression exp)
Determine if an expression is an IR immediate holding the value 0.
static boolean isLegalVarId(int varid)
static boolean isRegisterVarId(int varid)
static boolean isSingleSlotVarId(int varid)
static boolean isUsingCaughtException(IDMethodContext ctx, BasicBlock<IDInstruction> b)
static boolean isVirtualVarId(int varid)
static boolean mayBeFinal(IDField f, IDexUnit dex)
Determine whether the provided field is or appears to be final.
static int modifyInstructionSizes(IDMethodContext ctx, Function<IDInstruction, Integer> modifier)
Update the instruction sizes of a CFG.
static IDInstruction nextInstruction(CFG<IDInstruction> cfg, BasicBlock<IDInstruction> b, int i)
Determine the meaningful next instruction in the execution flow, assuming no exception was raised.
static int normalizeGraph(IDMethodContext ctx)
Normalize the IR by resetting all instructions to the unit size (1).
static int normalizeGraph(IDMethodContext ctx, int wantedInstructionSize)
Normalize the IR by resetting all instructions to the required size.
static int parseVarIdFromStandardName(String varname, boolean softFail)
Parse a standard variable name (as generated by formatVarId(int)) and retrieve the associated variable id.
static int removeGaps(CFG<IDInstruction> cfg)
Remove all gaps from the provided IR-CFG.
static boolean removeInstruction(BasicBlock<IDInstruction> b, int idx)
Remove an instruction in a block.
static int removeUnreachableBlocks(CFG<IDInstruction> cfg, IDTryData ex)
Remove unreachable blocks from an IR-CFG.
static int removeUnreachableBlocks(IDMethodContext ctx)
Remove unreachable blocks from an IR-CFG.
static boolean removeUnreachableTrampoline(CFG<IDInstruction> cfg, BasicBlock<IDInstruction> b)
Remove an unreachable trampoline block (ending on a JCOND or JUMP).
static boolean replaceInExpression(IDExpression e, IDExpression target, IDExpression repl)
Replace an IR expression located inside another IR.
static int simplifyJCondsAndSwitches(IDMethodContext ctx)
Simply DOpcodeType#JCOND and IR_SWITCH IR instructions:
- JCOND: the target branch must not point to the fallthrough instruction; if it is, the JCOND must be replaced by a JUMP (while taking care of potential side-effects introduced by the evaluation of the JCOND predicate)
- SWITCH: the case targets must not point to the fallthrough instruction; if any does, the case entry must be removed (and will be taken care by the switch's default entry)

Illegal JCOND/SWITCH are tolerated during an optimization phase; however, an optimizer, or any code modifying the IR, must provide a legal IR to subsequent components.

static BasicBlock<IDInstruction> splitBlock(IDMethodContext ctx, BasicBlock<IDInstruction> blk, int index)
Split a block of the context's CFG into two blocks.
static boolean unprotectBlock(CFG<IDInstruction> cfg, IDTryData exdata, int blkAddress)
Unprotect a basic block.
static List<IDInstruction> unroll(IDMethodContext ctx, IDVar pivotVar, long addrStart, long addrEnd, int maxProcessedInsnCount, int maxUnrolledInsnCount, int maxLoopIterCnt)
Attempt to unroll some code whose pivot is a single variable.
static int updateTargets(IDMethodContext ctx, Map<Integer, Integer> oldToNewOffsets)
static boolean usesReferences(IDExpression e)
Determine whether the IR expression uses references, defined as any of: accessing fields, accessing array elements, creating arrays.
static void verifyGraph(IDMethodContext ctx, String info)
Verify an IR-CFG from a method context.
static void verifyGraph(IDMethodContext ctx)
Verify an IR-CFG from a method context.
static void verifyGraph(IDMethodContext ctx, String dumpFilename, String info)
Verify an IR-CFG.
static void verifyGraph(IDMethodContext ctx, CFG<IDInstruction> cfg, IDTryData exdata, String dumpFilename, String info)
Verify an IR-CFG.
[Expand]
Inherited Methods
From class java.lang.Object

Public Constructors

public DUtil ()

Public Methods

public static int calculateComplexity (IDExpression e)

Calculate the trivial complexity metric for the provided IR expression. Every IR element has a weight of 1.

Parameters
e an IR expression
Returns
  • the complexity score

public static boolean canHandlerCatchException (IDMethodContext ctx, IDExceptionHandler h, String exceptionSig)

public static boolean checkBlock (BasicBlock<IDInstruction> b, DOpcodeType... opcodes)

Check for instruction matching in the provided block. The block must be fully matched.

public static int checkSequence (CFG<IDInstruction> cfg, int blkindex, DOpcodeType... opcodes)

Check for instruction matching in a sequence of blocks. Blocks must be fully contiguous and fully matched.
This is an extended version of #checkBlock(BasicBlock, DOpcodeType...), which performs matching on a single block.

Returns
  • the number of blocks containing the sequence; on failure

public static int cleanGraph (IDMethodContext ctx)

Clean the graph of an IR method context.

Returns
  • the number of clean-up operations performed

public static Set<Integer> collectUniqueVarIds (IDExpression e)

Collect the unique list of variable ids making up this expression, including the expression itself if is an IDVar.

Parameters
e an IR expression
Returns
  • a set of variable ids used in the expression

public static List<IDVar> collectVars (IDExpression e)

Collect all the variables making up this expression, including the expression itself if is a variable. The returned collection may contain duplicates. Example: If the provided expression if ((var1 + var2 + 5) / var1), this method will return [var1, var2, var1]. Note that the collection is done in post-order, so ordering is predictable.

Parameters
e an IR expression
Returns
  • a list of all vars used in the expression

public static CFG<IDInstruction> copyGraph (CFG<IDInstruction> cfg, boolean deepCopy, IDMethodContext newContext)

Copy an IR-CFG.

Parameters
cfg a CFG
deepCopy if false, the CFG is only structurally duplicated (that is, the copy is shallow: the instructions of the new CFG are reused in the new CFG); if true, the instructions are duplicated as well).
newContext if performing deep copy, the optional new context to be set up for the IR instructions
Returns
  • the CFG copy (deep or shallow)

public static int countVariable (IDExpression e, IDVar var)

Count the number of occurrences of a given variable in the provided IR expression.

Parameters
e an IR expression

public static int createRegisterVarId (int registerBase, boolean dualSlot)

Create the primary variable mapping to a register or couple of registers. A primary variable has an id that can be mapped directly to the underlying Dalvik register id(s).

Parameters
registerBase the register id of the Dalvik variable, or first register of the pair if the variable is dual-slot; must be in [0, 0xFFFF] (at most 0xFFFE for a dual-slot variable)

public static void dump (CFG<IDInstruction> cfg, String filename, String title)

Dump an IR-CFG to a Graphviz dot file in the user's temporary folder.

Parameters
cfg CFG
filename filename (the ".dot" extension will be appended if necessary)
title optional title or header string

public static void dump (CFG<IDInstruction> cfg, String filename)

Dump an IR-CFG to a Graphviz dot file in the user's temporary folder.

public static String formatVarId (int varid)

Generate the standard variable name associated with the provided variable id.

Parameters
varid a variable id
Returns
  • the variable name; on error, the method throws IllegalArgumentException

public static String formatVarIds (Collection<Integer> varids)

A convenience method to format a collection of variable ids into a comma-separated string.

Parameters
varids collection of variable ids
Returns
  • a string

public static SortedMap<Integer, Integer> generateBlockOffsetMap (IDMethodContext ctx)

Generate an offset IR-to-native offset conversion map.

Returns
  • a map of (IR block offset -> Dalvik block offset)

public static String generateNativeAddress (IDMethodContext ctx, IDExpression elt)

public static ICodeCoordinates generateNativeCoordinates (IDMethodContext ctx, IDExpression elt)

public static ContextAccessType getCAT (IDInstruction insn, boolean inclAssigDst)

Determine the aggregated context type of an instruction.

Parameters
insn instruction
inclAssigDst if true and the instruction is an assignment, the destination is included when calculated the CAT; else, the right-side only is considered
Returns
  • aggregated CAT

public static String getExceptionSignature (IDMethodContext ctx, IDExceptionHandler h)

public static Collection<BasicBlock<IDInstruction>> getReachableBlocks (CFG<IDInstruction> cfg)

Get the list of reachable blocks of the provided IR-CFG. They are the blocks that can be reached, regularly or irregularly, from the entry-point block (i.e. the first block, at offset 0).

public static boolean hasInvokeInfo (IDExpression e)

Determine whether the IR expression makes invocations (general invocations, new, new-array).

Parameters
e an IR expression

public static boolean hasVariable (IDExpression e, int varid)

Determine whether the provided expression is or contains the provided variable.

Parameters
e an expression
varid the searched variable id

public static boolean hasVariables (IDExpression e)

Determine whether the provided expression contains variables.

Parameters
e an IR expression

public static void insertHeaderBlock (IDMethodContext ctx, int reqInsnCount, int reqInsnSize)

Insert a header block filled with NOP instructions. Essentially, the CFG is shifted downward to accommodate the insertion of a number of lead instructions (to be executed before the entry point).

This method never fails. The returned CFG and IR context information is updated to maintain consistency.

Parameters
ctx an IR context
reqInsnCount number of NOP instructions to be prepended
reqInsnSize size set for each individual instruction

public static boolean isDoubleSlotVarId (int varid)

public static boolean isImmNonZero (IDExpression exp)

Determine if an expression is an IR immediate not holding the value 0.

Parameters
exp an IR expression
Returns
  • true if the provided expression is an immediate not equivalent to the value 0

public static boolean isImmValue (IDExpression exp, long value)

Determine if an expression is an IR immediate holding the provided value. The immediate value is determined according to its type. If the type of the expression is undetermined, a signed type is assumed.

Parameters
exp an IR expression
value the value to check against
Returns
  • true if the provided expression that evaluated to the provided value

public static boolean isImmZero (IDExpression exp)

Determine if an expression is an IR immediate holding the value 0.

Parameters
exp an IR expression
Returns
  • true if the provided expression is an immediate equivalent to the value 0

public static boolean isLegalVarId (int varid)

public static boolean isRegisterVarId (int varid)

public static boolean isSingleSlotVarId (int varid)

public static boolean isUsingCaughtException (IDMethodContext ctx, BasicBlock<IDInstruction> b)

public static boolean isVirtualVarId (int varid)

public static boolean mayBeFinal (IDField f, IDexUnit dex)

Determine whether the provided field is or appears to be final.

public static int modifyInstructionSizes (IDMethodContext ctx, Function<IDInstruction, Integer> modifier)

Update the instruction sizes of a CFG. This method is a general version of normalizeGraph(). No CFG block is inserted or deleted. Only instructions' sizes and offsets are updated. Note that the CFG is modified, but the CFG reference within the context is not changed (i.e. no new CFG is created).

Parameters
ctx IR context
modifier instruction size provider; the function may return null to indicate that the instruction size should not change
Returns
  • the number of modifications

public static IDInstruction nextInstruction (CFG<IDInstruction> cfg, BasicBlock<IDInstruction> b, int i)

Determine the meaningful next instruction in the execution flow, assuming no exception was raised. Jump targets are followed, no-operations are skipped.

Parameters
cfg current CFG
b current block
i index of the current instruction in the block
Returns
  • the next instruction, or null if it cannot be determined accurately

public static int normalizeGraph (IDMethodContext ctx)

Normalize the IR by resetting all instructions to the unit size (1). Exception data is updated as well. The modification are done in-place: the CFG and other objects references remain valid.

Parameters
ctx IR context
Returns
  • the number of modifications performed; if nothing has changed, the return value is 0

public static int normalizeGraph (IDMethodContext ctx, int wantedInstructionSize)

Normalize the IR by resetting all instructions to the required size. Exception data is updated as well. The modification are done in-place: the CFG and other objects references remain valid.

Parameters
ctx IR context
wantedInstructionSize required instruction size, must be 1 or above
Returns
  • the number of modifications performed; if nothing has changed, the return value is 0

public static int parseVarIdFromStandardName (String varname, boolean softFail)

Parse a standard variable name (as generated by formatVarId(int)) and retrieve the associated variable id.

Parameters
varname a variable name
softFail if true, return -1 on error; else, the method will throw IllegalArgumentException on error
Returns
  • the id

public static int removeGaps (CFG<IDInstruction> cfg)

Remove all gaps from the provided IR-CFG.

Gaps are illegal in an IR-CFG. They are tolerated during an optimization phase; however, an optimizer, or any code modifying the IR, must provide a legal IR to subsequent components.

Returns
  • the number of gaps that were removed

public static boolean removeInstruction (BasicBlock<IDInstruction> b, int idx)

Remove an instruction in a block. Throws on error (watch out: the boolean return value does not indicate failure).

Parameters
b basic block
idx index of the instruction to remove in this block
Returns
  • true if the instruction was truly removed, false if it was removed and replaced by an unconditional jump to avoid creating an empty block

public static int removeUnreachableBlocks (CFG<IDInstruction> cfg, IDTryData ex)

Remove unreachable blocks from an IR-CFG. They are blocks that cannot be reached, regularly or irregularly, from the entry-point block (i.e. the first block, at offset 0).

Unreachable blocks are illegal in an IR-CFG. They are tolerated during an optimization phase; however, an optimizer, or any code modifying the IR, must provide a legal IR to subsequent components.

public static int removeUnreachableBlocks (IDMethodContext ctx)

Remove unreachable blocks from an IR-CFG. They are blocks that cannot be reached, regularly or irregularly, from the entry-point block (i.e. the first block, at offset 0).

Unreachable blocks are illegal in an IR-CFG. They are tolerated during an optimization phase; however, an optimizer, or any code modifying the IR, must provide a legal IR to subsequent components.

public static boolean removeUnreachableTrampoline (CFG<IDInstruction> cfg, BasicBlock<IDInstruction> b)

Remove an unreachable trampoline block (ending on a JCOND or JUMP).

Parameters
b the block must be an unreachable (no input) trampoline (single-instruction jump/jcc); if the block is the first block in the CFG, the method will fail
Returns
  • true if the block was removed

public static boolean replaceInExpression (IDExpression e, IDExpression target, IDExpression repl)

Replace an IR expression located inside another IR. This method is a deep version of replaceSubExpression(IDExpression, IDExpression). Comparison is done by identity.

Parameters
e parent IR
target the target to be replaced; should not be the same as `e`
repl the replacement IR
Returns
  • true if the target was successfully replaced

public static int simplifyJCondsAndSwitches (IDMethodContext ctx)

Simply DOpcodeType#JCOND and IR_SWITCH IR instructions:
- JCOND: the target branch must not point to the fallthrough instruction; if it is, the JCOND must be replaced by a JUMP (while taking care of potential side-effects introduced by the evaluation of the JCOND predicate)
- SWITCH: the case targets must not point to the fallthrough instruction; if any does, the case entry must be removed (and will be taken care by the switch's default entry)

Illegal JCOND/SWITCH are tolerated during an optimization phase; however, an optimizer, or any code modifying the IR, must provide a legal IR to subsequent components.

public static BasicBlock<IDInstruction> splitBlock (IDMethodContext ctx, BasicBlock<IDInstruction> blk, int index)

Split a block of the context's CFG into two blocks. The newly-created block will be set up to have the same irregular outputs as the original block. The context's exception information data will be updated accordingly.

Parameters
ctx IR context
blk block to split
index index of the "split instruction" in the block; that instruction will be the first instruction of the newly-created block
Returns
  • the newly-created block

public static boolean unprotectBlock (CFG<IDInstruction> cfg, IDTryData exdata, int blkAddress)

Unprotect a basic block. The CFG is adjusted and cleaned afterward.

Parameters
blkAddress block address
Returns
  • true if the block was protected and is now unprotected; false if the block was not protected

public static List<IDInstruction> unroll (IDMethodContext ctx, IDVar pivotVar, long addrStart, long addrEnd, int maxProcessedInsnCount, int maxUnrolledInsnCount, int maxLoopIterCnt)

Attempt to unroll some code whose pivot is a single variable. The generated code will not contain branching instructions JUMP, JCOND, SWITCH, RETURN, THROW, etc.).

Parameters
ctx IR method context (which references the CFG to operate on)
pivotVar pivot variable
addrStart start address (inclusive) - generally, the instruction at that address initializes the pivot variable, although it is not a requirement
addrEnd end address (exclusive), will stop the unrolling process
maxProcessedInsnCount maximum amount of instructions to process until the end is reached
maxUnrolledInsnCount maximum amount of unrolled instructions that may be generated
maxLoopIterCnt maximum count of iterations to be unrolled (note: keep in mind for values greater than 1, the resulting IR is likely to be larger than the original IR)
Returns
  • null on error or failure, else the list of unrolled instructions (the list may contain duplicates, client code needs to use duplicate() to create unique instructions)

public static int updateTargets (IDMethodContext ctx, Map<Integer, Integer> oldToNewOffsets)

Parameters
ctx IR context
oldToNewOffsets a mapping of the old offsets to the corresponding new offsets
Returns
  • the number of modifications

public static boolean usesReferences (IDExpression e)

Determine whether the IR expression uses references, defined as any of: accessing fields, accessing array elements, creating arrays.

Parameters
e an IR expression

public static void verifyGraph (IDMethodContext ctx, String info)

Verify an IR-CFG from a method context. On failure, the CFG will be dumped to "failed.dot"

Parameters
ctx IR context, from which the CFG and optional exception-info object will be pulled
info optional string added to the generated DOT file's header containing the CFG (if verification failed)
Throws
RuntimeException (or derived, such as IllegalArgumentException or IllegalStateException) if the verification failed

public static void verifyGraph (IDMethodContext ctx)

Verify an IR-CFG from a method context. On failure, the CFG will be dumped to "failed.dot"

Parameters
ctx IR context, from which the CFG and optional exception-info object will be pulled
Throws
RuntimeException (or derived, such as IllegalArgumentException or IllegalStateException) if the verification failed

public static void verifyGraph (IDMethodContext ctx, String dumpFilename, String info)

Verify an IR-CFG.

Parameters
ctx context containing the CFG
dumpFilename optional path to filename where the CFG will be dumped if the verification filed
info optional string added to the generated DOT file's header containing the CFG (if verification failed)
Throws
RuntimeException (or derived, such as IllegalArgumentException or IllegalStateException) if the verification failed

public static void verifyGraph (IDMethodContext ctx, CFG<IDInstruction> cfg, IDTryData exdata, String dumpFilename, String info)

Verify an IR-CFG.

Parameters
cfg CFG
exdata optional exception-info object
dumpFilename optional path to filename where the CFG will be dumped if the verification filed
info optional string added to the generated DOT file's header containing the CFG (if verification failed)
Throws
RuntimeException (or derived, such as IllegalArgumentException or IllegalStateException) if the verification failed