linux-kernel - Re: [PATCH] lib/math/rational.c: Fix divide by zero

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 24 May 2021 13:51:41 +0300
From:   Andy Shevchenko <andriy.shevchenko@...el.com>
To:     Trent Piepho <tpiepho@...il.com>,
        Daniel Latypov <dlatypov@...gle.com>
Cc:     linux-kernel@...r.kernel.org, andy@...nel.org,
        akpm@...ux-foundation.org, oskar@...ra.com,
        Yiyuan Guo <yguoaz@...il.com>
Subject: Re: [PATCH] lib/math/rational.c: Fix divide by zero

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

Thanks for the fix! My comments below.

> If the input is out of the range of the allowed values, either larger
> than the largest value or closer to zero than the smallest non-zero
> allowed value, then a division by zero would occur.
> 
> In the case of input too large, the division by zero will occur on the
> first iteration.  The best result (largest allowed value) will be found
> by always choosing the semi-convergent and excluding the denominator
> based limit when finding it.
> 
> In the case of the input too small, the division by zero will occur on
> the second iteration.  The numerator based semi-convergent should not be
> calculated to avoid the division by zero.  But the semi-convergent vs
> previous convergent test is still needed, which effectively chooses
> between 0 (the previous convergent) vs the smallest allowed fraction
> (best semi-convergent) as the result.

This misses the test cases (*). Please, develop them with Daniel.

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

> Reported-by: Yiyuan Guo <yguoaz@...il.com>
> Signed-off-by: Trent Piepho <tpiepho@...il.com>

...

> +			/* This tests if the semi-convergent is closer than the previous
> +			 * convergent.  If d1 is zero there is no previous convergent as this
> +			 * is the 1st iteration, so always choose the semi-convergent.
>  			 */
> -			if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
> +			if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
>  				n1 = n0 + t * n1;
>  				d1 = d0 + t * d1;
>  			}

I think that refactoring may lead us to check first iteration before even going
into the loop. But it's another story and we may do it later (the algo uses
heavy division anyway, so couple of additional branches probably won't affect
performance too much).

-- 
With Best Regards,
Andy Shevchenko