Programming lesson
Dynamic Control Dependence Analysis with Pintool: Reconstructing Malware Execution Paths from GreenCat Traces
Learn how to build a dynamic control dependence graph (CDG) using Intel Pin and Python, inspired by a malware investigation scenario. This tutorial walks through computing immediate post-dominators from execution traces and generating DOT graphs to link C&C commands to malicious payloads.
Introduction: Why Dynamic Control Dependence Matters in Malware Analysis
In cybersecurity, understanding how a malware sample behaves under different inputs is crucial. Static analysis often falls short when code is packed, self-modifying, or obfuscated. Dynamic analysis, on the other hand, reveals true execution paths. A dynamic control dependence graph (CDG) maps each executed instruction to the predicate (branch condition) that controls its execution. This is exactly what you need when investigating a malware like greencat—you want to know which command-and-control (C&C) command triggered each malicious payload.
In this tutorial, we'll build a pintool (using Intel Pin) that records a dynamic control flow trace, then compute immediate post-dominators (IPDs) from that trace to derive the CDG. We'll output a DOT file ready for visualization. This approach mirrors real-world malware analysis workflows, where analysts instrument binaries, replay network inputs, and compare against packet captures.
Background: Control Dependence and Post-Dominators
Control dependence answers the question: Which branch decisions determine whether a particular instruction executes? Formally, instruction Y is control dependent on instruction X if:
- There exists a path from X to Y such that every node on that path (except X and Y) is post-dominated by Y.
- X is not post-dominated by Y.
Immediate post-dominator (IPD) of a node N is the unique node that post-dominates N and is post-dominated by every other post-dominator of N. In a dynamic trace, we approximate IPDs by analyzing the sequence of executed basic blocks. This is similar to how you might analyze a sports game: each play (instruction) depends on the coach's decision (predicate) that set the strategy.
Step 1: Setting Up Your Pintool for Dynamic Tracing
Your pintool from Lab #5 likely already instruments every instruction and records the control flow (e.g., taken/not taken branches). We'll extend it to collect a trace of instruction addresses and basic block transitions. For simplicity, we'll write a pintool that:
- Inserts a call before every instruction to log its address.
- Inserts a call before every branch to log the branch target and whether it was taken.
After execution, the pintool writes a trace file. Alternatively, you can accumulate data in memory and output at the end.
Pintool Skeleton (C++)
#include <fstream>
#include <iostream>
#include <pin.H>
ofstream OutFile;
VOID RecordInst(ADDRINT addr) {
OutFile << "I " << addr << endl;
}
VOID RecordBranch(ADDRINT ip, BOOL taken, ADDRINT target) {
OutFile << "B " << ip << " " << taken << " " << target << endl;
}
VOID Instruction(INS ins, VOID *v) {
INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)RecordInst,
IARG_ADDRINT, INS_Address(ins), IARG_END);
if (INS_IsBranch(ins) && INS_HasFallThrough(ins)) {
INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)RecordBranch,
IARG_ADDRINT, INS_Address(ins),
IARG_BRANCH_TAKEN,
IARG_ADDRINT, INS_DirectBranchOrCallTarget(ins),
IARG_END);
}
}
VOID Fini(INT32 code, VOID *v) {
OutFile.close();
}
int main(int argc, char *argv[]) {
PIN_Init(argc, argv);
OutFile.open("trace.out");
INS_AddInstrumentFunction(Instruction, 0);
PIN_AddFiniFunction(Fini, 0);
PIN_StartProgram();
return 0;
}Compile with: make obj-intel64/yourpintool.so
Step 2: Collecting Traces for Each C&C Command
From previous labs, you know greencat accepts commands like: cmd1, cmd2, etc. (refer to your earlier analysis). For each command, run greencat with your pintool:
pin -t obj-intel64/yourpintool.so -- ./greencat < cmd1.txtThis produces trace_cmd1.out. Repeat for all commands.
Step 3: Post-Processing with Python to Compute CDG
Now we'll parse the trace and build a control flow graph (CFG) of basic blocks, then compute IPDs and finally the CDG. We'll use NetworkX for graph operations.
Parse Trace into Basic Blocks
Group consecutive instructions that are not separated by a branch into a basic block. Each block has a start address and a list of instructions.
import networkx as nx
def parse_trace(filename):
blocks = []
current_block = []
with open(filename) as f:
for line in f:
parts = line.split()
if parts[0] == 'I':
addr = int(parts[1], 16)
current_block.append(addr)
elif parts[0] == 'B':
# branch ends current block
blocks.append(current_block)
current_block = []
if current_block:
blocks.append(current_block)
return blocks
Build CFG
Each block is a node (use start address as ID). Add edges based on branch taken/fall-through.
def build_cfg(blocks, trace_filename):
G = nx.DiGraph()
# add nodes
for i, block in enumerate(blocks):
start = block[0]
G.add_node(start, instrs=block)
# add edges from trace (branch lines)
with open(trace_filename) as f:
for line in f:
if line.startswith('B'):
parts = line.split()
ip = int(parts[1], 16)
taken = parts[2] == '1'
target = int(parts[3], 16)
# find source block (block containing ip)
src = None
for b in blocks:
if ip in b:
src = b[0]
break
# find dest block (block starting at target if taken, else next sequential)
if taken:
dst = target
else:
# fall-through: next instruction after ip
# need to find the next instruction address
# simplified: assume next block starts after ip
idx = blocks.index(src)
if idx + 1 < len(blocks):
dst = blocks[idx+1][0]
else:
continue
G.add_edge(src, dst)
return G
Compute Immediate Post-Dominators
We'll compute post-dominators using the standard algorithm: reverse the graph, compute dominators, then map back.
def get_ipd(G, start):
# reverse graph
revG = G.reverse()
# compute dominators in revG (post-dominators in original)
dom = nx.dominance.frontiers(revG, start) # not exactly; we need immediate dominators
# Actually use nx.immediate_dominators
idom = nx.immediate_dominators(revG, start)
# idom maps node -> immediate dominator in reversed graph = immediate post-dominator in original
return idom
Note: NetworkX provides nx.immediate_dominators(G, root). For post-dominators, we reverse the graph and compute dominators. The root in reversed graph is the exit node (or a virtual exit). We'll add a virtual EXIT node that has edges from all nodes with no successors.
Compute Control Dependence
Using the IPD map, we can compute control dependence edges. For each edge (A->B) in the original CFG, if A is not post-dominated by B, then all nodes on the path from A to B (excluding A and B) are control dependent on A. However, a simpler method: for each node X, its control dependence set is the set of nodes Y such that Y is in the dominance frontier of X in the post-dominator tree. But we can also iterate over CFG edges.
Here's a practical approach: for each CFG edge (u->v), if v is not in IPD[u] (i.e., u does not post-dominate v), then v is control dependent on u. Additionally, for nodes that are not post-dominated by any predecessor, they are control dependent on START.
def compute_cdg(G, ipd_map):
cdg = nx.DiGraph()
# add all nodes
for node in G.nodes():
cdg.add_node(node)
# add edges: for each CFG edge (u->v), if v not post-dominated by u, then v -> u (edge in CDG)
for u, v in G.edges():
if v not in ipd_map or ipd_map[v] != u: # u does not post-dominate v
cdg.add_edge(v, u) # v is control dependent on u
# handle START node (optional)
return cdg
Generate DOT File
def write_dot(cdg, filename):
nx.drawing.nx_pydot.write_dot(cdg, filename)
Run for each command trace and produce cdg_cmd1.dot, etc.
Step 4: Visualizing and Interpreting Results
Open the DOT file with Graphviz or a viewer. You should see a directed graph where edges point from an instruction to the predicate it depends on. For example, if instruction 0x4005a0 is control dependent on branch at 0x400580, there will be an edge 0x4005a0 -> 0x400580.
By comparing CDGs across C&C commands, you can identify which predicates are unique to each command. This helps pinpoint which network input triggers which malware behavior—exactly like matching packet traces in the original attack.
Putting It All Together: Full Python Script
import sys
import networkx as nx
def main(trace_file, output_dot):
blocks = parse_trace(trace_file)
G = build_cfg(blocks, trace_file)
# Add EXIT node
exit_node = 'EXIT'
G.add_node(exit_node)
for node in list(G.nodes()):
if node != exit_node and G.out_degree(node) == 0:
G.add_edge(node, exit_node)
# compute IPD using reversed graph
revG = G.reverse()
# need to ensure all nodes reachable from EXIT in reversed graph
idom = nx.immediate_dominators(revG, exit_node)
# map back to original nodes
ipd = {}
for node, dom in idom.items():
if dom != exit_node:
ipd[node] = dom
cdg = compute_cdg(G, ipd)
write_dot(cdg, output_dot)
if __name__ == '__main__':
main(sys.argv[1], sys.argv[2])
Usage: python build_cdg.py trace_cmd1.out cdg_cmd1.dot
Trend Connection: AI-Powered Malware Analysis
Just as AI models like GPT-4 are now used to generate code, they are also used to detect malware. Dynamic control dependence graphs feed into machine learning classifiers that identify malicious patterns. Understanding how to build these graphs manually gives you insight into the features that AI models use—making you a more effective cybersecurity professional in an AI-driven world.
Conclusion
By combining a pintool for dynamic tracing with a Python post-processing script, you've built a dynamic control dependence analyzer. This tool reveals which C&C commands drive each part of the greencat malware, enabling precise reconstruction of attack steps. The same technique applies to any binary with obfuscated control flow. In future labs, you might extend this to perform program slicing or integrate with Ghidra for visualization.
Key takeaway: Dynamic analysis with control dependence is a powerful weapon in the fight against malware—use it wisely.