Sartomiki.net

Implementazioni di Packet Filter
La soluzione hardware è data da un comparatore che verifica i bit. In questo modo si ha un risultato ad ogni colpo di clock, anche se è possibile verificare solo condizioni elementari. In più non è un sistema flessibile, in quanto è completamente hardwired.
La soluzione software è data da un programma che filtra i pacchetti. E' quindi necessario conoscere la sequenza di bit e, in base ai protocolli utilizzati dal pacchetto, controllare alcuni bit. Dopo aver eseguito la verifica delle condizioni si riconoscono i pacchetti. Il vantaggio principale è dato dalla grande flessibilità, a fronte però di una minore efficienza rispetto alle soluzioni hardware. Per verificare la qualità di una soluzione software esistono diversi parametri:
-efficienza, velocità di elaborazione/analisi dei pacchetti. Normalmente  i packet filtering devono lavorare su macchine molto veloci.
-sicurezza, nel senso di adattabilità in caso di pacchetti non corretti (malformati). Essi possono essere causati da errori di trasmissione oppure da attacchi esterni.
-componibilità, possibilità di inserire filtri diversi. E' necessario che riescano a trattare protocolli diversi con un numero molto limitato di confronti: se in ingresso è presente un pacchetto TCP e si impostano due filtri che usano TCP, è necessario utilizzare le informazioni in comune per decidere a quale applicazione corrisponde il pacchetto.
-velocità di aggiornamento, nel caso in cui si voglia gestire un firewall con aggiornamento dinamico delle condizioni. Questa operazione è molto comune ed è quindi necessario eseguirla velocemente. Ad esempio se si apre una sessione TCP, è importante che ci sia una condizione che permetta agli altri pacchetti della stessa sessione di essere processati velocemente.

CMU/Stanford Packet Filter (CSPF)
CSPF è il primo packet filtering, nato per consentire l'implementazione di protocolli in user space. Esso è stato implementato nel kernel 4.3 di BSD. L'applicazione doveva fornire al kernel i soli pacchetti che esso poteva comprendere. Il kernel, per mezzo di una virtual machine, eseguiva operazioni su tutti i pacchetti in ingresso in modo da filtrarli.
La struttura del software è data da un albero di condizioni booleane, detto expression tree. Il linguaggio per la gestione dei filtri CSPF è di tipo imperativo stack-based a 16bit (poichè le macchine su cui lavorava erano a 16bit). Ogni pacchetto è rappresentato con una sequenza di 16bit; questo rappresenta una grave limitazione in quanto non tutti gli header sono a 16bit (alcuni sono più lunghi altri più corti).
Per garantire la sicurezza CSPF ha un set di istruzioni limitato (stack, load da memoria, operatori logici e booleani). In più non esistono istruzioni di jump o loop, in modo da rendere impossibile l'accesso a parti di memoria esterne oppure la formazione di loop infiniti. Per una maggiore sicurezza si usa una macchina virtuale che inserisce una serie di controlli sulla correttezza del codice prima di eseguire le operazioni.
Le limitazioni di CSPF sono molteplici in quanto è un primo tentativo di packet filtering:
-non è presente la composizione di filtri.
-l'architettura a stack è difficile da implementare su macchine a registri. In teoria però facilita l'implementazione di un eventuale JIT, ma 20 anni fa non interessava.
-non permette di valutare condizioni nel caso di header di lunghezza variabile.
-si può accedere 16bit alla volta. Non più grandi (unione di più condizioni), non più piccole (mascheramento).
-non è efficiente, in quanto non ha memoria. Vengono letti più volte stessi spazi di memoria, ogni foglia dell'albero viene interpretata in modo indipendente dalle altre, neanche in situazioni di mutua esclusione.
Le idee interessanti, che poi sono state utilizzate anche per packet filter successivi sono state:
-implementazione a livello kernel.
-pila protocollare del packet filter in parallelo a quella delle reti protocollari dell'IP.
-batch processing, cioè la capacità di processare più pacchetti in parallelo. Senza batch processing sarebbe necessario un loop per ogni pacchetto.
-buffer. I risultati prodotti dal CSPF vengono messi in un buffer e messi a disposizione dell'utente. Nel momento in cui esso necessita i risultati può reperirli dal buffer e lo stesso vale per quando deve inviare i pacchetti.
-virtual machine. Essa è composta in pratica da uno switch, che va a leggere il valore puntato dal program counter (PC). Ad ogni operazione si incrementa il PC (a meno di istruzioni di jump) e si passa all'operazione successiva. Il ciclo finisce nel momento in cui non ci sono più operazioni.
-controlli sulla sicurezza. Ad ogni operazione vengono effettuati una serie di controlli per garantire la sicurezza:
--byte code non valido.
--salti non validi, cioè si va in zone di memoria al di fuori della virtual machine, in modo da non poter chiamare procedure esterne.
--numero finito di azioni.
--lettura/scrittura valida, cioè non si leggono/scrivono dati al di fuori della virtual machine.
--consumo di memoria finito.

Berkeley packet filter (BPF)
E' un sistema molto utilizzato dal 1994 ed è nato per sopperire alcune limitazioni del CSPF. Esso consentiva la creazione di tool di monitoring come tcpdump. Anche in questo caso si tratta di una virtual machine a registri con molte più funzioni utilizzabili. Un'altra importante novità è la libreria pcap che fornisce un'interfaccia per applicazioni esterne. La macchina virtuale è a 32bit e prevede la possibilità di funzionare anche a 8-16bit. Include un registro accumulatore (A), dove vanno i risultati, e un registro indice (x), che permette di accedere ai singoli bit, quindi sono possibili accessi ad offset variabile. L'instruction pointer è implicito ed è munito di una memoria per dati temporanei (anche se non è stata molto utilizzata dai tool di gestione). Esistono alcune istruzioni di jump, anche condizionato. Sono vietati i loop, per garantire la terminazione dei programmi, quindi sono previsti solo i jump in avanti. L'implementazione di default è nel kernel del sistema operativo.
Il BPF introduce un paradigma di esecuzione basato sul modello del Control Flow Graph (macchina a stati), molto simile al modello usato dall'assembler dei processori. Grazie a questa impostazione è possibile eseguire determinate operazioni in base ai risultati ottenuti durante l'esecuzione. E' quindi possibile ottimizzare le operazioni, evitando controlli inutili. Grazie alle ottimizzazioni si diminuisce il numero di operazioni per verificare tutte le condizioni e di conseguenza anche gli accessi a memoria.
BPF, come detto, incrementa le prestazioni di CSPF, anche se non elimina totalmente tutti i problemi di ridondanza (la soluzione sarà data da BPF+). In più non offre un supporto intelligente alla composizione dei filtri, nel senso che non li gestisce in parallelo. La componibilità, nel momento in cui è nato, non serviva poichè era raro avere più filtri in parallelo.
Nonostante queste limitazioni, per ragioni storiche, è ancora il packet filter più utilizzato.
Molte delle idee usate nel BPF erano già state usate nel CSPF altre sono nuove:
-implementazione in kernel mode.
-numero limitato di operazioni di read.
-batch processing.
-virtual machine basata su registri, più facile da emulare rispetto a una macchina a stack.
-implementabile su molti OS (Windows, Machintosh, Unix…).
Per realizzare il BPF viene definita una Network Tap (un aggancio del NIC driver nella scheda di rete), in modo da far sì che un pacchetto in ingresso venga introdotto nella pila di cattura in parallelo agli altri stack. In questo modo si "copia" il pacchetto di ingresso. Il pacchetto copiato viene poi passato a tutte le pile protocollari, anche se non è destinato a loro, in modo che esso venga filtrato automaticamente dagli stack.
Per ottenere questo risultato è necessario modificare i driver della scheda di rete, introducendo in essi la chiamata alla funzione bpf_tap, che rappresenta una chiamata esplicita al modulo del filtro.
Se il pacchetto filtrato soddisfa i requisiti viene copiato nello Store Buffer e successivamente nell'Hold Buffer. Il primo serve per essere riempito e nel momento in cui lo è, i pacchetti sono passati al secondo, in sola lettura.
A livello utente si vede la libpcap che è una libreria utile a implementare il codice relativo del BPF in user mode. Grazie a libpcap è possibile inserire un nuovo filtro nella macchina virtuale mediante un'interfaccia user friendly.

WinPcap
L'implementazione Windows più nota della libpcap è WinPcap, che è un clone di BPF. A livello kernel vengono inserite alcune novità:
-static mode, modalità in cui un pacchetto viene filtrato immediatamente, senza doverlo recapitare all'applicativo. In questo modo si risparmia tempo.
-packets injection, che consente l'invio di pacchetti specifici attraverso l'interfaccia di rete.
-remote capture, che permette la cattura in locale, anche su dati relativi ad un server.
-kernel buffer di qualche MB, a differenza del piccolo buffer da 4KB del BPF. In più ha una struttura circolare per poter utilizzare tutto lo spazio del buffer. Questo porta però a una perdita di tempo nel momento in cui si ha la necessità di copiare i risultati in user mode, poichè questa operazione blocca tutto il processo di filtering. L'efficienza del metodo è però garantita da una copia periodica di parti del buffer.
-NIC driver. Siccome non si possono modificare i driver, dato che in Windows sono file binari, si crea un Network Packet Filter (NPF), che appare come un protocol stack separato e che lavora in parallelo.
-All'interno di WinPcap è presente un file, denominato Packet.dll, che ha il compito di ricevere chiamate di sistema e rimapparle all'interno del kernel, in modo da poter avviare un context switching.
-La libreria Libpcap e tutte le migliorie di WinPcap sono contenute all'interno di un altro file, chiamato Wpcap.dll.
-ottimizzazione del processing e questo rende WinPcap il sistema standard più veloce in commercio.
-JIT sicuro, controllando tutte le condizioni come nel BPF.
-JIT efficiente.
-linguaggio nativo, che può essere inserito all'interno di programmi C. L'ordine in cui viene memorizzato è l'inverso rispetto a quello che avviene nella NPF. Questo problema è risolvibile mediante una macro o la funzione ntoh(). Con il JIT nativo si può avere una velocità dalle 5 alle 8 volte maggiore, che con il linguaggio interpretato.

PathFinder
E' un nuovo modello di packet filter che supporta un numero arbitrario di filtri. La visione di PathFilter determina che una serie di filtri vengono raggruppati in un unico filtro, in modo da rendere possibile la componibilità. L'idea è quella di unire i control flow graph in modo che tutti i controlli dello stesso campo si trovino nello stesso nodo del grafo non orientato. L'elemento base è la cella che identifica un campo all'interno della trama in ingresso e contiene al suo interno uno o più valori con i quali bisogna eseguire il confronto per la realizzazione del filtro. Ogni cella è descritta da una tupla: offset, length (lunghezza in byte), mask, value. Un filtro è definito da un percorso (una serie di celle). Esistono speciali nodi che contengono la lunghezza effettiva di ogni header. Celle diverse che descrivono lo stesso campo con valori diversi vengono memorizzati all'interno di una tabella di hash. Gli header a lunghezza variabile sono gestiti con apposite load, che permettono la memorizzazione in una variabile a runtime.
In PathFinder le celle uguali collassano nella stessa, le celle simili vengono condensate e i valori inseriti nella tabella di hash. La struttura di un filtro è quindi un trie. Nel momento in cui si vuole cercare se è verificato un filtro viene fatta una ricerca nell'albero (trie search). Dal punto di vista pratico, come detto, l'albero è implementato con una tabella di hash. In questo modo il trie può prendere la forma di un DAG, nel caso in cui bisogna matchare una serie di opzioni all'interno dello stesso protocollo di lunghezza non nota a priori.
Il codice è eseguito in macchina virtuale. Una volta definita una cella l'offset e la lunghezza vengono messi in due registri e viene prelevato il pacchetto. Viene presa la maschera e viene fatta una AND con essa. Viene messo il valore in un registro e si fa il confronto. Vengono quindi fatte 4 load per ogni cella che quindi creano molto overhead. A fronte di un'alta flessibilità e a una semplice implementazione dei filtri, corrisponde una diminuzione delle prestazioni.

Dynamic Packet Filter (DPF)
DPF è un'evoluzione di PathFinder, infatti è sempre basato su Trie Search. Esso è munito di un motore di esecuzione più efficiente, compilando i filtri al posto che lasciando l'esecuzione sequenziale. In questo modo il numero di load è molto minore e la velocità di esecuzione è nettamente maggiore. Il problema è una velocità di update inferiore, in quanto la compilazione risulta essere più complessa. Il tempo di update effettivo è dato dal tempo di update del filtro PathFinder sommato al tempo di generazione del codice. Il tempo di update spesso non è determinante, ma in caso di cambiamenti dinamici dei filtri esso è influente, in quanto porterebbe alla perdita di pacchetti validi.
Il tempo di esecuzione dei filtri è 13/26 volte minore rispetto al tempo del PathFinder, il tempo di update è circa il triplo rispetto a PathFinder.

BPF+
Non è mai stato rilasciato al pubblico, anche se sono usciti molti articoli a riguardo. Esso utilizza il BPF, anche se il codice viene ottimizzato e compilato JIT. L'ottimizzazione JIT migliora le prestazioni in quanto i pacchetti che si devono processare sono molto semplici.
Il load dei pacchetti è a offset fissi. Il linguaggio di alto livello passa per un compilatore, passato in SSA, con lo scopo di ottimizzare il codice, tradotto in Assembler e trasferito ad un controllore di sicurezza. A questo punto esso può essere eseguito da un interprete, oppure compilato JIT e trasformato in linguaggio nativo.
Le ottimizzazioni di BPF+ si riferiscono a singoli protocolli, analizzando i singoli casi. Un esempio è dato dai filtri:
-redundant predicate elimination. se source A e dst B || se source B e dst A si tagliano dei rami nel grafi.
-partial redundancy elimination. se source A || source B. In questo caso si eliminano le load inutili. Si può usare anche la tecnica precedente in modo da eseguire un numero di operazioni molto minore
-ottimizzazione degli switch. Se src A || src B || src C… In questo caso dopo aver utilizzato i metodi precedenti vengono inseriti SWITCH, mediante delle tabelle. Gli switch sono molto ottimizzati, in quanto sono molto usati nei linguaggi di alto livello.

xPF
E' un miglioramento della macchina virtuale BPF del 2002. Viene definita una memoria persistente (utile per creare lookup tables dinamiche per sessioni TCP) e viene data la possibilità di effettuare salti all'indietro nel CFG. Viene garantita la terminazione grazie ad un counter nel numero di istruzioni, che, se scade genera un'eccezione. I salti all'indietro sono utili per gestire i pacchetti di IPv4, in quanto le opzioni possono essere di un numero variabile. Se non si considerano le opzioni è possibile passare al protocollo successivo mediante la consultazione dell'header length. Un esempio in cui è invece essenziale l'uso dei loop è quello dei next header di IPv6.

FFPF
Viene presentato nel 2004 e definisce una vera e propria architettura di filtering. In questo modo si riescono a gestire un certo numero di applicazioni contemporanee. Con questo metodo i pacchetti vengono copiati un numero limitato di volte (NIC-BPF-buffer condiviso). E' presente un secondo buffer che contiene l'elenco degli indirizzi che puntano alle celle di memoria dove sono presenti i pacchetti. I programmi diventano più complessi e sono necessari molti controlli per la gestione dei puntatori e della memoria, ma il tempo di esecuzione del filtro è molto minore. Per il filtering è utilizzato non solo il BPF ma anche altri protocolli. Il packet filtering non viene toccato. Viene messo un buffer condiviso tra più applicazioni e ottimizzato il demultiplexing.

Swift
E' del 2008. Si focalizza sul tempo di aggiornamento dei filtri, è quindi fatto per una serie di filtri dinamici in parallelo. Viene realizzato mediante una nuova macchina virtuale con istruzioni SIMD (può operare su più indirizzi contemporaneamente).