KeYmaeraX: tutorial PROSSIMO Progettazione, sviluppo e ottimizzazione di sistemi intelligenti multi-oggetto

(1)

KeYmaeraX: tutorial

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”

1 / 99

(2)

Schema del tutorial

1 Panoramica su KeYmaera X

Obiettivo del tutorial e introduzione ai sistemi cyber-fisici (CPS)

2 Logica differenziale dinamica Programmi ibridi

Esempi

Logica dei sistemi ibridi Esercitazione: specificare CPS

3 Assiomi dinamici per sistemi dinamici Assiomatica

Prove dL in KeYmaera X Esempi

4 Invarianti differenziali per equazioni differenziali Completezza

Assiomatica Esempi

2 / 99

(3)

Schema del tutorial

Esempi

Assiomatica Esempi

3 / 99

(4)

Domande sulla correttezza nella progettazione di CPS

Safety Il sistema deve essere sicuro in ogni circostanza Liveness Il sistema deve raggiungere un determinato obiettivo Come possiamo rendere sicuri i sistemi cyber-fisici?

Test approfonditi? Revisioni del codice? Quando abbiamo finito?

Quanti casi di test sono sufficienti? Abbiamo coperto tutti i test?

4 / 99

(5)

Vantaggi dei fondamenti logici per la Verifica e la Validazione (V & V) di CPS

Dimostrazioni

Safety Formalizzare le proprietà del sistema: che cos’è “Sicuro”?

“Raggiunge l’obiettivo”?

ModelsFormalizzare i modelli di sistema, chiarire il comportamento Assumptions Rendere le ipotesi esplicite piuttosto che silenziose PredictionsL’analisi di sicurezza prevede il comportamento per infiniti casi

ConstraintsRivelare invarianti, condizioni di commutazione, condizioni operative

DesignInvarianti/prove guidano la progettazione di controller sicuri

5 / 99

(6)

Vantaggi dei fondamenti logici per la Verifica e la Validazione (V & V) di CPS [continua]

Sottoprodotti

Analisi Determinare tempestivamente compromessi di progettazione e fattibilità

Sintesi Trasforma i modelli in codice e in monitor per la sicurezza Strumenti

KeYmaera X aXiomatic Tactical Theorem Prover per CPS

6 / 99

(7)

Un aXiomatic Tactical Theorem Prover per CPS

7 / 99

(8)

Microkernel di KeYmaera

8 / 99

(9)

Usare KeYmaera X per:

1 Modellare sistemi cyber-fisici

2 Esprimere le proprietà di sicurezza/correttezza

3 Trovare bug nella progettazione di un sistema

4 Identificare i vincoli di sicurezza

5 Identificare le invarianti di sistema

6 Verificare il progetto finale del sistema

7 Scrivere tattiche di prova automatizzate

8 Provare le equazioni differenziali

9 Sintetizzare i monitor di runtime corretti per costruzione

9 / 99

(10)

Analisi di CPS

Nozione generale (Logica differenziale dinamica)

10 / 99

(11)

Analisi di CPS

11 / 99

(12)

Analisi di CPS

12 / 99

(13)

Schema del tutorial

Esempi

Assiomatica Esempi

13 / 99

(14)

Programmazione di CPS

Programmare CPS 6= programmare parte cyber k programmare parte fisica Definizione (Programma ibrido)

14 / 99

(15)

15 / 99

(16)

16 / 99

(17)

Runaround Robot

17 / 99

(18)

Runaround Robot

Esempio (Runaround Robot)

18 / 99

(19)

Runaround Robot

19 / 99

(20)

Runaround Robot

20 / 99

(21)

Runaround Robot

21 / 99

(22)

Runaround Robot

22 / 99

(23)

Runaround Robot

23 / 99

(24)

Runaround Robot

24 / 99

(25)

Runaround Robot

25 / 99

(26)

Runaround Robot

26 / 99

(27)

Runaround Robot

27 / 99

(28)

Runaround Robot

28 / 99

(29)

Runaround Robot

29 / 99

(30)

Runaround Robot

30 / 99

(31)

Logica per le specifiche di CPS: d L

Definizione (programma ibrido)

Definizione (logica differenziale dinamica)

31 / 99

(32)

32 / 99

(33)

33 / 99

(34)

34 / 99

(35)

35 / 99

(36)

36 / 99

(37)

37 / 99

(38)

38 / 99

(39)

Slide title

Definizione (semantica di un programma ibrido) (J·K : HP → ℘(S × S ))

Definizione (semantica d L) (J·K : Fml → ℘(S ))

39 / 99

(40)

Bouncing Ball

Esempio (Bouncing Ball)

40 / 99

(41)

Bouncing Ball

41 / 99

(42)

Bouncing Ball

Non se g <0 in antigravità Esempio (Bouncing Ball)

42 / 99

(43)

Bouncing Ball

43 / 99

(44)

Bouncing Ball

Non se c> 1 per anti-smorzamento Esempio (Bouncing Ball)

44 / 99

(45)

Bouncing Ball

45 / 99

(46)

Bouncing Ball

Non se v> 0 arrampicata iniziale Esempio (Bouncing Ball)

46 / 99

(47)

Bouncing Ball

47 / 99

(48)

Bouncing Ball

Non se v 0 dribbling iniziale Esempio (Bouncing Ball)

48 / 99

(49)

Bouncing Ball

49 / 99

(50)

Schema del tutorial

Esempi

Assiomatica Esempi

50 / 99

(51)

Prove per CPS

semantica composizionale ⇒ prove composizionali

51 / 99

(52)

Prove per CPS

52 / 99

(53)

Prove per CPS

53 / 99

(54)

Prove per CPS

54 / 99

(55)

Prove per CPS

55 / 99

(56)

Logica differenziale dinamica: Assiomatizzazione

56 / 99

(57)

KeYmaera X

Affidabile

Uniform substitution Sound & complete Small core: 1700 LOC

Flessibile

Prove automatiche UI interattiva Programmabile

Personalizzabile Scala + Java API Linea di comando REST API

57 / 99

(58)

KeYmaera X Microkernel (1700 Linee Di Codice)

58 / 99

(59)

Schema del tutorial

Esempi

Assiomatica Esempi

59 / 99

(60)

Assiomatizzazione dell’equazione differenziale

Approccio classico: 1 Data una ODE 2 Risolve la ODE 3 Analizza la soluzione

Potenza descrittiva: l’ODE è molto più semplice della sua soluzione Analizzare le ODE tramite le soluzioni annulla il potere descrittivo!

1 Fondamenti logici degli invarianti di equazioni differenziali

2 Decidere l’invarianza tramite una prova dL

non ha una soluzione elementare in forma chiusa

60 / 99

(61)

Proprietà delle Equazioni differenziali

Concetto(Logica Differenziale Dinamica)

61 / 99

(62)

Completezza per invarianti di equazioni differenziali

62 / 99

(63)

Assiomatizzazione dell’equazione differenziale

Teorema (Completezza Algebrica)

Il calcolo d L è un’assiomatizzazione sound & complete di invarianti algebrici di equazioni differenziali polinomiali. Sono decidibili tramite DI, DC, DG

Teorema (Completezza Semialgebrica)

Il calcolo d L con RI è un’assiomatizzazione sound & complete di invarianti semialgebrici di equazioni differenziali. Sono decidibili in d L

63 / 99

(64)

Invarianti Differenziali per Equazioni Differenziali

64 / 99

(65)

65 / 99

(66)

66 / 99

(67)

67 / 99

(68)

68 / 99

(69)

69 / 99

(70)

70 / 99

(71)

71 / 99

(72)

72 / 99

(73)

73 / 99

(74)

se g (x, y ) = a(x)y + b(x), ha una soluzione lunga!

74 / 99

(75)

75 / 99

(76)

76 / 99

(77)

77 / 99

(78)

78 / 99

(79)

79 / 99

(80)

80 / 99

(81)

Tagli Differenziali per Equazioni Differenziali

81 / 99

(82)

82 / 99

(83)

83 / 99

(84)

84 / 99

(85)

85 / 99

(86)

86 / 99

(87)

87 / 99

(88)

88 / 99

(89)

89 / 99

(90)

90 / 99

(91)

91 / 99

(92)

Completezza per invarianti di equazioni differenziali

92 / 99

(93)

Esempio: dinamica longitudinale di un aeroplano

Studio (equazioni di volo longitudinale del 6^o ordine)

93 / 99

(94)

Esempio: dinamica longitudinale di un aeroplano

Studio (equazioni di volo longitudinale del 6^o ordine)

DRI genera automaticamente funzioni invarianti

94 / 99

(95)

Esempio: dinamiche Dubins di 2 aeroplani

DRI genera automaticamente invarianti

95 / 99

(96)

Esempio: Problema dei due corpi di Keplero

96 / 99

(97)

Esempio (problema dei due corpi)

97 / 99

(98)

98 / 99

(99)

99 / 99