Som programvaruutvecklare skriver jag mycket kod för industriprodukter. Relativt komplicerade grejer med klasser, trådar, en del designinsatser, men också några kompromisser för prestanda. Jag testar mycket och jag är trött på att testa, så jag blev intresserad av formella bevisverktyg, som Coq, Isabelle … Kan jag använda en av dessa för att formellt bevisa att min kod är felfri och klar med det? – men varje gång jag kollar på ett av dessa verktyg, går jag bort övertygad om att de är användbara för daglig programvaruteknik. Nu kan det bara vara jag, och jag letar efter tips / åsikter / idéer om det 🙂

Specifikt får jag intrycket att det skulle kräva enormt att få ett av dessa verktyg att fungera för mig investering för att korrekt definiera föremål för objekt, metoder … för det aktuella programmet. Jag undrar sedan om bevisaren inte bara skulle ta slut ånga med tanke på storleken på allt som den skulle behöva hantera. Eller kanske skulle jag behöva bli av med biverkningar (dessa bevisverktyg verkar klara riktigt bra med deklarativa språk ) och jag undrar om det skulle resultera i en ”beprövad kod” som inte kunde användas eftersom den inte skulle vara snabb eller tillräckligt liten. Dessutom har jag inte lyxen att ändra det språk jag arbetar med, det måste vara Java eller C ++: Jag kan inte berätta för min chef att jag ska koda i OXXXml från och med nu, för det är det enda språket på vilket jag kan bevisa att koden är korrekt …

Kan någon med mer erfarenhet av formella bevisverktyg kommentera? Återigen – Jag skulle ÄLSKA att använda ett formellt bevisverktyg, jag tycker att de är fantastiska, men jag har intrycket att de är i ett elfenbenstorn som jag kan ”t når från det låga diken av Java / C ++ … (PS: Jag har också LOVE Haskell, OCaml … får inte fel idé: Jag är ett fan av deklarativa språk och formella bevis, jag försöker bara ing för att se hur jag realistiskt kunde göra det användbart för programvaruteknik)

Uppdatering: Eftersom detta är ganska brett, låt oss prova följande mer specifika frågor: 1) finns det exempel på att använda provers för att bevisa korrekthet av industriella Java / C ++ – program? 2) Skulle Coq vara lämpligt för den uppgiften? 3) Om Coq är lämplig, ska jag först skriva programmet i Coq och sedan skapa C ++ / Java från Coq? 4) Kan detta tillvägagångssätt hantera trådning och prestandaoptimeringar?

Kommentarer

  • Jag förstår och uppskattar ditt problem, men jag förstår inte ’ vad denna fråga är är efter (som ett SE-inlägg). Diskussion? Erfarenhet? Inget av dem är lämpligt för SE. ” Vad kan jag göra? ” tonen får mig att känna att det här också är en för bred fråga.
  • Jag förstår … Jag håller med om att denna fråga inte formulerades tydligt. Så, låt ’ s: 1) finns det exempel på att använda provers för att bevisa riktigheten i industriella Java / C ++ – program? 2) Skulle Coq vara lämpligt för den uppgiften? 3) Om Coq är lämpligt, ska jag först skriva programmet i Coq, då ska Coq generera C ++ / Java från det? 4) Kan detta tillvägagångssätt hantera trådning och prestandaoptimeringar?
  • Så att ’ är fyra frågor. 1) är troligen bättre på Software Engineering eftersom det är osannolikt att du stöter på (många) yrkesverksamma här. 2) smakar något subjektivt, men vi kan ha människor här som kan erbjuda ett objektivt perspektiv. 3) är, såvitt jag kan säga, helt subjektivt. 4) Är en trevlig fråga för denna webbplats. Sammanfattningsvis: snälla separera dina frågor, gå till Software Engineering med den första och tänk hårt om du kan förvänta dig ett objektivt (!) Svar här (!) Innan posta 2).
  • Du ’ beskriver drömmen om formell verifiering, men vi ’ är väldigt långt ifrån vara där. AFAIK, programverifiering är en icke-rutinmässig uppgift och gäller endast mycket enkla program. Med det sagt tror jag att den här frågan är perfekt för webbplatsen, och jag skulle uppskatta någon från området som erkänner gränserna för sitt område och förklarar det senaste och begränsningarna (kanske genom att länka till någon undersökning ).
  • Problemet med att verifiera C ++ – program är att C ++ inte är ett väldefinierat språk. Jag tror inte att storskalig verifiering är möjlig förrän många delar av mjukvarusystem (OS, bibliotek, programmeringsspråk) faktiskt får en ny design för att stödja verifiering. Som känt kan du inte bara dumpa 200000 kodrader på någon och säga ” verifiera! ”. Du måste verifiera och skriva kod tillsammans, och du måste anpassa dina programmeringsvanor till det faktum att du ’ också verifierar.

Svar

Jag försöker ge ett kortfattat svar på några av dina frågor.Tänk på att detta inte är mitt forskningsområde, så en del av min information kan vara föråldrad / felaktig.

  1. Det finns många verktyg som är särskilt utformade för att formellt bevisa egenskaper av Java och C ++.

    Men jag måste göra en liten avvikelse här: vad betyder det att bevisa riktigheten i ett program? Java-typkontrollen bevisar en formell egenskap hos ett Java-program, nämligen att vissa fel, som att lägga till en float och en int, aldrig kan inträffa! Jag antar att du är intresserad av mycket starkare egenskaper, nämligen att ditt program aldrig kan komma i ett oönskat tillstånd, eller att utdata från en viss funktion överensstämmer med en viss matematisk specifikation. Kort sagt, det finns en bred gradient av vad ”att bevisa ett program korrekt” kan betyda, från enkla säkerhetsegenskaper till ett fullständigt bevis på att programmet uppfyller en detaljerad specifikation.

    Nu ska jag anta att du är intresserad av att bevisa starka egenskaper om dina program. Om du är intresserad av säkerhetsegenskaper (ditt program kan inte nå ett visst tillstånd), verkar det i allmänhet vara det bästa tillvägagångssättet är modellkontroll . Men om du vill ange beteendet hos ett Java-program är det bästa alternativet att använda ett specifikationsspråk för det språket, till exempel JML . Det finns sådana språk för att specificera beteendet hos C-program, till exempel ACSL , men jag vet inte om C ++.

  2. När du har dina specifikationer måste du bevisa att programmet överensstämmer med den specifikationen.

    För detta behöver du ett verktyg som har en formell förståelse för båda din specifikation och den operativa semantiken för ditt språk (Java eller C ++) för att uttrycka adekvat teorem , nämligen att utförandet i programmet respekterar specifikationen.

    Detta verktyg bör också göra det möjligt för dig att formulera eller generera bevis för den teoremet. Nu är båda dessa uppgifter (att specificera och bevisa) ganska svåra, så de är ofta separerade i två:

    • Ett verktyg som analyserar koden, specifikationen och genererar adekvat teorem. Som Frank nämnde är Krakatoa ett exempel på ett sådant verktyg.

    • Ett verktyg som bevisar satsen ( s), automatiskt eller interaktivt. Coq interagerar med Krakatoa på detta sätt, och det finns några kraftfulla automatiserade verktyg som Z3 som också kan användas.

    En (mindre) punkt: det finns några satser som är alltför svåra att bevisas med automatiserade metoder, och det är känt att automatiska satsprover ibland har sundhetsfel som gör dem mindre pålitliga. Detta är ett område där Coq lyser i jämförelse (men det är inte automatiskt!).

  3. Om du vill generera Ocaml-kod, skriv definitivt i Coq (Gallina) först, extrahera sedan koden. Coq är dock hemskt på att generera C ++ eller Java, om det ens är möjligt.

  4. Kan de ovanstående verktygen hantera tråd- och prestandafrågor? Förmodligen inte, prestanda och gängningsproblem hanteras bäst av specifikt utformade verktyg, eftersom de är särskilt hårda problem. Jag är inte säker på att jag har några verktyg att rekommendera här, även om Martin Hofmanns projekt PolyNI verkar intressant.

    5. ol Sammanfattningsvis: formell verifiering av ”verkliga världen” Java- och C ++ – program är ett stort och välutvecklat område, och Coq är lämplig för delar av den uppgiften. Du hittar till exempel en högnivåöversikt här .

    Kommentarer

  • Tack för det här inlägget och de referenser du lagt till. IMHO, målet för mjukvaruutvecklare är att snabbt kunna släppa system som 1) alltid ger korrekta resultat, 2) aldrig misslyckas. Jag kunde se ett regressionsproblem här, där du kanske vill bevisa att specifikationen i sig är ” bugfri ” 🙂 typ av som att försöka definiera ” sant förslag på ett språk ” med ett metaspråk och sedan behöva ett annat metaspråk för det, sedan ett annat en …
  • Problemet är att det som användaren ” vill ” vanligtvis inte uttrycks i ett formellt språk! Det finns vanligtvis inget formellt svar på frågan: ” överensstämmer denna formella specifikation med min informella idé? ”. Det är ’ möjligt att testa en formell specifikation och bevisa att den har vissa matematiska egenskaper, men i slutändan måste du relatera matematiken till den verkliga världen, vilket är en icke-formell process.
  • Ja, naturligtvis – jag insåg alltid att de formella metoderna bara kunde börja från en väldefinierad punkt.Om denna specifikation överensstämmer med de medvetna / omedvetna / oupptäckta behoven hos användarna i verkligheten är ett annat problem, som inte kan adresseras med formella metoder (men verkligen ett problem för ingenjörer).
  • En teorem är per definition en bevisat förslag. Så du menar förmodligen inte att ” bevisa satsen ”.
  • @nbro Wikipedia verkar stämma överens med dig. Mathworld definierar emellertid en sats som en proposition som ” kan demonstreras vara sant genom accepterade matematiska operationer ”. I det här fallet är det inte bara möjligt att ge bevis på satser utan det är nödvändigt för att motivera att man kallar dem så! 🙂 (detta är naturligtvis en motkämpning)

Svar

Jag vill nämna tre anmärkningsvärda applikationer formella metoder / formella verifieringsverktyg inom industrin eller icke-triviala verkliga system. Observera att jag har liten erfarenhet av detta ämne och jag lär mig dem bara från att läsa artiklar.

  1. Open source-verktyget Java Pathfinder (JPF för kort) släppt av NASA 2005 är ett system för att verifiera körbara Java-bytecode-program (se Java Pathfinder @ wiki ). Den har använts för att upptäcka inkonsekvenser i den verkställande programvaran för K9 Rover på NASA Ames.

  2. Detta dokument: Använda modellkontroll för att hitta allvarliga filsystemfel @ OSDI ”04 visar hur man använder modellkontroll för att hitta allvarliga fel i filsystem. Ett system som heter FiSC tillämpas på tre mycket använda, mycket testade filsystem: ext3, JFS och ReiserFS, och 32 allvarliga buggar hittas. Det vann Best Paper Award.

  3. Denna uppsats: Hur Amazon Web Services använder formella metoder @ CACM ”15 beskriver hur AWS tillämpar formella metoder för dess produkter som S3, DynamoDB, EBS och Intern distribuerad låshanterare. Den fokuserar på Lamports TLA + -verktyg. Förresten har Lamport intensivt använt sin egen TLA-verktygslåda. Han ger ofta en (ganska fullständig) formell verifiering i TLA av de algoritmer / teormer som han själv har föreslagit (liksom medförfattare) i bilagorna till tidningarna.

Svar

Formell verifiering är nu möjlig för program skrivna en delmängd av C ++ utformad för säkerhetskritiska inbäddade system. Se http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.ppt för en kort presentation och http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.pdf för hela papperet.

Kommentarer

  • Tack för länkarna. Åtminstone en kort översikt över deras innehåll skulle vara användbart för att skydda mot länkrot, särskilt eftersom dina länkar är till en företagswebbplats: de tenderar att omorganiseras regelbundet och dödar alla länkar till webbplatsen.

Svar

En formell specifikation av ett program är (mer eller mindre) ett program skrivet på ett annat programmeringsspråk. Som ett resultat kommer specifikationen säkert att innehålla egna buggar.

Fördelen med formell verifiering är att eftersom programmet och specifikationen är två separata implementeringar, kommer deras buggar att vara olika. Men inte alltid: en vanlig källa till buggar, förbisedda fall, kommer ofta att matcha. Formell verifiering är alltså inte ett universalmedel: det kan fortfarande sakna ett icke-trivialt antal buggar.

En nackdel med formell verifiering är att den kan påföra något som dubbelt så mycket som implementeringskostnaden, förmodligen mer (du behöver en specialist i formell specifikation, och du måste använda de mer eller mindre experimentella verktygen som medföljer det, som inte kommer att bli billigt).

Jag antar att du ställer in testfall och byggnadsställningar för att köra dem automatiskt skulle vara en bättre användning av din tid.

Kommentarer

  • fördelen med formell verifiering är att … En andra nackdel med formell verifiering är att … Detta är förvirrande.
  • Jag tror att skillnaden mellan specifikation och informell uppgift är ett problem med analys av programvarukrav och inte en programmeringsfråga.

Svar

Du ställer några olika frågor. Jag håller med om att det verkar som om formella verifieringsmetoder för industriella / kommersiella applikationer inte är så vanliga. man bör dock inse att många ”formella verifieringsprinciper” är inbyggda i kompilatorer för att avgöra programmets korrekthet! så på ett sätt, om du använder en modern kompilator använder du mycket av det senaste inom formell verifiering.

Du säger ”Jag är trött på att testa” men formell verifiering är inte riktigt ett substitut för testning. på ett sätt är det en variation på testning.

Du nämner Java.det finns många avancerade formella verifieringsmetoder inbyggda i ett java-verifieringsprogram som heter FindBugs som verkligen kan köras över stora kodbaser. Observera att det kommer att dyka upp både ”falska positiva och falska negativ” och resultaten måste granskas / analyseras av en mänsklig utvecklare. Men notera, även om det inte visar på verkliga funktionsdefekter, visar det i allmänhet ”antipatroner” som bör undvikas i kod ändå.

Du nämner inte mer din specifika applikation än ”industriell” . Formell verifiering i praktiken tenderar att bero på den specifika applikationen.

Formella verifieringstekniker verkar ofta användas i EE för att bevisa kretsens korrekthet, t.ex. i mikroprocessordesign.

Här är ett exempel på en undersökning av formella verifieringsverktyg i EE-fältet av Lars Philipson .

Kommentarer

  • Det ’ är vilseledande att säga att ” a mycket ” formell verifiering ” principer är inbyggda i kompilatorer för att bestämma programkorrekthet ”. Vad du hänvisar till är statisk typkontroll som vissa kompilatorer gör, men egenskaperna som verifierats på det sättet är ganska enkla, t.ex. undvika att lägga till ett nummer och en sträng. Detta är till hjälp, men långt ifrån vad som vanligtvis understodd av ” formell verifiering ”.
  • gjorde inte referera till statisk typkontroll specifikt, även om det är ett enkelt / vanligt exempel. imho kompilatoroptimeringstekniker, som är utbredda och avancerade, liknar ungefär formella verifieringsprinciper, eftersom de involverar avancerade tekniker för att bestämma / visa ekvivalens av optimerade programvarianter. så det verkar som om det är viktigt att undvika ” rörliga målstolpar ” här och inte anta att bara för att en kompilator gör det eller är byggt in i kompilatorn är det inte formell verifiering.
  • enades om att detta inte är en vanlig uppfattning. optimeringsteknikerna skapar ungefär en modell för programbeteende, t.ex. av en loop eller subrutin, och optimerar den modellen och genererar sedan ny kod som är bevisbart likvärdig. så några av dessa optimeringar är ganska sofistikerade när det gäller att ordna om koden & för mig använder de formella verifieringsprinciper. det verkar finnas många andra exempel på formella verifieringsmetoder i kompilatorn … den ursprungliga frågan ställde många olika frågor som många har noterat, jag försöker inte svara på alla frågorna i den.
  • av sätt det verkar finnas några formella verifieringsprinciper som också används i JRE, java runtime engine, t.ex. dynamisk optimering, etc …
  • det vill säga ” drömmer om formell verifiering ” som filmus hänvisar till ovan, imho en chimär abstraktion, och den pragmatiska / utilitaristiska / realistiska industrin erkänner den till stor del som sådan. stora kodbaser har varit kända i årtionden att i sig ha $ x $ buggar / defekter per $ y $ K-rader kod och detta kommer aldrig att förändras oavsett hur teori / teknik utvecklas, det är ett faktum av mänsklig natur. och faktiskt mänskliga matematiska satser har samma egenskaper, även om detta inte uppskattas allmänt!

Svar

En modellkontroll kan kanske vara till hjälp.

http://alloytools.org/documentation.html Legering är en modellkontroll .

En trevlig presentation som förklarar begreppet modellkontroll med Alloy: https://www.youtube.com/watch?v=FvNRlE4E9QQ

I samma verktygsfamilj kommer ”fastighetsbaserad testning”, de försöker alla hitta ett motexempel för den angivna specifikationsmodellen för din programvara.

Lämna ett svar

Din e-postadress kommer inte publiceras. Obligatoriska fält är märkta *