GNNIC: Finding Long-Lost Sibling Functions with Abstract Similarity

GNNIC: Finding Long-Lost Sibling Functions with Abstract Similarity

Speakers: Qiushi Wu

Conference: NDSS Symposium

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

Overview

The talk "GNNIC: Finding Long-Lost Sibling Functions with Abstract Similarity," presented by Qiushi Wu at the NDSS Symposium, addresses a pervasive and critical challenge in program analysis: the accurate construction of call graphs for large-scale software systems, particularly operating system kernels. Modern software extensively uses indirect calls, where the target function is determined at runtime via function pointers. This flexibility, while powerful, renders traditional static analysis techniques largely ineffective in precisely identifying all potential targets, leading to highly imprecise call graphs. This imprecision cascades into significant limitations for various downstream security applications, including bug detection, program debloating, directed fuzzing, and vulnerability assessment, often resulting in an overwhelming number of false positives or missed vulnerabilities.

GNNIC (Graph Neural Network-based Indirect Call analyzer) proposes a novel solution by leveraging the concept of abstract similarity. The core insight is that despite polymorphic implementations, target functions of an indirect call often share common high-level characteristics, such as their functional descriptions, data types, and the set of functions they invoke. GNNIC consolidates this diverse information into a Representative Abstraction Graph (RAG) and employs Graph Neural Networks (GNNs) to learn rich, context-aware function embeddings. By combining a precise, albeit incomplete, method for identifying initial "anchor" targets with the power of GNNs to expand this search based on learned abstract similarities, GNNIC significantly refines call graph precision.

The impact of GNNIC is substantial. Evaluated extensively on major OS kernels like Linux, Android, and FreeBSD, the system dramatically outperforms state-of-the-art type-based techniques, reducing false target functions by an impressive 86% to 93%. This enhanced precision is not merely theoretical; it directly translates into tangible security benefits, including the discovery of 97 new NULL-pointer dereference bugs in Linux and FreeBSD kernels, a significant reduction in false positives for static analysis tools, and a dramatic improvement in the efficiency of vulnerability reachability analysis. GNNIC represents a leap forward in scalable and accurate program analysis for complex software, paving the way for more robust security assessments.

Background

▶ Watch: Introduction, problem of indirect calls, GNNIC overview (0:00)

The pervasive use of indirect calls in large software systems like operating system kernels presents a fundamental hurdle for program analysis. An indirect call, such as hw-mac.ops.check_for_link(hw) in the Linux kernel (Figure 1 in the original presentation), invokes a function whose address is stored in a function pointer, check_for_link, at runtime. Statically determining the precise targets of these calls is notoriously difficult due to the dynamic nature of pointer assignments and propagation. Imprecise call graphs, which list numerous potential but incorrect targets, severely hamper the effectiveness of security tools and analyses.

Current state-of-the-art approaches to resolving indirect calls predominantly fall into three categories, each with significant limitations:

1. Type-based Analysis: These methods, while widespread due to their simplicity, suffer from two primary issues. First, false positives arise from generic types. Function pointer types that are overly broad, such as int (console_blank_hook)(int) in Linux kernel V5.7, can match hundreds or even thousands of functions. An empirical study cited in the talk found this specific example matched over 1,200 functions, with only one being the true target. Existing multi-layer type analysis (MLTA) attempts to add constraints but still struggles. Second, false positives result from global search. Type analysis typically performs a global search across the entire program without tracking data flow, leading to matches between an indirect call and functions in entirely unrelated modules. For instance, functions in independent Linux kernel subsystems should not be targets for calls in other modules, but type matching often fails to respect these logical boundaries. Furthermore, MLTA itself has out-of-scope cases, failing to handle function pointers not involving composite types or those frequently cast to generic types like void . Consequently, MLTA still generates an average of 84.7 potential targets per indirect call in the Linux kernel, a number far too large for practical analysis.

1. Point-to Analysis: While more general and capable of tracking data flow, point-to analysis faces severe scalability and precision issues when applied to large programs like OS kernels. Its computational complexity makes it impractical for comprehensive, whole-program analysis at this scale.

1. Dynamic Analysis: Techniques like Control-Flow Integrity (CFI) or fuzzing offer precise target identification for executed code paths. However, their critical limitation is low code coverage. Recent kernel fuzzers such as HFL and DR.FUZZ often achieve less than 10% coverage, sometimes even less than 1% for drivers, making them unsuitable for exhaustively identifying all indirect call targets across a vast codebase.

These limitations motivated an empirical study into abstract behaviors. The researchers observed that even when target functions for an indirect call differ in their detailed implementations due to polymorphism, they invariably share common, high-level functionalities—their "abstract behaviors." For example, two target functions for hw-mac.ops.check_for_link(hw), e1000_check_for_copper_link_ich8lan() and e1000e_check_for_copper_link, both share the abstract behaviors of checking link existence, downshift, and configuring link status.

A manual analysis of 501 target functions from 100 random indirect calls confirmed this insight: all indirect calls had targets sharing at least one relevant abstract behavior. The study identified key abstractive information: function names and textual descriptions, nested function calls and their relations, and data types used by functions. Notably, 97% of indirect calls' targets shared similar names and descriptions. Jaccard similarities for nested function calls (0.62) and data types (0.41) were significantly higher than for random functions, contrasting sharply with much lower similarities for control and data flow (38% and 16%). This highlights that high-level abstractive information is more stable and representative of function behavior than low-level flow details. The challenge then shifted to automatically summarizing and processing this diverse, nested abstractive information, which naturally led to the adoption of Graph Neural Networks (GNNs), given their ability to aggregate information from neighboring nodes in a graph structure.

Key Findings

▶ Watch: Why state-of-the-art type analysis struggles with indirect calls (2:00)

GNNIC delivers a paradigm shift in resolving indirect call targets, yielding several compelling key findings and contributions:

• Dramatic Reduction in False Targets: GNNIC significantly outperforms state-of-the-art type-based techniques (like MLTA) by reducing the number of false target functions by 86% for FreeBSD, 88% for Linux, and 93% for Android kernels when using an abstract similarity threshold greater than 0.9. The mean number of targets per indirect call in Linux dropped from 84.7 to 9.7, in Android from 76.1 to 4.7, and in FreeBSD from 33.2 to 4.5.
• High Precision with Acceptable Recall: At its highest precision (92.3%), GNNIC achieves a recall of 84.8% for the Linux kernel, representing an 82.3% improvement in precision over MLTA (which had 10% precision) while missing only 16.2% of real targets. This demonstrates a superior balance for practical security analysis.
• Discovery of New Bugs: The precise call graphs generated by GNNIC enabled the discovery of 97 new NULL-pointer dereference bugs in Linux and FreeBSD kernels across 38 different allocation functions. A significant 63% of these functions were rarely used (less than 10 times), making them difficult for traditional cross-checking methods to identify, with 33 bugs entirely missed by such approaches.
• Significant Reduction in Static Analysis False Positives: GNNIC substantially reduces false positives in static analysis tools. For instance, it led to a 74% reduction in Crix warnings, resulting in a 44% overall reduction in total false positives, underscoring how imprecise indirect call analysis is a major contributor to noise in static analysis.
• Enhanced Vulnerability Reachability Analysis: For vulnerability assessment involving call chains with indirect calls, GNNIC dramatically prunes the search space. For a chain with an average of 4.7 indirect calls in the Linux kernel, the number of candidate call chains is reduced from approximately 10^9 (with type-based methods) to roughly 10^4, making reachability analysis far more feasible and precise.
• Scalability for Large Kernels: GNNIC demonstrates excellent scalability, completing analysis for Linux and Android kernels (over 20 million lines of code) in less than 4 hours, and for FreeBSD in less than one hour. This includes abstractive information collection, RAG building, GNN training, and anchor function identification.

Technical Deep Dive

▶ Watch: Core insight: target functions share common abstract behaviors (4:00)

GNNIC's workflow is meticulously designed to leverage abstract similarity, integrating program analysis with Graph Neural Networks. The process unfolds in four main parts:

1. Collecting Abstractive Information: This initial phase involves parsing source code and LLVM Intermediate Representation (IR) to extract fundamental information about functions and types. This includes function names, textual descriptions (often from comments or documentation), the set of functions called by each function (call relations), the data types used by functions, and the relationships between data types themselves (type inclusion relations, e.g., which structs contain other structs).

1. Building Representative Abstraction Graph (RAG): The collected diverse abstractive information is then structured into a unified graph format, the Representative Abstraction Graph (RAG), which serves as the input for the GNN model. Textual information (function and type names, descriptions) is first processed using standard NLP techniques like stop word removal and stemming. These textual tokens are then embedded into 300-dimensional vectors using a Word2Vec model. To ensure broad applicability, this Word2Vec model is pre-trained on a substantial 1.5GB corpus comprising code comments, documentation, and Git logs from major open-source projects like Linux, FreeBSD, and OpenSSL. These vectors form the initial feature representations for the nodes in the RAG. The RAG itself integrates three distinct graph structures:

• Function Call Graph: A directed graph where nodes are functions and edges represent direct caller-callee relationships (excluding indirect calls at this stage).
• Type Usage Graph: Nodes represent functions and types. Directed edges connect functions to the specific data types they utilize.
• Type-Relation Graph: Nodes are data types. Weighted directed edges indicate inclusion relationships, such as a composite type containing other types. For instance, struct e1000_mac_info might have edges to struct e1000_mac_operations (weight 1), u8 (weight 3), and bool (weight 12), reflecting the count of these element types within the container.

These individual graphs are merged into a single, comprehensive RAG, where nodes represent both functions and types, and edges capture their various interdependencies.

1. Collecting Anchor Functions: A crucial bootstrapping step for GNNIC is the identification of at least one highly precise, validated target function for each indirect call, termed an anchor function. Since dynamic analysis has low coverage and traditional static methods lack precision, GNNIC employs a novel program analysis technique: Scoped Unique-Name Matching combined with Definitive Data Flow Tracking.

• Scoped Unique-Name Matching: This technique prioritizes precision. The core insight is that if a function pointer's name is unique within its relevant "dependency scope," any function assigned to it is highly likely to be a valid target. To generalize this, unique names for function pointers within structs are defined as composite names, including the struct object's name and type, along with the function pointer's name and type (e.g., e1000_mac_operations.ops.s32*(struct e1000_hw ).check_for_link). The dependency scope is delimited by iteratively considering data-dependent modules (modules that call functions in or use global variables from another). Crucially, this process does not* consider data flow passed by indirect calls to avoid circular dependencies.
• Definitive Data Flow Tracking: This is used for specific scenarios where a function address is directly stored as an argument (callback functions) or directly assigned to a function pointer in global initializers (e.g., GV.func_pointer = foo). This technique, while limited, can identify anchors for approximately 2% of indirect calls.
• For the 6.3% of indirect calls where no anchors are initially found, GNNIC "borrows" anchors from the most similar indirect call, with similarity determined by comparing the name and type of the function pointer, based on the observation that similar indirect calls often have similar function pointers and abstract behaviors.

1. Identifying More Target Functions: With the RAG constructed and initial anchor functions identified, GNNIC trains an unsupervised GraphSage model (from the StellarGraph library) on the RAG. GraphSage is adept at aggregating feature information from a node's neighbors across multiple layers, thereby learning rich, context-aware embeddings for every function and type node. The model uses a directed GraphSage encoder with two layers, employing sample sizes of 10 and 5 for the first and second hops, respectively, and is trained for five epochs with a batch size of 10K.

Once these unique, 300-dimensional embeddings (representing the abstract behavior) are generated for all functions, GNNIC identifies additional targets. For each indirect call, the abstract similarity between its anchor function(s) and all candidate functions is computed using cosine similarity. A higher cosine similarity score (ranging from -1 to 1) indicates greater abstract similarity. This allows GNNIC to effectively filter out irrelevant targets from the candidate set provided by traditional techniques, with a tunable similarity threshold enabling users to optimize the balance between false positives and negatives. If a nested callee within the RAG is an indirect call whose targets are missing, GNNIC borrows its identified anchor functions to complete the RAG, enhancing model stability.

Demo / Proof of Concept

▶ Watch: Rationale for using GNNs to capture nested relationships (4:50)

While the talk did not feature a live, interactive demonstration, the efficacy and practical value of GNNIC were rigorously proven through extensive evaluations on real-world operating system kernels. These evaluations served as a comprehensive proof of concept, showcasing GNNIC's precision, scalability, and direct impact on security analysis.

The evaluation setup utilized a server with 8 cores/60GB RAM/GPU and a desktop with 24 cores/64GB RAM/GPU, both running Ubuntu 20.04. To establish a robust ground-truth for false-negative evaluation, the researchers analyzed 11,286 fuzzing logs from Syzbot 17, identifying 3,831 unique indirect caller-callee pairs. Since MLTA is theoretically sound (no false negatives), any targets missed by GNNIC in this dataset were considered false negatives. For false-positive evaluation, 100-300 sampled indirect caller-callee pairs from GNNIC, type analysis, and MLTA were manually analyzed to ensure a statistical margin of error of 5-10%. A target was deemed true if a valid path existed to the call site and its functionality was consistent, and false otherwise.

Scalability results were particularly impressive:

• For Linux and Android kernels (exceeding 20 million lines of code), collecting abstractive information took approximately 10 minutes.
• Word2Vec pre-training, a one-time reusable step, required about three hours.
• Building the RAG and training the GNN were efficient due to GraphSage's inductive learning capabilities.
• Generating anchor functions and final results took around 10 minutes.
• The total analysis time for Linux/Android kernels was less than 4 hours, and for FreeBSD, less than one hour, demonstrating GNNIC's practicality for large codebases.

Precision of anchor function identification was high, with 94% of 100 sampled indirect caller-target pairs identified as valid. The 6% false positives were attributed to complex source code and macro issues during name matching. For the 6.3% of indirect calls where GNNIC initially failed to find anchors in the Linux kernel, 56% were due to complex source code constructs, and 44% involved function pointers acquiring addresses indirectly from other function pointers.

The precision improvements on target identification were significant when compared against two-layer type analysis (MLTA). GNNIC achieved a reduction rate of 88% for Linux, 86% for FreeBSD, and 93% for Android in false target functions when the abstract similarity threshold was greater than 0.9. The ROC curve for GNNIC on the Linux kernel (Figure 7 in the presentation) showcased a good balance: at a false-positive rate of 0.33%, GNNIC achieved a true-positive rate (recall) of 84.8%. Pushing for a higher recall of 99.6% resulted in a false-positive rate of 60.7%. Crucially, GNNIC achieved a peak precision of 92.3% with a corresponding recall of 84.8%, an 82.3% improvement in precision over MLTA (which had a mere 10% precision for 100% theoretical recall), while only missing 16.2% of real targets. The mean number of targets per indirect call drastically dropped: from 84.7 to 9.7 in Linux, 76.1 to 4.7 in Android, and 33.2 to 4.5 in FreeBSD, validating GNNIC's effectiveness in refining indirect call targets and eliminating noise.

Defensive Implications

▶ Watch: High-level overview of GNNIC's four-part workflow (5:05)

The precise call graphs generated by GNNIC have profound and wide-ranging defensive implications for software security:

• Enhanced Bug Detection: GNNIC's improved accuracy directly translates into more effective static analysis for bug detection. By integrating GNNIC with existing static analysis tools, the researchers discovered 97 new NULL-pointer dereference bugs in Linux and FreeBSD kernels. A significant aspect of this finding is that 63% of these bugs were in functions used less than 10 times, making them difficult to detect by traditional cross-checking methods. GNNIC's abstract similarity-based clustering helped identify these overlooked vulnerabilities, with 33 of the 97 bugs entirely missed by cross-checking-only approaches. This demonstrates GNNIC's ability to uncover deep-seated, hard-to-find defects.

• Reduced False Positives in Static Analysis: A major impediment to the adoption of static analysis tools is the high volume of false positives. GNNIC addresses this directly by providing more accurate indirect call targets, which are a primary source of imprecision. For instance, GNNIC reduced Crix warnings by 74%, leading to a 44% reduction in total false positives. This makes static analysis reports far more actionable and reduces the burden on security analysts.

• Improved Vulnerability Reachability Analysis: In the context of vulnerability assessment, precisely identifying call chains that can reach a vulnerable function is critical. Syzbot logs indicate an average of 4.7 indirect calls per chain in the Linux kernel. With traditional type-based approaches, analyzing such a chain could involve exploring approximately 10^9 candidate call chains (84.7 to the power of 4.7). GNNIC, by reducing the mean targets per indirect call to 9.7 in Linux, slashes this to roughly 10^4 candidate chains (9.7 to the power of 4.7). This dramatic reduction in complexity makes accurate vulnerability reachability analysis feasible and significantly more efficient.

• Expanded Bug Identification Capabilities: The core concept of abstract similarity is highly extensible. Beyond NULL-pointer dereferences, it can be applied to detect other common bug types, such as permission issues in critical APIs or incorrect usage patterns. This opens avenues for broader and more effective automated bug hunting.

• Improving Directed Fuzzing and Concolic Execution: Advanced testing techniques like directed fuzzing and concolic execution often require accurate knowledge of indirect call targets to explore specific code paths or generate meaningful inputs. GNNIC's precise call graphs can significantly enhance the effectiveness of existing fuzzing and concolic execution instruments. Furthermore, the ability to adjust the abstract similarity thresholds allows users to fine-tune the balance between false positives and negatives, optimizing these security testing processes for specific objectives.

In essence, GNNIC empowers defenders with a more reliable and efficient foundation for understanding program behavior, identifying vulnerabilities, and verifying software integrity in complex, large-scale systems.

Key Takeaways

• Indirect calls are a major challenge for precise program analysis, particularly in large software like OS kernels, leading to imprecise call graphs and hindering security applications.
• GNNIC leverages the concept of abstract similarity, recognizing that polymorphic indirect call targets share high-level behaviors (names, descriptions, nested calls, data types), which are more stable than low-level control/data flow.
• The system employs scoped unique-name matching and definitive data flow tracking to precisely identify initial "anchor functions," a crucial bootstrapping step for GNNIC's operation.
• GNNIC integrates diverse abstractive information into a Representative Abstraction Graph (RAG), using Word2Vec for textual embeddings and GraphSage to learn rich, context-aware function embeddings.
• GNNIC dramatically improves precision, reducing false indirect call targets by 86% to 93% compared to state-of-the-art type-based methods, and achieving an 82.3% precision improvement over MLTA with acceptable recall.
• The enhanced precision has tangible security benefits, including the discovery of 97 new kernel NULL-pointer dereference bugs, a 44% reduction in static analysis false positives, and orders of magnitude improvement in vulnerability reachability analysis efficiency.

About the Speaker(s)

Qiushi Wu is a researcher who presented GNNIC at the NDSS Symposium. His work focuses on addressing critical challenges in program analysis for large-scale software, particularly operating system kernels, with an emphasis on improving security applications. The depth of the technical solutions presented indicates expertise in both program analysis techniques and the application of machine learning, specifically Graph Neural Networks, to complex software engineering problems.