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.

BIO
Rupak Majumdar is an Assistant Professor in the Department of Computer Science at the University of California, Los Angeles. His research interests are in the verification and control of reactive systems, software verification and programming languages, logic, and automata theory. He received the President's Gold Medal from IIT, Kanpur, the Leon O. Chua award from UC Berkeley, and an NSF CAREER award.

Return to 2008 Events Calendar