Un'immagine generale della verifica formale nel software

Question

Sto cercando di appoggiare un quadro generale dello stato della verifica del software formale, e sto passando un bel po 'di guai. Per il contesto, vengo da per lo più uno sfondo di matematica. Sono molto familiare con lo stato dei fornitori di teoremi automatici e degli assistenti di prova rispetto al loro uso per dimostrare dichiarazioni matematiche ben formate (ad esempio in CoQ, Isabelle, Lean, ecc.). Quello che sto avendo difficoltà a capire è ciò che sta succedendo con "metodi formali" nelle pratiche applicazioni CS.

Ho trovato che le aziende come Microsoft e AWS hanno utilizzato TLA + come "metodo formale" nel loro sviluppo software in qualche modo sostanzialmente. Ma quando ho iniziato a leggere Wayne's Pratico TLA + libro, ho scoperto che ha considerato un programma da verificare formalmente se controllamo solo un algoritmo di ordinamento sugli elenchi di lunghezza $ con voci tra 1 e $ N $ per alcuni file fissi $ n $ , cioè stiamo solo controllando tanti casi finalmente e diciamo che quindi l'algoritmo dovrebbe funzionare in generale. Questo non sembra particolarmente interessante; Solo un esempio di test di unità particolarmente rigorosi. In particolare non è una prova formale di correttezza.

D'altra parte, ho visto i mormori su Isabelle e Coq è in grado di dimostrare cose sul software proprio come possono rivelarsi teoremi matematici. Sebbene quando guardo i libri che sembrano promettere questo, ad es. Programmazione certificata di Chlipala con tipi dipendenti , vedo un sacco di cose astratte che sembra vagamente riguardare i programmi verificando formalmente, ma nessun esempio di prelievo di un vero programma scritto in una lingua che ha un uso diffuso (ad esempio C ++ , Python, Java, ecc.) O anche solo pseudocodice e "verificarlo", qualunque cosa significhi.

Qualcuno può cercare di chiarire la mia confusione?

Answer 1

Un programma formalmente provato è un programma formalmente comprovato indipendentemente da quale lingua è in entrata. Solo perché un programma è scritto in CoQ e forse Estratte a OCAML o Haskell, anziché scritto in una lingua più" enterprisia "come C ++ o Java, non lo rende meno un programma.

Proving Programmi scritti in linguaggi di programmazione per uso generico, anche "addomestici" come Haskell, sono difficili perché queste lingue includono tipicamente molte caratteristiche di convenienza, angoli scuri per prestazioni e interfacciarsi con il sistema operativo e ricco e complesso Biblioteche. Per dimostrare una proprietà di un programma, devi prima dichiarare questa proprietà, e la dichiarazione incorpora la semantica della lingua che il programma è scritto in. Quando si tenta di formalizzare le lingue che sono state inizialmente progettate senza una semantica formale (che è quasi Tutti loro), colpisci molto rapidamente angoli scuri che la descrizione inglese lascia non specificata, o dove è ambigua, o dove è assolutamente auto-contraddittorio, o dove l'implementazione di riferimento non fa ciò che dice la descrizione e questo è considerato un bug in l'inglese piuttosto che nell'attuazione. Lo stato dell'arte di dimostrare proprietà dei programmi scritti in un linguaggio preesistente è limitare i programmi a un sottoinsieme della lingua.

Cosa va in quel sottoinsieme è altamente variabile. Lo zucchero sintattico non è troppo difficile: la semantica ha solo bisogno di tradurlo in costrutti più semplici. Le proprietà di riflessione non sono particolarmente difficili da modellare, ma può rendere il modello molto più difficile per ragionare (ad esempio, invalida proprietà come "Questo snippet del codice non ha alcun modo per fare riferimento a questa variabile, quindi non può Cambia il suo valore "), tanti framework regolano questo. Le interazioni con il sistema operativo (tipicamente tramite le librerie) sono problematiche perché richiedono la modellazione del sistema operativo, che diventano estremamente complesse. Le operazioni del punto di galleggiamento sono difficili perché tenere traccia delle approssimazioni attraverso le operazioni successive provoca un enorme colpo in alto.

Per C, uno dei principali sottoinsiemi di grandi dimensioni con un modello formale è CompCert C, la lingua di CompCert . CompCert è un compilatore verificato formalmente (scritto in COQ), quindi se si dimostra una proprietà del programma C, è possibile ottenere una prova del codice della macchina generato. CompCert C è un sottoinsieme molto grande di C99, ma la formalizzazione esclude la maggior parte dello standard Biblioteca e alcuni stranni della lingua.

Per dimostrare un programma che è scritto in un (sottoinsieme adatto di a) linguaggio di programmazione del mondo reale, il programma deve essere strutturato in modo tale da rendere la prova tratto. In pratica, questo significa che ha scritto e ha dimostrato il programma prima in un linguaggio di livello superiore (che non ha un'implementazione su hardware reale) e utilizzando questo linguaggio di livello superiore come specifica del programma finale. Spesso ci sono diversi livelli di successivi perfezionamenti tra il programma eseguibile e le specifiche.

È abbastanza comune che il programma finale non è scritto manualmente, ma estratti meccanicamente da un linguaggio di livello superiore. Ad esempio, scrittura di Coq che viene estratta a OCAML, o scrivendo f * che viene estratta a C. Ma il L'approccio opposto è anche possibile, ad esempio scrittura ("addomesticato") C, annotandolo con proprietà delle funzioni e altre suddivisioni di codice e utilizzando FRAMA-C Per dimostrare quelle proprietà (e la proprietà implicita che il programma C non ha un comportamento indefinito).

Quando hai una semantica formale di un linguaggio di programmazione e un modo per esprimere proprietà dei programmi, dimostrando queste proprietà è un teorema matematico. Tipicamente questi teoremi non comportano alcuna complessa matematica come il calcolo (a meno che non viene portato dal dominio dell'applicazione, come il tracciamento del movimento di un oggetto fisico), ma sono difficili da dimostrare perché coinvolgono formule molto grandi e contengono dichiarazioni aritmetiche ( $ x ^ N + y ^ n= z ^ n $ non è un'equazione complessa, ma la risoluzione non è elementare!). È teoricamente impossibile scrivere un programma che può dimostrare una proprietà semantica non banali di tutti i programmi , e praticamente impossibile scrivere un programma che può rivelare molte proprietà interessanti dei programmi tipici. La verifica formale comporta una combinazione di rottura del problema verso il basso in passaggi sufficientemente piccoli (scrivendo piccole funzioni e affermando abbastanza proprietà precise di tali funzioni), con uno strumento dimostra automaticamente alcune di quelle proprietà (tali

come un SOLD SOLVER per la logica di proposizionabile), e avendo umani di scrivere prove in cui il computer può Lo faccio (ma il computer controllerà la prova dell'uomo). Assistenti di prova come CoQ e Isabelle entrano per questo ultimo passo.

Formalmente dimostrato un programma reale del mondo è uno sforzo enorme, richiedendo un tempo e una competenza molto più ampia del progetto software tipico. Viene raramente fatto al di fuori degli ambienti ad alta sicurezza, per lo più ambienti con elevati riassunti di sicurezza come il trasporto (aerei, treni, non tante auto), a volte ambienti con costi elevati come lo spazio o (molto raramente) con elevati requisiti di sicurezza come intelligente Carte.

.

Se vogliamo semplicemente dire un algoritmo di ordinamento sugli elenchi di lunghezza

Non sarebbe una prova formale a meno che il programma non abbia avuto un limite di articoli N per il suo input. Non conosco questo libro, ma sospetto sia che tu debba errorizzare qualcosa. Il controllo formalmente di un programma di smistamento comporterebbe dimostrare la sua correttezza per tutto n.