Project 4 of the Winter 2009 CS32 class was an Intrusion Prevention System. In this case, however, the Intrusion Prevention System was only a model: the streams and signatures were all plain text. The entire spec is still available.
From the spec:
What’s an Intrusion Prevention System? Well, it’s a software module that scans internet packets for malicious attacks and then blocks attacks. Modern security programs, like Norton Internet Security1, scan the contents of all incoming (from the Internet to your computer) and outgoing (visa versa) network packets for attacks that may harm your computer or originate from your computer and harm other computers. If an attack is found in any packet, that packet can be dropped and prevented from reaching/leaving your computer.
This was a very limited simulation. Packets all arrived in order, signatures were guaranteed to start with 6 constant characters and have a maximum length, and the use of a buffer was limited to 4500 characters. The hardest parts were making sure that offsets from the beginning of the stream were reported correctly and trying to minimize the number of times the same characters are re-scanned. One difficulty with the spec was that the implementation would never know that it was the last packet. Thus you had to maintain all characters relating to a partial match until you either matched a signature or were able to rule out a match, creating much repeated scanning of the same characters. I was not able to solve this problem elegantly in the assignment timeframe (although the professor was). Below is a class-diagram of my solution.
For my solution, I wrote an implementation of the Set (similar to STL Set) to store my detected Incidents and I created a Hash table for the signatures. I chose a set to store the Incidents so that I was guaranteed no duplicates, whereas I chose a Hash Table for the signatures for the O(1) performance. My set was unfortunately implemented as a circular linked list (with O(n) performance); it would have been much faster had I had the time to implement it as a Binary Search Tree. Packets were read into the buffer until there were at least 6 characters in the buffer. Once the buffer had sufficient characters, it was scanned against the hash table. My algorithm kept track of any partial matches—where the first part of a signature matched but the buffer did not contain enough characters to verify that the match was complete. If the algorithm was able to match a complete signature, it created an Incident marking the signature ID and the location in the stream. Once the entire buffer was scanned, the first part of the buffer was discarded up to the point of a partial match or the last 5 characters. Then a new packet is read into the buffer and we repeat! Since packets had a maximum length of 1500, and I discarded after each scan, the buffer was guaranteed to never reach beyond 3000 characters in size.
My solution was not very efficient. If the packet had included some parameter that described it as the last packet, it would have been quite simple to cut redundant scanning; just stop scanning as soon as you have reached a partial match in order to read in a new packet. However, this would create a bug in that incidents in the very last packet would not be caught if a partial match preceded that incident. Therefore, my solution had a bunch of redundant scanning and much more copying than would be warranted otherwise. This made my execution time rocket to about 10 times the Professor’s solution.
For those interested, my matching function is included below. It’s recursive, and probably like every other matching function, but here it is.
683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 | MatchType IPSImpl::match(const char* sig, const char* text) { for (size_t k = 0; sig[k] != '\0'; k++) { if (text[k] == '\0') { if (sig[k] == '*' && sig[k+1] == '\0') return MATCH; return PARTIAL_MATCH; } if (sig[k] == '*') //if the signature has a wildcard { for (size_t j = k; j-k <= WILDCARD_LENGTH; j++) { if (text[j] == sig[k + 1]) { MatchType temp = match(sig + k + 1, text + j); //recur if (temp != NO_MATCH) return temp; } if (text[j] == '\0') //could be a match in next packet return PARTIAL_MATCH; } return NO_MATCH; } if (sig[k] != text[k] && sig[k] != '?') return NO_MATCH; } return MATCH; } |
