Data Flow Analysis of Asynchronous Systems using Infinite Abstract Domains
Open Access
- 23 March 2021
- book chapter
- Published by Springer Nature
- Vol. 12648, 30-58
Abstract
Asynchronous message-passing systems are employed frequently to implement distributed mechanisms, protocols, and processes. This paper addresses the problem of precise data flow analysis for such systems. To obtain good precision, data flow analysis needs to somehow skip execution paths that read more messages than the number of messages sent so far in the path, as such paths are infeasible at run time. Existing data flow analysis techniques do elide a subset of such infeasible paths, but have the restriction that they admit only finite abstract analysis domains. In this paper we propose a generalization of these approaches to admit infinite abstract analysis domains, as such domains are commonly used in practice to obtain high precision. We have implemented our approach, and have analyzed its performance on a set of 14 benchmarks. On these benchmarks our tool obtains significantly higher precision compared to a baseline approach that does not elide any infeasible paths and to another baseline that elides infeasible paths but admits only finite abstract domains.Keywords
This publication has 50 references indexed in Scilit:
- Verifying liveness for asynchronous programsACM SIGPLAN Notices, 2009
- Interprocedural analysis of asynchronous programsACM SIGPLAN Notices, 2007
- Expand, Enlarge and Check: New algorithms for the coverability problem of WSTSJournal of Computer and System Sciences, 2006
- Precise interprocedural analysis through linear algebraACM SIGPLAN Notices, 2004
- State space reduction using partial order techniquesInternational Journal on Software Tools for Technology Transfer, 1999
- On-the-fly analysis of systems with unbounded, lossy FIFO channelsLecture Notes in Computer Science, 1998
- The model checker SPINIEEE Transactions on Software Engineering, 1997
- Precise interprocedural dataflow analysis with applications to constant propagationTheoretical Computer Science, 1996
- An O(n log n) unidirectional distributed algorithm for extrema finding in a circleJournal of Algorithms, 1982
- The Complexity of the Finite Containment Problem for Petri NetsJournal of the ACM, 1981