When the column about Core War appeared last May, it had not occurred to me how serious a topic I was raising. My descriptions of machine-language programs, moving about in memory and trying to destroy each other, struck a resonant chord. According to many readers, whose stories I shall tell, there are abundant examples of worms, viruses and other software creatures living in every conceivable computing environment. Some of the possibilities are so horrifying that I hesitate to set them down at all.
The French spy thriller Softwar: La Guerre Douce (English translation to be published by Holt, Rinehart & Windston) provides a geopolitical fantasy of this type. Authors Thierry Breton and Denis Beheich spin a chilling yarn about the purchase by the Soviet Union of an American supercomputer. Instead of blocking the sale, American authorities, displaying studied reluctance, agree to the transaction. The computer has been secretly programmed with a "software bomb." Ostensibly bought to help with weather forecasting over the vast territory of the Soviet Union, the machine, or rather its software, contains a hidden trigger; as soon as the U.S. National Weather Service reports a certain temperature at St. Thomas in the Virgin Islands, the program proceeds to subvert and destroy every piece of software it can find in the Soviet network. To the extent that such scenarios represent real possibilities, I am tempted to say, "If we must have war, by all means let it be soft." On the other hand, the possibility of an accident due to the intimate connection between military software and weapons-control systems gives me pause.
Before I describe the experiences of various readers with hostile programs it would be worthwhile to summarize Core War for those who missed the May 1984 column:
Two players write one program each in a low-level language called REDCODE. The programs are placed in a vast, circular arena called Core. In reality Core is simply an array of several thousand locations whose last address is contiguous to the first. Each battle-program instruction occupies one location in Core. A Memory Array Redcode Simulator executive program (MARS for short) runs the battle programs by alternately executing one instruction of each, in the manner of a simple time-sharing system: the two programs attack each other and seek in turn to avoid damage or to repair it. A simple mode of attack can be executed by means of MOV instructions. For example,
Since no computer, whether personal or mainframe, comes equipped with REDCODE and a convenient battle array, such features must be simulated. Guidelines for writing a simulation program were and still are available from the offices of Scientific American at a cost of $2 to cover postage and handling. Please address your request to Core War, Scientific American, 415 Madison Avenue, New York, N.Y. 10017. Last year several hundred readers obtained the guidelines and a large percentage of them wrote Core War game programs.
Inspired by a June 1959 Scientific American article on self-reproducing mechanisms by L. S. Penrose, Frederick G. Stahl of Chesterfield, Mo., created a miniature linear universe in which humble creatures lived, moved and (after a fashion) lived out their destinies. Stahl writes:
"Like Core War, I set aside a closed, linear segment of main memory in which a creature was simulated by modified machine language. The machine was an IBM Type 650 with drum memory. The creature was programmed to crawl through its universe eating food (nonzero words) and creating a duplicate of itself when enough food was accumulated. Like Core War, I had an executive program which kept track of who was alive and allocated execution time among the living creatures. I called it the 'Left Hand of God.'" Stahl goes on to discuss his program's ability to reproduce. He also describes an interesting mutation mechanism; a program being copied might experience a small number of random changes in its code. However, Stahl reports, "I abandoned this line of work after one production run in which a sterile mutant ate and killed the only fertile creature in the universe. It was apparent that extraordinarily large memories and long computer runs would be needed to achieve any interesting results."
A similar story concerns a game called Animal in which a program tries to determine what animal a human is thinking of by playing a form of Twenty Questions. David D. Clark of the Massachusetts Institute of Technology Laboratory for Computer Science writes that the employees of a certain company devotedly played Animal. While it resembles neither a battle program nor even Stahl's simple creatures, Animal achieved the ability to reproduce itself in the corridors of core through the efforts of a programmer to enhance a key feature of the game: when the program guesses incorrectly what animal the human has in mind, it asks the human to suggest a question it might ask to improve its future performance. This feature, Clark continues, led the programmer to invent a certain trick for making sure that everyone always had the same version of Animal.
"On a very early computer system, which lacked any shared directory structure, but also lacked any protection tools, a programmer invented a very novel way of making the game available to several users. A version of the game existed in one user's directory. Whenever he played the game, the program made a copy of itself into another directory. If that directory had previously contained a copy of the game, then the old version was overwritten, which made the behavior of the game change unexpectedly to the player. If that directory had previously had no version of Animal, the game had been offered to yet another user."
Clark recalls that Animal was such a popular game that eventually every directory in the company system contained a copy. "Furthermore, as employees of the company were transferred to other divisions...they took Animal as well, and thus it spread from machine to machine within the company." The situation would never have become serious had it not been for the fact that all those copies of this otherwise innocuous game began to clog the disk memory. Only when someone devised a more "virulent" version of the game was the situation brought under control. When the new version of Animal was played, it copied itself into other directories not once but twice. Given enough time, it was thought, this program would eventaully overwrite all the old versions of Animal. After a year had passed, a certain date triggered each copy of the new Animal program. "Instead of replicating itself twice whenever it was invoked, it now played one final game, wished the user 'goodbye' and then deleted itself. And thus Animal was purged from the system."
Ruth Lewart of Homdel, N.J., once created a monster (of sorts) without even writing a program. Working on her company's time-sharing system, she was preparing a demonstration version of a teaching program when she decided to make a backup copy on another time-sharing system. When the original system began to seem sluggish, she "switched to the backup system, which was very responsive -- for all of three minutes, by which time there was no response and utter chaos on the screen of my graphics terminal. It was not possible for any user to log on or to log off from the system. The conclusion was inescapable -- my program was somehow at fault! Despite my panic, I suddenly realized that I had specified an ampersand as the terminal's field separator character. But the ampersand was also the character used by the computer system to spawn a background process! The first time the computer read from the screen, it must have intercepted the ampersands meant for the terminal, and spawned a number of processes, which in turn each spawned more processes, ad infinitum." A frantic long-distance call informed a system administrator of the source of the disease and the mainframe computer was then shut down and restarted. Needless to say, Lewart changed the ampersand to a less dangerous character. Her program "has been humming happily ever since."
Even though Core War programs are not spawned in this manner, additional copies can enhance their survival. Several readers suggested three copies of a program be made so that the copy currently executing could use the other two copies to determine whether any of its instructions were wrong. The executing program could even replace a faulty instruction with a viable one. A similar idea lies behind Scavenger, a program designed to protect mass-storage files from error when backup copies are made on magnetic tape. Arthur Hudson, who lives in Newton, Mass. (and works for yet another unnamed company), writes: "Anyone who used much magnetic tape found himself beset by an alien force called the Law of Joint Probability." Hudson goes on to cite various errors connected with the handling of tapes and shows that, although each kind of error has a relatively small chance of happening, the probability or at least one of them occurring is uncomfortably large. He continues:
"Fear not, Scavenger is with you; If you place a mass-storage file in its care, it will copy the file on three magnetic tapes without bothering you with housekeeping details. Even if the computer crashes logically (as it did several times per day), the run backlog usually will not be destroyed; when the computer comes back up, whatever Scavenger worms are in the backlog will run in their turn. Each tape is written by a separate run scheduled from a master runstream."
Owners of Apple computers should beware a mean little program called Apple Worm, created by Jim Hauser and William R. Buckley of California Polytechnic State University at San Luis Obispo. Written for the Apple II in 6502 assembly language, this species of worm replicates itself on a merry little journey through the host Apple. Initially one loads a special BASIC program [see illustration on preceding page] that in turn loads the worm into low memory (the part with low addresses). The BASIC program, on the other hand, occupies high memory.
"Because the Worm is loaded into one of the graphics areas of the machine, you can watch the Worm as it begins it headlong (actually, tail-long) dash into high memory.... After the Worm leaves the graphics window... you can wait until the Worm erases all of high memory (including the BASIC program) and crashes into the system ROMS."
Hauser and Buckley plan to publish a collection of worms in the not too distant future. They have designed a Worm Operating System and have even written a video game with Worm as one of its main characters.
Another software threat has been propounded by Roberto Cerruti and Marco Morocutti of Brescia, Italy. Inspired by the translation of the column on Core War in the Italian edition of Scientific American, Le Scienze, the two sought a way of infecting the Apple II computer, not with a worm but with a virus. Reports Erruti:
"Marco thought to write a program capable of passing from one computer to the other, like a virus, and 'infecting' in this way other Apples. But we were not able to conceive it unil I realized that the program had to 'infect' floppy disks, and use the computers only like a media from a disk to the other. So our virus began to take shape.
"As you know every Apple diskette contains a copy of the Disk Operating System, which is bootstrapped by the computer at power on. The virus was an alteration in this DOS, which at every write operation checked his presence on the disk and, if not, would modify in the same way the DOS on the disk, thus copying itself on every diskette put in the drive after the first power up. We thought that installing such a DOS on some disks used in the biggest computer shop in out city, Brescia, would cause an epidemic to spread in the city.
"But was it a real epidemic, of such unharming viruses? No, our virus should be malignant! So we decided that after 16 self-reproduction cycles, counted on the disk itself, the program should decide to re-initialize the disk immediately after bootstrap. Now the awful evil of our idea was clear, and we decided neither to carry it out, nor to speak to anybody about our idea."
That was kind of Cerruti and Morocutti. In a personal computer the disk operating system is the ultimate arbiter of the fate of programs, data and all else. In the scheme just described the infected disk operating system erases the disk whence it came and can therefore never be loaded again except from a new disk. The diseased DOS could even cause an irritating message to be displayed periodically:
The viral infection just described has already happened on a small scale. Richard Skrenta, Jr., a high school student in Pittsburgh, wrote such a program. Instead of wiping disks or displaying advertisements, this form of infection caused subtle errors to appear throughout the operating system.
"All of this seems pretty juvenile now," writes Skrenta, but "Oh woe to me! I have never been able to get rid of my electronic plague. It infested all of my disks, and all of my friends' disks. It even managed to get onto my math teacher's graphing disks." Skrenta devised a program to destroy the virus, but it was never as effective as the virus itself had been.
There is a good problem implicit here and I would be both unimaginative and irresponsible for not posing it; In one page or less describe DOS DOCTOR, a program on disk that somehow stamps out such electronic epidemics. Many disks used by a personal computer contain copies of its DOS. When started up, the computer obtains its copy of the DOS from the disk. This DOS will still be in charge when other disks, also containing copies of the DOS, are run. If it is infected, the DOS currently in charge may alter the other copies of the DOS or even replace them with copies of itself. But how to counteract such virulence?
In the initial version of Core War the main challenge was to enable battle program A to protect itself from stray hits generated by battle program B. If such protection could be more or less guaranteed, then evolution of the game was to proceed to the next level, where programs would have been forced to seek each other out and develop concentrated attacks.
In an effort to guarantee such protection, I suggested in the May column the instruction
There is another use of this instruction, unforeseen in the earlier Core War article. Stephen Peters of Timaru, New Zealand, and Mark A. Durham of Winston-Salem, N.C., independently thought of using PCT offensively. A program called TRAP-DWARF lays down a barrage of zeros in the usual way but then protects each deposit against overwriting. This means that an unwary enemy program may fall into one of these traps in the course of writing inself into a new area. The instruction meant for the location occupied by a protected zero would of course have no effect on that location. Later, when the new program's execution reaches that address, it dies because 0 is not an executable instruction. PCT may be worthy of inclusion in some future version of Core War but I shall shelve it for now in the interest of simplicity, the game designer's touchstone.
Other reader ideas varied from the two-dimensional Core array suggested by Robert Norton of Madison, Wis., to the range-limitation rule suggested by William J. Mitchell of the mathematics department at Pennsylvania State University. Norton's idea is largely self-explanatory but Mitchell's suggestion requires some elaboration. Allow each battle program to alter the contents of any location up to a distance of some fixed number of addresses. Such a rule automatically keeps DWARF from doing any damage outside this neighborhood. The rule has many other effects as well, including a strong emphasis on movement. How else can a battle program get within range of an opponent? The rule has much merit and I hope that some of the many readers with a Core War system of their own will give it the further exploration it deserves.
Norton also suggests that each side in a Core War battle be allowed more than one execution. The same idea occurred to many other readers. Indeed, I have decided to adopt the suggestion. Core War now assumes a previously lacking wide-open character.
The change is made by adding the following instruction, called a split, to the official Core War list [see illustration on page 14].
To illustrate them suppose one player has programs A1, A2 and A3, whereas the other player has programs B1 and B2. One alternative is to have all the first player's programs run, followed by those of the second player. The order of execution would thus be A1, A2, A3 and then B1 and B2. The cycle would repeat indefinitely. The second alternative is to have the programs of the two players alternate. In this case the sequence would be A1, B1, A2, B2, A3, B1 and so on. The two schemes are quite different in effect. The first scheme puts great emphasis on unlimited proliferation and seems thereby to limit the role of intelligence in the game. The second scheme, however, implies that the more programs either player has running, the less often each will be executed. A low of diminishing returns seems appropriate in this context and I have therefore adopted the second scheme. The purpose of the game, in any event, is to bring all enemy programs to a halt.
The new instruction is rife with creative possibilities. As an illustration of the humblest issue possible, there is a battle program called IMP GUN:
Consider what happens when execution first arrives at the top of this program. The instruction SPL 2 means there will be two executions allotted to this program later: both JMP -1 and MOV 0 1 will be performed. The first instruction causes the program to recycle and the second sets an IMP in motion. The IMP will move down, of course, since the target of the MOV command will always be the next address, as indicated by they (positive) 1. The IMP's run pattering through Core bent on the destruction or subversion of hostile programs. At first glance it may seem that no defense is possible against such an army of IMP's, but in fact one is. Enter IMP PIT, an even simpler program set in motion by an SPL command in some larger assembly of instructions wishing to protect its upper flank:
In the expanded Core War game, one imagines each side generating and deploying small armies of programs individually shaped to detect, attack, protect and even repair. Many subtleties such as the one suggested by John McLean of Washington, D.C., await further investigation. McLean imagines a specialized trap program that places JMP commands at various addresses throughout the Core array in the hope of landing a JMP command inside an enemy program. Each JMP so placed would transfer execution of the enemy program to the trap program, causing it to go over to the enemy, so to speak.
One major problem in need of resolution emerges from the melee of battle programs. What is to prevent a battle program for one side from attacking its colleagues? A recognition system appears to be necessary.
Among the many readers who have constructed Core War systems three deserve special mention: Chan Godfrey of Wilton, Conn., Graeme R. McRae of Monmouth Junction, N.J., and Make Rosing of Littleton, Colo., have taken special care in defining and documenting their projects. I should particularly like to make Rosing's documents available to readers, but there is another and better idea that includes this possibility and solves other communication problems as well. If any reader with a Core War system already running will volunteer to act as the director of a Core War network, then documentation of various systems, rule suggestions, interesting programs and battles can be communicated to all participating Core War users. One volunteer will be chosen as director; the remaining volunteers might help with potential functions such as a newsletter, rules committee and so on, according to interest. In a future article I shall give the name and address of the network director.
