ultra summit set segfaults

[jeanluct]

Bug uncovered by Bert Wiest.

--------------------------------------------------------
----------------  This is Braiding 1.0  ----------------
--------------------------------------------------------
-----|  Copyright (C) 2004 Juan Gonzalez-Meneses  |-----
-----| Braiding comes with ABSOLUTELY NO WARRANTY |-----
-----|           This is free software            |-----
-----| See GNU General Public License in GPL.txt  |-----
--------------------------------------------------------

l: Left Normal Form          r: Right Normal Form       

p: Permutation               x: Crossing numbers        

v: Least Common Multiple     ^: Greatest Common Divisor 

s: Super Summit Set          z: Centralizer             

e: Conjugacy Test            u: Ultra Summit Set        

t: Set of Sliding Circuits   a: Ask for Powers (On/Off)   

q: Quit             

--------------------------------------------------------

Choose an option: (type '?' for help) u

Set the number of strands: 6

Type a braid with 6 strands: ('6' = Delta)

2 1 3 2 1 4 3 2 5 4 3 2 1 1 4

Type the name of the output file: foo.txt

Segmentation fault (core dumped)

[jeanluct]

Some initial checks with valgrind. Make a file bug.in that contains

u
6
2 1 3 2 1 4 3 2 5 4 3 2 1 1 4
foo.txt

Then, after compiling with -g flag (and without -O) in the two Makefiles, run

valgrind --leak-check=yes --track-origins=yes --log-file=valgrind.out ./braiding < bug.in 

Output file valgrind.out:

==20190== Memcheck, a memory error detector
==20190== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==20190== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==20190== Command: ./braiding
==20190== Parent PID: 15179
==20190== 
==20190== Use of uninitialised value of size 8
==20190==    at 0x409D4E: CBraid::Factor<CBraid::ArtinPresentation>::At(int) const (cbraid_implementation.h:494)
==20190==    by 0x4084E3: CBraid::Factor<CBraid::ArtinPresentation>::Flip(int) const (cbraid_implementation.h:665)
==20190==    by 0x412734: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1000)
==20190==    by 0x413EFC: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1163)
==20190==    by 0x414502: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1213)
==20190==    by 0x414C4A: Braiding::USS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1270)
==20190==    by 0x4057B2: main (braiding_main.cpp:740)
==20190==  Uninitialised value was created by a stack allocation
==20190==    at 0x412635: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:992)
==20190== 
==20190== Invalid read of size 4
==20190==    at 0x409D4E: CBraid::Factor<CBraid::ArtinPresentation>::At(int) const (cbraid_implementation.h:494)
==20190==    by 0x4084E3: CBraid::Factor<CBraid::ArtinPresentation>::Flip(int) const (cbraid_implementation.h:665)
==20190==    by 0x412734: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1000)
==20190==    by 0x413EFC: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1163)
==20190==    by 0x414502: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1213)
==20190==    by 0x414C4A: Braiding::USS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1270)
==20190==    by 0x4057B2: main (braiding_main.cpp:740)
==20190==  Address 0x14 is not stack'd, malloc'd or (recently) free'd
==20190== 
==20190== 
==20190== Process terminating with default action of signal 11 (SIGSEGV)
==20190==  Access not within mapped region at address 0x14
==20190==    at 0x409D4E: CBraid::Factor<CBraid::ArtinPresentation>::At(int) const (cbraid_implementation.h:494)
==20190==    by 0x4084E3: CBraid::Factor<CBraid::ArtinPresentation>::Flip(int) const (cbraid_implementation.h:665)
==20190==    by 0x412734: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1000)
==20190==    by 0x413EFC: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1163)
==20190==    by 0x414502: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1213)
==20190==    by 0x414C4A: Braiding::USS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1270)
==20190==    by 0x4057B2: main (braiding_main.cpp:740)
==20190==  If you believe this happened as a result of a stack
==20190==  overflow in your program's main thread (unlikely but
==20190==  possible), you can try to increase the size of the
==20190==  main thread stack using the --main-stacksize= flag.
==20190==  The main thread stack size used in this run was 8388608.
==20190== 
==20190== HEAP SUMMARY:
==20190==     in use at exit: 934 bytes in 35 blocks
==20190==   total heap usage: 475 allocs, 440 frees, 89,710 bytes allocated
==20190== 
==20190== LEAK SUMMARY:
==20190==    definitely lost: 0 bytes in 0 blocks
==20190==    indirectly lost: 0 bytes in 0 blocks
==20190==      possibly lost: 0 bytes in 0 blocks
==20190==    still reachable: 934 bytes in 35 blocks
==20190==         suppressed: 0 bytes in 0 blocks
==20190== Reachable blocks (those to which a pointer was found) are not shown.
==20190== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==20190== 
==20190== For counts of detected and suppressed errors, rerun with: -v
==20190== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

[jeanluct]

The problem seems to come from the expressions *B1.FactorList.begin() in braiding.cpp, function Returns (near line 1000). If we print B1, we get (1|0). The first part is its LeftDelta, but the second part is zero. If we add some test code before line 1000:

  std::cerr << B1 << std::endl;
  if (B1.FactorList.empty())
    {
      std::cerr << "FactorList is empty.\n";
    }
  std::cerr << *B1.FactorList.begin() << std::endl;

we get the output

(1|0)
FactorList is empty.
[Segmentation fault (core dumped)

Thus, I think the problem is due to trying to copy an empty FactorList. In particular, a line like

C1=ArtinBraid((*B1.FactorList.begin()).Flip(B1.LeftDelta));

will segfault if FactorList is empty. As far as I can see the goal of *B1.FactorList.begin() is to get the first factor. Then it gets flipped, and a braid is created from that. But here the problem is that there is no FactorList, just a LeftDelta.

[jeanluct]

E-mail de Bert:

j'ai regardé un peu la tresse (pas le code), et je comprends ton analyse. La tresse devient Delta après un cyclage. Du coup, j'ai trouvé un exemple plus simple qui crée le même plantage : 

la tresse à 5 brins  2 1 3 2 1 4 3 2 1 1

Pour une raison qui m'échappe complètement, la tresse à 4 brins  2 1 3 2 1 1  ne provoque pas de plantage. Très étrange.

J'ai un programme de [Juan] qui donne quelques options supplémentaires, comme par exemple "USS conjugacy graph", "minimal conj. graph", "Trajectory under sliding" etc

Je viens d'essayer la tresse qui fait planter ton code sur son programme. Il ne plante pas, mais il fait une autre bêtise : il répond

---------------------------------------------------------------------------------------------------
This file contains the Ultra Summit Set of the braid on 6 strands:

2 1 3 2 1 4 3 2 5 4 3 2 1 1 4 

It has 2 orbits, whose sizes are: 1, 1.

Total size:     2

Thurston type:  Periodic.

Rigidity:       Rigid.

-------------------
 Orbit number 1        Rigid.     Conjugate to itself by Delta.
-------------------

    1:   D


-------------------
 Orbit number 2        Rigid.     Conjugate to the previous orbit by Delta.
-------------------

    1:   D
---------------------------------------------------------------------------------------------------

[miguelmarco]

This same bug appears to be hit here:

sagemath/sage#35529

It definitely looks like it gets confused about the factors in a braid that is a power of Delta.

[jeanluct]

Yes, I supposed we looked at this years ago but never fixed it. I seemed to have emailed Bert Wiest about it above. I'm not the author of the code and I didn't have time back then to look at it more deeply. Not sure if you have a patch to suggest.

[miguelmarco]

I am working on it, but might need some help understanding what the method does (in particular, what is it supposed to do in that case). I have emailed Juan Gonzalez Meneses and Maria cumplido for help.

[miguelmarco]

I am suspicious with the solution, because if I try to compute the centralizer of the examples that used to crash, I get something that indeed is in the centralizer, but does not contain the braid itself (which should be trivially on the centralizer).

[jeanluct]

I create a branch iss033-ultra-summit-set-segfaults with a bugfix suggested by Miguel.

The code doesn't crash, and the output of foo.txt is:

This file contains the Ultra Summit Set of the braid on 6 strands:

2 1 3 2 1 4 3 2 5 4 3 2 1 1 4 

It has 1 orbit, whose size is 1.

Total size:     1

Thurston type:  Periodic.

Rigidity:       Rigid.

-------------------
 Orbit number 1        Rigid.     Conjugate to itself by Delta.
-------------------

    1:   D

Does this look right?