Georgia Institute of Technology
A Framework for Faster Software Verification and Better Compiler Optimizations through Symbiosis
Abstract
dc:description.abstractDespite 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 × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/81481