Testing, correttezza Testing, correttezza e invarianti e invarianti

(1)

Testing, correttezza Testing, correttezza

e invarianti e invarianti

Moreno Marzolla

(2)

Testing, correttezza e invarianti 2

(3)

(4)

Il primo "bug" software

9 settembre 1947

"First actual case of bug being found"

.

(5)

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

(6)

“Il testing verifica la presenza di errori, non la loro assenza”

Edsger W. Dijkstra (1930–2002)

(7)

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 essere sempre vera in quel punto

– si possono usare gli operatori logici and, or, not ...

(8)

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;

(9)

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 */

(10)

Invariante di ciclo

●

Serve a dimostrare la correttezza di un ciclo

●

Noi la applicheremo in modo informale ai cicli "for"

– Si può applicare anche agli altri tipi di cicli

●

L'invariante I di un ciclo è una proprietà che vale immediatamente prima dell'esecuzione del corpo

for (init; C; incr) {

/* L'invariante deve valere qui */

Body }

(11)

Invariante di ciclo

●

Proprietà dell'invariante I

– Deve essere vera la prima volta che il ciclo viene

eseguito

– Se è vera all'inizio di una

iterazione, deve rimanere vera all'inizio dell'iterazione

successiva

– Al termine del ciclo fornisce informazioni utili su ciò che il ciclo ha calcolato

Body

for (init; C; incr) { /* Invariante */

Body }

Init

C

I

Se l'invariante I I

vale qui...

...e resta valida anche qui...

(12)

Invariante di ciclo

●

Possono esistere più invarianti di ciclo

●

Ma di solito solo una

funziona per dimostrare la correttezza

●

Per trovarla suggerisco di

chiedersi: che proprietà deve valere all'inizio di ogni

iterazione?

^Body

I ∧ ¬C

for (init; C; incr) { /* Invariante */

Body }

Init

C

I

Incr

I

(13)

Es.: elevamento a

potenza

_{p = 1.0}^{i = 0}

i<n

p = p*x V

/* precondizione: n≥0 */ F

int n = …;

int i;

double x = … , p = 1.0;

for (i=0; i < n; i++) { p = p * x;

}

●

Dato x e un intero n ≥ 0,

calcolare x

ⁿ

(14)

Es.: elevamento a

potenza

_{p = 1.0}^{i = 0}

i<n

p = p*x

i = i + 1 V

/* precondizione: n≥0 */ F

int n = …;

int i;

double x = … , p = 1.0;

for (i=0; i < n; i++) { /* p=xⁱ ∧ i<n ∧ n≥0 */

p = p * x;

/* p=xⁱ⁺¹ ∧ i<n ∧ n≥0 */

}

/* p=xⁱ ∧ (i=n) ∧ n≥0 */

Invariante: ( p = xⁱ ∧ i ≤ n )

p=xⁱ ∧ i=0 ∧ n≥0

p=xⁱ⁺¹ ∧ i<n ∧ n≥0 p=xⁱ ∧ i<n ∧ n≥0

p=xⁱ ∧ i=n

∧ n≥0

●

Dato x e un intero n ≥ 0,

calcolare x

ⁿ

(15)

Es.: somma di un array

/* precondizione: n≥0 */

int i, s=0;

for (i=0; i<n; i++) { s = s + a[i];

}

s = 0 i = 0

i<n

s=s+a[i]

V

F

●

Calcolare la somma

degli elementi di un array

– L'array vuoto ha somma 0

(16)

Es.: somma di un array

int i, s=0;

for (i=0; i<n; i++) {

/* s=∑a[0..i-1] ∧ i<n ∧ n≥0 */

s = s + a[i];

/* s=∑a[0..i] ∧ 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

●

Calcolare la somma

degli elementi di un array

– L'array vuoto ha somma 0

(17)

Es.: minimo di un array

int i, m=a[0];

for (i=1; i<n; i++) {

if (a[i] < m) m = a[i];

}

m = a[0]

i = 1

i<n

m = min(m, a[i]) V

F

●

Determinare il valore

minimo in un array non

vuoto

(18)

Es.: minimo di un array

int i, m=a[0];

for (i=1; i<n; i++) {

/* 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 */

}/* m=min a[0..i-1] ∧ i=n ∧ n≥1 */

m = a[0]

i = 1

i<n

m = min(m, a[i])

i = i + 1 V

F

m=min a[0..i-1] ∧ i=1 ∧ n≥1

●

Determinare il valore minimo in un array non vuoto

Invariante: ( m = min a[0..i-1] ∧ i ≤ n )

m=min a[0..i-1] ∧ i<n ∧ n≥1

m=min a[0..i] ∧ i<n ∧ n≥1

m=min a[0..i-1]

∧ i=n ∧ n≥1

(19)

Osservazioni conclusive

●

L'uso di asserzioni e invarianti è uno strumento

potente per dimostrare la correttezza dei programmi

●

Ha però degli svantaggi:

– Non può essere applicato sempre (certe proprietà sono indimostrabili)

– Anche su programmi semplici, le dimostrazioni possono diventare molto laboriose

●

Testing, correttezza Testing, correttezza e invarianti e invarianti