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

In summary (as described by Esponda et al., 2006), a properly designed NDB can
act as a privacy-preserving storage system, which has the following properties:

Hard to reverse . Given an NDB, there should be no algorithm for obtaining
the positive-image PDB that is more e cient than exhaustive search.
Singleton NDB . Each hard-to-reverse entry in NDB represents either a string
in PDB, or no string at all, that is, reversing the database does not introduce
“false”-positive entries.
Easy to update . h ere should be e cient algorithms for adding and deleting
entries from the PDB.
Obfuscated size . h e size of the positive-image PDB should not be visible from
the NDB.
Probabilistic . A particular binary string s that belongs to PDB should have
many possible representations in NDB.

However, Danezis et al. (2007) described an e cient implement cryptographic
hash function to achieve the same functionalities as NDBs with security guaranteed.

4.10

Summary

h is chapter discusses various elements of NSAs in detail (Ceong et al., 2003;
Dasgupta, 1999a,b; Esponda and Forrest, 2002; Kim and Bentley, 2001; Stibor et al.,
2005, 2006). Diff erent NSAs are characterized by their representation schemes,
matching rules, and detector generation processes. h e detector generation mecha-
nism in NSAs, as described in the original model (Forrest et al., 1994), is a randomized
algorithm that generates candidates and then eliminates those that match self- samples
or training data. Except for the diff erence in the matching rules developed later,
most NSAs using string representation have the same or similar detector generation
process. In contrast, a few deterministic generation algorithms were also designed.
In many cases, they were described so as to study the algorithmic complexity and
detector coverage analytically (Ayara et al., 2002; D'haeseleer et al., 1996; Wierzchon,
2000). Because string representations provide a more convenient platform for such
analysis, deterministic algorithms are often discussed in such representations.
Kaers et al. (2003) categorized major detector generation algorithms into two types:
those built heavily on the assumption of the string representation: linear, greedy,
and binary template and those relatively independent of the “antibody morphol-
ogy”: exhaustive and NSMutation.
h e NSAs' uniqueness and strength can be grouped into two levels. h e
fundamental level includes some features that make this method really special:

No prior knowledge of nonself is required (D'haeseleer et al., 1996).
It is inherently distributable; no communication between detectors is needed
(D'haeseleer et al., 1996).