Enhancing Static Analyzers with Graph-Based Vulnerability Discovery

By Sara Tilly

6 min readAugust 14, 2024

In this blog post, we'll recap a fascinating discussion with Amazon security engineer Tom Ganz, who explores how graph-based techniques and Memgraph can transform traditional static analyzers into more accurate, context-sensitive tools for vulnerability discovery.

Watch the entire call with Tom on our Memgraph channel:

Talking Point 1: Introduction and Background

Tom Ganz is a security engineer at Amazon and has conducted his PhD research on graph-based vulnerability discovery. His research focuses on improving static analyzers, tools that identify code vulnerabilities without executing it.

Talking Point 2: Challenges with Current Static Analyzers

Tom opened with an analysis of the shortcomings inherent in existing static analysis tools. These tools, though widely used, often suffer from a high incidence of false positives and fail to detect many vulnerabilities due to their limited contextual awareness.

Static analyzers typically rely on a surface-level understanding of code, which leads to misinterpretations of complex programming constructs. For example, a static analyzer might incorrectly flag a division by zero error in a scenario where program logic ensures the error condition is never met. This disconnect between code analysis and actual runtime behavior is a significant challenge that current tools have not effectively addressed.

Talking Point 3: Theoretical Constraints

The limitations of static analyzers are not merely practical but also theoretical. Tom discussed how Rice’s theorem and the halting problem impose fundamental constraints on the capabilities of static analysis. Specifically, it is impossible to design a static analyzer that is both sound (accurate in all its findings) and complete (able to detect all existing vulnerabilities). This inherent trade-off forces developers to choose between minimizing false positives and maximizing vulnerability detection, a balance that is difficult to achieve with traditional methods.

Talking Point 4: Integrating Machine Learning with Graph-Based Analysis

To address these challenges, Tom advocated for integrating machine learning techniques with graph-based code representations. By modeling code as graphs—such as control flow graphs (CFG) and data flow graphs (DFG)—and applying graph neural networks (GNNs), it is possible to capture the nuanced dependencies and interactions within the code that are often overlooked by conventional static analyzers. GNNs are particularly well-suited for this task because they can iteratively aggregate information from a node's neighbors, thereby constructing a rich, context-aware representation of the code. This approach allows the analyzer to infer patterns indicative of vulnerabilities, leading to more accurate and reliable detection outcomes.

Talking Point 5: Pavudi, A Focused Patch-Based Methodology

A key innovation Tom presents is Pavudi (Patch Vulnerability Discovery), a methodology that refines the scope of static analysis to focus specifically on patches. Traditional static analyzers tend to scan entire codebases, which is time-consuming and computationally expensive, especially for large projects. Pavudi, in contrast, narrows the analysis to recent code changes, assessing whether these modifications introduce new vulnerabilities. This targeted approach reduces the computational overhead and enhances the precision of vulnerability detection.

Talking Point 6: Performance and Efficiency Gains

The performance improvements achieved by Pavudi are noteworthy. In rigorous benchmarks, Pavudi demonstrated a 50% increase in vulnerability detection accuracy compared to existing models. This enhancement is particularly significant in reducing false positives, a common issue that leads to wasted engineering resources. Moreover, Pavudi exhibited greater resilience to concept drift, maintaining its effectiveness over time as codebases evolve. This robustness makes Pavudi a compelling solution for integrating into CI/CD pipelines where the timely and accurate identification of vulnerabilities is critical.

Why Memgraph?

Tom picked Memgraph because it provided the necessary speed and efficiency to process large-scale graph data. Memgraph outperformed other options like Neo4j, offering nearly 100x faster query execution, crucial for the complex graph traversals required in vulnerability detection. Memgraph scalability, flexibility with custom queries, and user-friendly interface made it ideal for rapid experimentation and real-time analysis within CI/CD pipelines. This combination of capabilities enabled Tom to efficiently implement Pavudi, a novel patch-based vulnerability detection method, significantly improving the accuracy and effectiveness of static analysis tools.

Q&A

We’ve compiled the questions and answers from the community call Q&A session. Note that we’ve paraphrased them slightly for brevity. For complete details, watch the entire video.

1. What database options did you consider before choosing Memgraph?

Tom: We initially considered a relational database, but it was too slow for our needs. I also tried implementing the system in Python without a graph database, but it was frustratingly slow. After that, I switched to Java and began looking for a graph database that could meet my requirements. Memgraph stood out because of its performance and the availability of predefined functions like breadth-first search, which I used for graph traversal.

2. How was your overall experience with Memgraph?

Tom: I loved it. The support from the Memgraph team was excellent, something I don't think I would have gotten with Neo4j. The UI was particularly useful because it provided an instant feedback loop, allowing me to try out vulnerability detection without needing a machine learning model in the backend.

3. Are you running this in production? If not, what are the challenges of getting it to production?

Tom: We experimented with some production code, but it was still too slow for full deployment. This research is more foundational, aimed at exploring new ideas like improving the context in learning-based static analysis. Shifting focus to patches rather than entire programs is a new area of exploration that could lead to more effective machine learning-based static analysis, especially considering the limitations of context width in LLMs.

4. What is the latency requirement to make this viable for production?

Tom: I don’t have concrete latency numbers, but I recognize that my self-written versioning implementation could be more performant, perhaps by leveraging Git’s delta algorithm. If this aspect were improved, the system could be closer to being production-ready. The code is open-source, so anyone interested can review it and possibly enhance it.