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

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

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)?


>> -----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