The automated construction of computer programs from formal behavioral specifications has been a subject of active interest in the software engineering community for the last forty years. Several approaches for constructing programs from variants of temporal logics have been studied, and practical tools for generating programs from high-level specification languages such as UML have been implemented. However, little effort has been directed towards the automated synthesis of correct-by-construction software by leveraging complementary strengths of formal verification and modern machine learning techniques. Machine learning methods are quite adept at learning linear and nonlinear relations between two or more variables of interest to a data scientist. While these methods are scalable and can learn models with millions of data points with ease, they suffer from learning errors and may not necessarily learn the concept class being taught. On the other hand, formal verification methods can algorithmically decide if a candidate program satisfies the specifications that constraint the set of behaviors expected from the program. However, formal verification cannot generate the correct program from the specification itself. By combining the strengths of machine learning and formal verification, it is feasible to algorithmically synthesize programs from various flavors of formal and informal specifications, including logics, input-output examples, and a library of program templates. Conceptually, the synthesis technique leverages inductive learning techniques as a student generalizing from sets of behaviors to candidate programs while deductive formal methods serve as a teacher rectifying generalizations to slowly guide the automated synthesis technique towards provably correct programs. (Machine Learning for Automated Synthesis of Complex Software, Susmit Jha)
Last date updated on April, 2024