After recycling base=1 wt> Prevalence Threshol -Hash space Figure 4: When the bitmap covering the largest portion of the Figure 5: Content Sifting Algorithm as used in Early Bird ash space fills up, it is recycled. The bitmap is cleared most before recycling. Recycling covered by the bit 100 bytes is 55%, but for a worm with a signature of 20 bytes it increases to 92%o, and for 400 bytes to 99.64% The sampling value f represents a tradeoff between increase in the number of content sifting operations that processing and the probability of missing a worm; pro exceeds the capacity of our current CPU. While a faster cessing decreases linearly with f and the length of the in- CPU might solve this problem for a given traffic profile, variant content required increases linearly with f. Note the possibility of traffic surges and denial-of-service at hat all current worms have had invariant content of at acks on a sensor produce the same problem again. We least 400 bytes, for which the probability of false nega believe that a security device should not fail in these cir- tives is at most 0.36%. Our user-space software imple cumstances but instead smoothly scale back functionality mentation requires f= 1/64 to keep up with roughly to match capacity -still performing the same functions 200Mbps of traffic on a Gigabit Ethernet interface. Fi but perhaps with reduced fidelity or responsiveness nally, since the parameters of the Rabin fingerprint algo- The obvious approach to address this problem is via rithm p and M are not known, the worm writer cannot dynamic sampling. However, randomly sampling which determine which strings will not be sampled in advance substrings to process could cause us to miss a large frac tion of the occurrences of each substring and thus delay 5.4 Putting it together the generation of a worm's signature. Instead, we use Figure 5 depicts the content sifting algorithm imple sampling [20] and select only mented in the Early Bird prototype. As each packet ar- hich the fingerprint matches a certain pattern(e. g. the rives, its content(or substrings of its content) is hashed last 6 bits of the fingerprint are 0). Consequently, the al- d appended with the protocol identifier and destination gorithm will systematically ignore some substrings, but ort to produce a content hash code. In our implemen- track all occurrences of others. However, if a worm con- tation, we use a 32-bit Cyclic Redundancy Check(CRC) tains even a single tracked substring, it will be detected as a packet hash and 40-byte Rabin fingerprints for sub- as promptly as without the sampling. For example, if f string hashes. Each Rabin fingerprint is subsampled with is the fraction of the tracked substrings(e.g. f= 1/64 f= 1/64. The resulting hash codes are used to index if we track the substrings whose Rabin fingerprint ends the address dispersion table. If an entry already exists on 6 Os), then the probability of detecting a worm with a (the content has been determined to be prevalent) then signature of length z is Track(x)=1-e-/(x-9+1) the address dispersion table entries for source and desti- Since Rabin fingerprint are randomly distributed nation IP addresses(implemented as scaled bitmaps)are themselves, the probability of tracking a worm substring updated. If the source and destination counts exceed the of length B is f. Thus, the probability of missing the dispersion threshold, then the content string is reported. worm is pmiss(B)=l-f. The probability of not track If the content hash is not found in the dispersion ta- ing the worm is the probability of not tracking any ble, it is indexed into the content prevalence table. In Its substrings. If the worm signature has length I, it has our implementation, we use four independent hash func -B+ l substrings of length B. Assuming that no sub- tions of the content hash to create 4 indexes into four string of length B repeats in the signature, the probability counter arrays. Using the conservative update optimiza of not tracking the worm is Pmiss(r)=(1-f)x-p+l a tion, only the smallest among the four counters is incre e-f(x-p+1). For example with f=1/64 and B= 40, mented [10]. If all four counters are greater than the ne probability of tracking a worm with a signature of prevalence threshold, then a new entry is made in the adHash space Hash space Before recycling base=0 After recycling base=1 Figure 4: When the bitmap covering the largest portion of the hash space fills up, it is recycled. The bitmap is cleared and it is mapped to the largest uncovered portion of the hash space which is half the size of the portion covered by the bitmap right￾most before recycling. Recycling increments the variable base (see Figure 3) by one. increase in the number of content sifting operations that exceeds the capacity of our current CPU. While a faster CPU might solve this problem for a given traffic profile, the possibility of traffic surges and denial-of-service at￾tacks on a sensor produce the same problem again. We believe that a security device should not fail in these cir￾cumstances but instead smoothly scale back functionality to match capacity – still performing the same functions but perhaps with reduced fidelity or responsiveness. The obvious approach to address this problem is via dynamic sampling. However, randomly sampling which substrings to process could cause us to miss a large frac￾tion of the occurrences of each substring and thus delay the generation of a worm’s signature. Instead, we use value sampling [20] and select only those substrings for which the fingerprint matches a certain pattern (e.g. the last 6 bits of the fingerprint are 0). Consequently, the al￾gorithm will systematically ignore some substrings, but track all occurrences of others. However, if a worm con￾tains even a single tracked substring, it will be detected as promptly as without the sampling. For example, if f is the fraction of the tracked substrings (e.g. f = 1/64 if we track the substrings whose Rabin fingerprint ends on 6 0s), then the probability of detecting a worm with a signature of length x is ptrack(x) = 1 − e −f(x−β+1) . Since Rabin fingerprint are randomly distributed themselves, the probability of tracking a worm substring of length β is f. Thus, the probability of missing the worm is pmiss(β) = 1 − f. The probability of not track￾ing the worm is the probability of not tracking any of its substrings. If the worm signature has length x, it has x − β + 1 substrings of length β. Assuming that no sub￾string of length β repeats in the signature, the probability of not tracking the worm is pmiss(x) = (1−f) x−β+1 ≈ e −f(x−β+1) . For example with f = 1/64 and β = 40, the probability of tracking a worm with a signature of KEY COUNT Header Payload KEY DEST IP COUNT AD entry exists? Create AD entry Update counter else Counters > Dispersion Threshold? report KEY as suspected worm Key update counters Address Dispersion Table SRC IP COUNT Count > Prevalence Threshold? Content Prevalence Table protocol/dstPort +Payload Figure 5: Content Sifting Algorithm as used in EarlyBird. 100 bytes is 55%, but for a worm with a signature of 200 bytes it increases to 92%, and for 400 bytes to 99.64%. The sampling value f represents a tradeoff between processing and the probability of missing a worm; pro￾cessing decreases linearly with f and the length of the in￾variant content required increases linearly with f. Note that all current worms have had invariant content of at least 400 bytes, for which the probability of false nega￾tives is at most 0.36%. Our user-space software imple￾mentation requires f = 1/64 to keep up with roughly 200Mbps of traffic on a Gigabit Ethernet interface. Fi￾nally, since the parameters of the Rabin fingerprint algo￾rithm p and M are not known, the worm writer cannot determine which strings will not be sampled in advance. 5.4 Putting it together Figure 5 depicts the content sifting algorithm imple￾mented in the EarlyBird prototype. As each packet ar￾rives, its content (or substrings of its content) is hashed and appended with the protocol identifier and destination port to produce a content hash code. In our implemen￾tation, we use a 32-bit Cyclic Redundancy Check (CRC) as a packet hash and 40-byte Rabin fingerprints for sub￾string hashes. Each Rabin fingerprint is subsampled with f = 1/64. The resulting hash codes are used to index the address dispersion table. If an entry already exists (the content has been determined to be prevalent) then the address dispersion table entries for source and desti￾nation IP addresses (implemented as scaled bitmaps) are updated. If the source and destination counts exceed the dispersion threshold, then the content string is reported. If the content hash is not found in the dispersion ta￾ble, it is indexed into the content prevalence table. In our implementation, we use four independent hash func￾tions of the content hash to create 4 indexes into four counter arrays. Using the conservative update optimiza￾tion, only the smallest among the four counters is incre￾mented [10]. If all four counters are greater than the prevalence threshold, then a new entry is made in the ad-