From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.6 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: from minnie.tuhs.org (minnie.tuhs.org [50.116.15.146]) by inbox.vuxu.org (Postfix) with ESMTP id 4DCE028C47 for ; Fri, 24 May 2024 07:42:26 +0200 (CEST) Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 36F4C43A8D; Fri, 24 May 2024 15:42:21 +1000 (AEST) Received: from omta40.uswest2.a.cloudfilter.net (omta40.uswest2.a.cloudfilter.net [35.89.44.39]) by minnie.tuhs.org (Postfix) with ESMTPS id 85F6943A89 for ; Fri, 24 May 2024 15:42:08 +1000 (AEST) Received: from eig-obgw-6006a.ext.cloudfilter.net ([10.0.30.182]) by cmsmtp with ESMTPS id AK49scGOyrtmgANgusRLID; Fri, 24 May 2024 05:42:08 +0000 Received: from shared056.arvixe.com ([129.121.4.205]) by cmsmtp with ESMTPS id ANgtsBpuFccVaANgtsWimY; Fri, 24 May 2024 05:42:07 +0000 X-Authority-Analysis: v=2.4 cv=ObeeDATY c=1 sm=1 tr=0 ts=665028af a=ZXEiJ4ldN1eQiIvORaK8zw==:117 a=ZXEiJ4ldN1eQiIvORaK8zw==:17 a=TpHVaj0NuXgA:10 a=MwmYBGSu7XQA:10 a=7j0FZ4iXMVMA:10 a=pGLkceISAAAA:8 a=ir6IjIBgDnYbYQIntAIA:9 a=QEXdDO2ut3YA:10 a=LtM64g7_wCwFRoVU:21 a=_W_S_7VecoQA:10 a=lqcHg5cX4UMA:10 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=humeweb.com ; s=default; h=References:To:Cc:In-Reply-To:Date:Subject:Mime-Version: Content-Type:Message-Id:From:Sender:Reply-To:Content-Transfer-Encoding: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=+QfYlxSGFmHlY5Q94ujUpbDOKFbYb4X9+u1xalHOsDQ=; b=HkaAezkLVHU0QPrCX+a0c2jgvP lyIulfnqDrmCvcBwW7iVpHKhHDjakaD940JDzxqDFNmFh7wgk0esJ5pbR1fd9E/rxzMOVywXpSHw7 WV0c67WmgQI0wUfDQdBYuCvIOGsds1b1t87kItcDVF7VMkw+09EA0NDZSZzMc17ed4pE=; Received: from 99-98-248-85.lightspeed.irvnca.sbcglobal.net ([99.98.248.85]:50104 helo=smtpclient.apple) by shared056.arvixe.com with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96.2) (envelope-from ) id 1sANgs-000Hpo-2Z; Fri, 24 May 2024 00:42:06 -0500 From: "andrew@humeweb.com" Message-Id: Content-Type: multipart/alternative; boundary="Apple-Mail=_D8923162-D7BD-4E39-B3FA-0561E0248817" Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3774.500.171.1.1\)) Date: Thu, 23 May 2024 22:41:55 -0700 In-Reply-To: To: Rob Pike References: X-Mailer: Apple Mail (2.3774.500.171.1.1) X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - shared056.arvixe.com X-AntiAbuse: Original Domain - tuhs.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - humeweb.com X-BWhitelist: no X-Source-IP: 99.98.248.85 X-Source-L: No X-Exim-ID: 1sANgs-000Hpo-2Z X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 99-98-248-85.lightspeed.irvnca.sbcglobal.net (smtpclient.apple) [99.98.248.85]:50104 X-Source-Auth: ahume X-Email-Count: 1 X-Org: HG=asoshared_arvixe;ORG=aso; X-Source-Cap: YWh1bWU7YWh1bWU7c2hhcmVkMDU2LmFydml4ZS5jb20= X-Local-Domain: yes X-CMAE-Envelope: MS4xfHF8p3bKb6AeLGZrzBn8kw5AZjQg0LnDMYCVn0gPE9eRW+JgRFj027HHrxh4nM7EsSOyKjwxaWm7YhfGA7BBl5zZO9aDvQB7QEXg5gVUUdhk6lklG8lE np+0mTk2VeVDu9pniZfcVgSB/mwy4jg1km0MyoVRYq2ERS1F6HaTsbmn4hTxvkDKL+BNM2nixBOLxA== Message-ID-Hash: B4GURBCNONA5KCTJHI63MU7AJRVV5RR6 X-Message-ID-Hash: B4GURBCNONA5KCTJHI63MU7AJRVV5RR6 X-MailFrom: andrew@humeweb.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: Douglas McIlroy , TUHS main list X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [TUHS] Re: A fuzzy awk List-Id: The Unix Heritage Society mailing list Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --Apple-Mail=_D8923162-D7BD-4E39-B3FA-0561E0248817 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 i did some of the later testing of bitblt. it was a lovely thing, slowly constructing a trustable synthetic bitblt of ever great size and range that you could compare the bitblt to be = tested against. and we did find a couple of bugs, much to reiser=E2=80=99s chagrin. > On May 23, 2024, at 1:52=E2=80=AFPM, Rob Pike = wrote: >=20 > The semantic distinction is important but the end result is very = similar. "Fuzzing" as it is now called (for no reason I can intuit) = tries to get to the troublesome cases faster by a sort of depth-first = search, but exhaustive will always beat it for value. Our exhaustive = tester for bitblt, first done by John Reiser if I remember right, set = the stage for my own thinking about how you properly test something. >=20 > -rob >=20 >=20 > On Thu, May 23, 2024 at 11:49=E2=80=AFPM Douglas McIlroy = > = wrote: >> > Doug McIlroy was generating random regular expressions >>=20 >> Actually not. I exhaustively (within limits) tested an RE recognizer = without knowingly generating any RE either mechanically or by hand. >>=20 >> The trick: =46rom recursive equations (easily derived from the = grammar of REs), I counted how many REs exist up to various limits on = token counts, Then I generated all strings that satisfied those limits, = turned the recognizer loose on them and counted how many it accepted. = Any disagreement of counts revealed the existence (but not any symptom) = of bugs.=20 >>=20 >> Unlike most diagnostic techniques, this scheme produces a certificate = of (very high odds on) correctness over a representative subdomain. The = scheme also agnostically checks behavior on bad inputs as well as good. = It does not, however, provide a stress test of a recognizer's capacity = limits. And its exponential nature limits its applicability to rather = small domains. (REs have only 5 distinct kinds of token.) >>=20 >> Doug --Apple-Mail=_D8923162-D7BD-4E39-B3FA-0561E0248817 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 i did some of = the later testing of bitblt.
it was a lovely thing, slowly = constructing a trustable synthetic bitblt
of ever great size = and range that you could compare the bitblt to be tested = against.

and we did find a couple of bugs, much = to reiser=E2=80=99s chagrin.

On May 23, 2024, at 1:52=E2=80=AFPM, Rob Pike = <robpike@gmail.com> wrote:

The = semantic distinction is important but the end result is very similar. = "Fuzzing" as it is now called (for no reason I can intuit) tries to get = to the troublesome cases faster by a sort of depth-first search, but = exhaustive will always beat it for value. Our exhaustive tester for = bitblt, first done by John Reiser if I remember right, set the stage for = my own thinking about how you properly test something.

-rob


On Thu, May = 23, 2024 at 11:49=E2=80=AFPM Douglas McIlroy <douglas.mcilroy@dartmouth.ed= u> wrote:
> Doug = McIlroy was generating random regular expressions

Actually not. I exhaustively (within limits) = tested an RE recognizer without knowingly generating any RE either = mechanically or by hand.

The = trick: =46rom recursive equations (easily derived from the grammar of = REs), I counted how many REs exist up to various limits on token counts, = Then I generated all strings that satisfied those limits, turned the = recognizer loose on them and counted how many it accepted. Any = disagreement of counts revealed the existence (but not any symptom) of = bugs. 

Unlike most diagnostic techniques, this scheme produces a = certificate of (very high odds on) correctness over a representative = subdomain. The = scheme also agnostically checks behavior on bad inputs as well as = good.  It = does not, however, provide a stress test of a recognizer's capacity = limits. And its = exponential nature limits its applicability to rather small domains. = (REs have only 5 distinct kinds of token.)

Doug

= --Apple-Mail=_D8923162-D7BD-4E39-B3FA-0561E0248817--