The binarySearch exit condition is missing and may go into DOS or revert

[code423n4]

Lines of code

https://github.com/GenerationSoftware/pt-v5-prize-pool/blob/4bc8a12b857856828c018510b5500d722b79ca3a/src/libraries/DrawAccumulatorLib.sol#L454-L456

Vulnerability details

Impact

The binarySearch does not check for overlap between the left and right index of the sliding window, and loops indefinitely when satisfies item not exists in list until revert or gas is exhausted.

Proof of Concept

    while (true) {
      // We start our search in the middle of the `leftSide` and `rightSide`.
      // After each iteration, we narrow down the search to the left or the right side while still starting our search in the middle.
      currentIndex = (leftSide + rightSide) / 2;

      beforeOrAtIndex = uint16(RingBufferLib.wrap(currentIndex, _cardinality));
      beforeOrAtDrawId = _drawRingBuffer[beforeOrAtIndex];

      afterOrAtIndex = uint16(RingBufferLib.nextIndex(currentIndex, _cardinality));
      afterOrAtDrawId = _drawRingBuffer[afterOrAtIndex];

      bool targetAtOrAfter = beforeOrAtDrawId <= _targetLastClosedDrawId;

      // Check if we've found the corresponding Observation.
      if (targetAtOrAfter && _targetLastClosedDrawId <= afterOrAtDrawId) {
        break;
      }

      // If `beforeOrAtTimestamp` is greater than `_target`, then we keep searching lower. To the left of the current index.
      if (!targetAtOrAfter) {
        rightSide = currentIndex - 1;
      } else {
        // Otherwise, we keep searching higher. To the left of the current index.
        leftSide = currentIndex + 1;
      }
    }

According to the code only targetAtOrAfter &&_targetLastClosedDrawId <= afterOrAtDrawId can break loop, if no element in the list meets the condition, it loops indefinitely until the array index overflows or exhausts gas

Tools Used

Manual review

Recommended Mitigation Steps

Should check leftSide > rightSide to break the loop

Assessed type

Loop

[c4-sponsor]

asselstine marked the issue as sponsor confirmed

[Picodes]

There is a small chance of wasted gas due to this search never ending, but the report doesn't dig into the potential impact of this finding. Downgrading to Low.

[c4-judge]

Picodes changed the severity to QA (Quality Assurance)

[c4-judge]

Picodes marked the issue as grade-a