Qiushi Wu (University of Minnesota), Zhongshu Gu (IBM Research), Hani Jamjoom (IBM Research), Kangjie Lu (University of Minnesota)

Generating accurate call graphs for large programs, particularly at the operating system (OS) level, poses a well-known challenge. This difficulty stems from the widespread use of indirect calls within large programs, wherein the computation of call targets is deferred until runtime to achieve program polymorphism. Consequently, compilers are unable to statically determine indirect call edges. Recent advancements have attempted to use type analysis to globally match indirect call targets in programs. However, these approaches still suffer from low precision when handling large target programs or generic types.

This paper presents GNNIC, a Graph Neural Network (GNN) based Indirect Call analyzer. GNNIC employs a technique called abstract-similarity search to accurately identify indirect call targets in large programs. The approach is based on the observation that although indirect call targets exhibit intricate polymorphic behaviors, they share common abstract characteristics, such as function descriptions, data types, and invoked function calls. We consolidate such information into a representative abstraction graph (RAG) and employ GNNs to learn function embeddings. Abstract-similarity search relies on at least one anchor target to bootstrap. Therefore, we also propose a new program analysis technique to locally identify valid targets of each indirect call.
Starting from anchor targets, GNNIC can expand the search scope to find more targets of indirect calls in the whole program.
The implementation of GNNIC utilizes LLVM and GNN, and we evaluated it on multiple OS kernels. The results demonstrate that GNNIC outperforms state-of-the-art type-based techniques by reducing 86% to 93% of false target functions. Moreover, the abstract similarity and precise call graphs generated by GNNIC can enhance security applications by discovering new bugs, alleviating path-explosion issues, and improving the efficiency of static program analysis. The combination of static analysis and GNNIC resulted in finding 97 new bugs in Linux and FreeBSD kernels.

View More Papers

Towards Real-time Voice Interaction Data Collection Monitoring and Ambient...

Tu Le (University of California, Irvine), Zixin Wang (Zhejiang University), Danny Yuxing Huang (New York University), Yaxing Yao (Virginia Tech), Yuan Tian (University of California, Los Angeles)

Read More

WIP: A Trust Assessment Method for In-Vehicular Networks using...

Artur Hermann, Natasa Trkulja (Ulm University - Institute of Distributed Systems), Anderson Ramon Ferraz de Lucena, Alexander Kiening (DENSO AUTOMOTIVE Deutschland GmbH), Ana Petrovska (Huawei Technologies), Frank Kargl (Ulm University - Institute of Distributed Systems)

Read More

Cyclops: Binding a Vehicle’s Digital Identity to its Physical...

Lewis William Koplon, Ameer Ghasem Nessaee, Alex Choi (University of Arizona, Tucson), Andres Mentoza (New Mexico State University, Las Cruces), Michael Villasana, Loukas Lazos, Ming Li (University of Arizona, Tucson)

Read More

ReqsMiner: Automated Discovery of CDN Forwarding Request Inconsistencies and...

Linkai Zheng (Tsinghua University), Xiang Li (Tsinghua University), Chuhan Wang (Tsinghua University), Run Guo (Tsinghua University), Haixin Duan (Tsinghua University; Quancheng Laboratory), Jianjun Chen (Tsinghua University; Zhongguancun Laboratory), Chao Zhang (Tsinghua University; Zhongguancun Laboratory), Kaiwen Shen (Tsinghua University)

Read More