Survey of Context-Sensitivity of Value Flow Analysis

PhD Qualifying Examination


Title: "Survey of Context-Sensitivity of Value Flow Analysis"

by

Mr. Yongchao WANG


Abstract:

Context-sensitive value flow analysis has shown its promise to be highly 
effective in detecting a broad spectrum of software bugs by tracking the flow 
of values along data dependence relations such as memory leaks in resource 
usage, null pointer dereference in memory safety, and the propagation of 
tainted data in security properties. The key to this effectiveness lies in 
being context-sensitive, which distinguishes function calls and returns in 
different calling contexts. This allows the value flow analysis to compute 
only the realizable paths over the value flow graph. However, achieving 
context sensitivity is a non-trivial task and often suffers from scalability 
problems when analyzing large programs. In this survey, we investigate 
various techniques to alleviate the challenges of context sensitivity. 
Depending on the methodology, existing efforts can be classified into three 
categories: Function-cloning-based approaches: Inspired by classic compiler 
optimization, these approaches inline a copy of the function (or function 
summaries) into different callers, thereby automatically eliminating the 
calling context. Context-free language (CFL) reachability-based approaches: 
The context-sensitive analysis is formulated as a CFL reachability problem by 
applying Dyck-CFL to capture paired function calls and returns using matched 
parentheses. The CFL reachability is then solved using dynamic programming 
algorithms and datalog engines, such as Soufflé. Hybrid function cloning and 
CFL reachability approaches: Instead of applying function cloning at all call 
sites, hybrid approaches selectively apply function cloning at some call 
sites and then compute CFL reachability. We will discuss the details of these 
techniques and their limitations, and offering insights into opportunities 
for future research in this field.


Date:                   Monday, 27 January 2025

Time:                   10:00am - 12:00noon

Venue:                  Room 3494
                        Lifts 25/26

Committee Members:      Prof. Charles Zhang (Supervisor)
                        Prof. Qiong Luo (Chairperson)
                        Dr. Dongdong She
                        Dr. Shuai Wang