A Randomized algorithm for constructing cross-feature tests from single feature tests

Abstract

Memory protocol commands and firmware features for storage solutions may function correctly by themselves, but due to implicit cross-feature dependencies they may exhibit incorrect behavior when exercised in combination with other features or commands. How can we effciently use a set of standalone per-feature tests to test the cross-features dependencies? We define an algorithm that is based on greedy and randomized heuristics that can produce an optimized plan for cross-feature testing within a polynomial number of steps. The algorithm is designed to meet cross-feature coverage requirements and was used to find problems in memory chip firmware with good results. We were consistently able to produce a cross-feature test plan in no more than 5 hours given a set of more than 1400 per-feature test variants. We have successfully discovered bugs caused by incorrectly handled interrupts and errors in managing a shared resource, that would have been missed by the per-feature tests method.