It was shown that a test set for single stuck-at faults computed by injecting each fault into the fault free circuit and finding a test to distinguish the faulty circuit from the fault free one may be invalidated in the presence of faults that are not detected by the test set. We consider the problem of generating tests for single stuck-at faults that remain valid in the presence of undetected single stuck-at faults. We show that enumeration of all subsets of faults that may occur in the circuit without being detected may be too computation intensive, and is not necessary to obtain high-quality test sets. We present a test generation procedure to generate tests that remain valid in the presence of undetected faults. The procedure targets simultaneously multiple subsets of undetected faults that may be present in the circuit. It thus allows test generation time to be minimized by allowing the number of subsets of faults considered explicitly to be minimized. Based on this test generation procedure, several approximate procedures are also explored.