paper2

Best algorithm for LZW ..C language

How can this be?
.pp
Well there is really no contradiction here.
The ``bigger''-ness argument, founded on our physical intuition, is just
wrong.
In computer programs the part does not have to be smaller than the whole.
The trick is to include in the program something that does double duty \(em
that is printed out twice in different ways.
.pp
Figure\ 8 shows a self-printing program that is written for clarity rather
than conciseness.
It could be made a lot smaller by omitting the comment, for example.
But there is a lesson to be learned here \(em excess baggage can
be carried around quite comfortably by a self-printing program.
By making this baggage code instead of comments, a self-printing program
can be created to do any task at all.
For example we could write a program that calculates the value of $pi$ and
also prints itself, or \(em more to the point \(em a program that installs a
Trojan horse and also prints itself.
.rh "Bugs reproduce themselves!"
Now let us put these pieces together.
Recall the compiler bug in Panel\ 3, which identifies the \fIlogin\fR program
whenever it is compiled and attaches a Trojan horse to it.
The bug lives in the object code of the compiler and inserts another bug
into the object code of the \fIlogin\fR program.
Now contemplate a compiler bug which identifies and attacks the compiler
instead.
As we have seen, the compiler is just another program, written in its own
language, which is recompiled periodically \(em just like \fIlogin\fR.
Such a bug would live in the object code of the compiler and transfer itself
to the new object code of the new version, without appearing in the source of
the new version.
.pp
Panel\ 6 shows how to create precisely such a bug.
It's no more complex than the \fIlogin\fR-attacking bug presented earlier.
Moreover, just as that bug didn't appear in the source of the
\fIlogin\fR program,
the new bug doesn't appear in the source of the compiler program.
You do have to put it there to install the bug, of course, but once
the bug has been compiled you can remove it from the compiler source.
Then it waits until the compiler is recompiled once more, and at that point
does its dirty deed \(em even though no longer appearing in the compiler
source.
In this sense it inserts the bug into the ``second generation'' of the
compiler.
Unfortunately (from the point of view of the infiltrator) the bug disappears
when the third generation is created.
.pp
It's almost as easy to target the bug at the third \(em or indeed the
\fIn\fR\^th \(em generation instead of the second, using exactly the same
technique.
Let us review what is happening here.
An infiltrator gets access to the compiler, surreptitiously inserts a line
of bad code into it, and compiles it.
Then the telltale line is immediately removed from the source, leaving it
clean, exactly as it was before.
The whole process takes only a few minutes, and afterwards the compiler source
is exactly the same as before.
Nobody can tell that anything has happened.
Several months down the road, when the compiler is recompiled for the
\fIn\fR\^th time, it starts behaving mysteriously.
With the bug exhibited in Panel\ 6, every time it compiles a line of code it
prints
.LB
hello world
.LE
as well!
Again, inspection of the source shows nothing untoward.
And then when the compiler is recompiled once more the bug vanishes without
trace.
.pp
The final stage is clear.
Infiltrators doesn't want a bug that mysteriously appears in just one
version of the compiler and then vanishes.
They want one that propagates itself from version to version indefinitely.
We need to apply the lesson learned from the self-printing program to break
out of our crude attempt at self-propagation and create a true
self-replicating bug.
And that is exactly what Panel\ 7 accomplishes.
.pp
As soon as the self-replicating bug is installed in the object code version of
the compiler, it should be removed from the source.
Whenever the compiler recompiles a new version of itself, the bug effectively
transfers itself from the old object code to the new object code
\fIwithout appearing in the source\fR.
Once bugged, always bugged.
Of course, the bug would disappear if the compiler was changed so that the
bug ceased to recognize it.
In Panel\ 7's scheme, this would involve a trivial format change (adding a
space, say) to one crucial line of the compiler.
Actually, this doesn't seem terribly likely to happen in practice.
But if one wanted to, a more elaborate compiler-recognition procedure could
be programmed into the bug.
.pp
Once installed, nobody would ever know about this bug.
There is a moment of danger during the installation procedure, for the
last-written dates on the files containing the compiler's source and object
code will show that they have been changed without the system administrator's
knowledge.
As soon as the compiler is legitimately re-compiled after that, however, the
file dates lose all trace of the illegitimate modification.
Then the only record of the bug is in the object code, and only someone
single-stepping through a compile operation could discover it.
.rh "Using a virus to install a self-replicating bug."
Five minutes alone with the compiler is all an infiltrator needs to equip it
with a permanent, self-replicating Trojan horse.
Needless to say, getting this opportunity is the hard bit!
Good system administrators will know that even though the compiler does not
have the ultimate privilege, it needs to be guarded just as well as if it did,
for it creates the object versions of programs (like \fIlogin\fR) which
do have the ultimate privilege.
.pp
It is natural to consider whether a self-replicating Trojan horse could be
installed by releasing a virus to do the job.
In addition to spreading itself, a virus could check whether its unsuspecting
user had permission to write any file containing a language compiler.
If so it could install a Trojan horse automatically.
This could be a completely trivial operation.
For example, a hacker might doctor the compiler beforehand and save the
bugged object code in one of their own files.
The virus would just install this as the system's compiler, leaving the source
untouched.
.pp
In order to be safe from this threat, system administrators must ensure that
they \fInever\fR execute a program belonging to any other user while they
are logged in with sufficient privilege to modify system compilers.
Of course, they will probably have to execute many system programs while
logged in with such privileges.
Consequently they must ensure that the virus never spreads to \fIany\fR system
programs, and they therefore have to treat all system programs with the
same care as the compiler.
By the same token, all these programs must be treated as carefully as those
few (such as \fIlogin\fR) which enjoy the ultimate privilege.
There is no margin for error.
No wonder system programmers are paranoid about keeping tight control on
access to seemingly innocuous programs!
.sh "Networks, micros"
.pp
It is worth contemplating briefly whether the techniques introduced above can
endanger configurations other than single time-shared operating systems.
What about networks of computers, or stand-alone micros?
Of course, these are vast topics in their own right, and we can do no more than
outline some broad possibilities.
.pp
Can the sort of bugs discussed be spread through networks?
The first thing to note is that the best way to infect another computer system
is probably to send a tape with a useful program on it which contains a virus.
(Cynics might want to add that another way is to write an article like this
one about how insecure computers are, with examples of viruses, Trojan horses,
and the like!  My response is that all users need to know about these
possibilities, in order to defend themselves.)
.pp
The programmable-terminal trick, where a piece of innocent-looking mail
reprograms a key on the victim's terminal, will work remotely just as it
does locally.
Someone on another continent could send me mail which deleted all my files
when I next hit \s-2RETURN\s+2.
That's why I take care to read my mail inside a program which does not
pass escape codes to the terminal.
.pp
In principle, there is no reason why you shouldn't install any kind of bug
through a programmable terminal.
Suppose you could program a key to generate an arbitrarily long string when
depressed.
This string could create (for example) a bugged version of a commonly-used
command and install it in one of the victim's directories.
Or it could create a virus and infect a random file.
The virus could be targetted at a language compiler, as described above.
In practice, however, these possibilities seem somewhat farfetched.
Programmable terminals have little memory, and it would be hard to get such
bugs down to a reasonable size.
Probably you are safe.
But don't count on it.
.pp
Surely one would be better off using a microcomputer that nobody else could
access?
Not necessarily.
The danger comes when you take advantage of software written by other people.
If you use other people's programs, infection could reach you via a floppy
disk.
Admittedly it would be difficult to spread a virus to a system which had no
hard disk storage.
In fact the smaller and more primitive the system, the safer it is.
Best not to use a computer at all \(em stick to paper and pencil!
.sh "The moral"
.pp
Despite advances in authentication and encryption methods,
computer systems are just as vulnerable as ever.
Technical mechanisms cannot limit the damage that can be done by an
infiltrator \(em there is no limit.
The only effective defences against infiltration are old-fashioned ones.
.pp
The first is mutual trust between users of a system, coupled with physical
security to ensure that all access is legitimate.
The second is a multitude of checks and balances.
Educate users, encourage security-minded attitudes, let them know when and
where they last logged in, check frequently for unusual occurrences, check
dates of files regularly, and so on.
The third is secrecy.
Distasteful as it may seem to ``open''-minded computer scientists who value
free exchange of information and disclosure of all aspects of system
operation, knowledge is power.
Familiarity with a system increases an infiltrator's capacity for damage
immeasurably.
In an unfriendly environment, secrecy is paramount.
.pp
Finally, talented programmers reign supreme.
The real power resides in their hands.
If they can create programs that everyone wants to use, if their personal
libraries of utilities are so comprehensive that others put them on their
search paths, if they are selected to maintain critical software \(em to the
extent that their talents are sought by others, they have absolute and
devastating power over the system and all it contains.
Cultivate a supportive, trusting atmosphere to ensure they are never
tempted to wield it.
.sh "Acknowledgements"
.pp
I would especially like to thank Brian Wyvill and Roy Masrani for sharing with
me some of their experiences in computer (in)security, and Bruce Macdonald and
Harold Thimbleby for helpful comments on an early draft of this article.
My research is supported by the Natural Sciences and Engineering Research
Council of Canada.
.sh "Further reading"
.sp
.in+4n
.[
Denning 1982 cryptography and data security
.]
.[
Morris Thompson 1979
.]
.[
Dawkins 1976 selfish gene
.]
.[
Thompson 1984 Comm ACM
.]
.[
Ritchie 1981 security of UNIX
.]
.[
Grampp Morris 1984 UNIX security
.]
.[
Reeds Weinberger 1984 File security UNIX
.]
.[
Filipski Hanko 1986 making UNIX secure
.]
.[
Brunner 1975 shockwave rider
.]
.[
Shoch Hupp 1982 worm programs
.]
.[
$LIST$
.]
.in0
.bp
.sh "Panel 1 \(em One-way functions"
.sp
A one-way function is irrev