From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/521 Path: news.gmane.org!not-for-mail From: Pascal Cuoq Newsgroups: gmane.linux.lib.musl.general Subject: Re: Undefined behavior in atoi() Date: Sun, 6 Nov 2011 23:28:41 +0100 Message-ID: References: <20111106212145.GO132@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=f46d0444e945d6f24504b1187528 X-Trace: dough.gmane.org 1320618538 14617 80.91.229.12 (6 Nov 2011 22:28:58 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 6 Nov 2011 22:28:58 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-522-gllmg-musl=m.gmane.org@lists.openwall.com Sun Nov 06 23:28:54 2011 Return-path: Envelope-to: gllmg-musl@lo.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by lo.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1RNBCw-0004Km-Hq for gllmg-musl@lo.gmane.org; Sun, 06 Nov 2011 23:28:54 +0100 Original-Received: (qmail 3790 invoked by uid 550); 6 Nov 2011 22:28:54 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 3782 invoked from network); 6 Nov 2011 22:28:53 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=zFfyN0wfHXoRutm8i47NPVL2PS+Fzq3LvWQQ1QvB5rM=; b=F5D8fT7vPO8yrdeAb5ML5yvgzgniOFE/HRej41WKcEf20Yj7VUjm5rlN+AGJB51Mv0 QFsiU+K6MADN5vF94PDSJAG6/5ak5yK1+lKkPF2IPp6YQSiYyQbbdLxwHgk5jLq6Z3Ir Lj3dg+OeTKDMIsm/N6hfTwS9GwpzPoURnDw2c= In-Reply-To: <20111106212145.GO132@brightrain.aerifal.cx> Xref: news.gmane.org gmane.linux.lib.musl.general:521 Archived-At: --f46d0444e945d6f24504b1187528 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Sun, Nov 6, 2011 at 10:21 PM, Rich Felker wrote: > > Thanks. How did you manage to find this bug? Just browsing source? > I was looking at implementations for strtod() (long story for another time) and I noticed that this library was the most pleasant C code I had seen in months (seriously), so I lingered a bit. So, the straightforward answer is "yes, code review". The slightly longer answer is that I have done the formal verification of "string to number" C functions in the past, found that they were correct, noticed the opposite trick, and somehow the relationship between the two clicked. So I was looking for a classic pitfall here. Since my previous e-mail, I have been analyzing a few more cases for fun, and musl's original code also has this issue for the 40 or so values below LONG_MAX. The problem is then: src/stdlib/atol.orig.c:14:[kernel] warning: Signed overflow. assert (long)((long)10*n)+(long)*tmp_0 =E2=89=A4 9223372036854775807LL; That is, you should in any case subtract '0' from the digit before adding it in at line 14. In the case of atoll() on IA32, it will even be more efficient. Pascal --f46d0444e945d6f24504b1187528 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Sun, Nov 6, 2011 at 10:21 PM, Rich Felker <dalias@aerifal.cx> wrote:

Thanks. How did you manage to find this bug? Just browsing source?

I was looking at implementations for strt= od() (long story for another time)
and I noticed that this librar= y was the most pleasant C code I had
seen in months (seriously), so I lingered a bit. So, the straightforwa= rd
answer is "yes, code review".

The slightly longer answer is that I have done the formal verification o= f
"string to number" C functions in the past, found that they = were correct,
noticed the opposite trick, and somehow the relatio= nship
between the two clicked.=C2=A0So I was looking for a classi= c pitfall here.

Since my previous e-mail, I have been analyzing a few m= ore cases for fun,
and musl's original code also has this iss= ue for the 40 or so values
below LONG_MAX.

The problem is then:

src/stdlib/atol.ori= g.c:14:[kernel] warning: Signed overflow.
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 assert (long)((long)10*n)+(long)*= tmp_0 =E2=89=A4 9223372036854775807LL;

That is, you should in any case subtract '0' from th= e digit before adding it in
at line 14.=C2=A0In the case of atoll= () on IA32, it will even be more efficient.

Pascal=


--f46d0444e945d6f24504b1187528--