SICode: Embedding-Based Subgraph Isomorphism Identification for Bug Detection
Open Access
- 15 April 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 304-315
Abstract
Given a known buggy code snippet, searching for similar patterns in a target project to detect unknown bugs is a reasonable approach. In practice, a search unit, such as a function, may appear quite different from the buggy snippet but actually contains a similar buggy substructure. Utilizing subgraph isomorphism identification can effectively hunt potential bugs by checking whether an approximate copy of the buggy subgraph exists within the target code graphs. Regrettably, subgraph isomorphism identification is an NP-complete problem. In this paper, we propose an embedding-based method, SICode, to efficiently perform subgraph isomorphism identification for code graphs. We train a graph embedding model and the subgraph isomorphism relationship between two graphs can be measured by comparing their embedding vectors. In this manner, we can efficiently identify potential buggy code graphs via vector arithmetic without solving an NP-complete problem. A cascading loss scheme is presented to ensure the identification performance. SICode exhibits greater scalability than classic subgraph isomorphism algorithms, such as VF2, and maintains high precision and recall. Experiments also demonstrate that SICode offers advantages in detecting sub-structurally similar bugs. Our approach spotted 20 previously-unknown bugs in real-world projects, among which, 18 bugs were confirmed by their developers and ranked within the top ten results of retrieval. This result is very encouraging for detecting subtle sub-structurally similar bugs.Keywords
This publication has 28 references indexed in Scilit:
- InferCode: Self-Supervised Learning of Code Representations by Predicting Subtrees2021
- Hunting Vulnerable Smart Contracts via Graph Embedding Based Bytecode MatchingIEEE Transactions on Information Forensics and Security, 2021
- VUDDY: A Scalable Approach for Vulnerable Code Clone Discovery2017
- AntMiner2016
- VCCFinder2015
- Tracelet-based code search in executablesACM SIGPLAN Notices, 2014
- Modeling and Discovering Vulnerabilities with Code Property Graphs2014
- Generalized vulnerability extrapolation using abstract syntax trees2012
- Curriculum learning2009
- /*icomment2007