Documentation
¶
Overview ¶
Package cfg provides control flow graph (CFG) construction and analysis.
This package builds CFGs from statement sequences for flow-sensitive analysis. CFGs are essential for advanced static analysis including:
- Data flow analysis
- Taint propagation
- Dead code detection
- Reachability analysis
Basic Blocks ¶
A BasicBlock represents a maximal sequence of instructions with:
- Single entry point (at the beginning)
- Single exit point (at the end)
- No internal branches
Control Flow Graph ¶
Build a CFG from a sequence of statements:
cfg := cfg.BuildCFG(statements)
for _, block := range cfg.Blocks {
fmt.Printf("Block %d: %s\n", block.ID, block.Type)
for _, successor := range block.Successors {
fmt.Printf(" -> Block %d\n", successor.ID)
}
}
Block Types ¶
The package defines several block types:
- BlockTypeEntry: Function entry point
- BlockTypeExit: Function exit point
- BlockTypeNormal: Straight-line code
- BlockTypeConditional: If statements, ternary operators
- BlockTypeLoop: While/for loop headers
- BlockTypeSwitch: Switch/match statements
- BlockTypeTry: Try blocks
- BlockTypeCatch: Exception handlers
- BlockTypeFinally: Finally blocks
Usage Example ¶
// Build CFG for a function
cfg := cfg.NewControlFlowGraph("myapp.process_payment")
// Create basic blocks
entryBlock := &cfg.BasicBlock{
ID: 0,
Type: cfg.BlockTypeEntry,
}
cfg.Entry = entryBlock
cfg.Blocks = append(cfg.Blocks, entryBlock)
// Analyze control flow
for _, block := range cfg.Blocks {
if block.Type == cfg.BlockTypeConditional {
// Analyze both branches
}
}
Index ¶
- type BasicBlock
- type BlockType
- type ControlFlowGraph
- func (cfg *ControlFlowGraph) AddBlock(block *BasicBlock)
- func (cfg *ControlFlowGraph) AddEdge(fromBlockID, toBlockID string)
- func (cfg *ControlFlowGraph) ComputeDominators()
- func (cfg *ControlFlowGraph) GetAllPaths() [][]string
- func (cfg *ControlFlowGraph) GetBlock(blockID string) (*BasicBlock, bool)
- func (cfg *ControlFlowGraph) GetPredecessors(blockID string) []*BasicBlock
- func (cfg *ControlFlowGraph) GetSuccessors(blockID string) []*BasicBlock
- func (cfg *ControlFlowGraph) IsDominator(dominator, dominated string) bool
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BasicBlock ¶
type BasicBlock struct {
// ID uniquely identifies this block within the CFG
ID string
// Type categorizes the block for analysis purposes
Type BlockType
// StartLine is the first line of code in this block (1-indexed)
StartLine int
// EndLine is the last line of code in this block (1-indexed)
EndLine int
// Instructions contains the call sites within this block.
// Call sites represent function/method invocations that occur
// during execution of this block.
Instructions []core.CallSite
// Successors are the blocks that can execute after this block.
// For normal blocks: single successor
// For conditional blocks: two successors (true/false branches)
// For switch blocks: multiple successors (one per case)
// For exit blocks: empty (no successors)
Successors []string
// Predecessors are the blocks that can execute before this block.
// Used for backward analysis and dominance calculations.
Predecessors []string
// Condition stores the condition expression for conditional blocks.
// Empty for non-conditional blocks.
// Examples: "x > 0", "user.is_admin()", "data is not None"
Condition string
// Dominators are the blocks that always execute before this block
// on any path from entry. Used for security analysis to determine
// if sanitization always occurs before usage.
Dominators []string
}
BasicBlock represents a basic block in a control flow graph. A basic block is a maximal sequence of instructions with:
- Single entry point (at the beginning)
- Single exit point (at the end)
- No internal branches
Basic blocks are the nodes in a CFG, connected by edges representing control flow between blocks.
type BlockType ¶
type BlockType string
BlockType represents the type of basic block in a control flow graph. Different block types enable different security analysis patterns.
const ( // BlockTypeEntry represents the entry point of a function. // Every function has exactly one entry block. BlockTypeEntry BlockType = "entry" // BlockTypeExit represents the exit point of a function. // Every function has exactly one exit block where all return paths converge. BlockTypeExit BlockType = "exit" // BlockTypeNormal represents a regular basic block with sequential execution. // Contains straight-line code with no branches. BlockTypeNormal BlockType = "normal" // BlockTypeConditional represents a conditional branch block. // Has multiple successor blocks (true/false branches). // Examples: if statements, ternary operators, short-circuit logic. BlockTypeConditional BlockType = "conditional" // BlockTypeLoop represents a loop header block. // Has back-edges for loop iteration. // Examples: while loops, for loops, do-while loops. BlockTypeLoop BlockType = "loop" // BlockTypeSwitch represents a switch/match statement block. // Has multiple successor blocks (one per case). BlockTypeSwitch BlockType = "switch" // BlockTypeTry represents a try block in exception handling. // Has normal successor and exception handler successors. BlockTypeTry BlockType = "try" // BlockTypeCatch represents a catch/except block in exception handling. // Handles exceptions from try blocks. BlockTypeCatch BlockType = "catch" // BlockTypeFinally represents a finally block in exception handling. // Always executes regardless of exceptions. BlockTypeFinally BlockType = "finally" )
type ControlFlowGraph ¶
type ControlFlowGraph struct {
// FunctionFQN is the fully qualified name of the function this CFG represents
FunctionFQN string
// Blocks maps block IDs to BasicBlock objects
Blocks map[string]*BasicBlock
// EntryBlockID identifies the entry block
EntryBlockID string
// ExitBlockID identifies the exit block
ExitBlockID string
// CallGraph reference for resolving inter-procedural flows
CallGraph *core.CallGraph
}
ControlFlowGraph represents the control flow graph of a function. A CFG models all possible execution paths through a function, enabling data flow and taint analysis for security vulnerabilities.
Example:
def process_user(user_id):
user = get_user(user_id) # Block 1 (entry)
if user.is_admin(): # Block 2 (conditional)
grant_access() # Block 3 (true branch)
else:
deny_access() # Block 4 (false branch)
log_action(user) # Block 5 (merge point)
return # Block 6 (exit)
CFG Structure:
Entry → Block1 → Block2 → Block3 → Block5 → Exit
→ Block4 ↗
func NewControlFlowGraph ¶
func NewControlFlowGraph(functionFQN string) *ControlFlowGraph
NewControlFlowGraph creates and initializes a new CFG for a function.
func (*ControlFlowGraph) AddBlock ¶
func (cfg *ControlFlowGraph) AddBlock(block *BasicBlock)
AddBlock adds a basic block to the CFG.
func (*ControlFlowGraph) AddEdge ¶
func (cfg *ControlFlowGraph) AddEdge(fromBlockID, toBlockID string)
AddEdge adds a control flow edge from one block to another. Automatically updates both successors and predecessors.
func (*ControlFlowGraph) ComputeDominators ¶
func (cfg *ControlFlowGraph) ComputeDominators()
ComputeDominators calculates dominator sets for all blocks. A block X dominates block Y if every path from entry to Y must go through X. This is essential for determining if sanitization always occurs before usage.
Algorithm: Iterative data flow analysis
- Initialize: Entry dominates only itself, all others dominated by all blocks
- Iterate until fixed point: For each block B (except entry): Dom(B) = {B} ∪ (intersection of Dom(P) for all predecessors P of B)
func (*ControlFlowGraph) GetAllPaths ¶
func (cfg *ControlFlowGraph) GetAllPaths() [][]string
GetAllPaths returns all execution paths from entry to exit. Used for exhaustive security analysis. WARNING: Can be exponential in size for complex CFGs with loops.
func (*ControlFlowGraph) GetBlock ¶
func (cfg *ControlFlowGraph) GetBlock(blockID string) (*BasicBlock, bool)
GetBlock retrieves a block by ID.
func (*ControlFlowGraph) GetPredecessors ¶
func (cfg *ControlFlowGraph) GetPredecessors(blockID string) []*BasicBlock
GetPredecessors returns the predecessor blocks of a given block.
func (*ControlFlowGraph) GetSuccessors ¶
func (cfg *ControlFlowGraph) GetSuccessors(blockID string) []*BasicBlock
GetSuccessors returns the successor blocks of a given block.
func (*ControlFlowGraph) IsDominator ¶
func (cfg *ControlFlowGraph) IsDominator(dominator, dominated string) bool
IsDominator returns true if dominator dominates dominated. Used to check if sanitization (in dominator) always occurs before usage (in dominated).