Information Technology Reference
In-Depth Information
of the schemata using the traditional “generate-and-test” strategy. h e candidate
detector (detection rule) is rejected if it contains any common schemata.
4.4
Analysis of Negative Selection Algorithms
NSAs are based on the following argument (Forrest et al., 1994): given a reasonably
large number of possible strings, the probability of two randomly chosen strings
matching each other is relatively low; if the detector set is generated randomly and
the abnormal strings can be considered as random to some extent, the probability
that an abnormal string matches some detector increases with the number of detec-
tors. Defi ning “failure probability” P f as the probability that the detector set fails
to detect a change, the main conclusion of Forrest et al. (1994) is
P M N R
P f
e
where P M is the probability of a match between two random strings and N R is the
number of detectors in the detector set. P M is largely decided by three major control
parameters: m , the number of alphabet symbols; l, the length of string; and r , the
number of contiguous bits (rcb) used in the matching rule.
4.4.1
Complexity of Detector Generation
D'haeseleer et al. (1996) analyzed an “exhaustive detector generating algorithm,”
and noted that a run fi nishes when the required number of detectors are gener-
ated; the number of detectors is chosen separately as a control parameter. h e time
complexity is
ln
P
f
O
N
S
P
(
1
P
)
N
s
m
m
where P M is the “matching probability,” the probability that a randomly chosen
string and a detector match, N S is the size of the self-set. h e space complexity is
O(l
N S ). For specifi c matching rules, such as the dynamic programming approach
(or linear time algorithm) with the rcb matching rule (D'haeseleer et al., 1996), its
time complexity is O((1
+
+
r)
N S )
O((1
r)
2 r )
O(l
N R ) and space complex-
ity is O((1
2 r ) , where l is the string length; r is the number of contiguous bits
in the matching rule (rcb) . h is is more costly in space than the exhaustive algo-
rithm. Also depending on the rcb matching rule, the greedy algorithm (D'haeseleer
et al., 1996) has higher time complexity O((l
r) 2
N R ) and the same space
complexity as the preceding algorithm, but it provides the maximum coverage for a
given number of detectors, and the number of unmatched nonself strings is known
(Balthrop et al., 2002).
r)
2 r
Search WWH ::




Custom Search