Caches are crucial components in modern processors (both stand-alone or integrated into SoCs) and their test is a challenging task, especially when addressing complex and high-frequency devices. While the test of the memory array within the cache is usually accomplished resorting to BIST circuitry implementing March test inspired solutions, testing the cache controller logic poses some specific issues, mainly stemming from its limited accessibility. One possible solution consists in letting the processor execute suitable test programs, allowing the detection of possible faults by looking at the results they produce. In this paper we face the issue of generating suitable programs for testing the replacement logic in set-associative caches that implement a deterministic replacement policy. A test program generation approach based on modeling the replacement mechanism as a finite state machine (FSM) is proposed. Experimental results with a cache implementing a LRU policy are provided to assess the effectiveness of the method.