Pervasive computing systems will likely be deployed in the near future, with the proliferation of wireless devices and the emergence of ad hoc networking as key enablers. Coping with mobility and the volatility of wireless communications in such systems is critical. Neighborhood discovery (ND) — the discovery of devices directly reachable for communication or in physical proximity — becomes a fundamental requirement and building block for various applications. However, the very nature of wireless mobile networks makes it easy to abuse ND and thereby compromise the overlying protocols and applications. Thus, providing methods to mitigate this vulnerability and secure ND is crucial. In this article we focus on this problem and provide definitions of neighborhood types and ND protocol properties, as well as a broad classification of attacks. Our ND literature survey reveals that securing ND is indeed a difficult and largely open problem. Moreover, given the severity of the problem, we advocate the need to formally model neighborhoods and analyze ND schemes.