cfg

package
v0.0.0-...-d33c02b Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 16, 2025 License: AGPL-3.0 Imports: 1 Imported by: 0

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

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

  1. Initialize: Entry dominates only itself, all others dominated by all blocks
  2. 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).

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL