Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

1.2 THE TECHNIQUES: NETWORK ALGORITHMICS > 1.2.3 Thinking Algorithmically - Pg. 9

1.2 The Techniques: Network Algorithmics Threshold Array 0 2% Count Array 5 Get AIM://overflow # * # ! * # . . # . * 9 Evil code # 1% 3 Increment 255 F I G U R E 1.4 Strawman solution for detecting an evil packet by counting occurrences of each char- acter via a count array (middle) and then comparing in a final pass with an array of acceptable thresholds (left). 1.2.2 Strawman Solution The check of overall length is straightforward to implement, so we concentrate on checking for a prevalence of suspicious characters. The first strawman solution is illustrated in Figure 1.4. The chip maintains two arrays, T and C, with 256 elements each, one for each possible value of an 8-bit character. The threshold array, T , contains the acceptable percentage (as a fraction of the entire URL length) for each character. If the occurrences of a character in an actual URL fall above this fraction, the packet should be flagged. Each character can have a different threshold. The count array, C, in the middle, contains the current count C[i] for each possible character i. When the chip reads a new character i in the URL, it increments C[i] by 1. C[i] is initialized to 0 for all values of i when a new packet is encountered. The incrementing process starts only after the chip parses the HTTP header and recognizes the start of a URL.