search

Zac-HD / hypofuzz

Adaptive fuzzing of Hypothesis tests
https://hypofuzz.com/docs
GNU Affero General Public License v3.0
82 stars 3 forks source link

`raise NotImplementedError("unreachable")` when a falsifying case is found #15

Closed pradyunsg closed 1 year ago

pradyunsg commented 1 year ago

👋🏽

I was trying to use hypothesis + hypofuzz to fuzz a hand-written parser in https://github.com/pypa/packaging/, after we got a report of a parser regression in https://github.com/pypa/packaging/issues/618. In my first attempt to do so, I seem to have successfully hit a NotImplementedError, details below. :)

Steps to reproduce

from hypothesis import given, strategies as st

from packaging._tokenizer import Tokenizer

@given(st.from_regex(r"[a-zA-Z\_\.\-]+", fullmatch=True))
def test_names(name: str) -> None:
    # GIVEN
    source = name

    # WHEN
    tokens = Tokenizer(source)

    # THEN
    assert tokens.match("IDENTIFIER")

Output

❯ hypothesis fuzz -- tests/test_requirements_tokeniser.py
using up to 1 processes to fuzz:
    tests/test_requirements_tokeniser.py::test_names

        Now serving dashboard at  http://localhost:9999/

 * Serving Flask app 'hypofuzz.dashboard'
 * Debug mode: off
WARNING: This is a development server. Do not use it in a production deployment. Use a production WSGI server instead.
 * Running on http://localhost:9999
Press CTRL+C to quit
127.0.0.1 - - [03/Dec/2022 12:16:11] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:11] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:11] "POST /_dash-update-component HTTP/1.1" 200 -
Process Process-2:
Traceback (most recent call last):
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/hypofuzz/hy.py", line 264, in _run_test_on
    self.__test_fn(*args, **kwargs)
  File "/Users/pradyunsg/Developer/github/packaging/tests/test_requirements_tokeniser.py", line 15, in test_names
    assert tokens.match("IDENTIFIER")
AssertionError: assert False
 +  where False = <bound method Tokenizer.match of <packaging._tokenizer.Tokenizer object at 0x106154490>>('IDENTIFIER')
 +    where <bound method Tokenizer.match of <packaging._tokenizer.Tokenizer object at 0x106154490>> = <packaging._tokenizer.Tokenizer object at 0x106154490>.match

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/Users/pradyunsg/.asdf/installs/python/3.11.0/lib/python3.11/multiprocessing/process.py", line 314, in _bootstrap
    self.run()
  File "/Users/pradyunsg/.asdf/installs/python/3.11.0/lib/python3.11/multiprocessing/process.py", line 108, in run
    self._target(*self._args, **self._kwargs)
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/hypofuzz/interface.py", line 91, in _fuzz_several
    fuzz_several(*tests)
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/hypofuzz/hy.py", line 381, in fuzz_several
    targets[0].run_one()
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/hypofuzz/hy.py", line 198, in run_one
    result = self._run_test_on(self.generate_prefix())
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/hypofuzz/hy.py", line 275, in _run_test_on
    traceback.format_exception(etype=type(e), value=e, tb=tb)
TypeError: format_exception() got an unexpected keyword argument 'etype'
Traceback (most recent call last):
  File "/Users/pradyunsg/Developer/github/packaging/.venv/bin/hypothesis", line 8, in <module>
    sys.exit(main())
             ^^^^^^
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/click/core.py", line 1130, in __call__
    return self.main(*args, **kwargs)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/click/core.py", line 1055, in main
    rv = self.invoke(ctx)
         ^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/click/core.py", line 1657, in invoke
    return _process_result(sub_ctx.command.invoke(sub_ctx))
                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/click/core.py", line 1404, in invoke
    return ctx.invoke(self.callback, **ctx.params)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/click/core.py", line 760, in invoke
    return __callback(*args, **kwargs)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/Developer/github/packaging/.venv/lib/python3.11/site-packages/hypofuzz/entrypoint.py", line 93, in fuzz
    raise NotImplementedError("unreachable")
NotImplementedError: unreachable
127.0.0.1 - - [03/Dec/2022 12:16:16] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:16] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:16] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:21] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:21] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:21] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:26] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:26] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:26] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:31] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:31] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:31] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:36] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:36] "POST /_dash-update-component HTTP/1.1" 200 -
127.0.0.1 - - [03/Dec/2022 12:16:36] "POST /_dash-update-component HTTP/1.1" 200 -
^CException ignored in atexit callback: <function _exit_function at 0x11fa62f20>
Traceback (most recent call last):
  File "/Users/pradyunsg/.asdf/installs/python/3.11.0/lib/python3.11/multiprocessing/util.py", line 357, in _exit_function
    p.join()
  File "/Users/pradyunsg/.asdf/installs/python/3.11.0/lib/python3.11/multiprocessing/process.py", line 149, in join
    res = self._popen.wait(timeout)
          ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/.asdf/installs/python/3.11.0/lib/python3.11/multiprocessing/popen_fork.py", line 43, in wait
    return self.poll(os.WNOHANG if timeout == 0.0 else 0)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/Users/pradyunsg/.asdf/installs/python/3.11.0/lib/python3.11/multiprocessing/popen_fork.py", line 27, in poll
    pid, sts = os.waitpid(self.pid, flag)
               ^^^^^^^^^^^^^^^^^^^^^^^^^^
KeyboardInterrupt:
pradyunsg commented 1 year ago

Ah, this is likely due to https://docs.python.org/3/library/traceback.html#traceback.format_exception changing signatures:

Changed in version 3.10: This function’s behavior and signature were modified to match print_exception().

pradyunsg commented 1 year ago

A different error happens on 3.9.

❯ hypothesis fuzz -- tests/test_requirements_tokeniser.py     
using up to 1 processes to fuzz:
    tests/test_requirements_tokeniser.py::test_names

        Now serving dashboard at  http://localhost:9999/

 * Serving Flask app 'hypofuzz.dashboard'
 * Debug mode: off
WARNING: This is a development server. Do not use it in a production deployment. Use a production WSGI server instead.
 * Running on http://localhost:9999
Press CTRL+C to quit
127.0.0.1 - - [03/Dec/2022 12:30:11] "POST / HTTP/1.1" 200 -
found failing example for tests/test_requirements_tokeniser.py::test_names
Process Process-2:
Traceback (most recent call last):
  File "/Users/pradyunsg/.asdf/installs/python/3.9.8/lib/python3.9/multiprocessing/process.py", line 315, in _bootstrap
    self.run()
  File "/Users/pradyunsg/.asdf/installs/python/3.9.8/lib/python3.9/multiprocessing/process.py", line 108, in run
    self._target(*self._args, **self._kwargs)
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/hypofuzz/interface.py", line 91, in _fuzz_several
    fuzz_several(*tests)
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/hypofuzz/hy.py", line 389, in fuzz_several
    raise Exception("Found failures for all tests!")
Exception: Found failures for all tests!
Traceback (most recent call last):
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/bin/hypothesis", line 8, in <module>
    sys.exit(main())
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/click/core.py", line 1130, in __call__
    return self.main(*args, **kwargs)
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/click/core.py", line 1055, in main
    rv = self.invoke(ctx)
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/click/core.py", line 1657, in invoke
    return _process_result(sub_ctx.command.invoke(sub_ctx))
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/click/core.py", line 1404, in invoke
    return ctx.invoke(self.callback, **ctx.params)
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/click/core.py", line 760, in invoke
    return __callback(*args, **kwargs)
  File "/Users/pradyunsg/Developer/github/packaging/.venv39/lib/python3.9/site-packages/hypofuzz/entrypoint.py", line 93, in fuzz
    raise NotImplementedError("unreachable")
NotImplementedError: unreachable
Zac-HD commented 1 year ago

🙏 Thanks so much for the report! I've been flat-out with EOY work projects and travelling home to see family over the break, but I'm aiming to fix this in the next few weeks.

Unfortunately HypoFuzz is more of an MVP / "spike" than a production-ready system, and then I joined @anthropics instead of having 6-12 months of PhD to harden it 😅... and Hypothesis itself soaks up most of the time I carve out for OSS. Hypofuzz is suffering somewhat from having too many big improvements on the table combined with few enough users that I'm more motivated to work on quicker wins elsewhere.

pradyunsg commented 1 year ago

Thanks @Zac-HD!

I'm looking forward to the fixes but please don't feel any sort of push for urgency on this from my end. :)

jgbos commented 1 year ago

First, @Zac-HD , this looks amazing and plan on taking full advantage of this tool.

I just ran into this same issue (ignoring the 3.10 error), but after inspecting fuzz_several the output seems correct. Here's what I think is going on:

I may look into customizing fuzz_several, my goal is to run tests continuously even if there is a failure. Are there any gotchas for just continuing to run the tests instead of doing targets.pop(0)? Will the new test randomize correctly or just repeat the same test? I can open another issue if this is a bigger discussion.

Zac-HD commented 1 year ago

Kudos @jgbos, that's it! The solution will be to print "all tests fail" and then sys.exit(1), so pretty similar tbh 😁

I may look into customizing fuzz_several, my goal is to run tests continuously even if there is a failure. Are there any gotchas for just continuing to run the tests instead of doing targets.pop(0)? Will the new test randomize correctly or just repeat the same test? I can open another issue if this is a bigger discussion.

It's going to take a slightly deeper refactor I think, including a pile of new dashboard code (😬) - if you just restart for that test it'll promptly pick the same failing example up from the database.

But more generally I'd strongly advise against continuing to run on failure for more than the few seconds we do in Hypothesis itself (in case e.g. the minimal and every non-minimal example fail with different errors). It's a common request, but IMO kinda misguided because either the code or the test will have to change, and the pressure to keep a 'clean' build is actually an important benefit from the fuzzer.

jgbos commented 1 year ago

@Zac-HD thanks for the feedback, glad I understood the error.

As for continuing to run, I realized the best approach is to create a new target with the same test function and strategy with a new random seed. I'm currently customizing to support testing black box systems and trying to understand the regions of success or failures.

Zac-HD commented 1 year ago

I'm currently customizing to support testing black box systems and trying to understand the regions of success or failures.

For that I'd suggest a test that never fails, but just logs and then discards whatever exception it raises 🙂

pradyunsg commented 1 year ago

Thanks for the fix @Zac-HD! ^.^

pradyunsg commented 1 year ago

FWIW, I ended up not using hypothesis and ended up with heavily-parameterised tests instead in https://github.com/pypa/packaging/pull/624 :)

Zac-HD commented 1 year ago

We'll get you someday, I'm sure 😁 (e.g. when you need to test non-ascii strings...)