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::232; helo=mail-it0-x232.google.com; envelope-from=ard.biesheuvel@linaro.org; receiver=edk2-devel@lists.01.org Received: from mail-it0-x232.google.com (mail-it0-x232.google.com [IPv6:2607:f8b0:4001:c0b::232]) (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 8E21F21CF1D13 for ; Tue, 13 Feb 2018 09:49:18 -0800 (PST) Received: by mail-it0-x232.google.com with SMTP id y16so936547itc.0 for ; Tue, 13 Feb 2018 09:55:09 -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=A10NNfdbdHVpwKMzAPx0H2wVHLExXJziPjzpPz4sXys=; b=UKvuz5pgiBhwIo/cslSStEu6+P2eeMMoIvcufpa36mtwfKZFzFpPf8syuAkqqO9No6 +oPByWOggDsBCETPTpH46w28wR2tT7zIczM4/REJRnHONV0f4iuXPFmIbA1MnSePEx2b G9vEMmlHmp1cIwpazz2zA1tYss6IFNRicFtI4= 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=A10NNfdbdHVpwKMzAPx0H2wVHLExXJziPjzpPz4sXys=; b=VQHWODIqIoBqQ4XUAiOl6+IRBYiY5WYcjuICuKeVNR9ZEpci+L87KCtUfTF2igKn4c 5YFQMBNRHCMR7ZqwF5SfjRna5cIqWEet7DJJlDgL8njpOvVgsKr7kwbLlmuFCyQD4w54 yX+bxn5iCF/OPlauaLP3iyHdUupJg6KYDL8dTF7n/iitZHr3j8O3hjvQc987ZZ/l/GN9 5UTXz5/64U9H5ps5VaDOX+1XF9sjAVvfZdj+x4C0C4FXniFoYO4jRZGhm4vnlvk7cOYC a2VACiGSg55avXdJjkBmPADTGqhkEf3OdIZnGkGkZDnjshXn4xx63kPQaHfyRhhqoZOl LGyw== X-Gm-Message-State: APf1xPDJUuoS95O8sOu3TSHi+Li26h6GgEtVWkNW+jHLi83ucwKaSZzg myhs46FjJCCT4qz78sKOO2v+f3izcKCJMgWmDQM8aQ== X-Google-Smtp-Source: AH8x225IvdSnetLbS2+Wzl8Xyeo/vgQcn2ZFhX4nxxGOgwo3oTSHHjt0vgVNgb7aN2gnZ2opbodTkdSRKe9aaM9noVI= X-Received: by 10.36.53.146 with SMTP id k140mr2460997ita.17.1518544508280; Tue, 13 Feb 2018 09:55:08 -0800 (PST) MIME-Version: 1.0 Received: by 10.107.112.13 with HTTP; Tue, 13 Feb 2018 09:55:07 -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:55:07 +0000 Message-ID: To: Laszlo Ersek Cc: "Kinney, Michael D" , 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:49:19 -0000 Content-Type: text/plain; charset="UTF-8" On 13 February 2018 at 17:51, Laszlo Ersek wrote: > 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? > Ah yes, apologies. > 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 >