This document proposes two new non-deterministic and fully distributed (NDFD) protocols called RAndom WaLk (RAWL) and Table-assisted RAndom WaLk (TRAWL) to detect clone attacks in wireless sensor networks. Previous solutions have drawbacks such as requiring central control or being vulnerable to compromising critical witness nodes. The proposed protocols select witnesses through random walks to distribute this process and prevent adversaries from easily identifying critical nodes. They fulfill security requirements with moderate overhead compared to existing NDFD approaches. Simulation results show the protocols outperform others in witness selection and that TRAWL has the lowest memory overhead. While communication overhead is higher, it is acceptable given security improvements over alternatives.