From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=2607:f8b0:4001:c0b::229; helo=mail-it0-x229.google.com; envelope-from=ard.biesheuvel@linaro.org; receiver=edk2-devel@lists.01.org Received: from mail-it0-x229.google.com (mail-it0-x229.google.com [IPv6:2607:f8b0:4001:c0b::229]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id 8CC1321F0DA6B for ; Tue, 13 Feb 2018 09:12:45 -0800 (PST) Received: by mail-it0-x229.google.com with SMTP id e1so11684134ita.0 for ; Tue, 13 Feb 2018 09:18:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=J1j6Az3f6CZglfPKbzbDAofIh9wFMD0NaYZFwJHuOPs=; b=VbO6sjBSk9AsW3JUxIUvvPo9DD3OctVB20yKlCcvbNRiBPPQFMIPuGtRpM6IZ2N5Sa RWfs5r/Q33G42ghZF8oyeFgOdZyqf4wQ2HFayTZNmIydovmybsviOtg23jQmKIAPq+FM lZzP2E0tBtVMkcVQFejCD2jA+woN7OOJ0ydJ0= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=J1j6Az3f6CZglfPKbzbDAofIh9wFMD0NaYZFwJHuOPs=; b=b/vz9Su6HfCXNm7QEVEL6jfeRIEW9cQMUy6gd6IqR+hMlYT9EfBv96ywWFQYgLJl0V h4cq4PFfihslyK9Efiw2u1QrJy382b7/wE/pTF84oETElfgPNGOyat7K+ctxcEWIgl6L h6hQnqeHURzFshJQarQP+UweRSLrAGsNl2sWamZREqKwiIdoG2MqPyif58tlNlxjpjYv VRRLaoEnMHr/va5JAw8ni0KbM2PsBQYMTMm1DKx56u+dbnEctDZdlvX7JqvWAU1HTmls FzgWVLLzcZ2/sXDyqciIlAvbo2gqho4cHLL5oPx9KbjIGIOe6dAWnix4osoFkommigA2 CBcA== X-Gm-Message-State: APf1xPAgzfTdsT9i+fkjmIOQysN7b2RBwJXjF3qP6BfKFWB7h4fSMx3n ssDf2PqXY+BmI06lzCcoLlPbg3g3Q408mGtlAhs57g== X-Google-Smtp-Source: AH8x226Siin6K1VvH4KxMO033I5FuMWSFDvpjbISf/wuxL0nv7lrvG5y6860JdAslNCbWl085iPNrLmIKhnxXbqS7Jo= X-Received: by 10.36.216.65 with SMTP id b62mr2437123itg.17.1518542315085; Tue, 13 Feb 2018 09:18:35 -0800 (PST) MIME-Version: 1.0 Received: by 10.107.112.13 with HTTP; Tue, 13 Feb 2018 09:18:34 -0800 (PST) In-Reply-To: References: <20171219193625.16060-1-michael.d.kinney@intel.com> <656eb64b-3265-f021-ff4f-df2ed6b7c752@redhat.com> <868954f3-f368-073c-9e62-d11440e719c9@redhat.com> From: Ard Biesheuvel Date: Tue, 13 Feb 2018 17:18:34 +0000 Message-ID: To: "Kinney, Michael D" Cc: Laszlo Ersek , Sean Brogan , Bret Barkelew , "edk2-devel@lists.01.org" , "Gao, Liming" Subject: Re: [Patch] MdePkg/BaseSafeIntLib: Add SafeIntLib class and instance X-BeenThere: edk2-devel@lists.01.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: EDK II Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 13 Feb 2018 17:12:46 -0000 Content-Type: text/plain; charset="UTF-8" On 13 February 2018 at 16:17, Kinney, Michael D 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 ; Sean >> Brogan >> Cc: edk2-devel@lists.01.org; Gao, Liming >> >> 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 >> >>> >> >>> 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