[C] Ipfilter efficiente

[avware]

Ciao,
stavo cercando qualche buona idea/consiglio su come implementare un filtro ip in C. L'applicazione dovrebbe girare su piattaforma linux embedded tramite netfilter, ma aldilà di questo (cioè di come interagisce col sistema operativo), scrivo perché cercavo idee tecniche su come strutturare il software in modo che sia molto efficiente, poiché spesso i dispositivi embedded hanno hardware risicato con cpu mips a 400mhz e 8/16mb di ram.

Il filtraggio per ora si limita al solo protocollo ipv4: immaginate un router dove arrivano in continuazione richieste da forwardare.. ogni richiesta dovrebbe essere valutata (permetti, blocca) nel minor tempo possibile. Esperimenti con iptables e ipset hanno mostrato grossi limiti, soprattutto con filtri di 50k regole.. nel mio caso stiamo sui 200k range.

In prima battuta ho pensato alle liste, poi mi son detto: cavolo dovrei scorrere tutta la lista ogni volta! Forse un array di indirizzi ? Magari scomponendolo in gruppi e usando il primo gruppo per fare una ricerca indicizzata:

deny[0..255]

1.2.3.4-1.2.3.10 -> deny[1] -> lista (ricerca lineare) -> 2.3.[4-10]

Altre idee ?

[WarDuck]

Mi pare strano riuscire a far meglio di iptables, comunque hai scartato a priori l'uso di una hashtable e di una funzione di hash general purpose?

Ti dico subito che scomporre i blocchi (se ho capito cosa intendi) non funziona, perché potresti avere falsi positivi.

inserisci 1.2.3.4
inserisci 5.6.7.8

hai come falso positivo: 5.6.3.4 che non hai mai visto.

Se conosci in anticipo il range di IP da bloccare potresti tentare di fare una perfect hash function.

Oppure usi un bloom filter: https://en.wikipedia.org/wiki/Bloom_filter

Il vantaggio è che è molto compatto (nell'ordine di centinaia di kilobytes se usi k=8 funzioni hash a 20bit), lo svantaggio è che è probabilistico e va dimensionato correttamente.

Se riesci a tenere tutto nella cache del processore è abbastanza veloce.

[avware]

Mi pare strano riuscire a far meglio di iptables
Il problema non è fare meglio in termini di velocità [di match] - magari fossi già li - quanto riuscire almeno a fargli digerire i 250k range di regole. Giocando un pò con sed ho trasformato il mio file "ipfilter.dat" in 250k rule da aggiungere alla chain di input. Il pc, Core-i5, è diventato un fornelletto e dopo più di un'ora non aveva ancora finito di applicarle tutte :D Immagina a doverlo fare con un mips con la tosse.
comunque hai scartato a priori l'uso di una hashtable e di una funzione di hash general purpose?
Con questo hardware avevo escluso approcci funzionali/matematici.. o meglio stavo cercando di sostituirmi io (col mio cervello buggato) al grosso lavoro di distribuzione dei valori fatto dalle funzioni hash. Da qui l'idea esposta prima, in effetti esposta molto male ora che ho riletto; mi spiego meglio:

Ip d'esempio da filtrare: 1.2.3.4, 5.6.7.8

Come sto organizzando la memoria (ho appena finito un prototipo):

ip_bloccati[0] = nil;
ip_bloccati[1] = 0xblabla1;
ip_bloccati[2] = nil;
...
ip_bloccati[5] = 0xblabla2;
...
ip_bloccati[255] = nil;

In sostanza il primo gruppo/ottetto corrisponde all'indice dell'array, così mi evito una scrematura iniziale data dal dover scorrere tutta la struttura alla ricerca di un ip che potrebbe non esserci proprio e limito l'uso della memoria a circa 4k (256 valori * 16bit).

Una volta beccato un positivo, i puntatori mi aiutano a scorrere una lista che contiene range di ottetti. Avendo io un range, l'unico modo per gestirlo è che ogni ottetto (escluso il primo) venga rappresentato come una coppia di valori da-a. Da qui la struttura puntata da quei puntatori 0xblablabla:

typedef struct
{
uint8_t from;
uint8_t to;
} ipv4rangegroup_t;

typedef struct ipv4rule
{
ipv4rangegroup_t b;
ipv4rangegroup_t c;
ipv4rangegroup_t d;

struct ipv4rule *next;
} ipv4rule_t;

Usando i puntatori in questo modo - teoricamente - dovrei garantire un uso della memoria strettamente limitato al numero di regole contenute nel file (sto cercando di evitare di istanziare array su array su array che poi magari risultano "vuoti"); la parte di lettura del file ancora mi manca quindi non riesco a fare test di performance e allocazione.

In verità iptables non l'ho messo da parte, questo lavoro verrà integrato con un altro che ho già pronto e che usa la libnetfilter_queue per fare forward di tutto quello che arriva in INPUT verso una coda interna. In questo modo le rule iptables si limitano a 1 e il resto lo farebbe questo mio programmino C.

Se conosci in anticipo il range di IP da bloccare potresti tentare di fare una perfect hash function.

Oppure usi un bloom filter: https://en.wikipedia.org/wiki/Bloom_filter

Il vantaggio è che è molto compatto (nell'ordine di centinaia di kilobytes se usi k=8 funzioni hash a 20bit), lo svantaggio è che è probabilistico e va dimensionato correttamente.

Se riesci a tenere tutto nella cache del processore è abbastanza veloce.
Perdona l'ignoranza, non conosco Bloom Filter o perfect Hash function, anzi ti ringrazio per il link che sto già usando per una lettura riflessiva.. se solo il mio inglese fosse migliore lol. Comunque si, il range lo conosco.

[Daniels118]

Usa una hashmap, puoi implementarla tu stesso, è meno difficile di quanto sembra.
Avendo 250K elementi, puoi fare 250 bucket da 1000 elementi (in media).
I bucket non sono altro che delle liste, inserite in un array (in questo caso un array da 250 elementi).
Per capire in quale bucket si trova un ip, bisogna utilizzare una funzione hash, ovvero una funzione che trasforma l'ip in un indice.
Siccome l'ip non è altro che un numero a 32 bit, la funzione hash può essere semplicemente "ip % numero_bucket", il resto di questa divisione rappresenta l'indice dell'array nel quale c'è la lista dove si trova l'ip.
Il tempo di accesso al bucket è o(1), mentre la ricerca nel bucket è o(n), con avg(n)=num_elementi/num_bucket. L'overhead di memoria fisso è quello della lunghezza dell'array (250 puntatori).
Le liste possono essere implementate come linkedlist (con un piccolo overhead di memoria), oppure come array (con un overhead per ridimensionarli).

[avware]

Usa una hashmap, puoi implementarla tu stesso, è meno difficile di quanto sembra.
Avendo 250K elementi, puoi fare 250 bucket da 1000 elementi (in media).
I bucket non sono altro che delle liste, inserite in un array (in questo caso un array da 250 elementi).
Per capire in quale bucket si trova un ip, bisogna utilizzare una funzione hash, ovvero una funzione che trasforma l'ip in un indice.
Siccome l'ip non è altro che un numero a 32 bit, la funzione hash può essere semplicemente "ip % numero_bucket", il resto di questa divisione rappresenta l'indice dell'array nel quale c'è la lista dove si trova l'ip.
Il tempo di accesso al bucket è o(1), mentre la ricerca nel bucket è o(n), con avg(n)=num_elementi/num_bucket. L'overhead di memoria fisso è quello della lunghezza dell'array (250 puntatori).
Le liste possono essere implementate come linkedlist (con un piccolo overhead di memoria), oppure come array (con un overhead per ridimensionarli).
Ciao, si conosco il funzionamento delle mappe (sono programmatore java e ne faccio largo uso), sono quei nomi altisonanti - perfect hash function e Bloom filter - che mi hanno lasciato molto scosso :D

La tua idea è molto simile a quella che ho implementato, io ho usato bucket di 256 elementi uno per ogni primo-ottetto dell'indirizzo ip che contiene un puntatore ad una lista di range (ho sfruttato il fatto che ogni ottetto può contenere valori da 0 a 255 per costruire l'indice). Volendo valutare il costo in termini di velocità (il primo ottetto dell'ip da verificare):
- caso migliore: non è contenuto nella lista (puntatore nil);
- caso peggiore: punta ad una lista di N elementi, in questo caso il costo è variabile da 1 a N;

Se la regola esiste il costo è dipeso dalla sua posizione nella lista.. altrimenti il costo è N (deve scorrere tutta la lista prima di beccare un nil-fine lista).

Forse qui si potrebbe ottimizzare se uno sapesse a priori che la lista è ordinata (o potrebbe ordinarla di conseguenza in fase iniziale).

[Daniels118]

Utilizzare il primo byte come indice può essere una buona soluzione, l'inconveniente è che il numero di bucket deve essere esattamente 256, mentre con una funzione ad hoc puoi sceglierlo a piacere.

Un'ulteriore ottimizzazione potrebbe essere quella di "mescolare" i 4 byte così da distribuire meglio gli indirizzi. Consideriamo il caso in cui usi il primo byte come indice: se tutti gli ip sono del tipo "192.*.*.*" corri il rischio che finiscano tutti nello stesso bucket (e con 3 byte possiamo arrivare fino a 16 milioni!). Alcune possibilità sono:
1) indice = (a + b + c + d) % n_bucket
2) indice = (a ^ b ^ c ^ d) % n_bucket
Si potrebbe fare un programmino per testare le distribuzioni ottenute così da scegliere quella migliore.

Se usi una linked list puoi inserire gli elementi direttamente nella posizione giusta, così non devi riordinare l'intera lista ad ogni inserimento.
Se invece usi un array per implementare la lista puoi utilizzare la ricerca binaria, abbattendo la complessità a o(log(n)); ovviamente ciò ha il costo di dover usare realloc quando inserisci nuovi elementi.

Se l'inserimento viene fatto solo in fase di inizializzazione, o comunque di rado, conviene usare gli array e fare un unico sort dopo averli riempiti.

EDIT: Anzi, se l'inserimento è un'operazione rara ti conviene fare un unico enorme array, riempirlo, ordinarlo, e andare di ricerca binaria.