Multimedia SoCs are characterized by a main controller that directs the activity of several cores, each of which is in charge of a stage in the processing of a media stream. The verification of these SoCs is a significant challenge due to time-to-market constraints and system complexity. We present a novel approach to system-level, random test case generation for multimedia SoCs, and a tool, called SoCVer, that implements this approach. We use the SoC's main controller point of view for controlling the flow of data in the SoC. Test case generation is done by allocating processing tasks to the various cores and determining which core processes which data item at what time. Solving these scheduling problems allows SoCVer to generate software for the SoC's main controller; this software coordinates and synchronizes the operations of all the cores on the chip without the need for the real operational software. We demonstrate the use of SoCVer using a DVD player SoC.