Le prove di correttezza del codice diventeranno sempre più comuni? [chiuso]

14

Tutti tranne i programmi più banali sono pieni di bug e quindi tutto ciò che promette di rimuoverli è estremamente allettante. Al momento, le prove di correttezza sono codice estremamente esoterico, principalmente a causa della difficoltà di apprendimento di questo e dello sforzo extra necessario per dimostrare un programma corretto. Pensi che la dimostrazione del codice decollerà mai?

    
posta Casebash 02.09.2010 - 23:54
fonte

10 risposte

8

Non proprio in questo senso, ma la pura programmazione funzionale è buona in questo settore. Se usi Haskell, è probabile che il tuo programma sia corretto se il codice viene compilato. Tranne che da IO, un buon sistema di tipi è un buon aiuto.

Anche la programmazione a contratto può essere utile. Vedi Contratti Microsoft Code

    
risposta data 03.09.2010 - 00:49
fonte
14

All but the most trivial programs

non può essere completamente provato per essere corretto con uno sforzo ragionevole. Per qualsiasi prova formale di correttezza, è necessario almeno una specifica formale e tale specifica deve essere completa e corretta. Questo in genere non è possibile creare facilmente per la maggior parte dei programmi reali. Ad esempio, prova a scrivere tali specifiche per qualcosa come l'interfaccia utente di questo sito di discussione e sai cosa intendo.

Qui ho trovato un bell'articolo sull'argomento:

link

    
risposta data 22.12.2011 - 16:06
fonte
10

Il problema con le prove formali è che rimuove il problema solo di un passo.

Dire che un programma è corretto equivale a dire che un programma fa ciò che dovrebbe fare. Come definisci cosa dovrebbe fare il programma? Lo specifichi. E come definisci cosa dovrebbe fare il programma nei casi limite che le specifiche non coprono? Bene, allora devi rendere le specifiche più dettagliate.

Quindi diciamo che le tue specifiche diventano abbastanza dettagliate per descrivere il comportamento corretto di ogni aspetto dell'intero programma. Ora hai bisogno di un modo per far sì che i tuoi strumenti di prova lo capiscano. Quindi devi tradurre le specifiche in una sorta di linguaggio formale che lo strumento di prova può capire ... hey, aspetta un minuto!

    
risposta data 22.12.2011 - 18:52
fonte
8

La verifica formale ha fatto molta strada, ma in genere gli strumenti di settore / ampiamente utilizzati sono in ritardo rispetto alle ultime ricerche. Ecco alcuni sforzi recenti in questa direzione:

Spec # link Questa è un'estensione di C # che supporta i contratti di codice (pre / post condizioni e invarianti) e può utilizzare questi contratti per eseguire vari tipi di analisi statiche.

Progetti simili a questo esistono per altre lingue, come JML per java, e Eiffel ha questo praticamente integrato.

Andando ancora oltre, progetti come slam e blast può essere usato per verificare alcune proprietà comportamentali con annotazioni / interventi minimi del programmatore, ma non può ancora occuparsi della piena generalità dei linguaggi moderni ( cose come overte integer / aritmetica del puntatore non sono modellate).

Credo che vedremo molte più di queste tecniche utilizzate nella pratica in futuro. La barriera principale è che gli invarianti di programma sono difficili da dedurre senza annotazioni manuali, e di solito i programmatori non sono disposti a fornire queste annotazioni perché farlo è troppo noioso / richiede molto tempo.

    
risposta data 22.12.2011 - 15:49
fonte
4

A meno che non si presenti un metodo per provare automaticamente il codice senza un ampio lavoro di sviluppo.

    
risposta data 03.09.2010 - 00:35
fonte
3

Alcuni metodi formali strumenti (come ad esempio Frama-C per software C embedded critico) può essere visualizzato come (sort-of) fornendo, o almeno controllando, una prova (corretta) di un determinato software. (Frama-C controlla che un programma obbedisca alle sue specifiche formalizzate, in un certo senso, e rispetti invarianti esplicitamente annotati nel programma).

In alcuni settori, tali metodi formali sono possibili, ad es. come DO-178C per software critico in aeromobili civili. Quindi, in alcuni casi, tali approcci sono possibili e utili.

Ovviamente, lo sviluppo di software meno buggato è molto costoso. Ma l'approccio al metodo formale ha senso per qualche tipo di software. Se sei pessimista, potresti pensare che il bug venga spostato dal codice alle sue specifiche formali (che potrebbero avere alcuni "bug", perché la formalizzazione del comportamento previsto di un software è difficile e soggetta a errori).

    
risposta data 22.12.2011 - 16:34
fonte
3

Mi sono imbattuto in questa domanda e penso che questo link potrebbe essere interessante:

Applicazioni industriali di Astrée

Dimostrare che l'assenza di RTE in un sistema usato da Airbus con più di 130.000 linee di codice nel 2003 non sembra essere male, e mi chiedo se qualcuno dirà che non è vero.

    
risposta data 11.02.2012 - 02:31
fonte
2

No. Il proverbio comune per questo è, "In teoria, teoria e pratica sono le stesse. In pratica, no."

Un esempio molto semplice: Typos.

In realtà, l'esecuzione del codice tramite il test delle unità trova quasi immediatamente tali elementi e una serie di test coesivi annullerà la necessità di prove formali. Tutti i casi d'uso - buoni, cattivi, errori e casi limite - dovrebbero essere enumerati nei test unitari, che finiscono come prova migliore del codice è corretto rispetto a qualsiasi prova simile separata dal codice.

Specialmente se i requisiti cambiano, o l'algoritmo viene aggiornato per correggere un bug - la dimostrazione formale ha più probabilità di finire fuori data, come spesso accade ai commenti del codice.

    
risposta data 22.12.2011 - 17:06
fonte
1

Penso che i limiti imposti alle prove di correttezza a causa del problema di interruzione potrebbero essere il più grande ostacolo alle prove di correttezza che diventano mainstream.

    
risposta data 03.09.2010 - 00:40
fonte
1

È già usato da tutti. Ogni volta che usi il controllo del tipo del tuo linguaggio di programmazione, stai praticamente facendo una prova matematica della correttezza del tuo programma. Funziona già molto bene, richiede solo che tu scelga i tipi corretti per ogni funzione e struttura dati che usi. Più accurato è il tipo, migliore è il controllo che otterrai. I tipi esistenti disponibili nei linguaggi di programmazione dispongono già di strumenti abbastanza potenti per descrivere quasi tutti i possibili comportamenti. Funziona in tutte le lingue disponibili. C ++ e i linguaggi statici eseguono solo i controlli in fase di compilazione, mentre i linguaggi più dinamici come Python lo fanno quando viene eseguito il programma. Il controllo esiste ancora in tutte queste lingue. (ad esempio, c ++ supporta già il controllo degli effetti collaterali nello stesso modo di haskell, ma devi solo scegliere di usarlo.)

    
risposta data 22.12.2011 - 18:34
fonte

Leggi altre domande sui tag