Regular Symbolic Analysis of Dynamic Networks of Pushdown Systems

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=v_mwqwlO1rk


Duration: 1:00:49
130 views
2

We introduce abstract models for multithreaded programs based on dynamic networks of pushdown systems. We address the problem of symbolic reachability analysis for these models. More precisely, we consider the problem of computing effective representations of their reachability sets using (finite-state) automata-based techniques. We show that, while forward reachability sets are not regular in general (but context-free), backward reachability sets starting from regular sets of configurations are always regular. We provide algorithms for computing backward reachability sets using word/tree automata, and show how these algorithms can be applied for flow analysis of multithreaded programs. This is a joint work with Markus Mueller-Olm and Tayssir Touili.



Other Videos By Microsoft Research


2016-09-05Root numbers and ranks
2016-09-05Tutorial on Foundations of Probabilistic Answers to Queries
2016-09-05Generic Entity Resolution
2016-09-05Regular Extrapolation of Behavioural Models-Searching for Regular Patterns by Observation
2016-09-05The Stanford Data Stream Management System
2016-09-05Self-Replicating Machines, Open Source Hardware, & the Relationship Between Information & Structure
2016-09-05Dereverberation Suppression for Improved Speech Recognition and Human Perception
2016-09-05Using Machine Learning to Verify Systems
2016-09-05Friendly Virtual Machines: Leveraging a Feedback-Control Model for Application Adaptation
2016-09-05ExScal: Elements of an Extreme Scale Wireless Sensor Network
2016-09-05Regular Symbolic Analysis of Dynamic Networks of Pushdown Systems
2016-09-05Scalable Program Analysis Using Boolean Satisfiability
2016-09-05Slepian-Wolf coded quantization for Wyner-Ziv coding
2016-09-05Spoken Language Support for Software Development
2016-09-05Designing Extensible IP Router Software
2016-09-05Estimating Geometric Scene Context from a Single Image [1/3]
2016-09-05Singularity of random Bernoulli matrices
2016-09-05Scalable Knowledge Harvesting
2016-09-05Modeling and Analysis of Access Control Survivability
2016-09-05XML Full-Text Search and Scoring [1/25]
2016-09-05A Large-Margin Framework for Learning Structured Prediction Models


Tags:
microsoft research