Grant: Discovery Grants Program - Individual
University of Waterloo
$36,000.00
Language-Agnostic Program Reduction for Debugging Language Implementations
EF 2024-25
Résumé
Language implementations are fundamental system software, either for compiling source code into binary code (e.g., GCC, Rustc) or for directly interpreting the source code (e.g., Bash, Python). Debugging language implementations has long been recognized as a time-consuming and painstaking task due to the complexities within their algorithms and the bug-triggering input programs. (Inputs to language implementations are also programs.) Consequently, developers of language implementations have extensively adopted program reduction techniques to streamline the debugging process. Specifically, when given a bug-triggering program, a program reducer can autonomously produce a minimized program that still triggers the same bug but with bug-irrelevant code elements removed.
Existing program reduction algorithms exhibit shortcomings in efficiency (reduction time), effectiveness (size of reduced programs), or both. For example, language-agnostic program reducers work for a variety of languages but can be slow and produce large results (e.g., Delta Debugging, Hierarchical Delta Debugging, and Perses). On the other hand, language-specific program reducers are tailored and optimized to reduce programs in a particular language, often resulting in smaller outcomes at the cost of reduced generalizability.
This proposal aims to develop a novel, language-agnostic approach to address existing issues concerning effective, efficient, and general program reduction. The fundamental idea emerges from the PI's extensive experience over the past seven years in developing and using Perses. Specifically, the proposal has three main components. First, this proposal seeks to exploit the formal syntax of the program under reduction in a comprehensive manner, to expand the boundaries of syntax-guided, language-agnostic program reduction. Second, the proposal aims to harness the capabilities of Large Language Models (LLMs) for language-specific program reduction. LLMs have demonstrated exceptional proficiency in code understanding. Therefore, the proposal intends to leverage the power of LLMs to facilitate language-agnostic program reduction. For instance, LLMs can automatically inline functions in a program, and we can prompt them to do so during program reduction, resulting in more compact programs. This functionality is currently not feasible with existing language-agnostic program reducers. Last, this proposal will introduce a standardized evaluation procedure and a benchmark suite comprising multilingual programs. These resources will enable a comprehensive assessment of program reduction techniques from various perspectives.
The proposed research will benefit various development communities of language implementations. Notably, Google and the Rust language community have expressed interest in adopting Perses to reduce GLSL and Rust programs. This proposal will also benefit Canadian companies that develop language implementations, such as IBM Canada and Microchip.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2024-05173
Name nom
Sun, Chengnian
Department département
Cheriton School of Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
36000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Language-Agnostic Program Reduction for Debugging Language Implementations
Keywords
program reduction; test case minimization; compiler debugging; delta debugging
Application summary
Language implementations are fundamental system software, either for compiling source code into binary code (e.g., GCC, Rustc) or for directly interpreting the source code (e.g., Bash, Python). Debugging language implementations has long been recognized as a time-consuming and painstaking task due to the complexities within their algorithms and the bug-triggering input programs. (Inputs to language implementations are also programs.) Consequently, developers of language implementations have extensively adopted program reduction techniques to streamline the debugging process. Specifically, when given a bug-triggering program, a program reducer can autonomously produce a minimized program that still triggers the same bug but with bug-irrelevant code elements removed.
Existing program reduction algorithms exhibit shortcomings in efficiency (reduction time), effectiveness (size of reduced programs), or both. For example, language-agnostic program reducers work for a variety of languages but can be slow and produce large results (e.g., Delta Debugging, Hierarchical Delta Debugging, and Perses). On the other hand, language-specific program reducers are tailored and optimized to reduce programs in a particular language, often resulting in smaller outcomes at the cost of reduced generalizability.
This proposal aims to develop a novel, language-agnostic approach to address existing issues concerning effective, efficient, and general program reduction. The fundamental idea emerges from the PI's extensive experience over the past seven years in developing and using Perses. Specifically, the proposal has three main components. First, this proposal seeks to exploit the formal syntax of the program under reduction in a comprehensive manner, to expand the boundaries of syntax-guided, language-agnostic program reduction. Second, the proposal aims to harness the capabilities of Large Language Models (LLMs) for language-specific program reduction. LLMs have demonstrated exceptional proficiency in code understanding. Therefore, the proposal intends to leverage the power of LLMs to facilitate language-agnostic program reduction. For instance, LLMs can automatically inline functions in a program, and we can prompt them to do so during program reduction, resulting in more compact programs. This functionality is currently not feasible with existing language-agnostic program reducers. Last, this proposal will introduce a standardized evaluation procedure and a benchmark suite comprising multilingual programs. These resources will enable a comprehensive assessment of program reduction techniques from various perspectives.
The proposed research will benefit various development communities of language implementations. Notably, Google and the Rust language community have expressed interest in adopting Perses to reduce GLSL and Rust programs. This proposal will also benefit Canadian companies that develop language implementations, such as IBM Canada and Microchip.