From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=66.187.233.73; helo=mx1.redhat.com; envelope-from=lersek@redhat.com; receiver=edk2-devel@lists.01.org Received: from mx1.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id 8ACF521CF1CE8 for ; Tue, 13 Feb 2018 09:46:09 -0800 (PST) Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.rdu2.redhat.com [10.11.54.3]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 8FB388182D01; Tue, 13 Feb 2018 17:51:59 +0000 (UTC) Received: from lacos-laptop-7.usersys.redhat.com (ovpn-120-17.rdu2.redhat.com [10.10.120.17]) by smtp.corp.redhat.com (Postfix) with ESMTP id 4B2F110073A3; Tue, 13 Feb 2018 17:51:58 +0000 (UTC) To: Ard Biesheuvel , "Kinney, Michael D" Cc: Sean Brogan , Bret Barkelew , "edk2-devel@lists.01.org" , "Gao, Liming" References: <20171219193625.16060-1-michael.d.kinney@intel.com> <656eb64b-3265-f021-ff4f-df2ed6b7c752@redhat.com> <868954f3-f368-073c-9e62-d11440e719c9@redhat.com> From: Laszlo Ersek Message-ID: Date: Tue, 13 Feb 2018 18:51:57 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 2.78 on 10.11.54.3 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.11.55.8]); Tue, 13 Feb 2018 17:51:59 +0000 (UTC) X-Greylist: inspected by milter-greylist-4.5.16 (mx1.redhat.com [10.11.55.8]); Tue, 13 Feb 2018 17:51:59 +0000 (UTC) for IP:'10.11.54.3' DOMAIN:'int-mx03.intmail.prod.int.rdu2.redhat.com' HELO:'smtp.corp.redhat.com' FROM:'lersek@redhat.com' RCPT:'' 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:46:10 -0000 Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit On 02/13/18 18:18, Ard Biesheuvel wrote: > 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)? I think your question is "why has this patch been *committed* / pushed if such questions remain"; is that correct? 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 ; 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