Abstract

An asynchronous program is one that contains procedure calls which are not directly executed from the callsite, but stored and ``dispatched" in a non-deterministic order by an external scheduler at a later point. Asynchronous programs are at the core of many server programs, embedded systems, and popular programming models for the web (Javascript and AJAX). Asynchronous programs are hard to analyze statically as both the program stack and the number of outstanding asynchronous requests may be unbounded. We describe an algorithm for the problem of interprocedural dataflow analysis for asynchronous programs as a generalization of interprocedural dataflow analysis for sequential programs. Our algorithm can be easily implemented on top of any existing interprocedural dataflow analysis framework. Though the problem is theoretically hard, we find that in practice our technique can efficiently analyze programs by exploiting standard optimizations of interprocedural dataflow analyses.

(Joint work with Ranjit Jhala.)