A framework for generating random Java programs with Prolog knowledge base validation

Compilers and \textit{pRogram Analysis and Testing tool (RAT)} are software programs whose correctness affects in a significant way the quality and the performance of the software implemented in any production sector. Compilers are primarily essential for code design and implementation in terms of run time performance, reliability and even security of an application\cite{stewart1994effects}. Thus, the process of testing compilers and \textit{RAT} tools for discovering vulnerabilities and anomalies is in the best interest for any organization whose software is a core asset. Various software and academic organizations have approached with different methodologies the problem of testing compilers. A possible technique consists of applying formal methods, which are good for expressing constraints but do not \textit{a priori} guarantee correctness \cite{clarke1996formal}. Moreover, it is difficult to formalize a model and avoid ambiguity when using formal methods. Another possible approach is random testing, or fuzzing, which refers to the process of generating random programs as benchmarks (\cite{yang2011finding}, \cite{sheridan2007practical}, \cite{mckeeman1998differential}). Random testing has emerged as an important tool for finding bugs in compilers\cite{chen2013taming}. In this work, we propose ProGen, a framework for generating random Java programs with Prolog knowledge base validation. ProGen aims at combining both previously mentioned methods; a Prolog formal specification of the Java Language Specification \cite{joy2000java} validates the work of an automated program generator. The approach of the framework is to construct an abstract syntax tree from the BNF specification of a predefined subset of the Java grammar and to validate the nodes of the AST to be consistent with the Java Language Specification. Thus, the Prolog knowledge base models some rules of the language specification, enabling the random generator to prune incorrect sub-trees of the AST and to output a compilable program. The results from the application of this framework are syntactically correct but semantically meaningless programs in a subset of Java. We have used Scala as our programming language for allowing greater testability of the application and avoiding side effects in the application. Finally, we let the user specify parameters related to the generation properties, for example, the number of classes and the primitive types, to let the application be highly customizable and configurable.

I compilatori e i software di analisi (\textit{pRogram Analysis and Testing (RAT)}) sono programmi software la cui correttezza influenza in modo significativo la qualità e le prestazioni del software implementato in qualsiasi settore di produzione. I compilatori sono primariamente essenziali per la progettazione e l'implementazione del codice in termini di prestazioni, affidabilità e sicurezza di un'applicazione \cite{stewart1994effects}. Pertanto, testare i compilatori e i software \textit{RAT} per scoprire vulnerabilità e anomalie è nell'interesse di tutte le organizzazioni il cui software è una risorsa fondamentale. Svariate organizzazioni commerciali e accademiche hanno affrontato con diverse metodologie il problema di testare i compilatori. Un approccio consiste nell’applicazione dei metodi formali, i quali si rivelano buoni per esprimere vincoli su modelli ma non garantiscono \textit{a priori} la correttezza \cite{clarke1996formal}. Inoltre, è difficile formalizzare un modello o una specifica ed evitare ambiguità nella descrizione del modello. Un altro approccio possibile è il random testing, o fuzzing, che si riferisce al processo di generazione di programmi casuali come benchmark (\cite{yang2011finding}, \cite{sheridan2007practical}, \cite{mckeeman1998differential}). I fuzzers sono emersi come uno strumento importante per trovare bug nei compilatori \cite{chen2013taming}. In questo lavoro, viene proposto ProGen, un framework per generare programmi casuali in Java attraverso la convalida con una knowledge base in Prolog. ProGen mira a combinare entrambi i metodi precedentemente menzionati; una specifica formale Prolog della Java Language Specification \cite{joy2000java} convalida il lavoro di un generatore di programmi automatici. L'approccio del framework è di costruire un albero astratto di sintassi a partire dalla specifica BNF di un sottoinsieme predefinito della grammatica Java e di convalidare i nodi dell'AST per essere coerenti con la specifica del linguaggio Java. Pertanto, la knowledge base in Prolog elabora alcune regole della specifica del linguaggio, consentendo al generatore casuale di eliminare i sotto-alberi non corretti dell'AST e di generare un programma compilabile. Il risultato dall'applicazione di questo framework è una serie di programmi in un sottoinsieme di Java sintatticamente corretti e semanticamente privi di significato. Abbiamo usato Scala come linguaggio di programmazione per consentire una maggiore testabilità dell'applicazione ed evitare il più possibile \textit{side-effects}. Infine, viene offerta all'utilizzatore del framework la possibilità di specificare alcuni parametri relativi alle proprietà di generazione, ad esempio il numero di classi e i tipi primitivi, per consentire all'applicazione di essere altamente personalizzabile e configurabile.