paper2

Best algorithm for LZW ..C language

Given time, a cautious virus will slowly but steadily spread throughout a
computer system.
A hasty one is much more likely to be discovered.
(Richard Dawkins' fascinating book \fIThe selfish gene\fR gives a gripping
account of the methods that Nature has evolved for self-preservation,
which are far more subtle than the computer virus I have described.
Perhaps this bodes ill for computer security in the future.)
.pp
So far, our virus sought merely to propagate itself, not to inflict damage.
But presumably its perpetrator had some reason for planting it.
Maybe they wanted to read a file belonging to some particular person.
Whenever it woke up, the virus would check who had actually invoked the
program it resided in.
If it was the unfortunate victim \(em bingo, it would spring into action.
Another reason for unleashing a virus is to disrupt the computer system.
Again, this is best done slowly.
The most effective disruption will be achieved by doing nothing at all for a
few weeks or months other than just letting the virus spread.
It could watch a certain place on disk for a signal to start doing damage.
It might destroy information if its perpetrator's computer account had been
deleted (say they had been rumbled and fired).
Or the management might be held to ransom.
Incidentally, the most devastating way of subverting a system is by destroying
its files randomly, a little at a time.
Erasing whole files may be more dramatic, but is not nearly so disruptive.
Contemplate the effect of changing a random bit on the disk every day!
.rh "Experience with a virus."
Earlier I said ``Imagine''.
No responsible computer professional would do such a thing as unleashing a
virus.
Computer security is not a joke.
Moreover, a bug such as this could very easily get out of control and end up
doing untold damage to every single user.
.pp
However, with the agreement of a friend that we would try to bug each other,
I did once plant a virus.
Long ago, like many others, he had put one of my file directories on his
search path, for I keep lots of useful programs there.
(It is a tribute to human trust \(em or foolishness? \(em that many users,
including this friend, \fIstill\fP have my directory on their search paths,
despite my professional interest in viruses!)  \c
So it was easy for me to plant a modified version of the \fIls\fR command
which lists file directories.
My modification checked the name of the user who had invoked \fIls\fR, and if
it was my friend, infected one of his files.
Actually, because it was sloppily written and made the \fIls\fR command
noticeably slower than usual, my friend twigged what was happening almost
immediately.
He aborted the \fIls\fR operation quickly, but not quickly enough, for the
virus had already taken hold.
Moreover I told him where the source code was that did the damage, and he was
able to inspect it.
Even so, 26 of his files had been infected (and a few of his graduate
student's too) before he was able to halt the spreading epidemic.
.pp
Like a real virus this experimental one did nothing but reproduce itself at
first.
Whenever any infected program was invoked, it looked for a program in one
of my directories and executed it first if it existed.
Thus I was able to switch on the ``sabotage'' part whenever I wanted.
But my sabotage program didn't do any damage.
Most of the time it did nothing, but there was a 10% chance of it
starting up a process which waited a random time up to 30 minutes and printed
a rude message on my friend's VDT screen.
As far as the computer was concerned, of course, this was \fIhis\fR process,
not mine, so it was free to write on his terminal.
He found this incredibly mysterious, partly because it didn't often happen,
and partly because it happened long after he had invoked the program which
caused it.
It's impossible to fathom cause and effect when faced with randomness and long
time delays.
.pp
In the end, my friend found the virus and wiped it out.
(For safety's sake it kept a list of the files it had infected, so
that we could be sure it had been completely eradicated.)  \c
But to do so he had to study the source code I had written for the virus.
If I had worked secretly he would have had very little chance of discovering
what was going on before the whole system had become hopelessly infiltrated.
.rh "Exorcising a virus."
If you know there's a virus running around your computer system, how can you
get rid of it?
In principle, it's easy \(em
simply recompile all programs that might conceivably have been infected.
Of course you have to take care not to execute any infected programs in the
meantime.
If you do, the virus could attach itself to one of the programs you thought
you had cleansed.
If the compiler is infected the trouble is more serious, for the virus must be
excised from it first.
Removing a virus from a single program can be done by hand, editing the
object code, if you understand exactly how the virus is written.
.pp
But is it really feasible to recompile all programs at the same time?
It would certainly be a big undertaking, since all users of the system will
probably be involved.
Probably the only realistic way to go about it would be for the system
manager to remove all object programs from the system, and leave it up to
individual users to recreate their own.
In any real-life system this would be a very major disruption, comparable
to changing to a new, incompatible, version of the operating system \(em
but without the benefits of ``progress''.
.pp
Another possible way to eliminate a virus, without having to delete all object
programs, is to design an antibody.
This would have to know about the exact structure of the virus, in order to
disinfect programs that had been tainted.
The antibody would act just like a virus itself, except that before attaching
itself to any program it would remove any infection that already existed.
Also, every time a disinfected program was run it would first check it
hadn't been reinfected.
Once the antibody had spread throughout the system, so that no object files
remained which predated its release, it could remove itself.
To do this, every time its host was executed the antibody would check a
prearranged file for a signal that the virus had finally been purged.
On seeing the signal, it would simply remove itself from the object file.
.pp
Will this procedure work?
There is a further complication.
Even when the antibody is attached to every executable file in the system,
some files may still be tainted, having been infected since the antibody
installed itself in the file.
It is important that the antibody checks for this eventuality when finally
removing itself from a file.
But wait!  \(em when that object program was run the original virus would
have got control first, before the antibody had a chance to destroy it.
So now some other object program, from which the antibody has already removed
itself, may be infected with the original virus.
Oh no!
Setting a virus to catch a virus is no easy matter.
.sh "Surviving recompilation: the ultimate parasite"
.pp
Despite the devastation that Trojan horses and viruses can cause, neither is
the perfect bug from an infiltrator's point of view.
The trouble with a Trojan horse is that it can be seen in the source code.
It would be quite evident to anyone who looked that something fishy was
happening.
Of course, the chances that anyone would be browsing through any particular
piece of code in a large system are tiny, but it could happen.
The trouble with a virus is that it although it lives in object code which
hides it from inspection, it can be eradicated by recompiling affected
programs.
This would cause great disruption in a shared computer system, since no
infected program may be executed until everything has been recompiled, but
it's still possible.
.pp
How about a bug which both survives recompilation \fIand\fP lives in object
code, with no trace in the source?
Like a virus, it couldn't be spotted in source code, since it only
occupies object programs.
Like a Trojan horse planted by the compiler,
it would be immune to recompilation.
Surely it's not possible!
.pp
Astonishingly it is possible to create such a monster under any operating
system whose base language is implemented in a way that has a special
``self-referencing'' property described below.
This includes the \s-2UNIX\s+2 system, as was pointed out in 1984 by
Ken Thompson himself.
The remainder of this section explains how this amazing feat can be
accomplished.
Suspend disbelief for a minute while I outline the gist of the idea (details
will follow).
.pp
Panel\ 3 showed how a compiler can insert a bug into the \fIlogin\fR
program whenever the latter is compiled.
Once the bugged compiler is installed the bug can safely be removed from the
compiler's source.
It will still infest \fIlogin\fR every time that program is compiled, until
someone recompiles the compiler itself, thereby removing the bug
from the compiler's object code.
Most modern compilers are written in the language they compile.
For example, C compilers are written in the C language.
Each new version of the compiler is compiled by the previous version.
Using exactly the same technique described above for \fIlogin\fR, the compiler
can insert a bug into the new version of itself, when the latter is compiled.
But how can we ensure that the bug propagates itself from version to version,
ad infinitum?
Well, imagine a bug that \fIreplicates\fR itself.
Whenever it is executed, it produces a new copy of itself.
That is just like having a program that, when executed, prints itself.
It may sound impossible but in fact is not difficult to write.
.pp
Now for the details.
Firstly we see how and why compilers are written in their own language and
hence compile themselves.
Then we discover how programs can print themselves.
Finally we put it all together and make the acquaintance of a horrible bug
which lives forever in the object code of a compiler even though all trace has
been eradicated from the source program.
.rh "Compilers compile themselves!"
Most modern programming languages implement their own compiler.
Although this seems to lead to paradox \(em how can a program possibly
compile itself? \(em it is in fact a very reasonable thing to do.
.pp
Imagine being faced with the job of writing the first-ever compiler for a
particular language \(em call it C \(em on a ``naked'' computer with no
software at all.
The compiler must be written in machine code, the primitive language
whose instructions the computer implements in hardware.
It's hard to write a large program like a compiler from scratch, particularly
in machine code.
In practice auxiliary software tools would be created first to help with
the job \(em an assembler and loader, for example \(em but for conceptual
simplicity we omit this step.
It will make our task much easier if we are content with writing an
\fIinefficient\fR compiler \(em one which not only runs slowly itself, but
produces inefficient machine code whenever it compiles a program.
.pp
Suppose we have created the compiler, called v.0 (version 0), but now want a
better one.
It will be much simpler to write the new version, v.1, in the language being
compiled rather than in machine code.
For example, C compilers are easier to write in C than in machine code.
When it compiles a program, v.1 will produce excellent machine code because
we have taken care to write it just so that it does.
Unfortunately, in order to run v.1 it has to be compiled into
machine code by the old compiler, v.0.
Although this works all right, it means that v.1 is rather slow.
It produces good code, but it takes a long time to do it.
Now the final step is clear.
Use the compiled version of v.1 \fIon itself\fR.
Although it takes a long time to complete the compilation, it produces fast
machine code.
But this machine code is itself a compiler.
It generates good code (for it is just a machine code version of the v.1
algorithm) \fIand it runs fast\fR for it has been compiled by the v.1
algorithm!
Figure\ 7 illustrates the process.
.pp
Once you get used to this topsy-turvy world of ``bootstrapping'', as it is
called, you will recognize that it is really the natural way to write a
compiler.
The first version, v.0, is a throwaway program written in machine code.
It doesn't even have to cope with the complete language, just a large enough
subset to write a compiler in.
Once v.1 has been compiled, and has compiled itself, v.0 is no longer of any
interest.
New versions of the compiler source \(em v.2, v.3, ... \(em will be
modifications of v.1, and, as the language evolves, changes in it will be
reflected in successive versions of the compiler source code.
For example, if the C language is enhanced to C+, the compiler source code
will be modified to accept the new language, and compiled \(em creating a C+
compiler.
Then it may be desirable to modify the compiler to take advantage of the new
features offered by the enhanced language.
Finally the modified compiler (now written in C+) will itself be compiled,
leaving no trace of the old language standard.
.rh "Programs print themselves!"
The next tool we need is reproduction.
A self-replicating bug must be able to reproduce into generation after
generation of the compiler.
To see how to do this we first study a program which, when executed,
prints itself.
.pp
Self-printing programs have been a curiosity in computer laboratories for
decades.
On the face of it it seems unlikely that a program could print itself.
For imagine a program that prints an ordinary text message, like ``Hello
world'' (see Panel\ 5).
It must include that message somehow.
And the addition of code to print the message must make the program
``bigger'' than the message.
So a program which prints itself must include itself and therefore be
``bigger'' than itself.