Test programs for Software-based Self-Test (SBST) can be exploited during the mission phase of microprocessor-based systems to periodically assess hardware integrity. However, several additional constraints must be imposed due to the coexistence of test programs with the mission application. This paper proposes a method for the generation of SBST on-line test programs for embedded RISC processors, systems where the impact of on-line constraints is significant. The proposed strategy exploits an evolutionary optimizer that is able to create a complete test set of programs relying on a new cooperative scheme. Experimental results showed high fault coverage values on two different modules of a MIPS-like processor core. These two case studies demonstrate the effectiveness of the technique and the low human effort required for its implementation.