From: Kenneth R. van Wyk (The Moderator) 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" 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" 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 > 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 ------------------------------ 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" 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 ------------------------------ 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: 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" 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 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