"Eigenvalues did not converge" error uncovered by Coverage-guided Fuzzing #101

c-bata · 2021-03-09T01:44:23Z

Bug reports

To uncover bugs, I use hypothesis for coverage-guided fuzzing.

import hypothesis.extra.numpy as npst
import unittest
from hypothesis import given, strategies as st

from cmaes import CMA


class TestFuzzing(unittest.TestCase):
    @given(
        data=st.data(),
    )
    def test_cma_tell(self, data):
        dim = data.draw(st.integers(min_value=2, max_value=100))
        mean = data.draw(npst.arrays(dtype=float, shape=dim))
        sigma = data.draw(st.floats(min_value=1e-16))
        n_iterations = data.draw(st.integers(min_value=1))
        optimizer = CMA(mean, sigma)
        popsize = optimizer.population_size
        for _ in range(n_iterations):
            tell_solutions = data.draw(
                st.lists(st.tuples(npst.arrays(dtype=float, shape=dim), st.floats()),
                         min_size=popsize, max_size=popsize)
            )
            optimizer.ask()
            optimizer.tell(tell_solutions)
            optimizer.ask()

(venv) $ py.test tests/test_fuzzing.py 
===================================================================================== test session starts =====================================================================================
platform darwin -- Python 3.9.0, pytest-6.2.2, py-1.9.0, pluggy-0.13.1
rootdir: /Users/a14737/go/src/github.com/CyberAgent/cmaes
plugins: hypothesis-6.6.0
collected 1 item                                                                                                                                                                              

tests/test_fuzzing.py F                                                                                                                                                                 [100%]

========================================================================================== FAILURES ===========================================================================================
__________________________________________________________________________________ TestFuzzing.test_cma_tell __________________________________________________________________________________

self = <tests.test_fuzzing.TestFuzzing testMethod=test_cma_tell>

    @given(
>       data=st.data(),
    )

tests/test_fuzzing.py:10: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
tests/test_fuzzing.py:26: in test_cma_tell
    optimizer.ask()
cmaes/_cma.py:238: in ask
    x = self._sample_solution()
cmaes/_cma.py:258: in _sample_solution
    B, D = self._eigen_decomposition()
cmaes/_cma.py:250: in _eigen_decomposition
    D2, B = np.linalg.eigh(self._C)
<__array_function__ internals>:5: in eigh
    ???
venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:1471: in eigh
    w, vt = gufunc(a, signature=signature, extobj=extobj)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

err = 'invalid value', flag = 8

    def _raise_linalgerror_eigenvalues_nonconvergence(err, flag):
>       raise LinAlgError("Eigenvalues did not converge")
E       numpy.linalg.LinAlgError: Eigenvalues did not converge

venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:94: LinAlgError
----------------------------------------------------------------------------------------- Hypothesis ------------------------------------------------------------------------------------------
Falsifying example: test_cma_tell(
    self=<tests.test_fuzzing.TestFuzzing testMethod=test_cma_tell>,
    data=data(...),
)
Draw 1: 3
Draw 2: array([1.34078079e+138, 1.34078079e+138, 1.34078079e+138])
Draw 3: 1e-16
Draw 4: 1
Draw 5: [(array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0)]
====================================================================================== warnings summary =======================================================================================
tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/core/fromnumeric.py:87: RuntimeWarning: invalid value encountered in reduce
    return ufunc.reduce(obj, axis, dtype, out, **passkwargs)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:300: RuntimeWarning: overflow encountered in true_divide
    y_k = (x_k - self._mean) / self._sigma  # ~ N(0, C)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:328: RuntimeWarning: invalid value encountered in multiply
    self._pc = (1 - self._cc) * self._pc + h_sigma * math.sqrt(

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:2560: RuntimeWarning: overflow encountered in multiply
    s = (x.conj() * x).real

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/core/numeric.py:909: RuntimeWarning: overflow encountered in multiply
    return multiply(a.ravel()[:, newaxis], b.ravel()[newaxis, :], out)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:345: RuntimeWarning: invalid value encountered in multiply
    np.array([w * np.outer(y, y) for w, y in zip(w_io, y_k)]), axis=0

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:261: RuntimeWarning: overflow encountered in multiply
    x = self._mean + self._sigma * y  # ~ N(m, σ^2 C)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:261: RuntimeWarning: invalid value encountered in add
    x = self._mean + self._sigma * y  # ~ N(m, σ^2 C)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:300: RuntimeWarning: invalid value encountered in subtract
    y_k = (x_k - self._mean) / self._sigma  # ~ N(0, C)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:304: RuntimeWarning: invalid value encountered in add
    self._mean += self._cm * self._sigma * y_w

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/core/numeric.py:909: RuntimeWarning: invalid value encountered in multiply
    return multiply(a.ravel()[:, newaxis], b.ravel()[newaxis, :], out)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:315: RuntimeWarning: overflow encountered in exp
    self._sigma *= np.exp(

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:310: RuntimeWarning: overflow encountered in multiply
    self._p_sigma = (1 - self._c_sigma) * self._p_sigma + math.sqrt(

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:2561: RuntimeWarning: overflow encountered in reduce
    return sqrt(add.reduce(s, axis=axis, keepdims=keepdims))

-- Docs: https://docs.pytest.org/en/stable/warnings.html
=================================================================================== short test summary info ===================================================================================
FAILED tests/test_fuzzing.py::TestFuzzing::test_cma_tell - numpy.linalg.LinAlgError: Eigenvalues did not converge
=============================================================================== 1 failed, 14 warnings in 6.53s ================================================================================

Expected Behavior

Does not raise exception.

Context

Please provide any relevant information about your setup. This is important in case the issue is not reproducible except for under certain conditions.

cmaes version or commit revision: b112c0c ( hypothesis branch)

The text was updated successfully, but these errors were encountered:

c-bata · 2021-04-10T15:52:40Z

Most minimal code to reproduce is here:

import numpy as np
from cmaes import CMA


def main():
    mean = np.array([1.34078079e+138, 1.34078079e+138, 1.34078079e+138], dtype=float)
    optimizer = CMA(mean=mean, sigma=1e-16)
    while True:
        solutions = []
        for _ in range(optimizer.population_size):
            x = np.zeros(3)
            solutions.append((x, 0.0))
        optimizer.tell(solutions)


if __name__ == "__main__":
    main()

$ python examples/quadratic_function.py 
/Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:2561: RuntimeWarning: overflow encountered in reduce
  return sqrt(add.reduce(s, axis=axis, keepdims=keepdims))
/Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:315: RuntimeWarning: overflow encountered in exp
  self._sigma *= np.exp(
Traceback (most recent call last):
  File "/Users/a14737/go/src/github.com/CyberAgent/cmaes/examples/quadratic_function.py", line 17, in <module>
    main()
  File "/Users/a14737/go/src/github.com/CyberAgent/cmaes/examples/quadratic_function.py", line 13, in main
    optimizer.tell(solutions)
  File "/Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py", line 296, in tell
    B, D = self._eigen_decomposition()
  File "/Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py", line 250, in _eigen_decomposition
    D2, B = np.linalg.eigh(self._C)
  File "<__array_function__ internals>", line 5, in eigh
  File "/Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/linalg/linalg.py", line 1471, in eigh
    w, vt = gufunc(a, signature=signature, extobj=extobj)
  File "/Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/linalg/linalg.py", line 94, in _raise_linalgerror_eigenvalues_nonconvergence
    raise LinAlgError("Eigenvalues did not converge")
numpy.linalg.LinAlgError: Eigenvalues did not converge

c-bata · 2021-04-10T16:04:18Z

Fixed the previous error at 3c1dd0d, then found new errors:

$ py.test tests/test_fuzzing.py 
================================================================================================================= test session starts ==================================================================================================================
platform darwin -- Python 3.9.0, pytest-6.2.2, py-1.9.0, pluggy-0.13.1
rootdir: /Users/a14737/go/src/github.com/CyberAgent/cmaes
plugins: hypothesis-6.6.0
collected 1 item                                                                                                                                                                                                                                       

tests/test_fuzzing.py F                                                                                                                                                                                                                          [100%]

======================================================================================================================= FAILURES =======================================================================================================================
______________________________________________________________________________________________________________ TestFuzzing.test_cma_tell _______________________________________________________________________________________________________________

self = <tests.test_fuzzing.TestFuzzing testMethod=test_cma_tell>

    @given(
>       data=st.data(),
    )

tests/test_fuzzing.py:10: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
tests/test_fuzzing.py:29: in test_cma_tell
    optimizer.ask()
cmaes/_cma.py:241: in ask
    x = self._sample_solution()
cmaes/_cma.py:261: in _sample_solution
    B, D = self._eigen_decomposition()
cmaes/_cma.py:253: in _eigen_decomposition
    D2, B = np.linalg.eigh(self._C)
<__array_function__ internals>:5: in eigh
    ???
venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:1471: in eigh
    w, vt = gufunc(a, signature=signature, extobj=extobj)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

err = 'invalid value', flag = 8

    def _raise_linalgerror_eigenvalues_nonconvergence(err, flag):
>       raise LinAlgError("Eigenvalues did not converge")
E       numpy.linalg.LinAlgError: Eigenvalues did not converge

venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:94: LinAlgError
---------------------------------------------------------------------------------------------------------------------- Hypothesis ----------------------------------------------------------------------------------------------------------------------
Falsifying example: test_cma_tell(
    self=<tests.test_fuzzing.TestFuzzing testMethod=test_cma_tell>,
    data=data(...),
)
Draw 1: 3
Draw 2: array([0., 0., 0.])
Draw 3: 1e-16
Draw 4: 1
Draw 5: [(array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([0., 0., 0.]), 0.0), (array([1.34078079e+138, 1.34078079e+138, 1.34078079e+138]), 0.0)]
=================================================================================================================== warnings summary ===================================================================================================================
tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:303: RuntimeWarning: overflow encountered in true_divide
    y_k = (x_k - self._mean) / self._sigma  # ~ N(0, C)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/core/fromnumeric.py:87: RuntimeWarning: invalid value encountered in reduce
    return ufunc.reduce(obj, axis, dtype, out, **passkwargs)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/core/numeric.py:909: RuntimeWarning: overflow encountered in multiply
    return multiply(a.ravel()[:, newaxis], b.ravel()[newaxis, :], out)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:303: RuntimeWarning: invalid value encountered in true_divide
    y_k = (x_k - self._mean) / self._sigma  # ~ N(0, C)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:307: RuntimeWarning: invalid value encountered in multiply
    self._mean += self._cm * self._sigma * y_w

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/core/numeric.py:909: RuntimeWarning: invalid value encountered in multiply
    return multiply(a.ravel()[:, newaxis], b.ravel()[newaxis, :], out)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:348: RuntimeWarning: invalid value encountered in multiply
    np.array([w * np.outer(y, y) for w, y in zip(w_io, y_k)]), axis=0

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:331: RuntimeWarning: invalid value encountered in multiply
    self._pc = (1 - self._cc) * self._pc + h_sigma * math.sqrt(

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:303: RuntimeWarning: invalid value encountered in subtract
    y_k = (x_k - self._mean) / self._sigma  # ~ N(0, C)

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:307: RuntimeWarning: invalid value encountered in add
    self._mean += self._cm * self._sigma * y_w

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:2560: RuntimeWarning: overflow encountered in multiply
    s = (x.conj() * x).real

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/cmaes/_cma.py:318: RuntimeWarning: overflow encountered in exp
    self._sigma *= np.exp(

tests/test_fuzzing.py::TestFuzzing::test_cma_tell
  /Users/a14737/go/src/github.com/CyberAgent/cmaes/venv/lib/python3.9/site-packages/numpy/linalg/linalg.py:2561: RuntimeWarning: overflow encountered in reduce
    return sqrt(add.reduce(s, axis=axis, keepdims=keepdims))

-- Docs: https://docs.pytest.org/en/stable/warnings.html
=============================================================================================================== short test summary info ================================================================================================================
FAILED tests/test_fuzzing.py::TestFuzzing::test_cma_tell - numpy.linalg.LinAlgError: Eigenvalues did not converge
============================================================================================================ 1 failed, 13 warnings in 6.04s ============================================================================================================

c-bata added the bug Something isn't working label Mar 9, 2021

c-bata added this to the v1.0 release milestone Mar 9, 2021

c-bata changed the title ~~Found an "Eigenvalues did not converge" error by Coverage-guided Fuzzing~~ "Eigenvalues did not converge" error uncovered by Coverage-guided Fuzzing Mar 9, 2021

c-bata mentioned this issue Apr 10, 2021

Fix overflow errors uncovered by Coverage-guided Fuzzing. #104

Merged

c-bata closed this as completed in #104 Apr 10, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

"Eigenvalues did not converge" error uncovered by Coverage-guided Fuzzing #101

"Eigenvalues did not converge" error uncovered by Coverage-guided Fuzzing #101

c-bata commented Mar 9, 2021 •

edited

Loading

c-bata commented Apr 10, 2021 •

edited

Loading

c-bata commented Apr 10, 2021 •

edited

Loading

"Eigenvalues did not converge" error uncovered by Coverage-guided Fuzzing #101

"Eigenvalues did not converge" error uncovered by Coverage-guided Fuzzing #101

Comments

c-bata commented Mar 9, 2021 • edited Loading

Bug reports

Expected Behavior

Context

c-bata commented Apr 10, 2021 • edited Loading

c-bata commented Apr 10, 2021 • edited Loading

c-bata commented Mar 9, 2021 •

edited

Loading

c-bata commented Apr 10, 2021 •

edited

Loading

c-bata commented Apr 10, 2021 •

edited

Loading