Call Graphs & Accountability: What Execution Can and Can’t Prove

Call graphs show which functions call which, but they cannot prove what actually happened during execution. This article explains what call graphs can and cannot demonstrate about program behavior, accountability, and debugging, and how to use them effectively.

Background: What a Call Graph Is

A call graph is a directed graph that represents calling relationships between subroutines in a computer program. Each node represents a function or method, and each directed edge from function A to function B indicates that A calls B. Call graphs can be built statically from source code or dynamically from execution traces. Static call graphs include all possible calls based on code analysis, while dynamic call graphs show only the calls that actually occurred during a particular run.

How Call Graphs Are Built

There are two main approaches to constructing call graphs:

• Static analysis: The compiler or a separate tool parses the source code and determines all potential call sites. This includes indirect calls through function pointers, virtual methods, and reflection, which are challenging to resolve precisely.
• Dynamic tracing: The program is instrumented to log every function entry and exit during execution. This produces an exact record of what happened in that specific run, but only for the inputs and code paths exercised.

Dynamic call graphs are often used for profiling and debugging because they reflect actual behavior. Static call graphs are useful for understanding the overall structure and for detecting potential issues like unreachable code or missing dependencies.

What Execution Can Prove

When you have a dynamic call graph from a specific execution, you can prove several things about that run:

• Which functions were actually called: The set of nodes that appear in the graph are exactly the functions that were entered at least once.
• Call order and nesting: The edges and their traversal order show the sequence of calls and the call stack depth at each point.
• Coverage of code paths: By comparing the dynamic call graph to the static one, you can see which branches and functions were not exercised.
• Performance bottlenecks: Combined with timing data, you can identify which functions consumed the most time or were called most frequently.

These facts are empirical and reproducible for the same input and environment. They are the basis for many debugging and profiling tools.

What Execution Cannot Prove

However, a call graph from a single execution (or even many executions) has significant limitations:

• It cannot prove correctness: A function may be called with valid inputs and produce wrong results without any call graph anomaly. The graph only shows that the call happened, not whether the logic was correct.
• It cannot prove absence of bugs: The fact that a particular bug did not manifest in one run does not mean it cannot occur with different inputs or under different conditions. The call graph only covers the executed paths.
• It cannot prove thread safety: Even if a dynamic call graph shows no race condition in one run, concurrency bugs are often timing-dependent and may not appear in that trace.
• It cannot prove resource safety: Memory leaks, file handle leaks, or deadlocks may not be visible in a call graph unless the graph includes resource acquisition and release events, which it typically does not.
• It cannot prove security: A call graph cannot show that a function is vulnerable to injection or that an attacker can reach a dangerous function. It only shows the call relationships, not the data flow or input validation.

Accountability in Debugging

Call graphs are often used for accountability in the sense of understanding who is responsible for a failure. For example, if a program crashes, a dynamic call graph (or stack trace) can show the exact sequence of calls that led to the crash. This helps pinpoint the function that triggered the error and the caller that passed bad data. However, the call graph alone does not tell you why the bad data was passed or whether the root cause is in the caller, the callee, or an earlier mutation. You need additional information like variable values, logs, or memory dumps to establish causality.

Common Misconceptions and Pitfalls

One common misconception is that a static call graph is a complete and accurate representation of program behavior. In languages with dynamic dispatch (e.g., C++ virtual functions, Java interfaces, Python dynamic typing), static analysis may produce false positives (calls that never happen) or false negatives (calls that are missed). This can lead to incorrect conclusions about reachability or impact analysis.

Another pitfall is assuming that a dynamic call graph from a test run covers all production scenarios. If the test inputs are not representative, the call graph will miss critical paths. This is why coverage tools are used to measure how much of the static graph was exercised, but even 100% line coverage does not guarantee correctness.

How to Use Call Graphs Effectively

To get the most value from call graphs for accountability and debugging:

1. Combine static and dynamic graphs: Use the static graph for structure and the dynamic graph for actual behavior. Compare them to find dead code or unexpected calls.
2. Instrument with data: Record not just calls but also key variable values, return values, and timestamps. This turns a call graph into a rich execution trace.
3. Use multiple runs: For concurrency or input-dependent behavior, collect several traces with different inputs and seeds to increase confidence.
4. Correlate with logs: Cross-reference call graphs with application logs to understand the context of each call.
5. Automate regression analysis: When a bug is fixed, compare the call graph of the failing test before and after the fix to ensure the intended path is now taken.

Frequently Asked Questions

Can a call graph prove that a program is bug-free?

No. A call graph only shows the calling relationships, not the correctness of the logic inside each function. Even if a dynamic call graph shows a clean run, there could be latent bugs that only appear with different inputs or environments.

What is the difference between a call graph and a stack trace?

A stack trace is a snapshot of the current call stack at a single moment (usually at an error). A call graph is a complete record of all calls made during a run (or all possible calls in static analysis). A stack trace is like a single frame from a movie, while a call graph is the whole screenplay.

How can I get a call graph from my code?

For static graphs, tools like Doxygen (C++), pyan (Python), or CodeViz can generate them. For dynamic graphs, you can use profilers like gprof, perf, or language-specific tracing tools (e.g., Python’s trace module, Java’s JFR). Many IDEs also have built-in call graph visualization.

Can call graphs help with security auditing?

They can help identify attack surface by showing which functions are reachable from external inputs, but they cannot prove that a vulnerability is exploitable. You still need to analyze data flow and input validation.

Are call graphs useful for microservices or distributed systems?

Traditional call graphs are for single-process programs. For distributed systems, you need distributed tracing (like Jaeger or Zipkin) that spans services. These traces effectively create a call graph across processes, but they have additional challenges like clock synchronization and sampling.

Related

• Nginx UI vs Nginx Proxy Manager: Which to Use?
• Business AI Agent Data Needs & Access Control
• How to Delete Saved Passwords: Desktop & Mobile