Grey-box learning of Interfaces for Refactoring Legacy Software (GIRLS)

Project coordinator: Frits Vaandrager; this project will start in 2019.

Scientific Summary

Beyond a certain point, further use and development of legacy code is no longer feasible and reengineering becomes unavoidable. From a business perspective this is a nightmare, as it is costly and highly risky. How to ensure that the reengineered software has the same functionality, given our poor understanding of the existing software? There is a desperate need for automatic tools that support reverse engineering of legacy code.

The GIRLS project explores the use of model learning to address this problem. Model learning aims to construct state diagram models of software and hardware systems by providing inputs and observing outputs. It is emerging as a highly effective bug-finding technique, with applications in areas such as banking cards and network protocols. By constructing state diagrams models of legacy software and a refactored implementation, model learning can be used to check whether legacy and refactored software have the same behavior.

GIRLS addresses the fundamental research problem to make model learning algorithms more scalable, and applicable to a larger class of systems involving data and timing. The project will study combinations of SL*, a state-of-the-art black-box learning algorithm for register automata, with dynamic taint analysis. Moreover, the project will extend existing learning algorithms for untimed systems to Mealy machines with timers, a class of models that is sufficiently expressive to describe timing behavior of many embedded applications, but also sufficiently simple to be efficiently learnable. The developed learning algorithms will be evaluated on legacy software case studies provided by the Dutch high-tech industry.

Lekensamenvatting

Onze moderne samenleving draait op honderden miljarden regels software. Veel hiervan is legacy software: code die een vitale rol speelt binnen een toepassing, maar waarvan we eigenlijk niet meer weten wat we er mee aan moeten. Legacy software is gebaseerd op verouderde technologie, documentatie ontbreekt of is uiterst beperkt, de oorspronkelijke ontwikkelaars zijn er niet meer, en gedurende vele jaren zijn nieuwe toeters en bellen toegevoegd door steeds weer andere programmeurs op basis van onvolledige informatie. ICT systemen van bijvoorbeeld de belastingdienst, banken, ziekenhuizen en high-tech bedrijven bevatten allemaal cruciale stukken legacy software van minimaal 30 jaar oud.

Vanaf een zeker moment is het niet langer haalbaar om legacy code nog langer te gebruiken en wordt herontwerp onvermijdelijk. Vanuit een bedrijfsmatig perspectief is dit een nachtmerrie, aangezien enorm veel geld uitgegeven moet worden zonder dat een product of dienst er beter op wordt. Herontwerp is ook buitengewoon risicovol. Want hoe kun je garanderen dat de herontworpen software goed werkt wanneer je werking van de oorspronkelijke legacy software niet eens begrijpt? Bedrijven zijn daarom wanhopig op zoek naar methoden en gereedschappen die kunnen helpen bij het herontwerpen van legacy software.

Het basisidee van het GIRLS project is dat we algoritmen willen ontwikkelen waarmee computers geheel automatisch wiskundig modellen (toestandsdiagrammen) kunnen leren die beschrijven hoe software componenten zich gedragen, simpelweg door te experimenteren en te kijken naar het observeerbare gedrag: hoe reageert een component op invoer A, hoe reageert hij op invoer B, enz. Wanneer we eenmaal een model hebben geleerd van een legacy component kunnen we dit gebruiken bij het herontwerp, bijvoorbeeld door het te vergelijken met een model van de herontworpen software, en zo garanderen dat de oude en de nieuwe software zich precies hetzelfde gedragen. Door enorme vooruitgang op het gebied van machine learning gedurende de laatste jaren, hebben we inmiddels beschikking over krachtige leer-algoritmen, waarmee bijvoorbeeld veel fouten zijn opgespoord in implementaties van Internet protocollen zoals TCP, TLS en SSH. Leeralgoritmen zijn er ook in geslaagd om fouten te vinden in herontwerpen van legacy componenten van embedded control software, maar bestaande technologie schaalt nog niet goed naar meer complexe software, en is ook nog niet goed toepasbaar op systemen waarbij data en de timing van gebeurtenissen een rol spelen in het gedrag.

Het GIRLS project doet fundamenteel onderzoek om de schaalbaarheid en toepasbaarheid van deze machine learning technieken te verbeteren. Een eerste idee is om bestaande leeralgoritmen te combineren met de techniek van dynamic taint analysis. Hierbij wordt een invoerwaarden voor de legacy component als het ware gekleurd, waardoor je precies kunt volgen wat de software allemaal doet met deze data. Deze extra informatie maakt het veel eenvoudiger om een model te leren. Het tweede idee is om bestaande leertheorie te generaliseren naar een klasse van Mealy machines met timers. Deze modellen zijn enerzijds voldoende krachtig om het real-time gedrag van veel embedded software componenten te beschrijven, maar lijken anderzijds net voldoende simpel te zijn om volautomatisch en efficiënt te kunnen leren.

Funding

NWO project 612.001.852, Physical Sciences TOP-Grants for curiosity-driven research 2017-2018, module 1

Proposal

Proposal (pdf)

Press

Nieuwsbericht Radboud Universiteit
News item Radboud University