In short -- your inputs may be non-deterministic (or effectively so) but your program is, by definition, deterministic. Isolate the input stream and replace it with a known stream and test that.

If you're using the build in rand to introduce random behavior, I humbly suggest my own Test::MockRandom. With it you can intercept the built-in rand function to return values that you preset in advance and can test for correct behavior across the range of potential results

If the source of randomness is truly out of your control (e.g. network packet timings), then my suggestion is to break up your code so that the external dependency is isolated and wrapped in a class. Then use Test::MockObject to simulate the dependency with known results and test across the full range of likely inputs.