linux-kernel - Re: A divide by zero bug in lib/math/rational.c (with triggering input)

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]

Message-ID: <CA+7tXijWgDGzWPOYhzX+bWn0cjOZ9y1-gWRG+0uobQ128=8vCg@mail.gmail.com>
Date:   Sat, 22 May 2021 17:05:08 -0700
From:   Trent Piepho <tpiepho@...il.com>
To:     Andy Shevchenko <andy.shevchenko@...il.com>
Cc:     Daniel Latypov <dlatypov@...gle.com>,
        Yiyuan guo <yguoaz@...il.com>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "andy@...nel.org" <andy@...nel.org>,
        "akpm@...ux-foundation.org" <akpm@...ux-foundation.org>,
        "oskar@...ra.com" <oskar@...ra.com>
Subject: Re: A divide by zero bug in lib/math/rational.c (with triggering input)

On Fri, May 21, 2021 at 2:53 AM Andy Shevchenko
<andy.shevchenko@...il.com> wrote:
> >
> > I think the error can only occur when the loop exits on the 1st
> > iteration, when d1 is still zero.  In this case the prior convergent,
> > n1/d1 = 1/0, does not really exist as this is the 1st iteration.  The
> > actual series of convergents generated will never have zero terms,
> > because we stop at zero, so there will never be zero from the prior
> > iteration as we would have stopped there.
>
> This is my conclusion as well, but you beat me to it.
> And below is exactly my understanding of what's going on.

I came up with some more test cases, and there is another possibility,
if the value is small. e.g.

rational_best_approximation(1,30, 1,10, ...)
rational_best_approximation(1,19, 1,10, ...)

The former should be 0/1 and the latter 1/10.  These will divide by
zero on the 2nd iteration.

But I have a patch now that works.  It gets the closest answer in all
cases, larger than max, less than min but closer to the min than to
zero, and closest to zero.

It ends up being zero additional arithmetic to do this.   All that is
needed is a few additional branches in the termination condition.