Re: [Patch] MdePkg/BaseSafeIntLib: Add SafeIntLib class and instance

[Ard Biesheuvel <ard.biesheuvel@linaro.org>]

On 13 February 2018 at 17:51, Laszlo Ersek <lersek@redhat.com> wrote:
> On 02/13/18 18:18, Ard Biesheuvel wrote:
>> On 13 February 2018 at 16:17, Kinney, Michael D
>> <michael.d.kinney@intel.com> wrote:
>>> +Bret
>>>
>>> Mike
>>>
>>
>> Why has this patch been submitted if there are unanswered questions of
>> such a fundamental nature?
>> Could someone please revert it until there is agreement about its
>> inclusion (and in which form)?
>
> I think your question is "why has this patch been *committed* / pushed
> if such questions remain"; is that correct?
>

Ah yes, apologies.

> The patch was correctly submitted to edk2-devel for review back in
> December 2017. At that time I quickly glanced at the diffstat, and I
> didn't even start reviewing the patch -- "15 files changed, 8915
> insertions(+), 9 deletions(-)". For me to review such a large amount of
> code in detail, it would have to be split into tens of patches, and I'd
> likely have to work on the review intensely for a week or more. So, I
> asumed that SafeIntLib had been carefully reviewed for strict standards
> compliance.
>
> My interest in SafeIntLib was renewed recently, upon seeing:
>
> [edk2] [Patch 05/10] OvmfPkg: Add SafeIntLib and BmpSupportLib to DSC
>                      files
> [edk2] [Patch 10/10] ArmVirtPkg: Add SafeIntLib and BmpSupportLib to DSC
>                      files
>
> With those patches committed (which is the current status), OvmfPkg and
> ArmVirtPkg produce and include EFI binaries that contain SafeIntLib
> code, according to the build report files -- namely
> BootGraphicsResourceTableDxe. (As Mike explained in the thread,
> BootGraphicsResourceTableDxe uses BmpSupportLib, and BaseBmpSupportLib
> uses SafeIntLib as part of the pixel format conversion, and/or as part
> of the BMP<->GOP BLT format conversion -- if I understood correctly.)
>
> Due to SafeIntLib being indirectly pulled into the OVMF and ArmVirt
> firmware binaries (and due to expecting more wide-spread use of
> SafeIntLib in the future -- which is a good thing!), I figured I'd take
> one look. Because developers frequently miss that signed integer
> overflow is actually undefined behavior, I checked SafeInt64Sub().
> Indeed it is affected.
>
> I don't necessarily think we should revert the patch, but it certainly
> needs a re-evaluation (I proposed a fix for SafeInt64Sub() up-thread).
>
> *Alternatively* -- and we should be fully aware of this as well! --, we
> *can* define C language behavior, for edk2, *on top* of ISO C. For
> example, we can say, "given the compiler options that we use with edk2,
> signed integer overflow is actually well-defined: it behaves as you
> would expect from the two's complement representation".
>
> This is a perfectly valid thing to say, and we are already saying things
> like it: for example, ISO C also leaves violations of the effective type
> / strict aliasing rules "undefined behavior", but we don't care (edk2 is
> chock-full of type punning!): we pass "-fno-strict-aliasing" to all GCC
> and CLANG toolchains that we support.
>
>
> So, my point is, we should be aware of what ISO C says about integer
> overflow, and then pick one:
>
> - we target strict ISO C compliance (wrt. integer arithmetic) with
> SafeIntLib -- in which case a re-evaluation and patches are necessary,
>
> - or else we define additional C language guarantees, and then we
> *ensure* those via compiler flags, universally.
>
> Thanks,
> Laszlo
>
>
>>
>>
>>>> -----Original Message-----
>>>> From: edk2-devel [mailto:edk2-devel-bounces@lists.01.org]
>>>> On Behalf Of Laszlo Ersek
>>>> Sent: Tuesday, February 13, 2018 4:24 AM
>>>> To: Kinney, Michael D <michael.d.kinney@intel.com>; Sean
>>>> Brogan <sean.brogan@microsoft.com>
>>>> Cc: edk2-devel@lists.01.org; Gao, Liming
>>>> <liming.gao@intel.com>
>>>> Subject: Re: [edk2] [Patch] MdePkg/BaseSafeIntLib: Add
>>>> SafeIntLib class and instance
>>>>
>>>> Sean, Michael,
>>>>
>>>> can you please follow up on this?
>>>>
>>>> To clarify, I think this is a serious bug in SafeIntLib,
>>>> dependent on
>>>> what we want to use this library for. As far as I
>>>> understand, SafeIntLib
>>>> intends to centralize integer manipulation / arithmetic,
>>>> so that client
>>>> code need not concern itself with overflow checking and
>>>> such (on the C
>>>> expression level -- it still has to check return
>>>> statuses, of course).
>>>> In other words, undefined behavior related to integer
>>>> arithmetic is
>>>> supposed to be prevented in various modules by moving all
>>>> such
>>>> operations into SafeIntLib, and letting client code use
>>>> SafeIntLib APIs.
>>>>
>>>> However, for this to work, SafeIntLib itself must be 100%
>>>> free of
>>>> undefined behavior. And that's not the case (unless we
>>>> define additional
>>>> guarantees -- on top of ISO C -- for edk2 target
>>>> architectures). Should
>>>> I file a TianoCore BZ? Or is someone already (re)auditing
>>>> the library?
>>>> Or else, is my concern unjustified? Please comment.
>>>>
>>>> Thanks,
>>>> Laszlo
>>>>
>>>> On 02/08/18 01:45, Laszlo Ersek wrote:
>>>>> On 02/08/18 01:32, Laszlo Ersek wrote:
>>>>>> On 12/19/17 20:36, Kinney, Michael D wrote:
>>>>>>> From: Sean Brogan <sean.brogan@microsoft.com>
>>>>>>>
>>>>>>> SafeIntLib provides helper functions to prevent
>>>> integer overflow
>>>>>>> during type conversion, addition, subtraction, and
>>>> multiplication.
>>>>>>
>>>>>> I clearly cannot review such a huge patch, but I've
>>>> noticed something
>>>>>> and would like to ask for clarification:
>>>>>>
>>>>>>> +/**
>>>>>>> +  INT64 Subtraction
>>>>>>> +
>>>>>>> +  Performs the requested operation using the input
>>>> parameters into a value
>>>>>>> +  specified by Result type and stores the converted
>>>> value into the caller
>>>>>>> +  allocated output buffer specified by Result.  The
>>>> caller must pass in a
>>>>>>> +  Result buffer that is at least as large as the
>>>> Result type.
>>>>>>> +
>>>>>>> +  If Result is NULL, RETURN_INVALID_PARAMETER is
>>>> returned.
>>>>>>> +
>>>>>>> +  If the requested operation results in an overflow
>>>> or an underflow condition,
>>>>>>> +  then Result is set to INT64_ERROR and
>>>> RETURN_BUFFER_TOO_SMALL is returned.
>>>>>>> +
>>>>>>> +  @param[in]   Minuend     A number from which
>>>> another is to be subtracted.
>>>>>>> +  @param[in]   Subtrahend  A number to be subtracted
>>>> from another
>>>>>>> +  @param[out]  Result      Pointer to the result of
>>>> subtraction
>>>>>>> +
>>>>>>> +  @retval  RETURN_SUCCESS            Successful
>>>> subtraction
>>>>>>> +  @retval  RETURN_BUFFER_TOO_SMALL   Underflow
>>>>>>> +  @retval  RETURN_INVALID_PARAMETER  Result is NULL
>>>>>>> +**/
>>>>>>> +RETURN_STATUS
>>>>>>> +EFIAPI
>>>>>>> +SafeInt64Sub (
>>>>>>> +  IN  INT64  Minuend,
>>>>>>> +  IN  INT64  Subtrahend,
>>>>>>> +  OUT INT64  *Result
>>>>>>> +  )
>>>>>>> +{
>>>>>>> +  RETURN_STATUS  Status;
>>>>>>> +  INT64          SignedResult;
>>>>>>> +
>>>>>>> +  if (Result == NULL) {
>>>>>>> +    return RETURN_INVALID_PARAMETER;
>>>>>>> +  }
>>>>>>> +
>>>>>>> +  SignedResult = Minuend - Subtrahend;
>>>>>>> +
>>>>>>> +  //
>>>>>>> +  // Subtracting a positive number from a positive
>>>> number never overflows.
>>>>>>> +  // Subtracting a negative number from a negative
>>>> number never overflows.
>>>>>>> +  // If you subtract a negative number from a
>>>> positive number, you expect a positive result.
>>>>>>> +  // If you subtract a positive number from a
>>>> negative number, you expect a negative result.
>>>>>>> +  // Overflow if inputs vary in sign and the output
>>>> does not have the same sign as the first input.
>>>>>>> +  //
>>>>>>> +  if (((Minuend < 0) != (Subtrahend < 0)) &&
>>>>>>> +      ((Minuend < 0) != (SignedResult < 0))) {
>>>>>>> +    *Result = INT64_ERROR;
>>>>>>> +    Status = RETURN_BUFFER_TOO_SMALL;
>>>>>>> +  } else {
>>>>>>> +    *Result = SignedResult;
>>>>>>> +    Status = RETURN_SUCCESS;
>>>>>>> +  }
>>>>>>> +
>>>>>>> +  return Status;
>>>>>>> +}
>>>>>>
>>>>>> Is our goal to
>>>>>>
>>>>>> (a) catch overflows before the caller goes wrong due
>>>> to them, or
>>>>>> (b) completely prevent undefined behavior from
>>>> happening, even inside
>>>>>> SafeInt64Sub()?
>>>>>>
>>>>>> The above implementation may be good for (a), but it's
>>>> not correct for
>>>>>> (b). The
>>>>>>
>>>>>>   SignedResult = Minuend - Subtrahend;
>>>>>>
>>>>>> subtraction invokes undefined behavior if the result
>>>> cannot be
>>>>>> represented [*]; the rest of the code cannot help.
>>>>>>
>>>>>> Now if we say that such subtractions always occur
>>>> according to the
>>>>>> "usual two's complement definition", on all
>>>> architectures that edk2
>>>>>> targets, and we're sure that no compiler or analysis
>>>> tool will flag --
>>>>>> or exploit -- the UB either, then the code is fine;
>>>> meaning our choice
>>>>>> is (a).
>>>>>>
>>>>>> But, if (b) is our goal, I would replace the current
>>>> error condition with:
>>>>>>
>>>>>>   (((Subtrahend > 0) && (Minuend < MIN_INT64 +
>>>> Subtrahend)) ||
>>>>>>    ((Subtrahend < 0) && (Minuend > MAX_INT64 +
>>>> Subtrahend)))
>>>>>
>>>>> To clarify, I wouldn't just replace the error
>>>> condition. In addition to
>>>>> that, I would remove the SignedResult helper variable
>>>> (together with the
>>>>> current subtraction), and calculate & assign
>>>>>
>>>>>   *Result = Minuend - Subtrahend;
>>>>>
>>>>> only after the error condition fails (i.e. the
>>>> subtraction is safe).
>>>>>
>>>>> Thanks,
>>>>> Laszlo
>>>>>
>>>>>
>>>>>> Justification:
>>>>>>
>>>>>> * Subtrahend==0 can never cause overflow
>>>>>>
>>>>>> * Subtrahend>0 can only cause overflow at the negative
>>>> end, so check
>>>>>>   that: (Minuend - Subtrahend < MIN_INT64),
>>>> mathematically speaking.
>>>>>>   In order to write that down in C, add Subtrahend (a
>>>> positive value)
>>>>>>   to both sides, yielding (Minuend < MIN_INT64 +
>>>> Subtrahend). Here,
>>>>>>   (MIN_INT64 + Subtrahend) will never go out of range,
>>>> because
>>>>>>   Subtrahend is positive, and (MIN_INT64 + MAX_INT64)
>>>> is representable.
>>>>>>
>>>>>> * Subtrahend<0 can only cause overflow at the positive
>>>> end, so check
>>>>>>   that: (Minuend - Subtrahend > MAX_INT64),
>>>> mathematically speaking.
>>>>>>   In order to write that down in C, add Subtrahend (a
>>>> negative value)
>>>>>>   to both sides, yielding (Minuend > MAX_INT64 +
>>>> Subtrahend). Here,
>>>>>>   (MAX_INT64 + Subtrahend) will never go out of range,
>>>> because
>>>>>>   Subtrahend is negative, and (MAX_INT64 + MIN_INT64)
>>>> is representable.
>>>>>>
>>>>>> (
>>>>>>
>>>>>> [*] ISO C99 section 6.5 Expressions, p5: "If an
>>>> exceptional condition
>>>>>> occurs during the evaluation of an expression (that
>>>> is, if the result is
>>>>>> not mathematically defined or not in the range of
>>>> representable values
>>>>>> for its type), the behavior is undefined."
>>>>>>
>>>>>> Section 6.2.5 Types, p9 only exempts unsigned
>>>> integers, "A computation
>>>>>> involving unsigned operands can never overflow,
>>>> because a result that
>>>>>> cannot be represented by the resulting unsigned
>>>> integer type is reduced
>>>>>> modulo the number that is one greater than the largest
>>>> value that can be
>>>>>> represented by the resulting type."
>>>>>>
>>>>>> Note that this is different from conversion, where the
>>>> computation first
>>>>>> succeeds (= we have a value), and then the value is
>>>> converted to a type
>>>>>> that causes truncation: section 6.3.1.3 Signed and
>>>> unsigned integers,
>>>>>> p3: "Otherwise, the new type is signed and the value
>>>> cannot be
>>>>>> represented in it; either the result is
>>>> implementation-defined or an
>>>>>> implementation-defined signal is raised."
>>>>>>
>>>>>> In the code above, the expression (Minuend -
>>>> Subtrahend) can invoke
>>>>>> undefined behavior, there is no conversion (not even
>>>> as part of the
>>>>>> assignment to SignedResult).
>>>>>>
>>>>>> )
>>>>>>
>>>>>> Thanks,
>>>>>> Laszlo
>>>>>> _______________________________________________
>>>>>> edk2-devel mailing list
>>>>>> edk2-devel@lists.01.org
>>>>>> https://lists.01.org/mailman/listinfo/edk2-devel
>>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> edk2-devel mailing list
>>>>> edk2-devel@lists.01.org
>>>>> https://lists.01.org/mailman/listinfo/edk2-devel
>>>>>
>>>>
>>>> _______________________________________________
>>>> edk2-devel mailing list
>>>> edk2-devel@lists.01.org
>>>> https://lists.01.org/mailman/listinfo/edk2-devel
>>> _______________________________________________
>>> edk2-devel mailing list
>>> edk2-devel@lists.01.org
>>> https://lists.01.org/mailman/listinfo/edk2-devel
>