Många grafalgoritmer är baserade på djup-först sökning (DFS). Formaliseringarna av sådana algoritmer delar vanligtvis många gemensamma idéer. I detta dokument sammanfattar vi dessa idéer till en ram i Isabelle/HOL. Med utgångspunkt i Isabelle Raffinement Framework tillhandahåller vi stöd för en förfining baserad utveckling av DFS-baserade algoritmer, från att definiera och bevisa att den abstrakta algoritmen är korrekt, över att välja en lämplig genomförandestil (t. ex. rekursiv, svansrekursiv) för att skapa en exekverbar algoritm som använder effektiva datastrukturer. Som fallstudie verifierar vi DFS-baserade algoritmer av olika komplexitet, från en enkel cyklisk kontroll, över en modellkontroll av säkerhetsfastigheter, till komplexa algoritmer som inbäddade DFS och Tarjans SCC-algoritm.  Kategorier och ämnesdeskriptorer Algoritmer baserade på djup-första sökning (DFS) är utbredda. De sträcker sig från enkla sådana, som cyklisk kontroll och säkerhetsfastighet modell kontroll, till mer komplicerade sådana som bo DFS [3, 6, 16], och Tarjan algoritm för att beräkna uppsättningen starkt anslutna komponenter (SCC) [17]. I vår verifierade LTL-modellkontroll CAVA [4] hittar vi flera DFS-algoritmer sida vid sida: Nested DFS för t.ex. sökning, SCC-algoritmer för räknare t.ex. sökning och optimering av Büchi-automata, och grafsökning för räknare t.ex. rekonstruktion. Trots deras gemensamma bas, en hel del dubblerade ansträngningar är involverad i formalisering och verifiera dem, på grund av deras ad hoc formaliseringar av DFS. Syftet med detta dokument är att tillhandahålla ett ramverk som stöder algoritmutvecklaren i alla faser av den (raffinaderibaserade) utvecklingsprocessen, från korrekturbevis för den abstrakta algoritmen till generering av verifierad, effektivt körbar kod. Sammanfattningsvis vill vi göra verifieringen av enkla DFSBefogenhet att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt bruk eller klassrumsbruk beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än upphovsmannen måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org. CPP '15, 13-14 januari 2015, Mumbai, Indien. Upphovsrätten innehas av ägaren/författarna. Utgivningsrättigheter som är licensierade till ACM. ACM 978-4503-3300-9/15/01. .... 15.00 dollar. http://dx.doi.org/10.1145/2676724.2693165 baserade algoritmer nästan triviala, och avsevärt minska ansträngningen för komplexa algoritmer. Djup-första sökning är en av de grundläggande algoritmerna i grafteori. Den korsar grafen så länge som möjligt (dvs. tills det inte finns några fler icke-besökta efterträdare kvar) längs en gren innan den spåras tillbaka. Som nämndes i föregående avsnitt är det basen för en mängd grafer och automatiserade algoritmer. I detta dokument presenterar vi ett ramverk i Isabelle/HOL [13] för modellering och verifiering av DFS-baserade algoritmer, inklusive generering av effektivt körbar kod. Ramverket följer en parametriseringsmetod: Vi modellerar en allmän DFS-algoritm med förlängningspunkter. En verklig algoritm definieras genom att ange funktioner för att koppla in dessa förlängningspunkter. Dessa krokfunktioner åberopas när kontrollflödet når motsvarande förlängningspunkt. Kroken fungerar på en ogenomskinlig förlängning tillstånd, som är oberoende av tillståndet för bas DFS algoritm. Egenskaper hos algoritmen anges av invarianter av söktillståndet. För att etablera nya invarianter behöver man bara visa att de bevaras av krokfunktionerna. Dessutom stöder vår ram ett stegvist tillvägagångssätt, d.v.s. när en ny invariant inrättas, kan redan etablerade invarianter antas. Detta modulerar bevisen, eftersom det inte är nödvändigt att ange en stor invariant. Vårt ramverk har ett förfiningsbaserat tillvägagångssätt som utnyttjar de allmänna begreppen i Isabelle Raffinement Framework [11]: För det första är en abstrakt algoritm specificerad och bevisad korrekt. Därefter förfinas den abstrakta algoritmen mot ett effektivt genomförande, eventuellt i många steg. Förfining sker på ett korrekt och bevarande sätt, så att man till slut får ett korrekt genomförande. Den förfiningsbaserade metoden introducerar en separation av bekymmer: Den abstrakta algoritmen kan fokusera på den algoritmiska idén, medan förfiningen fokuserar på hur denna idé genomförs effektivt. Detta förenklar i hög grad bevisen, och gör verifiering av mer komplexa algoritmer hanterbar i första hand. På abstrakt nivå, vi ger en mycket detaljerad bas tillstånd, innehåller sökstacken, timing information om noderna, och uppsättningar av besökta tillbaka, kors och trädkanter. I detta detaljerade tillstånd tillhandahåller vi ett stort bibliotek med standardinvarianter, som är oberoende av utvidgningstillståndet, och därmed kan återanvändas för alla korrekta bevis. För förfining skiljer vi två ortogonala frågor: Strukturell förfining gäller algoritmens övergripande struktur. I detta syfte stöder vår ram för närvarande rekursiva och rekursiva genomföranden. Förfining av uppgifter gäller statens representation. Det gör det möjligt att förfina till ett konkret tillstånd med sitt innehåll anpassat till de specifika kraven i parametriseringen. Detta inkluderar projicering bort delar av staten som inte behövs av den faktiska algoritmen, samt representera staten genom effektiv 137
REF utökade Isabelle Raffinement Framework för att verifiera en rad DFS-algoritmer genom stegvis förfining.
A Framework for Verifying Depth-First Search Algorithms
{'venue': "CPP '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}