Segmentation fault in scipy.spatial.HalfspaceIntersection

[NateAM]

I am trying to compute the intersection of halfspaces using scipy.spatial.HalfspaceIntersection. When I run with a small data-set the code runs to completion but when I use a larger (though still small) dataset the code produces a segmentation fault.

The inputs to the function are a scipy.spatial.qhull.ConvexHull object, a list of lists of equations which define the bounding planes of a halfspace, and a bounding box for the ConvexHull object. I've included a pickle file which when placed in a directory with the attached python code causes the segmentation fault on my machine.

I am finding that it appears to be a problem with the equations that I go in as when I run with the same halfspace set over and over it will complete. If I run the command:

>python segmentation_fault.py segfault_data.pckl

which uses a particular collection of data I will see the segmentation fault. If you run

>python segmentation_fault.py n

where n is an integer it seems to work just fine.

I've attached the pickle file and a python script which demonstrates the problem.

Scipy/Numpy/Python version information:

scipy version: 1.1.0
numpy version: 1.14.2
system version info:sys.version_info(major=3, minor=6, micro=5, releaselevel='final', serial=0)

segfault_files.zip

Edit:

For a bit more info here is what comes out of a gdb run:

(gdb) run segmentation_fault.py segfault_data.pckl 
Starting program: /apps/anaconda3/bin/python segmentation_fault.py segfault_data.pckl
[Thread debugging using libthread_db enabled]
Missing separate debuginfo for /apps/anaconda3/lib/python3.6/site-packages/mkl_fft/../../../libiomp5.so
scipy version: 1.1.0
numpy version: 1.14.2
system version info:sys.version_info(major=3, minor=6, micro=5, releaselevel='final', serial=0)

Program received signal SIGSEGV, Segmentation fault.
0x00007fffe2455f90 in qh_memfree () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.212.el6.x86_64 libgcc-4.4.7-23.el6.x86_64
(gdb) bt
#0  0x00007fffe2455f90 in qh_memfree () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#1  0x00007fffe242f1db in qh_setfree () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#2  0x00007fffe244044b in qh_freebuild () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#3  0x00007fffe2440525 in qh_freeqhull () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#4  0x00007fffe2414767 in __pyx_pw_5scipy_7spatial_5qhull_6_Qhull_7close () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#5  0x00007fffe23e4762 in __Pyx_PyObject_CallNoArg () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#6  0x00007fffe2411dab in __pyx_pf_5scipy_7spatial_5qhull_6_Qhull___init__ () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#7  0x00007fffe2412810 in __pyx_pw_5scipy_7spatial_5qhull_6_Qhull_1__init__ () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#8  0x00007ffff7c489b7 in type_call ()
#9  0x00007fffe23cf74d in __Pyx_PyObject_Call () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#10 0x00007fffe23fdad9 in __pyx_pw_5scipy_7spatial_5qhull_21HalfspaceIntersection_1__init__ () from /apps/anaconda3/lib/python3.6/site-packages/scipy/spatial/qhull.cpython-36m-x86_64-linux-gnu.so
#11 0x00007ffff7bb8d7b in _PyObject_FastCallDict ()
#12 0x00007ffff7bbda03 in _PyObject_Call_Prepend ()
#13 0x00007ffff7bb899e in PyObject_Call ()
#14 0x00007ffff7c1502b in slot_tp_init ()
#15 0x00007ffff7c489b7 in type_call ()
#16 0x00007ffff7bb8d7b in _PyObject_FastCallDict ()
#17 0x00007ffff7c487ce in call_function ()
#18 0x00007ffff7c6acba in _PyEval_EvalFrameDefault ()
#19 0x00007ffff7c4270b in fast_function ()
#20 0x00007ffff7c48755 in call_function ()
#21 0x00007ffff7c6acba in _PyEval_EvalFrameDefault ()
#22 0x00007ffff7c41a94 in _PyEval_EvalCodeWithName ()
#23 0x00007ffff7c42941 in fast_function ()
#24 0x00007ffff7c48755 in call_function ()
#25 0x00007ffff7c6acba in _PyEval_EvalFrameDefault ()
#26 0x00007ffff7c43459 in PyEval_EvalCodeEx ()
#27 0x00007ffff7c441ec in PyEval_EvalCode ()
#28 0x00007ffff7cbe9a4 in run_mod ()
#29 0x00007ffff7cbeda1 in PyRun_FileExFlags ()
#30 0x00007ffff7cbefa4 in PyRun_SimpleFileExFlags ()
#31 0x00007ffff7cc2a9e in Py_Main ()
#32 0x00007ffff7b8a4be in main ()

[pv]

If you know how to convert the example input to the format understood by the QHull standalone "qhalf" program http://www.qhull.org/html/qhalf.htm, could be interesting to know if it crashes also.

[rgommers]

This doesn't crash for me with current main on 64-bit Linux:

In [1]: run ../tmp/crash_halfspace.py
scipy version: 1.9.0.dev0+2160.ddc0c90
numpy version: 1.22.3
system version info:sys.version_info(major=3, minor=10, micro=2, releaselevel='final', serial=0)
[[-0.00000000e+00 -0.00000000e+00  1.00000000e+00 -0.00000000e+00]
 [-0.00000000e+00 -0.00000000e+00  1.00000000e+00 -0.00000000e+00]
 [ 0.00000000e+00  1.00000000e+00  0.00000000e+00 -0.00000000e+00]
 [ 0.00000000e+00  1.00000000e+00  0.00000000e+00 -0.00000000e+00]
 [-1.00000000e+00  0.00000000e+00  0.00000000e+00 -1.00000000e+00]
 [-1.00000000e+00  0.00000000e+00  0.00000000e+00 -1.00000000e+00]
 [ 1.00000000e+00  0.00000000e+00 -0.00000000e+00 -0.00000000e+00]
 [ 1.00000000e+00  0.00000000e+00 -0.00000000e+00 -0.00000000e+00]
 [ 0.00000000e+00 -1.00000000e+00  0.00000000e+00 -1.00000000e+00]
 [ 0.00000000e+00 -1.00000000e+00  0.00000000e+00 -1.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00 -1.00000000e+00 -1.00000000e+00]
 [ 0.00000000e+00  0.00000000e+00 -1.00000000e+00 -1.00000000e+00]
 [-3.28379010e-01 -5.21749569e-01  7.87365616e-01 -2.45614702e-01]
 [ 4.58153366e-01  6.15620900e-01  6.41175796e-01  6.50773918e-01]
 [-2.68613164e-01  6.88569447e-01  6.73586732e-01  1.87008836e-01]
 [-8.67536922e-01  3.75057204e-01  3.26667696e-01 -3.99584260e-01]
 [-9.92627820e-01 -6.42592274e-02 -1.02765568e-01 -7.87212511e-01]
 [-4.85243264e-01 -7.86405701e-01  3.82236901e-01 -5.85446144e-01]
 [ 4.35523713e-01 -7.87805935e-01  4.35523713e-01  3.79511504e-02]
 [ 8.67536922e-01 -3.75057204e-01 -3.26667696e-01  2.51648964e-01]
 [ 1.64852723e-01 -9.80036617e-01  1.11138691e-01 -3.25473839e-01]
 [-4.07631459e-01 -6.45545153e-01 -6.45839027e-01 -7.62285577e-01]
 [ 0.00000000e+00  7.07106781e-01 -7.07106781e-01  5.55111512e-17]
 [ 7.42054668e-01  6.67788179e-02 -6.67004842e-01  2.15249961e-01]
 [-2.43903847e-01  9.14743829e-01  3.22109672e-01  1.69806178e-01]
 [-6.95063891e-01  7.04689714e-01 -1.42473136e-01 -3.20143827e-01]
 [-8.09912084e-01  3.40978699e-01 -4.77258780e-01 -6.42308136e-01]
 [-2.72510235e-01  9.42117006e-02 -9.57529283e-01 -5.09603998e-01]]
[-0.64067854 -0.38369867 -0.29192993]
intersections:
 [[-0.61142595 -0.39728621 -0.39728621]
 [-0.73264817 -0.35902185 -0.35902185]
 [-0.67738891 -0.27086792 -0.27086792]
 [-0.54747666 -0.31822621 -0.31822621]
 [-0.54747666 -0.31822621 -0.31822621]
 [-0.61142595 -0.39728621 -0.39728621]
 [-0.61142595 -0.39728621 -0.39728621]
 [-0.73877373 -0.41009459 -0.26791843]
 [-0.73580813 -0.34024225 -0.34024225]
 [-0.73264817 -0.35902185 -0.35902185]
 [-0.73264817 -0.35902185 -0.35902185]
 [-0.68409577 -0.34249666 -0.2003205 ]
 [-0.68138586 -0.34252606 -0.19920979]
 [-0.68013061 -0.27140858 -0.27140858]
 [-0.67738891 -0.27086792 -0.27086792]
 [-0.61471199 -0.46997695 -0.32255451]
 [-0.55158813 -0.39193743 -0.24451498]
 [-0.60293627 -0.39723073 -0.20274174]
 [-0.68013061 -0.27140858 -0.27140858]
 [-0.68013061 -0.27140858 -0.27140858]
 [-0.73580813 -0.34024225 -0.34024225]
 [-0.73580813 -0.34024225 -0.34024225]
 [-0.73558202 -0.42979541 -0.28642875]
 [-0.73698731 -0.42407058 -0.27643461]
 [-0.6618107  -0.47001672 -0.27552773]
 [-0.6571959  -0.47555644 -0.29016316]
 [-0.66139564 -0.47592096 -0.28714808]
 [-0.66117406 -0.47583075 -0.28668119]]

For whoever reads this next: the pickle file isn't needed to run the reproducer.

[cielavenir]

I was able to reproduce this issue:

I used https://hub.docker.com/layers/cielavenir/qhull/focal_scipy9025/images/sha256-16d21afab834011b2d80b18d1f50d07cf99f8f7ea5a1cce8c98a4fe9716aa666?context=repo or https://hub.docker.com/layers/cielavenir/qhull/buster_scipy9025/images/sha256-61f5e35eea0af66b7e1786936cb8f950eee6db71b4eb8eefd45d164b28690cf2?context=repo

• Debian Buster: python 3.7.3 / numpy 1.16.2 / scipy 1.1.0
• Ubuntu Focal: python 3.8.2 / numpy 1.17.4 / scipy 1.1.0

After loading this image, run python3 -m pip install dist/scipy*.whl then python3 segmentation_fault.py segfault_data.pckl.

Then I see this

double free or corruption (out)
Aborted

You do need scipy 1.1.0 to reproduce the issue.

[lucascolley]

Thanks @cielavenir , if the problem is gone on versions more recent that 1.1.0, then I think this can be closed.

[cielavenir]

python3 -m pip install scipy/dist/scipy*.whl, which uses #20440 , fixes the segfault.

[cielavenir]

@lucascolley it is unfortunate but we have not completed python3 migration, so we need scipy 1.2.3, which is below 1.4.0, so we are affected...

[lucascolley]

I don't think there's much we can do to help you if you are still on Python 2. New bugfix releases only happen for the last few minor versions unless there is something severe. There won't be another bugfix release for SciPy<1.4

[cielavenir]

Sure, anyway we can build my qhull-patched 1.2.3...