Since a key advantage of Software Defined Networks (SDN) is providing a logically centralized view of the network topology, the correctness of such a view becomes critical for SDN applications to make the right management decisions. However, recently discovered vulnerabilities in OpenFlow Discovery Protocol (OFDP) show that malicious hosts and switches can poison the network view of the SDN controller and consequently lead to more severe security attacks, such as man-in-the-middle or denial of service. Several solutions have been proposed to address such topology poisoning attacks, but their scope is mostly limited to malicious hosts injecting or relaying fake Link Layer Discovery Protocol (LLDP) packets. In this work, we propose Stealthy Probing-based Verification (SPV), a novel stealthy probing-based approach, to significantly extend the scope of existing solutions. Specifically, SPV incrementally verifies legitimate links and detects fake links by sending probing packets. Such packets are sent in a stealthy manner to deceive malicious hosts or switches who may be trying to identify the probing attempts among normal traffic. To illustrate the feasibility of our approach, we implement SPV in an emulated SDN environment using Mininet and OpenDaylight. We further evaluate the applicability and the performance of SPV in a real SDN/cloud topology. We show that SPV can achieve a very low verification time (i.e., less than 120 milliseconds) in both real and emulated environments which makes SPV a scalable solution for large SDN networks.