Scalable Path-Sensitive Data-Dependence Analysis in the Presence of Aliasing

MPhil Thesis Defence


Title: "Scalable Path-Sensitive Data-Dependence Analysis in the Presence 
of Aliasing"

By

Mr. Peisen YAO


Abstract

This thesis addresses the challenge of precise and scalable 
data-dependence analysis, which tracks the definition-use information in a 
program. Such information can be used for detecting a broad category of 
software properties, such as memory safety (e.g., null dereference), 
resource usage (e.g., memory leak), and security properties (e.g., the use 
of tainted data). However, owing to the innate undecidability of program 
analysis, there is still little progress on path-sensitive data-dependence 
analysis that can scale to millions of lines of code.

We present a path- and context-sensitive data-dependence analysis that 
significantly improves upon the state-of-the-art. Our approach decomposes 
a path-sensitive data-dependence analysis into 1) a lightweight but 
precision-preserving quasi-path-sensitive and context-sensitive alias 
analysis that constructs guarded data-dependence graphs, and 2) a 
demand-driven phase where we resolve the full path- and context-sensitive 
data-dependence relations via graph reachability queries.

We have implemented the proposed technique as a tool called Falcon. Using 
a suite of sixteen open-source C/C++ programs, which range in size from 13 
KLoC to 7.99 MLoC, we compare our techniques against the state-of-the-art 
approaches for data-dependence graph construction and path-sensitive 
data-dependence analysis. The experimental results show that Falcon 
gracefully scales to a large codebase and is useful for bug hunting. Our 
work has made path-sensitive data-dependence analysis a reasonable choice 
for applications with millions of lines of code. In a virtuous circle, the 
development of such an analysis would likely uncover additional clients 
that benefit from the added precision.


Date:			Friday, 27 September 2019

Time:			1:30pm - 3:30pm

Venue:			Room 3598
 			Lifts 27/28

Committee Members:	Dr. Charles Zhang (Supervisor)
 			Prof. Shing-Chi Cheung (Chairperson)
 			Dr. Shuai Wang


**** ALL are Welcome ****