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

["Kinney, Michael D" <michael.d.kinney@intel.com>]

+Bret

Mike

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