Segmentation faults for small srgb

[f0k]

First of all, thanks a lot for packaging this!

I've noticed some interesting errors when creating a pairwise potential with very small stddev for the feature comparison. Minimal example:

import sys
import numpy as np
from pydensecrf import densecrf, utils

n = int(sys.argv[1])
s = float(sys.argv[2])

x = np.random.rand(1, n, n)
d = densecrf.DenseCRF2D(n, n, 2)
B = utils.create_pairwise_bilateral((30, 30), s, x, chdim=0)
print("addPairwiseEnergy()")
d.addPairwiseEnergy(B, 2.5)
print("worked.")

When passing a small scale parameter (1e-8 and smaller), I can provoke different crashes:

$ python3 crfbug.py 64 1e-7
addPairwiseEnergy()
worked.
$ python3 crfbug.py 64 1e-8
addPairwiseEnergy()
worked.
double free or corruption (out)
Aborted (core dumped)
$ python3 crfbug.py 128 1e-8
addPairwiseEnergy()
corrupted size vs. prev_size
Aborted (core dumped)
$ python3 crfbug.py 256 1e-8
addPairwiseEnergy()
free(): invalid pointer
Aborted (core dumped)
$ python3 crfbug.py 64 1e-10
addPairwiseEnergy()
Segmentation fault (core dumped)

The error message is not completely deterministic.

Relevant part of the backtrace for one of those:

#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1  0x00007ffff7a24801 in __GI_abort () at abort.c:79
#2  0x00007ffff7a6d897 in __libc_message (action=action@entry=do_abort, 
    fmt=fmt@entry=0x7ffff7b9ab9a "%s\n") at ../sysdeps/posix/libc_fatal.c:181
#3  0x00007ffff7a7490a in malloc_printerr (
    str=str@entry=0x7ffff7b9c870 "double free or corruption (out)")
    at malloc.c:5350
#4  0x00007ffff7a7be75 in _int_free (have_lock=0, p=0xecc0b0, 
    av=0x7ffff7dcfc40 <main_arena>) at malloc.c:4278
#5  __GI___libc_free (mem=0xecc0c0) at malloc.c:3124
#6  0x00007fffe97e1573 in Permutohedral::init (this=0xe6dc30, feature=...)
    at pydensecrf/densecrf/src/permutohedral.cpp:283
#7  0x00007fffe97d9d17 in DenseKernel::initLattice (f=..., this=0xe6dc20)
    at pydensecrf/densecrf/src/pairwise.cpp:42
#8  DenseKernel::DenseKernel (ntype=<optimized out>, ktype=<optimized out>, 
    f=..., this=0xe6dc20) at pydensecrf/densecrf/src/pairwise.cpp:121
#9  PairwisePotential::PairwisePotential (this=0xb517a0, features=..., 
    compatibility=<optimized out>, ktype=<optimized out>, 
    ntype=<optimized out>) at pydensecrf/densecrf/src/pairwise.cpp:171
#10 0x00007fffe97d25e0 in DenseCRF::addPairwiseEnergy (
    this=this@entry=0xea04a0, features=..., function=function@entry=0xb51710, 
    kernel_type=kernel_type@entry=DIAG_KERNEL, 
    normalization_type=normalization_type@entry=NORMALIZE_SYMMETRIC)
    at pydensecrf/densecrf/src/densecrf.cpp:56

So in this case, it crashed at https://github.com/lucasb-eyer/pydensecrf/blob/0632813/pydensecrf/densecrf/src/permutohedral.cpp#L283, I also get crashes at line 255 or 284. All this seems like some memory is overwritten somewhere.

Running valgrind --tool=memcheck --suppressions=valgrind-python.supp python3 crfbug.py 64 1e-8, the first two relevant errors are:

an invalid read

addPairwiseEnergy()
==30527== Invalid read of size 2
==30527==    at 0x1497415A: Permutohedral::init(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&) (permutohedral.cpp:270)
==30527==    by 0x1496CD16: initLattice (pairwise.cpp:42)
==30527==    by 0x1496CD16: DenseKernel (pairwise.cpp:121)
==30527==    by 0x1496CD16: PairwisePotential::PairwisePotential(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (pairwise.cpp:171)
==30527==    by 0x149655DF: DenseCRF::addPairwiseEnergy(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (densecrf.cpp:56)
==30527==    by 0x1495C7D0: __pyx_pf_10pydensecrf_8densecrf_8DenseCRF_4addPairwiseEnergy (densecrf.cpp:3236)
==30527==    by 0x1495C7D0: __pyx_pw_10pydensecrf_8densecrf_8DenseCRF_5addPairwiseEnergy(_object*, _object*, _object*) (densecrf.cpp:3100)
==30527==    by 0x50ABC4: ??? (in /usr/bin/python3.6)
==30527==    by 0x50C548: _PyEval_EvalFrameDefault (in /usr/bin/python3.6)
==30527==    by 0x5081D4: ??? (in /usr/bin/python3.6)
==30527==    by 0x50B3A2: PyEval_EvalCode (in /usr/bin/python3.6)
==30527==    by 0x635081: ??? (in /usr/bin/python3.6)
==30527==    by 0x635136: PyRun_FileExFlags (in /usr/bin/python3.6)
==30527==    by 0x6388EE: PyRun_SimpleFileExFlags (in /usr/bin/python3.6)
==30527==    by 0x639490: Py_Main (in /usr/bin/python3.6)
==30527==  Address 0x140b7c58 is 8 bytes before a block of size 32 alloc'd
==30527==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30527==    by 0x14973C04: Permutohedral::init(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&) (permutohedral.cpp:167)
==30527==    by 0x1496CD16: initLattice (pairwise.cpp:42)
==30527==    by 0x1496CD16: DenseKernel (pairwise.cpp:121)
==30527==    by 0x1496CD16: PairwisePotential::PairwisePotential(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (pairwise.cpp:171)
==30527==    by 0x149655DF: DenseCRF::addPairwiseEnergy(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (densecrf.cpp:56)
==30527==    by 0x1495C7D0: __pyx_pf_10pydensecrf_8densecrf_8DenseCRF_4addPairwiseEnergy (densecrf.cpp:3236)
==30527==    by 0x1495C7D0: __pyx_pw_10pydensecrf_8densecrf_8DenseCRF_5addPairwiseEnergy(_object*, _object*, _object*) (densecrf.cpp:3100)
==30527==    by 0x50ABC4: ??? (in /usr/bin/python3.6)
==30527==    by 0x50C548: _PyEval_EvalFrameDefault (in /usr/bin/python3.6)
==30527==    by 0x5081D4: ??? (in /usr/bin/python3.6)
==30527==    by 0x50B3A2: PyEval_EvalCode (in /usr/bin/python3.6)
==30527==    by 0x635081: ??? (in /usr/bin/python3.6)
==30527==    by 0x635136: PyRun_FileExFlags (in /usr/bin/python3.6)
==30527==    by 0x6388EE: PyRun_SimpleFileExFlags (in /usr/bin/python3.6)

shortly followed by an invalid write

==30696== Invalid write of size 4
==30696==    at 0x1497409A: Permutohedral::init(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&) (permutohedral.cpp:255)
==30696==    by 0x1496CD16: initLattice (pairwise.cpp:42)
==30696==    by 0x1496CD16: DenseKernel (pairwise.cpp:121)
==30696==    by 0x1496CD16: PairwisePotential::PairwisePotential(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (pairwise.cpp:171)
==30696==    by 0x149655DF: DenseCRF::addPairwiseEnergy(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (densecrf.cpp:56)
==30696==    by 0x1495C7D0: __pyx_pf_10pydensecrf_8densecrf_8DenseCRF_4addPairwiseEnergy (densecrf.cpp:3236)
==30696==    by 0x1495C7D0: __pyx_pw_10pydensecrf_8densecrf_8DenseCRF_5addPairwiseEnergy(_object*, _object*, _object*) (densecrf.cpp:3100)
==30696==    by 0x50ABC4: ??? (in /usr/bin/python3.6)
==30696==    by 0x50C548: _PyEval_EvalFrameDefault (in /usr/bin/python3.6)
==30696==    by 0x5081D4: ??? (in /usr/bin/python3.6)
==30696==    by 0x50B3A2: PyEval_EvalCode (in /usr/bin/python3.6)
==30696==    by 0x635081: ??? (in /usr/bin/python3.6)
==30696==    by 0x635136: PyRun_FileExFlags (in /usr/bin/python3.6)
==30696==    by 0x6388EE: PyRun_SimpleFileExFlags (in /usr/bin/python3.6)
==30696==    by 0x639490: Py_Main (in /usr/bin/python3.6)
==30696==  Address 0x140b7c28 is 8 bytes after a block of size 80 alloc'd
==30696==    at 0x4C3089F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==30696==    by 0x14973BD7: Permutohedral::init(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&) (permutohedral.cpp:166)
==30696==    by 0x1496CD16: initLattice (pairwise.cpp:42)
==30696==    by 0x1496CD16: DenseKernel (pairwise.cpp:121)
==30696==    by 0x1496CD16: PairwisePotential::PairwisePotential(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (pairwise.cpp:171)
==30696==    by 0x149655DF: DenseCRF::addPairwiseEnergy(Eigen::Matrix<float, -1, -1, 0, -1, -1> const&, LabelCompatibility*, KernelType, NormalizationType) (densecrf.cpp:56)
==30696==    by 0x1495C7D0: __pyx_pf_10pydensecrf_8densecrf_8DenseCRF_4addPairwiseEnergy (densecrf.cpp:3236)
==30696==    by 0x1495C7D0: __pyx_pw_10pydensecrf_8densecrf_8DenseCRF_5addPairwiseEnergy(_object*, _object*, _object*) (densecrf.cpp:3100)
==30696==    by 0x50ABC4: ??? (in /usr/bin/python3.6)
==30696==    by 0x50C548: _PyEval_EvalFrameDefault (in /usr/bin/python3.6)
==30696==    by 0x5081D4: ??? (in /usr/bin/python3.6)
==30696==    by 0x50B3A2: PyEval_EvalCode (in /usr/bin/python3.6)
==30696==    by 0x635081: ??? (in /usr/bin/python3.6)
==30696==    by 0x635136: PyRun_FileExFlags (in /usr/bin/python3.6)
==30696==    by 0x6388EE: PyRun_SimpleFileExFlags (in /usr/bin/python3.6)

Focusing on the latter, in https://github.com/lucasb-eyer/pydensecrf/blob/0632813/pydensecrf/densecrf/src/permutohedral.cpp#L255, it's writing beyond the array allocated in https://github.com/lucasb-eyer/pydensecrf/blob/0632813/pydensecrf/densecrf/src/permutohedral.cpp#L160, which is the barycentric array. So barycentric[j*(d_+2)+p ] seems to be used with a too large index. This probably means that the rank array contained negative values?

Anyway, that's all I can do quickly without delving into the algorithm and/or compiling the package myself. And I realize this is outside the scope of the Python wrapper, so you may not want to deal with this, but maybe at least it will help someone searching for this error.