• Non ci sono risultati.

Testing, correttezza Testing, correttezza e invarianti e invarianti

N/A
N/A
Protected

Academic year: 2021

Condividi "Testing, correttezza Testing, correttezza e invarianti e invarianti"

Copied!
27
0
0

Testo completo

(1)

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

(2)
(3)

http://www.cbi.umn.edu/hostedpublications/Tomash/Images%20web%20site/Image%20files/H%20Imag

Harvard Mark II

(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)

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

(7)

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

...

(8)

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

Edsger W. Dijkstra (1930–2002)

(9)

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 ...

(10)

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;

(11)

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

(12)

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

(13)

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

(14)

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

(15)

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

(16)

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)

(17)

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

(18)

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

(19)

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

(20)

Es.: elevamento a

potenza

p = 1.0i = 0

i<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;

/* */

}/* */

(21)

Es.: elevamento a

potenza

p = 1.0i = 0

i<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

(22)

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

(23)

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

(24)

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

(25)

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

(26)

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

(27)

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

Riferimenti

Documenti correlati

Abbandoniamo ora i nodi e le trecce, e concentriamoci sulla ricerca degli operatori di Yang-Baxter: alla fine di questa sezione avremo un modo mol- to generale per produrre

E’ possibile che, dopo un certo numero di volte, sulla lavagna rimanga solo il numero 2018?.

Angelo scrive una riga di 1000 numeri interi, Beatrice sotto ad ogni numero scrive quante volte compare nella riga, ottenendo cos`ı una seconda riga di 1000 interi.. Angelo

In generale dunque ogni iterazione dell'algoritmo riduce lo spazio totale utilizzato creando viste più generiche, allo scotto di aumentare normalmente il tempo totale di

• Introduciamo un contatore che contiene il numero di giorni nei quali l’azione è aumentata rispetto al giorno precedente e un contatore nel quale registriamo i giorni nei quali

Come vedremo, gli ideali moltiplicatori di I σ sono generati da prodotti di minori, la cui appartenenza o meno all’ideale dipende solo dalla taglia.... Lo scopo del resto del

– Deve essere vera la prima volta che il ciclo

Vedremo inoltre come la mancanza di raggiungibilit`a o di osservabilit`a possano essere viste come “patologie del sistema che hanno come conseguenza l’incongruenza tra