Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer Information

Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer Information

Speakers: Yuandao Cai

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=v3baeOaUCJ8

Overview

This talk, presented by Yuandao Cai from The Hong Kong University of Science and Technology on behalf of the authors, introduces a novel approach to call graph construction, a fundamental task in program analysis and verification. The research tackles the long-standing challenge of precisely and efficiently resolving indirect function calls, particularly prevalent in C programs. While call graphs are critical for understanding program behavior and enabling various security and reliability analyses, existing methods struggle to balance precision with scalability when dealing with the complexities of C's function pointers.

The core of this work lies in identifying and leveraging distinct characteristics of function pointers to apply the most appropriate analysis technique. By intelligently combining pointer analysis for "simple" indirect calls and a refined type analysis for "complex" ones, the presented system, named C, aims to overcome the limitations of traditional approaches. The talk highlights how this hybrid methodology significantly enhances the precision of call graph construction without incurring prohibitive performance overhead, making it applicable to large-scale real-world software systems.

The significance of this research extends beyond mere academic improvement. Accurate call graphs are the bedrock for numerous downstream applications, including vulnerability detection, static analysis for concurrency bugs, and effective fuzzing. By providing a more reliable foundation, C promises to improve the efficacy and reduce the false positive rates of these critical security tools, thereby contributing to the development of more robust and secure software systems.

Background

▶ Watch: Introduction to call graphs and indirect call challenges (0:00)

The call graph, a fundamental representation in program analysis, depicts the caller-to-callee relationships among functions within a program. Its importance cannot be overstated, serving as a cornerstone for understanding program control flow, enabling various static analyses, and facilitating program verification. The concept dates back to 1979 with Baba-Rer publishing the first algorithm for Fortran programs. In the context of the C language, which continues to power critical systems and software worldwide, call graph construction presents unique challenges due to its extensive use of function pointers. Function pointers enable more compact code and dynamic program behavior, but they introduce indirect calls where the target function is not explicitly named but determined at runtime. A study cited in the talk found that over 16% of functions in representative open-source C projects are invoked via indirect calls.

Resolving these indirect calls accurately is a notoriously difficult problem. Two primary categories of techniques have been explored:

1. Type Analysis: This approach resolves indirect targets by checking the type comparability between all address-taken functions and all function pointers. It is highly scalable, capable of analyzing millions of lines of code in minutes, but suffers from significant imprecision. Type analysis overlooks memory load and store operations, leading to an over-approximation of possible targets. For instance, if a function pointer's type matches multiple address-taken functions, type analysis will conservatively identify all of them as potential targets, even if only one is reachable through actual program execution. This imprecision is exacerbated by general type parameters like void or void*, which can lead to a large number of unrelated functions being matched. A common example illustrates this: if a function pointer FP at line 9 has a type compatible with both sub_check and add, type analysis will resolve to both, even if only sub_check is the actual target.

1. Pointer Analysis: In contrast, pointer analysis aims for higher precision by computing the possible values (points-to targets) of each function pointer, meticulously considering memory load and store operations. For example, it could correctly deduce that FP at line 9 points specifically to sub_check. While more precise, pointer analysis is computationally expensive and often inefficient, particularly for large C codebases. It must account for complex control flow, multiple call contexts, and intricate memory interactions, making it difficult to scale to real-world systems with millions of lines of code within practical timeframes.

The goal of the presented work is to improve the traditional type analysis, retaining its scalability while significantly enhancing its precision, thereby bridging the gap between these two existing, yet imperfect, methodologies.

Key Findings

▶ Watch: Limitations of pointer analysis: precise but inefficient (4:00)

The central insight driving this research is the observation that not all function pointers are equally complex in their value propagation. This led to the classification of function pointers and indirect calls, and the introduction of a new concept:

1. Simple vs. Complex Function Pointers and Indirect Calls:

• A simple function pointer is one whose value is neither exposed to memory (its address isn't taken) nor derived through a pointer dereference (load operation). Its value propagation is straightforward and can be efficiently tracked using a lightweight pointer analysis.
• A complex function pointer is one whose value either involves memory indirection (e.g., ptr = &func; FP = ptr;) or whose address is exposed to memory (e.g., void **pp = &FP;). These are the challenging cases for precise analysis.
• Consequently, an indirect call is classified as simple or complex based on the nature of the function pointer used in the call.

1. Confined Functions: The work defines confined functions as address-taken functions that are only ever invoked by simple indirect calls. This means their addresses do not propagate to complex function pointers or are not used in complex indirect call sites.

Based on these distinctions, the key idea of the C approach is to strategically separate and apply different analysis techniques:

• For simple indirect calls, a precise, yet efficient, form of pointer analysis (specifically, a def-use analysis) is employed to resolve their targets with high accuracy. The efficiency stems from the "simple" nature of these pointers, limiting the scope of pointer analysis.
• For complex indirect calls, a type analysis is still used to maintain scalability and avoid the performance penalties of a full-blown pointer analysis.

Furthermore, to address the imprecision of type analysis for complex indirect calls, C introduces a crucial refinement: when performing type matching for complex indirect calls, it excludes confined functions from the set of potential targets. The rationale is that if a function is "confined" to simple indirect calls, it logically cannot be a target of a complex indirect call. This exclusion significantly reduces the over-approximation inherent in traditional type analysis for the remaining complex calls, leading to a substantial improvement in precision.

In summary, C combines the strengths of both pointer and type analysis, using a targeted, hybrid approach. It leverages lightweight pointer analysis for easily resolvable cases and enhances type analysis for complex cases by intelligently pruning the candidate target set, resulting in improved precision across the board compared to traditional type analysis, with minimal performance overhead.

Technical Deep Dive

▶ Watch: Key insight: simple versus complex function pointers (5:00)

The proposed system, C, operates in two distinct but interconnected stages to construct a precise and efficient call graph.

Stage 1: Def-Use Analysis for Simple Indirect Calls

The first stage focuses on precisely resolving targets for simple indirect calls using a form of def-use analysis. This analysis is a specialized, lightweight pointer analysis tailored for function pointers that exhibit simple propagation patterns.

Consider a concrete example from the talk:

For the function pointer B1 involved in the indirect call at line 8, C performs a backward traversal of its def-use chain. It traces how the value of B1 is defined and used. In this instance, tracing B1 backward from line 8 leads directly to the assignment statement at line 1: B1 = &Qs;. This is a direct address-of assignment, indicating that B1 is a simple function pointer. Consequently, C precisely resolves the indirect call B1() at line 8 to target only the function Qs.

If, during this def-use chain traversal, C encounters a memory load operation (e.g., FP = *memory_location;) or if the address of the function pointer itself is taken (e.g., void pp = &FP;), then the function pointer is identified as a complex function pointer**. In such cases, C does not attempt to resolve the call precisely in this stage but defers it to the second stage, acknowledging that a lightweight def-use analysis is insufficient. For example, tracing B2 from line 9 back to line 3 (B2 = ptr;), the presence of a dereference (ptr) immediately flags B2 as a complex function pointer.

Stage 2: Type Analysis with Confined Function Exclusion for Complex Indirect Calls

The second stage addresses the complex indirect calls identified in Stage 1. For these calls, C reverts to a type-based matching strategy, but with a critical enhancement to improve precision while retaining scalability.

Before performing type matching, C first identifies all confined functions. A function is classified as confined if its address is only ever propagated to and invoked by simple indirect calls (which were precisely resolved in Stage 1). In our example, if the address of Qs only ever reaches B1 (a simple function pointer), then Qs would be identified as a confined function.

Now, when C needs to resolve a complex indirect call (e.g., B2() at line 9), it performs type matching between the type of B2 and the types of all remaining address-taken functions. Crucially, this set of "remaining functions" explicitly excludes any functions that have been identified as confined functions.

Returning to the example:

• Suppose Qs was determined to be a confined function because its address only propagated to B1, which was precisely resolved to Qs in Stage 1.
• Suppose B is another address-taken function whose address propagates through *ptr to B2.
• Traditional type analysis for B2() would consider both Qs and B as potential targets if their types match B2. This would lead to imprecision if B is the only actual target.
• However, C, having identified Qs as confined, will exclude Qs from the candidate set for B2().
• If B is the only other address-taken function whose type matches B2, then C will precisely resolve B2() to target only B.

This two-stage approach ensures that C achieves high precision for a significant portion of indirect calls (the simple ones) through efficient pointer analysis, and for the remaining complex calls, it drastically improves the precision of type analysis by intelligently pruning the target set based on the concept of confined functions. This hybrid strategy allows C to compute a more accurate call graph for each indirect call site.

Demo / Proof of Concept

▶ Watch: Proposed approach: combining pointer and type analysis (6:00)

While the talk did not feature a live, interactive demonstration of the C tool, the authors rigorously evaluated its effectiveness through comprehensive experiments on a large set of real-world software projects. This evaluation served as the proof of concept, demonstrating C's practical applicability and superior performance compared to existing state-of-the-art methods.

The evaluation involved 20 large, diverse open-source projects, following methodologies established in prior USENIX program analysis work. These projects were specifically chosen for their scale and complexity, which typically render precise pointer analysis impractical within reasonable timeframes. A notable example analyzed was the Linux kernel, a massive codebase comprising 27 million lines of C code.

The baseline for comparison was "not-layer type analysis," a technique recognized as the best paper at CS 2019, representing a highly optimized and scalable type-based approach. C's performance was measured across three critical metrics:

• Precision: Quantified by the average number of call targets resolved per indirect call site. A lower number indicates higher precision.
• Performance: Measured by the total time consumption for call graph construction.
• Recall: Assessed by checking for any false negatives, ensuring that no valid call targets were missed.

The results were compelling:

• Precision Improvement: C successfully reduced the average number of call targets per indirect call by 55% compared to the existing baseline. This significant reduction highlights the effectiveness of the hybrid approach in pruning imprecise targets.
• Recall: Crucially, C achieved this precision gain with no false negatives, confirming that its optimizations do not compromise the soundness of the call graph.
• Performance Overhead: The precision improvement came with a remarkably low performance cost, incurring only a 7% time overhead compared to the baseline. For instance, analyzing the entire Linux kernel (27 million LoC) with C was completed in just 11 minutes, utilizing a peak memory of 1 GB, demonstrating its exceptional scalability.

Beyond call graph construction itself, the authors also performed downstream application analysis to validate the practical impact of C's improved call graphs. They integrated C's output into several security-critical applications, including:

• Static concurrency analysis: For detecting potential race conditions and other concurrency bugs.
• Static bug finding: For identifying various software vulnerabilities.
• Dynamic fuzzing: For generating test inputs to uncover crashes and other defects.

The results consistently showed that the more precise call graphs generated by C significantly improved the effectiveness of these downstream applications, often with only a few seconds of additional time overhead. This demonstrates that C not only builds better call graphs but also directly contributes to more effective and efficient security and reliability testing tools.

Defensive Implications

▶ Watch: Concrete example demonstrating the two-stage analysis (7:00)

The improved precision and scalability of call graph construction offered by C have profound defensive implications for software security and reliability. Accurate call graphs are a foundational component for a wide array of security analysis tools, and C's advancements enhance their efficacy in several key areas:

1. Enhanced Vulnerability Detection: Static analysis tools that rely on call graphs for control flow understanding will benefit immensely. By reducing the number of false positive call targets, C can help these tools trace execution paths more accurately, leading to more precise identification of vulnerabilities such as buffer overflows, use-after-free errors, and command injection flaws. This can significantly lower the noise in security reports, allowing developers to focus on real issues.

1. More Effective Static Analysis for Concurrency: Concurrency bugs (e.g., race conditions, deadlocks) are notoriously difficult to detect and debug. Static analysis for concurrency often requires precise knowledge of which functions can be called by concurrent threads. C's ability to provide a more accurate call graph, especially for indirect calls, allows concurrency analysis tools to build a more reliable model of inter-thread communication and potential shared resource access, improving their ability to pinpoint subtle concurrency issues.

1. Improved Fuzzing Strategies: Fuzzing, a dynamic testing technique, benefits from understanding program structure. A precise call graph can guide fuzzers to explore deeper and more relevant code paths, particularly those accessible via indirect calls. By knowing the actual potential targets of indirect calls, fuzzers can generate more intelligent inputs that trigger specific functions or code branches, leading to more efficient discovery of vulnerabilities and crashes.

1. Reduced False Positives in Security Tools: A common challenge with many security analysis tools is a high rate of false positives, which can overwhelm developers and reduce trust in the tools. The imprecision of traditional call graph construction is a significant contributor to this. By providing a more precise call graph, C helps downstream tools make more accurate judgments about program behavior, reducing the number of spurious alerts and allowing security teams to operate more efficiently.

1. Reliable Program Understanding and Auditing: For security auditors and reverse engineers, an accurate call graph is invaluable for understanding the functionality and potential attack surface of complex C binaries. C enables a more trustworthy and detailed understanding of how functions are invoked, even through intricate indirect call mechanisms, which is critical for manual code reviews and threat modeling.

In essence, C provides a stronger, more reliable foundation for building and deploying advanced security analysis capabilities, ultimately contributing to the development of more secure and robust software systems.

Key Takeaways

• Indirect Call Resolution is Critical and Challenging: Resolving indirect function calls in C programs is fundamental for program analysis and security, but existing methods face a dilemma between precision (pointer analysis) and scalability (type analysis).
• Hybrid Approach for Optimal Balance: The C system introduces a novel hybrid approach that intelligently combines lightweight pointer analysis for "simple" indirect calls with a refined type analysis for "complex" ones, achieving both high precision and scalability.
• Novel Concepts for Precision: C classifies function pointers as "simple" or "complex" and introduces "confined functions" (address-taken functions only invoked by simple calls) to significantly improve the precision of type analysis for complex indirect calls.
• Significant Precision Gains with Minimal Overhead: C demonstrated a 55% reduction in average call targets per indirect call without any false negatives, while incurring only a 7% time overhead compared to state-of-the-art type analysis.
• Scalability to Real-World Systems: The approach is highly scalable, successfully analyzing the Linux kernel (27 million lines of C code) in just 11 minutes with 1GB of memory, making it practical for large-scale software.
• Improved Downstream Security Applications: More precise call graphs from C significantly enhance the effectiveness of downstream security analyses, including static concurrency analysis, bug finding, and dynamic fuzzing, leading to more robust software.

About the Speaker(s)

The talk was presented by Yuandao Cai, representing The Hong Kong University of Science and Technology. Yuandao Cai delivered the presentation on behalf of the authors of the paper, who were unable to attend the USENIX Security '24 conference in person. His presentation provided a clear and detailed overview of the research and its implications for call graph construction in C programs.