Automatic Definition of Test Procedures via Constraint-Solving

Abstract

Testing og verifisering av digitale systemer er en nødvendig del av design av digitale kretser i industrien. Den beste måten å verifisere at et digitalt system fungerer som det skal er omfattende testing. Jobben med å lage disse testene er vanskelig og tidkrevende, så automatisering av denne jobben vil føre til økt produktivitet. Den vanligste måten denne typen automatisering gjøres i dagens industri er vha. Constrained Random Verification, som er en teknikk hvor tilfeldig stimulus blir generert innenfor visse rammer, eller "constraints". Disse rammene begrenser hvilke verdier som blir generert, å fører derfor til at testene som utføres er mer spissa inn mot systemet som skal testes ("device under test"). De løsningene som finnes på markedet i dag tvinger verifiseringsingeniører inn i en gitt arbeidsflyt, som ikke nødvendigvis stemmer overens med den flyten som brukes for øyeblikket, noe som gjør det vanskelig å ta i bruk disse løsningene.

Denne rapporten beskriver et system som er designet for å automatisk generere slike tester, men på en måte som gjør det lettere å integrere denne automatiseringen i eksisterende metoder og arbeidsflyt. Systemet skal kunne generere tilfeldige test-programmer i C/VHDL gitt en høy-nivå beskrivelse av systemet som skal testes. Dette skal gjøres med en tilpasset "constraint solver" for å generere gyldig stimulus. Noen forskjellige constraint solvers presenteres og sammenlignes.

En tilpasset prototype av en tilfeldig constraint solver basert på Monte-Carlo-metoder har blitt utviklet og implementert i C++/Prolog. Constraint solver-en tar en egenlagd "constraint tree" datastruktur som inndata, og gir ut uniformt distribuerte tilfeldige løsninger som holder seg innenfor rammene spesifisert i denne. Systemet oversetter dette constraint-treet til et Prolog-program, som deretter blir brukt til å sjekke at de tilfeldig genererte løsningene er innenfor de gitte rammene. Systemet er veldig fleksibelt, og kan bli utvidet til å løse nye problemer når de dukker opp. Denne fleksibiliteten kommer på bekostning av hastighet, så fremtidige optimaliseringer av system kan potensielt inkludere en annen constraint solver, f.eks. en av de andre som blir presentert og diskutert i denne rapporten. Resten av systemet må fullføres i et senere prosjekt.

Verification of digital systems is a vital part of the design process in the semiconductor industry. Currently, the best way to verify that a device operates according to specifications is through rigorous testing. Creating these tests is a difficult and time-consuming task, so automating the creation of these tests would lead to great gains in productivity. The main way this is done in industry is "Constrained Random Verification", where random stimulus is generated based on some given constraints. These constraints limit the values that are generated for the stimulus, ideally so that the tests are more targeted for the "device under test". Existing solutions force verification engineers to adapt a specific workflow, that might differ from the workflow currently used, making it harder to adapt these methods.

This report describes a system designed to automatically generate such tests, but in a way that can be more easily integrated into a current verification workflow. The system should be able to generate random test procedures in C/VHDL given a high level description, using a custom randomized constraint solver to generate valid test sequences. Different constraint solver approaches are presented and compared.

A custom proof-of-concept randomized constraint solver based on monte-carlo methods was developed and implemented in C++/Prolog. The constraint solver takes a custom "constraint tree" data structure as an input, and outputs uniformly distributed random solutions that adhere to these constraints. The solver translates the constraint tree into a Prolog program, which is used to check each randomly generated solution for constraint violations. The constraint solver is highly flexible, and can be extended to accommodate new problems when they appear. This flexibility comes at the cost of performance, so future optimizations to the system could potentially include a different solver approach like one of the others presented in this report. The rest of the proposed system is left for a posterior project.