Andreas Pavlogiannis
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Andreas Pavlogiannis has a total of 90 co-authors. Here are the top co-authors by number of shared publications:
Krishnendu Chatterjee
IST Austria Klosterneuburg Austria
17 shared publications- Krishnendu Chatterjee
IST Austria, Klosterneuburg, Austria
16 shared publications - Rasmus Ibsen-Jensen
University of Liverpool Liverpool UK
10 shared publications - Umang Mathur
National University of Singapore, Singapore, Singapore
8 shared publications Amir Kafshdar Goharshady
IST Austria Klosterneuburg Austria
6 shared publications- Hünkar Can Tunç
Aarhus University, Denmark
6 shared publications
Latest Publications
- Open Access
- 1 October 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 1465-1488
A New Approach to Optimal Function Inlining for Code Size Minimization via E-graphs
Minimizing code size is a central problem in compiler optimization, especially in the context of embedded systems and mobile applications. One of the classical optimizations that has recently been adopted to reduce the output code size is function inlining, i.e. repeatedly replacing a function call site by the body of the called function. At first glance, the fact that inlining can help reduce code size is counter-intuitive. However, it enables two types of subsequent optimizations which can affect the code size significantly: (i) the intra-procedural optimizations performed within each function, which make use of the additional context provided by inlining, and (ii) the elimination of dead functions. Many existing heuristics, such as those used by LLVM, focus on a local size analysis based on a few call sites. Thus, they miss the global opportunities to remove dead functions. On the other hand, the current state-of-the-art approach of auto-tuning by Theodoridis et al. [ASPLOS 2022] focuses on global code size but inspects each call site independently in order to avoid a combinatorial explosion. However, inlining decisions are not independent in practice. It is possible that two inlining choices each increase code size on their own, but applying both of them together reduces the size. In this work, we show that the problem of optimal inlining for code size minimization is NP-hard. We then present a completely different approach to this problem. Our algorithm is based on equality graphs (e-graphs), which are a standard tool in automated theorem proving and have recently been adopted by the compiler optimization community as a key ingredient in equality saturation. We show that optimal function inlining can be reduced to e-graph extraction. Although e-graph extraction is also NP-hard, there are efficient solvers that can handle sparse instances of this problem [OOPSLA 2024]. We build upon these solvers and add further inlining-specific heuristics to design an algorithm for code size reduction. Finally, we present experimental results on the standard SPEC benchmarks. Compared with LLVM, our approach reduces the code size to 95.34%. This is competitive with the state-of-the-art auto-tuning method of [ASPLOS 2022], which achieves 95.24%. In terms of running time, our approach is 20x faster than auto-tuning. More importantly, due to the two methods having orthogonal strengths, applying both of them leads to a further significant improvement, reducing the code size to 93.94% of LLVM's output.
- 1 October 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 1465-1488
Open AccessA New Approach to Optimal Function Inlining for Code Size Minimization via E-graphs
Minimizing code size is a central problem in compiler optimization, especially in the context of embedded systems and mobile applications. One of the classical optimizations that has recently been adopted to reduce the output code size is function inlining, i.e. repeatedly replacing a function call site by the body of the called function. At first glance, the fact that inlining can help reduce code size is counter-intuitive. However, it enables two types of subsequent optimizations which can affect the code size significantly: (i) the intra-procedural optimizations performed within each function, which make use of the additional context provided by inlining, and (ii) the elimination of dead functions. Many existing heuristics, such as those used by LLVM, focus on a local size analysis based on a few call sites. Thus, they miss the global opportunities to remove dead functions. On the other hand, the current state-of-the-art approach of auto-tuning by Theodoridis et al. [ASPLOS 2022] focuses on global code size but inspects each call site independently in order to avoid a combinatorial explosion. However, inlining decisions are not independent in practice. It is possible that two inlining choices each increase code size on their own, but applying both of them together reduces the size. In this work, we show that the problem of optimal inlining for code size minimization is NP-hard. We then present a completely different approach to this problem. Our algorithm is based on equality graphs (e-graphs), which are a standard tool in automated theorem proving and have recently been adopted by the compiler optimization community as a key ingredient in equality saturation. We show that optimal function inlining can be reduced to e-graph extraction. Although e-graph extraction is also NP-hard, there are efficient solvers that can handle sparse instances of this problem [OOPSLA 2024]. We build upon these solvers and add further inlining-specific heuristics to design an algorithm for code size reduction. Finally, we present experimental results on the standard SPEC benchmarks. Compared with LLVM, our approach reduces the code size to 95.34%. This is competitive with the state-of-the-art auto-tuning method of [ASPLOS 2022], which achieves 95.24%. In terms of running time, our approach is 20x faster than auto-tuning. More importantly, due to the two methods having orthogonal strengths, applying both of them leads to a further significant improvement, reducing the code size to 93.94% of LLVM's output.
- Open Access
- 8 June 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (PLDI) , 29-52
Fast Atomicity Monitoring
Atomicity is a fundamental abstraction in concurrency, specifying that program behavior can be understood by considering specific code blocks executing atomically. However, atomicity invariants are tricky to maintain while also optimizing for code efficiency, and atomicity violations are a common root cause of many concurrency bugs. To address this problem, several dynamic techniques have been developed for testing whether a program execution adheres to an atomicity specification, most often instantiated as conflict serializability . The efficiency of the analysis has been targeted in various papers, with the state-of-the-art algorithms RegionTrack and Aerodrome achieving a time complexity O ( nk 3 ) and O ( nk ( k + v + ℓ)), respectively, for a trace σ of n events, k threads, v locations, and ℓ locks. In this paper we introduce AtomSanitizer, a new algorithm for testing conflict serializability, with time complexity O ( nk 2 ). AtomSanitizer operates in an efficient streaming style, is theoretically faster than all existing algorithms, and also has a smaller memory footprint. Moreover, AtomSanitizer is the first algorithm designed to incur minimal locking when deployed in a concurrent monitoring setting. Experiments on standard benchmarks indicate that AtomSanitizer is always faster in practice than all existing conflict-serializability testers. Finally, we also implement AtomSanitizer inside the TSAN framework, for monitoring atomicity in real time. Our experiments reveal that AtomSanitizer incurs minimal time and space overhead compared to the data-race detection engine of TSAN, and thus is the first algorithm for conflict serializability demonstrated to be suitable for a runtime monitoring setting.
- 8 June 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (PLDI) , 29-52
Open AccessFast Atomicity Monitoring
Atomicity is a fundamental abstraction in concurrency, specifying that program behavior can be understood by considering specific code blocks executing atomically. However, atomicity invariants are tricky to maintain while also optimizing for code efficiency, and atomicity violations are a common root cause of many concurrency bugs. To address this problem, several dynamic techniques have been developed for testing whether a program execution adheres to an atomicity specification, most often instantiated as conflict serializability . The efficiency of the analysis has been targeted in various papers, with the state-of-the-art algorithms RegionTrack and Aerodrome achieving a time complexity O ( nk 3 ) and O ( nk ( k + v + ℓ)), respectively, for a trace σ of n events, k threads, v locations, and ℓ locks. In this paper we introduce AtomSanitizer, a new algorithm for testing conflict serializability, with time complexity O ( nk 2 ). AtomSanitizer operates in an efficient streaming style, is theoretically faster than all existing algorithms, and also has a smaller memory footprint. Moreover, AtomSanitizer is the first algorithm designed to incur minimal locking when deployed in a concurrent monitoring setting. Experiments on standard benchmarks indicate that AtomSanitizer is always faster in practice than all existing conflict-serializability testers. Finally, we also implement AtomSanitizer inside the TSAN framework, for monitoring atomicity in real time. Our experiments reveal that AtomSanitizer incurs minimal time and space overhead compared to the data-race detection engine of TSAN, and thus is the first algorithm for conflict serializability demonstrated to be suitable for a runtime monitoring setting.
- Open Access
- 5 May 2026
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 10
Efficient Simulation of High-Level Quantum Gates
Quantum circuit simulation is paramount to the verification and optimization of quantum algorithms, and considerable research efforts have been made towards efficient simulators. While circuits often contain high-level gates such as oracles and multi-controlled X ( C k X ) gates, existing simulation methods require compilation to a low-level gate-set before simulation. This, however, increases circuit size and incurs a considerable (typically exponential) overhead, even when the number of high-level gates is small. Here we present a gadget-based simulator which simulates high-level gates directly, thereby allowing to avoid or reduce the blowup of compilation. Our simulator uses a stabilizer decomposition of the magic state of non-stabilizer gates, with improvements in the rank of the magic state directly improving performance. We then proceed to establish a small stabilizer rank for a range of high-level gates that are common in various quantum algorithms. Using these bounds in our simulator, we improve both the theoretical complexity of simulating circuits containing such gates, and the practical running time compared to standard simulators found in IBM's Qiskit Aer library. We also derive exponential lower-bounds for the stabilizer rank of some gates under common complexity-theoretic hypotheses. In certain cases, our lower-bounds are asymptotically tight on the exponent.
- 5 May 2026
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 10
Open AccessEfficient Simulation of High-Level Quantum Gates
Quantum circuit simulation is paramount to the verification and optimization of quantum algorithms, and considerable research efforts have been made towards efficient simulators. While circuits often contain high-level gates such as oracles and multi-controlled X ( C k X ) gates, existing simulation methods require compilation to a low-level gate-set before simulation. This, however, increases circuit size and incurs a considerable (typically exponential) overhead, even when the number of high-level gates is small. Here we present a gadget-based simulator which simulates high-level gates directly, thereby allowing to avoid or reduce the blowup of compilation. Our simulator uses a stabilizer decomposition of the magic state of non-stabilizer gates, with improvements in the rank of the magic state directly improving performance. We then proceed to establish a small stabilizer rank for a range of high-level gates that are common in various quantum algorithms. Using these bounds in our simulator, we improve both the theoretical complexity of simulating circuits containing such gates, and the practical running time compared to standard simulators found in IBM's Qiskit Aer library. We also derive exponential lower-bounds for the stabilizer rank of some gates under common complexity-theoretic hypotheses. In certain cases, our lower-bounds are asymptotically tight on the exponent.
- Open Access
- 8 January 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 1-32
The Complexity of Testing Message-Passing Concurrency
A key computational question underpinning the automated testing and verification of concurrent programs is the consistency question — given a partial execution history, can it be completed in a consistent manner? Due to its importance, consistency testing has been studied extensively for memory models, as well as for database isolation levels. A common theme in all these settings is the use of shared-memory as the primal mode of interthread communication. On the other hand, modern programming languages, such as Go, Rust and Kotlin, advocate a paradigm shift towards channel-based (i.e., message-passing) communication. However, the consistency question for channel-based concurrency is currently poorly understood. In this paper we lift the study of fundamental consistency problems to channels, taking into account various input parameters, such as the number of threads executing, the number of channels, and the channel capacities. We draw a rich complexity landscape, including upper bounds that become polynomial when certain input parameters are fixed, as well as hardness lower bounds. Our upper bounds are based on algorithms that can drive the verification of channel consistency in automated verification tools. Our lower bounds characterize minimal input parameters that are sufficient for hardness to arise, and thus shed light on the intricacies of testing channel-based concurrency. In combination, our upper and lower bounds characterize the boundary of tractability/intractability of verifying channel consistency, and imply that our algorithms are often (nearly) optimal. We have also implemented our main consistency checking algorithm and designed optimizations to enhance its performance. We evaluated the performance of our implementation over a set of 103 instances obtained from open source Go projects, and compared it against a constraint-solving based algorithm. Our experimental results demonstrate the power of our consistency-checking algorithm; it scales to around 1M events, and is significantly faster in running-time performance, compared to a constraint-solving approach.
- 8 January 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 1-32
Open AccessThe Complexity of Testing Message-Passing Concurrency
A key computational question underpinning the automated testing and verification of concurrent programs is the consistency question — given a partial execution history, can it be completed in a consistent manner? Due to its importance, consistency testing has been studied extensively for memory models, as well as for database isolation levels. A common theme in all these settings is the use of shared-memory as the primal mode of interthread communication. On the other hand, modern programming languages, such as Go, Rust and Kotlin, advocate a paradigm shift towards channel-based (i.e., message-passing) communication. However, the consistency question for channel-based concurrency is currently poorly understood. In this paper we lift the study of fundamental consistency problems to channels, taking into account various input parameters, such as the number of threads executing, the number of channels, and the channel capacities. We draw a rich complexity landscape, including upper bounds that become polynomial when certain input parameters are fixed, as well as hardness lower bounds. Our upper bounds are based on algorithms that can drive the verification of channel consistency in automated verification tools. Our lower bounds characterize minimal input parameters that are sufficient for hardness to arise, and thus shed light on the intricacies of testing channel-based concurrency. In combination, our upper and lower bounds characterize the boundary of tractability/intractability of verifying channel consistency, and imply that our algorithms are often (nearly) optimal. We have also implemented our main consistency checking algorithm and designed optimizations to enhance its performance. We evaluated the performance of our implementation over a set of 103 instances obtained from open source Go projects, and compared it against a constraint-solving based algorithm. Our experimental results demonstrate the power of our consistency-checking algorithm; it scales to around 1M events, and is significantly faster in running-time performance, compared to a constraint-solving approach.
- Open Access
- 30 October 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computer Systems
- Vol. 44 (3) , 1-31
Efficient Dynamic Concurrency Analysis with Collective Sparse Segment Trees
Dynamic analyses are a standard approach to analyzing and testing concurrent programs. Such techniques observe program traces σ and analyze them to infer the presence or absence of bugs. At its core, each analysis maintains a partial order P that represents order dependencies between the events of σ . Naturally, the scalability of the analysis largely depends on maintaining P efficiently. The standard data structure for this task has thus far been Vector Clocks. These, however, are slow for analyses that follow a non-streaming style, costing O ( n ) time for inserting (and propagating) each new ordering in P , where n is the size of σ , while they cannot handle the deletion of existing orderings. In this paper we develop Collective Sparse Segment Trees ( CSSTs ), a simple but elegant data structure for maintaining a partial order P . CSSTs thrive when the width k of P is much smaller than the size n of its domain, allowing inserting, deleting, and querying for orderings in P to run in O (log n ) time. For a concurrent trace, k normally equals the number of its threads, and is orders of magnitude smaller than its size n , making CSSTs fitting for this setting. Our experiments confirm that CSSTs are the best data structure currently to handle a range of dynamic analyses from existing literature.
- 30 October 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computer Systems
- Vol. 44 (3) , 1-31
Open AccessEfficient Dynamic Concurrency Analysis with Collective Sparse Segment Trees
Dynamic analyses are a standard approach to analyzing and testing concurrent programs. Such techniques observe program traces σ and analyze them to infer the presence or absence of bugs. At its core, each analysis maintains a partial order P that represents order dependencies between the events of σ . Naturally, the scalability of the analysis largely depends on maintaining P efficiently. The standard data structure for this task has thus far been Vector Clocks. These, however, are slow for analyses that follow a non-streaming style, costing O ( n ) time for inserting (and propagating) each new ordering in P , where n is the size of σ , while they cannot handle the deletion of existing orderings. In this paper we develop Collective Sparse Segment Trees ( CSSTs ), a simple but elegant data structure for maintaining a partial order P . CSSTs thrive when the width k of P is much smaller than the size n of its domain, allowing inserting, deleting, and querying for orderings in P to run in O (log n ) time. For a concurrent trace, k normally equals the number of its threads, and is orders of magnitude smaller than its size n , making CSSTs fitting for this setting. Our experiments confirm that CSSTs are the best data structure currently to handle a range of dynamic analyses from existing literature.
- Open Access
- 23 July 2025
- Published by Springer Nature
- p. 321-346
$\textsf{GPUMC}$: A Stateless Model Checker for GPU Weak Memory ConcurrencyGPU computing is embracing weak memory concurrency for performance improvement. However, compared to CPUs, modern GPUs provide more fine-grained concurrency features such as scopes, have additional properties like divergence, and thereby follow different weak memory consistency models. These features and properties make concurrent programming on GPUs more complex and error-prone. To this end, we present $$\textsf{GPUMC}$$ , a stateless model checker to check the correctness of GPU shared-memory concurrent programs under scoped-RC11 weak memory concurrency model. $$\textsf{GPUMC}$$ explores all possible executions in GPU programs to reveal various errors - races, barrier divergence, and assertion violations. In addition, $$\textsf{GPUMC}$$ also automatically repairs these errors in the appropriate cases. We evaluate $$\textsf{GPUMC}$$ on benchmarks and real-life GPU programs. $$\textsf{GPUMC}$$ is efficient both in time and memory in verifying large GPU programs where state-of-the-art tools are timed out. In addition, $$\textsf{GPUMC}$$ identifies all known errors in these benchmarks compared to the state-of-the-art tools.- 23 July 2025
- Published by Springer Nature
- p. 321-346
Open Access$\textsf{GPUMC}$: A Stateless Model Checker for GPU Weak Memory ConcurrencyGPU computing is embracing weak memory concurrency for performance improvement. However, compared to CPUs, modern GPUs provide more fine-grained concurrency features such as scopes, have additional properties like divergence, and thereby follow different weak memory consistency models. These features and properties make concurrent programming on GPUs more complex and error-prone. To this end, we present $$\textsf{GPUMC}$$ , a stateless model checker to check the correctness of GPU shared-memory concurrent programs under scoped-RC11 weak memory concurrency model. $$\textsf{GPUMC}$$ explores all possible executions in GPU programs to reveal various errors - races, barrier divergence, and assertion violations. In addition, $$\textsf{GPUMC}$$ also automatically repairs these errors in the appropriate cases. We evaluate $$\textsf{GPUMC}$$ on benchmarks and real-life GPU programs. $$\textsf{GPUMC}$$ is efficient both in time and memory in verifying large GPU programs where state-of-the-art tools are timed out. In addition, $$\textsf{GPUMC}$$ identifies all known errors in these benchmarks compared to the state-of-the-art tools. - Open Access
- 10 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 1540-1564
AWDIT: An Optimal Weak Database Isolation Tester
Database isolation is a formal contract concerning the level of data consistency that a database provides to its clients. In order to achieve low latency, high throughput, and partition tolerance, modern databases forgo strong transaction isolation for weak isolation guarantees. However, several production databases have been found to suffer from isolation bugs , breaking their data-consistency contract. Black-box testing is a prominent technique for detecting isolation bugs, by checking whether histories of database transactions adhere to a prescribed isolation level. In order to test databases on realistic workloads of large size, isolation testers must be as efficient as possible, a requirement that has initiated a study of the complexity of isolation testing. Although testing strong isolation has been known to be NP-complete, weak isolation levels were recently shown to be testable in polynomial time, which has propelled the scalability of testing tools. However, existing testers have a large polynomial complexity, restricting testing to workloads of only moderate size, which is not typical of large-scale databases. How efficiently can we provably test weak database isolation? In this work, we develop AWDIT, a highly-efficient and provably optimal tester for weak database isolation . Given a history H of size n and k sessions, AWDIT tests whether H satisfies the most common weak isolation levels of Read Committed (RC), Read Atomic (RA), and Causal Consistency (CC) in time O ( n 3/2 ), O ( n 3/2 ), and O ( n · k ), respectively, improving significantly over the state of the art. Moreover, we prove that AWDIT is essentially optimal , in the sense that there is a lower bound of n 3/2 , based on the combinatorial BMM hypothesis, for any weak isolation level between RC and CC. Our experiments show that AWDIT is significantly faster than existing, highly optimized testers; e.g., for the ∼20% largest histories, AWDIT obtains an average speedup of 245×, 193×, and 62× for RC, RA, and CC, respectively, over the best baseline.
- 10 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 1540-1564
Open AccessAWDIT: An Optimal Weak Database Isolation Tester
Database isolation is a formal contract concerning the level of data consistency that a database provides to its clients. In order to achieve low latency, high throughput, and partition tolerance, modern databases forgo strong transaction isolation for weak isolation guarantees. However, several production databases have been found to suffer from isolation bugs , breaking their data-consistency contract. Black-box testing is a prominent technique for detecting isolation bugs, by checking whether histories of database transactions adhere to a prescribed isolation level. In order to test databases on realistic workloads of large size, isolation testers must be as efficient as possible, a requirement that has initiated a study of the complexity of isolation testing. Although testing strong isolation has been known to be NP-complete, weak isolation levels were recently shown to be testable in polynomial time, which has propelled the scalability of testing tools. However, existing testers have a large polynomial complexity, restricting testing to workloads of only moderate size, which is not typical of large-scale databases. How efficiently can we provably test weak database isolation? In this work, we develop AWDIT, a highly-efficient and provably optimal tester for weak database isolation . Given a history H of size n and k sessions, AWDIT tests whether H satisfies the most common weak isolation levels of Read Committed (RC), Read Atomic (RA), and Causal Consistency (CC) in time O ( n 3/2 ), O ( n 3/2 ), and O ( n · k ), respectively, improving significantly over the state of the art. Moreover, we prove that AWDIT is essentially optimal , in the sense that there is a lower bound of n 3/2 , based on the combinatorial BMM hypothesis, for any weak isolation level between RC and CC. Our experiments show that AWDIT is significantly faster than existing, highly optimized testers; e.g., for the ∼20% largest histories, AWDIT obtains an average speedup of 245×, 193×, and 62× for RC, RA, and CC, respectively, over the best baseline.
- Open Access
GPUMC: A Stateless Model Checker for GPU Weak Memory Concurrency
GPU computing is embracing weak memory concurrency for performance improvement. However, compared to CPUs, modern GPUs provide more fine-grained concurrency features such as scopes, have additional properties like divergence, and thereby follow different weak memory consistency models. These features and properties make concurrent programming on GPUs more complex and error-prone. To this end, we present GPUMC, a stateless model checker to check the correctness of GPU shared-memory concurrent programs under scoped-RC11 weak memory concurrency model. GPUMC explores all possible executions in GPU programs to reveal various errors - races, barrier divergence, and assertion violations. In addition, GPUMC also automatically repairs these errors in the appropriate cases. We evaluate GPUMC with benchmarks and real-life GPU programs. GPUMC is efficient both in time and memory in verifying large GPU programs where state-of-the-art tools are timed out. In addition, GPUMC identifies all known errors in these benchmarks compared to the state-of-the-art tools.
Open AccessGPUMC: A Stateless Model Checker for GPU Weak Memory Concurrency
GPU computing is embracing weak memory concurrency for performance improvement. However, compared to CPUs, modern GPUs provide more fine-grained concurrency features such as scopes, have additional properties like divergence, and thereby follow different weak memory consistency models. These features and properties make concurrent programming on GPUs more complex and error-prone. To this end, we present GPUMC, a stateless model checker to check the correctness of GPU shared-memory concurrent programs under scoped-RC11 weak memory concurrency model. GPUMC explores all possible executions in GPU programs to reveal various errors - races, barrier divergence, and assertion violations. In addition, GPUMC also automatically repairs these errors in the appropriate cases. We evaluate GPUMC with benchmarks and real-life GPU programs. GPUMC is efficient both in time and memory in verifying large GPU programs where state-of-the-art tools are timed out. In addition, GPUMC identifies all known errors in these benchmarks compared to the state-of-the-art tools.
- Open Access
- 15 April 2025
- Published by Springer Nature in International Journal on Software Tools for Technology Transfer
- Vol. 27 (2) , 255-266
CFL-based methods for approximating interleaved Dyck reachability
Interleaved Dyck Reachability is a standard, graph-based formulation of a plethora of static analyses that seek to be context- and field-sensitive, where each type of sensitivity is expressed via a CFL/Dyck language. Unfortunately, the problem is well known to be undecidable in general, and thus existing approaches resort to clever overapproximations. Recently, a mutual-refinement algorithm, that iteratively considers each of the two sensitivities in isolation until a fixpoint is reached, was shown to achieve high precision. In this work we present a more precise approximation of Interleaved Dyck Reachability, by extending the mutual-refinement algorithm in three general directions. First, we develop refined CFLs to express each type of sensitivity precisely, while simultaneously also lightly overapproximating the opposite type. Second, we modify the graph information in a way to highlight unreachable paths not previously captured by the algorithm. Third, we apply the resulting algorithm on an on-demand basis, which effectively masks out imprecision incurred by parts of the graph that are irrelevant for the query at hand. Our experiments show that the new approach offers significantly higher precision than the vanilla mutual-refinement algorithm and other common baselines; for a particularly challenging benchmark, we report, on average, $51\%$ of the reachable pairs compared to the most recent alternative.- 15 April 2025
- Published by Springer Nature in International Journal on Software Tools for Technology Transfer
- Vol. 27 (2) , 255-266
Open AccessCFL-based methods for approximating interleaved Dyck reachability
Interleaved Dyck Reachability is a standard, graph-based formulation of a plethora of static analyses that seek to be context- and field-sensitive, where each type of sensitivity is expressed via a CFL/Dyck language. Unfortunately, the problem is well known to be undecidable in general, and thus existing approaches resort to clever overapproximations. Recently, a mutual-refinement algorithm, that iteratively considers each of the two sensitivities in isolation until a fixpoint is reached, was shown to achieve high precision. In this work we present a more precise approximation of Interleaved Dyck Reachability, by extending the mutual-refinement algorithm in three general directions. First, we develop refined CFLs to express each type of sensitivity precisely, while simultaneously also lightly overapproximating the opposite type. Second, we modify the graph information in a way to highlight unreachable paths not previously captured by the algorithm. Third, we apply the resulting algorithm on an on-demand basis, which effectively masks out imprecision incurred by parts of the graph that are irrelevant for the query at hand. Our experiments show that the new approach offers significantly higher precision than the vanilla mutual-refinement algorithm and other common baselines; for a particularly challenging benchmark, we report, on average, $51\%$ of the reachable pairs compared to the most recent alternative.