101      /* There is no direct way to determine the number of symbols in the
   102         dynamic symbol table and no hash table is present.  The ELF
   103         binary is ill-formed but what shall we do?  Use the beginning of
   104         the string table which generally follows the symbol table.  */
   105      symtabend = (const ElfW(Sym) *) strtab;

Ralf Burger to me (12/17/06)
	
herm1t schrieb:
- Show quoted text -
hello,

ups..... thats more then 20 years ago!....

I think, I found it in the archives of "Universitaet Dortmund".
But I don't remember it excatly.

Best regrads

Ralf Burger

Editors/translators Foreword

Bereishit In the beginning, there was bureaucracy. I had tried to get major AV companies to give me malware samples to study in an academic setting, but to no avail: Liability reasons, and their suggestion — trekking back and forth to their corporate 'clean' room — was unpalatable to me. I like flat hierarchies, so I turned to herm1t. Herm1t runs (singlehandedly, with minimal equipment and funds) the labour of love known as vxheavens (http://vx.netlux.org), a full-spectrum site dedicated to computer viruses. As quid pro quo, I sent him historical papers he sought for his collection. One title, though, seemed out of reach: A German 1980 MSc thesis by some fellow named Juergen Kraus.

A hefty Dortmund package arrived late October 2006. I was quite pleased. After almost a year of unsuccessful attempts through US academic institutions' Intra Library Loan program, I had the epiphany to contact the computer science librarian at the University of Dortmund, Peter Kleffmann. He managed to locate the sole remaining public copy of the thesis — adding an air of mystery to this trouvaille, it was found stashed away in a vault. I skimmed the thesis: Over two hundred pages on the topic of self-reproducing programs, yet set on a mechanical typewriter, chock- full with hand-edited mathematical formulae and notation, Siemens assembly and SIMULA code. I could not fend off a feeling of nostalgia (and gratitude for Donald Knuth). I set it aside till Christmas break.

As I worked my way through the thesis over Christmas break 2006, my cursory curiosity gave way to wonderment, then awe, then electricity. I felt as if I had stumbled upon a 10th century manuscript in an Scottish convent, delineating the calculus seven hundred years before Leibnitz and Newton. Aspects of the history of computer virology had to be rewritten and proper due given — what a fortuitous find! I sent a printed snail mail copy off to herm1t in the Ukraine and pondered my next steps.

In early February, Eric Filiol, after having discovered an electronic version of the thesis on vxheavens, proposed to me that we jointly translate the work into English, with Juergen Kraus' permission. After almost two years of translation and editing work, Eric and I are pleased to make the translated MSc thesis On Self-Reproducing Computer Programs — easily PhD quality at a top notch institution today — available to a wider audience.

Kraus' work can be approached from several perspectives: As a software engineering tour de force; as a scholarly mathematical investigation of the minimal requirements for self-reproducing computer programs, as an example of William Carlos William's musings of what would happen in a world, lit by the imagination. It may also be read, as the author suggests, as an expression of the scientific "Zeitgeist" of the late 1970s: With the advent of powerful computer systems (like the IBM 360 series) hooked up to networks (US DoD's ARPANET), the spirit of space exploration still fresh and diffuse fears of computers taking over the world popping up in science fiction themes (movies like Colossus), the question Kraus alluded to seems not too farfetched: Could one identify complex structures within computer systems? Moreover, could these structures evolve into something that resembled biological life? Could they even evolve? Thus, an insouciant and inquisitive Juergen Kraus set out to study artificial digital life, with self-reproducing computer programs as his object of investigation. He subsequently offered not only proof that self-reproduction is weaker than recursion (LOOP1 programs are sufficient) and clever constructive examples of such programs in several languages, but had them compete for resources — complete with mutations and crossovers and fitness functions — in a digital biotope.

It is instructive to review some historical precedent. Kleene's recursion theorem (1938) is, of course, explicitly acknowledged in the thesis. Kraus and Claus' speculations were anticipated by von Neumann in his 1949 lecture series where he opined that life as a process could be abstracted away from a particular medium. In 1962 at Bell Labs, Victor Vyssotsky, Robert Morris Sr (Morris fils is the father of the 1988 worm) and Douglas McIllroy developed Darwin, where reproducing computer programs (with the help of a centralized umpire) tried to eliminate competing programs. This setup inspired Core Wars in 1984. The first known (so far) self-reproducing program, a so-called quine written in Atlas Autocode, is attributed to Hamisch Dewar at the University of Edinburgh in the 1960s. His work inspired Bratley and Milo's paper on self-reproducing automata in 1972. Kraus' work in 1980 proved, among other things, that arbitrary functions could be added to self-reproducing programs. As such, he implicitly foreshadowed Cohen and Adleman's 1984 computer virus conceptualization, if not their seminal formalization. ¹

In 1994, ecologist Thomas Ray devised a virtual world called Tierra, seeded with one engineered computer program. Its subsequent offspring, subject to evolutionary pressure in their competition for time and memory resources, gave rise to an ecosystem complete with 'organisms', 'parasites' and 'hyperparasites'. Also in 1994, using a genetic programming framework with LISP programs, John Koza studied the spontaneous emergence of self-reproducing computer programs. Starting with a seed of 12 million 'normal' programs whose functions and terminals could recombine, several hundred self-reproducing programs spontaneously emerged, with a calculated probability of 10^-6 to 10^-9. One has to admire the audacity, instincts, scope and prescience of Kraus's artificial life enterprise.

In addition, considering both the history of computer virology in particular, as well as the domain computer science in general, his work has an incomparable, special quality to it. Between von Neumann's groundbreaking work on cellular automata self-reproduction and Cohen's formalization of computer viruses, Juergen Kraus addressed existing epistemological lacunae in an particularly masterly way. While Kleene's recursion theorem (at least one of the numerous forms of that deep theorem) contains already the essence of computer virology (and much more; the reader is refer to Raymond Smullyan's Diagonalization and Self-reference) — never before did this complex theorem receive any "practical" treatment. Kraus was the first who not only presented such an application, but also illustrated it with many clever practical programs, thus realizing a harmonious synthesis between hard theory and elegant programming. Where von Neumann's approach was — in this context — rather inductive, Kraus's work is deductive. This last point clearly illustrates the European approach to science where mathematical formalism represents the essential theoretical 'seed' scaffolding for subsequent practical application. In this respect, Kraus built a bridge between Kleene's work and Cohen's thesis. Thus, we may definitively claim that computer virology was born on the "old continent" Europe. Why was Kraus' groundbreaking contribution virtually unknown for so long? There were rumors of the German government locking up the thesis to prevent knowledge of viruses from seeping out. The truth proved much more prosaic: Mr Decker, who realized earlier than most the scientific treasure Dortmund harbored, presciently stashed the last copy in a safe to prevent tidy-minded secretaries from throwing it out.²

We are extremely honored to give Juergen Kraus and his work his long overdue tribute. We would like to furthermore extend our gratitude to the following people, without whose efforts none of this could have happened. Prof. Volker Claus (now at the University of Stuttgart, among myriads of innovation a co-founder of the German ACM), the modest and farsighted pioneer of computer science in Germany, for inspiring and guiding Juergen Kraus that fateful winter of 1978/1979. We all should be so lucky to find mentors and students like that. The dedicated herm1t, whose boundless curiosity proved infectious (which does not lack a certain poetry, given the subject matter) and whose services to the virology community are greatly appreciated. Mr Peter Kleffmann, without whose persistence the remaining copy would not have been located. Mr Hans Decker, who enthusiastically supported this translation venture and provided the fascinating background history (of which just the surface was scratched in this foreword). Mr Decker also enabled us to contact Mr Kraus and to obtain the copyright permissions for this translation. Lastly, Mr Juergen Kraus, whom I had the pleasure of meeting at the 25th anniversary of Computer Science at the University of Dortmund in November 2007. He gave a didactically outstanding presentation. I remember recalling wistfully von Hofmannsthal

"Wie wunderbar sind diese Wesen,
Die, was nicht deutbar, dennoch deuten,
Was nie geschrieben wurde, lesen,
Verworrenes beherrschend binden
Und Wege noch im Ewig- Dunkeln finden."

We hope you, the readers, will agree.

Foreword

Jürgen Kraus

This foreword was translated from German by the editors Daniel Bilar and Eric Filiol (corresponding editor: efiliol@wanadoo.fr)

Let us take a scroll down memory lane; some twenty-eight years to be exact.

In 1980 — the year in which Ronald Reagan had just been elected 40th President of the United States — we find the Cold War still very much ongoing and Java synonimous with an island in the Indian Ocean. Adolescents had not yet had their spatial acuity tested by Rubic's Cube, and you could be fairly certain that chess skills were measured solely against other carbon-based bipeds.

In 1980, most computers were behemoths, so-called main-frames, whose gargantuan dimensions filled entire halls. However, one could discern the first stirrings of change, with home computers like the Atari 400 or the Sinclair ZX80 appearing. What we call our present day Internet was slowly developing from the US DoD's ARPANET project. The poster child of the personal computer era, the IBM PC, was to be launched a mere year later.

In 1980, the University of Dortmund was also about to graduate me in Computer Science; in those days a field still in its infancy.

My studies comprised in roughly equal parts theoretical and practical subjects; though I had always felt especially drawn to theoretical vantage points. You may ask why: On the one hand , the bromide of theory revealing the essence of things by virtue of material detachment rang true to me, on the other hand, I did minor in mathematics.

Though exams were tedious, I needed to hand in thesis to graduate; this pre-supposed my finding a topic first. Here is where my penchant for theory paid off handsomely: I had been auditing the course "Recursive Functions" in the Winter semester 1978/1979, taugh by Prof. Volker Claus, one of Germany's outstanding computer science pioneers. I approached Prof Claus in my search for a thesis topic. His suggestions revolved around computability and recursive functions, which helped crystallize the following question: Is it possible to construct self-reproducing programs, and can we analyze their algorithmic complexity and the function classes these programs realize?

The impetus for this particular line of investigation lay in Prof Claus' visionary ideas: "If one conceives of a computer system (in a feat of futuristic abstraction) as an artificial world, we may search for life-like processes therein. Computer programs may be cast in the role of simple living things as long as they evince defining traits such as mutation, reproduction and metabolism; roughly analogous to their biological counterparts."

In the mind of an euphoric student, a thesis on self-reproducing programs represented no less than the quest for life in a primordial computer soup consisting of ones and zeroes. It also obviate the need to fly to Mars to find little green men — and happily, to substitute astronaut food for donuts and to subject oneself to space radiation. After all, the computer system might be harboring creatures just waiting to be discovered by yours truly.

Hence, I adopted the topic. I did this in full knowledge that the existence of self-reproducing programs (also in higher level language) followed by necessity from Kleene's recursion theorem, but that, in practice, actual construction using said theorem would have to fail. I had to find a way, my own way — that was the challenge.

To cut to the chase, the thesis' goals were met in that self-reproducing programs in higher level programming languages were constructed and their properties investigated. It turned out that self-reproducing properties could be formulated with relative few lines of code and simple algorithmic (loop1) complexity. Of particular importance was the realization that self-reproducing programs could be enhanced by arbitrary — possibly harmful — functions while maintaining their self-reproductive capabilities. Put another way, in addition to their harmful functionality, malicious programs could have self-reproduction added to their repertoire, thereby significantly increasing reach and noxiousness.

Compared to biological organisms, however, self-reproducing programs lack a metabolism. As such, they can at most be classified as viruses. It seems that little green men are yet more likely to be found on Mars or in some other galaxy.

Thus, already in 1980, self-reproducing programs with noxious capabilities described the notion of a "computer virus", albeit unwittingly and without appreciating the notoriety the subject would achieve in years to come.

After receiving my Master's from the University of Dortmund and starting my corporate career end of 1980, I could therefore not have anticipated running into my old thesis "On Self-Reproducing Programs" over and over again. Quite a few articles on computer viruses referenced my work. As far as I know, the first in-depth discussion appeared in Ralph Burger's "Das Grosse Computerbuch" (Data Becker 1987). He found it remarkable that on the one hand, it predated Fred Cohen's "Computer Viruses — Theory and Experiments" (University of Southern California 1983) by roughly four years. On the other hand, the treaties had remained virtually uknown to the general public. Though not missing or lost, it was only accessible via the University (todat Technical University) of Dortmund.

The relative obscurity has come to an end, in part thanks to Daniel Bilar, a promising young scientist at the Univeristy of New Orleans. He had heard abouth the thesis in the course of his investigating metamorphic computer viruses. He queried for and obtained — after some determined efforts — a copy from Dortmund. He then enthusiastically announced to the Dortmund Department of Computer Science his intentions to make an English translation available: His colleague, fellow translator and editor-in-chief Eric Filiol would publish it in the leading specialized academic computer virology journal, "The Journal in Computer Virology" (Springer Paris). With pleasure, I agreed to this endeavor. To have the treatise "on Self-Reproducing Programs" republished, after almost thirty years, is after all a very special honor.

Hagen, November 2008 Jürgen Kraus

2 The suppression is not completely without merit: The US NSA did try to forbid the publication of Schneier's Applied Cryptography in the 1990s and in the 1980s, the German Federal Intelligence Services were particularly interested in the power of computer viruses. Pars pro toto, we mention Stoessel and the BND's Rahab project.