LLVM Bugzilla is read-only and represents the historical archive of all LLVM issues filled before November 26, 2021. Use github to submit LLVM bugs

Bug 51407 - Infinite loop in demangler
Summary: Infinite loop in demangler
Status: RESOLVED FIXED
Alias: None
Product: tools
Classification: Unclassified
Component: llvm-c++filt (show other bugs)
Version: trunk
Hardware: All All
: P normal
Assignee: Unassigned LLVM Bugs
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2021-08-08 02:35 PDT by Mikhail Borisov
Modified: 2021-08-17 15:18 PDT (History)
2 users (show)

See Also:
Fixed By Commit(s): f0fcd42495432670664a661e75e7cae7e904dd3e


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Mikhail Borisov 2021-08-08 02:35:36 PDT
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)
Comment 1 Mikhail Borisov 2021-08-08 03:58:30 PDT
Possible fix: https://reviews.llvm.org/D107712
Comment 2 Louis Dionne 2021-08-17 15:18:43 PDT
Fixed by:

commit f0fcd42495432670664a661e75e7cae7e904dd3e
Author: Mikhail Borisov <borisov.mikhail@gmail.com>
Date:   Tue Aug 17 18:10:57 2021 -0400

    [libc++abi] Fix possible infinite loop in itanium demangler


Thanks a lot!