Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
pradyunsg opened this issue Dec 3, 2022 · 11 comments
Closed

Comments

@pradyunsg
Copy link

pradyunsg commented Dec 3, 2022

👋🏽

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 pypa/packaging#618. In my first attempt to do so, I seem to have successfully hit a NotImplementedError, details below. :)

Steps to reproduce

  • Create a Python 3.11 venv and activate.
  • pip install hypofuzz
  • pip install git+https://github.com/pypa/packaging.git@606c71acce93d04e778cdbdea16231b36d6b870f (get the current main)
  • Have a test like:
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")
  • Run hypothesis fuzz -- {the-test-file-above}.
  • Notice a traceback after a few seconds.

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
Copy link
Author

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 pradyunsg changed the title raise NotImplementedError("unreachable") error when a falsifying case is found Python 3.10+ triggers raise NotImplementedError("unreachable") when a falsifying case is found Dec 3, 2022
@pradyunsg pradyunsg changed the title Python 3.10+ triggers raise NotImplementedError("unreachable") when a falsifying case is found raise NotImplementedError("unreachable") when a falsifying case is found Dec 3, 2022
@pradyunsg
Copy link
Author

pradyunsg commented Dec 3, 2022

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
Copy link
Owner

Zac-HD commented Dec 19, 2022

🙏 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
Copy link
Author

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
Copy link

jgbos commented Dec 21, 2022

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:

  • HypoFuzz collects all tests, one in this case
  • Runs through all the tests
  • The test finds a failure and it is "popped" from the list of targets
  • Because there is only one test and a failure was found, the process exits with NotImplementedError error

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
Copy link
Owner

Zac-HD commented Dec 22, 2022

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.

@Zac-HD Zac-HD closed this as completed in 4817778 Dec 22, 2022
Zac-HD added a commit that referenced this issue Dec 22, 2022
Zac-HD added a commit that referenced this issue Dec 22, 2022
@jgbos
Copy link

jgbos commented Dec 22, 2022

@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
Copy link
Owner

Zac-HD commented Dec 22, 2022

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
Copy link
Author

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

@pradyunsg
Copy link
Author

pradyunsg commented Dec 22, 2022

FWIW, I ended up not using hypothesis and ended up with heavily-parameterised tests instead in pypa/packaging#624 :)

@Zac-HD
Copy link
Owner

Zac-HD commented Dec 23, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants