Ever Wondered How Static Analysis Tools Find Bugs? Start with CFG and DFG

These are 9 parts explaining Control Flow Graphs, Data Flow Graphs, Program Dependence Graphs, program slicing, binary CFG recovery, and graph-based vulnerability detection.

Index

Why Static Analysis Tools Think in Graphs
Control Flow Graphs - Mapping How Code Executes
Data Flow Graphs - Following Data from Source to Sink
Program Dependence Graphs - Where Control Flow Meets Data Flow
Program Slicing - Reducing Noise in Static Analysis
Recovering Control Flow Graphs from Binaries and Firmware
Using CFG, DFG, and PDG for Vulnerability Detection
From CFG and DFG to Code Property Graphs and ML-Based Analysis
Building a Simple Static Analyzer with CFG and DFG Concepts

1. Why Static Analysis Tools Think in Graphs

Static analysis tools do not simply read source code line by line. They transform programs into structured representations that make program behavior easier to reason about. One of the most important forms of representation is the program graph.

Program graphs allow tools to answer questions such as:

Which code paths are reachable?
Where does user-controlled input go?
Which statements depend on a condition?
Can a dangerous function be reached without proper validation?

Why Raw Code Is Hard to Analyze

Source code is written for humans, but static analysis tools need structure. A simple program may contain branches, loops, function calls, callbacks, exceptions, and external input. Reading the text alone is not enough.

x = input()
y = x + "test"
print(y)

A human can immediately understand that x comes from user input and then flows into y. A static analyzer represents this relationship as a graph:

Basic Graph Concepts

Before studying program graphs, we need a few basic terms:

Node: an instruction, statement, variable, function, or basic block.
Edge: a relationship between two nodes.
Path: a sequence of connected nodes.
Source: a point where data enters the program, such as user input.
Sink: a sensitive operation, such as SQL execution, command execution, or file access.

Main Program Graphs

Graph	Purpose
Control Flow Graph	Shows possible execution paths.
Data Flow Graph	Shows how values move through the program.
Program Dependence Graph	Combines control dependence and data dependence.
Call Graph	Shows relationships between functions.
Code Property Graph	Combines multiple graph views for vulnerability discovery.

Security Relevance

In application security, these graphs help detect vulnerabilities such as SQL injection, command injection, path traversal, missing authorization, insecure deserialization, and unsafe memory usage.

For example, a tool may search for this pattern:

2. Control Flow Graphs - Mapping How Code Executes

A Control Flow Graph, or CFG, represents the possible execution paths inside a program. It is one of the most important structures used in compilers, static analysis tools, symbolic execution engines, reverse engineering tools, and vulnerability scanners.

What Is a Control Flow Graph?

In a CFG:

Each node usually represents a basic block.
Each edge represents a possible transfer of control.
Branches, loops, returns, exceptions, and function calls create control-flow edges.

A basic block is a sequence of instructions with one entry point and one exit point.

Example

int check_login(int attempts, int is_admin) {
    if (is_admin) {
        return 1;
    }

    if (attempts > 3) {
        return 0;
    }

    return 1;
}

Simplified CFG

Why CFG Matters

A CFG helps answer questions such as:

Can this code be reached?
Can a security check be bypassed?
Can a dangerous function execute?
Are there unreachable blocks?
Does every branch return safely?

Security Example: Missing Return After Authentication Failure

void handle_request(char *user, int authenticated) {
    if (!authenticated) {
        printf("Access denied\n");
    }

    system(user);
}

The developer checks whether the user is authenticated, but the function does not stop execution when authentication fails.

CFG View


The dangerous function system(user) is reachable whether authentication succeeds or fails.

Fixed Version

void handle_request(char *user, int authenticated) {
    if (!authenticated) {
        printf("Access denied\n");
        return;
    }

    system(user);
}

3. Data Flow Graphs - Following Data from Source to Sink

A Data Flow Graph, or DFG, represents how values move through a program. While a Control Flow Graph explains which paths are possible, a Data Flow Graph explains where data comes from and where it goes.

What Is a Data Flow Graph?

In a DFG:

Nodes represent variables, expressions, operations, or instructions.
Edges represent data dependencies.
The graph shows how values are created, transformed, and consumed.

Simple Example

int total_price(int price, int quantity) {
    int subtotal = price * quantity;
    int tax = subtotal / 10;
    int total = subtotal + tax;
    return total;
}

Simplified DFG

Security Meaning

In security analysis, DFGs are often used for taint analysis. Taint analysis tracks whether attacker-controlled input can reach a dangerous operation.

Example: SQL Injection

from flask import request
import sqlite3

@app.route("/user")
def get_user():
    user_id = request.args.get("id")
    query = "SELECT * FROM users WHERE id = " + user_id
    result = db.execute(query)
    return result

DFG View

The attacker-controlled value from request.args.get("id") flows into db.execute(query). This is a classic source-to-sink vulnerability path.

Fixed Version

@app.route("/user")
def get_user():
    user_id = request.args.get("id")
    result = db.execute(
        "SELECT * FROM users WHERE id = ?",
        (user_id,)
    )
    return result

4. Program Dependence Graphs - Where Control Flow Meets Data Flow

A Program Dependence Graph, or PDG, combines control dependence and data dependence into one representation. It allows static analysis tools to understand not only how data moves, but also which conditions control the execution of statements.

Why CFG and DFG Alone Are Not Enough

A CFG tells us which execution paths are possible. A DFG tells us how values flow. But many security questions require both.

For example:

void update_email(char *email, int is_verified) {
    if (is_verified) {
        save_email(email);
    }
}

The call to save_email(email) is:

Data-dependent on email.
Control-dependent on is_verified.

Example: Money Transfer

void transfer(int balance, int amount, int is_admin) {
    if (is_admin) {
        balance = balance - amount;
        send_money(amount);
    }
}

Dependency View

send_money(amount)
    data-dependent on: amount
    control-dependent on: is_admin

balance = balance - amount
    data-dependent on: balance, amount
    control-dependent on: is_admin

Simplified PDG

Security Use

PDGs are useful for understanding authorization logic, source-to-sink paths, validation checks, and program slicing. A vulnerability scanner can use PDG-style reasoning to ask:

Is this dangerous operation controlled by a security check?
Does attacker-controlled data reach the operation?
Is the validation actually connected to the sensitive sink?

5. Program Slicing - Reducing Noise in Static Analysis

Program slicing is a technique used to extract only the parts of a program that are relevant to a specific variable, statement, or behavior. It helps developers, researchers, and static analysis tools focus on the code that matters.

What Is Program Slicing?

A program slice is a subset of a program that affects, or is affected by, a selected point of interest. This point is called the slicing criterion.

Example

int main() {
    int a = 10;
    int b = 20;
    int c = a + b;
    int d = 5;
    printf("%d", c);
}

If we slice backward from:

printf("%d", c);

The relevant code is:

int a = 10;
int b = 20;
int c = a + b;
printf("%d", c);

The following statement is irrelevant to the value of c:

int d = 5;

Backward Slicing

Backward slicing answers:

Which statements could affect this point?

This is useful for debugging and vulnerability root-cause analysis.

Forward Slicing

Forward slicing answers:

Which statements could be affected by this value?

This is useful for impact analysis and taint propagation.

Security Example

name = request.args.get("name")
safe = "hello"
cmd = "echo " + name
os.system(cmd)

A backward slice from os.system(cmd) keeps:

name = request.args.get("name")
cmd = "echo " + name
os.system(cmd)

It removes:

safe = "hello"

6. Recovering Control Flow Graphs from Binaries and Firmware

Control Flow Graphs are not only useful for source code. They are also essential in binary analysis, malware analysis, firmware research, exploit development, and reverse engineering.

What Is CFG Recovery?

CFG recovery is the process of reconstructing possible execution paths from compiled binary code. Unlike source-code analysis, binary analysis does not have high-level constructs such as clear function names, variables, classes, or type information.

Why Binary CFG Recovery Is Difficult

Binary CFG recovery is difficult because binaries may contain:

Indirect jumps
Function pointers
Jump tables
Callbacks
Exception handlers
Obfuscation
Dynamically loaded code

Example: Function Pointer

void (*handler)(void);

void register_handler(void (*h)(void)) {
    handler = h;
}

void interrupt_event() {
    handler();
}

Incomplete CFG

Recovered CFG

Static vs Dynamic CFG Recovery

Approach	Description	Strength	Weakness
Static	Analyzes the binary without running it.	Good coverage.	Hard to resolve indirect control flow.
Dynamic	Observes execution at runtime.	Accurate observed paths.	May miss unexecuted paths.
Hybrid	Combines static and dynamic analysis.	Better balance.	More complex.

7. Using CFG, DFG, and PDG for Vulnerability Detection

Modern vulnerability detection often depends on graph-based reasoning. A security tool needs to understand not only what the code says, but how execution and data movement interact.

Source-to-Sink Analysis

Many vulnerabilities can be described as a source-to-sink problem:

Examples of sources include:

HTTP parameters
Cookies
Headers
Uploaded files
Environment variables

Examples of sinks include:

SQL execution
Command execution
File system access
Template rendering
Deserialization

Example: Command Injection

import os
from flask import request

@app.route("/ping")
def ping():
    host = request.args.get("host")

    if host:
        cmd = "ping -c 1 " + host
        return os.popen(cmd).read()

    return "Missing host"

Data Flow

Control Flow

Secure Version

import subprocess
import re
from flask import request

@app.route("/ping")
def ping():
    host = request.args.get("host")

    if not re.match(r"^[a-zA-Z0-9.-]+$", host):
        return "Invalid host"

    result = subprocess.run(
        ["ping", "-c", "1", host],
        capture_output=True,
        text=True
    )

    return result.stdout

Why Graphs Help

The DFG shows that attacker input reaches the command.
The CFG shows that the sink is reachable when host exists.
The PDG can show whether validation controls the sink.

8. From CFG and DFG to Code Property Graphs and ML-Based Analysis

Modern program analysis rarely depends on only one graph. Instead, tools often combine multiple program representations to capture syntax, execution, data movement, dependencies, and function relationships.

Why One Graph Is Not Enough

A CFG can show execution paths, but it does not fully explain data movement. A DFG can show value dependencies, but it does not fully explain which paths are executable. A call graph can show function relationships, but it does not show statement-level behavior.

Common Program Representations

Representation	What It Captures
AST	Syntax structure.
CFG	Execution paths.
DFG	Data movement.
PDG	Control and data dependencies.
Call Graph	Function-to-function relationships.
Code Property Graph	Combined representation for security queries.

Combined View

Graph-Based Machine Learning

Modern research uses graph neural networks and graph-based embeddings to detect vulnerabilities, classify code behavior, infer variable usage, and perform compiler optimization tasks.

Instead of representing code as plain text, these approaches encode structural information such as:

Which variable depends on which input
Which branch controls a sensitive call
Which function calls another function
Which operations are reachable

Limitations

Graph-based analysis is powerful, but it is not perfect. Common challenges include:

False positives
False negatives
Incomplete call graph construction
Dynamic language features
Reflection and callbacks
Obfuscation
Scalability on large codebases

9. Building a Simple Static Analyzer with CFG and DFG Concepts

In this part, we build a simple mental model for a static analyzer. The goal is not to create a production-grade scanner, but to understand how CFG and DFG concepts become practical vulnerability detection logic.

Target Code

from flask import request
import os

def run():
    name = request.args.get("name")
    cmd = "echo " + name
    os.system(cmd)

Detection Goal

We want to detect whether attacker-controlled input reaches a dangerous command-execution sink.

source: request.args.get
sink: os.system
path: request.args.get -> name -> cmd -> os.system
result: possible command injection

Step 1: Define Sources

sources = [
    "request.args.get",
    "request.form.get",
    "input"
]

Step 2: Define Sinks

sinks = [
    "os.system",
    "os.popen",
    "subprocess.call",
    "subprocess.Popen",
    "db.execute"
]

Step 3: Track Assignments

name = request.args.get("name")

The variable name becomes tainted because it receives data from a source.

Step 4: Propagate Taint

cmd = "echo " + name

The variable cmd becomes tainted because it depends on name.

Step 5: Detect Sink Usage

os.system(cmd)

The analyzer reports a finding because tainted data reaches a command-execution sink.

Pseudo-Code

sources = ["request.args.get", "input"]
sinks = ["os.system", "subprocess.call", "db.execute"]

for assignment in program.assignments:
    if assignment.value in sources:
        mark_as_tainted(assignment.variable)

    if assignment.value_uses_tainted_variable():
        mark_as_tainted(assignment.variable)

for call in program.calls:
    if call.function in sinks:
        if any(argument_is_tainted(arg) for arg in call.arguments):
            report_vulnerability(call)

Adding Control-Flow Awareness

A more advanced analyzer also checks whether the dangerous sink is protected by validation:

if is_safe(name):
    os.system("echo " + name)

This requires control-flow and dependence analysis, not just simple data tracking.