Scalable Defect Detection via Traversal on Code Graph

Zhengyao Liu, Xitong Zhong, Xingjing Deng, Shuo Hong, Xiang Gao, Hailong SunarXiv 2024 · DOI · arXiv

Abstract

Modern static analysis tools often rely on Code Property Graphs (CPGs) to detect vulnerabilities, but they frequently struggle with scalability and rule specificity. This paper presents QVoG, a high-performance defect detection platform that utilizes a compressed, statement-level CPG and a hybrid detection engine. By combining declarative domain-specific language (DSL) queries with machine learning models like CodeBERT, QVoG achieves significant improvements in analysis speed and memory efficiency. Experimental results on large-scale open-source projects and standard benchmarks show that QVoG outperforms existing tools like CodeQL and Joern, completing analysis of million-line codebases in minutes while maintaining high precision and recall.

Introduction

Static analysis is a critical component of the secure software development lifecycle. By inspecting source code without execution, tools can identify potential security vulnerabilities early. The Code Property Graph (CPG) has emerged as a powerful representation, merging Abstract Syntax Trees (AST), Control Flow Graphs (CFG), and Data Flow Graphs (DFG). However, traditional CPG-based tools face three primary challenges: scalability issues due to AST-level granularity, the complexity of writing custom detection rules in specialized languages, and the "brittleness" of rule-based systems that fail to catch subtle variations of known bugs.

System Architecture

QVoG addresses these challenges through a multi-layered architecture designed for efficiency and flexibility.

The comprehensive architecture of QVoG, spanning pattern extraction to data storage.

The system consists of four main stages:

  1. Pattern Extraction: Leverages existing vulnerability databases (CVE/CWE) and machine learning to identify common defect patterns.
  2. DSL Parsing: Provides a user-friendly, SQL-like interface for defining custom queries, which are then parsed into a language-independent representation.
  3. Query Engine: A hybrid engine that combines traditional graph traversals with ML-assisted detection (using CodeBERT) to identify potential sources and sinks.
  4. Data Storage: Utilizes a multi-database approach, including graph databases (Neo4j/Gremlin) for structure, relational databases for metadata, and a cache for intermediate results.

Methodology

The core innovation of QVoG lies in its "compressed" CPG. Unlike standard tools that create nodes for every AST element, QVoG operates at the statement level. Detailed syntax information is embedded as attributes within these statement nodes, drastically reducing the graph's size and complexity.

High-level workflow showing the transition from source code to vulnerability reports.

To enhance detection capabilities, QVoG integrates a hybrid ML approach. It uses two CodeBERT-based models: Model_type to classify code segments as potential "Sources" (untrusted inputs) or "Sinks" (dangerous operations), and Model_pair to validate the reachability and vulnerability of paths between them. This allows the system to generalize beyond rigid, manually-defined rules.

Evaluation

QVoG was evaluated against industry-standard benchmarks and real-world projects:

  • Performance: On the PostgreSQL codebase (over 1.5 million lines of code), QVoG completed its analysis in 15 minutes, outperforming CodeQL (19 minutes) and maintaining a lower memory footprint than Joern.
  • Accuracy: On the Juliet Test Suite, the system achieved 90% precision and 95% recall, particularly excelling in memory-related vulnerabilities (CWE-401, 415, 416).
  • ML Efficacy: The ML components reached 92% accuracy in source/sink identification and successfully detected a real-world vulnerability in the Pillow library (CVE-2023-50447) that was missed by CodeQL.

Conclusion and Future Work

QVoG demonstrates that statement-level granularity in code graphs significantly improves the scalability of static analysis without sacrificing semantic depth. By bridging the gap between declarative rules and machine learning, it provides a robust and efficient solution for modern vulnerability detection. Future work will focus on improving intra-file parallelism for amalgamated source files and expanding language support beyond C, Java, and Python.

Summary updated

Abstract

Detecting defects and vulnerabilities in the early stage has long been a challenge in software engineering. Static analysis, a technique that inspects code without execution, has emerged as a key strategy to address this challenge. Among recent advancements, the use of graph-based representations, particularly Code Property Graph (CPG), has gained traction due to its comprehensive depiction of code structure and semantics. Despite the progress, existing graph-based analysis tools still face performance and scalability issues. The main bottleneck lies in the size and complexity of CPG, which makes analyzing large codebases inefficient and memory-consuming. Also, query rules used by the current tools can be over-specific. Hence, we introduce QVoG, a graph-based static analysis platform for detecting defects and vulnerabilities. It employs a compressed CPG representation to maintain a reasonable graph size, thereby enhancing the overall query efficiency. Based on the CPG, it also offers a declarative query language to simplify the queries. Furthermore, it takes a step forward to integrate machine learning to enhance the generality of vulnerability detection. For projects consisting of 1,000,000+ lines of code, QVoG can complete analysis in approximately 15 minutes, as opposed to 19 minutes with CodeQL.
BibTeX
@misc{liu2024scalable,
  author = {Zhengyao Liu and Xitong Zhong and Xingjing Deng and Shuo Hong and Xiang Gao and Hailong Sun},
  title = {{Scalable Defect Detection via Traversal on Code Graph}},
  year = {2024},
  eprint = {2406.08098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.08098},
}
Figure