Delta debugging for CUE configurations

Abstract

Program-Reduction hat sich als wirksames Mittel erwiesen, um die Compilerentwicklung zu beschleunigen bzw. Programme zu verkleinern, um sie sicherer zu machen. Kernstück vieler Reduktionsalgorithmen ist Delta-Debugging, ein Algorithmus zur systematischen Entfernung von Elementen aus einem Programm, währenddessen eine gegebene Eigenschaft erhalten bleiben soll. Da das Problem der Suche nach einem globalen Minimum als NP-complete eingestuft wird, definiert Program-Reduction den Begriff der "1-minimalen Lösung", bei der das Programm beim Entfernen eines einzelnen Elements die ewünschte Eigenschaft verlieren würde. Verbesserte Versionen von Delta-Debugging nutzen die baumartige Struktur des Quellcodes zur Reduzierung der notwendigen Tests, die formale Syntax von Programmiersprachen zur Begrenzung des Suchraums und probabilistische Modelle zur Beschleunigung des Reduktionsprozesses. Reduktionsalgorithmen werden in zwei Gruppen unterteilt: sprachunabhängige Algorithmen verwenden allgemeine Transformationen, um Programme in jeder beliebigen Sprache zu verkleinern, während sprachspezifische Reduktionsalgorithmen Domänenwissen nutzen, um spezifische und effektive Transformationen zu implementieren. Die meisten dieser Algorithmen werden auf prozedurale Sprachen angewandt. Diese Arbeit schlägt ein neuartiges Framework namens Seru vor, das sprach-agnostische Reduktionsalgorithmen erweitert und sprachspezifische Heuristiken auf modulare Weise integriert. Der Ansatz kann auf mehrere Sprachen angewandt werden, während das semantische Verständnis einer bestimmten Sprache genutzt wird, um Programme weiter zu reduzieren. Seru wird mit der Sprache CUE evaluiert, die starke Einflüsse von logischen Programmiersprachen enthält. Ergebnisse zeigen Verbesserungen für beide genutzten Reduktionsalgorithmen, Perses und Vulcan, mit bis zu 20,88% bzw. 16,94% kleineren Dateien. Der kombinierte Ansatz aus sprachunabhängigen Reduktionsalgorithmen und semantischen Heuristiken erwies sich als effektiv, aber zeitaufwändig in der Ausführung. Die Programmreduktion ist nicht nur für prozedurale Sprachen effektiv, sondern erweist sich auch als nützliches Werkzeug zur Reduktion logischer Programmiersprachen. In zukünftigen Arbeiten könnten Large Language Models verwendet werden, um die Entwicklung von Heuristiken für weitere Sprachen zu beschleunigen.

Program reduction proved to be an effective way to speed up compiler development or shrink programs to make them more robust. At the core of many reduction algorithms is delta debugging, a technique to systematically remove elements from a program while ensuring a required property holds. Since finding a global minimum is an NP-complete problem, program reduction aims to find a 1-minimal result, where any removal of one element causes a test failure. Delta debugging was further improved by utilizing the tree-like structure of source code, by leveraging the formal syntax of programming languages to limit the search space and by building a probabilistic model to speed-up the reduction process. Reducers are partitioned into two groups: language-agnostic reducers use general transformations to shrink programs of any language while language-specific reducers leverage domain knowledge to implement specific and powerful transformations. Most of these reducers focus on procedural languages. This work proposes a novel framework called Seru, that extends agnostic reducers and adds the ability to integrate language-specific heuristics in a modular way. The generality of the approach is kept, while the semantic understanding of a specific language is utilized to further shrink inputs. Seru is evaluated on the language CUE, which has its roots in logic programming. The results show improvements for both base reducers, Perses and Vulcan, ranging up to 20.88% and 16.94%, respectively. The combined approach of language-agnostic reducers and semantic heuristics proved effective, yet time-consuming. Program reduction is not only effective for procedural languages, but shows to be a useful tool to reduce logic programming languages as well. In future work, large language models could be used to accelerate development of heuristics for more languages.