[madez]

Randomized test with a suitable number of runs will cost-efficiently give useable results.

I agree, it's not trivial. But, it's not hard either.