Methods, apparatus and systems are provided that enable the generation of random regression suites for verification of a hardware or software design to be formulated as optimization problems. Solution of the optimization problems using probabilistic methods provides information on which set of test specifications should be used, and how many tests should be generated from each specification. In one mode of operation regression suites are constructed that use the minimal number of tests required to achieve a specific coverage goal. In another mode of operation regression suites are constructed so as to maximize task coverage when a fixed number of tests are run or within a fixed cost.