Random failures with hypothesis.errors.StopTest exception raised

[tomato42]

I have a rather simple test case:
https://github.com/tlsfuzzer/tlslite-ng/blob/b6dd1c2bd3b3dc05bf1d794344ad4c2e4a0e20d9/unit_tests/test_tlslite_utils_cryptomath.py#L175-L184

    @given(integers(min_value=0, max_value=1<<16384))
    @example(0)
    @example(255)
    @example(256)
    @example((1<<1024)-1)
    @example((1<<521)-1)
    @example(1<<8192)
    @example((1<<8192)-1)
    def test_numBits(self, number):
        self.assertEqual(numBits(number), self.num_bits(number))

It's randomly failing:

ERROR: test_numBits (unit_tests.test_tlslite_utils_cryptomath.TestNumBits.test_numBits)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/runner/work/tlslite-ng/tlslite-ng/unit_tests/test_tlslite_utils_cryptomath.py", line 176, in test_numBits
    @example(0)
               ^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/core.py", line 1602, in wrapped_test
    raise the_error_hypothesis_found
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/core.py", line 1565, in wrapped_test
    state.run_engine()
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/core.py", line 1097, in run_engine
    runner.run()
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/engine.py", line 496, in run
    self._run()
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/engine.py", line 905, in _run
    self.generate_new_examples()
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/engine.py", line 699, in generate_new_examples
    prefix = self.generate_novel_prefix()
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/engine.py", line 352, in generate_novel_prefix
    return self.tree.generate_novel_prefix(self.random)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/datatree.py", line 672, in generate_novel_prefix
    (v, buf) = self._draw(
               ^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/datatree.py", line 770, in _draw
    value = draw_func(**kwargs, forced=forced)
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/data.py", line 1565, in draw_integer
    value = self.provider.draw_integer(**kwargs, forced=forced)
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/data.py", line 1087, in draw_integer
    return self._draw_bounded_integer(
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/data.py", line 1312, in _draw_bounded_integer
    probe = self._cd.draw_bits(
            ^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/data.py", line 1863, in draw_bits
    self.__check_capacity(n_bytes)
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/data.py", line 1905, in __check_capacity
    self.mark_overrun()
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/data.py", line 1930, in mark_overrun
    self.conclude_test(Status.OVERRUN)
  File "/opt/hostedtoolcache/Python/3.11.7/x64/lib/python3.11/site-packages/hypothesis/internal/conjecture/data.py", line 1917, in conclude_test
    raise StopTest(self.testcounter)
hypothesis.errors.StopTest: 3178

----------------------------------------------------------------------
Ran 1686 tests in 18.615s

FAILED (errors=1, skipped=32, expected failures=2)
You can add @seed(63542525054868526981564917001292471200) to this test to reproduce this failure.

This is with hypothesis-6.98.2 on python 3.11.7 (main, Dec 5 2023, 08:47:01) [GCC 11.4.0]

But I've seen it failing on Pythons from 3.8 up.

It's failing once about every 20-30 executions.

[tybug]

Thanks for the report! I have no doubt this regressed in #3818. I'll take a look later today.

[tybug]

Hmm. This is an overrun during generate_novel_prefix, due to the possibility that drawing a single node during novel generation takes more than BUFFER_SIZE in extreme cases. In the case above, this is a combination of unlucky successive probes + large max integer bounds (1500 bytes per probe).

One solution is retrying these overruns in generate_novel_prefix via a try/catch of StopTest. I'm nervous this will end in infinite loops or severe slowdowns in extreme cases, but I can't think of something that would repeatedly trigger this behavior in generate_novel_prefix while avoiding HealthCheck.too_large, so maybe this would be ok? (thinking aloud: what about a case where every novel prefix is > BUFFER_SIZE, so we hit this infinite loop before reaching enough overruns to raise the health check?)

[tomato42]

(yeah, yeah, I know some of those words.jpg)

Unfortunately I'm not able to help with this. What I can say, that I have some other non-trivial usages of hypothesis, ones that are complex enough that sometimes they time-out with old versions; so they may be good to verify sanity of complex test generation.