From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 15 04:12:10 2014 Received: (at submit) by debbugs.gnu.org; 15 Nov 2014 09:12:10 +0000 Received: from localhost ([127.0.0.1]:33210 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpZOr-0000y5-JT for submit@debbugs.gnu.org; Sat, 15 Nov 2014 04:12:10 -0500 Received: from eggs.gnu.org ([208.118.235.92]:47040) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpZOp-0000xr-Gr for submit@debbugs.gnu.org; Sat, 15 Nov 2014 04:12:08 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XpZOg-0006WR-Jy for submit@debbugs.gnu.org; Sat, 15 Nov 2014 04:12:07 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:42772) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XpZOg-0006WN-HM for submit@debbugs.gnu.org; Sat, 15 Nov 2014 04:11:58 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:48722) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XpZOY-0005eA-JN for bug-grep@gnu.org; Sat, 15 Nov 2014 04:11:58 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XpZOM-0006Uv-7c for bug-grep@gnu.org; Sat, 15 Nov 2014 04:11:50 -0500 Received: from mailgw05.kcn.ne.jp ([61.86.7.212]:51974) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XpZOL-0006UW-Oi for bug-grep@gnu.org; Sat, 15 Nov 2014 04:11:38 -0500 Received: from imp01 (mailgw5.kcn.ne.jp [61.86.15.231]) by mailgw05.kcn.ne.jp (Postfix) with ESMTP id 8A1D867DE4 for ; Sat, 15 Nov 2014 18:11:33 +0900 (JST) Received: from mail08.kcn.ne.jp ([61.86.6.187]) by imp01 with bizsmtp id FlBZ1p00F426eXR01lBZUQ; Sat, 15 Nov 2014 18:11:33 +0900 X-OrgRCPT: bug-grep@gnu.org Received: from [10.120.1.58] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail08.kcn.ne.jp (Postfix) with ESMTPA id 5CB9C12B8099 for ; Sat, 15 Nov 2014 18:11:33 +0900 (JST) Date: Sat, 15 Nov 2014 18:11:32 +0900 From: Norihiro Tanaka To: bug-grep@gnu.org Subject: [PATCH] dfa: building superset, access to unallocated memory Message-Id: <20141115181123.71E4.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5467187D0000000071DF_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-detected-operating-system: by eggs.gnu.org: Mac OS X 10.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) --------_5467187D0000000071DF_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit If original DFA does not have any CSETs, no memory allocated for CSET. Even then DFA try to copy CSET from original DFA to the superset. As a result, it is caused to access to unallocated memory. We have no test case so that it is very difficult that we always reproduce this bug, as CSET may be added only one in building superset. --------_5467187D0000000071DF_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-dfa-building-superset-access-to-unallocated-memory.patch" Content-Disposition: attachment; filename="0001-dfa-building-superset-access-to-unallocated-memory.patch" Content-Transfer-Encoding: base64 RnJvbSA2Yjk5YTRhYmQ2Zjk2OWVmMTc3MTBiMGYzZWExNmU0YjBlNGVmMjczIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDE1IE5vdiAyMDE0IDE3OjEzOjEwICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZGZh OiBidWlsZGluZyBzdXBlcnNldCwgYWNjZXNzIHRvIHVuYWxsb2NhdGVkIG1lbW9yeQoKSWYgb3Jp Z2luYWwgREZBIGRvZXMgbm90IGhhdmUgYW55IENTRVRzLCBubyBtZW1vcnkgYWxsb2NhdGVkIGZv ciBDU0VULgpFdmVuIHRoZW4gREZBIHRyeSB0byBjb3B5IENTRVQgZnJvbSBvcmlnaW5hbCBERkEg dG8gdGhlIHN1cGVyc2V0LiAgQXMKYSByZXN1bHQsIGl0IGlzIGNhdXNlZCB0byBhY2Nlc3MgdG8g dW5hbGxvY2F0ZWQgbWVtb3J5LiAgV2UgaGF2ZSBubyB0ZXN0CmNhc2Ugc28gdGhhdCBpdCBpcyB2 ZXJ5IGRpZmZpY3VsdCB0aGF0IHdlIGFsd2F5cyByZXByb2R1Y2UgdGhpcyBidWcsIGFzCkNTRVQg bWF5IGJlIGFkZGVkIG9ubHkgb25lIGluIGJ1aWxkaW5nIHN1cGVyc2V0LgoKKiBzcmMvZGZhLmMg KGRmYXNzYnVpbGQpOiBDaGFuZ2Ugc28gdGhhdCB3aGVuIG9yaWduYWwgREZBIGRvZXMgbm90IGhh dmUKYW55IENTRVRzLCBkbyBub3QgY29weSBpdC4KKiBORVdTIChCdWcgZml4ZXMpOiBNZW50aW9u IGl0LgotLS0KIE5FV1MgICAgICB8IDQgKysrKwogc3JjL2RmYS5jIHwgOSArKysrKystLS0KIDIg ZmlsZXMgY2hhbmdlZCwgMTAgaW5zZXJ0aW9ucygrKSwgMyBkZWxldGlvbnMoLSkKCmRpZmYgLS1n aXQgYS9ORVdTIGIvTkVXUwppbmRleCBjNDY1MTYyLi5mZmUwZjQ0IDEwMDY0NAotLS0gYS9ORVdT CisrKyBiL05FV1MKQEAgLTQ1LDYgKzQ1LDEwIEBAIEdOVSBncmVwIE5FV1MgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAtKi0gb3V0bGluZSAtKi0KICAgb2YgYSBtdWx0aWJ5dGUg Y2hhcmFjdGVyIHdoZW4gdXNpbmcgYSAnXictYW5jaG9yZWQgYWx0ZXJuYXRlIGluIGEgcGF0dGVy biwKICAgbGVhZGluZyBpdCB0byBwcmludCBub24tbWF0Y2hpbmcgbGluZXMuICBbYnVnIHByZXNl bnQgc2luY2UgInRoZSBiZWdpbm5pbmciXQogCisgIGdyZXAgbm8gbG9uZ2VyIGNyYXNoZXMgZm9y IHBhdHRlcm5zIHRoYXQgY29udGFpbiBwZXJpb2QsIGJyYWNrZXQgZXhwcmVzc2lvbiwKKyAgYmFj ayByZWZlcmVuY2UsIGV0Yy4KKyAgW2J1ZyBpbnRyb2R1Y2VkIGluIGdyZXAtMi4xOV0KKwogICBn cmVwIC1FIHJlamVjdGVkIHVubWF0Y2hlZCAnKScsIGluc3RlYWQgb2YgdHJlYXRpbmcgaXQgbGlr ZSAnXCknLgogICBbYnVnIHByZXNlbnQgc2luY2UgInRoZSBiZWdpbm5pbmciXQogCmRpZmYgLS1n aXQgYS9zcmMvZGZhLmMgYi9zcmMvZGZhLmMKaW5kZXggZTBmYzEyMC4uZDllZjY1MiAxMDA2NDQK LS0tIGEvc3JjL2RmYS5jCisrKyBiL3NyYy9kZmEuYwpAQCAtMzY1OSw5ICszNjU5LDEyIEBAIGRm YXNzYnVpbGQgKHN0cnVjdCBkZmEgKmQpCiAgIHN1cC0+bmV3bGluZXMgPSBOVUxMOwogICBzdXAt Pm11c3RzID0gTlVMTDsKIAotICBzdXAtPmNoYXJjbGFzc2VzID0geG5tYWxsb2MgKHN1cC0+Y2Fs bG9jLCBzaXplb2YgKnN1cC0+Y2hhcmNsYXNzZXMpOwotICBtZW1jcHkgKHN1cC0+Y2hhcmNsYXNz ZXMsIGQtPmNoYXJjbGFzc2VzLAotICAgICAgICAgIGQtPmNpbmRleCAqIHNpemVvZiAqc3VwLT5j aGFyY2xhc3Nlcyk7CisgIGlmIChzdXAtPmNhbGxvYyA+IDApCisgICAgeworICAgICAgc3VwLT5j aGFyY2xhc3NlcyA9IHhubWFsbG9jIChzdXAtPmNhbGxvYywgc2l6ZW9mICpzdXAtPmNoYXJjbGFz c2VzKTsKKyAgICAgIG1lbWNweSAoc3VwLT5jaGFyY2xhc3NlcywgZC0+Y2hhcmNsYXNzZXMsCisg ICAgICAgICAgICAgIGQtPmNpbmRleCAqIHNpemVvZiAqc3VwLT5jaGFyY2xhc3Nlcyk7CisgICAg fQogCiAgIHN1cC0+dG9rZW5zID0geG5tYWxsb2MgKGQtPnRpbmRleCwgMiAqIHNpemVvZiAqc3Vw LT50b2tlbnMpOwogICBzdXAtPnRhbGxvYyA9IGQtPnRpbmRleCAqIDI7Ci0tIAoyLjEuMwoK --------_5467187D0000000071DF_MULTIPART_MIXED_-- From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 15 13:01:13 2014 Received: (at 19061) by debbugs.gnu.org; 15 Nov 2014 18:01:14 +0000 Received: from localhost ([127.0.0.1]:34069 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xpher-0003XU-B7 for submit@debbugs.gnu.org; Sat, 15 Nov 2014 13:01:13 -0500 Received: from mail-yk0-f172.google.com ([209.85.160.172]:41535) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xpheo-0003XM-Pu for 19061@debbugs.gnu.org; Sat, 15 Nov 2014 13:01:11 -0500 Received: by mail-yk0-f172.google.com with SMTP id 131so339249ykp.31 for <19061@debbugs.gnu.org>; Sat, 15 Nov 2014 10:01:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=y/0SABTRIlcX5PiMwfK2ilTlUgwU+yDYlFe6xzpUA0E=; b=qJ+Ai80TyHYT0SSdw9FXzEoozINGJkWwdfb2IXHJJItUVhKqfd4z5Y9Acfi90dAso8 whu/Mw6zvYFWpTr9B/ZWzwBzW0NYGnpU7rifwZd8/rA+j1XgedWVAh67ceM8yqm73FJm 7qm65yZ/X8ULsp4BkCEBtggXZStqDV9FdZVN7nXZ8YDAhC/ZTAUqW30zuFPyZB5Uof0Q zNvSywqi8GWc4b3dhzQ6ZvV5R6UNwy1V5jXInqg3h8xuC3lTNov3cdIK51M5UVy3lkQK ppUdhwpfog1VA/aM5E1KQVFO2ltEDeQkS8jhNmbhJtWvlRuXwkGw0kjv7PdrPniayrET YAQQ== X-Received: by 10.170.186.74 with SMTP id c71mr13535728yke.46.1416074469981; Sat, 15 Nov 2014 10:01:09 -0800 (PST) MIME-Version: 1.0 Received: by 10.170.157.9 with HTTP; Sat, 15 Nov 2014 10:00:49 -0800 (PST) In-Reply-To: <20141115181123.71E4.27F6AC2D@kcn.ne.jp> References: <20141115181123.71E4.27F6AC2D@kcn.ne.jp> From: Jim Meyering Date: Sat, 15 Nov 2014 10:00:49 -0800 X-Google-Sender-Auth: BGX0fCmIT2Cm6vLVogFCL0SDrtY Message-ID: Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory To: Norihiro Tanaka Content-Type: text/plain; charset=ISO-8859-1 X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 19061 Cc: 19061@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) On Sat, Nov 15, 2014 at 1:11 AM, Norihiro Tanaka wrote: > If original DFA does not have any CSETs, no memory allocated for CSET. > Even then DFA try to copy CSET from original DFA to the superset. As > a result, it is caused to access to unallocated memory. We have no test > case so that it is very difficult that we always reproduce this bug, as > CSET may be added only one in building superset. Thank you for the patch. That seems like a fine change, but so far, I cannot see how it avoids accessing uninitialized memory. I do see that it fixes an error whereby memcpy was being called with its 2nd argument NULL, though in each case, the third argument is always 0. Passing a NULL pointer as the 2nd argument to memcpy is officially "undefined behavior", and I confirmed that building with gcc and its "undefined behavior sanitizer", the problem was exposed, and that your patch fixes it. Do you know of a way to make grep crash, as stated in your proposed NEWS entry? If so, please give details. It is UB after all. Perhaps you found a system whose memcpy dereferences the source pointer even when the size is 0? From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 15 15:59:32 2014 Received: (at 19061) by debbugs.gnu.org; 15 Nov 2014 20:59:32 +0000 Received: from localhost ([127.0.0.1]:34153 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpkRP-0002ZR-LG for submit@debbugs.gnu.org; Sat, 15 Nov 2014 15:59:32 -0500 Received: from smtp.cs.ucla.edu ([131.179.128.62]:36297) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpkRN-0002ZJ-25 for 19061@debbugs.gnu.org; Sat, 15 Nov 2014 15:59:29 -0500 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 7865FA60005; Sat, 15 Nov 2014 12:59:26 -0800 (PST) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6acfTHiYwd8E; Sat, 15 Nov 2014 12:59:17 -0800 (PST) Received: from [192.168.1.9] (pool-71-177-17-123.lsanca.dsl-w.verizon.net [71.177.17.123]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 7EBAFA60035; Sat, 15 Nov 2014 12:59:17 -0800 (PST) Message-ID: <5467BEA1.7030405@cs.ucla.edu> Date: Sat, 15 Nov 2014 12:59:13 -0800 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0 MIME-Version: 1.0 To: Jim Meyering , Norihiro Tanaka Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory References: <20141115181123.71E4.27F6AC2D@kcn.ne.jp> In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 19061 Cc: 19061@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) Jim Meyering wrote: > Perhaps you found a system whose memcpy > dereferences the source pointer even when the size is 0? That seems pretty unlikely, on a flat-address-space machine. And grep already assumes a flat address space, since gnulib does. From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 15 20:06:46 2014 Received: (at 19061) by debbugs.gnu.org; 16 Nov 2014 01:06:46 +0000 Received: from localhost ([127.0.0.1]:34203 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpoIf-0003TM-QB for submit@debbugs.gnu.org; Sat, 15 Nov 2014 20:06:46 -0500 Received: from mailgw05.kcn.ne.jp ([61.86.7.212]:62262) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpoId-0003TA-2x for 19061@debbugs.gnu.org; Sat, 15 Nov 2014 20:06:44 -0500 Received: from imp02 (mailgw6.kcn.ne.jp [61.86.15.232]) by mailgw05.kcn.ne.jp (Postfix) with ESMTP id B0F1C67E11 for <19061@debbugs.gnu.org>; Sun, 16 Nov 2014 10:06:40 +0900 (JST) Received: from mail09.kcn.ne.jp ([61.86.6.188]) by imp02 with bizsmtp id G16g1p00V43QJrh0116gjZ; Sun, 16 Nov 2014 10:06:40 +0900 X-OrgRCPT: 19061@debbugs.gnu.org Received: from [10.120.1.32] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail09.kcn.ne.jp (Postfix) with ESMTPA id 941CA1BD00C8; Sun, 16 Nov 2014 10:06:40 +0900 (JST) Date: Sun, 16 Nov 2014 10:06:41 +0900 From: Norihiro Tanaka To: Jim Meyering Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory In-Reply-To: References: <20141115181123.71E4.27F6AC2D@kcn.ne.jp> Message-Id: <20141116100641.A9A0.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 19061 Cc: 19061@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) On Sat, 15 Nov 2014 10:00:49 -0800 Jim Meyering wrote: > Thank you for the patch. > That seems like a fine change, but so far, I cannot see how > it avoids accessing uninitialized memory. > I do see that it fixes an error whereby memcpy was being > called with its 2nd argument NULL, though in each case, > the third argument is always 0. Passing a NULL pointer as > the 2nd argument to memcpy is officially "undefined > behavior", and I confirmed that building with gcc and its > "undefined behavior sanitizer", the problem was exposed, > and that your patch fixes it. > > Do you know of a way to make grep crash, as stated in your > proposed NEWS entry? If so, please give details. > > It is UB after all. Perhaps you found a system whose memcpy > dereferences the source pointer even when the size is 0? Thanks for the review. I ran accross this problem when I made next improvement. If size is 0, when dfa_charclass_index has been called, the crash was caused. And If I fixed it, the crash was not caused. So I think that it is a bug. However, I deleted the branch as the improvement was bad. And I cannot see cause of the bug in the source code. I seem that the code has no bug. Further more, I could not reproduce it, though I re-wrote a similar code to the branch. Possibly other changes which I made are bad, and it might cause a buffer-overrun and override memory range for characlasses in the branch. From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 16 01:28:18 2014 Received: (at 19061) by debbugs.gnu.org; 16 Nov 2014 06:28:18 +0000 Received: from localhost ([127.0.0.1]:34267 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XptJp-0003AH-SG for submit@debbugs.gnu.org; Sun, 16 Nov 2014 01:28:18 -0500 Received: from mail-yk0-f178.google.com ([209.85.160.178]:35968) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XptJj-0003A5-St for 19061@debbugs.gnu.org; Sun, 16 Nov 2014 01:28:13 -0500 Received: by mail-yk0-f178.google.com with SMTP id 20so2131147yks.37 for <19061@debbugs.gnu.org>; Sat, 15 Nov 2014 22:28:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=A0Fnd7flfhG94h1EHDH8H+PlsRBNsVTPfVcIHteHoBQ=; b=L8vMgAwKoJ7GSOtfw9WjlxDdXE3yNVSMvH9gFXK3qmMDlvNFbRUF5gkkaVzFLTmZsP jt6qc2cGo3MjYxD6h6pHsP4MyuJJSwB6ct0BJ3n8X8K7efRZ2H2SrTCan88C4W3IWXKX iDSYCRtswrJhSP9l3gqvWU3yzYqzaS5yHW7TaOKc7IKRZfuQrfpPRX4BEnUISM/E6FAT GFUN5bzUoONn0mJu4jvvXRnHuN4+2rOOxFA40/yDmByQT6jvfm3k7Re3DRLa7l8ingO9 KUBFUyiZ8Y4KOWEEuZ++GmfAWnu5E9hHcTthD1G0RhdlwXDugFXeUs1yFpdtgbY0Tb4y mrDg== X-Received: by 10.170.69.67 with SMTP id l64mr20375730ykl.13.1416119291262; Sat, 15 Nov 2014 22:28:11 -0800 (PST) MIME-Version: 1.0 Received: by 10.170.157.9 with HTTP; Sat, 15 Nov 2014 22:27:50 -0800 (PST) In-Reply-To: <20141116100641.A9A0.27F6AC2D@kcn.ne.jp> References: <20141115181123.71E4.27F6AC2D@kcn.ne.jp> <20141116100641.A9A0.27F6AC2D@kcn.ne.jp> From: Jim Meyering Date: Sat, 15 Nov 2014 22:27:50 -0800 X-Google-Sender-Auth: IirtjefoyDd58B_Qgt3aDIwuxV4 Message-ID: Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory To: Norihiro Tanaka Content-Type: multipart/mixed; boundary=001a1139f33450d6190507f3f796 X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 19061 Cc: 19061 <19061@debbugs.gnu.org> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) --001a1139f33450d6190507f3f796 Content-Type: text/plain; charset=ISO-8859-1 On Sat, Nov 15, 2014 at 5:06 PM, Norihiro Tanaka wrote: > On Sat, 15 Nov 2014 10:00:49 -0800 > Jim Meyering wrote: >> Thank you for the patch. >> That seems like a fine change, but so far, I cannot see how >> it avoids accessing uninitialized memory. >> I do see that it fixes an error whereby memcpy was being >> called with its 2nd argument NULL, though in each case, >> the third argument is always 0. Passing a NULL pointer as >> the 2nd argument to memcpy is officially "undefined >> behavior", and I confirmed that building with gcc and its >> "undefined behavior sanitizer", the problem was exposed, >> and that your patch fixes it. >> >> Do you know of a way to make grep crash, as stated in your >> proposed NEWS entry? If so, please give details. >> >> It is UB after all. Perhaps you found a system whose memcpy >> dereferences the source pointer even when the size is 0? > > Thanks for the review. > > I ran accross this problem when I made next improvement. If size is 0, > when dfa_charclass_index has been called, the crash was caused. And If > I fixed it, the crash was not caused. So I think that it is a bug. > > However, I deleted the branch as the improvement was bad. And I cannot > see cause of the bug in the source code. I seem that the code has no bug. > Further more, I could not reproduce it, though I re-wrote a similar code > to the branch. > > Possibly other changes which I made are bad, and it might cause a > buffer-overrun and override memory range for characlasses in the branch. Thanks for confirming. In that case, since I see no harm in calling xnmalloc with N = 0, I will use a more conservative change: guard only the undefined use of memcpy. I've left your name on this amended patch. --001a1139f33450d6190507f3f796 Content-Type: application/octet-stream; name="0001-dfa-avoid-undefined-behavior.patch" Content-Disposition: attachment; filename="0001-dfa-avoid-undefined-behavior.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_i2k0sdbq0 RnJvbSBmODc4MjE2OTgyZDBkMzI2YWM4Mzk3YTFhNDM2YjJmZDYwZWQ1NGUyIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBTYXQsIDE1IE5vdiAyMDE0IDIyOjIxOjM0IC0wODAwClN1YmplY3Q6IFtQQVRDSF0gZGZh OiBhdm9pZCB1bmRlZmluZWQgYmVoYXZpb3IKCiogc3JjL2RmYS5jIChkZmFzc2J1aWxkKTogRG9u J3QgY2FsbCBtZW1jcHkgd2l0aCBhIHNlY29uZAphcmd1bWVudCBvZiBOVUxMLCBldmVuIHdoZW4g dGhlIHNpemUgKDNyZCBhcmd1bWVudCkgaXMgMC4KLS0tCiBzcmMvZGZhLmMgfCA3ICsrKysrLS0K IDEgZmlsZSBjaGFuZ2VkLCA1IGluc2VydGlvbnMoKyksIDIgZGVsZXRpb25zKC0pCgpkaWZmIC0t Z2l0IGEvc3JjL2RmYS5jIGIvc3JjL2RmYS5jCmluZGV4IGUwZmMxMjAuLjY1ODYyZTggMTAwNjQ0 Ci0tLSBhL3NyYy9kZmEuYworKysgYi9zcmMvZGZhLmMKQEAgLTM2NjAsOCArMzY2MCwxMSBAQCBk ZmFzc2J1aWxkIChzdHJ1Y3QgZGZhICpkKQogICBzdXAtPm11c3RzID0gTlVMTDsKCiAgIHN1cC0+ Y2hhcmNsYXNzZXMgPSB4bm1hbGxvYyAoc3VwLT5jYWxsb2MsIHNpemVvZiAqc3VwLT5jaGFyY2xh c3Nlcyk7Ci0gIG1lbWNweSAoc3VwLT5jaGFyY2xhc3NlcywgZC0+Y2hhcmNsYXNzZXMsCi0gICAg ICAgICAgZC0+Y2luZGV4ICogc2l6ZW9mICpzdXAtPmNoYXJjbGFzc2VzKTsKKyAgaWYgKGQtPmNp bmRleCkKKyAgICB7CisgICAgICBtZW1jcHkgKHN1cC0+Y2hhcmNsYXNzZXMsIGQtPmNoYXJjbGFz c2VzLAorICAgICAgICAgICAgICBkLT5jaW5kZXggKiBzaXplb2YgKnN1cC0+Y2hhcmNsYXNzZXMp OworICAgIH0KCiAgIHN1cC0+dG9rZW5zID0geG5tYWxsb2MgKGQtPnRpbmRleCwgMiAqIHNpemVv ZiAqc3VwLT50b2tlbnMpOwogICBzdXAtPnRhbGxvYyA9IGQtPnRpbmRleCAqIDI7Ci0tIAoyLjEu MgoK --001a1139f33450d6190507f3f796-- From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 16 04:18:13 2014 Received: (at 19061) by debbugs.gnu.org; 16 Nov 2014 09:18:13 +0000 Received: from localhost ([127.0.0.1]:34305 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpvyG-0008LX-Nu for submit@debbugs.gnu.org; Sun, 16 Nov 2014 04:18:13 -0500 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:34264) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XpvyA-0008LC-KU for 19061@debbugs.gnu.org; Sun, 16 Nov 2014 04:18:11 -0500 Received: from imp02 (mailgw6.kcn.ne.jp [61.86.15.232]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 9AD78E80020 for <19061@debbugs.gnu.org>; Sun, 16 Nov 2014 18:18:04 +0900 (JST) Received: from mail04.kcn.ne.jp ([61.86.6.183]) by imp02 with bizsmtp id G9J41p00L3wvxAM019J4F0; Sun, 16 Nov 2014 18:18:04 +0900 X-OrgRCPT: 19061@debbugs.gnu.org Received: from [10.120.1.32] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail04.kcn.ne.jp (Postfix) with ESMTPA id 3DB58129009B; Sun, 16 Nov 2014 18:18:04 +0900 (JST) Date: Sun, 16 Nov 2014 18:18:04 +0900 From: Norihiro Tanaka To: Jim Meyering Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory In-Reply-To: References: <20141116100641.A9A0.27F6AC2D@kcn.ne.jp> Message-Id: <20141116181803.A9A8.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 19061 Cc: 19061 <19061@debbugs.gnu.org> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) On Sat, 15 Nov 2014 22:27:50 -0800 Jim Meyering wrote: > Thanks for confirming. > In that case, since I see no harm in calling xnmalloc with N = 0, I > will use a more conservative change: guard only the undefined use of > memcpy. > I've left your name on this amended patch. Thanks for the ajustment. You are right, but the purpose of the code is to make a clone of original DFA. If we do not guard xnmalloc, when calloc is 0, charclasses is NULL in original DFA, and it is *NOT* NULL in the superset. I think that it is not right logically. From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 16 10:48:57 2014 Received: (at 19061) by debbugs.gnu.org; 16 Nov 2014 15:48:57 +0000 Received: from localhost ([127.0.0.1]:35459 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xq24P-0002G9-3c for submit@debbugs.gnu.org; Sun, 16 Nov 2014 10:48:57 -0500 Received: from mail-yh0-f42.google.com ([209.85.213.42]:56344) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xq24N-0002G1-Nj for 19061@debbugs.gnu.org; Sun, 16 Nov 2014 10:48:56 -0500 Received: by mail-yh0-f42.google.com with SMTP id b6so10239472yha.15 for <19061@debbugs.gnu.org>; Sun, 16 Nov 2014 07:48:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=naG8K5K/u5l+/c5BE8hcwCi4MsP7fZVzCQtv25TrsmY=; b=WQDLiLwjH8TEiGCDikzsHQ/7d8DocMllscEeGrNbK+IH0bRaU/Ao5Z+fw/c7PxTBmL dh7BsQe5dQwvl62ocLEquPtRtnK4dErFKvsVY4UTOBV+Rf63t5mgKrGfwZKx4h0yRL9L kh8w0pvZMQW293I0rQKQV8P68kWaxS9TWyYGxU0q7chhRKdqHrrhRyVtaUwV3/CYJ14p NcfQzMgRlF7bN3BYNrudWp+QNQn09ne/mdgsxL4XdoZ9mXfg4epgnfpWgeWcOAVCW6Za QsN5OeSjsMM5FGmXXomy07GckxVCA9ot3N33vtomN+QPaoj142F8k//8M230QzD6QjZ6 DPPA== X-Received: by 10.236.230.36 with SMTP id i34mr46866yhq.124.1416152934936; Sun, 16 Nov 2014 07:48:54 -0800 (PST) MIME-Version: 1.0 Received: by 10.170.157.9 with HTTP; Sun, 16 Nov 2014 07:48:34 -0800 (PST) In-Reply-To: <20141116181803.A9A8.27F6AC2D@kcn.ne.jp> References: <20141116100641.A9A0.27F6AC2D@kcn.ne.jp> <20141116181803.A9A8.27F6AC2D@kcn.ne.jp> From: Jim Meyering Date: Sun, 16 Nov 2014 07:48:34 -0800 X-Google-Sender-Auth: Hggn8Yh1ssJVFLq-NzPZ_2CMak4 Message-ID: Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory To: Norihiro Tanaka Content-Type: text/plain; charset=ISO-8859-1 X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 19061 Cc: 19061 <19061@debbugs.gnu.org> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) On Sun, Nov 16, 2014 at 1:18 AM, Norihiro Tanaka wrote: > On Sat, 15 Nov 2014 22:27:50 -0800 > Jim Meyering wrote: >> Thanks for confirming. >> In that case, since I see no harm in calling xnmalloc with N = 0, I >> will use a more conservative change: guard only the undefined use of >> memcpy. >> I've left your name on this amended patch. > > Thanks for the ajustment. You are right, but the purpose of the code > is to make a clone of original DFA. If we do not guard xnmalloc, when > calloc is 0, charclasses is NULL in original DFA, and it is *NOT* NULL > in the superset. I think that it is not right logically. Does some code assume that V->charclasses != NULL implies 0 < V->calloc? I would argue that such code is incorrect. I.e., in the degenerate case (calloc == 0), the code should not distinguish between a NULL charclasses member and one that points to a malloc'd buffer of length 0. From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 16 10:50:01 2014 Received: (at 19061-done) by debbugs.gnu.org; 16 Nov 2014 15:50:01 +0000 Received: from localhost ([127.0.0.1]:35463 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xq25Q-0002I8-Np for submit@debbugs.gnu.org; Sun, 16 Nov 2014 10:50:01 -0500 Received: from mail-yh0-f48.google.com ([209.85.213.48]:62705) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xq25O-0002I0-Cu for 19061-done@debbugs.gnu.org; Sun, 16 Nov 2014 10:49:58 -0500 Received: by mail-yh0-f48.google.com with SMTP id i57so368047yha.21 for <19061-done@debbugs.gnu.org>; Sun, 16 Nov 2014 07:49:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=b8rUDXSqroGkf4J7gIiAr12eYmFjbFM/Tf9XnakPudU=; b=dCy1nW2k62/k79RkoV6KODS//eQD6xAOx1x2KwnTiEbKxeIpJPlKErd9L2P/ibAJmb xIlnDVLsA/3KtFLy52HCJ3Ke4oCSHfwTSLJ7vNRApFl3EKaqvwK7vGvVS8qe76zKjAka a83bhqD0h+4TYweq1MbYeBBzYjzScZ8kzlz9LB+A1wF14In+DRQc0fF4zKOSKo1ICIQe JQNSlzFsos13CbEMy21SfuEeAxaU5JUKSIq4oR8DnMNYb3GW4fJM7EQ5wKrH/PsoxTKI vNBJzC3CzHbFhF5ADOHOoDf0XupM12fN3W6W+HLGWlKV1c+bb452TqD8Cn80wEkFriGr VnkA== X-Received: by 10.170.128.207 with SMTP id u198mr2554012ykb.51.1416152997963; Sun, 16 Nov 2014 07:49:57 -0800 (PST) MIME-Version: 1.0 Received: by 10.170.157.9 with HTTP; Sun, 16 Nov 2014 07:49:37 -0800 (PST) In-Reply-To: References: <20141116100641.A9A0.27F6AC2D@kcn.ne.jp> <20141116181803.A9A8.27F6AC2D@kcn.ne.jp> From: Jim Meyering Date: Sun, 16 Nov 2014 07:49:37 -0800 X-Google-Sender-Auth: XsKqZZBA6d_3dKH0yi4kZwuzqi8 Message-ID: Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory To: Norihiro Tanaka Content-Type: text/plain; charset=ISO-8859-1 X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 19061-done Cc: 19061 <19061-done@debbugs.gnu.org> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) I have pushed that change and am preparing another snapshot. From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 16 17:56:21 2014 Received: (at 19061) by debbugs.gnu.org; 16 Nov 2014 22:56:21 +0000 Received: from localhost ([127.0.0.1]:35629 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xq8k0-0007K7-MG for submit@debbugs.gnu.org; Sun, 16 Nov 2014 17:56:20 -0500 Received: from mailgw06.kcn.ne.jp ([61.86.7.213]:39111) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Xq8jw-0007Jw-QD for 19061@debbugs.gnu.org; Sun, 16 Nov 2014 17:56:18 -0500 Received: from imp02 (mailgw6.kcn.ne.jp [61.86.15.232]) by mailgw06.kcn.ne.jp (Postfix) with ESMTP id 406D6E80021 for <19061@debbugs.gnu.org>; Mon, 17 Nov 2014 07:56:14 +0900 (JST) Received: from mail01.kcn.ne.jp ([61.86.6.180]) by imp02 with bizsmtp id GNwE1p0043t2w9Z01NwEUy; Mon, 17 Nov 2014 07:56:14 +0900 X-OrgRCPT: 19061@debbugs.gnu.org Received: from [10.120.1.55] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail01.kcn.ne.jp (Postfix) with ESMTPA id F0CED5A8310; Mon, 17 Nov 2014 07:56:13 +0900 (JST) Date: Mon, 17 Nov 2014 07:56:13 +0900 From: Norihiro Tanaka To: Jim Meyering Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated memory In-Reply-To: References: <20141116181803.A9A8.27F6AC2D@kcn.ne.jp> Message-Id: <20141117075612.6DFA.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 19061 Cc: 19061 <19061@debbugs.gnu.org> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) On Sun, 16 Nov 2014 07:48:34 -0800 Jim Meyering wrote: > Does some code assume that V->charclasses != NULL implies > 0 < V->calloc? I would argue that such code is incorrect. I.e., > in the degenerate case (calloc == 0), the code should not > distinguish between a NULL charclasses member and one > that points to a malloc'd buffer of length 0. Thanks for the pushing. I understood that you said. From unknown Fri Jun 20 07:26:51 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Mon, 15 Dec 2014 12:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator