Αλγόριθμος Ε2*Β

Ο αλγόριθμος Ε2*Β είναι μια σειρά ειδικών αλγορίθμων που έχουν σχεδιαστεί,προκειμένου να αυξήσουν την αποτελεσματικότητα και την ικανότητα των NIDSes(Συστήματα Ανίχνευσης Εισβολέων)για τα δίκτυα υπολογιστών. Οι πρώτοι που εξέτασαν τον σχεδιασμό ειδικών αλγορίθμων των NIDSes ήταν οι Fisk και Varghere (2002).

Τα NIDSes λειτουργούν ως ασπίδα ενάντια στις προσπάθειες που θέτουν σε κίνδυνο την εμπιστευτικότητα,ακεραιότητα,διαθεσιμότητα ή ακόμα και την προσπάθεια να παρακαμφθεί η ασφάλεια μηχανισμού σε δίκτυα υπολογιστών. Η τυπική λειτουργία βασίζεται σε μια σειρά από υπογραφές από τις οποίες η καθεμία περιγράφει μια γνωστή απειλή που σκοπεύει να εισβάλλει στο δίκτυο.1 NIDSes εξετάζει την κίνηση στο δίκτυο και καθορίζει αν τυχόν υπογραφές προσπαθούν να εισβάλλουν κάνοντας δοκιμές αντιστοίχησης. Η πιο κοινή επιθεώρηση του είναι να αντιστοιχεί τα πρότυπα σειρών ενάντια στο πακέτο που παρελήφθη σε μια σύνδεση δικτύου. Έτσι,προκειμένου να επιβιώσουν στις υψηλές απαιτήσεις και στην ταχύτητα σύνδεσης τα NIDSes πρέπει να έχουν μεγάλη απόδοση για να ανιχνεύουν γρήγορα τους εισβολείς, καθώς και να λαμβάνουν υπόψη το κόστος στις χορδές προκειμένου να δρομολογήσουν την αναζήτηση και να ταξινομήσουν τα πακέτα σε IP forwarding. Ο αλγόριθμος http://www.snort.org/ έχει δείξει από πειράματα πως μπορεί να γίνει ως και 36% πιο γρήγορος, εφικτός από υπάρχοντες αλγορίθμους (π.χ. Boyer-Moore, Horspool), καθώς χρησιμοποιεί λιγότερες οδηγίες και λιγότερη μνήμη από τους υπόλοιπους.

Ε2*Β αλγόριθμος θεωρείται βέλτιστος, καθώς παρέχει γρήγορη αναζήτηση όταν μια συμβολοσειρά δεν υπάρχει στο ωφέλιμο φορτίο πακέτων. Επίσης, αντί να χρησιμοποιήσει χαρακτήρες των 8 bit ή των 16 bit όπως οι άλλοι, χρησιμοποιεί bit-strings αυθαίρετου μήκους. Το σύνολο των κανόνων που εφαρμόζει, είναι δομημένο σαν μια δισδιάστατη αλυσίδα, όπου κάθε στοιχείο έχει κεφαλίδα αλυσίδα. Όταν ένας κανόνας του πακέτου ταιριάζει στην κεφαλίδα σε μια σειρά εξετάσεων υπογραφών, τότε έχουμε εκτέλεση της συμβολοσειράς. Ο επιλεγμένος κανόνας από την αρχή αποτελείται από 187 κεφαλίδα με συνολικά 1.661 κανόνες από τους οποίους οι 1.575 είναι σειρές που ταιριάζουν στους κανόνες.

pre_process(char *input, int len){pktid=pktno & (1<<cellsize - 1);for (int idx = 0 ; idx < len-1 ; idx++) {element = s[idx]<< ( elementsize-8 ) ˆ s[idx+1];occurence_map [ element ] = pktid;}}search(char *s, char *input, int len_s, int len){for (int idx = 0 ; idx < len_s-1 ; idx++) {element= s[idx]<< ( elementsize-8 ) ˆ s[idx+1];if ( occurence_map [ element ] != pktid)return DOES_NOT_EXIST ;}return boyer_moore(s, len_s, input, len);}

Ο νέος αλγόριθμος που βελτιώνει αισθητά το ταίριασμα των χορδών και την επίδοσή των NIDSes μπορεί να λειτουργήσει αποτελεσματικά μόνο για κανόνες μεσαίου μεγέθους,καθώς σε μικρά ή πολύ μεγάλα σύνολα κανόνων δεν μπορούν να δουλέψουν.

• [http://www.google.gr/url?sa=t&rct=j&q=A+Domain-Specific+String+Matching+Algorithm+for+Intrusion+Detection&source=web&cd=4&ved=0CEIQFjAD&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.7.2593%26rep%3Drep1%26type%3Dpdf&ei=6pApT6fsIIa8-Qbgh5HDBQ&usg=AFQjCNGClqzu8gKOQqDQdBUWbWO8naR3Lw]