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

[Laszlo Ersek <lersek@redhat.com>]

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
>