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.

Sign up for GitHub

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

Jump to bottom

implicitly fuzz RNG-dependent doctests with a random random seed #29935

Closed
dimpase opened this issue Jun 22, 2020 · 249 comments
Closed

implicitly fuzz RNG-dependent doctests with a random random seed #29935

dimpase opened this issue Jun 22, 2020 · 249 comments
Labels
c: doctest framework p: major / 3 t: enhancement
Milestone
sage-9.5

Comments

@dimpase
Copy link
Member

dimpase commented Jun 22, 2020

Our documentation and tests include a variety of
examples and tests involving randomness.

Those depend on a randomness seed, and up to Sage 9.1
they always used the same one: 0. Thus every run
of sage -t or make [p]test[all][long] would run
those "random" doctests deterministically.
In many cases, the output of those tests even relied
on that. As a result, random examples and tests
were actually testing that they were run non-randomly!

This is reminiscent of
an xkcd comic illustration of random number generators.

Based on these considerations and the
related sage-devel discussion,
we propose to:

  • allow specifying a randomness when running tests (Introduce random-seed option to allow fuzzing of doctests #29962),
  • adapt tests involving randomness, making sure they
    test mathematical functionality independent of
    the randomness seed used to run them (see roadmap),
  • default to a random randomness seed when none is specified
    (present ticket),

thus making those tests more robust and more useful,
by becoming more likely to reveal bugs in a variety
of cases including corner cases.

The first step (see #29962, merged in Sage 9.2)
adds a --random-seed flag to sage -t, allowing:

sage -t --long --random-seed=9876543210 src/sage/

Still, when no randomness seed is specified,
the default seed 0 is used. This means most testers
test with the same randomness seed, making "random"
doctests still mostly deterministic in practice.

Here is a way to pick a random randomness seed
and run tests with it (can be used to work on
the tickets in the roadmap):

$ randseed() {
    sage -c "import sage.misc.randstate as randstate; \
             randstate.set_random_seed(); \
             print(randstate.initial_seed())";
    }
$ SEED=$(randseed)
$ DIR=src/sage
$ echo "$ sage -t --long --random-seed=${SEED} ${DIR}" \
  && ./sage -t --long --random-seed=${SEED} ${DIR}

Once examples and tests involving randomness
have been adapted, the present ticket puts
the final touch by making it so that
when running tests with no seed specified,
a random one will be used:

sage -t src/sage/all.py 
Running doctests with ID 2020-06-23-23-19-03-8003eea5.
...
sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py
    [16 tests, 0.73 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.7 seconds
    cumulative wall time: 0.7 seconds

Being displayed in the output, the seed used
can be used again if needed:

sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py

allowing to explore any problematic case
revealed by running the tests with that seed.

Roadmap:

Follow-up:

Errors discovered by this ticket:

Depends on #32667

CC: @kliem @orlitzky @DaveWitteMorris @slel @mantepse

Component: doctest framework

Keywords: fuzz, random, seed

Author: Jonathan Kliem

Branch/Commit: 047379c

Reviewer: Michael Orlitzky

Issue created by migration from https://trac.sagemath.org/ticket/29935
@dimpase dimpase added this to the sage-9.2 milestone Jun 22, 2020
@dimpase

This comment has been minimized.

Sign in to view
@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

comment:3

Just so that we don't forget that we will have to update

https://doc.sagemath.org/html/en/developer/coding_basics.html

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

Work Issues: modify coding conventions

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

Dependencies: #29904

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

comment:5

geometry/hyperbolic_space/hyperbolic_geodesic.py makes some claims on how good approximations work, which doesn't seem to work. I had this thing run 7 times now and not one time did all tests pass. E.g. there is one test that gives me absolute errors of 0.7 when running this in the shell, but the test claims it is below 10**-9.

There is also #29904. Other than that the geometry module appears to ready.

Edit: And there is some place where you need to add set_random_seed(0) now or similar.

@dimpase
Copy link
Member Author

dimpase commented Jun 22, 2020

comment:6

Replying to @kliem:

geometry/hyperbolic_space/hyperbolic_geodesic.py makes some claims on how good approximations work, which doesn't seem to work. I had this thing run 7 times now and not one time did all tests pass. E.g. there is one test that gives me absolute errors of 0.7 when running this in the shell, but the test claims it is below 10**-9.

this is a great example of fuzzing catching an apparent error, it seems.

There is also #29904. Other than that the geometry module appears to ready.

Edit: And there is some place where you need to add set_random_seed(0) now or similar.

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

New commits:

d5fc5bestart from a "random" random seed for doctesting
5c7e562fix double description of hypercube
6b41bdbMerge branch 'public/29904' of git://trac.sagemath.org/sage into public/29935
b2954cefix random test in geometry/linear_expression

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

Branch: public/29935

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

Commit: b2954ce

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

comment:8

Even in the developer guide there is an example, where it is confusing:

sage: M = matrix.identity(3) + random_matrix(RR,3,3)/10^3
sage: M^2 # abs tol 1e-2
[1 0 0]
[0 1 0]
[0 0 1]

There is no mentioning there that only one particular matrix is tested.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jun 22, 2020

Branch pushed to git repo; I updated commit sha1. New commits:

dc49dd0update developer guide

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jun 22, 2020

Changed commit from b2954ce to dc49dd0

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

Changed work issues from modify coding conventions to none

@dimpase
Copy link
Member Author

dimpase commented Jun 22, 2020

comment:11

Replying to @kliem:

Even in the developer guide there is an example, where it is confusing:

sage: M = matrix.identity(3) + random_matrix(RR,3,3)/10^3
sage: M^2 # abs tol 1e-2
[1 0 0]
[0 1 0]
[0 0 1]

There is no mentioning there that only one particular matrix is tested.

indeed it assumes (?) that the entries of the random matrix are small in abs value

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

comment:12

Nothing to assume there. random_matrix(RR,3,3) has entries between -1 and 1. After dividing we are good.

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

Changed dependencies from #29904 to #29904, #29936

@mkoeppe
Copy link
Contributor

mkoeppe commented Jun 22, 2020

comment:14

How about making the random seed an option to sage-runtests. Then people can fuzz the doctests if they want.

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

comment:15

Will people do that? Especially enough to find incorrect claims. If you look into #29936 we have been claiming a preciseness that is far from true. Even if you consider the relative error instead of the absolute error. fuzzed doctests would have easily detected that. Even worse. Maybe the situation was better at some point and we never caught on about the regression.

@dimpase
Copy link
Member Author

dimpase commented Jun 22, 2020

comment:16

it is not a "real" (time-consuming) fuzzing, it is making the main random seed nondeterministic in tests. making it optional is akin to making tests optional.

we already found a couple of examples which show usefulness of this change in detecting bugs in Sage.

@mkoeppe
Copy link
Contributor

mkoeppe commented Jun 22, 2020

comment:17

The option that I propose to add needs to be added in any case, so that when a failure is revealed by a random random seeds, we can reproduce the failure with that seed.

@dimpase
Copy link
Member Author

dimpase commented Jun 22, 2020

comment:18

it is a good point - and the non-det. seed needs to be logged - if this is not yet in the branch it should get there.

@mkoeppe
Copy link
Contributor

mkoeppe commented Jun 22, 2020

comment:19

So I would suggest to use this ticket to introduce the option, not change the default.

@dimpase
Copy link
Member Author

dimpase commented Jun 22, 2020

comment:20

no, I don't agree, it makes no sense to test less if one can test more, and also not having it default would not force people to make their tests robust.

@mkoeppe
Copy link
Contributor

mkoeppe commented Jun 22, 2020

comment:21

By the way I don't think most doctests have the ambition to demonstrate correctness of mathematical claims. In my opinion, if a doctest intends to do that, it should run an explicit loop of several tests. Still deterministically.

@mkoeppe
Copy link
Contributor

mkoeppe commented Jun 22, 2020

comment:22

Why would creating the option and changing the default have to be done on the same ticket? I think it's best practices to separate the two steps on two tickets.

@kliem
Copy link
Contributor

kliem commented Jun 22, 2020

comment:23

Feel free to do with the branch whatever you think is reasonable.

@kliem
Copy link
Contributor

kliem commented Oct 13, 2021

comment:175

Thank you.

@orlitzky
Copy link
Contributor

comment:176

No problem, you'll have to rebase this onto the typo-fix too I think.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 13, 2021

Changed commit from 5739ef7 to 2c478d1

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 13, 2021

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. Last 10 new commits:

3cfe235implicitly fuzz RNG-dependent doctests
1980561reduce vertices for edge disjoint spanning trees
e6dd027do not remove fixed doctest
22c2b66simplify doctest
e32986cfix unstable doctests
7b1bd36fixed some doctests for disjoint spanning trees
812b555fix unstable doctest in book_stein_ent
74e505bedge disjoint spanning tree not as fast as claimed, see #32169
44cd7aefix doctest failure for random matrix
2c478d1one more unstable doctest

@kliem
Copy link
Contributor

kliem commented Oct 13, 2021

comment:179

Replying to @orlitzky:

No problem, you'll have to rebase this onto the typo-fix too I think.

I don't know, if this is necessary, but it sure doesn't hurt.

@vbraun
Copy link
Member

vbraun commented Oct 13, 2021

comment:180

Merge conflict

@kliem
Copy link
Contributor

kliem commented Oct 13, 2021

comment:181

This is the merge conflict, which permits a trivial solution (at least trivial for a human being):

diff --cc src/bin/sage-runtests
index d1fe6567e7,4fc2062b15..0000000000
--- a/src/bin/sage-runtests
+++ b/src/bin/sage-runtests
@@@ -64,59 -55,60 +55,97 @@@ if __name__ == "__main__"
               'if "external" is listed, will also run tests for available external software; '
               'if "build" is listed, will also run tests specific to Sage\'s build/packaging system; '
               'if set to "all", then all tests will be run')
++<<<<<<< HEAD
 +    parser.add_option("--randorder", type=int, metavar="SEED", help="randomize order of tests")
 +    parser.add_option("--random-seed", dest="random_seed", type=int, metavar="SEED", help="random seed (integer) for fuzzing doctests")
 +    parser.add_option("--global-iterations", "--global_iterations", type=int, default=0, help="repeat the whole testing process this many times")
 +    parser.add_option("--file-iterations", "--file_iterations", type=int, default=0, help="repeat each file this many times, stopping on the first failure")
 +    parser.add_option("--environment", type=str, default="sage.repl.ipython_kernel.all_jupyter", help="name of a module that provides the global environment for tests")
 +
 +    parser.add_option("-i", "--initial", action="store_true", default=False, help="only show the first failure in each file")
 +    parser.add_option("--exitfirst", action="store_true", default=False, help="end the test run immediately after the first failure or unexpected exception")
 +    parser.add_option("--force_lib", "--force-lib", action="store_true", default=False, help="do not import anything from the tested file(s)")
 +    parser.add_option("--abspath", action="store_true", default=False, help="print absolute paths rather than relative paths")
 +    parser.add_option("--verbose", action="store_true", default=False, help="print debugging output during the test")
 +    parser.add_option("-d", "--debug", action="store_true", default=False, help="drop into a python debugger when an unexpected error is raised")
 +    parser.add_option("--only-errors", action="store_true", default=False, help="only output failures, not test successes")
 +
 +    parser.add_option("--gdb", action="store_true", default=False, help="run doctests under the control of gdb")
 +    parser.add_option("--valgrind", "--memcheck", action="store_true", default=False,
 +                      help="run doctests using Valgrind's memcheck tool.  The log "
 +                         "files are named sage-memcheck.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--massif", action="store_true", default=False,
 +                      help="run doctests using Valgrind's massif tool.  The log "
 +                         "files are named sage-massif.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--cachegrind", action="store_true", default=False,
 +                      help="run doctests using Valgrind's cachegrind tool.  The log "
 +                         "files are named sage-cachegrind.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--omega", action="store_true", default=False,
 +                      help="run doctests using Valgrind's omega tool.  The log "
 +                         "files are named sage-omega.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +
 +    parser.add_option("-f", "--failed", action="store_true", default=False,
++=======
+     parser.add_argument("--randorder", type=int, metavar="SEED", help="randomize order of tests")
+     parser.add_argument("--random-seed", dest="random_seed", type=int, metavar="SEED", help="random seed for fuzzing doctests")
+     parser.add_argument("--global-iterations", "--global_iterations", type=int, default=0, help="repeat the whole testing process this many times")
+     parser.add_argument("--file-iterations", "--file_iterations", type=int, default=0, help="repeat each file this many times, stopping on the first failure")
+     parser.add_argument("--environment", type=str, default="sage.repl.ipython_kernel.all_jupyter", help="name of a module that provides the global environment for tests")
+ 
+     parser.add_argument("-i", "--initial", action="store_true", default=False, help="only show the first failure in each file")
+     parser.add_argument("--exitfirst", action="store_true", default=False, help="end the test run immediately after the first failure or unexpected exception")
+     parser.add_argument("--force_lib", "--force-lib", action="store_true", default=False, help="do not import anything from the test
...

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 13, 2021

Changed commit from 2c478d1 to 047379c

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Oct 13, 2021

Branch pushed to git repo; I updated commit sha1. New commits:

047379cfix merge conflict

@vbraun
Copy link
Member

vbraun commented Oct 19, 2021

Changed branch from public/29935-reb to 047379c

@vbraun vbraun closed this as completed in c6268d1 Oct 19, 2021
This was referenced May 27, 2021
Closed
Closed
Closed
Closed
Closed
Closed
Closed
@roed314 roed314 mentioned this issue Feb 22, 2022
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: doctest framework p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-9.5
Development

No branches or pull requests