Tecniche di test e debugging contro il teorema di Rice

1

Per quanto ho capito correttamente, come risultato del teorema di Rice, l'equivalenza di due programmi non è generalmente decidibile.

Tuttavia, esiste una vasta gamma di tecniche di test e debug, che cambiano il programma per il loro scopo: in realtà, riesco a malapena a pensare a una tecnica che non lo fa. Quindi, in realtà, non lavori mai con il programma che vuoi investigare - il caso migliore è abbastanza simile, ma in linea di principio puoi ricevere un programma arbitrariamente diverso.

Il ragionamento generale che ho sentito su questo punto è simile a "Questo è solo stat xy, che non fa altro che aiutare nel test / debugging". Ma soprattutto nel contesto di bug di solito difficili da trovare come le condizioni di gara e altri problemi legati alla temporizzazione, qualsiasi alterazione del flusso del programma si è dimostrata sostanziale.

Anche se sono consapevole che tali considerazioni potrebbero essere eccessive per un'ampia varietà di applicazioni, diventano significative non appena si suppone che l'applicazione sia implementata in un ambiente in cui le vite dipendono da esso, come ad esempio le apparecchiature mediche. Gli standard di cui sono a conoscenza, come l'IEC 62304, eludono questo problema richiedendo test più approfonditi per le classi di certificazione più elevate, ma questa sembra essere solo la migliore pratica.

Non dovrebbe esserci una base teorica per discutere sull'estensione dei test necessari nonostante l'esistenza del teorema di Rice, per rendere il più sicuro possibile, che le tecniche di test e debug utilizzate non nascondano bug esistenti? La letteratura scientifica in questo settore sembra essere estremamente scarsa, ma quali sono i comitati di certificazione, che definiscono quegli standard, basando i loro requisiti su?

    
posta Wanderer 22.04.2018 - 18:39
fonte

2 risposte

2

Il teorema di Rice è una scienza computerizzata / affermazione matematica sulla computabilità, cioè macchine di Turing astratte. Non ci può essere una procedura generale per decidere l'equivalenza di due programmi qualsiasi. Ma ciò non esclude che alcune procedure possano decidere l'equivalenza per un piccolo sottoinsieme di programmi. Ad esempio, molti programmi pratici non sono completi di Turing.

Inoltre, potrebbe essere possibile dimostrare che alcune trasformazioni di programma danno come risultato un programma equivalente, per quanto riguarda certe proprietà di quel programma. Ad esempio, molte trasformazioni del compilatore potrebbero essere probabilmente corrette.

Tuttavia, si tratta ancora di modelli astratti di computazione, e non di una dichiarazione sull'hardware di calcolo attuale. Non è quindi utile invocare il teorema di Rice nel contesto di comportamenti non deterministici come le condizioni di gara.

Tuttavia, si fa riferimento a un problema importante, che il manufatto software in fase di test è spesso diverso dal manufatto software che viene implementato. Fortunatamente, ci sono modi per ridurre questo impatto, ad esempio lasciando i meccanismi di debug ampiamente attivati in modalità di rilascio (come asserzioni e registrazione) e scrivendo codice che non è sensibile ai problemi di temporizzazione, ad es. utilizzando strategie di sincronizzazione adeguate.

È possibile formulare un'argomentazione formale sulla necessità di test approfonditi: il test campiona il comportamento del sistema sotto test. Lo spazio dei comportamenti possibili è molto ampio, quindi non può essere campionato nella sua interezza. Ma prendere più campioni (= eseguire più test) ci dà migliori probabilità di trovare più difetti. Inoltre, non tutti i difetti sono ugualmente probabili. Alcuni difetti potrebbero essere così rari da non essere mai osservati dagli utenti. Test più approfonditi possono riguardare il comportamento di più utenti, in modo che restino meno difetti da parte degli utenti.

    
risposta data 22.04.2018 - 20:04
fonte
3

La differenza tra un bug e una caratteristica è la stessa differenza tra una pianta e un'erbaccia. O è voluto o non lo è.

Il lavoro svolto per dimostrare la correttezza e la verifica del codice non consiste nel mostrare il codice per essere perfetto e privo di errori. Si tratta di stabilire quanto sia comprensibile il codice. Solo una volta che il codice è compreso puoi decidere se fa quello che vuoi. Ma senza sapere quello che vuoi nessuno può dimostrare che tutto funziona.

Il teorema di Rice sottolinea solo che non possiamo cambiare il codice e quindi provare che abbiamo solo rifattorizzato il codice senza cambiare comportamento. Ma dal momento che è molto più importante stabilire quale comportamento vogliamo e dimostrare che non è cambiato come noi refactoring, non dobbiamo preoccuparci dell'equivalenza. Dopo tutto, come sapevi che il vecchio aveva il comportamento che volevi comunque?

    
risposta data 22.04.2018 - 19:27
fonte

Leggi altre domande sui tag