Testing, correttezza Testing, correttezza
e invarianti e invarianti
Moreno Marzolla
Dipartimento di Informatica—Scienza e Ingegneria (DISI) Università di Bologna https://www.moreno.marzolla.name/
Cap. 3.2 dispensa
http://www.cbi.umn.edu/hostedpublications/Tomash/Images%20web%20site/Image%20files/H%20Imag
Harvard Mark II
Il primo "bug" software
9 settembre 1947
"First actual case of bug being found"
Come verificare che un programma sia corretto?
●
Mediante test (collaudo)
– Si preparano dei casi di test
– Per ognuno di essi, si verifica che il programma fornisca il risultato atteso
●
Mediante dimostrazioni di correttezza
– Si dimostra formalmente (matematicamente) che il programma calcola il risultato corretto
Testing (collaudo)
●
Collaudo white-box
– Si conosce la struttura interna del programma
●
Collaudo black-box
– Non si conosce la struttura interna del programma
●
Testing e debugging sono due cose distinte
– Testing = verificare se ci sono errori
– Debugging = localizzare e correggere gli errori
Collaudi di tipo black-box
●
La struttura interna del programma non è nota
– Es., perché il sorgente non è disponibile
– Es., perché il sorgente non è ancora disponibile
●
Una strategia comune è di esaminare i casi limite
●
Esempio: alcuni casi di test per una funzione che ordina un array di n ≥ 0 elementi
– Test 1: array vuoto
– Test 2: array con un solo elemento (n = 1)
– Test 3: array già ordinato
– Test 4: array ordinato in senso contrario
– Test 5: array composto da valori tutti uguali
– ...
“Il testing verifica la presenza di errori, non la loro assenza”
Edsger W. Dijkstra (1930–2002)
Dimostrazioni di correttezza
●
Dimostrare che un dato frammento di codice calcola il risultato atteso
●
Come? Specificando dopo ogni istruzione quali proprietà valgono in quel punto (asserzioni)
– cioè di quali proprietà godono i valori delle variabili in quel punto
●
Una asserzione è una espressione logica che deve risultare sempre vera in quel punto
– si possono usare gli operatori logici and, or, not ...
Esempio
●
Supponiamo che
all'inizio si abbia x=x0, y=y0
●
Cosa possiamo dire dei valori di x e y al termine di questo frammento di codice?
/* x = x0 ∧ y = y0 */
x = x – y;
y = x + y;
x = y – x;
Esempio
●
Supponiamo che
all'inizio si abbia x=x0, y=y0
●
Cosa possiamo dire dei valori di x e y al termine di questo frammento di codice?
/* x = x0 ∧ y = y0 */
x = x – y;
/* x = x0 – y0 ∧ y = y0 */
y = x + y;
/* x = x0 – y0 ∧ y = x0 */
x = y – x;
/* x = y0 ∧ y = x0 */
Asserzioni
●
Una asserzione ha la forma
{P} S {Q}
dove:
– P e Q sono espressioni logiche
– S è una istruzione o sequenza di istruzioni
●
Significa:
– Se prima di eseguire S, l'espressione P è vera...
– ...allora dopo l'esecuzione di S, sarà vera l'espressione Q
Assegnamento "x = E"
●
Esempi:
– {True} x = 15; {x = 15}
– {x = 46} y = x+1; {y=47 ∧ x=46}
– {x < n} x = x+1; {x ≤ n}
●
Schema generale
– { P[x→E] } x = E; { P }
– P[x→E] indica la proprietà P in cui ogni occorrenza del simbolo "x" viene
rimpiazzata dall'espressione "E"
x = E
P[x→E]
P
Strutture condizionali
●
Supponiamo che prima dell'”if” valga P. Allora
– All'inizio del ramo “vero”
vale (P ∧ C)
– All'inizio del ramo
“falso” vale (P ∧ ¬C)
●
Supponiamo che al
termine del ramo “vero”
valga Q, e al termine del ramo “falso” valga R. Allora
– Alla fine vale (Q ∨ R)
C F V
P
P ∧ ¬C P ∧ C
R Q
Q ∨ R
Esempio
●
Supponiamo che inizialmente x=x0
●
Che proprietà vale al termine di questo
frammento di codice?
if ( x < 0 ) { x = -x;
}
x<0
x = -x
V
F
Esempio
●
Supponiamo che inizialmente x=x0
●
Che proprietà vale al termine di questo
frammento di codice?
if ( x < 0 ) { x = -x;
}
x<0
x = -x
V
F
x=x0
x=x0 ∧ x<0
x=-x0 ∧ x>0
x=x0 ∧ x≥0
(x=x0 ∧ x≥0) ∨ (x=-x0 ∧ x>0)
Invariante di ciclo
●
Serve a dimostrare la correttezza di un ciclo
●
L'invariante è una proprietà I che:
– deve valere prima del ciclo
– deve valere subito dopo il corpo del ciclo
●
Nota: oltre all'invariante,
possono valere anche altre proprietà
C
Body V
F
I
I ∧ ¬C I I ∧ C
while (C) { Body }
Se l'invariante I vale qui...
...e resta valida anche qui...
...allora al termine del ciclo
vale I ∧ ¬C
Invariante di ciclo
●
Trovare l'invariante I di un ciclo non è facile
●
Suggerisco di procedere a ritroso:
– Cerchiamo una proprietà I che sia vera subito dopo il corpo del ciclo
– I vale prima dell'inizio del ciclo?
– I vale subito dopo il corpo del ciclo?
– Se rispondiamo "sì" a entrambe le domande, allora I è una
possibile invariante
C
Body V
F
I
I ∧ ¬C I I ∧ C
Esempio: elevamento a potenza
●
Determinare una invariante del seguente ciclo
– Dato n ≥ 0 e x, il calcola xn
int n = …;
int i=0; double x = … , p = 1.0;
/* precondizione: n≥0 */
/* l'invariante I deve valere qui */
while (i < n) { p = p * x;
i = i + 1;
/* l'invariante I deve valere qui */
}
/* qui vale I ∧ (i≥n) */
Es.: elevamento a
potenza
p = 1.0i = 0i<n
p = p*x
i = i + 1 V
F
/* precondizione: n≥0 */
int n = …;
int i=0; double x = … , p = 1.0;
/* */
while (i < n) {
/* */
p = p * x;
/* */
i = i + 1;
/* */
}/* */
Es.: elevamento a
potenza
p = 1.0i = 0i<n
p = p*x
i = i + 1 V
F
/* precondizione: n≥0 */
int n = …;
int i=0; double x = … , p = 1.0;
/* p=xi ∧ i=0 ∧ n≥0 */
while (i < n) {
/* p=xi ∧ i<n ∧ n≥0 */
p = p * x;
/* p=xi+1 ∧ i<n ∧ n≥0 */
i = i + 1;
/* p=xi ∧ i≤n ∧ n≥0 */
}
/* p=xi ∧ (i=n) ∧ n≥0 */
Invariante: ( p=xi ∧ i≤n )
p=xi ∧ i=0 ∧ n≥0
p=xi+1 ∧ i<n ∧ n≥0
p=xi ∧ i≤n ∧ n≥0 p=xi ∧ i<n ∧ n≥0
p=xi ∧ i=n
∧ n≥0 Questa asserzione
implica l'invariante
Es.: somma contenuto di un array
●
Determinare una invariante del seguente ciclo
– a[] è un array di interi di lunghezza n ≥ 0
– Il programma calcola la somma dei valori in a[]
/* precondizione: n≥0 */
int i=0, s=0;
/* l'invariante I deve valere qui */
while (i<n) {
s = s + a[i];
i = i + 1;
/* l'invariante I deve valere qui */
}
/* qui vale I ∧ (i≥n) */
Es.: somma di un array
/* precondizione: n≥0 */
int i=0, s=0;
/* */
while (i<n) {
/* */
s = s + a[i];
/* */
i = i + 1;
/* */
}
/* */
s = 0 i = 0
i<n
s=s+a[i]
i = i + 1 V
F
Es.: somma di un array
/* precondizione: n≥0 */
int i=0, s=0;
/* s=∑a[0..i-1] ∧ i=0 ∧ n≥0 */
while (i<n) {
/* s=∑a[0..i-1] ∧ i<n ∧ n≥0 */
s = s + a[i];
/* s=∑a[0..i] ∧ i<n ∧ n≥0 */
i = i + 1;
/* s=∑a[0..i-1] ∧ i≤n ∧ n≥0 */
}/* s=∑a[0..i-1] ∧ i=n ∧ n≥0 */
Invariante: ( s=Σa[0..i-1] ∧ i≤n )
s = 0 i = 0
i<n
s=s+a[i]
i = i + 1 V
F
s=∑a[0..i-1] ∧ i=0 ∧ n≥0
s=∑a[0..i-1] ∧ i<n ∧ n≥0
s=∑a[0..i] ∧ i<n ∧ n≥0
s=∑a[0..i-1] ∧ i≤n ∧ n≥0
s=∑a[0..i-1] ∧ i=n ∧ n≥0 Questa asserzione
implica l'invariante
Es.: minimo di un array
●
Determinare una invariante del seguente ciclo
– a[] è un array di interi di lunghezza n ≥ 1
– Il programma calcola il minimo valore in a[]
/* precondizione: n≥1 */
int i=1, m=a[0];
/* l'invariante I deve valere qui */
while (i<n) {
if (a[i] < m) { m = a[i];
}
i = i + 1;
/* l'invariante I deve valere qui */
}
/* qui vale I ∧ (i≥n) */
Es.: minimo di un array
/* precondizione: n≥1 */
int i=1, m=a[0];
/* m = min a[0..i-1] ∧ i=1 ∧ n≥1 */
while (i<n) {
/* m = min a[0..i-1] ∧ i<n ∧ n≥1 */
if (a[i] < m) { m = a[i];
}
/* m = min a[0..i] ∧ i<n ∧ n≥1 */
i = i + 1;
/* m = min a[0..i-1] ∧ i≤n ∧ n≥1 */
}/* m = min a[0..i-1] ∧ i=n ∧ n≥1 */
Invariante: ( m = min a[0..i-1] ∧ i≤n )
Questa asserzione implica l'invariante
Osservazioni conclusive
●
L'uso di asserzioni e invarianti è uno strumento molto potente per dimostrare la correttezza di programmi
●
Ha però degli svantaggi:
– Non può essere applicato sempre (certe proprietà sono indimostrabili)
– Anche su programmi semplici, le dimostrazioni possono diventare molto laboriose
●
Come alternativa si ricorre spesso al testing, che a sua volta ha delle limitazioni:
– Tranne in casi banali, è impossibile definire un insieme di test esaustivi
– Non dimostra l'assenza di errori, ma solo la loro presenza