home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Hacker Chronicles 1
/
HACKER1.ISO
/
misc
/
v05i017.txt
< prev
next >
Wrap
Internet Message Format
|
1992-09-27
|
32KB
From: Kenneth R. van Wyk (The Moderator) <krvw@CERT.SEI.CMU.EDU>
Errors-To: krvw@CERT.SEI.CMU.EDU
To: VIRUS-L@IBM1.CC.LEHIGH.EDU
Path: cert.sei.cmu.edu!krvw
Subject: VIRUS-L Digest V5 #17
Reply-To: VIRUS-L@IBM1.CC.LEHIGH.EDU
--------
VIRUS-L Digest Thursday, 30 Jan 1992 Volume 5 : Issue 17
Today's Topics:
Stoned on SafeMBR?? Say it ain't so! (PC)
Re: Stoned on SafeMBR drive (PC)
Help! Ghost Virus! (PC)
Stoned (PC)
CHKDSK and Viruses (PC)
Michelangelo Virus from Verbatim Disks (PC)
Re: QEMM386's LOADHI with VSHIELD1 and/or VIRSTOP (PC)
Boot Sectors Nomenclature (PC)
AUX "file" (PC)
Aircop & Laser? (PC)
Virus, typing '- -' (PC)
Re: Trojan program collects passwords
Re: New Antivirus Organization Announced
Updated FPROT202 on BEACH (PC)
"Commercial safety" myth
Cohen's error
VIRUS-L is a moderated, digested mail forum for discussing computer
virus issues; comp.virus is a non-digested Usenet counterpart.
Discussions are not limited to any one hardware/software platform -
diversity is welcomed. Contributions should be relevant, concise,
polite, etc. (The complete set of posting guidelines is available by
FTP on cert.sei.cmu.edu or upon request.) Please sign submissions
with your real name. Send contributions to VIRUS-L@IBM1.CC.LEHIGH.EDU
(that's equivalent to VIRUS-L at LEHIIBM1 for you BITNET folks).
Information on accessing anti-virus, documentation, and back-issue
archives is distributed periodically on the list. Administrative mail
(comments, suggestions, and so forth) should be sent to me at:
krvw@CERT.SEI.CMU.EDU.
Ken van Wyk
----------------------------------------------------------------------
Date: 27 Jan 92 09:38:30 -0500
From: "Don Medal" <MEDAL@mail.crk.umn.edu>
Subject: Stoned on SafeMBR?? Say it ain't so! (PC)
My computer lab attendants report seeing our old nemisis STONED
reappearing on lab machines (XTs) previously protected with SAFEMBR.
Frankly I don't know whether staff is right or freaking out from to
many virus worries during the night hours. The instances to date have
been "fixed" with CLEAN before I could look at them, and I wonder if
they were not really floppy disk based cases.
Could this be so? (that STONED can infect a SafeMBR protected drive?)
eGad, will this never stop?
[Moderator's Note: See follow-up below.]
Don
- -------------------------------------------------------
Don Medal internet: medal@mail.crk.umn.edu
UMC Computing Services BITNET: dmedal@UMNACVX.BITNET
Univ of Minnesota Crookston voice: (218) 281-6510 ext 432
- -------------------------------------------------------
------------------------------
Date: Tue, 28 Jan 92 15:47:34 -0500
From: padgett%tccslr.dnet@uvs1.orl.mmc.com (A. Padgett Peterson)
Subject: Re: Stoned on SafeMBR drive (PC)
Don:
Sure, STONED can infect a SafeMBR protected drive - SafeMBR
cannot stop someone from booting from a floppy, not can it stop a
booted floppy from writing to the disk. What SafeMBR does is DETECT
the infection and hang the boot if its integrity check fails.
Similarly, you can't prevent a virus from removing SafeMBR by
replacing the entire MBR with itself - AZUSA does this - but then my
logo won't display. What you can do is to put CHKSMBR in the
autoexec.bat - it will return errorlevels depending on whether SafeMBR
is still there you can use in a .BAT file (see the .DOC).
I am sending a uuencoded ZIP of the entire new Fix, Chk, & NoFBoot
package for you to try.
Warmly,
Padgett
ps if you have something that can get by SafeMBR, then it is not the
vanilla STONED - please send me a copy. - app
------------------------------
Date: Mon, 27 Jan 92 15:54:36 +0000
From: smasilam@uokmax.ecn.uoknor.edu (Senthilamudhan Masilamani)
Subject: Help! Ghost Virus! (PC)
I found jeru -A , jeru, and 15xx spread accross a few diskette
originals and on thus on my system. When I put the diskettes(procomm
and MTEZ) into another older model pc and scanned them using the lates
Virusscan(Scan85 i think) , the same version i used earlier to find
the viruses, The viruses were no longer there!! The scan reports the
disks to be clean ! Whats goin on???
Thanks,
smasilam@uokmax.ecn.uoknor.edu
------------------------------
Date: 27 Jan 92 10:50:00 -0500
From: "V70D::HUNTRESS" <HUNTRESS%V70D.decnet@npt.nusc.navy.mil>
Subject: Stoned (PC)
Hi,
I found and cleaned Stoned from my system this weekend (f-prot is
*GREAT*). I have no idea how long it had been resident, and since I
never saw it trigger (never got the message "You have been stoned"), I
started to wonder what causes it to trigger. A date? A number of
boots? Random?
Gary Huntress
huntress@npt.nusc.navy.mil
------------------------------
Date: Mon, 27 Jan 92 15:44:08 -0500
From: padgett%tccslr.dnet@mmc.com (A. Padgett Peterson)
Subject: CHKDSK and Viruses (PC)
From: Josep Fortiana Gregori <UBAESQ01@EBCESCA1.BITNET>
> After reading the note by Padgett Peterson about the
> Michelangelo virus, I checked my machines and found
> that one of them (a 486/33MHz clone AT with 8M ram)
> reports total memory = 654336 = 655360 - 1024 when
> booted from drive C: and 655360 when booted from A:
Actually, there are quite a few things that can cause CHKDSK to return
less than "655,360".
Return of 654336 (note: the memory from 9fc0:0 to 9fc0:3ff will be mostly
nulls (zeros). If full of code not recognized, I become very suspicious).
a) DOS 4.x (ROM BIOS data extension - not used with DOS 5.0)
b) Older Compaqs (buffer for Compaq mouse - 1k can be returned by moving
jumper on motherboard - no, I do not know which one)
c) My DISKSECURE program (not SafeMBR though)
d) A small number of non-stealth (so far) viruses e.g. AIRCOP
Return of 653,312 or less
a) many MBR viruses
b) H/P Vectra (651,264 as I recall)
c) many resident access control programs that promise "no booting from
floppy"
Return of 524,288
PC with 512k memory
Any combination of the above.
Additionally, there are a small number of systems that will report in
excess of 655,360 normally. See "BEST" below.
In short, if I see 655360 on a plain-jane PC, there is a very good chance
that the system does not have a MBR virus - certainly not Aircop, Brain,
Alameda, Azusa, Joshi, Michelangelo, Empire, etc. If less, I want to know
why but there often may be innocent reasons, some of which I have listed
above. The BEST way to use CHKDSK returns is to make a note of what it is
for the PC when known to be clean and to watch for any change.
One way is with my FREEWARE (worth every penny) CHKMEM.COM program. Invoked
with the known size (e.g. CHKMEM 640) it will fall through if ok and halt with
a message if there is a problem. It will not find 100% of all known and
unknown viruses, it will not even find all MBR infections, but it will
find the popular ones that have spread widely. Look it in CHK.ZIP or
FixUtil.ZIP.
Warmly, "back home agaaaaain..."
Padgett
<padgett%tccslr.dnet@mmc.com>
------------------------------
Date: Mon, 27 Jan 92 21:36:23 +0000
From: brabec@pysgjb.physics.ncsu.edu (Charles Brabec)
Subject: Michelangelo Virus from Verbatim Disks (PC)
A friend of mine says his computers at work got infected from a batch
of brand-new Pre-formated Verbatim 1.44Mb disks. I don't have the lot
number, but I figured people ought to know. It would probably be a
good idea to check out ALL preformated disks before using them.
Charles
- --
- --------------------------------------------------------------
Charles Brabec 304 Cox Hall
brabec@pysgjb.physics.ncsu.edu (919) 515-7228
------------------------------
Date: 28 Jan 92 00:58:11 -0500
From: heinicke@uwovax.uwo.ca (Allan Heinicke)
Subject: Re: QEMM386's LOADHI with VSHIELD1 and/or VIRSTOP (PC)
hendee%3338.span@Sdsc.Edu (Jim Hendee) writes:
> I've noticed that you can use Quarterdeck's QEMM386 and LOADHI to load
> VSHIELD1.EXE in high memory, as well as FPROT's VIRSTOP.EXE, but you
> can't load VSHIELD.EXE high (so far as I'm aware). My questions are:
>
> 1) When you load these two small anti-viral programs high, do they still
> work?
Virstop loads high using QEMM (v.5.12 anyway) and detects the F-CHK
virus simulator from the old F-Prot package. Fortunately, I haven't
had a real virus that I know of so I cannot attest that it works.
Be aware however that if you are using Desqview, virstop is not working
inside the DOS windows: to quote from the F-Prot documentation--
VIRSTOP.EXE is not effective if run before a program which totally
takes over the "Load-and-Execute" function. This includes Novell
Netware and PC-NFS, and as explained elsewhere, VIRSTOP should be run
after those programs. However, this also applies to DesqView - which
means that VIRSTOP is not effective inside a DOS window in DesqView.
------------------------------
Date: 28 Jan 92 11:15:14 -0500
From: "Otto.Stolz" <RZOTTO@DKNKURZ1.BITNET>
Subject: Boot Sectors Nomenclature (PC)
Hello,
In contributions to this forum and in various anti-virus software, I
found differing technical terms for the two sorts of boot sectors
found on MS-DOS hard disks. As some of these technical terms may be
regarded misleading, I suggest that we all agree on particular terms
(I'll present below) and try to avoid the misleading terms,
henceforth.
Let me recall the technical facts, first. If you know them already,
you may want to skip to the Summary, below.
If a PC is booted with no diskette in drive A, the BIOS (after some
preliminaries) will read the 1st physical sector from the hard disk into
a fixed location in memory and execute it. This sector contains a boot-
strap program and is only found once on the whole disk; hence it is
widely known as "Master Boot Record (MBR)".
The MBR (after some simple checks) loads another boot sector from the HD
and executes it. This second boot sector is located at the beginning of
the "active partition". If a HD is partitioned into several partitions,
every partition starts with a boot sector, but only one partition can be
the "active" one at any moment, hence only one of those bootstrap pro-
grams is executed during the bootup process. As every partition
contains such boot sector as its 1st (logical) block, we could term them
"Partition Boot Sectors" (I'll explain shortly why I think this is not
a good idea, though).
How does the MBR know where the partions are on the HD and which one
is the active one? Very simple: there is a Partition Table built into
it (somewhere towards its end). Now some authors call the MBR imprecisely
"Partition Table" (and some even "Partition Record"). I suggest to avoid
this terminology for two reasons:
1. It is imprecise: the PT is only part of the MBR.
2. It is misleading: the term PT could all too easy be confused with
the term Partition Boot Record.
Now we even have a /MBR option in an official DOS command, I suggest
everybody should use the term Master Boot Record (MBR) and cease using
any other term for the 1st physical sector of a HD.
After "Partition Table" has been used widely for the MBR (and still
will and should be used to refer to that part of the MBR), I think the
term "Partition Boot Sector" for the 1st logical sector of a partition
(though precise) is too confusing to be regarded as a good term. I
suggest to use the term "DOS Boot Sector" instead, as this sector looks
pretty much the same as the only boot sector on a DOS diskette.
To boot an operating system other than DOS (e.g. Unix or Novell) from a
HD, the active partition contains a "Unix Boot Sector" or a "Novell Boot
Sector" instead of the DOS Boot Sector, while the MBR does not look any
different than on a genuine DOS hard disk. So we could use those terms
for particular operating systems; however, I cannot imagine a suitable
term (other than "Partition Boot Sector") in case you want to avoid
being specific about the particular operating system. Any suggestions?
Summary of the terms suggested:
Master Boot Record (MBR) : The 1st physical sector on a hard disk
**Cease calling it Partition Table|**
DOS Boot Sector : The 1st (logical) sector of a DOS partition on
a hard disk, or the 1st (physical and logical)
sector of a DOS diskette.
(Similar terms to be coined for other
operating systems)
Partition Table : A particular part of the MBR.
**Use this term only when particularaly
referring to this part of the MBR, as opposed
to other parts**
I'd rather see a better term for the following one (suggestions?):
Partition Boot Sector : A genuine term for the 1st (logical) sector of
a partition on a HD, if you do not want to
refer to a particular operating system.
**Try to avoid this term, as some readers will
confuse it with the PT (or even with the MBR,
due to sloppy language in the past)**
Best regards,
Otto Stolz <RZOTTO@DKNKURZ1.Bitnet>
<RZOTTO@nyx.uni-konstanz.de>
------------------------------
Date: 28 Jan 92 17:41:57 -0500
From: Leonard Erickson <70524.2603@CompuServe.COM>
Subject: AUX "file" (PC)
In VIRUS-L V5#15, diaz@leland.stanford.edu (Kathy Diaz) writes:
>I have a question it seems that I have come across some sort of virus.
>My Dos Machine has in every directory a file called aux. It seems also
>that you can't find it by normal means. I guess the best way to find
>it is to use any editor(edlin, edit, vi, etc..) to look at it, but
>what you actually get is a computer freeze.
>
>You could also try to rename a file to aux and you will some sort of
>duplicate file error.
>
>Each aux file is about 112 bytes long.
>It doesn't seem to be malicious aside from taking up space but I can't
>even look in the file and try to dump the contents onto a file or
>something. And scanv85 doesn't find it. Same thing with CPAV. If
>anybody knows something about this all your help will be greatly
>appreciated.
AUX is one of the default *devices* in MS-DOS. It is usually mapped to
COM1:. Like all devices it can be *addressed* as if it were a file. (ie
COPY XYZ AUX)
The 112 bytes (how'd you get that?) is probably the buffer size for AUX.
The list of standard MS-DOS devices follows:
device Input Output
CON yes yes input=keyboard/output=screen
PRN no yes mapped to LPT1
AUX yes yes mapped to COM1
NUL yes yes
LPT1 no yes
LPT2 no yes
LPT3 no yes
LPT4 no yes only exists in recent DOS versions
COM1 yes yes
COM2 yes yes
COM3 yes yes
COM4 yes yes
...
The LPT and COM devices only "exist" if the appropriate hardware exists.
Another surprise is that DOS has a fake *directory* called "dev" (for
device). Try copying some files to \dev\prn for example...
------------------------------
Date: Tue, 28 Jan 92 19:50:51 -0600
From: be215645@uwspmail.uwsp.edu
Subject: Aircop & Laser? (PC)
Greetings,
I recently found the Aircop virus on a friend's computer. She can't
remember using any boot disks except for the ones that came with it. When I
checked it, I only found the virus on 3 disks.
It's a Laser 286/2 VTS that was bought from a discount store around
Sept.-Oct. 1990. Laser included the PC Tools Deluxe program with the
package. I found the virus on these disks:
Laser - Utilities
Laser - DSK HD FORMAT UTILITY (ST)
Central Point/Laser - PC Tools Deluxe Version 6
Disk 1 - PC Setup
Could this have come from Laser? It could have also come from the
discount store. Comments anyone?
Thanks.
=====================================================================
Andy Berkvam | be215645@uwspmail.uwsp.edu
414 Neale Hall | The only thing necessary for the
University of Wisconsin | triumph of evil is for good men
Stevens Point, WI 54481 | to do nothing.
(715) 346-3153 | -Edmund Burke
================================\\//_================================
------------------------------
Date: Tue, 28 Jan 92 20:10:18 -0600
From: <rmikke@mimuw.edu.pl>
Subject: Virus, typing '- -' (PC)
Has anyone heard of the virus on PC, that blanks the screen, and then
starts to type '- -' all over it? Or maybe it writes '_ _' - I
couldn't make sure on the blank screen. It has also crashed a few .EXE
files. I have diskduped suspected diskettes, if anyone wants to have
a look at the beast.
Waiting for any help
Rysiek.
- ------------------------------------------
Ryszard Korwin-Mikke. Internet: rmikke@mimuw.edu.pl
Bitnet: rmikke@plearn
------------------------------
Date: Tue, 28 Jan 92 01:13:00 +0100
From: "Olivier M.J. Crepin-Leblond" <UMEEB37@VAXA.CC.IMPERIAL.AC.UK>
Subject: Re: Trojan program collects passwords
This is quite an old trick - but very successful for the hacker. I
recall a similar story about three years ago in a London University.
In 2 days, the hackers managed to get passwords for over 100 accounts.
Fortunately, word got round, and users were asked to press <break> or
ctrl-c before calling a host. The error trapping of the
password-catching program was not behaving in a similar manner as the
PAD (Packet Assembler- Disassembler) was.
Olivier M.J. Crepin-Leblond, Electrical Engineering Dept.,
Imperial College of Science, Technology and Medicine, London, UK.
------------------------------
Date: 28 Jan 92 15:41:43 +0000
From: spaf@cs.purdue.edu (Gene Spafford)
Subject: Re: New Antivirus Organization Announced
The "Reply-to" header got stripped out of my posting, so I have been
getting mail from people wanting more info on the Antivirus Methods
Congress.
[Moderator's Note: Sorry, the reply-to: was lost due to the mechanics
of how the list gets distributed. I'm looking into alternative ways
of distributing the two groups.]
I am not (currently) associated with the AMC. If you want more
information, or you want to join, contact Dick Lefkon directly at
dklefkon@well.sf.ca.us
- --
Gene Spafford
NSF/Purdue/U of Florida Software Engineering Research Center,
Dept. of Computer Sciences, Purdue University, W. Lafayette IN 47907-1398
Internet: spaf@cs.purdue.edu phone: (317) 494-7825
------------------------------
Date: Wed, 29 Jan 92 10:08:33 -0600
From: PERRY@beach.gal.utexas.edu (John Perry KG5RG)
Subject: Updated FPROT202 on BEACH (PC)
To All Concerned:
An updated version of FPROT202.ZIP is now available on
beach.gal.utexas.edu (129.109.1.207).
Note to all users: I have received numerous mail messages indicating
difficulty with using the ftp archive on beach. Beach is a VMS
machine, not a UNIX machine. Therefore the file naming conventions are
a little different from what you are used to. When FTP'ing to beach,
changing directories is accomplished as follows:
cd [anonymous.pub.virus.pc]
instead of
cd pub/virus/pc
If you still have trouble, please feel free to contact
perry@beach.gal.utexas.edu.
John Perry KG5RG | perry@beach.gal.utexas.edu - Internet
University of Texas Medical Branch | PERRY@UTMBEACH - BITnet
Galveston, Texas 77550-2772
------------------------------
Date: Wed, 29 Jan 92 15:37:11 -0800
From: p1@arkham.wimsey.bc.ca (Rob Slade)
Subject: "Commercial safety" myth
p1@arkham.wimsey.bc.ca (Rob Slade) writes:
> survey of 600,000 PCs indicated that 63% had been hit with an infection.
> Why? Easy. Only 25% had any kind of protection against viri. (Note -
> even more disturbing - *at least* 48% *have been hit and STILL HAVE NOT
In which we prove that Rob Slade is not so very clever after all.
Sufficient numbers have now pointed out to me that 63 - 25 = 38, and
not 48.
Thank you. (At least it proves people read the post! :-)
==============
Vancouver p1@arkham.wimsey.bc.ca | "A ship in a harbour
Institute for Robert_Slade@sfu.ca | is safe, but that is
Research into CyberStore Dpac 85301030 | not what ships are
User rslade@cue.bc.ca | built for."
Security Canada V7K 2G6 | John Parks
------------------------------
Date: 24 Jan 92 21:43:59 +0000
From: bontchev@fbihh.informatik.uni-hamburg.de (Vesselin Bontchev)
Subject: Cohen's error
Hello, everybody!
As I mentioned in one of my postings some time ago, it is possible to
find errors even in Fred Cohen's papers... :-) In his first and most
often quoted paper [1], where he gives a definition to the term
"computer virus", there are two serious errors.
The first one is in his sample program, which represents a computer
virus. The program is as follows:
Program V :=
{1234567;
Subroutine infect-executable:=
{loop: file=random-executable;
if (first-line of file = 1234567)
then goto loop;
else prepend V to file;}
Subroutine do-damage:=
{whatever damage you can program}
Subroutine trigger-pulled:=
{whatever trigger you want here}
Main-program-of-virus:=
{infect-executable;
if (trigger-pulled) then do-damage;
goto next;}
next:
}
As Cohen himself notices in his textbook [2], thousands of people have
looked at the above program and nobody has noticed that the program is
not correct and contains an error. To see the error, consider for a
moment that the above virus has infected -all- the available executable
files in the system. It is obvious that the next time you run a program,
the routine in the virus, which looks for an uninfected executable, will
loop forever! But, as I already mentioned, Cohen has found this error
himself.
The second error in his paper is much more important. It is in his proof
that the problem of recognizing a computer virus by its appearance is
undecidable. I'll explain the error in detail here.
DISCLAIMER: The following ideas are not mine. The error has been first
noticed by Dr. Franz X. Steinparz from Johannes Kepler Universitaet
Linz, Technisch-Naturwissenschaftliche Fakultaet, Forschungsinstitut
fuer Mikroprozessortechnik, A-4040 Linz/Auhof, Altenbergerstrasse 69,
Austria. I saw a pre-release version of his paper, entiteled "A
Comment on Cohen's Theorem About Undecidability of Viral
Dedection" and decided that the matter is quite important and
should be discussed here. Also, in the paper the error has been just
pointed out in two sentences; I'm giving here a more detailed
explanation.
First of all, I'll explain here the proof which Cohen gives. It is
probably well-known to most of you, but we need it for the explanation.
The proof is based on the well-known proof of undecidability of the
so-called halting problem. Cohen himself does not state this explicitely
in his paper, but the analogy is obvious. So, let's begin with the
halting problem.
The problem consists in the following. It is impossible to write a
program (or more exactly, to construct an algorithm), which accepts
another program as an input and outputs a boolean result (false or
true), indicating whether the program in question will stop after a
finite number of steps or not, respectively, and which is able to
produce correct results in -all- possible cases. The proof is as
follows.
- -------cut here------
Let's assume that such an algorithm exists and it has been implemented
in the function D(P), which gets the program P as input and returns a
boolean result, indicating whether the program P will not stop after a
finite number of steps. Let's also construct the following program P1:
program P1;
function D (prog P) : boolean;
begin
.
.
.
end;
procedure dont_stop;
begin
repeat
until false
end;
begin
if D (P1)
then halt
else dont_stop
end.
It is obvious that the function D is unable to give a correct result in
this case. If it returns true (which means that the program P1 will not
stop), then the program P1 will stop (if D (P1) then halt). If it
returns false (which means that the program P1 will stop), then the
program P1 will never stop (the dont_stop procedure will be executed,
which consists of an endless loop). Therefore the algorithm D is unable
to give a correct result at least in this one case. Therefore no such
algorithm exists, since we assumed that it will work in all cases.
There is no contradiction, however, if the function D itself does not
stop after a finite number of steps. Therefore, we just proved that an
algorithm, which is able to recognize whether a program will not stop
after a finite number of steps, does not exist, or will run forever in
some cases.
- -------cut here------
In fact, the above is just a particular case of the Rice theorem, which
states that all non-trivial properties of the Turing machines are
undecidable. (A property is considered trivial, if either all Turing
machines have it, or no Turing machine has it.) Note that the proof
holds only for Turing machines, not for real computers, but I'll
consider this later.
Now, let's see the problem of recognizing a virus by its appearance.
First, we need a definition of what a computer virus is. Cohen gives
such a definition in his paper: "A computer virus is a program, which
has the ability to infect other programs by modifying them in such a
way, that they will include a possibly evolved copy of itself". In
short, a virus is a program, which infects other programs.
The problem consists in the following. It is impossible to write a
program (or more exactly, to construct an algorithm), which accepts
another program as an input and outputs a boolean result (true or
false), indicating whether the program in question will infect other
programs or not, respectively, and which is able to produce correct
results in -all- possible cases. The proof is as follows.
- -------cut here------
Let's assume that such an algorithm exists and it has been implemented
in the function D(P), which gets the program P as input and returns a
boolean result, indicating whether the program P will infect other
programs. Let's also construct the following program P1:
program P1;
function D (prog P) : boolean;
begin
.
.
.
end;
procedure infect;
begin
.
. { Not shown for security reasons :-) }
.
end;
begin
if D (P1)
then halt
else infect
end.
It is obvious that the function D is unable to give a correct result in
this case. If it returns true (which means that the program P1 will
infect other programs), then the program P1 will not infect other
programs (if D (P1) then halt). If it returns false (which means that
the program P1 will not infect other programs), then the program P1 will
infect other programs (the infect procedure will be executed, which will
do it). Therefore the algorithm D is unable to give a correct result at
least in this one case. Therefore no such algorithm exists, since we
assumed that it will work in all cases.
There is no contradiction, however, if the function D itself does not
stop after a finite number of steps. Therefore, we just proved that an
algorithm, which is able to recognize whether a program will infect
other programs, does not exist, or will run forever in some cases.
- -------cut here------
Well, the above is the proof, which Cohen gives. Have you noticed how
similar it is to the proof of the halting problem? We just replaced
"does not stop after a finite number of steps" with "will infect other
programs" and did some other cosmetic changes... Cohen himself does not
mention explicitely in his paper that his proof is constructed after the
one of the halting problem, but the analogy is obvious.
But wait! Look at the two proofs again. Did we do the replacement
everywhere? No! In the last paragraph of the second proof we are still
speaking about programs, which to not stop after a finite number of
steps... While assuming that the function D will not stop after a finite
number of steps in some cases indeed removes the contradiction, a
correct replacement will require that we assume that the function D
itself has the side-effect to infect file, i.e. that it is a virus!
So, Fred Cohen's proof does not prove that detecting a virus by its
appearance is undecidable! It only proves that if a universal virus
detector exists, it will either run forever in some cases, or will be
itself a virus...
Well, so what? Does this mean that we have to allow everybody to
write viruses, in hope that they'll found one, which is the universal
virus detector? Fortunately, no! The problem whether a program is a
virus or not, is still undecidable. However, proving it is a bit
more tricky...
In fact, Fred Cohen himself supplies a correct proof in his paper [3],
without mentioning, however, that his first proof is wrong. In this
paper he proves that the class of computer viruses is equivalent to the
class of Turing machines, which always stop after a finite number of
steps. And, since recognizing those by their appearance is undecidable
(the halting problem), therefore, the recognition of computer viruses in
the general case is undecidable either. However, everybody, who makes
the effort to read and understand [3], will see that proving that is
not that trivial at all...
Well, as I said, all the above proofs hold only for Turing machines.
Solving the halting problem for finite automata is trivial, since they
all stop after a finite number of steps by definition. Writing an
universal virus detector for a finite automate should be just as
trivial. It is obvious that the real computers are not Turing machines,
since they have only a finite number of memory (the Turing machine has
an endless from both sides tape, which can be used as memory).
I thought that the finite number of memory cells in the real computers
implies that they are in fact finite automata. However, as Yisrael Radai
has pointed to me in our private correspondence, if we have a
civilization, which generates programs and supplies it to a computer
with a finite number of memory cells, you still can get a computer with
infinite number of programs... The question turned out to be of
philosophycal matter.
I consulted a specialist in computational theory and here is what I was
told. It seems that there are three kinds of infinity.
The first kind is the practical infinity - say a number like 10^100.
Such number is infinite in practice, since it cannot exist - it is
much, much larger than the estimated number of elementary particles in
the Universe. Of course, the mathematics does not consider this as
infinity at all. :-)
The second kind of infinity is e.g. a class, which has an infinite
number of elements, but for which you have a determined rule or set of
rules how to obtain the next element. A typical example is the class of
natural numbers. There is infinite number of natural numbers, but you
can always obtain the next element. It seems that the computer with
finite munber of memory cells, combined with a civilization, which
produces programs is an infinite computer of this class.
And, at last, there is the in
Downloaded From P-80 International Information Systems 304-744-2253