memory corruption in braid centralizer

[dimpase]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**: Debian stable
- **Sage Version**: 10.0.beta9

Steps To Reproduce

Run

BG = BraidGroup(5)
b = BG([3, 3, 4, 3, 3, 2, 1, 4, 3, 2]) # b is s2^2*s3*s2^2*s1*s0*s3*s2*s1
b.centralizer()

Expected Behavior

something reasonable

Actual Behavior

sage: BG = BraidGroup(5)
sage: b = BG([3, 3, 4, 3, 3, 2, 1, 4, 3, 2]); b
s2^2*s3*s2^2*s1*s0*s3*s2*s1
sage: b.centralizer()
double free or corruption (out)

and the process hangs (with debian libbraiding 1.0), or segfauts (with libbraiding 1.1 and 1.2)

Additional Information

reported in https://groups.google.com/g/sage-support/c/TSowX4BXbXI/m/BHwHQaGDCAAJ
(also a problem in SageMath 8.2 until SageMath 9.8)

[tscrim]

I get a segfault, but it still is a bug. Close but slightly different things work.

As far as I can tell, this is an upstream bug in libbraiding.

[dimpase]

I'm using Debian's libbraiding, version 1.0-1+b1

[dimpase]

I just tried to update to libbrainding 1.2 (the latest), and am getting a segfault, too:

sage: b.centralizer()
---------------------------------------------------------------------------
SignalError                               Traceback (most recent call last)
Cell In [2], line 1
----> 1 b.centralizer()

File ~/work/software/sage/src/sage/groups/braid.py:1623, in Braid.centralizer(self)
   1611 def centralizer(self):
   1612     """
   1613     Return a list of generators of the centralizer of the braid.
   1614 
   (...)
   1621 
   1622     """
-> 1623     l = centralizer(self)
   1624     B = self.parent()
   1625     return [B._element_from_libbraiding(b) for b in l]

File ~/work/software/sage/src/sage/misc/lazy_import.pyx:404, in sage.misc.lazy_import.LazyImport.__call__()
    402         True
    403     """
--> 404     return self.get_object()(*args, **kwds)
    405 
    406 def __repr__(self):

File ~/work/software/sage/src/sage/libs/braiding.pyx:233, in sage.libs.braiding.centralizer()
    231         return [[[0], [i+1, nstrands - i -1]] for i in range(nstrands//2-1)] + [[[0], [nstrands//2]]]
    232 l = braid.Tietze()
--> 233 sig_on()
    234 cdef list[list[list[int]]] rop = CentralizerGenerators(nstrands, l)
    235 sig_off()

SignalError: Segmentation fault

[dimpase]

here is the patch to upgrade

index bb76fa5b60..2d4afc78a2 100644
--- a/build/pkgs/libbraiding/checksums.ini
+++ b/build/pkgs/libbraiding/checksums.ini
@@ -1,5 +1,5 @@
 tarball=libbraiding-VERSION.tar.gz
-sha1=06610e47eb243b27aea0ad399b41614fcdb179c9
-md5=5466605026b90bdca7ca20852f88b5c5
-cksum=704753563
-upstream_url=https://github.com/miguelmarco/libbraiding/releases/download/1.1/libbraiding-1.1.tar.gz
+sha1=b7e13778784fe1e36e7c0cbd7a4c234a090cd1b2
+md5=0513967c81b783ea66336b7ad0562534
+cksum=3619705925
+upstream_url=https://github.com/miguelmarco/libbraiding/releases/download/VERSION/libbraiding-VERSION.tar.gz
diff --git a/build/pkgs/libbraiding/package-version.txt b/build/pkgs/libbraiding/package-version.txt
index 9459d4ba2a..5625e59da8 100644
--- a/build/pkgs/libbraiding/package-version.txt
+++ b/build/pkgs/libbraiding/package-version.txt
@@ -1 +1 @@
-1.1
+1.2

[dimpase]

@miguelmarco - can you have a look?

[enriqueartal]

It is curious that the same computation in BraidGroup(n) works, n=6,7,8.

[jhpalmieri]

For what it's worth, this works fine for me with OS X (and Sage's libbraiding):

sage: BG = BraidGroup(5)
sage: b = BG([3, 3, 4, 3, 3, 2, 1, 4, 3, 2])
sage: b.centralizer()
[s0^-1*s1^-1*s2^-1*s3^-1*s0^-1*s3*s2*s1*s0*s3^2*s2*s1, s0*s2]

[dimpase]

works fine for me with OS X

quite different compiler, etc...

[jhpalmieri]

works fine for me with OS X

quite different compiler, etc...

Sure, I'm just adding a data point.

[miguelmarco]

I also get a segfault. It definitely comes from upstream (it segfaults also there). I will try to take a look, but it might be tricky to debug.

[dimpase]

I'd say that straight C++ code should be debuggable - valgrind etc to begin with.

[miguelmarco]

I have started looking around, and I think i found the exact line where it crashes:

https://github.com/jeanluct/cbraid/blob/e55b6f906eff801a5b3272aea883341b5387bf6f/lib/braiding.cpp#L1030

I think it is the same bug mentioned here :

jeanluct/cbraid#3

although we are hitting it in another place. It seems that it expects the braid to have factors, but it happens to be a power of Delta in disguise, so it has no factors. I have no clue why it is not a problem in different platforms.

[culler]

I am seeing the segfault on macOS Ventura with the binary release of SageMath 10.0.

[sheerluck]

I applied https://github.com/jeanluct/cbraid/pull/6/files to sci-libs/libbraiding-1.2 and got

sage: BG = BraidGroup(5)
sage: b = BG([3, 3, 4, 3, 3, 2, 1, 4, 3, 2])
....: b
s2^2*s3*s2^2*s1*s0*s3*s2*s1
sage: b.centralizer()
[s2*s3*s2^2*s1*s0*s3*s2*s1*s0]

[miguelmarco]

I applied https://github.com/jeanluct/cbraid/pull/6/files to sci-libs/libbraiding-1.2 and got

sage: BG = BraidGroup(5)
sage: b = BG([3, 3, 4, 3, 3, 2, 1, 4, 3, 2])
....: b
s2^2*s3*s2^2*s1*s0*s3*s2*s1
sage: b.centralizer()
[s2*s3*s2^2*s1*s0*s3*s2*s1*s0]

That patch gives an incorrect result: the centralizer of that braid is actually bigger (s0*s2 lives in it for example).

Still haven't found the reason why it fails. I suspect the origin is somewhere else in the code, and that is just the place where it explodes.

[miguelmarco]

A hacky workaround could be something like this:

def mycen(b):
    try:
        return b.centralizer()
    except:
        NB = BraidGroup(b.strands()+1)
        bigcen = NB(b).centralizer()
        return [br for br in bigcen if all(abs(i)<b.strands() for i in br.Tietze())]