T Cell–Inspired Algorithms - Immunological Computation: Theory and Applications - page 75

h e existence of holes imposes a lower bound on the failure probability P f you
can achieve with a detection method because it will always fail to detect holes (see
Table 4.2). D'haeseleer et al. (1996) reported that the required number of detec-
tors to achieve a certain acceptable P f without taking holes into account the real
P f achieved with this detector set may be substantially higher than expected. Fur-
ther, the failure probability associated with the holes themselves does not improve
by distributing the algorithm if we use the same matching rule at all the sites.
D'haeseleer et al. (1996) gave an analysis of the number of detectors for a given
failure probability, P f , or the fraction of nonself strings that are not covered by the
detector set. Denoting the information content (or entropy) of a self-set S of size N S
as H(S) , and the information about S that is missing in the detector set R as H(S | R) ,
it is concluded that the diff erence between H(S) and H(S | R) , called “mutual infor-
mation” of S and R , is

≡ − ≈ ⋅

log 2 (1/P f )
For string length l and alphabet size m, the lower bound of detector size

I(S; R) H(S) H (S | R) N S

⋅
⋅

N log ( / 1 P )

s 2 f

N

R

l log ( m )

2

Table 4.2 Shows the Number of Holes and Best Achievable P f for Different

Confi gurations

Lowest
Possible P f e L a N b L b r b P c Number of Holes d

500 B 250 16 10 0.00391 634 0.0097

9 0.00879 4,438 0.0677

8 0.01953 21,076 0.3216

1 KB 250 32 11 0.00562 2,649 6.1676e-07

10 0.01172 24,911 5.8000e-06

9 0.02441 2,150,714 0.0005

8 0.05078 5.1815e + 08 0.1206

500 16 11 0.00171 882 0.0135

10 0.00391 3,854 0.0588

9 0.00879 24,937 0.3805

Note : These results were calculated on randomly generated self of sizes 500 bytes (B),
1 kilobytes (KB).
a Size of the dataset.
b Parameters chosen for the matching rule ( rcb ).
c Corresponding matching probability P M .
d Number of holes present.
e Resulting best achievable failure rate P f .
Source : Reported by D'haeseleer P., S. Forrest and P. Helman, An immunological
approach to change detection: Algorithms, analysis and implications.
Proceedings of the 9th IEEE Computer Security Foundations Workshop ,
pp. 18-26, Los Alamitos, CA, June, 1996.