Grammar-based Program Generation for Challenging Testing Frameworks and Shell Interpreters

You are cordially invited to attend the PhD Dissertation Defence of Riccardo Felici on Tuesday 28 January 2025 at 13:00 in room D0.02.

Abstract:
Automated testing techniques are widely used for the detection and debugging of software errors. The main high-level goals of this research are the improvement of their bug-detection capabilities and the enhancement of their level of automation. In particular, the present thesis focuses on two main domains: benchmarks for testing frameworks and grammar-based program generation to test shell interpreters. In order to compare existing automated testing techniques, it is necessary to have ground-truth benchmarks of faulty programs with different characteristics and known faults. The first result discussed in this document is the design of HyperPUT: a grammar-based program-under-test generator that is able to produce programs with seeded bugs for evaluating and comparing the bug-detection capabilities of existing testing techniques. HyperPUT produces synthetic programs with injected bugs belonging to several categories, together with the corresponding triggering input. An experimental evaluation demonstrates the flexibility of HyperPUT and its capability to produce synthetic buggy program under tests (PUTs) of various complexities and features, which can complement and extend existing manually-curated benchmarks of buggy programs. Since they are based on random mutations, raw fuzzing techniques may be insufficient to test programs that take complex, highly structured inputs, such as language compilers and interpreters. A second contribution described in this thesis is a technique to effectively detect different categories of defects in shell interpreters, whose safety and reliability are very important given their role as part of the computing infrastructure. This document presents a grammar-based approach to generate a large number of shell programs with predictable characteristics. In the described experiments, executing these programs on open-source implementations of common Unix shells revealed bugs that were previously undiscovered and have been confirmed by the shell maintainers. Compared to existing standard fuzzing approaches, our technique has advantages in terms of control of the testing environment and level of automation.

Dissertation Committee:
- Prof. Laura Pozzi, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Carlo Alberto Furia, Università della Svizzera italiana, Switzerland (Research co-Advisor)
- Prof. Gabriele Bavota, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Antonio Carzaniga, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Alessio Gambi, Krems University of Applied Sciences, Austria (External Member)
- Prof. Angelo Gargantini, Università di Bergamo, Italy (External Member)