Enhancing Static Call Graph Construction: A Survey

PhD Qualifying Examination


Title: "Enhancing Static Call Graph Construction: A Survey"

by

Mr. Yibo JIN


Abstract:

Program call graphs model caller-callee relations between procedures. They
are indispensable for multiple downstream clients, including program
understanding and bug detection, all of which pursue precise call graphs
and scalable construction to ensure high effectiveness. Static call graph
construction is commonly employed to compute potential callees at runtime
without executing programs. Its core challenge stems from indirect calls
and virtual calls, whose dynamic behaviors necessitate over-approximation.
However, two fundamental techniques in static call graph construction,
namely type analysis and pointer analysis, have distinct defects, where the
former suffers from notorious imprecision, while the latter is
computationally expensive by nature.

This survey provides a comprehensive overview of problems, challenges, and
existing solutions for enhancing static call graph construction for indirect
calls and virtual calls in terms of precision and scalability. Specifically,
we first explore static precision enhancement schemes for type analysis,
which incorporate diverse program information to narrow the broad range of
type matching. Then we investigate static scalability enhancement schemes for
pointer analysis, which debloat redundant computation for fine-grained
pointer information possibly at the expense of reduced precision. We expect
our survey to shed light on our future work on developing practical
algorithms for static call graph construction.


Date:                   Wednesday, 3 December 2025

Time:                   10:00am - 12:00pm

Venue:                  Room 5501
                        Lift 25/26

Committee Members:      Prof. Charles Zhang (Supervisor)
                        Dr. Wei Wang (Chairperson)
                        Dr. Dimitris Papadopoulos