La Network survivability, in italiano, sopravvivenza di rete è la possibilità che, in seguito ad una o più eventi critici, il sistema continui a funzionare per quello che è stato progettato.

Intendendo sempre la rete come un insieme di nodi e di servizi, allo scopo di questa analisi gli eventi saranno mappati su qualunque occorrenza accada nella rete (evento utente, evento interno, evento di comunicazione, fault). Col termine servizio ci si riferisce invece a una qualunque attività che è prevista essere iniziata da uno start event e terminata da un end event. La Survivability analysis può essere di grande aiuto sia in fase progettuale, sia in fase di review post-facto della rete, per trovarne i punti deboli, meno affidabili, od i colli di bottiglia.

Tre gli aspetti che il modello è in grado di descrivere:

1. L'effetto che una fault può avere sul sistema
2. L'affidabilità del sistema, intesa come la probabilità che il servizio iniziato termini correttamente
3. La convenienza costo-beneficio del sistema, ossia la valutazione di quali componenti siano meglio aggiornabili in termini di rapporto costo/beneficio.

Perché questa analisi sia corretta, è necessario in primo luogo analizzare tutti i possibili casi di failure accidentali e maliziose, e pesarne l'importanza all'interno della rete (ad esempio, un BOF su un server centrale ha sicuramente peso maggiore che il reboot di una macchina periferica di un qualche utente). Si introduce inoltre, a differenza di quanto visto finora, la dipendenza tra gli eventi (in particolare gli eventi che portano a una fault). Questo significa che l'accadimento di un evento può rendere più probabile l'accadimento di un secondo, distaccato ma dipendente, evento. È in questo modo possibile, inoltre, modellare quelli che sono definiti come attacchi correlati, ossia tentativi sequenziali di attacco che singolarmente non hanno effetto ma che insieme sono in grado di compromettere una risorsa od un servizio (es: DDoS). L'analisi dovrebbe essere fatta a seconda dei servizi che la riguardano, e dunque essere costruita sullo scopo della rete (o parte di essa) che si vuole analizzare.

Nel Markov Decision Process (MDP), gli agenti che perpetuano il processo cercano di trovare delle policy, e quindi di effettuare delle scelte, che portino a massimizzare un obiettivo dato. Quando però gli obiettivi sono più d'uno, magari conflittuali, bisogna ricorrere a un framework diverso, appunto CMDP.

Nel modello CMDP, le probabilità delle transizioni dipendono dalla storia h delle stesse. Un CMDP è composto da 5 tuple:

• Uno spazio degli stati finito e discreto, S
• Un set finito di azioni A, dove A(s) indica l'insieme di azioni disponibili per lo stato s.
• Probabilità di transizione tra gli stati, P
• Il costo immediato di un'azione, descritto come c(s,a) è il costo di prendere la decisione di azione a quando si è nello stato s
• Un vettore di costi immediati d

Una policy u è una regola di decisione che tiene in considerazione la storia della rete, e determina l'azione successiva all'istante; la notazione per cui la policy u al tempo t intraprende l'azione a è

${\displaystyle u=(a|ht)\,}$

Una policy u definisce il costo delle azioni che vengono intraprese se la policy u viene applicata allo stato iniziale s. Analogamente, d è il costo immediato dell'intraprendere una policy u partendo da s. è un vettore k-dimensionale referenziato da un altro vettore C che indicizza i costi di ogni elemento i di, permettendo di effettuare il confronto tra i vari costi delle policy così da poter scegliere tra tutte quelle possibili quella più conveniente, per poter ottenere il valore di minore.

Il modello proposto ed in analisi prevede che sia nodi che archi vengano rappresentati come macchine a stati che comunicano attraverso variabili condivise. La composizione di queste macchine a stati (nodi e link) crea il modello della rete.

Come anticipato, in questo caso sia i nodi che i link sono da considerare con affidabilità <1, e dunque non perfetti: questo riassume il concetto di link in quello di nodo, configurando di fatto un modello in cui i link altri non sono che nodi che fungono da tramite per la comunicazione tra due nodi a loro periferici. Per studiare come la rete reagisca ad un fallimento, questo va inserito nel modello; chiaramente, ogni diversa applicazione a cui la rete è rivolta comporta un comportamento diverso del nodo che fallisce (si ricorda che l'analisi è service-dependant). Le fault vengono rappresentate da una variabile chiamata fault, inserita in ogni nodo della rete, che può assumere 3 diversi valori: {normal, failed, intruded}. A seconda del valore assunto dalla variabile fault, il comportamento del nodo varia (modi operativi): il comportamento che ogni nodo assume a seconda del modo operativo in cui si trova al tempo t è deciso in fase progettuale dall'architetto della rete. È anche possibile, nel modello, prevedere che le transizioni di stato siano del tutto non-deterministiche. Sebbene il comportamento di ogni nodo è relativo all'applicazione contestuale in cui si trova inserito, almeno due sono i comportamenti comuni a tutte le applicazioni:

• Stuck-at-fault: il nodo è stato compromesso dalla failure, non accetta alcun input e dunque non produce alcun output (Logical Stuck Fault Model – Stuck at 0, Stuck at 1)
• Byzantine fault: il nodo entra in uno stato non consistente in cui commette errori in maniera non prevedibile, comportandosi in maniera completamente non deterministica.

Da questo punto di vista, una byzantine fault può essere usata per modellare un nodo che è ha subito un'intrusione {intruded}.

La survivability è definita dall'architetto della rete che specifica della proprietà ad essa inerenti utilizzando la logica formale, di qualunque tipo essa voglia essere. Due le classi di proprietà definibili nel modello: proprietà relazionate alle fault, e proprietà relazionate ai servizi.

• Fault related properties: questo tipo di proprietà specificano quale debbano essere le restrizioni del comportamento assunto da un nodo che entra in uno stato di fault. Ad esempio, un progettista potrebbe specificare come proprietà per la survivability che non sia possibile per un nodo N raggiungere uno stato non-sicuro se il network parte da uno stato iniziale. La comodità della logica formale è che ogni proposizione atomica, negata o affermata, può assumere una varietà di significati semantici a discrezione del progettista, così da poter modellare facilmente anche proprietà particolari o complesse.

• Service related properties: le proprietà relative ai servizi riguardano l'esecuzione di questi e le caratteristiche che devono assicurare: ad esempio, se un servizio parte è necessario che alla fine della sua esecuzione questo necessariamente termini, senza eccezioni. Meno sinteticamente, per tutti gli stati da cui un servizio può partire, e per tutti i percorsi che partono da quei nodi, esiste uno stato in cui il servizio termina sempre.

AG(start → AF(finished))

Definite queste proprietà, è possibile verificare, attraverso il modello creato, se vengono rispettate, ed individuare così i nodi critici per un certo servizio.

Definito il modello M della rete composto dalle macchine a stati rappresentati ogni nodo, e identificate le proprietà P il passo successivo è ottenere uno grafo dello scenario, in cui ti tiene conto di tutte le tracce di M rispettando P. Due grafi in particolare sono ottenibili da questo: fault scenario graph è un grafo in cui si rappresentano tutte le tracce che terminano in uno stato unsafe. Un service success/failure scenario graph rappresenta invece tutte le tracce che portano un servizio a terminare/non terminare.

Il grafo ottenuto è soggetto a diversi tipi di analisi, tra cui quella per l'affidabilità e il ritardo della comunicazione. In primo luogo è necessario che il progettista specifichi le probabilità di accadimento degli eventi più significativi che possono accadere nel sistema (faults). Essendo queste probabilità non indipendenti tra di loro, l'analisi avviene attraverso Bayesian Networks, grafi orientato aciclici in cui ogni nodo rappresenta una variabile (dunque, evento) ed un arco ne identifica la relazione con un altro nodo: è così possibile rappresentare la probabilità condizionale di accadimento degli eventi. Nel formalismo dei bayesian network, se un evento A dipende da un set di eventi, è necessario specificare la probabilità che avvenga A per ogni coppia di set di eventi. Ad esempio, se A dipende da {E1,E2}, bisognerà specificare P(A|A1,A2), P(A|A1,!A2), P(A|!A1,A2), P(A|!A1,!A2).

Non essendo necessariamente tutte le transizioni deterministiche, il progettista non è costretto a rappresentare tutte le probabilità in gioco, ma solo quelle di interesse per lo scopo dell'analisi. Le probabilità di funzionamento/rottura dei nodi, dunque, cambiano a seconda dello scenario.

Il calcolo dell'affidabilità avviene valutando i costi degli archi e il “tipo” di stato in cui questi archi portano. Ricordando il servizio essere il punto centrale dell'analisi, si assegna un valore V(s)=1 a tutti gli stati che soddisfano la condizione finished. A tutti i rimanenti, si assegna V(s)=0. L'algoritmo per trovare V*, ossia la funzione della policy ottimale, è denominato policy iteration ed è specifico degli scenari MDP.

Assumendo c(s→s') il costo dell'arco che collega lo stato s con s', e p(s,s') la probabilità del passaggio di stato (se esistente, poiché non tutte le transizioni sono necessariamente probabilistiche):

${\displaystyle min\ c(s->s')+V(s')\,}$

${\displaystyle \sum _{s'\epsilon succ(s)}p(s,s')(c(s->s')+V'(s)\,}$

Chiaramente il primo caso fa riferimento a uno stato s iniziale non deterministico, mentre il secondo ad un probabilistico.

Quando il costo associato con gli archi diventa 0 (c(s→s')=0, per qualunque coppia esistente (s,s')), V*(s) è l'affidabilità, nel caso peggiore, raggiungibile per la proprietà specificata; in altre parole, è la probabilità che, nel caso peggiore, il servizio iniziato alla fine termini.

Se c(s→s') è invece considerato essere il negativo della latenza (latenza = 30ms → costo= -30), quello che si ottiene è il peggiore tempo di esecuzione di un processo prima che questo raggiunga uno stato con finished attivata.

L'analisi costo/beneficio si prefigge invece di rilevare quali archi sia meglio aggiungere al grafo per ottenere la massima affidabilità a beneficio di un costo quanto più basso possibile. Dato che l'aggiunta degli archi non dipende dallo stato del sistema, il problema (che altrimenti sarebbe di classe NP-Hard), si riduce ad un problema di programmazione non lineare, risolvibile mediante diversi approcci euristici.

• Jia, S., and J. M. Wing. Survivability Analysis of Networked Systems. From the Carnegie Mellon Web site: https://www.cs.cmu.edu/∼wing/^{[collegamento interrotto]} (2001)
• Reliability of Computer Systems and Networks - Fault Tolerance, Analysis, and Design (Martin L. Shooman), ed. Team Fly

• Network reliability