public class

CFGUtil

extends Object
java.lang.Object
   ↳ com.pnfsoftware.jeb.core.units.code.CFGUtil

Class Overview

Utility code for IControlFlowGraph.

Summary

Nested Classes
class CFGUtil.BlockGroup Given a start block A and an end block B, find the group of blocks G flowing from A to B, such that: 1) all blocks in G are reachable from A; 2) no blocks in G are reachable from B. 
class CFGUtil.DotFileGenerator GraphViz generator for CFG objects. 
class CFGUtil.RegionFinder This class attempts to determine a region in a graph. 
Public Constructors
CFGUtil()
Public Methods
static boolean canReach(IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to)
Determine whether a regular path exists between a source block and a destination block.
static boolean canReach(IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to, boolean alsoFollowIrregularFlow)
Determine whether a path exists between a source block and a destination block.
static boolean canReach(IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to, boolean alsoFollowIrregularFlow, Collection<IBasicBlock<? extends IInstruction>> stopperBlocks)
Determine whether a path exists between a source block and a destination block.
static int countDeepInputs(IBasicBlock<? extends IInstruction> b, int maxdepth)
Count regular the number of top-level input blocks leading to the provided block.
static void toDot(IControlFlowGraph<?, ?> cfg, File file)
Build the CFG text representation using the dot language.
static void toDot(IControlFlowGraph<?, ?> cfg, File file, String title, Map<Long, String> blockHeaders)
Build the CFG text representation using the dot language.
static void toDot(IControlFlowGraph<?, ?> cfg, File file, String title)
Build the CFG text representation using the dot language.
static void toDot(IControlFlowGraph<?, ?> cfg, File file, String title, Map<Long, String> blockHeaders, int lineLimit)
Build the CFG text representation using the dot language.
static void toTempDot(IControlFlowGraph<?, ?> cfg, String name, String title, Map<Long, String> blockHeaders, int lineLimit)
static void toTempDot(IControlFlowGraph<?, ?> cfg, String name)
static void verify(IControlFlowGraph<?, ?> cfg)
Verification of a CFG.
static void verify(IControlFlowGraph<?, ?> cfg, boolean checkConnected, boolean checkGapless, boolean checkFlowinfo, boolean checkNoDupEdges, boolean checkNoDupIrregularEdges)
Verification of a CFG.
[Expand]
Inherited Methods
From class java.lang.Object

Public Constructors

public CFGUtil ()

Public Methods

public static boolean canReach (IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to)

Determine whether a regular path exists between a source block and a destination block. If both source and destination blocks are the same block B, the method returns true if B is part of a regular loop (i.e., a path exists from B to B). Exceptional flow (irregular edges) are disregarded.

Parameters
from source block
to destination block
Returns
  • true if a path exists between the source and the destination

public static boolean canReach (IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to, boolean alsoFollowIrregularFlow)

Determine whether a path exists between a source block and a destination block. If both source and destination blocks are the same block B, the method returns true if B is part of a loop (i.e., a path exists from B to B).

Parameters
from source block
to destination block
alsoFollowIrregularFlow if true, irregular control flow will also be followed
Returns
  • true if a path exists between the source and the destination

public static boolean canReach (IBasicBlock<? extends IInstruction> from, IBasicBlock<? extends IInstruction> to, boolean alsoFollowIrregularFlow, Collection<IBasicBlock<? extends IInstruction>> stopperBlocks)

Determine whether a path exists between a source block and a destination block. If both source and destination blocks are the same block B, the method returns true if B is part of a loop (i.e., a path exists from B to B).

Parameters
from source block
to destination block
alsoFollowIrregularFlow if true, irregular control flow will also be followed
Returns
  • true if a path exists between the source and the destination

public static int countDeepInputs (IBasicBlock<? extends IInstruction> b, int maxdepth)

Count regular the number of top-level input blocks leading to the provided block.

Parameters
b the basic block to be examined
maxdepth if less or equal than 1, this method is equivalent to insize()
Returns
  • the number of inputs

public static void toDot (IControlFlowGraph<?, ?> cfg, File file)

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Parameters
file output file
Throws
IOException

public static void toDot (IControlFlowGraph<?, ?> cfg, File file, String title, Map<Long, String> blockHeaders)

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Parameters
file output file
title optional graph title
blockHeaders optional map of block headers (block_address -> block_description_string); if null, a standard header "(block_index)" is used
Throws
IOException

public static void toDot (IControlFlowGraph<?, ?> cfg, File file, String title)

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Parameters
file output file
title optional graph title
Throws
IOException

public static void toDot (IControlFlowGraph<?, ?> cfg, File file, String title, Map<Long, String> blockHeaders, int lineLimit)

Build the CFG text representation using the dot language. To generate a PNG: dot out.dot -Tpng -o out.png

Throws
IOException

public static void toTempDot (IControlFlowGraph<?, ?> cfg, String name, String title, Map<Long, String> blockHeaders, int lineLimit)

public static void toTempDot (IControlFlowGraph<?, ?> cfg, String name)

public static void verify (IControlFlowGraph<?, ?> cfg)

Verification of a CFG. Throws RuntimeException (or derived) on error.

Calls verify(IControlFlowGraph, boolean, boolean, boolean, boolean, boolean) with all optional checks enabled.

Parameters
cfg the CFG to be verified
Throws
RuntimeException if the verification failed

public static void verify (IControlFlowGraph<?, ?> cfg, boolean checkConnected, boolean checkGapless, boolean checkFlowinfo, boolean checkNoDupEdges, boolean checkNoDupIrregularEdges)

Verification of a CFG. Throws RuntimeException (or derived) on error.

This method checks the following:
- the graph is not empty
- no block is empty
- all blocks are reachable, either regularly or irregularly, from the entry node #0

Additional optional checks can be performed, see the parameters.

Parameters
cfg the CFG to be verified
checkConnected if true, the graph is verified to be connected, i.e. all blocks must be reachable from the entry block
checkGapless if true, the graph cannot have gaps between basic blocks
checkFlowinfo if true, consistency checks between getBreakingFlow(long) and getOutputBlocks() are performed
checkNoDupEdges if true, verify that CFG input/output regular edges of basic blocks do not contain duplicates
checkNoDupIrregularEdges if true, verify that CFG input/output irregular edges of basic blocks do not contain duplicates
Throws
RuntimeException if the verification failed