We present a metaheuristic-based attack against the traceability of an ultra-lightweight authentication protocol for RFID environments called SLMAP, and analyze its implications. The main interest of our approach is that it constitutes a complete black-box technique that does not make any assumptions on the components of the underlying protocol and can thus be easily generalized to analyze many other proposals.