Proseminar

Proseminar

Würmer, Viren und Krieg der Bits

Jörg Hakenberg

Proseminar "Artificial Life"

Sommersemester 1998

Universität Ulm


Inhalt

  1. Core Wars
    1. Was ist Core Wars ?
    2. Die Core Wars - Umgebung
    3. Aufbau der Programme
    4. Simulation einiger Kämpfe über Beamer
    5. ´Leben´ durch Splitten der Programme
  2. Würmer und Viren
    1. Unterschiede
    2. Wirkungsweise von Viren

Top

Core Wars

Was ist Core Wars ?

Das ´Spiel´ Core Wars stellt eine Simulation von gegeneinander kämpfenden Programmen dar. Diese Programme, in einer stark vereinfachten Assemblersprache verfasst, werden dabei in einen abgekapselten Speicherbereich eines Computers geladen und tragen dort ihre Gefechte gegeneinander aus. In gewisser Weise setzt die auf der Simulation von Langton´s Ameisen auf, in Core Wars beinhalten die kleinen Programme jedoch Mechanismen zur gezielten Zerstörung ihrer Kontrahenten sowie Reparatur- und Reproduktionsfunktionen. Daraus ergibt sich auch das Ziel des Spieles - die feindlichen Programme zum Stoppen zu bringen und den eigenen Code zu schützen und zu verbreiten.
Erfunden wurde Core Wars von Alexander K. Dewdney, der zusammen mit einem Studenten seiner Abteilung an der Universität von Western Ontario die erste Version programmierte. Die erste Publikation über Core Wars erschien 1984 in der Zeitschrift Scientific American [1].

Die Core Wars - Umgebung

Um die Programme im Speicher gegeneinander antreten zu lassen, ist ein Simulator notwendig, der den Programmcode ausführen und den jeweiligen Spielstand bis hin zum Sieg eines Programmes erfassen kann. Der ursprüngliche, von A.K. Dewdney entwickelte Simulator MARS (Memory Array Redcode Simulator) [6] wurde in der Vergangenheit ständig erweitert und es ergaben sich auch etliche Clones mit unterschiedlichsten Neuerungen. Inzwischen sind solche CoreWars-Umgebungen für beinahe sämtliche Plattformen verfügbar. Um die einzelnen (vom Simulator im Quellcode eingelesenen) Schlachtprogramme portabel zu halten, wurde die Sprache REDCODE, die MARS zugrunde liegt, standardisiert.
Das im Vortrag vorgestellte Simulationsprogramm ist das unter DOS lauffähige Core War [11], es umfasst denselben Sprachumfang und überträgt den Kampf im Speicher auf den Bildschirm, während das originäre MARS lediglich das Endergebnis ausgibt.

MARS stellt für das Schlachtfeld ein eindimensionales Array von 8000 Plätzen zur Verfügung und lädt die einzelnen Programme an verschiedene Stellen (mindestens 1000 Plätze voneinander entfernt) des gesamten Feldes. Dieser Speicherbereich ist - vom Simulator überwacht - vollkommen autark vom restlichen Hauptspeicher des Computers abgekapselt, ´Querschläger´, die nicht zur Simulation gehörende Daten beeinflussen könnten, werden hierdurch ausgeschlossen. Die Instruktionen der geladenen Programme gelangen einzeln und zwischen den Programmen alternierend zur Ausführung. Stösst der Simulator dabei auf eine nicht ausführbare Anweisung (so zum Beispiel ein reines Datenfeld), wird das betreffende Programm angehalten und der Gegner gewinnt. Bleiben auch nach einer definierten (rechnerabhängigen) Zeitspanne sämtliche Programme ablauffähig, wird die Simulation mit einem Remis abgebrochen.

Aufbau der Programme

Sprache REDCODE

Die Sprache, in der die Core Wars - Programme erstellt werden, trägt den Namen REDCODE. REDCODE ist eine Assemblersprache, die allerdings einen stark eingeschränkten Funktionsumfang besitzt. Für die Zwecke von Core Wars reichen die wenigen Befehle jedoch auch vollkommen aus, ein allzu grosser Befehlssatz würde das Ergebnis des Kampfes wohl ausschliesslich von der Reihenfolge der Ausführung der einzelnen Programme abhängig machen. Und schliesslich sollen auch direkte Eingriffe in das gesamte Computersystem verhindert werden.
Seit dem ersten Simulator von A.K. Dewdney hat sich der Funktionsumfang von REDCODE laufend weiterentwickelt. Er wurde in verschiedenen Standards deklariert, zuletzt im ICWS´94 (International Core War Society), der auch die restlichen Bestimmungen zu Core Wars regelt. Ferner richtet die ICWS auch noch offizielle Wettkämpfe aus [4].

Der Befehlsumfang von REDCODE
OpcodesOperandenMnemonicWirkungsweise
DATAdataSpeichere den Wert A ab. Nicht ausführbar.
MOVA BmoveKopiere A nach B.
ADDA BaddAddiere A zu B.
SUBA BsubtractSubtrahiere A von B.
JMPAjumpSetze Programm an relativer Adresse A fort.
JMZA Bjump if zeroSpringe nach A, wenn B = 0.
JMGA Bjump if greaterSpringe nach A, wenn B > 0.
DJZA Bdecrement and jump if zeroSubtrahiere 1 von B. Springe nach A, wenn jetzt B = 0.
CMPA BcompareFolgende Anweisung übergehen, falls A = B.
SPLAsplitSpalte die Ausführung des Programmes in zwei Teile. Programm wird an der Stelle nach dem Kommando SPL und an der relativen Adresse A fortgesetzt.
PCLAprotect cellSchütze die durch A angegebene Zelle.

Operanden in REDCODE
OperandWirkungsweise
Abezeichnet relative Speicheradresse (auch negative Werte möglich)
#Ameint den Wert (die Zahl) A
@Abezieht sich auf den Inhalt der relativen Speicheradresse A

Beispielprogramme

Zunächst möchte ich nun einmal einige kleinere und recht einfache Beispielprogramme vorstellen und danach noch allgemein auf (Überlebens-)Strategien eingehen.

Das erste Programm, DWARF, ist zwar nicht sehr clever, dafür aber auch recht gefährlich. Die mit DWARF realisierte Idee besteht darin, den kompletten Speicher mit Nullen zu bombardieren. Wird ein feindliches Programm von solch einer Null getroffen, so wird der vorher an der entsprechenden Zelle stehende Codeteil dieses Programmes überschrieben, und zwar mit einem nicht ausfürbaren Befehl. Gelangt das Programm einmal an diese Stelle, so wird es automatisch gestoppt und DWARF gewinnt den Kampf. Um sich selbst jedoch vor seinen ´Bomben´ zu schützen, beschiesst DWARF, das nur vier Zellen für seine Befehle benötigt, nur jeden fünften Speicherplatz und trifft damit zwar die Zellen direkt vor und nach seinem eigenen Code, niemals aber sich selbst.

DWARF
DAT #-1		; Startwert im Speicher ablegen
ADD #5, -1	; zur vorherigen Adress fünf dazuzählen
MOV #0, @-2	; eine Null an die Adresse schreiben,
		  die in der DAT-Zelle zwei Plätze vorher festgelegt ist
JMP -2		; zwei Plätze zurückspringen auf den ADD-Befehl

Als zweites kleines Beispiel dient das wohl einfachste und vor allem kürzeste in REDCODE realisierbare Schlachtprogramm, IMP. IMP durchläuft in einem fort den gesamten Speicher, indem es sich immer wieder selbst an die nächste Adresse kopiert. Nach der Ausführung des einzigen Befehles des Programmes gelangt die Kontrolle ja automatisch an die im Speicher direkt folgende Zelle, in die IMP sich gerade selbst kopiert hatte.

IMP
MOV 0, 1	; schreibt den Inhalt der aktuellen Zelle in die folgende

Ein auf den ersten Blick etwas komplizierteres Programm ist GEMINI. Seine Funktion besteht ähnlich wie beim IMP darin, sich selbst immer wieder an eine andere Stelle im Speicher zu schreiben und die so entstandene Kopie zum eigentlichen Programm zu machen. Dazu verschiebt GEMINI sich jedoch wirklich, der komplette Code wird jeweils um hundert Felder im Speicher nach hinten kopiert und die Ausführung explizit an den neuen Code übergeben.

GEMINI
DAT 0		; Zeiger auf den Quellcode
DAT 99		; Zeiger auf die Zieladresse
MOV @-2 @-1	; Quellcode ans Ziel kopieren
CMP -3 #9	; Sind alle zehn Zeilen kopiert ...
JMP 4		; ... dann die Schleife verlassen
ADD #1 -5	; ... sonst die nächste zu kopierende Zeile ´berechnen´
ADD #1 -5	;     sowie die nächste Zieladresse
JMP -5		;     und die Schleife nochmals durchlaufen
MOV #99 93	; Die nächste Zieladresse festlegen
JMP 93		; Schliesslich die Ausführung an die Kopie übergeben

Strategien

Die vorgestellten Programme DWARF und IMP könnte man als klein und gefährlich bezeichnen, sie sind jedoch auch recht starr und unflexibel.
Auf dem nächsthöheren Niveau liegen diejenigen Schlachtprogramme, die etwas grösser sein können und auch weniger aggressiv, dafür aber mit der vorherigen Klasse keine grossen Probleme mehr haben. Diese clevereren Programme verschieben sich einfach an immer wieder neue Stellen im Speicher und können so den meisten Angriffen entgehen. Jedes dieser Programme enthält einen Codeteil ähnlich wie den von GEMINI, auch wenn dieser Code für sich betrachtet nahezu rein defensiv ist (ein Überschreiben eines feindlichen Programmes wäre wohl eher zufällig). Aus GEMINI lassen sich jedoch auch andere Programme ableiten, wie zum Beispiel JUGGERNAUT [7], das sich selbst um lediglich jeweils zehn Plätze verschiebt und damit wie IMP nach und nach den gesamten Speicher überrollt. BIGFOOT [8] hingegen berechnet seine neue Adresse anhand grosser Primzahlen und ist damit nur sehr schwer zu fassen.
Aber auch mit JUGGERNAUT und BIGFOOT sind noch nicht alle Möglichkeiten von REDCODE ausgereizt. In die nächste Klasse von Schlachtprogrammen zählt nun allerdings RAIDAR [9]. RAIDAR schützt seinen Codeteil durch zwei Mauern, die jeweils aus 100 mit ´1´ gefüllten DAT-Zellen bestehen und um 100 Plätze vor und nach dem Code im Speicher stehen. Das Programm selber besteht aus zwei Blöcken : der eine greift Speicherzellen ausserhalb seiner Grenzen an und der andere tastet permantent die beiden Schutzwälle ab. Wurde einer der Wälle verändert, so sieht RAIDAR dies (wohl zurecht) als einen Angriff an und kopiert sich selbst auf die andere Seite dieses angegriffenen Walles. Anschliessend repariert es diese beschädigte Mauer und errichtet auf seiner jetzt ungeschützten Seite eine neue, bevor es wieder mit den eigenen Angriffen und der Kontrolle der Wälle fortfährt.
Eine andere Form des Selbstschutzes führt SCANNER [10] vor. Während die bisher erwähnten Programme bei einem direkten Treffer ihres (wichtigsten) Codeteiles früher oder später angehalten werden, ist SCANNER in der Lage, Beschädigungen an sich selbst zu reparieren. Dazu hält es zwei Kopien von sich gleichzeitig im Speicher, wobei allerdings nur eine davon wirklich ausgeführt wird. Die ablaufende Kopie vergleicht sich selbst ständig mit der anderen und kann so einen Angriff auf sich feststellen. SCANNER nimmt dabei an, dass die jeweils ausgeführte Version die fehlerfreie ist. Entdeckt es eine Änderung des Codes, so repariert das Programm diese und verlagert die Ausführung dann auf die Kopie, die vorher zum Vergleich benutzt wurde. SCANNER ist ein rein defensives Schlachtprogramm, sein Code könnte allerdings für den Bau komplexerer, sich auch offensiv verhaltender Programme weiterverwendet werden.

Leben

Wirklich interessant wurde CoreWars mit der Einführung eines neuen Kommandos : Split (SPL). Split ermöglicht es, ein Programm nicht nur an der dem Kommando direkt folgenden Adresse fortzusetzen, wie es bei den restlichen Befehlen (von den Jumps einmal abgesehen) üblich ist, sondern simultan auch an der dem SPL als Operand übergebenen Adresse. Dies erlaubt einem grösseren Programm, sich in mehrere kleine ´aufzuteilen´ und damit lässt sich dann eine ganze Armee von Schlachtprogrammen aufbauen, deren ´Teilstreitkräfte´ die unterschiedlichsten Aufgaben erfüllen können. Auch diese kleinen Teile des Programmes dürfen natürlich wiederum SPL-Befehle enthalten und können die Programme weiter untergliedern.

Eine einfache Verwendungsmöglichkeit des SPL-Kommandos nutzt IMP GUN. Dieses Programm funktioniert fast wie IMP, nur durchläuft hier nicht nur eines davon den Speicherraum.

IMP GUN
SPL 2		; verzweigt nach JMP -1 und MOV 0 1
JMP -1		; springt eine Zelle zurück
MOV 0 1		; wie IMP : "MOV 0 1" in folgende Zelle schreiben

Früher oder später erreichen die IMPs des IMP GUN leider den SPL-Befehl dieses Programmes und überschreiben ihn. Zwar sind dann immer noch knapp 8000 IMPs unterwegs (zumindest theoretisch), aber schade ist diese Tatsache natürlich trotzdem. Die Schlachtprogramme können sich jedoch durch eine kleine aber feine Falle, IMP PIT, vor der heraneilenden Bedrohung retten. Diese Falle macht auch erst mit der Einführung des SPL Sinn, stellte sie vorher ja lediglich einen Schutz vor IMPs bereit und konnte weder andere Programme attackieren noch sich gegen sie verteidigen. Mit SPL allerdings lässt IMP PIT sich ja parallel zum eigentlichen Code einsetzen, der damit vor den wenig intelligenten Programmen nach Art des IMP sicher ist. Die Falle wird dem eigentlichen Code einfach vorangestellt und bietet damit eine effektive Barriere.

IMP PIT
MOV #0, -1	; schreibt eine Null in die vorhergehende Zelle
JMP -1		; springt zurück zum MOV



Top

Würmer und Viren

Unterschiede

Ein Computervirus ist ein Codestück von typischerweise 200-4000 Bytes Länge, welches sich in fremde, grössere Programme einklinkt, sobald es einmal gestartet und damit in den Speicher geladen wurde. Wird ein infiziertes Wirtsprogramm ausgeführt, so wird auch der Virencode durchlaufen und das Virus kann sich weiterverbreiten, indem es andere Programme befällt.
Im Gegensatz dazu bilden Computerwürmer eigenständige Programme, die fremden Code grundsätzlich nicht verändern. Ein Wurm verbreitet sich über Computernetze, Kopien desselben Wurmes können dabei gleichzeitig auf vielen verschiedenen Rechnern laufen.

Während inzwischen Tausende von Computerviren existieren, gibt es demgegenüber nur eine relativ geringe Anzahl von Würmern. Dies liegt vor allem daran, dass ein Wurm recht schwer zu programmieren ist.
Ein Virus ist lediglich in der Lage, auf einer Hardwareplattform unter einem bestimmten Betriebssystem zu laufen (die meisten Computerviren sind für x86-PC´s mit DOS geschrieben). Disketten, auf denen sich die infizierten Programme befinden, werden mit vielen PC´s genutzt und so gelangen Computerviren von einem Rechner zum nächsten, welcher den Viren wieder dieselben Voraussetzungen von Hard- und Softwareseite her bietet.
Da heutzutage die verschiedensten Rechnertypen miteinander vernetzt werden können, müssen Würmer f¨hig sein, mit den unterschiedlichsten Gegebenheiten zurechtzukommen - eine schwer lösbare Aufgabe.

Wirkungsweise von Viren

Ein typischer Computervirus besteht aus zwei Teilen : einem Reproduktions- und einem Manipulationsteil. Der Reproduktionsteil sorgt für die Weiterverbreitung und der Manipulationsteil ist für die eigentliche ´Aufgabe´ des Virus´ zuständig.
Ist ein Virus einmal in den Hauptspeicher geladen und aktiv, so versucht es, sämtliche nach ihm gestarteten Programme zu infizieren. Dazu schreibt es eine Kopie von sich selbst in die Programmdatei des neuen Wirtes. Dabei kann es sich selbst zum Hauptprogramm machen und den originalen Programmcode in einer Art Subroutine aufrufen (Shell-Virus), sich vor oder hinter den Programmcode schreiben und die Einsprungadressen am Programmbeginn auf sich selbst umbiegen (Add-On-Virus) oder das Original einfach überschreiben (Intrusive-Virus).
Wurde ein Virus durch das Starten eines infizierten Programmes aktiviert, so testet es, ob eine bestimmte Bedingung innerhalb des Computersystems erfüllt ist (beispielsweise das Erreichen eines festgelgeten Datums). In diesem Falle führt das Virus den Codeteil aus, der das eigentliche Virenprogamm darstellt (und z.B. eine Bildschirmausgabe liefert, Dateien löscht, etc.).




Literatur

  1. Alexander K. Dewdney : "COMPUTER RECREATIONS : In the game called Core War hostile programs engage in a battle of bits". In Scientific American 250 (May), 1984. Seiten 14-19.
  2. A.K. Dewdney : "COMPUTER RECREATIONS : A Core War bestiary of viruses, worms and other threats to computer memories". In Scientific American 252 (May), 1986. Seiten 14-19.
  3. A.K. Dewdney : "COMPUTER RECREATIONS : Of worms, viruses and core wars". In Scientific American 260 (March), 1987. Seiten 110-113.
  4. nähre Informationen zum ICWS´94 bietet ftp://ftp.csua.berkeley.edu/pub/corewar/documents/icws94.0202.Z.
  5. Eugene Spafford : "Computer Viruses : A Form of Artifical Life ?". In Artificial Life II. SFI Studies in the Science of Complexity. Vol XII. Eds. D Farmer, C. Langton, S. Rasmussen, C. Taylor. Addison-Wesley 1991.
  6. MARS ist erhältlich unter ftp://ftp.de.uu.net/pub/research/ci/Alife/ak-dewdney/.
  7. Juggernaut-Quellcode : http://www.koth.org/planar/rc/Juggernaut[AKD].txt.
  8. Bigfoot-Quellcode : [12].
  9. Raidar-Quellcode : http://www.koth.org/planar/rc/RAIDAR.txt.
  10. Scanner-Quellcode : [12].
  11. Der Simulator ´CoreWar´ von Edwin J. Herrell und Brad J. Hlista : ftp://ftp.de.uu.net/pub/research/ci/Alife/packages/corewar/
  12. Index von Schlachtprogrammen mit Sourcecode : http://www.koth.org/planar/by-author/complete.htm
  13. Newsgroup zu CoreWars : rec.games.corewar.
  14. CoreWars-FAQ : http://www.stormking.com/~koth/corewar-faq.html.
  15. Links zum Thema ´Artificial Life´ unter http://research.germany.eu.net:8080/public/zooland/.