  The Sybil attack in unknown port networks such as wireless is not considered
tractable. A wireless node is not capable of independently differentiating the
universe of real nodes from the universe of arbitrary non-existent fictitious
nodes created by the attacker. Similar to failure detectors, we propose to use
universe detectors to help nodes determine which universe is real. In this
paper, we (i) define several variants of the neighborhood discovery problem
under Sybil attack (ii) propose a set of matching universe detectors (iii)
demonstrate the necessity of additional topological constraints for the
problems to be solvable: node density and communication range; (iv) present
SAND -- an algorithm that solves these problems with the help of appropriate
universe detectors, this solution demonstrates that the proposed universe
detectors are the weakest detectors possible for each problem.
