Indexing Context-Sensitive Reachability

• URL: http://arxiv.org/abs/2109.01321v1
• Date: Fri, 3 Sep 2021 05:41:30 GMT
• Title: Indexing Context-Sensitive Reachability
• Authors: Qingkai Shi, Yongchao Wang, Charles Zhang
• Abstract summary: textscFlare is a reduction from the CFL reachability problem to the conventional graph reachability problem for context-sensitive data flow analysis. We have applied our reduction to a context-sensitive alias analysis and a context-sensitive information-flow analysis for C/C++ programs.
• Score: 16.114012813668932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many context-sensitive data flow analyses can be formulated as a variant of the all-pairs Dyck-CFL reachability problem, which, in general, is of sub-cubic time complexity and quadratic space complexity. Such high complexity significantly limits the scalability of context-sensitive data flow analysis and is not affordable for analyzing large-scale software. This paper presents \textsc{Flare}, a reduction from the CFL reachability problem to the conventional graph reachability problem for context-sensitive data flow analysis. This reduction allows us to benefit from recent advances in reachability indexing schemes, which often consume almost linear space for answering reachability queries in almost constant time. We have applied our reduction to a context-sensitive alias analysis and a context-sensitive information-flow analysis for C/C++ programs. Experimental results on standard benchmarks and open-source software demonstrate that we can achieve orders of magnitude speedup at the cost of only moderate space to store the indexes. The implementation of our approach is publicly available.

Related papers

• QUITO: Accelerating Long-Context Reasoning through Query-Guided Context Compression [37.08536175557748]
  In this paper, we introduce a novel Query-gUIded aTtention cOmpression (QUITO) method to filter useless information. Specifically, we take a trigger token to calculate the attention distribution of the context in response to the question. We evaluate the QUITO using two widely-used datasets, namely, NaturalQuestions and ASQA.
  arXiv  Detail & Related papers  (2024-08-01T04:28:38Z)
• KV Cache Compression, But What Must We Give in Return? A Comprehensive Benchmark of Long Context Capable Approaches [52.02764371205856]
  Long context capability is a crucial competency for large language models (LLMs) This work provides a taxonomy of current methods and evaluating 10+ state-of-the-art approaches across seven categories of long context tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:59:47Z)
• Scalable Sparse Regression for Model Discovery: The Fast Lane to Insight [0.0]
  Sparse regression applied to symbolic libraries has quickly emerged as a powerful tool for learning governing equations directly from data. I present a general purpose, model sparse regression algorithm that extends a recently proposed exhaustive search. It is intended to maintain agnostic sensitivity to small coefficients and be of reasonable computational cost for large symbolic libraries.
  arXiv  Detail & Related papers  (2024-05-14T18:09:43Z)
• LLMC: Benchmarking Large Language Model Quantization with a Versatile Compression Toolkit [55.73370804397226]
  Quantization, a key compression technique, can effectively mitigate these demands by compressing and accelerating large language models. We present LLMC, a plug-and-play compression toolkit, to fairly and systematically explore the impact of quantization. Powered by this versatile toolkit, our benchmark covers three key aspects: calibration data, algorithms (three strategies), and data formats.
  arXiv  Detail & Related papers  (2024-05-09T11:49:05Z)
• When Dataflow Analysis Meets Large Language Models [9.458251511218817]
  This paper introduces LLMDFA, an LLM-powered dataflow analysis framework that analyzes arbitrary code snippets without requiring a compilation infrastructure. Inspired by summary-based dataflow analysis, LLMDFA decomposes the problem into three sub-problems, which are effectively resolved by several essential strategies. Our evaluation has shown that the design can mitigate the hallucination and improve the reasoning ability, obtaining high precision and recall in detecting dataflow-related bugs.
  arXiv  Detail & Related papers  (2024-02-16T15:21:35Z)
• Building Interpretable and Reliable Open Information Retriever for New Domains Overnight [67.03842581848299]
  Information retrieval is a critical component for many down-stream tasks such as open-domain question answering (QA) We propose an information retrieval pipeline that uses entity/event linking model and query decomposition model to focus more accurately on different information units of the query. We show that, while being more interpretable and reliable, our proposed pipeline significantly improves passage coverages and denotation accuracies across five IR and QA benchmarks.
  arXiv  Detail & Related papers  (2023-08-09T07:47:17Z)
• Analysis and Optimization of Wireless Federated Learning with Data Heterogeneity [72.85248553787538]
  This paper focuses on performance analysis and optimization for wireless FL, considering data heterogeneity, combined with wireless resource allocation. We formulate the loss function minimization problem, under constraints on long-term energy consumption and latency, and jointly optimize client scheduling, resource allocation, and the number of local training epochs (CRE) Experiments on real-world datasets demonstrate that the proposed algorithm outperforms other benchmarks in terms of the learning accuracy and energy consumption.
  arXiv  Detail & Related papers  (2023-08-04T04:18:01Z)
• Salesforce CausalAI Library: A Fast and Scalable Framework for Causal Analysis of Time Series and Tabular Data [76.85310770921876]
  We introduce the Salesforce CausalAI Library, an open-source library for causal analysis using observational data. The goal of this library is to provide a fast and flexible solution for a variety of problems in the domain of causality.
  arXiv  Detail & Related papers  (2023-01-25T22:42:48Z)
• Computing unsatisfiable cores for LTLf specifications [3.251765107970636]
  Linear-time temporal logic on finite traces (LTLf) is rapidly becoming a de-facto standard to produce specifications in many application domains. We provide four algorithms for extracting an unsatisfiable core using state-of-the-art approaches to satisfiability checking. The results show the feasibility, effectiveness, and complementarities of the different algorithms and tools.
  arXiv  Detail & Related papers  (2022-03-09T16:08:43Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• A Complementarity Analysis of the COCO Benchmark Problems and Artificially Generated Problems [0.0]
  In this paper, one such single-objective continuous problem generation approach is analyzed and compared with the COCO benchmark problem set. We show that such representations allow us to further explore the relations between the problems by applying visualization and correlation analysis techniques.
  arXiv  Detail & Related papers  (2021-04-27T09:18:43Z)

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.