Massive content about user's social, personal and professional life stored on Online Social Networks (OSNs) has attracted not only the attention of researchers and social analysts but also the cyber criminals. These cyber criminals penetrate illegally into an OSN by establishing fake profiles or by designing bots and exploit the vulnerabilities of an OSN to carry out illegal activities. With the growth of technology cyber crimes have been increasing manifold. Daily reports of the security and privacy threats in the OSNs demand not only the intelligent automated detection systems that can identify and alleviate fake profiles in real time but also the reinforcement of the security and privacy laws to curtail the cyber crime. In this paper, we have studied various categories of fake profiles like compromised profiles, cloned profiles and online bots (spam-bots, social-bots, like-bots and influential-bots) on different OSN sites along with existing cyber laws to mitigate their threats. In order to design fake profile detection systems, we have highlighted different category of fake profile features which are capable to distinguish different kinds of fake entities from real ones. Another major challenges faced by researchers while building the fake profile detection systems is the unavailability of data specific to fake users. The paper addresses this challenge by providing extremely obliging data collection techniques along with some existing data sources. Furthermore, an attempt is made to present several machine learning techniques employed to design different fake profile detection systems.