[Colloquium] Xiao/Dissertation Defense/May 4, 2010

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Yingqi Xiao

Date:  Tuesday, May 4, 2010

Time:  12:00 PM

Place:  Ryerson 251

Title: Abstract Trace Analysis for Concurrent Programs

Abstract:
Program analysis plays an important role in modern software. With the
advent of cheap parallel processing on the desktop(and laptop),
concurrency is increasingly widely used in software. Many concurrent
languages provide powerful concurrency primitives, such as dynamic
creation of processes, dynamic creation of first class channels and
communication over those channels. These primitives provide more
flexibility of concurrent programing to programs. But at the same
time, they make programs more complex and more non-deterministic. The
consequence is that designing and implementing static analysis for
such programs become more important and challenging.

One fundamental challenge of static analysis for concurrent programs
is that deciding if an program point is reachable in the presence of
nondeterminism is undecidable. To solve this problem, we have to
provide safe approximation of the set of possible run-time behaviors
so that we can compute satisfying properties of programs while without
losing too much precision. The goal of this thesis is to investigate
techniques of static analysis of dynamic communication of concurrent
programs and present a new approach to analyze concurrent programs.

In this thesis, we present a new approach to compute a precise
approximation of all possible control paths that reach each program
points. We call the approach abstract trace analysis. The
approximation is precise because it only considers valid control paths
that functions return to where they get called. We also demonstrate
how to do powerful analysis based on abstract trace analysis. We show
how to analyze communication topology based on abstract trace
analysis. The analysis can extract channel usage information from
abstract trace, distinguish different abstract dynamic instances of
same channels and generate more precise output than our previous
modular work. In this thesis, we also show how to extract concurrency
information from abstract trace and use it to do optimization by
detecting and transforming monitor threads into more efficient monitor
functions.

Yingqi's advisor is Prof. John Reppy

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#xiaoyq

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=