Runtime verificatie - Runtime verification

Runtime-verificatie is een analyse- en uitvoeringsbenadering van het computersysteem gebaseerd op het extraheren van informatie uit een actief systeem en het te gebruiken om waargenomen gedrag te detecteren en mogelijk te reageren op bepaalde eigenschappen die voldoen aan of schenden. Aan sommige zeer specifieke eigenschappen, zoals datarace en deadlock-vrijheid, wordt doorgaans door alle systemen verlangd dat ze door alle systemen worden vervuld en deze kunnen het best algoritmisch worden geïmplementeerd. Andere eigenschappen kunnen gemakkelijker worden vastgelegd als formele specificaties . Runtime-verificatiespecificaties worden doorgaans uitgedrukt in trace-predikaatformalismen, zoals eindige-toestandsmachines , reguliere expressies, contextvrije patronen, lineaire temporele logica's , enz., Of uitbreidingen hiervan. Hierdoor is een minder ad-hocbenadering mogelijk dan bij normaal testen. Elk mechanisme voor het bewaken van een uitvoerend systeem wordt echter beschouwd als runtimeverificatie, inclusief verificatie aan de hand van testorakels en referentie-implementaties. Wanneer specificaties voor formele vereisten worden verstrekt, worden monitoren daaruit gesynthetiseerd en door middel van instrumentatie in het systeem ingebracht. Runtime verificatie kan worden gebruikt voor vele doeleinden, zoals veiligheid of veiligheidsbeleid monitoring, debuggen, testen, verificatie, validatie, profilering, fout bescherming, gedragsverandering (bv herstel), enz. Runtime verificatie vermijdt de complexiteit van de traditionele formele verificatie technieken , zoals het controleren van modellen en het bewijzen van stellingen, door slechts één of enkele uitvoeringssporen te analyseren en rechtstreeks met het eigenlijke systeem te werken, waardoor relatief goed wordt geschaald en meer vertrouwen wordt gegeven in de resultaten van de analyse (omdat het vervelende en foutieve -voorliggende stap van het formeel modelleren van het systeem), ten koste van minder dekking. Bovendien kan door zijn reflecterende mogelijkheden runtime-verificatie een integraal onderdeel van het doelsysteem worden en de uitvoering ervan tijdens de implementatie bewaken en begeleiden.

Geschiedenis en context

Het controleren van formeel of informeel gespecificeerde eigenschappen ten opzichte van uitvoerende systemen of programma's is een oud onderwerp (opmerkelijke voorbeelden zijn dynamisch typen in software, of fail-safe apparaten of watchdog-timers in hardware), waarvan de precieze wortels moeilijk te achterhalen zijn. De terminologie- runtime-verificatie werd formeel geïntroduceerd als de naam van een workshop uit 2001 die gericht was op het aanpakken van problemen op de grens tussen formele verificatie en testen. Voor grote codebases blijkt het handmatig schrijven van testcases erg tijdrovend. Bovendien kunnen niet alle fouten tijdens de ontwikkeling worden gedetecteerd. Klaus Havelund en Grigore Rosu hebben in het NASA Ames Research Center vroege bijdragen geleverd aan het automatiseren van verificatie om hoge veiligheidsnormen voor ruimtevaartuigen, rovers en vliegtuigelektronica te archiveren. Ze stelden een tool voor om specificaties in temporele logica te verifiëren en om racecondities en deadlocks in Java-programma's te detecteren door afzonderlijke uitvoeringspaden te analyseren.

Momenteel worden runtime-verificatietechnieken vaak gepresenteerd met verschillende alternatieve namen, zoals runtime-monitoring, runtime-controle, runtime-reflectie, runtime-analyse, dynamische analyse , runtime / dynamische symbolische analyse, trace-analyse, logfile-analyse, enz., Allemaal verwijzend naar instanties van hetzelfde concept op hoog niveau dat op verschillende gebieden of door wetenschappers uit verschillende gemeenschappen wordt toegepast. Runtimeverificatie is nauw verwant aan andere gevestigde gebieden, zoals testen (met name op modellen gebaseerde testen) bij gebruik vóór implementatie en fouttolerante systemen bij gebruik tijdens implementatie.

Binnen het brede gebied van runtime-verificatie kunnen verschillende categorieën worden onderscheiden, zoals:

"specificatie-loze" monitoring die zich richt op een vaste set van voornamelijk gelijktijdigheidgerelateerde eigenschappen zoals atomiciteit. Het pionierswerk op dit gebied is van Savage et al. met het Eraser-algoritme
monitoring met betrekking tot temporele logische specificaties; vroege bijdragen in deze richting zijn gemaakt door Lee, Kannan en hun medewerkers, en Havelund en Rosu.

Basisbenaderingen

Overzicht van het op een monitor gebaseerde verificatieproces zoals beschreven door Havelund et al. in A Tutorial on Runtime Verification .

Het brede veld van runtime-verificatiemethoden kan worden ingedeeld in drie dimensies:

Het systeem kan worden gemonitord tijdens de uitvoering zelf (online) of na de uitvoering bijvoorbeeld in de vorm van loganalyse (offline).
De verificatiecode is geïntegreerd in het systeem (zoals gedaan in Aspect-georiënteerd programmeren ) of wordt geleverd als een externe entiteit.
De monitor kan schending of validatie van de gewenste specificatie melden.

Desalniettemin blijft het basisproces bij runtime-verificatie vergelijkbaar:

Een monitor wordt gemaakt op basis van een formele specificatie. Dit proces kan gewoonlijk automatisch worden uitgevoerd als er een equivalente automaat is voor de formele taal waarin de eigenschap is gespecificeerd. Om een reguliere expressie te transformeren kan een eindige-toestandsmachine worden gebruikt; een eigenschap in lineaire temporele logica kan worden omgezet in een Büchi-automaat (zie ook Lineaire temporele logica naar Büchi-automaat ).
Het systeem is uitgerust om gebeurtenissen met betrekking tot de uitvoeringsstatus naar de monitor te verzenden.
Het systeem wordt uitgevoerd en wordt geverifieerd door de monitor.
De monitor verifieert de ontvangen gebeurtenistracering en geeft een oordeel of aan de specificatie is voldaan. Bovendien stuurt de monitor feedback naar het systeem om eventueel foutief gedrag te corrigeren. Bij gebruik van offline monitoring kan het systeem van oorzaak geen feedback ontvangen, aangezien de verificatie op een later tijdstip plaatsvindt.

Voorbeelden

De onderstaande voorbeelden bespreken enkele eenvoudige eigenschappen die zijn overwogen, mogelijk met kleine variaties, door verschillende runtime-verificatiegroepen op het moment van schrijven (april 2011). Om ze interessanter te maken, gebruikt elke eigenschap hieronder een ander specificatieformalisme en ze zijn allemaal parametrisch. Parametrische eigenschappen zijn eigenschappen over traces die zijn gevormd met parametrische gebeurtenissen, dit zijn gebeurtenissen die gegevens aan parameters binden. Hier heeft een parametrische eigenschap de vorm waarin een specificatie in een of ander passend formalisme is die verwijst naar generieke (niet-geïnstantieerde) parametrische gebeurtenissen. De intuïtie voor dergelijke parametrische eigenschappen is dat de eigenschap uitgedrukt door moet gelden voor alle parameterinstanties die worden aangetroffen (via parametrische gebeurtenissen) in de waargenomen trace. Geen van de volgende voorbeelden is specifiek voor een bepaald runtime-verificatiesysteem, hoewel ondersteuning voor parameters uiteraard nodig is. In de volgende voorbeelden wordt de Java-syntaxis aangenomen, dus "==" is logische gelijkheid, terwijl "=" toewijzing is. Sommige methoden (bijvoorbeeld in het UnsafeEnumExample) zijn dummy-methoden, die geen deel uitmaken van de Java API, die voor de duidelijkheid worden gebruikt. ${\ displaystyle \ voor alle parameters: \ varphi}$ ${\ displaystyle \ varphi}$ ${\ displaystyle \ varphi}$ update()

HeeftNext

De eigenschap HasNext

De Java Iterator- interface vereist dat de hasNext() methode wordt aangeroepen en true retourneert voordat de next() methode wordt aangeroepen. Als dit niet het geval is, is het heel goed mogelijk dat een gebruiker "aan het einde van" een Collectie herhaalt . De afbeelding rechts toont een eindige-toestandsmachine die een mogelijke monitor definieert voor het controleren en afdwingen van deze eigenschap met runtimeverificatie. Vanuit de onbekende toestand is het altijd een fout om de next() methode aan te roepen , omdat een dergelijke bewerking onveilig kan zijn. Als hasNext() wordt aangeroepen en true retourneert , is het veilig om te bellen next() , dus de monitor gaat naar de status meer . Als de hasNext() methode echter false retourneert , zijn er geen elementen meer en gaat de monitor naar de status none . In de meer en geen staten hasNext() levert het aanroepen van de methode geen nieuwe informatie op. Het is veilig om de next() methode aan te roepen vanuit de status more , maar het wordt onbekend of er meer elementen bestaan, dus de monitor gaat opnieuw naar de oorspronkelijke onbekende status. Ten slotte resulteert het aanroepen van de next() methode vanuit de status geen in het invoeren van de foutstatus . Wat volgt is een weergave van deze eigenschap met behulp van parametrische lineaire temporele logica uit het verleden .

${\ displaystyle \ forall ~ {\ text {Iterator}} ~ i \ quad i. {\ text {next}} () ~ \ rightarrow ~ \ odot (i. {\ text {hasNext}} () == true) }$

Deze formule zegt dat elke aanroep van de next() methode onmiddellijk moet worden voorafgegaan door een aanroep van een hasNext() methode die true retourneert. De eigenschap hier is parametrisch in de Iterator i . Conceptueel betekent dit dat er voor elke mogelijke Iterator in een testprogramma één exemplaar van de monitor zal zijn, hoewel runtime-verificatiesystemen hun parametrische monitors niet op deze manier hoeven te implementeren. De monitor voor deze eigenschap zou worden ingesteld om een handler te activeren wanneer de formule wordt geschonden (equivalent wanneer de eindige-toestandsmachine de foutstatus ingaat ), wat zal optreden wanneer een van beide next() wordt aangeroepen zonder de eerste aanroep hasNext() of wanneer eerder hasNext() wordt aangeroepen next() , maar geretourneerd false .

OnveiligEnum

Code die de UnsafeEnum-eigenschap schendt

De Vector- klasse in Java heeft twee manieren om de elementen ervan te herhalen. Men kan de Iterator-interface gebruiken, zoals gezien in het vorige voorbeeld, of men kan de Enumeration- interface gebruiken. Naast de toevoeging van een verwijderingsmethode voor de Iterator-interface, is het belangrijkste verschil dat Iterator "snel faalt" en Enumeration niet. Dit betekent dat als men de Vector wijzigt (anders dan door de Iterator-verwijdermethode te gebruiken) wanneer men over de Vector itereert met behulp van een Iterator, er een ConcurrentModificationException wordt gegenereerd. Bij het gebruik van een Enumeratie is dit echter niet het geval, zoals vermeld. Dit kan resulteren in niet-deterministische resultaten van een programma omdat de Vector in een inconsistente staat wordt achtergelaten vanuit het perspectief van de opsomming. Voor oudere programma's die nog steeds de Enumeratie-interface gebruiken, kan men willen afdwingen dat Enumeraties niet worden gebruikt wanneer hun onderliggende Vector wordt gewijzigd. Het volgende parametrische regelmatige patroon kan worden gebruikt om dit gedrag af te dwingen:

Dit patroon is parametrisch in zowel de opsomming als de vector. Intuïtief, en aangezien bovenstaande runtime-verificatiesystemen hun parametrische monitors niet op deze manier hoeven te implementeren, zou men de parametrische monitor voor deze eigenschap kunnen beschouwen als het creëren en bijhouden van een niet-parametrische monitorinstantie voor elk mogelijk paar van vector en opsomming. Sommige gebeurtenissen kunnen meerdere monitoren tegelijkertijd betreffen, zoals v.update() , dus het runtime-verificatiesysteem moet ze (wederom conceptueel) naar alle geïnteresseerde monitoren sturen. Hier wordt de eigenschap gespecificeerd, zodat deze het slechte gedrag van het programma aangeeft. Deze eigenschap moet dan worden gecontroleerd op de overeenkomst met het patroon. De afbeelding rechts toont Java-code die overeenkomt met dit patroon en dus in strijd is met de eigenschap. De vector, v, wordt bijgewerkt nadat de opsomming, e, is gemaakt, en e wordt vervolgens gebruikt.

Kluis slot

De vorige twee voorbeelden tonen eigenschappen van eindige toestanden, maar eigenschappen die bij runtime-verificatie worden gebruikt, kunnen veel complexer zijn. De SafeLock-eigenschap dwingt het beleid af dat het aantal acquires en releases van een (herintredende) Lock-klasse overeenkomt binnen een bepaalde methodeaanroep. Dit staat het vrijgeven van Locks natuurlijk niet toe op andere methoden dan die waarmee ze worden verkregen, maar dit is zeer waarschijnlijk een wenselijk doel voor het geteste systeem om te bereiken. Hieronder vindt u een specificatie van deze eigenschap met behulp van een parametrisch contextvrij patroon:

Een tracering die twee schendingen van de SafeLock-eigenschap laat zien.

Het patroon specificeert uitgebalanceerde reeksen van geneste begin / einde en verwerven / vrijgeven-paren voor elke Thread en Lock ( is de lege reeks). Begin en einde verwijzen hier naar het begin en het einde van elke methode in het programma (behalve de oproepen om zichzelf te verwerven en vrij te geven). Ze zijn parametrisch in de thread omdat het nodig is om het begin en het einde van methoden te koppelen als en alleen als ze tot dezelfde thread behoren. De verwervings- en vrijgavegebeurtenissen zijn om dezelfde reden ook parametrisch in de thread. Ze zijn bovendien parametrisch in Lock omdat we de releases van het ene slot niet willen associëren met de acquisities van een ander. In het uiterste geval is het mogelijk dat er een instantie van de eigenschap zal zijn, dat wil zeggen een kopie van het contextvrije parseermechanisme, voor elke mogelijke combinatie van Thread met Lock; dit gebeurt wederom intuïtief, omdat runtime-verificatiesystemen dezelfde functionaliteit anders kunnen implementeren. Als een systeem bijvoorbeeld Threads heeft , en met Locks en , dan is het mogelijk om eigenschapinstanties te moeten onderhouden voor de paren < , >, < , >, < , >, < , >, < , > en < , >. Deze eigenschap moet worden gecontroleerd op fouten die overeenkomen met het patroon, omdat het patroon het juiste gedrag heeft gespecificeerd. De figuur rechts toont een spoor dat twee schendingen van deze eigenschap oplevert. De stappen naar beneden in de figuur vertegenwoordigen het begin van een methode, terwijl de stappen omhoog het einde zijn. De grijze pijlen in de afbeelding tonen de overeenkomst tussen bepaalde verkrijgingen en releases van hetzelfde slot. Eenvoudigheidshalve toont het tracé slechts één draad en één slot. ${\ displaystyle \ epsilon}$ ${\ displaystyle t_ {1}}$ ${\ displaystyle t_ {2}}$ ${\ displaystyle t_ {3}}$ ${\ displaystyle l_ {1}}$ ${\ displaystyle l_ {2}}$ ${\ displaystyle t_ {1}}$ ${\ displaystyle l_ {1}}$ ${\ displaystyle t_ {1}}$ ${\ displaystyle l_ {2}}$ ${\ displaystyle t_ {2}}$ ${\ displaystyle l_ {1}}$ ${\ displaystyle t_ {2}}$ ${\ displaystyle l_ {2}}$ ${\ displaystyle t_ {3}}$ ${\ displaystyle l_ {1}}$ ${\ displaystyle t_ {3}}$ ${\ displaystyle l_ {2}}$

Onderzoek uitdagingen en toepassingen

De meeste onderzoeken naar runtime-verificatie hebben betrekking op een of meer van de onderstaande onderwerpen.

Overheadkosten tijdens runtime verminderen

Het observeren van een uitvoerend systeem leidt doorgaans tot enige runtime-overhead (hardwaremonitors kunnen een uitzondering vormen). Het is belangrijk om de overhead van runtime-verificatietools zo veel mogelijk te beperken, vooral wanneer de gegenereerde monitoren met het systeem worden geïmplementeerd. Runtime-overheadreducerende technieken omvatten:

Verbeterde instrumentatie . Het extraheren van gebeurtenissen uit het uitvoerende systeem en het verzenden ervan naar monitors kan een grote runtime-overhead genereren als dit naïef wordt gedaan. Goede systeeminstrumenten zijn van cruciaal belang voor elke runtime-verificatietool, tenzij de tool zich expliciet richt op bestaande uitvoeringslogboeken. Er zijn momenteel veel instrumentatiebenaderingen in gebruik, elk met zijn voor- en nadelen, variërend van aangepaste of handmatige instrumentatie tot gespecialiseerde bibliotheken, tot compilatie in aspectgeoriënteerde talen, tot het vergroten van de virtuele machine, tot het bouwen op hardware-ondersteuning.
Combinatie met statische analyse . Een veel voorkomende combinatie van statische en dynamische analyses, vooral bij compilers, is het monitoren van alle eisen die niet statisch kunnen worden ontladen. Een tweeledige en uiteindelijk gelijkwaardige benadering wordt de norm bij runtime-verificatie, namelijk het gebruik van statische analyse om de hoeveelheid anderszins uitputtende monitoring te verminderen. Statische analyse kan zowel op het te bewaken terrein als op het te bewaken systeem worden uitgevoerd. Statische analyse van de te monitoren eigenschap kan aan het licht brengen dat bepaalde gebeurtenissen niet nodig zijn om te monitoren, dat het aanmaken van bepaalde monitoren kan worden vertraagd en dat bepaalde bestaande monitoren nooit zullen worden geactiveerd en dus als afval kunnen worden opgehaald. Statische analyse van het te monitoren systeem kan code detecteren die de monitoren nooit kan beïnvloeden. Als je bijvoorbeeld de HasNext- eigenschap hierboven bewaakt, hoef je geen codegedeelten te instrumenteren waarbij elke aanroep i.next() onmiddellijk op een pad wordt voorafgegaan door een aanroep i.hasnext() die true retourneert (zichtbaar in de control-flow-grafiek).
Efficiënte generatie en beheer van monitoren . Bij het bewaken van parametrische eigenschappen zoals die in de bovenstaande voorbeelden, moet het bewakingssysteem de status van de bewaakte eigenschap bijhouden met betrekking tot elke parameterinstantie. Het aantal van dergelijke gevallen is theoretisch onbegrensd en neigt in de praktijk enorm te zijn. Een belangrijke onderzoeksuitdaging is hoe geobserveerde gebeurtenissen efficiënt kunnen worden verzonden naar precies die instanties die ze nodig hebben. Een verwante uitdaging is hoe het aantal van dergelijke instanties klein kan worden gehouden (zodat de verzending sneller verloopt), of met andere woorden, hoe u het creëren van onnodige instanties zo lang mogelijk kunt vermijden en, dubbel, hoe u reeds aangemaakte instanties zo snel mogelijk kunt verwijderen. ze worden overbodig. Ten slotte generaliseren parametrische monitoringalgoritmen doorgaans vergelijkbare algoritmen voor het genereren van niet-parametrische monitoren. De kwaliteit van de gegenereerde niet-parametrische monitors bepaalt dus de kwaliteit van de resulterende parametrische monitors. In tegenstelling tot andere verificatiebenaderingen (bijv. Modelcontrole), is het aantal toestanden of de grootte van de gegenereerde monitor echter minder belangrijk bij runtime-verificatie; in feite kunnen sommige monitoren oneindig veel toestanden hebben, zoals die voor de SafeLock- eigenschap hierboven, hoewel er op elk moment in de tijd slechts een eindig aantal toestanden kan zijn opgetreden. Wat belangrijk is, is hoe efficiënt de monitor van een toestand naar zijn volgende toestand overgaat wanneer hij een gebeurtenis ontvangt van het uitvoerende systeem.

Eigenschappen specificeren

Een van de belangrijkste praktische belemmeringen van alle formele benaderingen is dat hun gebruikers terughoudend zijn in, of niet weten en niet willen leren hoe ze specificaties moeten lezen of schrijven. In sommige gevallen zijn de specificaties impliciet, zoals die voor deadlocks en dataraces, maar in de meeste gevallen moeten ze worden geproduceerd. Een bijkomend ongemak, vooral in de context van runtime-verificatie, is dat veel bestaande specificatietalen niet expressief genoeg zijn om de beoogde eigenschappen vast te leggen.

Betere formalismen. In de runtime-verificatiegemeenschap is een aanzienlijke hoeveelheid werk gestoken in het ontwerpen van specificatieformalismen die beter passen bij de gewenste toepassingsdomeinen voor runtime-verificatie dan de conventionele specificatieformalismen. Sommige hiervan bestaan uit kleine of geen syntactische veranderingen in de conventionele formalismen, maar alleen uit veranderingen in hun semantiek (bijv. Eindige trace versus oneindige trace semantiek, etc.) en hun implementatie (geoptimaliseerde eindige-toestandsmachines in plaats van Büchi-automaten, enz. .). Anderen breiden bestaande formalismen uit met functies die geschikt zijn voor runtime-verificatie, maar misschien niet gemakkelijk voor andere verificatiebenaderingen, zoals het toevoegen van parameters, zoals te zien is in de bovenstaande voorbeelden. Ten slotte zijn er specificatieformalismen die specifiek zijn ontworpen voor runtime-verificatie, waarbij wordt geprobeerd hun best te doen voor dit domein en weinig om andere toepassingsdomeinen geeft. Het ontwerpen van universeel betere of domeinspecifiek betere specificatieformalismen voor runtime-verificatie is en blijft een van de belangrijkste onderzoeksuitdagingen.
Kwantitatieve eigenschappen. Vergeleken met andere verificatiebenaderingen kan runtime-verificatie werken op concrete waarden van systeemstatusvariabelen, waardoor het mogelijk wordt statistische informatie over de uitvoering van het programma te verzamelen en deze informatie te gebruiken om complexe kwantitatieve eigenschappen te beoordelen. Er zijn meer expressieve eigendomstalen nodig die ons in staat stellen deze mogelijkheid volledig te benutten.
Betere interfaces. Het lezen en schrijven van eigenschappenspecificaties is niet eenvoudig voor niet-experts. Zelfs experts staren vaak minutenlang naar relatief kleine temporele logische formules (vooral wanneer ze "tot" -operatoren hebben genest). Een belangrijk onderzoeksgebied is het ontwikkelen van krachtige gebruikersinterfaces voor verschillende specificatieformalismen waarmee gebruikers eigenschappen gemakkelijker kunnen begrijpen, schrijven en misschien zelfs visualiseren.
Mijnbouwspecificaties. Welke toolondersteuning er ook beschikbaar is om gebruikers te helpen bij het opstellen van specificaties, ze zullen bijna altijd meer tevreden zijn als ze helemaal geen specificaties hoeven te schrijven, vooral als ze triviaal zijn. Gelukkig zijn er tal van programma's die zogenaamd correct gebruik maken van de acties / gebeurtenissen waarover men eigenschappen wil hebben. Is dat het geval, dan is het denkbaar dat men van die juiste programma's gebruik wil maken door daar automatisch de gewenste eigenschappen van te leren. Zelfs als de algehele kwaliteit van de automatisch gedolven specificaties naar verwachting lager zal zijn dan die van handmatig geproduceerde specificaties, kunnen ze dienen als startpunt voor de laatste of als basis voor automatische runtime-verificatietools die specifiek gericht zijn op het vinden van bugs (waar een slechte specificatie verandert in valse positieven of negatieven, vaak acceptabel tijdens het testen).

Uitvoeringsmodellen en voorspellende analyse

Het vermogen van een runtime-verificateur om fouten te detecteren, hangt strikt af van zijn vermogen om uitvoeringssporen te analyseren. Wanneer de monitoren met het systeem worden ingezet, is de instrumentatie doorgaans minimaal en zijn de uitvoeringssporen zo eenvoudig mogelijk om de runtime-overhead laag te houden. Wanneer runtime-verificatie wordt gebruikt voor testen, kan men zich uitgebreidere instrumenten veroorloven die gebeurtenissen aanvullen met belangrijke systeeminformatie die door de monitors kan worden gebruikt om meer verfijnde modellen van het uitvoerende systeem te construeren en dus te analyseren. Door bijvoorbeeld gebeurtenissen aan te vullen met vectorklokinformatie en met gegevens en informatie over de besturingsstroom, kunnen de monitoren een oorzakelijk model construeren van het actieve systeem waarin de waargenomen uitvoering slechts één mogelijk geval was. Elke andere permutatie van gebeurtenissen die consistent is met het model, is een haalbare uitvoering van het systeem, die zou kunnen gebeuren onder een andere thread-interleaving. Door eigendomsovertredingen in dergelijke afgeleide uitvoeringen op te sporen (door ze te bewaken), kan de monitor fouten voorspellen die niet zijn opgetreden bij de waargenomen uitvoering, maar die wel kunnen voorkomen bij een andere uitvoering van hetzelfde systeem. Een belangrijke onderzoeksuitdaging is om uit executiesporen modellen te extraheren die zoveel mogelijk andere executiesporen bevatten.

Gedragswijziging

In tegenstelling tot testen of uitgebreide verificatie, houdt runtime-verificatie de belofte in dat het systeem kan herstellen van gedetecteerde overtredingen, door middel van herconfiguratie, micro-resets of door fijnere interventiemechanismen, ook wel afstemming of besturing genoemd. Implementatie van deze technieken binnen het rigoureuze kader van runtime-verificatie brengt extra uitdagingen met zich mee.

Specificatie van acties. Men moet de wijziging die moet worden uitgevoerd op een voldoende abstracte manier specificeren, waarbij de gebruiker geen irrelevante implementatiedetails hoeft te kennen. Bovendien moet worden gespecificeerd wanneer een dergelijke wijziging kan plaatsvinden om de integriteit van het systeem te behouden.
Redeneren over interventie-effecten. Het is belangrijk om te weten dat een interventie de situatie verbetert, of in ieder geval niet verergert.
Actie-interfaces. Net als bij de instrumentatie voor monitoring, moeten we het systeem in staat stellen actie-aanroepen te ontvangen. Aanroepmechanismen zullen noodzakelijkerwijs afhankelijk zijn van de implementatiedetails van het systeem. Op specificatieniveau moeten we de gebruiker echter een declaratieve manier bieden om feedback aan het systeem te geven door te specificeren welke acties onder welke omstandigheden moeten worden uitgevoerd.

Gerelateerd werk

Aspect Oriented Programming

Onderzoekers in Runtime Verification erkenden het potentieel van het gebruik van Aspect-georiënteerd programmeren als een techniek om programma-instrumentatie op een modulaire manier te definiëren. Aspect-georiënteerd programmeren (AOP) bevordert over het algemeen de modularisering van transversale problemen. Runtime Verification is natuurlijk zo'n zorg en kan daarom profiteren van bepaalde eigenschappen van AOP. Aspect-georiënteerde monitordefinities zijn grotendeels declaratief en zijn daarom vaak eenvoudiger te beredeneren dan instrumentatie die wordt uitgedrukt door een programmatransformatie geschreven in een imperatieve programmeertaal. Verder kunnen statische analyses gemakkelijker redeneren over monitoringaspecten dan over andere vormen van programma-instrumentatie, aangezien alle instrumentatie ondergebracht is in één aspect. Veel huidige runtime-verificatietools zijn daarom gebouwd in de vorm van specificatiecompilers, die een expressieve specificatie op hoog niveau als invoer gebruiken en als uitvoercode produceren die is geschreven in een Aspect-georiënteerde programmeertaal (zoals AspectJ ).

Combinatie met formele verificatie

Runtime-verificatie kan, indien gebruikt in combinatie met aantoonbaar correcte herstelcode, een infrastructuur van onschatbare waarde bieden voor programmaverificatie, die de complexiteit van deze laatste aanzienlijk kan verminderen. Het formeel verifiëren van het heap-sort-algoritme is bijvoorbeeld een grote uitdaging. Een minder uitdagende techniek om het te verifiëren, is om de te sorteren output te controleren (een lineaire complexiteitsmonitor) en, indien niet gesorteerd, deze te sorteren met behulp van een gemakkelijk verifieerbare procedure, bijvoorbeeld invoegsortering. Het resulterende sorteerprogramma is nu gemakkelijker verifieerbaar, het enige dat van heap-sort vereist is, is dat het de oorspronkelijke elementen die als een multiset worden beschouwd niet vernietigt, wat veel gemakkelijker te bewijzen is. Vanuit de andere richting bekeken, kan men formele verificatie gebruiken om de overhead van runtime-verificatie te verminderen, zoals hierboven al vermeld voor statische analyse in plaats van formele verificatie. Men kan inderdaad beginnen met een volledig geverifieerd, maar waarschijnlijk traag programma. Vervolgens kan men formele verificatie (of statische analyse) gebruiken om monitoren te ontladen, op dezelfde manier als een compiler statische analyse gebruikt om runtime-controles van typecorrectheid of geheugenveiligheid te ontladen .

Dekking vergroten

In vergelijking met de meer traditionele verificatiebenaderingen is een direct nadeel van runtime-verificatie de verminderde dekking. Dit is niet problematisch wanneer de runtime-monitors met het systeem worden geïmplementeerd (samen met de juiste herstelcode die moet worden uitgevoerd wanneer de eigenschap wordt geschonden), maar het kan de effectiviteit van runtime-verificatie beperken wanneer deze wordt gebruikt om fouten in systemen te vinden. Technieken om de dekking van runtimeverificatie te vergroten voor foutdetectiedoeleinden zijn onder meer:

Input generatie. Het is algemeen bekend dat het genereren van een goede set aan inputs (waarden van programma-invoervariabelen, systeemoproepwaarden, threadschema's, enz.) De effectiviteit van het testen enorm kan verhogen. Dat geldt ook voor runtime-verificatie die wordt gebruikt voor foutdetectie, maar naast het gebruik van de programmacode om het inputgeneratieproces aan te sturen, kan men bij runtime-verificatie ook de eigenschapsspecificaties gebruiken, indien beschikbaar, en kan men ook monitoringtechnieken gebruiken om gewenst gedrag. Door dit gebruik van runtime-verificatie is het nauw verwant aan op modellen gebaseerde tests, hoewel de specificaties voor runtime-verificatie doorgaans algemeen doel zijn en niet noodzakelijkerwijs zijn ontworpen om testredenen. Bedenk bijvoorbeeld dat men de bovenstaande UnsafeEnum- eigenschap voor algemeen gebruik wil testen . In plaats van alleen de bovengenoemde monitor te genereren om de systeemuitvoering passief te observeren, kan men een slimmere monitor genereren die de thread bevriest die probeert de tweede e.nextElement () -gebeurtenis te genereren (net voordat deze deze genereert), waardoor de andere threads kunnen worden uitgevoerd in de hoop dat een van hen een v.update () -gebeurtenis genereert , in welk geval er een fout is gevonden.
Dynamische symbolische uitvoering. Bij symbolische uitvoering worden programma's symbolisch uitgevoerd en bewaakt, dat wil zeggen zonder concrete input. Een symbolische uitvoering van het systeem kan betrekking hebben op een groot aantal concrete inputs. Kant-en-klare technieken voor het oplossen van beperkingen of het controleren van de geschiktheid worden vaak gebruikt om symbolische executies aan te sturen of om systematisch de ruimte ervan te verkennen. Als de onderliggende tevredenheidscheckers een keuzepunt niet aankunnen, kan er een concrete input worden gegenereerd om dat punt te passeren; deze combinatie van conc rete en symb olische uitvoering wordt ook wel concolische uitvoering genoemd.

Languages

In other projects