Back to search

Georgia Institute of Technology

A Framework for Faster Software Verification and Better Compiler Optimizations through Symbiosis

Abstract

dc:description.abstract

Despite significant advancements over the years, compilers and software verification systems still face limitations in their capabilities. The conservative nature of static program analysis restricts the applicability and effectiveness of compiler optimizations. In addition, software verification remains intractable for real-world applications of reasonable size due to the significant time required. There is a growing need for optimization approaches that leverage verification techniques and vice versa. This work highlights the symbiotic relationship between compiler analyses and software verification, demonstrating how each can benefit from the other's advancements. It also proposes new analyses and techniques to further capitalize on this relationship. This dissertation demonstrates that both directions of the symbiotic relationship are highly valuable. It introduces a framework called VICO, which transforms conservative dependence and alias constraints into invariants verified in a demand-driven manner. These verified dependence invariants enable improved auto-parallelization and loop transformations, resulting in performance gains in over 75 loops, with an average speedup of 14.7x on Apple M1 Pro systems and 6.07x on Intel Xeon E5-2660 systems. Additionally, verified alias invariants improve register allocation and global value numbering (GVN), reducing code size and improving execution times for Linux programs and SPEC benchmarks. On the verification front, two significant challenges are procedure calls and loops. To address the challenge of procedure calls, this work presents CVFunc, a framework that combines novel compiler analysis with reinforcement learning to accelerate interprocedural software verification tasks. CVFunc uses bi-directional dataflow analysis to identify variables that influence verifier constructs, such as assertions. By focusing on these variables, the framework introduces a new analysis to guide inlining decisions at call sites, avoiding the approximations introduced by verifier summaries. At the verifier level, CVFunc employs reinforcement learning to optimize approximations and inlining decisions and incorporates parallel refinements to accelerate the counterexample-guided abstraction refinement (CEGAR) process. As a result, CVFunc improves verification times by an average of 13.22%, with a maximum improvement of 21.9%, and successfully resolves 68 previously unsolved tasks in the software verification competition, SV-COMP. To address the challenge of loops, this dissertation introduces CVLoop, a framework that combines loop transformations and array dataflow analysis to enhance loop-based software verification tasks. CVLoop abstracts loop nests by creating iteration models that simplify loops for verification, enabling the verifier to prove properties more effectively. It then applies array dataflow analysis to remaining loops, defining possible interval values that can be directly used to prove properties or generate invariants for k-induction. In SV-COMP's loop category, CVLoop solves 38 new verification tasks in CPAChecker and achieves an average improvement of 13 tasks (up to 23) across other verification tools. In summary, this dissertation develops innovative techniques that exploit the symbiotic relationship between compiler analysis/optimizations and software verification. The empirical results demonstrate the substantial benefits of this approach, addressing key challenges in SV-COMP and advancing the state of the art in compiler optimization and software verification.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Khan, Sharjeel Mahmood
Advisor dc:contributor.advisor
  • Pande, Santosh
Committee members dc:contributor.committeemember
  • Sarkar, Vivek
  • Zhang, Qirun
  • Ganesh, Vijay
  • Feron, Eric

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/81481

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Khan, Sharjeel Mahmood. A Framework for Faster Software Verification and Better Compiler Optimizations through Symbiosis. Doctoral thesis, Georgia Institute of Technology, 2025. https://hdl.handle.net/1853/81481