1. Implementazione del loglogcounter Appendice

(1)

Appendice

1. Implementazione del loglogcounter

LogLogCount():M(MDEF),K(log2(MDEF)),mask((1<<K)-1) {

for (unsigned int i=0; i<M; i++) counters.push_back(0); }

Il costruttore di default costruisce l’istanza della classe

LogLogCount nel caso in cui non si passino argomenti; crea un

numero default di sottoblocchi del loglogcounter e li inizializza

a 0.

LogLogCount(int m):M(m),K(log2(m)),mask((1<<K)-1) {

for (unsigned int i=0; i<M; i++) counters.push_back(0); }

Questo costruttore accetta un argomento, m, che corrisponde al

numero di sottogruppi del LogLogCounter; crea gli m

sottoblocchi del loglogcounter e li inizializza a 0.

LogLogCount(const LogLogCount& in):M(in.M),K(in.K),mask(in.mask) {

for (unsigned int i=0; i<M; i++)

(2)

}

Il copy constructor di una qualsiasi classe è invocato quando è

effettuata esplicitamente una copia, oppure quando si ha una

funzione che ritorna quella classe per copia o che accetta il

passaggio di parametri per copia. In questo caso specifico,

questo tipo di costruttore crea gli m sottoblocchi del

LogLogCounter e li inizializza con un valore analogo a quello

della classe LogLogCount in passata come argomento.

void LogLogCount::insert(unsigned short in,unsigned long long ***hasht,int k, unsigned int b)

{

unsigned int a;

int p=2147483647,ho=1; unsigned long long hash=0; unsigned int mask2=0; unsigned int mask3=0; unsigned long long esp[4]; for (unsigned int i=0;i<16-K;i++) ho=ho*2;

for (unsigned int i=0;i<K;i++) {

mask2+=ho; ho*=2; }

ho=1;

for (unsigned int i=0;i<16-K;i++) {

(3)

mask3+=ho; ho*=2; } esp[0]=1LL; for (int n=1; n<4; n++) esp[n] = (esp[n-1]*in); for (int i=0;i<4;i++) { a=hasht[b][k][i]; hash=(hash+(a*esp[i])%p)%p; hash=(hash)%p; } hash=(hash)%65536;

unsigned int index=((unsigned int)(hash)&mask2)>>(16-K); if(index>=M)

{

std::out_of_range ex("loglog counter m index"); throw(ex);

}

unsigned int count=((unsigned int)hash)&mask3; unsigned int lsb=0;

for(unsigned int i=16-K;i>0;i--) {

unsigned int m=1<<(i-1); if((m&count)!=0) { lsb=16-K+1-i; break; } } if(counters[index]<lsb) counters[index]=lsb;

(4)

}

“insert” è la funzione utilizzata per determinare l'indice (index)

e il valore da inserire nei sottoblocchi del loglogcounter (lsb),

calcolati sulla porta di destinazione in. Si è utilizzato la

funzione hash della formula (18) e dell'uscita di tale funzione si

è usato mask2 per selezionare i primi K bit, da utilizzare per

l'indice, mentre sui bit restanti si va a calcolare la funzione

ρ(x), che individua l'indice del primo bit diverso da 0. Se il

sottogruppo contiene un valore minore di quello appena

ottenuto, esso viene aggiornato, altrimenti no: vedi formula (2).

int count() const {

double pi=3.14159265358979323846264338; double mean=0;

for(unsigned int i=0; i<M; i++) mean+=counters[i]; mean=mean/(double)M;

double deb=0.39701-((2*pi*pi+log10((double) 2 )*log10((double) 2 ))/(48*M));

double retval=deb* M *pow(2,mean); int ret=(int) retval;

return(ret); }

Il metodo count realizza la formula (4), che implementa la

stima della cardinalità.

void merge(const LogLogCount& in) {

(5)

if(in.M!=M)

{

std::out_of_range ex("loglog counter merge impossible with different sizes");

throw(ex);

}

for (unsigned int i=0; i<M; i++) if(counters[i]<in.counters[i]) counters[i]=in.counters[i]; }

Per ogni cella del LogLogCount, la funzione merge realizza il

max merge (19), cioè controlla se il contatore attuale è

inferiore a quello passato per const reference in e in questo

caso lo aggiorna.

virtual ~LogLogCount(){}

Il distruttore del LogLogCount, invocato automaticamente alla

fine dello scope di ogni LogLogCount, non effettua alcuna

azione. La parola chiave virtual indica che la classe è

polimorfica, per cui le eventuali classi derivate da questa

quando invocano il distruttore chiameranno effettivamente il

proprio distruttore, e non quello della classe base.

2. Implementazione del logsketch

Si descrive nel seguito la classe che implementa il

LLCS.

(6)

KeyType ReorderKey(KeyType key) { #ifdef NEW_MANGLE return mangler->MangleShortTable(key); #else return (KeyType)((key * a) % N); #endif }

Questo metodo implementa l'IP mangling, ovvero va a

“rimescolare” l'indirizzo IP di destinazione key.

RevKSketch(int numHashTbls, int inxBits,int M) {

numTbls = numHashTbls;

hashTbls = new RevHashTable*[numTbls]; for( int i = 0; i < numTbls; i++ )

hashTbls[i] = new RevHashTable(i, inxBits,M); #ifdef NEW_MANGLE

mangler = new Mangler(); else

= A;

_inv = FindInverse(a); endif

}

Il costruttore di logsketch accetta tre parametri: il numero delle

righe dello sketch, il logaritmo in base due del numero di

colonne e il numero di sottogruppi per i LogLogCount; la

funzione di tale costruttore è quella di creare numTbls

Loghashtable.

~RevKSketch() {

(7)

#ifdef NEW_MANGLE delete mangler; #endif

for ( int i = 0; i < numTbls; i++ ) delete hashTbls[i]; delete[] hashTbls;

}

Il distruttore del LogSketch libera la memoria allocata

dinamicamente (utilizzando cioè il comando new) appena si

esce dallo scope del LogSketch.

void AddValue(KeyType key, unsigned short val,unsigned int ***hasht,unsigned long long ***hasht2,int r)

{

KeyType rkey = ReorderKey(key); for( int i = 0; i < numTbls; i++ )

hashTbls[i]->AddValue(rkey, val,hasht,hasht2,i,r);

}

Il metodo AddValue riordina la chiave (indirizzo IP di

destinazione) passata, in modo che gli indirizzi IP con i primi

tre ottetti uguali non cadano negli stessi bucket.

Successivamente per ogni Loghashtable del LogSketch chiama

la funzione AddValue di Loghashtable.

int** export_counters() const {

int** table2=new int*[numTbls]; for(int i=0; i<numTbls; ++i) {

(8)

const std::vector<LogLogCount>& vec(hashTbls[i]->counters());

table2[i]=new int[vec.size()];

for (unsigned int j=0; j<vec.size(); ++j) table2[i][j]=vec[j].count(); }

return table2; }

“export_counters”

crea

una

tabella

di

dimensione

numBins

numTbl 

che contiene, nel relativo bucket, i valori F

stimati in base all'algoritmo L

OG

L

OG

(formula 4), e la ritorna.

Il qualificatore const specifica che questa funzione non può

modificare alcun membro della classe LogSketch, ma solo

leggerne il contenuto.

void merge(const RevKSketch& in) {

assert(numTbls==in.numTbls); for(int i=0; i<numTbls; ++i)

hashTbls[i]->merge(*in.hashTbls[i]); }

“merge” controlla che il LogSketch passato per const reference

abbia lo stesso numero di Loghashtable di quello attuale, e per

ogni Loghashtable invoca la funzione merge passandogli come

right value la Loghashtable i-esima del LogSketch in.

void cusum(double** mu, double** var,int time, double h, double** g, int** Am)

{

(9)

double mun, varn; int **t=export_counters(); double L;

for (int i=0; i<numTbls; i++) for (uint32 j=0; j<K; j++) { mun=alpha*mu[i][j]+(1-alpha)*(t[i][j]); varn=alpha*var[i][j]+(1-alpha)*pow((t[i][j]-mun),2); L=t[i][j]-(mun+coeff*sqrt(varn)); if(L>0) g[i][j]+=L; if(g[i][j]>=h) { Am[i][j]=1; g[i][j]=0; } else { g[i][j]=0; mu[i][j]=mun; var[i][j]=varn; } } delete t; }

Questa funzione realizza l’algoritmo di anomaly detection

MNP-CUSUM, applicandolo ad ogni bucket t[i][j] dello

sketch. Le righe 10 e 11 stimano il valore corrente di valor

medio e varianza secondo le formule (15) e (16); alla riga 12 si

valuta il valore della funzione L come indicato dall’equazione

(10)

(14), mentre le righe 13-26 applicano il vero e proprio

algoritmo CUSUM della formula (13).

3. Implementazione del revsketch

Si tratta della classe che implementa il Reversbible

Sketch.

typedef struct NodeType {

list<unsigned char> keyList;

unsigned char numFound; // Number of HT's in which this key has been found

// List of heavy change buckets to which this key corresponds for each HT

vector<list<IndexType> > bktLists;

NodeType(unsigned char key, IndexType bkt, unsigned char tbl, int numTbls) { keyList.push_back(key); numFound = 1; bktLists.resize(numTbls); bktLists[tbl].push_back(bkt); } NodeType() { numFound = 0; } } NodeType;

Questa struttura descrive il formato dei nodi che

costituiscono l’albero: ogni nodo memorizza la parte di chiave

a cui è legato, il numero di hash table in cui questa chiave è

stata trovata, una lista per ogni hash table dei bucket anomali in

(11)

cui essa cade; nel caso in cui si debba creare un nuovo nodo, si

passano i parametri key, bkt, tbl, numTbls che la funzione

NodeType penserà a collocare opportunamente all’intero della

struttura.

KeyType ReorderKey(KeyType key) { #ifdef NEW_MANGLE return mangler->MangleShortTable(key); #else return (KeyType)((key * a) % N); #endif }

Questo metodo implementa l'IP mangling, ovvero va a

“rimescolare” l'indirizzo IP di destinazione key.

RevSketch(int numHashTbls, int inxBits) { numTbls = numHashTbls; if(numTbls%2==0) r=numTbls/2-1; else r=numTbls/2-1.5; table = new revintable*[numTbls]; for( int i = 0; i < numTbls; i++ )

table[i] = new revintable(i, inxBits);

#ifdef NEW_MANGLE

mangler = new Mangler(); #else

a = A;

a_inv = FindInverse(a); #endif

(12)

}

Il costruttore di RevSketch accetta due parametri: il

numero delle righe dello sketch, il logaritmo in base due del

numero di colonne; la funzione di tale costruttore è quella di

creare numTbls Revhashtable.

~RevSketch() {

#ifdef NEW_MANGLE

delete mangler; #endif

for ( int i = 0; i < numTbls; i++ ) delete table[i];

delete[] table; }

Il distruttore del RevSketch libera la memoria allocate

dinamicamente (utilizzando il comando new) appena si esce

dallo scope del RevSketch.

void crealista(KeyType key,KeyType key2,int** Am,unsigned int ***hasht,int r)

{

KeyType rkey2 = ReorderKey(key2); for (int k=0; k<numTbls; k++)

table[k]->crealista(key,rkey2,k,Am,hasht,r); }

Il metodo crealista riordina la chiave (indirizzo IP di

destinazione) passata, in da agire in parallelo ad AddValue.

(13)

Successivamente per ogni revhashtable del Revsketch chiama

la funzione crealista.

void ChangeDetection(list<KeyType> &resultList,int** Am) {

// Get the heavy change buckets for each table vector<list<IndexType> > bktLists(numTbls);

int tbl;

for( tbl = 0; tbl < numTbls; tbl++ )

table[tbl]->ChangeDetection(tbl,bktLists[tbl],Am); // Create the nodes in the graph

GraphType graph; graph.clear();

CreateNodes(graph, bktLists); // Create the links between each level for( int div = 0; div < 3; div++ ) CreateLinks(graph, div);

// Get the full keys from the graph after the traversal GenerateFullKeys(graph, resultList);

resultList.sort(); resultList.unique(); }

Questa funzione, implementata dagli autori di [3], mette

insieme tutte le operazioni necessarie per risalire agli indirizzi

IP di destinazione che hanno causato le anomalie rilevate: crea

i nodi e i percorsi del grafo e in base a questo determina gli

indirizzi IP anomali.

(14)

void CreateNodes(GraphType &graph, const vector<list<IndexType> > &bktLists)

{

// A map that associates key segments with nodes map<unsigned char, NodeType*> nodeMap; graph.resize(4); // Initialize the graph // For each key division

for( int div = 0; div < 4; div++ ) {

nodeMap.clear();

// For each hash table in the sketch for( int tbl = 0; tbl < numTbls; tbl++ ) {

// For each heavy change bucket for this hash table for( list<IndexType>::const_iterator bktListIt = bktLists[tbl].begin(); bktListIt != bktLists[tbl].end(); bktListIt++ )

{

list<unsigned char> keys;

table[tbl]->GetPossibleKeys(keys, div, *bktListIt,tbl);

// For each of the possible key segments

for( list<unsigned char>::iterator keyIt = keys.begin(); keyIt != keys.end(); keyIt++ )

{

NodeType *node = nodeMap[*keyIt]; // Get the node, if one exists

if( node == NULL )

{ // Key does not already exist in the map

// Create a new node and add it to the map

node = new NodeType(*keyIt, *bktListIt, tbl, numTbls); nodeMap[*keyIt] = node; } else { if( node->bktLists[tbl].empty() ) // First entry for this HT

(15)

node->numFound++;

node->bktLists[tbl].push_back(*bktListIt);

}

} // End for ... keyIt } // End for ... bktListIt } // End for ... tbl

// Enter the nodes where numTbls - numFound <= R into the graph for( map<unsigned char, NodeType*>::iterator nodeMapIt = nodeMap.begin(); nodeMapIt != nodeMap.end(); nodeMapIt++ )

{

NodeType *node = nodeMapIt->second; if( (numTbls - node->numFound) <= r ) graph[div].push_back(node); else

delete node; } // End for ... nodeMapIt

} // End for ... div }

Questa funzione crea i nodi del grafo: viene generato un nodo

per ogni parte div-esima di tutte le chiavi che cadono in un

bucket anomalo; ma alla fine non viene cancellato solo se la

chiave cade in un bucket anomalo in almeno r hashtable su

numTbls, con

r

<

_

numTbls

/

2 _

.

void CreateLinks(GraphType &graph, int startDiv) {

if( startDiv >= 3 )

return; // cannot start at the last level list<NodeType*> *l1List = &(graph[startDiv]); list<NodeType*> *l2List = &(graph[startDiv+1]); list<NodeType*> linkList;

(16)

for( list<NodeType*>::iterator l1It = >begin(); l1It != l1List->end(); l1It++ )

{

for( list<NodeType*>::iterator l2It = l2List->begin(); l2It != l2List->end(); l2It++ )

{

NodeType *newNode = RIntersect(*l1It, *l2It); if( newNode != NULL )

linkList.push_back(newNode); } // End for...l2It

delete *l1It; // no longer need this node in level 1 }

// Delete all of the nodes in L2

for( list<NodeType*>::iterator l2It = >begin(); l2It != l2List->end(); l2It++ )

delete *l2It; l1List->clear(); l2List->clear();

l2List->insert(l2List->end(), linkList.begin(), linkList.end()); }

Questa funzione va a scoprire se esistono link tra i nodi del

grafo.

Infatti, considera il grafo div-esimo e per ogni nodo che lo

compone, verifica se ci sono chiavi che hanno almeno un

bucket anomalo in comune con qualsiasi altra chiave di un

nodo del grafo (div+1)-esimo; se questa corrispondenza esiste,

memorizza i possibili percorsi in l2List. In questo modo,

graph[3] avrà memorizzata al suo interno una lista completa

delle parti di chiavi risultate anomale. La descrizione teorica

dell’algoritmo è inserita nel paragrafo 3.3.

(17)

NodeType* RIntersect(NodeType *node1, NodeType *node2) {

NodeType *newNode = new NodeType; newNode->bktLists.resize(numTbls); for( int tbl = 0; tbl < numTbls; tbl++ ) {

list<IndexType> *node1Lst = &(node1->bktLists[tbl]); list<IndexType> *node2Lst = &(node2->bktLists[tbl]); list<IndexType> *newLst = &(newNode->bktLists[tbl]); ListIntersect(*newLst, *node1Lst, *node2Lst);

if( newLst->empty() ) { if( newNode->numFound >= r ) { delete newNode; return NULL; } else newNode->numFound++; } }

list<unsigned char> *keyLst = &(newNode->keyList);

keyLst->insert(keyLst->end(), node1->keyList.begin(), node1->keyList.end());

keyLst->insert(keyLst->end(), node2->keyList.begin(), node2->keyList.end());

return newNode; }

La funzione RIntersect implementa la formula 12: cerca se

esistono intersezioni tra gli elementi di ogni riga di tbl di node1

e node2, se è una nuova intersezione, la inserisce in newLst se

c’è un numero minore di r di *, ovvero se ci sono almeno D-r

hashtable con almeno un bucket anomalo in comune tra node1

(18)

e node2, se è un’intersezione già trovata, incrementa il

contatore.

void GenerateFullKeys(GraphType &graph, list<KeyType> &resultList) {

unsigned int fullKey;

unsigned char *keyDivided = (unsigned char *)&fullKey;

for( list<NodeType*>::iterator lstIt = graph[3].begin(); lstIt != graph[3].end(); lstIt++ )

{

list<unsigned char> *keyList = &((*lstIt)->keyList); if( keyList->size() == 4 )

{

int div = 3;

for( list<unsigned char>::iterator keyIt = keyList->begin(); keyIt != keyList->end(); keyIt++, div-- )

keyDivided[div] = *keyIt; resultList.push_back(fullKey); } // end if delete *lstIt; } // end for }

Per tutti gli elementi di graph[3], mette in result list le chiavi

costituite effettivamente da quattro parti.

void ListIntersect(list<IndexType> &outList, const list<IndexType> &l1, const list<IndexType> &l2)

{

outList.clear();

list<IndexType>::const_iterator l1It = l1.begin(); list<IndexType>::const_iterator l2It = l2.begin(); while( true )

{

if( (l1It == l1.end()) || (l2It == l2.end()) ) return;

(19)

if( *l1It > *l2It ) l2It++; else if( *l1It < *l2It ) l1It++; else { outList.push_back(*l1It); l1It++; l2It++; } } }

Questo metodo cerca le intersezioni tra le liste l1 e l2, e se le

trova le inserisce in outlist.

4. Implementazione delle LogLoghashTable

RevHashTable(int seed, int inxBits, int M):m_counters((1U << inxBits),LogLogCount(M))

{

if( (inxBits % NUM_DIVISIONS) != 0 ) {

cerr << "Number of index bits must be divisible by " << NUM_DIVISIONS << endl; exit(-1);

}

numBins = (1U << inxBits);

bitsPerDiv = inxBits / NUM_DIVISIONS; srand(seed+1);

}

Il costruttore di logsketch accetta tre parametri: il seme con cui

inizializzare il generatore di numeri casuali, il logaritmo in

(20)

base due del numero di bucket e il numero di sottogruppi dei

LogLogCounter.

const std::vector<LogLogCount>& counters() const {

return m_counters; }

Ritorna l'insieme degli M sottogruppi di LogLogCounter di

quel bucket.

void merge(const RevHashTable& in) {

assert(in.m_counters.size()==m_counters.size()); for (unsigned int i=0; i<m_counters.size();++i)

m_counters[i].merge(in.m_counters[i]); }

Dopo aver controllato se la loghashtable attuale e quella

passata per reference abbiano la stessa dimensione, questo

metodo chiama le funzione merge relativa ai LogLogcounter.

~RevHashTable() {}

Il distruttore non effettua nessuna azione.

uint32 GetNumBins() const {

return numBins; }

Funzione che permette di conoscere dall'esterno il numero di

bucket, può essere usata solo per accedere in lettura alla classe.

(21)

void AddValue(KeyType rkey,unsigned short val,unsigned int ***hasht,unsigned long long ***hasht2, int k,int r)

{

m_counters[GetIndex(rkey,hasht,k,r)].insert(val,hasht2,k,GetIndex (rkey,hasht,k,r));

}

Dopo aver determinato il bucket in cui cade la chiave

mescolata, questo metodo va a chiamarci la funzione insert del

LogLogCounter.

uint32 hashparziale(uint8 in,int o,unsigned int ***hasht,int k,int r) {

unsigned int a; int p=8191; uint32 hash=0; unsigned int esp[4]; unsigned int x=1; esp[0]=1; for (int n=1; n<4; n++) esp[n] = (esp[n-1]*in); for(uint32 j=0;j<bitsPerDiv;j++) x*=2;

for (int i=0;i<4;i++) { a=hasht[k][o][i][r]; hash=(hash+(a*esp[i])%p)%p; hash=(hash)%p; } hash=(hash)%x; return hash; }

Secondo la formula (17), “Hash parziale” va a calcolare

h

d,k,r

(x

div

) con i coefficienti memorizzati nella tabella hasht.

(22)

IndexType GetIndex(uint32 key,unsigned int ***hasht, int k) {

// key is in permuted format

// XXX: assume values in lookupTable[][] has been shifted properly int32views h; h.as_int32 = key; return (hashparziale(h.as_int8s[3],3,hasht,k,r) << (0*bitsPerDiv)) | (hashparziale(h.as_int8s[2],2,hasht,k,r) << (1*bitsPerDiv)) | (hashparziale(h.as_int8s[1],1,hasht,k,r) << (2*bitsPerDiv)) | (hashparziale(h.as_int8s[0],0,hasht,k,r) << (3*bitsPerDiv)); }

Calcola la hash function finale che determina l'indice del

bucket in cui cade la chiave key, secondo la formula(6).

5. Implementazione delle revHashTable

revintable(int seed, int inxBits)

{

uint32 i;

numBins = (1U << inxBits);

bitsPerDiv = inxBits / NUM_DIVISIONS; binsPerDiv = (1U << bitsPerDiv);

divMask = binsPerDiv - 1; for(int oo=0;oo<16;oo++) { revLookupTable[oo].resize(4); for( i = 0; i < 4; i++ ) revLookupTable[oo][i].resize(MAX_KEY + 1);

(23)

}

srand(seed+1); }

Il costruttore di revhashtable accetta due parametri: il seme con

cui inizializzare il generatore di numeri casuali e il logaritmo in

base due del numero di bucket.

~revintable() {}

Il distruttore non effettua nessuna azione.

uint32 hashparziale(uint8 in,int o,unsigned int ***hasht,int k,int r) {

unsigned int a; int p=8191; uint32 hash=0; unsigned int esp[4]; unsigned int x=1; esp[0]=1; for (int n=1; n<4; n++) esp[n] = (esp[n-1]*in); for(uint32 j=0;j<bitsPerDiv;j++) x*=2;

for (int i=0;i<4;i++) { a=hasht[k][o][i][r]; hash=(hash+(a*esp[i])%p)%p; hash=(hash)%p; } hash=(hash)%x; return hash; }

(24)

Secondo la formula (17), va a calcolare h

d,k,r

(x

div

) con i

coefficienti memorizzati nella tabella hasht.

IndexType GetIndex(uint32 key,unsigned int ***hasht, int k,int r) {

// key is in permuted format

// XXX: assume values in lookupTable[][] has been shifted properly int32views h; h.as_int32 = key; return (hashparziale(h.as_int8s[3],3,hasht,k,r) << (0*bitsPerDiv)) | (hashparziale(h.as_int8s[2],2,hasht,k,r) << (1*bitsPerDiv)) | (hashparziale(h.as_int8s[1],1,hasht,k,r) << (2*bitsPerDiv)) | (hashparziale(h.as_int8s[0],0,hasht,k,r) << (3*bitsPerDiv)); }

Calcola la hash function finale che determina l'indice del

bucket in cui cade la chiave key, secondo la formula (8).

void crealista(int** Am, uint32 rkey,uint32 key,int k,unsigned int ****hasht,int r)

{

uint32 divMask2=255; uint32 bitsPerDiv2=8;

unsigned int j=GetIndex(rkey,hasht,k,r); if(Am[k][j]==1)

{

int divk;

for (int div=0;div<4;div++) {

(25)

switch(div) { case 0: divk=3; break; case 1: divk=2; break; case 2: divk=1; break; case 3: divk=0; break; }

uint32 keyd=(key>>(divk*bitsPerDiv2)) & divMask2;

uint32 jd=uint8((j>>(divk* bitsPerDiv)) & divMask);

revLookupTable[k][div][jd].push_back((uint8)keyd); }

} }

Memorizza gli indirizzi IP di sorgente dei bucket risultati

anomali, inserendo la parte div-esima dell'indirizzo IP di

destinazione in revLookupTable[k][div][jd] dove jd è la parte

div-esima dell'indice del bucket (formula 9) e k l'indice

dell'hashtable attuale.

void GetPossibleKeys(list<uint8> &keys,int div,IndexType bin,int k) {

int divk; switch(div) {

(26)

divk=3; break; case 1: divk=2; break; case 2: divk=1; break; case 3: divk=0; break; }

bin = (bin >> (divk * bitsPerDiv)) & divMask; vector<uint8> &rt = revLookupTable[k][div][bin]; keys.clear();

int numKeys = rt.size();

for( int i = 0; i < numKeys; i++ ) keys.push_back(rt[i]); }

La funzione inserisce in keys tutte le parti div-esime di chiave

risultate anomale.

void ChangeDetection(int k,list<IndexType> &changes, int** Am) {

for (uint32 j=0; j<numBins; j++) if(Am[k][j]==1)

changes.push_back(j); }

Questo metodo inserisce nella lista changes gli indici dei

bucket risultati anomali per l'hashtable k in base ai risultati

memorizzati nella tabella Am.

(27)

6. Implementazione dell'IP mangling

Seguono le funzioni che realizzano l'IP mangling

descritto nel paragrafo 3.2.

Le strutture dati,necessarie per reaizzare il calcolo di

x

a  in forma tabellare,sono definite in questo modo:

uint32 short_mgltbl0[65536]; uint32 short_mgltbl1[65536];

uint32 short_revtbl0[65536]; uint32 short_revtbl1[65536];

Dove mgltbl0 e revtbl0 sono dedicate ai primi 16 bit della

chiave, le altre due agli ultimi 16.

void InitShortTable(GaloisField *gf) { uint64 i, a, b; a = rand32bit(); b = gf->Inv(a); for (i = 0; i < 65536; i++) { short_mgltbl0[i] = uint32(gf->Mul(i<<16,a)); short_mgltbl1[i] = uint32(gf->Mul(i,a)); short_revtbl0[i] = uint32(gf->Mul(i<<16,b)); short_revtbl1[i] = uint32(gf->Mul(i,b)); } }

(28)

La funzione InitShortTable inizializza le quattro tabelle

secondo la formula 9, ma i=0,1 perchè si divide la chiave in

due parti di 16 bit e non in quattro parti di 8 bit.

uint32 MangleShortTable(uint32 k) { int32views x; x.as_int32 = k; return short_mgltbl0[x.as_int16s[0]] ^ short_mgltbl1[x.as_int16s[1]]; }

Il metodo MangleShortTable calcola il valore mescolato della

chiave k, secondo la formula 10, ma realizzata dividendo la

chiave in caratteri di 16 bit invece che 8, per cui i=0,1.

uint32 ReverseShortTable(uint32 k) { int32views x; x.as_int32 = k; return short_revtbl0[x.as_int16s[0]] ^ short_revtbl1[x.as_int16s[1]]; }

Il metodo ReverseShortTable calcola il valore originario della

chiave k rimescolata, secondo la formula 10, ma realizzata

dividendo la chiave in caratteri di 16 bit invece che 8, per cui

i=0,1.

(29)

Analizziamo adesso il main nel caso della versione

distribuita.

#include "LogSketch.h" #include "RevSketch.h" #include <stdexcept> #include<assert.h> #include <fstream> #define P1 8191 #define P2 2147483647 unsigned int cco(char* s) {

assert(s);

unsigned int res=0;

unsigned int byte1,byte2,byte3,byte4;

sscanf(s,"%d.%d.%d.%d",&byte4,&byte3,&byte2,&byte1); res=byte1|(byte2<<8)|(byte3<<16)|(byte4<<24); return res; } struct tuple {

unsigned int sip; unsigned int dip; unsigned short sp; unsigned short dp; unsigned short proto; };

int main (int argc, char** argv) { int NUMFILES=2016; int M=-1; int ll=-1; char* directory=NULL; int nfolders=-1;

(30)

int LogNbin=-1; double threshold=600; char c=getopt(argc,argv,"m:l:d:n:f:b:"); fstream f,h; h.open("indirizzi.txt",ios::out); f.open("timebin.txt",ios::out); double** mu, **var,**S; int** Am;

unsigned int ****hasht; unsigned long long ***hasht2; while(c!=-1) { switch (c) { case 'm': sscanf(optarg,"%d",&M); break; case 'n': sscanf(optarg,"%d",&nfolders); break; case 'l': sscanf(optarg,"%d",&ll); break; case 'f': sscanf(optarg,"%d",&NUMFILES); break; case 'b': sscanf(optarg,"%d",&LogNbin); break; case 'd': directory=optarg; break; default: throw std::runtime_error("invalid command line option");

}

c=getopt(argc,argv,"m:l:d:n:f:b:"); }

(31)

if((ll==-1)||(M==-1)||(!directory)||(nfolders==-1)||(LogNbin==-1)) {

printf("missing arguments\n mandatory arguments are:\n - log2 of the number of buckets in the sketch \n-d directory \n-l loglog counter number of bins \n -m number of rows in the sketch \n -n number of routers (subdirectories) \n -f (OPTIONAL) number of files per router (default is 2016) \n ");

return (-1); }

srand(871);

hasht = (unsigned int****)malloc(sizeof(unsigned int***)*M); for (int i=0; i<M; i++)

{ hasht[i]=(unsigned int***)malloc(sizeof(unsigned int**)*4); for (int k=0; k<4; k++) { hasht[i][k]=(unsigned int**)malloc(sizeof(unsigned int*)*4); for (int j=0; j<4; j++) { hasht[i][k][j]=(unsigned int*)malloc(sizeof(unsigned int)*nfolders); for(int tr=0;tr<nfolders;tr++) hasht[i][k][j][tr]=rand() %(P1-1); } } } srand(871);

hasht2 = (unsigned long long***)malloc(sizeof(unsigned long long**)*4096);

for (int i=0; i<4096; i++) {

hasht2[i]=(unsigned long long**)malloc(sizeof(unsigned long long*)*M);

for (int k=0; k<M; k++) {

(32)

hasht2[i][k]=(unsigned long long*)malloc(sizeof(unsigned long long)*4);

for (int j=0; j<4; j++)

hasht2[i][k][j]=rand() %(P2-1); }

}

int h_anom=M/2+1;

f<<"h_anom: "<<h_anom<<" soglia: "<<threshold<<endl; uint32 K=pow(2,LogNbin);

mu = (double**) malloc (sizeof(double*)*M); for (int i=0; i<M; i++)

{

mu[i] = (double*) malloc (sizeof(double)*K); for (uint32 j=0; j<K; j++)

mu[i][j]=0; }

var = (double**) malloc (sizeof(double*)*M); for (int i=0; i<M; i++)

{

var[i] = (double*) malloc (sizeof(double)*K); for (uint32 j=0; j<K; j++)

var[i][j]=0; }

Am = (int**) malloc (sizeof(int*)*M); for (int i=0; i<M; i++)

{

Am[i] = (int*) malloc (sizeof(int)*K); for (uint32 j=0; j<K; j++)

Am[i][j]=0; }

S= (double**) malloc (sizeof(double*)*M); for (int i=0; i<M; i++)

{

S[i] = (double*) malloc (sizeof(double)*K); for (uint32 j=0; j<K; j++)

(33)

}

for (int i=0;i<NUMFILES;i++) {

RevKSketch aggregated(M,LogNbin,ll); for (int k=0; k<M; k++)

for (uint32 j=0; j<K; j++) Am[k][j]=0; for (int r=0; r<nfolders; ++r) { RevKSketch local(M,LogNbin,ll); char foldername[200]; sprintf(foldername,"router_%d",r); char filename [200]; sprintf(filename,"%s/%s/%d.dat",directory,foldername,i); FILE* p =fopen(filename,"r"); assert(p); char row [1024]; while(fgets(row,1024,p)) { struct tuple tmp; memset(&tmp,0x0,sizeof(struct tuple)); char* cur=strtok(row," ,:"); assert(cur); tmp.sip=cco(cur); cur=strtok(NULL," ,:"); assert(cur); tmp.dip=cco(cur); cur=strtok(NULL," ,:"); assert(cur); sscanf(cur,"%hd",&tmp.sp); cur=strtok(NULL," ,:"); assert(cur); sscanf(cur,"%hd",&tmp.dp); cur=strtok(NULL," ,:"); local.AddValue(tmp.dip,tmp.dp,hasht,hasht2,r); } fclose(p);

(34)

aggregated.merge(local); }// per ogni folder r

aggregated.cusum(mu,var,i,threshold,S,Am); int count=0; for (int k=0; k<M; k++) { for (uint32 j=0; j<K; j++) if(Am[k][j]==1) { count++; break; } } if (count>h_anom) { f<<i<<endl;

for (int r=0; r<nfolders; ++r)

{ RevSketch aggregated2(M,LogNbin,ll); char foldername[200]; sprintf(foldername,"router_%d",r); char filename [200]; sprintf(filename,"%s/%s/%d.dat",directory,foldername,i); FILE* p =fopen(filename,"r"); assert(p); char row [1024]; while(fgets(row,1024,p)) { struct tuple tmp; memset(&tmp,0x0,sizeof(struct tuple)); char* cur=strtok(row," ,:"); assert(cur); tmp.sip=cco(cur);

(35)

cur=strtok(NULL," ,:"); assert(cur); tmp.dip=cco(cur); cur=strtok(NULL," ,:"); assert(cur); sscanf(cur,"%hd",&tmp.sp); cur=strtok(NULL," ,:"); assert(cur); sscanf(cur,"%hd",&tmp.dp); sscanf(cur,"%hd",&tmp.proto); aggregated2.crealista(Am,tmp.dip,hasht,r); }//fine while fclose(p);

list <uint32> offendingKeys; aggregated2.ChangeDetection(offendingKeys,Am);

for( list<uint32>::iterator listIt = offendingKeys.begin();

listIt != offendingKeys.end(); listIt++ )

{

for (int div=3;div>-1;div--) {

if(div==3)h<<"timebin"<<i<<", router "<<r<<": ";

uint32 jd=(*listIt>>(div* 8)) & 255;

h<<jd<<"."; }

h<<endl;

}

}// per ogni folder r }//fine if count>h_anom

}//per ogni file i for (int i=0; i<M; i++)

(36)

free(Am);

for (int i=0; i<M; i++) free(S[i]); free(S);

for (int i=0; i<M; i++) free(var[i]); free(var);

for (int i=0; i<M; i++) free(mu[i]); free(mu); free(hasht2); free(hasht); h.close(); return 0; }