The following code takes ~9 Minutes to finish while running at 100% on 1 CPU core (3.4 GHz). building: - cd into libiberty/ - gcc x.c -o x libiberty.a - ./x #include "../include/demangle.h" void main(void) { const char *input = "_ZZ1_DOaaaa1zmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm1Dclaa1D1VEE1VE2zo"; cplus_demangle(input, DMGL_GNU_V3); }
Hi Tim, Why is this a bug ? You give the demangler a pathological name and it takes a long time for it to process it. Where is the mystery ? Cheers Nick PS. You do not need to use a custom compiled program to see this behaviour, you can just pass the mangled name to the cxxfilt program: % cxxfilt _ZZ1_DOaaaa1zmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm1Dclaa1D1VEE1VE2zo _(V noexcept((z&&((((((((((((((((((((((((((((((((((D--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--)--))&&((D&&V)())))::zo Time spent in user mode (CPU seconds) : 125.645 Total time (wall clock seconds) : 2:05.74 CPU utilisation (CPU time/wall time) : 99.9% Maximum memory use (kilobytes) : 2344
Hi Nick, no mystery. But a possible DoS vector and in the end just an example that demangling may take longer as expected (and possibly necessary). Smaller and 'real-world' input may have the same issue just on a much smaller scale - so I wonder if this an 'easy-to-fix' code flaw or an 'fixed' design (flaw). Such a CPU hog also prevents proper fuzzing, thus it prevents finding other bugs. You sound like this is a well-known behavior of the demangler and nothing can be done. If that is the case, then sorry for not knowing. Feel free to close the issue :-)
Hi Tim, > Smaller and 'real-world' input may have the same issue just on a much > smaller scale - so I wonder if this an 'easy-to-fix' code flaw or an 'fixed' > design (flaw). I would say both... see below. > You sound like this is a well-known behavior of the demangler and nothing > can be done. If that is the case, then sorry for not knowing. Feel free to > close the issue :-) Well, it is a well known issue, but something could be done. The cause of the problem is basically due to the recursive nature of name mangling, and there is nothing that can be done about this. But there is a built-in recursion limit in the demangling code which is intended to catch cases like this one. It is controlled by the value of DEMANGLE_RECURSION_LIMIT which is defined in demangle.h. Currently this value is set to 2048, which was chosen because it does not break any of the existing demangling tests. But in theory itcould be smaller. For example, if you change the value 20 and rebuild, then your test case returns in less than one second. (The string is not demangled, because the limiter just stops the operation of the library function, but cpu resources are not hogged either). I did try changing the value to 1024, but this allowed the test case to have its slow down effect, and it is already known that 1024 prevents some real world name demangling from working, so it looks like there is no easy cure for this particular test. (I did consider making the limit definable via a command line option, but this would involve a lot of changes to the libiberty library and the tools that use it, and in the end an attacker would just disable it). So I am sorry, but I think that in this case there is nothing that we can do. Cheers Nick
(In reply to Nick Clifton from comment #3) > The cause of the problem is basically due to the recursive nature of name > mangling, and there is nothing that can be done about this. But there is a > built-in recursion limit in the demangling code which is intended to catch > cases like this one. It is controlled by the value of > DEMANGLE_RECURSION_LIMIT which is defined in demangle.h. Currently this > value is set to 2048, which was chosen because it does not break any of the > existing demangling tests. But in theory itcould be smaller. > > For example, if you change the value 20 and rebuild, then your test case > returns in less than one second. (The string is not demangled, because the > limiter just stops the operation of the library function, but cpu resources > are not hogged either). > > I did try changing the value to 1024, but this allowed the test case to have > its slow down effect, and it is already known that 1024 prevents some real > world name demangling from working, so it looks like there is no easy cure > for this > particular test. (I did consider making the limit definable via a command > line option, but this would involve a lot of changes to the libiberty > library and the tools that use it, and in the end an attacker would just > disable it). > > So I am sorry, but I think that in this case there is nothing that we can do. I already took a quick look at the weekend - the recursion depth toggled between 73,74,75 again and again. It looked like an endless loop but after a few millions (?) operations, it finally came to an end. Possibly the recursion counter can be moved, so that it increments at the beginning of the recursive function and decrements when it returns. I'll try to find some time in the next days to investigate further. I would add a comment in case I find a proposal for a solution.
Created attachment 12072 [details] Fix for 25180 (demangler slowness)
Hi Nick, the attached patch fixes the demangler slowness (see commit message for a description).
Hi Tim, (In reply to Tim Rühsen from comment #6) > the attached patch fixes the demangler slowness (see commit message for a > description). Did you run the libiberty testsuite to see if it introduces any new failures ? Also it would be a good idea to run the g++ testsuite as well, just in case... Given that you check for "d->d_counting > 1", would it make more sense to make that field a boolean ? If not, then should the limit be configurable somehow ? Other than that though the patch looks fine to me, but of course I cannot approve it. Are you going to submit it to gcc-patches ? Cheers Nick
Hi Nick, (In reply to Nick Clifton from comment #7) > > the attached patch fixes the demangler slowness (see commit message for a > > description). > > Did you run the libiberty testsuite to see if it introduces any new failures > ? I did, no (new) errors. What is the trick to run the test suite with valgrind (except from manually running each test) ? > Also it would be a good idea to run the g++ testsuite as well, just in > case... What is your suggestion to do that with least effort ? > Given that you check for "d->d_counting > 1", would it make more sense to > make that field a boolean ? If not, then should the limit be configurable > somehow ? No and no. Booleans can't be > 1 ;-) Just joking, in that case I also have to change d->d_printing to boolean, which is IMO an unrelated optimization / cleanup. I do not see any benefits in configuring the limit. > Other than that though the patch looks fine to me, but of course I cannot > approve it. Are you going to submit it to gcc-patches ? I will, thanks !
(In reply to Tim Rühsen from comment #8) Hi Tim, > I did, no (new) errors. What is the trick to run the test suite with > valgrind (except from manually running each test) ? Well assuming that you have a built toolchain available then: cd libiberty/testsuite make clean make check CC="valgrind gcc" Should work. > > Also it would be a good idea to run the g++ testsuite as well, just in > > case... > > What is your suggestion to do that with least effort ? Again assuming that you have a built toolchain available: cd gcc make check-gcc RUNTESTFLAGS="gcc/testsuite/g++.dg/dg.exp" Cheers Nick