1069859 - overflow-prone binary search algorithms in 3rd-party code

Status: RESOLVED FIXED

(Core :: Security, defect)

Description

[Georg Fritzsche [:gfritzsche]]

Attachment: 3rd-party.txt

This is the 3rd-party part of the potential vulnerabilities in bug 917918.

I attached the list of suspects in external code. We should get in contact with the affected libraries developers.

Comment 1

[Georg Fritzsche [:gfritzsche]]

Is the outreach WIP? Does this bug block landing the "obvious fixups" in bug 917918?

Comment 2

[Georg Fritzsche [:gfritzsche]]

(In reply to Georg Fritzsche [:gfritzsche] from comment #1)
>Does this bug block landing the "obvious fixups" in bug 917918?

... that is, landing them in late 35 beta.

Comment 3

[Georg Fritzsche [:gfritzsche]]

dveditz, abillings, anything happening for this?

Comment 4

[Al Billings [:abillings - ex-MoCo]]

This is the first that I've ever seen this bug. So, nothing has been happening. Are you expecting me or Dan to figure out who to contact and to contact them?

Comment 5

[Georg Fritzsche [:gfritzsche]]

(In reply to Al Billings [:abillings] from comment #4)
> This is the first that I've ever seen this bug. So, nothing has been
> happening. Are you expecting me or Dan to figure out who to contact and to
> contact them?

Per an earlier mail threead with dveditz, the security team can do the outreach, so i filed this bug for it.
If not, we need to figure out something else. Note that i'm on PTO until Portland.

Comment 6

[Daniel Veditz [:dveditz]]

This does not block landing fixes for bug 917918

Comment 7

[Frederik Braun [:freddy]]

So, this is the matcher that would find overflows like the one shared in comment 0, https://godbolt.org/z/cVJD6K, i.e.:

set bind-root false

let assignmentRight expr(
  binaryOperator(
    allOf(
      hasOperatorName("/"),
      hasRHS(
        integerLiteral(equals(2))),
      hasLHS(
        binaryOperator(
          allOf(
               hasOperatorName("+"),  
               unless(
                 anyOf(
                 hasLHS(anyOf(integerLiteral(), characterLiteral(), floatLiteral())),
                 hasRHS(anyOf(integerLiteral(), characterLiteral(), floatLiteral()))
                 )
               )
          )
        ).bind("addition"))
    )
  )
).bind("midcalculation")

m assignmentRight

which is matching code like int mid = (low + high) / 2; and binds the addition enclosed in the parentheses to a node called "addition" and the whole expression on the right-hand side of the assignment to "midcalculation".

This has a couple of minor issues, that I'd like to sort out:

• this doesn't match the whole line (i.e., the assignment) and I can't seem to find a assignmentExpression kind of matcher.
• this doesn't match the types of variables in the addition (e.g., low and high) and I'm not sure whether I want to make this exclusively for integers or also include other sized types (e.g., uint32_t)
• this explicitly excludes literals by naming them all in an unless()-statement (integerLiteral, characterLiteral etc.). They all directly inherit from expr() and AFAIU there's no way to say "any literal".

As a next step, I will sort out how big of these issues listed above are by looking at violations and false positives in our source code.

Looking forward to any guiding comment that folks reading along might have.

Comment 8

[Joshua Cranmer [:jcranmer]]

I wrote the LLVM matcher several years ago (code is at https://bug917918.bmoattachments.org/attachment.cgi?id=8486207). In my matcher, I included both (low + high) / 2 and (low + high) >> 1. As I reported in bug 917918 comment 42, the quick-and-dirty matcher only found one false-positive. Considering that the check to make sure it was actually a search only required that the low and high were loop-varying phis, that's pretty precise.

It's been several years, but my recollection is that the >> 1 check did catch a few binary searches.

Comment 9

[Frederik Braun [:freddy]]

Thanks, Joshua. That's super valuable input. My understanding is that I'll get to a better end-result doing the following:

1. Build a clang-plugin rule that uses the matcher from comment 8
2. adding the right-shift case
3. in the check function, make sure that low & high are loop-variables (using code from bug 917918 comment 42)

I see how your code is doing step 3, but I don't really understand the underlying logic, just from looking at the patch and the class description at http://llvm.org/doxygen/classllvm_1_1PHINode.html - is there something else you could provide as reading material or maybe explain here in the bug?

I'll also follow up with a WIP patch so we can iterate on working code

Comment 10

[Frederik Braun [:freddy]]

This was implemented in the civet repo.