LLMSA: A Compositional Neuro-Symbolic Approach to Compilation-free and Customizable Static Analysis

• URL: http://arxiv.org/abs/2412.14399v1
• Date: Wed, 18 Dec 2024 23:14:59 GMT
• Title: LLMSA: A Compositional Neuro-Symbolic Approach to Compilation-free and Customizable Static Analysis
• Authors: Chengpeng Wang, Yifei Gao, Wuqi Zhang, Xuwei Liu, Qingkai Shi, Xiangyu Zhang,
• Abstract summary: We propose a compositional neuro-symbolic approach for compilation-free, customizable static analysis with reduced hallucinations. It attains 66.27% precision and 78.57% recall in taint vulnerability detection, surpassing an industrial approach in F1 score by 0.20.
• Score: 13.993290878789779
• License:
• Abstract: Static analysis is essential for program optimization, bug detection, and debugging, but its reliance on compilation and limited customization hampers practical use. Advances in LLMs enable a new paradigm of compilation-free, customizable analysis via prompting. LLMs excel in interpreting program semantics on small code snippets and allow users to define analysis tasks in natural language with few-shot examples. However, misalignment with program semantics can cause hallucinations, especially in sophisticated semantic analysis upon lengthy code snippets. We propose LLMSA, a compositional neuro-symbolic approach for compilation-free, customizable static analysis with reduced hallucinations. Specifically, we propose an analysis policy language to support users decomposing an analysis problem into several sub-problems that target simple syntactic or semantic properties upon smaller code snippets. The problem decomposition enables the LLMs to target more manageable semantic-related sub-problems, while the syntactic ones are resolved by parsing-based analysis without hallucinations. An analysis policy is evaluated with lazy, incremental, and parallel prompting, which mitigates the hallucinations and improves the performance. It is shown that LLMSA achieves comparable and even superior performance to existing techniques in various clients. For instance, it attains 66.27% precision and 78.57% recall in taint vulnerability detection, surpassing an industrial approach in F1 score by 0.20.

Related papers

• Automated Refactoring of Non-Idiomatic Python Code: A Differentiated Replication with LLMs [54.309127753635366]
  We present the results of a replication study in which we investigate GPT-4 effectiveness in recommending and suggesting idiomatic actions. Our findings underscore the potential of LLMs to achieve tasks where, in the past, implementing recommenders based on complex code analyses was required.
  arXiv  Detail & Related papers  (2025-01-28T15:41:54Z)
• Semantic-Enhanced Indirect Call Analysis with Large Language Models [14.517268546437917]
  This paper proposes Semantic-Enhanced Analysis (SEA) to enhance the effectiveness of indirect call analysis. For common programming practices, indirect calls often exhibit semantic similarity with their invoked targets. SEA generates natural language summaries of both indirect calls and target functions from multiple perspectives.
  arXiv  Detail & Related papers  (2024-08-08T10:04:50Z)
• Categorical Syllogisms Revisited: A Review of the Logical Reasoning Abilities of LLMs for Analyzing Categorical Syllogism [62.571419297164645]
  This paper provides a systematic overview of prior works on the logical reasoning ability of large language models for analyzing categorical syllogisms. We first investigate all the possible variations for the categorical syllogisms from a purely logical perspective. We then examine the underlying configurations (i.e., mood and figure) tested by the existing datasets.
  arXiv  Detail & Related papers  (2024-06-26T21:17:20Z)
• The Emergence of Large Language Models in Static Analysis: A First Look through Micro-Benchmarks [3.848607479075651]
  We investigate the role that current Large Language Models (LLMs) can play in improving callgraph analysis and type inference for Python programs. Our study reveals that LLMs show promising results in type inference, demonstrating higher accuracy than traditional methods, yet they exhibit limitations in callgraph analysis.
  arXiv  Detail & Related papers  (2024-02-27T16:53:53Z)
• LLMDFA: Analyzing Dataflow in Code with Large Language Models [8.92611389987991]
  This paper presents LLMDFA, a compilation-free and customizable dataflow analysis framework. We decompose the problem into several subtasks and introduce a series of novel strategies. On average, LLMDFA achieves 87.10% precision and 80.77% recall, surpassing existing techniques with F1 score improvements of up to 0.35.
  arXiv  Detail & Related papers  (2024-02-16T15:21:35Z)
• Zero-shot Causal Graph Extrapolation from Text via LLMs [50.596179963913045]
  We evaluate the ability of large language models (LLMs) to infer causal relations from natural language. LLMs show competitive performance in a benchmark of pairwise relations without needing (explicit) training samples. We extend our approach to extrapolating causal graphs through iterated pairwise queries.
  arXiv  Detail & Related papers  (2023-12-22T13:14:38Z)
• E&V: Prompting Large Language Models to Perform Static Analysis by Pseudo-code Execution and Verification [7.745665775992235]
  Large Language Models (LLMs) offer new capabilities for software engineering tasks. LLMs simulate the execution of pseudo-code, effectively conducting static analysis encoded in the pseudo-code with minimal human effort. E&V includes a verification process for pseudo-code execution without needing an external oracle.
  arXiv  Detail & Related papers  (2023-12-13T19:31:00Z)
• Sentiment Analysis through LLM Negotiations [58.67939611291001]
  A standard paradigm for sentiment analysis is to rely on a singular LLM and makes the decision in a single round. This paper introduces a multi-LLM negotiation framework for sentiment analysis.
  arXiv  Detail & Related papers  (2023-11-03T12:35:29Z)
• The Hitchhiker's Guide to Program Analysis: A Journey with Large Language Models [18.026567399243]
  Large Language Models (LLMs) offer a promising alternative to static analysis. In this paper, we take a deep dive into the open space of LLM-assisted static analysis. We develop LLift, a fully automated framework that interfaces with both a static analysis tool and an LLM.
  arXiv  Detail & Related papers  (2023-08-01T02:57:43Z)
• Sentiment Analysis in the Era of Large Language Models: A Reality Check [69.97942065617664]
  This paper investigates the capabilities of large language models (LLMs) in performing various sentiment analysis tasks. We evaluate performance across 13 tasks on 26 datasets and compare the results against small language models (SLMs) trained on domain-specific datasets.
  arXiv  Detail & Related papers  (2023-05-24T10:45:25Z)
• Reducing Confusion in Active Learning for Part-Of-Speech Tagging [100.08742107682264]
  Active learning (AL) uses a data selection algorithm to select useful training samples to minimize annotation cost. We study the problem of selecting instances which maximally reduce the confusion between particular pairs of output tags. Our proposed AL strategy outperforms other AL strategies by a significant margin.
  arXiv  Detail & Related papers  (2020-11-02T06:24:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.