Boolean Expression

admin

5.1 Specifiche basate sullo stato

Le specifiche basate sullo stato descrivono i sistemi software in termini di stati ed effetti delle operazioni sugli stati. Tali specifiche sono supportate da diversi linguaggi di specifica, che abbiamo raggruppato in due gruppi: linguaggi di specifica classici, come Z, B e VDM, e linguaggi di asserzione, come Eiffel, JML (Java Modeling Language) e le tabelle di Peters e Parnas. Mentre i linguaggi di specifica classici definiscono stati e transizioni indipendentemente dall’implementazione, i linguaggi di asserzione specificano stati e transizioni come dichiarazioni o annotazioni del programma sorgente.

Le specifiche basate sugli stati sono usate come oracoli di test verificando la conformità delle esecuzioni dei test con le specifiche. Il problema principale nella generazione di oracoli di test da specifiche basate sullo stato deriva dai diversi livelli di astrazione tra le specifiche e le operazioni monitorate durante l’esecuzione del test; quindi, le specifiche delle operazioni saranno tradotte in una forma verificabile. I linguaggi di specifica sono di solito abbastanza espressivi per rappresentare varie strutture di dati e proprietà basate sullo stato, ma la loro espressività complica la traduzione in forma eseguibile. Spesso la traduzione fa alcune assunzioni semplificatrici, come limitare gli insiemi infiniti, per esempio l’insieme infinito dei numeri naturali, e gestire gli elementi non eseguibili solo parzialmente e a volte richiedendo qualche intervento umano.

Qui, discutiamo i principali approcci per tradurre le specifiche basate sullo stato in una forma eseguibile. La traduzione delle specifiche Z, B e VDM presenta gli stessi problemi relativi alle strutture dati infinite, alle espressioni parzialmente definite e alle strutture orientate agli oggetti. La traduzione di Eiffel, JML e altri linguaggi di asserzione in forma verificabile presenta problemi simili ma ad un diverso livello di astrazione. Nel seguito, presentiamo i principali approcci per tradurre le specifiche basate sugli stati in forma verificabile facendo riferimento a Z; gli approcci per altri linguaggi sono simili. Poi, discutiamo i problemi di compilazione delle asserzioni in controlli eseguibili facendo riferimento a Eiffel, JML, e alle tabelle di Peters e Parnas.

Il compilatore di predicati di schema proposto da Mikk compila le specifiche Z in codice C. Per ogni schema Z, che è l’unità di base in Z, l’approccio genera una funzione C che valuta i predicati dello schema usando lo stato del programma passato alla funzione come parametro. Il codice generato valuta i predicati dello schema con una strategia di “forza bruta”: Dato uno stato, il codice sostituisce essenzialmente le espressioni con i loro valori, valuta le formule del calcolo proposizionale usando le tabelle di verità, e valuta le quantificazioni e le costruzioni di set iterando attraverso le strutture dati. Per ridurre la complessità delle funzioni C generate, l’approccio propone una fase di ottimizzazione per garantire che il codice C generato termini sempre. Per ottimizzare il codice, la tecnica definisce un sottoinsieme “eseguibile” del linguaggio Z. Il sottoinsieme consiste di predicati finiti, come formule del calcolo proposizionale, quantificazioni su insiemi finiti e costruzioni di insiemi basate sull’iterazione finita. La tecnica estende l’insieme dei predicati eseguibili con un insieme di regole per trasformare speciali predicati non eseguibili che soddisfano certe condizioni in predicati eseguibili senza cambiare la loro semantica. Per esempio, le seguenti due regole eliminano i quantificatori:

∀x:M-PM≠∅⇒PNotOccurxP∃x:M-PM≠∅∧PNotOccurxP

dove M è un insieme, la variabile x rappresenta un elemento in M, e P è un predicato. L’operatore -, noto anche come “punto di notazione Z”, significa “tale che” quando è usato con il quantificatore ∃ e “che” quando è usato con il quantificatore ∀. Per esempio, ∃ x : M – P significa che esiste almeno un valore x in M tale che il predicato P è vero. La condizione NotOccur(x, P) indica che x non è una variabile libera nel predicato P. Anche se l’insieme M può essere infinito, il compilatore può ancora compilare specifiche usando quantificatori su M, purché i quantificatori possano essere eliminati applicando le regole di cui sopra. Per le funzioni definite dall’utente che possono essere introdotte da definizioni assiomatiche o generiche, il compilatore richiede all’utente di fornire il codice corrispondente. Mikk propone anche una soluzione al problema delle specifiche parzialmente definite. Egli usa VDM-SL come forma intermedia e il compilatore VDM-SL sviluppato da Schmidt e Hörcher per tradurre le specifiche Z in codice C. Quando si ha a che fare con espressioni parzialmente definite, cioè sia funzioni che relazioni che possono valutare indefinito (denotato come ⊥) quando valutato al di fuori del loro dominio di definizione, l’approccio genera gestori di eccezioni.

Le estensioni orientate agli oggetti di Z, come Object-Z, esacerbano i problemi. McDonald et al. traducono le specifiche Ojbect-Z delle classi contenitore in codice C++ in tre fasi: ottimizzazione, mappatura strutturale e traduzione dei predicati. Nella fase di ottimizzazione, essi riorganizzano la specifica per semplificare la successiva traduzione attraverso diversi passi, compresa la sostituzione delle variabili costanti con i loro valori e la rimozione delle variabili secondarie e degli arricchimenti dello schema. Nella fase di mappatura strutturale, essi mappano le strutture nella specifica Object-Z ai loro corrispondenti elementi di codice: Le costanti e le variabili della specifica in variabili con inizializzazioni appropriate, e i tipi di variabili in tipi primitivi C++ o classi corrispondenti nella libreria del toolkit Z usato dalla tecnica. Per esempio, mappano i tipi interi e booleani a int, e il tipo di insiemi interi a z_set<int >. Essi mappano lo schema di inizializzazione in un costruttore, e gli schemi di operazione in funzioni membro, creano una funzione membro speciale, inv(), per controllare l’invariante di classe, e generano una classe di eccezione per ogni schema di eccezione.

Nella traduzione del predicato DeepL, la tecnica si concentra su come generare codice per controllare lo stato del programma, invece di valutare i predicati. Per esempio, la traduzione impedisce alla funzione inv() di chiamare qualsiasi altra funzione membro, per evitare la ricorsione infinita. In un costruttore, l’invariante di classe è controllato alla sua uscita.

Richardson et al. si concentrano su sistemi critici per il tempo, trattano una combinazione di logica Z e di intervallo temporale, e propongono una traduzione delle specifiche in oracoli di test per mezzo dell’interpretazione simbolica. L’interpretazione simbolica assegna i nomi simbolici nelle specifiche agli ingressi dello stimolo e alle variabili di stato iniziali, facendo riferimento alle mappature dei dati e dei controlli. Poi, l’interpretazione simbolica interpreta ogni percorso di controllo nelle specifiche, cioè crea un’asserzione che esprime la condizione sui dati di specifica in base allo stato simbolico in ogni punto di controllo di specifica. Un punto di controllo della specifica è un elemento rilevante, come un evento parametrizzato, una transizione e un’operazione. Dopo l’interpretazione simbolica della specifica Z, l’informazione dell’oracolo è rappresentata come una lista di schemi Z pertinenti e le loro asserzioni corrispondenti, che sono controllate se lo schema è invocato. L’esecuzione di un caso di test si riferisce ad un input di test concreto da cui variabili ed eventi concreti sono legati alle loro controparti nella classe di test (ogni classe di test è una partizione di input di test). L’esecuzione del caso di test produce un profilo di esecuzione, e gli eventi concreti e i valori delle variabili contenuti nel profilo di esecuzione sono mappati al livello dell’oracolo per controllare la loro coerenza con le informazioni dell’oracolo.

I linguaggi di asserzione uniscono le specifiche al codice sorgente, semplificando così, ma non eliminando il problema della traduzione. Le asserzioni sono supportate da diversi linguaggi e metodologie. La progettazione per contratto è un paradigma di progettazione del software che postula la progettazione congiunta di codice e asserzioni. Il design per contratto è stato proposto da Meyer ed è pienamente supportato dal linguaggio di programmazione Eiffel. A differenza dei linguaggi di specifica generali, come Z, le specifiche in Eiffel, chiamate contratti, sono fuse nel codice sorgente e definiscono obblighi e benefici dei componenti software che comunicano attraverso interfacce ben progettate. Nei linguaggi che supportano i contratti, gli obblighi e i benefici del cliente sono espressi come pre e postcondizioni dei fornitori di servizi. Il codice sorgente è arricchito con invarianti che rappresentano proprietà di stato che devono essere mantenute durante ogni interazione.

I contratti sono stati estesi a molti linguaggi. iContract è stato il primo strumento a supportare i contratti in Java. In iContract, i contratti sono scritti come commenti al codice con tag speciali. I contratti supportati da iContract sono espressioni booleane conformi alla sintassi Java, ad eccezione di alcune estensioni sintattiche che includono la quantificazione universale (∀), la quantificazione esistenziale (∃), e l’implicazione (→). Queste estensioni sono progettate per semplificare la loro traduzione nel codice Java. Per esempio, the syntax of ∀ is forall < Class >< var > in < Enum >< Exp_var >, where < Class > is the type of the variable < var >, which represents an element of < Enum >. A reasonable translation of the ∀ expression is to use a Java loop to iterate over the enumeration < Enum > and evaluate the boolean expression < Exp_var > in each iteration. The existential quantification is translated similarly. An implication expression C implies I can be simply translated into an if statement: “se C allora controlla I.”

Oltre alla semplice traduzione delle espressioni booleane, iContract affronta questioni relative al ciclo di vita degli oggetti, lo scopo delle variabili e l’ereditarietà, la maggior parte delle quali sono specifiche della programmazione orientata agli oggetti. Le regole più importanti relative al ciclo di vita degli oggetti sono le seguenti:

Nella costruzione di un oggetto, le precondizioni devono essere controllate all’inizio della costruzione, mentre le invarianti e le postcondizioni sono controllate solo se la costruzione termina normalmente (senza eccezioni).

Per le normali invocazioni di metodi sugli oggetti, le pre e postcondizioni sono controllate all’entrata e all’uscita dei metodi invocati, e le invarianti non sono controllate per i metodi privati.

Nella distruzione degli oggetti, non è richiesto alcun controllo. Quindi, nessun codice di controllo è inserito nei metodi finalize().

I predicati usati nelle postcondizioni spesso si riferiscono sia al valore di ritorno del metodo che al “vecchio” valore (o “entry-value”) di alcune variabili. iContract sintetizza una pseudo-variabile, chiamata return, per rappresentare il valore di ritorno, memorizza i valori delle variabili all’ingresso, e li rende accessibili come i nomi delle variabili con il postfix @pre. espressioni, i loro riferimenti agli oggetti sono memorizzati direttamente. iContract permette chiamate ai metodi membri nei contratti. Come risultato, ci possono essere potenziali ricorsioni infinite nel controllo degli invarianti. Per risolvere questo problema, iContract tiene traccia della profondità di ricorsione per ogni oggetto all’interno di ogni thread e controlla solo le invarianti con profondità 0. I meccanismi di estensione dei tipi in Java hanno diverse implicazioni su come i contratti dei tipi dovrebbero essere gestiti. iContract propaga i contratti seguendo queste regole:

Le invarianti sono congiunte, cioè l’invariante di un sottotipo è la congiunzione delle invarianti di tutti i suoi supertipi.

Le postcondizioni sono congiunte, cioè la postcondizione di un sottotipo è la congiunzione delle postcondizioni di tutti i suoi supertipi.

Le precondizioni sono disgiunte, cioè la precondizione di un sottotipo è la disgiunzione delle precondizioni di tutti i suoi supertipi.

JML è un popolare linguaggio di specifiche comportamentali che supporta il Design by Contract in Java. I contratti JML sono sotto forma di commenti speciali in Java. JML esprime precondizioni, postcondizioni e invarianti come espressioni booleane precedute dalle parole chiave requires, ensures e invariant, rispettivamente, e usa il metodo built-in \ old(x) per rappresentare il valore di x prima di un’operazione. Simile alla notazione ▵ in Z, JML fornisce la parola chiave modifies per indicare le variabili che vengono cambiate nel corpo di un metodo. Inoltre, JML tratta diverse caratteristiche orientate agli oggetti, come la visibilità e l’ereditarietà.

JML è la base di molti approcci alla generazione di oracoli di test. Bhorkar ha proposto una tecnica per tradurre i contratti JML in asserzioni Java. Anche se supporta solo le precondizioni, questa tecnica affronta i problemi relativi alle variabili di sola specificazione, il raffinamento, l’ereditarietà delle specifiche e la privacy. Simile a iContract, la tecnica gestisce l’ereditarietà dei contratti congiungendo e disgiungendo i contratti secondo i loro tipi. La tecnica utilizza anche una tabella hash (per thread) per evitare ricorsioni nel controllo di runtime. Le espressioni che usano quantificatori sono considerate non eseguibili dalla tecnica, e non viene generato codice Java per tali espressioni.

Korat ha proposto una tecnica per generare sia casi di test che oracoli dalle specifiche JML. La tecnica di Korat genera casi di test da precondizioni e invarianti e oracoli da postcondizioni e invarianti. Araujo et al. hanno esteso JML aggiungendo contratti concorrenti e hanno proposto un supporto runtime per consentire il controllo runtime delle asserzioni che specificano le proprietà concorrenti.

Peters e Parnas hanno introdotto un approccio per generare oracoli di test dalla documentazione formale. La documentazione è data in una forma tabellare che consiste in relazioni che specificano le interfacce delle procedure e viene tradotta in oracoli in codice C e C++. L’elemento centrale della documentazione formale consiste in espressioni di predicati scritte in una variante della logica dei predicati con costrutti speciali per trattare le funzioni parziali. Simile ad altre tecniche di oracolo basate sulle specifiche, questa tecnica tratta i quantificatori limitandoli ad insiemi finiti.

Per permettere iterazioni su insiemi di elementi con quantificatori, Peters e Parnas introducono predicati definiti induttivamente. Per un insieme S (da usare nelle quantificazioni), un predicato induttivamente definito P è definito con tre elementi I, G e Q. L’insieme iniziale I contiene un numero finito di elementi, G è una funzione, chiamata “funzione generatrice”, che genera gli elementi dell’insieme, e Q è un predicato che caratterizza le proprietà dell’insieme. L’insieme S è definito come l’insieme minimo costruito nei passi induttivi seguenti:

S0 = I

Sn + 1 = Sn ∪ {G(x)|x ∈ Sn ∧ Q(x)}

I, G e Q devono essere definiti per soddisfare una condizione speciale che assicura che l’insieme costruito S sia finito.

Peters e Parnas propongono un approccio per tradurre le documentazioni tabulari in codice C . Poiché la forma delle espressioni usate nelle documentazioni è ben definita, la traduzione è fatta sistematicamente.

Altre specifiche basate sugli stati sono anche usate per derivare gli oracoli di test. I modelli UML sono generalmente informali; tuttavia, Bouquet et al. hanno definito un sottoinsieme di UML 2.1, chiamato UML-MBT, che è abbastanza preciso per generare automaticamente casi di test. UML-MBT include diagrammi di classe, macchine di stato e un sottoinsieme di OCL 2.0. Bouquet et al. usano specifiche scritte in VDM-SL per generare oracoli di test.