  In wireless systems, neighbor discovery (ND) is a fundamental building block:
determining which devices are within direct radio communication is an enabler
for networking protocols and a wide range of applications. To thwart abuse of
ND and the resultant compromise of the dependent functionality of wireless
systems, numerous works proposed solutions to secure ND. Nonetheless, until
very recently, there has been no formal analysis of secure ND protocols. We
close this gap in \cite{asiaccs08}, but we concentrate primarily on the
derivation of an impossibility result for a class of protocols. In this paper,
we focus on reasoning about specific protocols. First, we contribute a number
of extensions and refinements on the framework of [24]. As we are particularly
concerned with the practicality of provably secure ND protocols, we investigate
availability and redefine accordingly the ND specification, and also consider
composability of ND with other protocols. Then, we propose and analyze two
secure ND protocols: We revisit one of the protocols analyzed in [24], and
introduce and prove correct a more elaborate challenge-response protocol.
