[libc++abi] Fix possible infinite loop in itanium demangler
authorMikhail Borisov <borisov.mikhail@gmail.com>
Tue, 17 Aug 2021 22:10:57 +0000 (18:10 -0400)
committerLouis Dionne <ldionne.2@gmail.com>
Tue, 17 Aug 2021 22:13:26 +0000 (18:13 -0400)
commitf0fcd42495432670664a661e75e7cae7e904dd3e
tree59b52a40b62c02deb6b8cc96106f2b913938fd18
parentdb7c68d80807bcb5127e9acc3818a3ae9855108c
[libc++abi] Fix possible infinite loop in itanium demangler

A libfuzzer run has discovered some inputs for which the demangler does
not terminate. When minimized, it looks like this: _Zcv1BIRT_EIS1_E

Deciphered:

_Z
cv    - conversion operator

      * result type
 1B   - "B"
 I    - template args begin
  R   - reference type              <.
   T_ - forward template reference   |  *
 E    - template args end            |  |
                                     |  |
      * parameter type               |  |
 I    - template args begin          |  |
  S1_ - substitution #1              * <'
 E    - template args end

The reason is: template-parameter refs in conversion operator result type
create forward-references, while substitutions are instantly resolved via
back-references. Together these can create a reference loop. It causes an
infinite loop in ReferenceType::collapse().

I see three possible ways to avoid these loops:

1. check if resolving a forward reference creates a loop and reject the
   invalid input (hard to traverse AST at this point)
2. check if a substitution contains a malicious forward reference and
   reject the invalid input (hard to traverse AST at this point;
   substitutions are quite common: may affect performance; hard to
   clearly detect loops at this point)
3. detect loops in ReferenceType::collapse() (cannot reject the input)

This patch implements (3) as seemingly the least-impact change. As a
side effect, such invalid input strings are not rejected and produce
garbage, however there are already similar guards in
`if (Printing) return;` checks.

Fixes https://llvm.org/PR51407

Differential Revision: https://reviews.llvm.org/D107712
libcxxabi/src/demangle/ItaniumDemangle.h
libcxxabi/test/test_demangle.pass.cpp
llvm/include/llvm/Demangle/ItaniumDemangle.h