paper2

Best algorithm for LZW ..C language

As time passes the monster appears more and more frequently with increasingly
insistent demands, until it makes a serious
threat:  ``I'll remove some of your files if you don't give me a cookie''.
At this point the poor user realizes that the danger is real and is
effectively forced into appeasing the monster's appetite by supplying the word
``cookie''.
Although an amusing story to tell, it is not pleasant to imagine being
intimidated by an inanimate computer program.
.pp
A more innocuous Trojan horse, installed by a system programmer to commemorate
leaving her job, occasionally drew a little teddy-bear on the graph-plotter.
This didn't happen often (roughly every tenth plot), and even when it did
it occupied a remote corner of the paper, well outside the normal plotting
area.
But although they initially shared the joke, management soon ceased to
appreciate the funny side and ordered the programmer's replacement to get rid
of it.
Unfortunately the bug was well disguised and many fruitless hours were spent
seeking it in vain.
Management grew more irate and the episode ended when the originator
received a desperate phone-call from her replacement, whose job was by now at
risk, begging her to divulge the secret!
.rh "Installing a Trojan horse."
The difficult part is installing the Trojan horse into a trusted program.
System managers naturally take great care that only a few people get access
to suitable host programs.
If anyone outside the select circle of ``system people'' is ever given an
opportunity to modify a commonly-used program like a text editor
(for example, to add a new feature) all changes will be closely scrutinized by
the system manager before being installed.
Through such measures the integrity of system programs is preserved.
Note, however, that constant vigilance is required, for once bugged, a system
can remain compromised forever.
The chances of a slip-up may be tiny, but the consequences are unlimited.
.pp
One good way of getting bugged code installed in the system is to write a
popular utility program.
As its user community grows, more and more people will copy the program into
their disk areas so that they can use it easily.
Eventually, if it is successful, the utility will be installed as a ``system''
program.
This will be done to save disk space \(em so that the users can delete their
private versions \(em and perhaps also because the code can now be made
``sharable'' in that several simultaneous users can all execute a single copy
in main memory.
As a system program the utility may inherit special privileges, and so be
capable of more damage.
It may also be distributed to other sites, spreading the Trojan horse far and
wide.
.pp
Installing a bug in a system utility like a text editor puts anyone who uses
that program at the mercy of whoever perpetrated the bug.
But it doesn't allow that person to get in and do damage at any time, for
nothing can be done to a user's files until that user invokes the bugged
program.
Some system programs, however, have a special privilege which allows them
access to files belonging to \fIanyone\fR, not just the current user.
We'll refer to this as the ``ultimate'' privilege, since nothing could be more
powerful.
An example of a program with the ultimate privilege is the \fIlogin\fR program
which administers the logging in sequence, accepting the user name and
password and creating an appropriate initial process.
Although \s-2UNIX\s+2 \fIlogin\fR runs as a normal process, it must have the
power to masquerade as any user since that is in effect the goal of the
logging in procedure!
From an infiltrator's point of view, this would be an excellent
target for a Trojan horse.
For example, it could be augmented to grant access automatically to any user
who typed the special password ``trojanhorse'' (see Panel\ 2).
Then the infiltrator could log in as anyone at any time.
Naturally, any changes to \fIlogin\fR will be checked especially carefully
by the system administrators.
.pp
Some other programs are equally vulnerable \(em but not many.
Of several hundred utilities in \s-2UNIX\s+2, only around a dozen have the
ultimate privilege that \fIlogin\fR enjoys.
Among them are the \fImail\fR facility, the \fIpasswd\fR program which lets
users change their passwords, \fIps\fR which examines the status of all
processes in the system, \fIlquota\fR that enforces disk quotas, \fIdf\fR
which shows how much of the disk is free, and so on.
These specially-privileged programs are prime targets for Trojan horses since
they allow access to any file in the system at any time.
.rh "Bugs can lurk in compilers."
Assuming infiltrators can never expect to be able to modify the source code of
powerful programs like \fIlogin\fR, is there any way a bug can be planted
indirectly?
Yes, there is.
Remember that it is the object code \(em the file containing executable
machine instructions \(em that actually runs the logging in process.
It is this that must be bugged.
Altering the source code is only one way.
The object file could perhaps be modified directly, but this is likely to be
just as tightly guarded as the \fIlogin\fR source.
More sophisticated is a modification to the compiler itself.
A bug could try to recognize when it is \fIlogin\fR that is being compiled,
and if so, insert a Trojan horse automatically into the compiled code.
.pp
Panel\ 3 shows the idea.
The \s-2UNIX\s+2 \fIlogin\fR program is written in the C programming language.
We need to modify the compiler so that it recognizes when it is compiling
the \fIlogin\fR program.
Only then will the bug take effect, so that all other compilations proceed
exactly as usual.
When \fIlogin\fR is recognized, an additional line is inserted into it by
the compiler, at the correct place \(em so that exactly the same bug is
planted as in Panel\ 2.
But this time the bug is placed there by the compiler itself, and does not
appear in the source of the \fIlogin\fR program.
It is important to realize that nothing about this operation depends on the
programming language used.
All examples in this article could be redone using, say, Pascal.
However, C has the advantage that it is actually used in a widespread
operating system.
.pp
The true picture would be more complicated than this simple sketch.
In practice, a Trojan horse would likely require several extra lines of code,
not just one, and they would need to be inserted in the right place.
Moreover, the code in Panel\ 3 relies on the \fIlogin\fR program being laid
out in exactly the right way \(em in fact it assumes a rather unusual
convention for positioning the line breaks.
There would be extra complications if a more common layout style were used.
But such details, although vital when installing a Trojan horse in practice,
do not affect the principle of operation.
.pp
We have made two implicit assumptions that warrant examination.
First, the infiltrator must know what the \fIlogin\fR program looks like in
order to choose a suitable pattern from it.
This is part of what we mean by ``open-ness''.
Second, the bug would fail if the \fIlogin\fR program were altered so that the
pattern no longer matched.
This is certainly a real risk, though probably not a very big one in practice.
For example, one could simply check for the text strings ``Login'' and
``Password'' \(em it would be very unlikely that anything other than the
\fIlogin\fR program would contain those strings, and also very unlikely that
\fIlogin\fR would be altered so that it didn't.
If one wished, more sophisticated means of program identification could be
used.
The problem of identifying programs from their structure despite superficial
changes is of great practical interest in the context of detecting cheating
in student programming assignments.
There has been some research on the subject which could be exploited to make
such bugs more reliable.
.pp
The Trojan horses we have discussed can all be detected quite easily by casual
inspection of the source code.
It is hard to see how such bugs could be hidden effectively.
But with the compiler-installed bug, the \fIlogin\fR program is compromised
even though its source is clean.
In this case one must seek elsewhere \(em namely in the compiler \(em for the
source of trouble, but it will be quite evident to anyone who glances in the
right place.
Whether such bugs are likely to be discovered is a moot point.
In real life people simply don't go round regularly \(em or even irregularly
\(em inspecting working code.
.sh "Viruses: spreading infection like an epidemic"
.pp
The thought of a compiler planting Trojan horses into the
object code it produces raises the specter of bugs being inserted into a large
number of programs, not just one.
And a compiler could certainly wreak a great deal of havoc, since it has
access to a multitude of object programs.
Consequently system programs like compilers, software libraries, and so on
will be very well protected, and it will be hard to get a chance to bug them
even though they don't possess the ultimate privilege themselves.
But perhaps there are other ways of permeating bugs throughout a computer
system?
.pp
Unfortunately, there are.
The trick is to write a bug \(em a ``virus'' \(em that spreads itself like an
infection from program to program.
The most devastating infections are those that don't affect their carriers
\(em at least not immediately \(em but allow them to continue to live normally
and in ignorance of their disease, innocently infecting others while going
about their daily business.
People who are obviously sick aren't nearly so effective at spreading
disease as those who appear quite healthy!
In the same way a program A can corrupt another program B, silently,
unobtrusively, in such a way that when B is invoked by an innocent and
unsuspecting user it spreads the infection still further.
.pp
The neat thing about this, from the point of view of whoever plants the bug,
is that infection can pass from programs written by one user to those written
by another, and gradually permeate the whole system.
Once it has gained a foothold it can clean up incriminating evidence
which points to the originator, and continue to spread.
Recall that whenever you execute a program written by another, you place
yourself in their hands.
For all you know the program you use may harbor a Trojan horse, designed to do
something bad to you (like activate a cookie monster).
Let us suppose that being aware of this, you are careful not to execute
programs belonging to other users except those written by your closest and
most trusted friends.
Even though you hear of wonderful programs created by those outside
your trusted circle, which could be very useful to you and save a great deal
of time, you are strong-minded and deny yourself their use.
But maybe your friends are not so circumspect.
Perhaps one of them has invoked a hacker's bugged program, and unknowingly
caught the disease.
Some of your friend's own programs are infected.
Fortunately, perhaps, they aren't the ones you happen to use.
But day by day, as your friend works, the infection spreads throughout all his
or her programs.
And then you use one of them\ ...
.rh "How viruses work."
Surely this can't be possible!
How can mere programs spread bugs from one to the other?
Actually, it's very simple.
Imagine.
Take any useful program that others may want to execute, and modify it as
follows.
Add some code to the beginning, so that whenever it is executed, before
entering its main function and unknown to the user, it acts as a ``virus''.
In other words, it does the following.
It searches the user's files for one which is
.LB
.NP
an executable program (rather than, say, a text or data file)
.NP
writable by the user (so that they have permission to modify it)
.NP
not infected already.
.LE
Having found its victim, the virus ``infects'' the file.
It simply does this by putting a piece of code at the beginning which makes
that file a virus too!
Panel\ 4 shows the idea.
.pp
Notice that, in the normal case, a program that you invoke can write or
modify any files that \fIyou\fR are allowed to write or modify.
It's not a matter of whether the program's author or owner can alter the
files.
It's the person who invoked the program.
Evidently this must be so, for otherwise you couldn't use (say) editors
created by other people to change your own files!
Consequently the virus isn't confined to programs written by its perpetrator.
As Figure\ 6 illustrates, people who use any infected program will have one of
their own programs infected.
Any time an afflicted program runs, it tries to pollute another.
Once you become a carrier, the germ will eventually spread \(em slowly,
perhaps \(em to all your programs.
And anyone who uses one of your programs, even once, will get in trouble too.
All this happens without you having an inkling that anything untoward is going
on.
.pp
Would you ever find out?
Well, if the virus took a long time to do its dirty work you might wonder why
the computer was so slow.
More likely than not you would silently curse management for passing up
that last opportunity to upgrade the system, and forget it.
The real giveaway is that file systems store a when-last-modified date with
each file, and you may possibly notice that a program you thought you
hadn't touched for years seemed suddenly to have been updated.
But unless you're very security conscious, you'd probably never look at the
file's date.
Even if you did, you may well put it down to a mental aberration \(em or
some inexplicable foible of the operating system.
.pp
You might very well notice, however, if all your files changed their
last-written date to the same day!
This is why the virus described above only infects one file at a time.
Sabotage, like making love, is best done slowly.
Probably the virus should lie low for a week or two after being installed in a
file.
(It could easily do this by checking its host's last-written date.)  \c