Progettazione e modellazione di sistemi basata su contratti
PROSSIMO
Progettazione, sviluppo e ottimizzazione di sistemi intelligenti multi-oggetto
Azioni Cluster “Top Down”
Progetto finanziato con fondi POR FESR 2014/2020
ASSE PRIORITARIO I “RICERCA SCIENTIFICA, SVILUPPO TECNOLOGICO E INNOVAZIONE”
Decomposizione gerarchica
Sistema A
Il sistema A viene decomposto nei sottosistemi B e C
Il sottosistema B viene decom- posto nelle apparecchiature D ed E
La decomposizione gerarchica preserva le porte
Specifica dei componenti con contratti
Un componente è immerso in un ambiente
Il suo comportamento è specifica- to da contratti
Contratto: assunzioni + garanzie Assunzioni: cosa dovrebbe fare l’ambiente verso il componente Garanzie: cosa deve fare il componente
Controllo anticipato dei requisiti
Specificare i componenti durante la progettazione
decomposizione delle specifi- che in base alla decomposizio- ne dell’architettura
Garantire la correttezza della decomposizione
Il contratto di A deriva dai contratti di B e C?
Riutilizzo dei componenti
Libreria di componenti affidabili es. la SRA dell’ESA
Implementazione + contratti Integrabile?
confrontare i contratti!
Correttezza per costruzione!
Ulteriori vantaggi
Segue il processo di sviluppo strutturato Esempio, dominio aerospaziale Fornisce supporto formale
Da informale a formale (“gap semantico”) Supporto automatico anticipato
Non sono richiesti modelli di comportamento dettagliati Sfrutta la decomposizione per la scalabilità
Nessuna analisi monolitica intrinsecamente incrementale
Le modifiche locali non influiscono sull’intera decomposizione
Elementi per la “visione formale”
Un linguaggio formale per speci- ficare i contratti
Logiche Temporali
Un framework per il corretto raffinamento del contratto
Obbligo di prova
Conseguenza logica delle for- mule logiche temporali Un linguaggio formale per speci- ficare l’implementazione
Macchine a stati finiti Verifica dell’implementazione
Linguaggi di specifica delle proprietà
Linguaggi di specifica delle
proprietà
Proprietà
Le proprietà sono espressioni in una logica matematica che utilizza simboli della descrizione del sistema.
Utilizzato per formalizzare i requisiti.
Spesso più vicino alle descrizioni informali che comportamentali Ogni proprietà è associata all’insieme del comportamento del sistema.
Problemi:
Specifica: definire le proprietà di un sistema.
Verifica: controlla se il sistema soddisfa le proprietà.
Convalida: controlla se stiamo considerando le giuste proprietà.
Sintesi: costruire un sistema che soddisfi le proprietà.
Proprietà, tracce e logica
Logica Temporale Lineare (LTL)
Modelli lineari
Tracce come sequenze di stati Costruito su proposizioni atomi- che
Utilizzo di connettori booleani E operatori temporali
Esempi LTL
Gp
“sempre p” – invariante G (p → Fq)
“p è sempre seguito da q” – reazione G (p → Xq)
“ogni volta che p è verificato, q è assegnato a true nel ciclo successivo reazione immediata
GFp
“infinite volte p” – fairness FGp
“alla fine in modo permanente p”
G (p → (q U r ))
Esempio di implicazione semplice
Date le seguenti formule G (request → F (received )) G (received → F (processed )) G (processed → X (grant)) Da cui possiamo implicare
G (request → F (grant))
Operatori “Past”
Y p:
“nello stato precedente p”
Duale dell’operatore next X O p
“In passato una volta p”
Duale dell’operatore eventually F H p
“In passato sempre p”
Duale dell’operatore always G p S q (p since q)
“in uno stato precedente p, e da allora q”
Duale dell’operatore until U
Espressioni regolari
RELTL arricchisce LTL con espressioni regolari:
Implicazione del suffisso {r } |→ p significa che ogni sequenza finita corrispondente a r è seguita da un suffisso corrispondente a p
La congiunzione del suffisso {r } → p significa che esiste una sequenza finita corrispondente a r seguita da un suffisso corrispondente a p Esempi
{{¬p}[∗]; p}[∗3] |→ q
G ({request; busy [∗]; grant} |→ response)
Base formale per il linguaggio di descrizione hardware PSL
Da finito a infinito
Usa predicati del primo ordine anziché proposizioni G (x ≥ a ∨ x ≤ b)
GF (x = a) ∧ GF (x = b)
Predicati interpretati secondo la teoria specifica T (da qui in poi, ven- gono utilizzati solo i reali)
Operatore “next” per esprimere cambiamenti/transizioni:
G (next(x ) = x + 1) G (next(a) − a ≤ b)
Logica temporale metrica
G (p → F≤3q)
“p è seguito da q entro 3 unità di tempo”
G (p → G≤20q)
ogni volta che si verifica p, allora q vale nelle seguenti 20 unità di tempo”
G (p → (¬q U≥5q))
“p è seguito da q ma non prima di 5 unità di tempo”
HRELTL: RELTL ibrido
G (der (x ) < 2)
“la derivata di x è sempre inferiore a 2”
G (a → der (x ) = 0)
ogni volta che si verifica a, la derivata di x è 0”
G (a → (b U der (x ) ≤ 5))
“Ogni volta che si verifica a, b rimane vero fino a quando la derivata di x è minore o uguale a 5”
G (speed > limit → F (warning ))
Othello
Linguaggio leggibile dall’uomo per HRELTL Espressioni di linguaggio naturale controllate Sviluppato nel progetto EuRailCheck
Finanziamento da parte dell’Agenzia ferroviaria europea Formalizzazione e convalida dei requisiti ETCS
Convalida basata sulla modellazione da parte di ingegneri delle specifiche
Progettazione basata su componenti
Progettazione basata su
componenti
Componente
Un componente ha:
Un’interfaccia sintattica
Opzionalmente, una struttura interna Un comportamento
Un ambiente Proprietà
Interfaccia componente a scatola nera
Un’interfaccia del componente definisce il confine dell’interazione tra il componente e il suo ambiente.
Consiste di:
Set di porte di input e output (sintassi)
Le porte rappresentano dati visibili ed eventi scambiati con l’ambiente.
Set di tracce (semantica)
Le tracce rappresentano il comportamento, la cronologia degli eventi e i valori sulle porte dati.
Struttura del componente a scatola trasparente
Un componente ha una struttura interna.
Vista dell’architettura:
Sottocomponenti Interconnessioni Delegazioni
Vista macchina a stati:
Implementazione dei componenti
IS: porte di input del componente S OS: porte di output di S
VS = IS ∪ OS: tutte le porte di S Tr (X ) tracce di X ⊆ VS
Sequenza di assegnazioni a X
Macchina a stati Imp implementazione di S se e solo se L(Imp) ⊆ Tr (VS)
M può essere associato a µImp : Tr (IS) → 2Tr (OS) tale che µImp(σi) = {σ0 | σi ∈ L(Imp)}
Traccia di input mappata ad un set di tracce di output Set usato per considerare il non determinismo
Il set vuoto corrisponde alla traccia di input rifiutata
Ambiente dei componenti
Macchina a stati Env ambiente di S se e solo se L(Env ) ⊆ Tr (IS) Compatibilità dell’implementazione con l’ambiente (ad es. per il riuti- lizzo)
Vista basata sulla traccia (scatola nera):
Imp deve accettare qualsiasi traccia di Env L(Env ) ⊆ {σ | µImp(σ) 6= ∅}
Vista basata sullo stato (scatola trasparente):
Per qualsiasi stato raggiungibile di Imp × Env , per qualsiasi transizione di input di Env , esiste una transizione corrispondente di Imp
Come nella teoria dell’interfaccia
(notare che Imp × Env è un sistema chiuso )
Componenti e collegamenti compositi
I componenti sono composti per creare componenti compositi.
Diversi tipi di composizioni:
Sincrona, Asincrona, Sincronizzazioni,
Rendez-vous contro buffered
Pairwise, multicast, broadcast, multicast con un ricevitore
Mappa delle connessioni (regola generale dei linguaggi architetturali):
Porte di input del componente composito Porte di output dei sottocomponenti in
Porte di input dei sottocomponenti.
Porte di output del componente composito
Architettura di sistema
Un componente è in realtà un tipo di componente
Un’architettura di sistema è un’istanza di un componente composito.
Definisce un albero di istanze del componente.
Progettazione basata su contratti con logiche temporali
Progettazione basata su contratti
con logiche temporali
Contratti
Proprietà del componente e del suo ambiente.
Può essere visto come asserzioni per le interfacce dei componenti.
I contratti vengono utilizzati per caratterizzare la correttezza delle im- plementazioni e degli ambienti dei componenti.
In genere, le proprietà per il Model Checking hanno una vista “comple- tamente osservabile” dell’interno del sistema
Per i componenti invece:
Limitato alle interfacce dei componenti.
Struttura rappresentata tramite assunzioni e garanzie.
I contratti per la programmazione Orientata agli Oggetti sono pre/post- condizioni
Contratti basati sulla traccia
Asserzioni utilizzate per rappresentare insiemi di tracce sulle porte dei componenti:
Φ(V ) asserzione sulle variabili V hhΦii ⊆ Tr (V ) semantica di Φ
Un contratto del componente S è una coppiadi asserzioni <A,G> su VS
A è l’assunzione G è la garanzia
Env è un ambiente corretto se e solo se L(Env ) ⊆ hhΦii Imp è un’implementazione corretta se L(Imp) ∩ hhAii ⊆ hhG ii
Raffinamento: obblighi di prova
Dato il contratto C = <A,G> per un componente
Dati i contratti C1 = <A1,G1> , ..., <An,Gn> per i sottocomponenti Obblighi di prova per “{Ci} raffina C ”:
Cosa significa?
Focalizziamoci sulle proprietà del componente padre
Il contratto della componente padre A → G deve seguire i contratti dei sottocomponenti
Visione alternativa:
Cosa significa? [continua]
Focalizziamoci sull’i-esimo sottocomponente
Le assunzini dell’i-esimo sottocomponente devono derivare dai contratti degli altri sottocomponenti più le assunzioni della componente padre
Obblighi di prova
Gli obblighi di prova sono necessari e sufficiente per un corretto raffina- mento del contratto
Estensione per gestire la composizione asincrona Problema chiave: informazioni diagnostiche!
In caso di violazione, traccia
Localizzazione mediante metodi basati su prove estrazione di un core non soddisfacibile
Assunzioni deboli vs. forti
Assunzioni deboli vs. forti (entrambe importanti) Assunzioni deboli
Definire il contesto in cui è assicurata la garanzia Come nel ragionamento assunzione-garanzia
Diverse coppie di assunzione-garanzia potrebbero avere ipotesi incoerenti (sex > 0 allora ..., se x < 0 allora ...)
Assunzioni forti
Definire le proprietà che devono essere soddisfatte dall’ambiente.
Idea originale di progettazione basata su contratto.
Se non soddisfatto, l’ambiente può causare un guasto (divisione per zero, mancanza di energia, collisione).
Ragionamento assunzione-garanzia
Corrisponde ad una direzione del raffinamento del contratto
Molti lavori si concentrano sulla ricerca della giusta assunzione/garanzia Per esempio, come interrompere la circolarità
Meccanismi basati sull’induzione
Si noti che sono modi strutturali per dimostrare il raffinamento basato sulla proprietà
OCRA come strumento di supporto
OCRA come strumento di
supporto
OCRA come strumento di supporto
OCRA=Othello Contract Refinement Analysis Asserzioni sui contratti specificate in Otello.
Rappresentazione testuale dell’architettura.
Costruito su nuXmv per il model checking a stati infiniti Integrato con altri strumenti
Uno dei pochi strumenti a supporto della progettazione basata su con- tratto per sistemi embedded.
Disponibile pubblicamente (per scopi non commerciali) all’indirizzo https://es.fbk.eu/tools/ocra
Principali caratteristiche di OCRA
Interfacce di componenti ricche per specificare:
Porte di Input/Output Porte per Dati/Eventi
Comprende aspetti in tempo reale e di sicurezza.
Contratti in logiche temporali.
Formule temporali utilizzate per caratterizzare un insieme di tracce sulle porte dei componenti.
Linguaggio di OCRA
Interfaccia componente
Contratti in Othello
Raffinamento dei componenti
Raffinamento dei contratti
Esempio completo
Esempio completo [continua]
OCRA: una vista parametrizzata
Il flusso implementato in OCRA è parametrico Sono supportate molteplici logiche
Le tracce possono essere discrete o ibride Funzionalità richieste
Implicazione logica
Aspetti ibridi di OCRA
I tipi di porta possono essere
Tipi finiti: “booleani”, “enumerativi”, ...
Tipi infiniti: “reali”, “interi”, ...
Tipo “continuo”: porte a valore reale costrette ad evolversi continuamen- te nel tempo
Tipo “evento”: porte con valore booleano assegnate solo su transizioni discrete
Le formule atomiche possono essere:
Variabili booleane.
Uguaglianze.
Predicati aritmetici su termini interi, reali e continui.
Operatori temporali: come in LTL e HRELTL
Funzionalità
Verifica della sintassi Verifica del raffinamento
Genera tutti gli obblighi di prova ed esegue la verifica delle implicazioni Verifica della consistenza
Ci sono assunzioni/garanzie incoerenti?
Verifica dell’implementazione
L’implementazione dei componenti soddisfa i contratti?
Verifica della ricettività
L’implementazione dei componenti è in grado di reagire ad ogni input dell’ambiente?
Risultati della verifica del raffinamento
Per ogni componente, per ogni contratto raffinato, verifica il raffina- mento.
Per ogni obbligo di prova, verifica la validità:
[OK] se valido
[BOUND OK] se nessun controesempio viene trovato fino a k [FAIL] se viene trovato un controesempio
