Indexing Context-Sensitive Reachability
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.
Code (1)
Similar Papers 제목 키워드 기반
A Schema-aware Logic Reformulation for Graph Reachability
Graph reachability is the task of understanding whether two distinct points in a graph are interconnected by arcs to which in general a semantic is attached. Reachability has plenty of applications, ranging from motion p…
ARCMotion PlanningLanguage Models as Context-sensitive Word Search Engines
Context-sensitive word search engines are writing assistants that support word choice, phrasing, and idiomatic language use by indexing large-scale n-gram collections and implementing a wildcard search. However, search r…
Language ModelingLanguage ModellingEfficient Similarity Indexing and Searching in High Dimensions
Efficient indexing and searching of high dimensional data has been an area of active research due to the growing exploitation of high dimensional data and the vulnerability of traditional search methods to the curse of d…
Vocal Bursts Intensity PredictionUsing Petri Nets for Context-Adaptive Robot Explanations
In human-robot interaction, robots must communicate in a natural and transparent manner to foster trust, which requires adapting their communication to the context. In this paper, we propose using Petri nets (PNs) to mod…
Safe Control for Nonlinear Systems with Stochastic Uncertainty via Risk Control Barrier Functions
Guaranteeing safety for robotic and autonomous systems in real-world environments is a challenging task that requires the mitigation of stochastic uncertainties. Control barrier functions have, in recent years, been wide…