Testing cache memories is a challenging task, especially when targeting complex and high-frequency devices such as modern processors. While the memory array in a cache is usually tested exploiting BIST circuits that implement March-based solutions, there is no established methodology to tackle the cache controller logic, mainly due to its limited accessibility. One possible approach is Software-Based Self Testing (SBST): however, devising test programs able to thoroughly excite the replacement logic and made the results observable is not trivial. A test program generation approach, based on a Finite State Machine (FSM) model of the replacement mechanism, is proposed in this paper. The effectiveness of the method is assessed on a case study considering a data cache implementing the pLRU replacement policy.