I'm no expert but this seems like a good case for doing random subsampling during the test.

IMO fast probabilistic total coverage test is better than no test or partial coverage.