Ohjelmistoinsinöörinä kirjoitan paljon koodia teollisuustuotteille. Suhteellisen monimutkainen juttu, jossa on luokkia, ketjuja, joitain suunnittelutyötä, mutta myös joitain kompromisseja suorituskyvyn suhteen. Teen paljon testejä ja olen kyllästynyt testaamiseen, joten kiinnostuin muodollisista todistustyökaluista, kuten Coq, Isabelle … Voinko käyttää jotain näistä todistaakseni muodollisesti, että koodini on virheetön ja valmis sen kanssa? – mutta joka kerta kun tutustun johonkin näistä työkaluista, kävelen pois vakuuttumattomana siitä, että ne ovat käyttökelpoisia jokapäiväisessä ohjelmistotuotannossa. Se voisin olla vain minä, ja etsin siitä vihjeitä / mielipiteitä / ideoita 🙂

Erityisesti minusta tuntuu, että yhden näistä työkaluista saaminen toimisi minulle investoinnit, jotta määriteltäisiin oikein sananlaskijalle tarkasteltavan ohjelman tavoitteet, menetelmät … Sitten ihmettelen, eikö sananlaskija vain loppuisi höyrystä, kun otetaan huomioon kaiken, mitä sen on käsiteltävä. Tai ehkä minun pitäisi päästä eroon sivuvaikutuksista (nuo sananlaskutyökalut näyttävät pärjäävän hyvin deklaratiivisten kielten kanssa) ), ja ihmettelen, johtaako tämä ”todistettuun koodiin”, jota ei voitu käyttää, koska se ei olisi tarpeeksi nopea tai tarpeeksi pieni. Minulla ei ole myöskään ylellisyyttä vaihtaa kieltä, jolla työskentelen, sen on oltava Java tai C ++: En voi kertoa pomolleni, että aion koodata tästä lähtien OXXXml: ssä, koska se on ainoa kieli, jolla voin todistaa koodin oikeellisuuden …

Voisiko joku, jolla on enemmän kokemusta muodollisista todistustyökaluista, kommentoida? Jälleen – haluan LOVE käyttää virallista sananlaskutyökalua, mielestäni ne ovat hienoja, mutta minusta tuntuu, että he ovat norsunluun tornissa, että voin ”älä päästä Java / C ++: n alhaisesta ojasta … (PS: Minä myös LOVE Haskell, OCaml … älä saa väärää ajatusta: Olen julistavien kielten ja muodollisten fani todiste, yritän vain nähdäksesi kuinka voisin tehdä siitä realistisesti ohjelmistotuotannolle)

Päivitys: Koska tämä on melko laaja, kokeilemme seuraavia tarkempia kysymyksiä: 1) onko olemassa esimerkkejä todistajien käyttämisestä oikeellisuuden osoittamiseksi teollisuuden Java / C ++ -ohjelmista? 2) Sopisiko Coq tähän tehtävään? 3) Jos Coq on sopiva, pitäisikö minun kirjoittaa ohjelma ensin Coq: iin ja sitten generoida C ++ / Java Coq: sta? 4) Voisiko tämä lähestymistapa käsitellä ketjuttamista ja suorituskyvyn optimointia?

kommentit

  • Saan ja arvostan ongelmasi, mutta en ymmärrä, mitä tämä kysymys ’ on jälkeen (SE-virtana). Keskustelu? Kokea? Kumpikaan ei sovi SE: lle. ” Mitä voin tehdä? ” -sävy saa minut tuntemaan myös tämän olevan liian laaja kysymys.
  • Katson … Olen samaa mieltä siitä, että tätä kysymystä ei muotoiltu selkeästi. Joten sanokaat ’ s: 1) Onko olemassa esimerkkejä kokeiden käyttämisestä teollisten Java / C ++ -ohjelmien oikeellisuuden osoittamiseksi? 2) Sopisiko Coq tähän tehtävään? 3) Jos Coq on sopiva, pitäisikö minun kirjoittaa ohjelma ensin Coq: iin, sitten pitäisikö Coqin luoda siitä C ++ / Java? 4) Voisiko tämä lähestymistapa selviytyä ketjutuksesta ja suorituskyvyn optimoinnista?
  • Joten ’ on sitten neljä kysymystä. 1) on todennäköisesti parempi kuin ohjelmistotuotannossa , koska tuskin törmäät täällä (moniin) alan ammattilaisiin. 2) maistuu jonkin verran subjektiiviselta, mutta meillä saattaa olla ihmisiä, jotka voivat tarjota objektiivisen näkökulman. 3) on, sikäli kuin voin kertoa, täysin subjektiivinen. 4) Onko mukavia kysymyksiä tälle sivustolle. Yhteenvetona: erota kysymyksesi, siirry ensin ohjelmistotuotantoon ja mieti kovasti, voitko odottaa objektiivista (!) Vastausta täällä (!) Ennen lähettäminen 2).
  • Sinä ’ kuvaat uudestaan muodollisen todentamisen unta, mutta me ’ olemme hyvin kaukana olla siellä. AFAIK, ohjelman todentaminen ei ole rutiininomainen tehtävä, ja se koskee vain hyvin yksinkertaisia ohjelmia. Uskon kuitenkin, että tämä kysymys on paikalla sivustolla, ja arvostan sitä, että joku alueesta myöntää alansa rajat selittäen huipputekniikkaa ja rajoituksia (ehkä linkittämällä johonkin kyselyyn) ).
  • C ++ -ohjelmien todentamisen ongelmana on, että C ++ ei ole tarkalleen määritelty kieli. En usko, että laajamittainen todentaminen on mahdollista, ennen kuin monet ohjelmistojärjestelmien osat (käyttöjärjestelmä, kirjastot, ohjelmointikielet) todella suunnitellaan uudelleen tukemaan vahvistusta. Kuten tiedetään, et voi vain kaataa 200000 koodiriviä jollekin ja sanoa ” vahvista! ”. Sinun on vahvistettava ja kirjoitettava koodi yhdessä, ja sinun on mukautettava ohjelmointitottumuksesi siihen, että ’ myös vahvistat.

Vastaus

Yritän vastata ytimekkäästi joihinkin kysymyksiisi.Muista, että tämä ei ole yksinomaan tutkimusalueeni, joten osa tiedoistani saattaa olla vanhentunut / virheellinen.

  1. On olemassa monia työkaluja, jotka on erityisesti suunniteltu todistamaan ominaisuudet virallisesti Java ja C ++.

    Minun on kuitenkin tehtävä pieni poikkeama tässä: mitä tarkoittaa todistaa ohjelman oikeellisuuden? Java-tyypin tarkistus osoittaa Java-ohjelman muodollisen ominaisuuden, nimittäin että tietyt virheet, kuten float ja int lisääminen, eivät voi koskaan tapahtua! Luulen, että olet kiinnostunut paljon vahvemmista ominaisuuksista, nimittäin siitä, että ohjelmasi ei voi koskaan siirtyä ei-toivottuun tilaan tai että tietyn funktion lähtö vastaa tiettyä matemaattista eritelmää. Lyhyesti sanottuna on olemassa suuri gradientti siitä, mitä ”ohjelman oikeaksi todistaminen” voi tarkoittaa, yksinkertaisista suojausominaisuuksista täydelliseen todisteeseen siitä, että ohjelma täyttää yksityiskohtaiset eritelmät.

    Oletan, että olet kiinnostunut todistamaan ohjelmiesi vahvat ominaisuudet. Jos olet kiinnostunut tietoturvaominaisuuksista (ohjelmasi ei voi saavuttaa tiettyä tilaa), yleisesti ottaen näyttää siltä, että paras tapa on mallintarkistus . Jos kuitenkin haluat määrittää Java-ohjelman käyttäytymisen täysin, on parasta käyttää kyseisen kielen määrityskieliä, esimerkiksi JML . C-ohjelmien käyttäytymisen määrittämiseen on olemassa sellaisia kieliä, esimerkiksi ACSL , mutta en tiedä C ++.

  2. Kun olet saanut määritykset, sinun on todistettava, että ohjelma noudattaa kyseistä määritystä.

    Tätä varten tarvitset työkalun, jolla on muodollinen käsitys molemmista määrittelysi ja kielesi operatiivinen semantiikka (Java tai C ++) ilmaisemaan riittävyyslause , nimittäin että suoritus ohjelmasta noudattaa määrittelyä.

    Tämän työkalun avulla voit myös muotoilla tai luoda todisteen kyseisestä lauseesta. Nyt molemmat tehtävät (määritteleminen ja todentaminen) ovat melko vaikeita, joten ne erotetaan usein kahtia:

    • Yksi työkalu, joka jäsentää koodin, määrityksen ja muodostaa riittävyyslauseen. Kuten Frank mainitsi, Krakatoa on esimerkki tällaisesta työkalusta.

    • Yksi lause, joka todistaa lauseen ( s) automaattisesti tai vuorovaikutteisesti. Coq on vuorovaikutuksessa Krakatoa kanssa tällä tavalla, ja on olemassa joitain tehokkaita automatisoituja työkaluja, kuten Z3 , joita voidaan myös käyttää.

    Yksi (pieni) kohta: on joitain lauseita, joita on liian vaikea todistaa automaattisilla menetelmillä, ja automaattisilla lauseiden todistajilla tiedetään toisinaan olevan vikoja, jotka tekevät niistä vähemmän luotettavia. Tämä on alue, jolla Coq loistaa vertailussa (mutta se ei ole automaattista!).

  3. Jos haluat luoda Ocaml-koodin, kirjoita ehdottomasti ensin Coq (Gallina), sitten pura koodi. Coq on kuitenkin kauhea luomaan C ++ tai Java, jos se on edes mahdollista.

  4. Voivatko yllä olevat työkalut käsitellä ketjutusta ja suorituskykyä? Luultavasti ei, suorituskykyyn ja kierteitykseen liittyvät ongelmat hoidetaan parhaiten erityisesti suunnitelluilla työkaluilla, koska ne ovat erityisen vaikeita ongelmia. En ole varma, onko minulla mitään suositeltavia työkaluja, vaikka Martin Hofmannin PolyNI -projekti vaikuttaa mielenkiintoiselta.

Yhteenvetona: ”todellisen maailman” Java- ja C ++ -ohjelmien virallinen todentaminen on suuri ja hyvin kehittynyt ala, ja Coq soveltuu osiin tätä tehtävää. Löydät esimerkiksi korkean tason yleiskatsauksen täältä .

Kommentit

  • Kiitos tästä viestistä ja lisäämistäsi viitteistä. IMHO, ohjelmistosuunnittelijoiden tavoitteena on pystyä vapauttamaan nopeasti järjestelmät, jotka 1) tuottavat aina oikeat tulokset, 2) eivät koskaan vikaudu. Voisin nähdä regressio-ongelman täällä, jossa haluat ehkä todistaa, että erittely itse on ” virhevapaa ” 🙂 kuin yrittää määritellä ” kielen todellinen ehdotus ” metakielellä ja tarvitsee sitten toinen metakieli, sitten toinen yksi …
  • Ongelmana on, että mitä käyttäjä ” haluaa ”, ei yleensä ilmaista muodollisessa muodossa Kieli! muodollista vastausta kysymykseen ei yleensä ole: ” vastaako tämä virallinen eritelmä epävirallista ajatustani? ”. ’ on mahdollista testata muodollinen eritelmä ja todistaa, että sillä on tiettyjä matemaattisia ominaisuuksia, mutta viime kädessä sinun on yhdistettävä matematiikka todelliseen maailmaan, mikä on epävirallinen prosessi.
  • Kyllä tietysti – tajusin aina, että muodolliset menetelmät voivat alkaa vain hyvin määritellystä pisteestä.Jos kyseinen eritelmä vastaa tosielämän käyttäjien tietoisia / tiedostamattomia / tuntemattomia tarpeita, se on toinen ongelma, jota ei voida käsitellä muodollisilla menetelmillä (mutta varmasti ongelma insinööreille).
  • Lause on määritelmän mukaan todistettu ehdotus. Joten et todennäköisesti tarkoita ” todistavan lause ”.
  • @nbro Wikipedia näyttää olevan samaa mieltä kanssasi. Mathworld määrittelee lauseen kuitenkin lauseeksi, jonka ” voidaan osoittaa olevan totta hyväksytyillä matemaattisilla operaatioilla ”. Tässä tapauksessa todisteiden antaminen lauseista ei ole vain mahdollista, vaan myös välttämätöntä, jotta voidaan kutsua niitä niin! 🙂 (tämä on tietysti vasta-aine)

Vastaa

Haluan mainita kolme merkittävää sovellusta muodollisten menetelmien / muodollisten todentamisvälineiden käyttö teollisuudessa tai ei-triviaalisissa todellisissa järjestelmissä. Huomaa, että minulla on vähän kokemusta tästä aiheesta ja opin ne vain lukemalla papereita.

  1. Avoimen lähdekoodin työkalu Java Pathfinder (lyhyt JPF) , jonka NASA julkaisi vuonna 2005 on järjestelmä, jolla todennetaan suoritettavat Java-tavuohjelmakoodit (katso Java Pathfinder @ wiki ). Sitä on käytetty epäjohdonmukaisuuksien havaitsemiseen NASA Amesin K9 Roverin johto-ohjelmistossa.

  2. iv Tämä artikkeli: Mallintarkastuksen käyttäminen vakavien tiedostojärjestelmävirheiden etsimiseen @ OSDI ”04 näyttää kuinka käyttää mallintarkistus vakavien virheiden löytämiseksi tiedostojärjestelmistä. FiSC-järjestelmää käytetään kolmelle laajasti käytetylle, erittäin testatulle tiedostojärjestelmälle: ext3, JFS ja ReiserFS, ja löydetään 32 vakavaa virhettä. Se voitti parhaan paperin palkinnon.

  3. Tämä artikkeli: Kuinka Amazon Web Services käyttää muodollisia menetelmiä @ CACM ”15 kuvaa, kuinka AWS soveltaa muodollisia menetelmiä sen tuotteet, kuten S3, DynamoDB, EBS ja sisäinen hajautetun lukituksen hallinta. Se keskittyy Lamportin TLA + -työkaluun. Muuten, Lamport on käyttänyt intensiivisesti omaa TLA-työkalupakettiaan. Hän antaa usein (melko täydellisen) muodollisen vahvistuksen TLA: ssa hänen (samoin kuin muiden tekijöiden) ehdottamista algoritmeista / teoreemeista artikkeleiden liitteissä.

Vastaa

Muodollinen vahvistus on nyt mahdollista ohjelmille, jotka ovat kirjoittaneet C ++: n osajoukon, joka on suunniteltu turvallisuuden kannalta kriittisille sulautetuille järjestelmille. Katso http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.ppt lyhyelle esitykselle ja http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.pdf koko paperille.

Kommentit

  • Kiitos linkeistä. Ainakin lyhyt yleiskatsaus niiden sisällöstä olisi hyödyllinen, jotta vältytään linkkien murtumiselta, varsinkin kun linkit ovat yrityksen verkkosivustolle: niillä on taipumus järjestäytyä säännöllisin väliajoin ja tappaa kaikki linkit sivustoon.

Vastaa

Muodollinen ohjelman määrittely on (enemmän tai vähemmän) toisella ohjelmointikielellä kirjoitettu ohjelma. Tämän seurauksena määrittely sisältää varmasti omat virheensä.

Muodollisen vahvistuksen etuna on, että koska ohjelma ja määrittely ovat kaksi erillistä toteutusta, niiden virheet ovat erilaiset. Mutta ei aina: Yksi yleinen virhelähde, unohdetut tapaukset, sopivat usein yhteen. Muodollinen todentaminen ei siis ole ihmelääke: se voi silti ohittaa ei-triviaalin määrän vikoja.

Muodollisen todentamisen haittana on, että se voi määrätä jotain kaksinkertaisesta toteutuskustannuksesta, todennäköisesti enemmän (tarvitset virallisen spesifikaation asiantuntija, ja sinun on käytettävä sen mukana tulevia enemmän tai vähemmän kokeellisia työkaluja; jotka eivät tule halpoja.

Luulisin, että koetapauksia ja rakennustelineitä niiden ajamiseksi. automaattisesti olisi parempaa aikaa.

Kommentit

  • Muodollisen vahvistuksen etu on, että … . Muodollisen todentamisen toinen haitta on se, että … Tämä on hämmentävää.
  • Mielestäni eritelmien ja epävirallisten tehtävien välinen ristiriita on ohjelmistovaatimusten analyysi, ei ohjelmointikysymys.

Vastaa

Esität muutamia erilaisia kysymyksiä. Olen samaa mieltä siitä, että viralliset todentamismenetelmät teollisissa / kaupallisissa sovelluksissa eivät ole niin yleisiä. tulisi kuitenkin ymmärtää, että kääntäjiin on rakennettu paljon ”muodollisen todentamisen” periaatteita ohjelman oikeellisuuden määrittämiseksi! Joten jos käytät nykyaikaista kääntäjää, käytät muodollisessa todentamisessa suurinta osaa tekniikan tasosta.

Sanot ”Olen kyllästynyt testaamiseen”, mutta muodollinen vahvistus ei todellakaan korvaa testausta. tavallaan sen muunnelma testauksessa.

Mainitset Java.Java-tarkistusohjelmaan nimeltä FindBugs on sisäänrakennettu monia edistyneitä muodollisia todentamismenetelmiä, jotka todellakin voidaan suorittaa isojen kooditietokantojen yli. Huomaa, että se tuottaa sekä ”vääriä positiivisia että vääriä negatiivisia”, ja ihmisen kehittäjän on tarkistettava / analysoitava tulokset. Mutta huomaa, että vaikka se ei olekaan todellisia toimintahäiriöitä, se aiheuttaa yleensä ”anti-malleja”, jotka tulisi joka tapauksessa välttää koodissa.

Et enää mainitse tiettyä sovellustasi muuten kuin ”teollinen”. . Muodollinen todentaminen käytännössä yleensä riippuu tietystä sovelluksesta.

Muodolliset todentamistekniikat näyttävät olevan yleisesti käytetty EE: ssä todistamaan piirin oikeellisuus esim. mikroprosessorisuunnittelussa.

Tässä on esimerkki Lars Philipsonin virallisten varmennustyökalujen kyselystä EE-kentässä.

Kommentit

  • ’ on harhaanjohtavaa sanoa, että ” a Paljon ” muodollisen todentamisen periaatteita ” on rakennettu kääntäjiin ohjelman oikeellisuuden määrittämiseksi ”. Tarkoitat staattista tyyppitarkistusta, jonka jotkut kääntäjät tekevät, mutta tällä tavoin todennetut ominaisuudet ovat melko yksinkertaisia, esim. välttämällä numeron ja merkkijonon lisäämistä. Tämä on hyödyllistä, mutta kaukana siitä, mikä ” muodollisella todentamisella ” yleensä ymmärretään.
  • ei viittaa erityisesti staattiseen tyyppitarkistukseen, vaikka se onkin yksi yksinkertainen / yleinen esimerkki. imho-kääntäjän optimointitekniikat, jotka ovat laajalti ja edistyneitä, ovat suunnilleen samankaltaisia kuin muodolliset todentamisperiaatteet, koska niihin sisältyy edistyneitä tekniikoita optimoidun ohjelmamuunnelman vastaavuuden määrittämiseksi / osoittamiseksi. joten näyttää siltä, että on tärkeää välttää ” liikkuvia maalipisteitä ” asia tässä, eikä olettaa, että pelkästään siksi, että kääntäjä tekee sen tai rakentaa sen kääntäjään, se ei ole muodollinen todentaminen.
  • katsoi, että tämä ei ole yleinen käsitys. optimointitekniikat luovat karkeasti mallin ohjelmakäyttäytymisestä esim. silmukasta tai aliohjelmasta, optimoivat kyseisen mallin ja tuottavat sitten uuden, todistettavasti vastaavan koodin. Jotkut näistä optimoinnista ovat melko hienostuneita järjestäessään koodia & uudelleen minulle, koska ne käyttävät muodollisia todentamisperiaatteita. kääntäjässä näyttää olevan monia muita esimerkkejä muodollisista todentamismenetelmistä … alkuperäinen kysymys esitti monia erilaisia kysymyksiä, kuten monet ovat huomanneet, en yritä vastata kaikkiin kysymyksiin.
  • tavalla näyttää siltä, että JRE: ssä, Java-ajonaikaisessa moottorissa, käytetään myös joitain muodollisia todentamisperiaatteita, esimerkiksi dynaaminen optimointi jne. …
  • eli ” unelma muodollisesta todentamisesta ”, johon elokuva viittaa, imho kimeerinen abstraktio, ja käytännöllinen / utilitaristinen / realistinen teollisuus tunnistaa sen suurelta osin sellaiseksi. suurten kooditietokantojen tiedetään vuosikymmenien ajan olleen luonnostaan $ x $ -vikoja / vikoja per $ y $ K-koodiriviä, ja tämä ei koskaan muutu riippumatta siitä, kuinka teoria / tekniikka etenee, sen tosiasia ihmisen luonne. ja itse asiassa ihmisen luomilla matemaattisilla lauseilla on samat ominaisuudet, vaikka tätä ei arvosteta laajalti!

Vastaus

Ehkä mallintarkistaja voi olla hyödyllinen.

http://alloytools.org/documentation.html Alloy on mallintarkistaja .

Mukava esitys, joka selittää mallintarkastuksen käsitteen Alloy: https://www.youtube.com/watch?v=FvNRlE4E9QQ

Samassa työkalupaketissa on ”omaisuuspohjainen testaus”, ja ne kaikki yrittävät löytää vasta-esimerkin ohjelmiston määritetylle mallille.

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *