Most serious bugs do not live in one function. Input arrives in one place, travels through a few helpers, and reaches a dangerous line somewhere else entirely. To follow that path you need a map of which function calls which, and building that map is what call graph analysis gives you. This post explains what a call graph is, why it is the backbone of any analysis that crosses function boundaries, and where it gets hard and honestly stays an approximation.
What a call graph is
A call graph is a simple idea drawn out in full. Each function in your program is a node. Each call from one function to another is an edge, drawn from the caller to the callee. That is the whole structure. If handleRequest calls parseBody, and parseBody calls saveToDb, you get three nodes and two edges, a little chain you can walk.
Once you have that map, two questions become answerable. Point at a function and ask who calls this, and you follow the edges backward. Ask what does this call, and you follow them forward. Those two questions sound small, but almost every question that matters in security is built out of them.
Why call graph analysis is the backbone
Here is the reason it matters. A bug where user input arrives in one function and reaches a sink in another is invisible if you only read one function at a time. You have to connect the two, and the call graph is the thing that connects them.
Take a small example spread across three functions:
def handle(req):
name = req.query["name"]
return build_page(name)
def build_page(value):
return render(value)
def render(text):
return "<div>" + text + "</div>"The tainted value enters in handle. It is passed to build_page, then to render, where it lands in raw HTML with no escaping. That is a cross site scripting bug. But no single function looks wrong on its own. handle just reads a query parameter. render just concatenates two strings. Only when you walk the edges from handle to build_page to render does the flow appear. Tracking a tainted value across those hops is called interprocedural taint analysis, and you can read more on interprocedural taint analysis. None of it works without the call graph underneath.
A single function almost never looks guilty. The bug lives in the edges between functions, which is exactly what a call graph makes visible.
Direct calls are easy
When the call target is written in the text, the edge is obvious. saveToDb(row) names the function it calls. A parser reads that line, sees the name, and draws an edge to saveToDb. This is the easy case, and for a lot of straight line code it is most of the graph. Direct calls are why call graph tools feel reliable at first glance.
Indirect calls are the hard part
The trouble starts when the target is not written in the text. Plenty of real code decides at run time which function to call:
- Virtual methods.
animal.speak()could run the dog version or the cat version depending on the object’s real type. - Function pointers. A C struct holds a pointer to a handler that gets set somewhere far away and called later.
- Callbacks. You pass a function into
sortor an event listener, and the library calls it back with no name at the call site. - Dynamic dispatch and reflection. Code that does
getattr(obj, method_name)()picks the target from a string, sometimes a string that came from input.
In every one of these, the call site does not say who it calls. The actual target is decided by data that flows in at run time. So the analysis has to guess, and a call graph stops being a fact and becomes an approximation.
Overapproximation versus underapproximation
There are two ways to be wrong about an indirect call, and they fail in opposite directions.
- Overapproximation adds every target that could possibly be called. If a function pointer might point at any of five handlers, draw edges to all five. This is safe, because you never miss a real call, but it is noisy. You end up chasing flows through targets that never actually run, and the graph gets crowded.
- Underapproximation only draws edges it is sure about and skips the rest. This is quiet and clean, but unsafe, because a target you dropped might be the exact one the attacker reaches. A missed edge is a missed bug.
Good tools lean toward overapproximation for anything security relevant, then work to trim the noise, because a false path costs you time but a missing path costs you the finding. The honest framing is that no call graph over a language with dynamic dispatch is exact. It is a careful estimate, and knowing which way it errs tells you how to read its results.
Where text search quietly fails and a real graph does not
The clearest reason to build a real call graph instead of grepping is that names lie. Search finds the string you typed. It does not follow a rename or an alias.
Suppose a function is imported under a new name:
from db import execute as run_query
def save(row):
run_query("INSERT ...") # this calls db.executeNow search your codebase for callers of execute. The line above never matches, because the text says run_query. To a person skimming grep results, save looks like it has nothing to do with execute. It is a hidden caller. A call graph built from a real parse resolves the import, sees that run_query is a local alias for db.execute, and draws the edge anyway. Ask it who calls execute and save shows up. The same holds for a method renamed in a subclass, a wrapper that forwards a call, or an object bound to a shorter local variable. Text does not track identity across a rename. A graph built from the compiler’s own understanding does.
This is what a precise call graph from a real parse is for. It answers who calls this and what does this call without dropping an aliased caller because the letters changed. The public engine we build for this is lachesis, which reads the code the way the compiler does rather than the way search does. It is the same structural idea behind a code property graph, which you can read about in what is a code property graph.
Reading a call graph honestly
Because indirect calls make the graph an estimate, treat every edge as evidence with a confidence, not as a verdict. A direct call is solid. A function pointer resolved through data flow is a good guess. A call through reflection off an input string may be unresolved, which means the tool is telling you it does not know, not that nothing is called there. That last case is where a human still has to read the source. Knowing the difference between scanners that pattern match and research that reasons about a program is its own topic, covered in scanners vs research.
A call graph is the map that lets an analysis cross function boundaries at all, and getting the indirect edges right is most of the work. That mapping is exactly the groundwork an autonomous researcher needs before it can reason about how one function’s assumptions break in another, which is what we build toward at UnboundCompute.
Frequently asked questions
What is a call graph?
A call graph is a map of a program where each function is a node and each call from one function to another is an edge drawn from caller to callee. If handle calls build_page and build_page calls render, you get three nodes and two edges you can walk. It lets you ask who calls a function and what a function calls.
Why does call graph analysis matter for finding bugs?
Many serious bugs span more than one function. Input arrives in one place and reaches a dangerous line somewhere else, so no single function looks wrong on its own. The call graph connects the caller to the callee, which is what lets an analysis follow a tainted value across function boundaries and see the flow that a single function view hides.
Why are indirect calls hard for a call graph?
With virtual methods, function pointers, callbacks, and reflection, the call target is decided by data at run time and is not written at the call site. The tool has to estimate the targets, so the graph becomes an approximation. It can overapproximate by adding every possible target, which is safe but noisy, or underapproximate by dropping uncertain ones, which is quiet but can miss a real bug.
Why not just grep for who calls a function?
Text search only finds the string you typed, so it misses a caller when a function is renamed or imported under an alias. If db.execute is imported as run_query, a search for execute never matches the call. A call graph built from a real parse resolves the alias and still draws the edge, so the hidden caller shows up.
Put an autonomous researcher on your own systems
UnboundCompute is an autonomous security researcher that reasons about how an application fits together and proves the access control and injection bugs it finds. We are opening a small number of founding design partner seats: private early access pointed at a staging target you choose, and a say in what it looks for. If your team ships software worth pressure testing, apply to the design partner program.