[TUHS] "Webster's Second on the Head of a Pin"?

[TUHS] "Webster's Second on the Head of a Pin"?

[Royce Williams]

[-- Attachment #1: Type: text/plain, Size: 406 bytes --]

Someone I know is seeking the original version of an internal Bell Labs
memo from 1974 titled "Webster's Second on the Head of a Pin" by Morris and
Thompson. The topic appears to be related to improving the speed of lookups
or search. It's cited in a few papers as "Unpublished Technical Memo, Bell
Laboratories, Murray Hill, NJ 1974." All I can find online is citations.
Any leads appreciated!

-- 
Royce

[-- Attachment #2: Type: text/html, Size: 624 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Douglas McIlroy]

I can supply a copy if no one else has beaten me to it.

Ron Hardin subsequently pushed the limit even further. Unfortunately,
I do not have a record of that work.

Doug

On Sat, Dec 28, 2024 at 9:54 PM Royce Williams <royce@techsolvency.com> wrote:
>
> Someone I know is seeking the original version of an internal Bell Labs memo from 1974 titled "Webster's Second on the Head of a Pin" by Morris and Thompson. The topic appears to be related to improving the speed of lookups or search. It's cited in a few papers as "Unpublished Technical Memo, Bell Laboratories, Murray Hill, NJ 1974." All I can find online is citations. Any leads appreciated!
>
> --
> Royce

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[sjenkin]

Not dissimilar work at AT&T Research ~2000 - compressing fixed-length records, better than gzip, +30% for similar compute time.

‘pzip’ - Adam Bushman & Glen Fowler
	<https://web.archive.org/web/20041019142227/http://www.research.att.com/~gsf/pzip/pzip.html>

Later work by others, building on ‘pzip’ ,claims ‘100x’.

> On 30 Dec 2024, at 00:44, Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
> 
> I can supply a copy if no one else has beaten me to it.
> 
> Ron Hardin subsequently pushed the limit even further. Unfortunately,
> I do not have a record of that work.
> 
> Doug
> 
> On Sat, Dec 28, 2024 at 9:54 PM Royce Williams <royce@techsolvency.com> wrote:
>> 
>> Someone I know is seeking the original version of an internal Bell Labs memo from 1974 titled "Webster's Second on the Head of a Pin" by Morris and Thompson. The topic appears to be related to improving the speed of lookups or search. It's cited in a few papers as "Unpublished Technical Memo, Bell Laboratories, Murray Hill, NJ 1974." All I can find online is citations. Any leads appreciated!
>> 
>> --
>> Royce


Other links:

This repository included ksh-93 sources

Glen Fowlers’ downloads
	<https://web.archive.org/web/20130514131958/http://www2.research.att.com/~gsf/download/>

Later AT&T Research page with Software downloads
	<https://web.archive.org/web/20090626002505/http://public.research.att.com/index.cfm?portal=19&h=55>

THE AT&T AST OPENSOURCE SOFTWARE COLLECTION
	2000
	<https://www.usenix.org/legacy/publications/library/proceedings/usenix2000/freenix/full_papers/fowler/fowler.pdf>

Github Repo for AST - I couldn’t make these compile
	<https://github.com/att/ast/tree/master>

KSH93
	<https://github.com/ksh93>

--
Steve Jenkin, IT Systems and Design 
0412 786 915 (+61 412 786 915)
PO Box 38, Kippax ACT 2615, AUSTRALIA

mailto:sjenkin@canb.auug.org.au http://members.tip.net.au/~sjenkin

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Chet Ramey via TUHS]

[-- Attachment #1.1: Type: text/plain, Size: 699 bytes --]

On 12/29/24 8:44 AM, Douglas McIlroy wrote:
> I can supply a copy if no one else has beaten me to it.
> 
> Ron Hardin subsequently pushed the limit even further. Unfortunately,
> I do not have a record of that work.

Along these same lines, does anyone on the list have a copy of

"J. A. Reeds, /bin/sh: The biggest UNIX security Loophole,
11217-840302-04TM, AT&T Bell Laboratories, Murray Hill, NJ (1984)"?

Years ago, in another lifetime, I wrote and asked him for a copy, but
never got a reply.

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
		 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 203 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Douglas McIlroy]

I have it and will try to scan it in the next few days. Bug me if it
doesn't appear.

Doug

On Tue, Dec 31, 2024 at 11:37 AM Chet Ramey <chet.ramey@case.edu> wrote:
>
> On 12/29/24 8:44 AM, Douglas McIlroy wrote:
> > I can supply a copy if no one else has beaten me to it.
> >
> > Ron Hardin subsequently pushed the limit even further. Unfortunately,
> > I do not have a record of that work.
>
> Along these same lines, does anyone on the list have a copy of
>
> "J. A. Reeds, /bin/sh: The biggest UNIX security Loophole,
> 11217-840302-04TM, AT&T Bell Laboratories, Murray Hill, NJ (1984)"?
>
> Years ago, in another lifetime, I wrote and asked him for a copy, but
> never got a reply.
>
> --
> ``The lyf so short, the craft so long to lerne.'' - Chaucer
>                  ``Ars longa, vita brevis'' - Hippocrates
> Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Rik Farrow]

[-- Attachment #1: Type: text/plain, Size: 1518 bytes --]

I wonder what Reeds meant. I know there are issues. For example, the 3B2 I
administered for a while in the late 80s had multiple accounts with rsh,
the restricted shell, as the login shell. That was okay, unless you used su
and then had access to a root shell.

HP/UX was way worse, with over 120 SUID shell scripts in the 90s. A much
more interesting example of insecurity. But somehow, I'm guessing that's
not what Reeds wrote about.

Rik


On Wed, Jan 1, 2025 at 8:02 AM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

> I have it and will try to scan it in the next few days. Bug me if it
> doesn't appear.
>
> Doug
>
> On Tue, Dec 31, 2024 at 11:37 AM Chet Ramey <chet.ramey@case.edu> wrote:
> >
> > On 12/29/24 8:44 AM, Douglas McIlroy wrote:
> > > I can supply a copy if no one else has beaten me to it.
> > >
> > > Ron Hardin subsequently pushed the limit even further. Unfortunately,
> > > I do not have a record of that work.
> >
> > Along these same lines, does anyone on the list have a copy of
> >
> > "J. A. Reeds, /bin/sh: The biggest UNIX security Loophole,
> > 11217-840302-04TM, AT&T Bell Laboratories, Murray Hill, NJ (1984)"?
> >
> > Years ago, in another lifetime, I wrote and asked him for a copy, but
> > never got a reply.
> >
> > --
> > ``The lyf so short, the craft so long to lerne.'' - Chaucer
> >                  ``Ars longa, vita brevis'' - Hippocrates
> > Chet Ramey, UTech, CWRU    chet@case.edu
> http://tiswww.cwru.edu/~chet/
>

[-- Attachment #2: Type: text/html, Size: 2239 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Douglas McIlroy]

I think $IFS ranks at the top of Jim's cabinet of horrors. For our
multilevel-secure Unix (https://www.cs.dartmouth.edu/~doug/IX), he
took almost everything out of the administrative shell, nosh (the
no-shell shell), The classic /bin/sh was not endowed with any of the
capabilities necessary to override Bell-LaPadula-Biba secrecy or
integrity constraints.

On Wed, Jan 1, 2025 at 1:11 PM Rik Farrow <rik@rikfarrow.com> wrote:
>
> I wonder what Reeds meant. I know there are issues. For example, the 3B2 I administered for a while in the late 80s had multiple accounts with rsh, the restricted shell, as the login shell. That was okay, unless you used su and then had access to a root shell.
>
> HP/UX was way worse, with over 120 SUID shell scripts in the 90s. A much more interesting example of insecurity. But somehow, I'm guessing that's not what Reeds wrote about.
>
> Rik
>
>
> On Wed, Jan 1, 2025 at 8:02 AM Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
>>
>> I have it and will try to scan it in the next few days. Bug me if it
>> doesn't appear.
>>
>> Doug
>>
>> On Tue, Dec 31, 2024 at 11:37 AM Chet Ramey <chet.ramey@case.edu> wrote:
>> >
>> > On 12/29/24 8:44 AM, Douglas McIlroy wrote:
>> > > I can supply a copy if no one else has beaten me to it.
>> > >
>> > > Ron Hardin subsequently pushed the limit even further. Unfortunately,
>> > > I do not have a record of that work.
>> >
>> > Along these same lines, does anyone on the list have a copy of
>> >
>> > "J. A. Reeds, /bin/sh: The biggest UNIX security Loophole,
>> > 11217-840302-04TM, AT&T Bell Laboratories, Murray Hill, NJ (1984)"?
>> >
>> > Years ago, in another lifetime, I wrote and asked him for a copy, but
>> > never got a reply.
>> >
>> > --
>> > ``The lyf so short, the craft so long to lerne.'' - Chaucer
>> >                  ``Ars longa, vita brevis'' - Hippocrates
>> > Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Chet Ramey via TUHS]

[-- Attachment #1.1: Type: text/plain, Size: 435 bytes --]

On 1/1/25 10:05 PM, Douglas McIlroy wrote:
> I think $IFS ranks at the top of Jim's cabinet of horrors.

Well, the Bourne shell's combination of importing IFS from the environment
and then using it to split all words was particularly lethal.

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
		 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 203 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Chet Ramey via TUHS]

[-- Attachment #1.1: Type: text/plain, Size: 787 bytes --]

On 1/1/25 1:11 PM, Rik Farrow wrote:
> I wonder what Reeds meant. I know there are issues.

I've wondered myself. I am curious how many of these issues POSIX
addresses (and bash, too, of course).

> For example, the 3B2 I 
> administered for a while in the late 80s had multiple accounts with rsh, 
> the restricted shell, as the login shell. That was okay, unless you used su 
> and then had access to a root shell.

That's an administrator problem. Part of setting up a restricted shell
environment is creating a directory of necessary binaries and setting
PATH appropriately.

Chet
-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
		 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 203 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Rik Farrow]

[-- Attachment #1: Type: text/plain, Size: 975 bytes --]

On Thu, Jan 2, 2025 at 7:23 AM Chet Ramey <chet.ramey@case.edu> wrote:

> On 1/1/25 1:11 PM, Rik Farrow wrote:
> > For example, the 3B2 I
> > administered for a while in the late 80s had multiple accounts with rsh,
> > the restricted shell, as the login shell. That was okay, unless you used
> su
> > and then had access to a root shell.
>
> That's an administrator problem. Part of setting up a restricted shell
> environment is creating a directory of necessary binaries and setting
> PATH appropriately.
>
> Each of these special accounts did have a home directory with a .profile
to set up the restricted environment, then run a shell script to perform
some task as root. For example, logging in as 'backup' would run
/user/backup/.profile and allow a non-privileged user to run a backup
script as root.

But typing "su backup" produced a root-owner shell without restrictions.
You need to type "su - " to run the account's .profile script.

Rik

[-- Attachment #2: Type: text/html, Size: 1443 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Chet Ramey via TUHS]

[-- Attachment #1.1: Type: text/plain, Size: 1389 bytes --]

On 1/2/25 1:13 PM, Rik Farrow wrote:
> 
> 
> On Thu, Jan 2, 2025 at 7:23 AM Chet Ramey <chet.ramey@case.edu 
> <mailto:chet.ramey@case.edu>> wrote:
> 
>     On 1/1/25 1:11 PM, Rik Farrow wrote:
>      > For example, the 3B2 I
>      > administered for a while in the late 80s had multiple accounts with
>     rsh,
>      > the restricted shell, as the login shell. That was okay, unless you
>     used su
>      > and then had access to a root shell.
> 
>     That's an administrator problem. Part of setting up a restricted shell
>     environment is creating a directory of necessary binaries and setting
>     PATH appropriately.
> 
> Each of these special accounts did have a home directory with a .profile to 
> set up the restricted environment, then run a shell script to perform some 
> task as root. For example, logging in as 'backup' would run /user/ 
> backup/.profile and allow a non-privileged user to run a backup script as root.
> 
> But typing "su backup" produced a root-owner shell without restrictions. 
> You need to type "su - " to run the account's .profile script.

OK, I thought you meant the other way, breaking out of a restricted
environment.

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
		 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 203 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 564 bytes --]

I have sent a copy to Warren for the Unix archives.

Doug

On Sat, Dec 28, 2024 at 9:54 PM Royce Williams <royce@techsolvency.com> wrote:
>
> Someone I know is seeking the original version of an internal Bell Labs memo from 1974 titled "Webster's Second on the Head of a Pin" by Morris and Thompson. The topic appears to be related to improving the speed of lookups or search. It's cited in a few papers as "Unpublished Technical Memo, Bell Laboratories, Murray Hill, NJ 1974." All I can find online is citations. Any leads appreciated!
>
> --
> Royce

[-- Attachment #2: PinheadWebster.pdf --]
[-- Type: application/pdf, Size: 5881080 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[James Johnston]

[-- Attachment #1: Type: text/plain, Size: 860 bytes --]

Doug, do you know how much better Ziv-Lempel does? I'm guessing "a little
bit"?

On Mon, Mar 10, 2025 at 3:52 PM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

> I have sent a copy to Warren for the Unix archives.
>
> Doug
>
> On Sat, Dec 28, 2024 at 9:54 PM Royce Williams <royce@techsolvency.com>
> wrote:
> >
> > Someone I know is seeking the original version of an internal Bell Labs
> memo from 1974 titled "Webster's Second on the Head of a Pin" by Morris and
> Thompson. The topic appears to be related to improving the speed of lookups
> or search. It's cited in a few papers as "Unpublished Technical Memo, Bell
> Laboratories, Murray Hill, NJ 1974." All I can find online is citations.
> Any leads appreciated!
> >
> > --
> > Royce
>


-- 
James D. (jj) Johnston

Former Chief Scientist, Immersion Networks

[-- Attachment #2: Type: text/html, Size: 1462 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Douglas McIlroy]

Gnu lzip -9  got a 3.92 compression factor , while Morris-Thompson got 4.52.

According to the lzip man page, lzip has integrity checks, which must
take some space. It is also said to be a "simplified" L-Z, though the
only simplification that is mentioned--bounding the size of the
dictionary--can only happen on much bigger files than Webster. If you
still wonder how well "pure" L-Z does, I'll be happy to try your
favorite implementation.

 It did not surprise me that lzip lost to M-T, for it has to discover
over and over again that the dictionary is lexicographically
ordered--a fact that gives M-T most of its leverage. The dictionary is
definitely not generated by a Markov process!

Doug

On Mon, Mar 10, 2025 at 6:56 PM James Johnston <audioskeptic@gmail.com> wrote:
>
> Doug, do you know how much better Ziv-Lempel does? I'm guessing "a little bit"?
>
> On Mon, Mar 10, 2025 at 3:52 PM Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
>>
>> I have sent a copy to Warren for the Unix archives.
>>
>> Doug
>>
>> On Sat, Dec 28, 2024 at 9:54 PM Royce Williams <royce@techsolvency.com> wrote:
>> >
>> > Someone I know is seeking the original version of an internal Bell Labs memo from 1974 titled "Webster's Second on the Head of a Pin" by Morris and Thompson. The topic appears to be related to improving the speed of lookups or search. It's cited in a few papers as "Unpublished Technical Memo, Bell Laboratories, Murray Hill, NJ 1974." All I can find online is citations. Any leads appreciated!
>> >
>> > --
>> > Royce
>
>
>
> --
> James D. (jj) Johnston
>
> Former Chief Scientist, Immersion Networks

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Jeff Johnson]

As far as getting maximum compression from lzip, `lzip -9 -s 512Mi`
is usually the preferred invocation.  I think the default dictionary
size at -9 is 64MiB, but that's not that relevant I guess, unless
we are comparing different methods and trying to see about what
ratios different algorithms get at similar memory usage.  

--
Jeffrey H. Johnson
trnsz@pobox.com

On Mon, Mar 10, 2025, at 8:23 PM, Douglas McIlroy wrote:
> Gnu lzip -9  got a 3.92 compression factor , while Morris-Thompson got 4.52.

--
Jeffrey H. Johnson
trnsz@pobox.com

On Mon, Mar 10, 2025, at 8:23 PM, Douglas McIlroy wrote:
> Gnu lzip -9  got a 3.92 compression factor , while Morris-Thompson got 4.52.

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 981 bytes --]

Thanks for the advice. I somehow had inferred from the man page that 512M
was the default. In any event, it doesn't move the needle on compression
ratio.

Doug

On Tue, Mar 11, 2025 at 10:47 AM Jeff Johnson <trnsz@pobox.com> wrote:

> As far as getting maximum compression from lzip, `lzip -9 -s 512Mi`
> is usually the preferred invocation.  I think the default dictionary
> size at -9 is 64MiB, but that's not that relevant I guess, unless
> we are comparing different methods and trying to see about what
> ratios different algorithms get at similar memory usage.
>
> --
> Jeffrey H. Johnson
> trnsz@pobox.com
>
> On Mon, Mar 10, 2025, at 8:23 PM, Douglas McIlroy wrote:
> > Gnu lzip -9  got a 3.92 compression factor , while Morris-Thompson got
> 4.52.
>
> --
> Jeffrey H. Johnson
> trnsz@pobox.com
>
> On Mon, Mar 10, 2025, at 8:23 PM, Douglas McIlroy wrote:
> > Gnu lzip -9  got a 3.92 compression factor , while Morris-Thompson got
> 4.52.
>

[-- Attachment #2: Type: text/html, Size: 1453 bytes --]

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Warren Toomey via TUHS]

On Sat, Dec 28, 2024 at 05:53:48PM -0900, Royce Williams wrote:
>    Someone I know is seeking the original version of an internal Bell Labs
>    memo from 1974 titled "Webster's Second on the Head of a Pin" by Morris
>    and Thompson. The topic appears to be related to improving the speed of
>    lookups or search. It's cited in a few papers as "Unpublished Technical
>    Memo, Bell Laboratories, Murray Hill, NJ 1974." All I can find online
>    is citations. Any leads appreciated!

Doug McIlroy sent me a copy, it's now here:

https://www.tuhs.org/Archive/Documentation/TechReports/Bell_Labs/PinheadWebster.pdf

Thanks Doug!

	Warren

[TUHS] Re: "Webster's Second on the Head of a Pin"?

[Royce Williams]

[-- Attachment #1: Type: text/plain, Size: 1859 bytes --]

On Sun, Dec 29, 2024 at 3:37 PM Warren Toomey <wkt@tuhs.org> wrote:

> On Sat, Dec 28, 2024 at 05:53:48PM -0900, Royce Williams wrote:
> >    Someone I know is seeking the original version of an internal Bell
> Labs
> >    memo from 1974 titled "Webster's Second on the Head of a Pin" by
> Morris
> >    and Thompson. The topic appears to be related to improving the speed
> of
> >    lookups or search. It's cited in a few papers as "Unpublished
> Technical
> >    Memo, Bell Laboratories, Murray Hill, NJ 1974." All I can find online
> >    is citations. Any leads appreciated!
>
> Doug McIlroy sent me a copy, it's now here:
>
>
> https://www.tuhs.org/Archive/Documentation/TechReports/Bell_Labs/PinheadWebster.pdf
>
> Thanks Doug!
>

And many thanks from me and my colleague as well, Doug!

For future searchers, what follows is selected (unique) front matter from
the memo, rewrapped slightly for Mailman width.


Title - Webster's Second on the Head of a Pin
Date - July 15, 1974
TM - 74-1271-13

Other keywords - words, text compression

Author Location Extension
Robert Morris MH 2C-524 3878
Ken Thompson MH 2C-523 2394

Charging case - 39199
Filing Case - 39199-11


ABSTRACT

We used the list of words from Webster's Second Unabridged Dictionary
(without definitions) as a test case for special purpose text
compression techniques.

We compressed it by a factor of 4.52 to 1.

The 234,932 words originally occupied 2,486,781 bytes and were
compressed into 549,388 bytes. The size of the decoding program is
1356 bytes.

The initial characters of a word that agreed with the initial
characters of the previous word were dropped and replaced by a code.
Common suffixes were also coded. Finally, a variable-length code was
used.


Pages Text    6    Other   0    Total   6


-- 
Royce

[-- Attachment #2: Type: text/html, Size: 2641 bytes --]