Boosting Path-Sensitive Value Flow Analysis via Removal of Redundant Summaries

• URL: http://arxiv.org/abs/2502.04952v3
• Date: Wed, 12 Feb 2025 08:05:44 GMT
• Title: Boosting Path-Sensitive Value Flow Analysis via Removal of Redundant Summaries
• Authors: Yongchao Wang, Yuandao Cai, Charles Zhang,
• Abstract summary: We present the first approach that can effectively identify and eliminate redundant summaries.<n>Our identification algorithm can significantly reduce the time and memory overhead of the state-of-the-art value flow analysis.<n>In the largest textitd project, the identification algorithm reduces the time by 8107 seconds (2.25 hours) with a mere 17.31 seconds of additional overhead, leading to a ratio of time savings to paid overhead (i.e., performance gain) of 468.48 $times$.
• Score: 12.187048691454239
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Value flow analysis that tracks the flow of values via data dependence is a widely used technique for detecting a broad spectrum of software bugs. However, the scalability issue often deteriorates when high precision (i.e., path-sensitivity) is required, as the instantiation of function summaries becomes excessively time- and memory-intensive. The primary culprit, as we observe, is the existence of redundant computations resulting from blindly computing summaries for a function, irrespective of whether they are related to bugs being checked. To address this problem, we present the first approach that can effectively identify and eliminate redundant summaries, thereby reducing the size of collected summaries from callee functions without compromising soundness or efficiency. Our evaluation on large programs demonstrates that our identification algorithm can significantly reduce the time and memory overhead of the state-of-the-art value flow analysis by 45\% and 27\%, respectively. Furthermore, the identification algorithm demonstrates remarkable efficiency by identifying nearly 80\% of redundant summaries while incurring a minimal additional overhead. In the largest \textit{mysqld} project, the identification algorithm reduces the time by 8107 seconds (2.25 hours) with a mere 17.31 seconds of additional overhead, leading to a ratio of time savings to paid overhead (i.e., performance gain) of 468.48 $\times$. In total, our method attains an average performance gain of 632.1 $\times$.

Related papers

• Delta Attention: Fast and Accurate Sparse Attention Inference by Delta Correction [52.14200610448542]
  A transformer has a quadratic complexity, leading to high inference costs and latency for long sequences.<n>We propose a simple, novel, and effective procedure for correcting this distributional shift.<n>Our method can maintain approximately 98.5% sparsity over full quadratic attention, making our model 32 times faster than Flash Attention 2 when processing 1M token prefills.
  arXiv  Detail & Related papers  (2025-05-16T13:48:33Z)
• An Efficient Outlier Detection Algorithm for Data Streaming [51.56874851156008]
  Traditional outlier detection methods, such as the Local Outlier Factor (LOF) algorithm, struggle with real-time data.<n>We propose a novel approach to enhance the efficiency of LOF algorithms for online anomaly detection, named the Efficient Incremental LOF (EILOF) algorithm.<n>The EILOF algorithm not only significantly reduces computational costs, but also systematically improves detection accuracy when the number of additional points increases.
  arXiv  Detail & Related papers  (2025-01-02T05:12:43Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Cascade Reward Sampling for Efficient Decoding-Time Alignment [17.278488115500615]
  We introduce Cascade Reward Sampling (CARDS) to resolve both efficiency in decoding-time alignment. CARDS minimizes redundant computations of both large language models (LLMs) and reward models (RMs)
  arXiv  Detail & Related papers  (2024-06-24T04:08:35Z)
• Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation [62.969796245827006]
  Delayed-PSVI is an optimistic value-based algorithm that explores the value function space via noise perturbation with posterior sampling. We show our algorithm achieves $widetildeO(sqrtd3H3 T + d2H2 E[tau]$ worst-case regret in the presence of unknown delays. We incorporate a gradient-based approximate sampling scheme via Langevin dynamics for Delayed-LPSVI.
  arXiv  Detail & Related papers  (2023-10-29T06:12:43Z)
• Optimizing Retrieval-augmented Reader Models via Token Elimination [30.53636918279251]
  We analyze the contribution and necessity of all the retrieved passages to the performance of reader models. We demonstrate that our method can reduce run-time by up to 62.2%, with only a 2% reduction in performance, and in some cases, even improve the performance results.
  arXiv  Detail & Related papers  (2023-10-20T17:41:36Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• DeLag: Using Multi-Objective Optimization to Enhance the Detection of Latency Degradation Patterns in Service-based Systems [0.76146285961466]
  We present DeLag, a novel automated search-based approach for diagnosing performance issues in service-based systems. DeLag simultaneously searches for multiple latency patterns while optimizing precision, recall and dissimilarity.
  arXiv  Detail & Related papers  (2021-10-21T13:59:32Z)
• Learning to Schedule [3.5408022972081685]
  This paper proposes a learning and scheduling algorithm to minimize the expected cumulative holding cost incurred by jobs. In each time slot, the server can process a job while receiving the realized random holding costs of the jobs remaining in the system.
  arXiv  Detail & Related papers  (2021-05-28T08:04:06Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
  We develop a hard thresholding algorithm for AUC in distributiond classification. We conduct experiments to show the efficiency and effectiveness of the proposed algorithms.
  arXiv  Detail & Related papers  (2020-11-04T16:49:29Z)
• Real-time Semantic Segmentation with Fast Attention [94.88466483540692]
  We propose a novel architecture for semantic segmentation of high-resolution images and videos in real-time. The proposed architecture relies on our fast spatial attention, which is a simple yet efficient modification of the popular self-attention mechanism. We show that results on multiple datasets demonstrate superior performance with better accuracy and speed compared to existing approaches.
  arXiv  Detail & Related papers  (2020-07-07T22:37:16Z)

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.