469,592 Members | 1,713 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,592 developers. It's quick & easy.

Self-reproducing program in Ken Thompson's Turing paper

Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing paper,
http://www.acm.org/classics/sep95/ . Can this be done in C? How can a
program at runtime know its compiling-time source code?

May 10 '07 #1
11 3758
lovecreatesbea...@gmail.com <lo***************@gmail.comwrote:
Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing paper,
http://www.acm.org/classics/sep95/ . Can this be done in C? How can a
program at runtime know its compiling-time source code?
Sure.

#include <stdlib.h>

int main( void ) {
system( "links http://www.google.com" ); /* On DS9K, may open "link"
to the Underdark, beware */
return 0;
}

Surely you've posted here often enough to know that you'll get "STFW"
for an answer to this question? Certainly quines have been discussed
many times on this very newsgroup.

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
May 10 '07 #2
On May 10, 11:23 am, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.comwrote:
Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing paper,http://www.acm.org/classics/sep95/. Can this be done in C?
Gosh, I don't know. Maybe I should do a web search, or check the FAQ
or try to run the
strange looking code that shows up in people's signatures.
How can a
program at runtime know its compiling-time source code?
In general it can't, but most programs are not self-reproducing..
However, given that the runtime is a function of the source code,
maybe it
would be possible to choose the source code so that the runtime
prints out this source code. Maybe I should do a web search, or check
the FAQ or try to run the
strange looking code that shows up in people's signatures.

--
William Hughes

10 LIST

May 10 '07 #3
On 10 May, 16:23, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.comwrote:
Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing paper,http://www.acm.org/classics/sep95/. Can this be done in C? How can a
program at runtime know its compiling-time source code?

http://www.nyx.net/~gthompso/quine.htm
May 10 '07 #4
"lovecreatesbea...@gmail.com" <lo***************@gmail.comwrites:
Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing paper,
http://www.acm.org/classics/sep95/ . Can this be done in C? How can a
program at runtime know its compiling-time source code?
The comp.lang.c FAQ is at <http://www.c-faq.com/>. You've just asked
question 20.34.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
May 10 '07 #5
On May 10, 11:23 am, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.comwrote:
Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing paper,http://www.acm.org/classics/sep95/. Can this be done in C? How can a
program at runtime know its compiling-time source code?
Others have pointed you at various resources wrt writing C quines.
They have answered your basic question.

But, if that's all you got out of Ken T's paper, then you missed a
lot.

His paper wasn't so much about quines as stand-alone programs, but
with the potential security exposures that quines (when incorporated
into C compilers) could have. He pointed out that a compiler could
imbed a trap-door security breach into anything it compiles, and (if
the compiler was compiled with itself), that trap-door could be
hidden /in the program/ rather than in the source code.

The quine comes from the compiler compiling in the security breach
insertion code into the (2nd generation) compiler - a quine in object
code rather than a quine in source code.

--
Lew

May 10 '07 #6
Lew Pitcher <lp******@teksavvy.comwrote:
But, if that's all you got out of Ken T's paper, then you missed a
lot.

His paper wasn't so much about quines as stand-alone programs, but
with the potential security exposures that quines (when incorporated
into C compilers) could have. He pointed out that a compiler could
imbed a trap-door security breach into anything it compiles, and (if
the compiler was compiled with itself), that trap-door could be
hidden /in the program/ rather than in the source code.
Mind you, that trap-door only works if you assume that the compiler will
only be used to compile itself. It doesn't work if you use it to compile
an unrelated compiler of another language, which is used to compile a
cross-compiler of a language using another paradigm, which is used to
compile - for a different CPU - an interpreter for yet another language,
which is used to interpret a re-cross-compiler of the original language.
Bonus points if any of the architectures involved is completely virtual;
more bonus points if any of the languages was designed specifically for
this purpose.

Richard
May 11 '07 #7

"Lew Pitcher" <lp******@teksavvy.comha scritto nel messaggio
news:11**********************@u30g2000hsc.googlegr oups.com...
On May 10, 11:23 am, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.comwrote:
>Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing
paper,http://www.acm.org/classics/sep95/. Can this be done in C? How can
a
program at runtime know its compiling-time source code?

Others have pointed you at various resources wrt writing C quines.
They have answered your basic question.

But, if that's all you got out of Ken T's paper, then you missed a
lot.

His paper wasn't so much about quines as stand-alone programs, but
with the potential security exposures that quines (when incorporated
into C compilers) could have. He pointed out that a compiler could
imbed a trap-door security breach into anything it compiles, and (if
the compiler was compiled with itself), that trap-door could be
hidden /in the program/ rather than in the source code.

The quine comes from the compiler compiling in the security breach
insertion code into the (2nd generation) compiler - a quine in object
code rather than a quine in source code.
Huh?

--
#include <stdlib.h>
int main(int argc, char *argv[])
{
return system(argv[0]);
}
May 11 '07 #8
Richard Bos wrote:
>
Mind you, that trap-door only works if you assume that the compiler will
only be used to compile itself.
Only??! It will work in more cases than that.

The seriousness here, is that system programs are typically written in
C, and C compilers are typically written in C.

If you develop a new C compiler, and use the infected compiler when
bootstrapping, the backdoor will be inherited. Also, if you create a C
cross compiler, the backdoor will be passed forward.

The payload, can even be targeted for multiple platforms.
--
Tor
May 17 '07 #9
lovecreatesbea...@gmail.com wrote:
Ken Thompson mentioned a self-reproducing program that products an
exact copy of its source code as output in his 1983 Turing paper,
http://www.acm.org/classics/sep95/ . Can this be done in C? How can a
program at runtime know its compiling-time source code?
This is a brilliant paper, read it carefully.I have given this puzzle to
student/junior programmers, multiple times.

If you really want to learn something, try hard to solve this puzzle in
C yourself. Seeing a solution, gives you little.
--
Tor <torust [at] online [dot] no>
May 17 '07 #10
Tor Rustad <torust_at_online.nowrites:
Richard Bos wrote:
>Mind you, that trap-door only works if you assume that the compiler
will
only be used to compile itself.

Only??! It will work in more cases than that.

The seriousness here, is that system programs are typically written in
C, and C compilers are typically written in C.

If you develop a new C compiler, and use the infected compiler when
bootstrapping, the backdoor will be inherited. Also, if you create a C
cross compiler, the backdoor will be passed forward.
If I recall correctly (and it's entirely possible I don't), that's
unlikely. The trapdoor works by recognizing a certain piece of the
code being compiled, and generating special output in response to it.
An independently developed cpomiler is unlikely to contain anything
matching that pattern.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
May 18 '07 #11
[Can't see my response, this is a repost & possibly a duplicate message]

Keith Thompson wrote:
>
If I recall correctly (and it's entirely possible I don't), that's
unlikely. The trapdoor works by recognizing a certain piece of the
code being compiled, and generating special output in response to it.
Right. There are two parts, the "back door" and the "infecter". The back
door is targeted for some security sensitive software, e.g. SSH, while
the "infecter" is targeted the compiler, which will later be used to
compile e.g. SSH.
An independently developed cpomiler is unlikely to contain anything
matching that pattern.
Normally, compilers these days are not hand-coded, tools like lex & yacc
generate some of the C code of the compiler. These tools will leave a
signature. I have not done any prototyping of this, but it should not be
that hard to detect tokens like e.g. yyparse for the infecter.

--
Tor <torust [at] online [dot] no>
May 18 '07 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

15 posts views Thread by Ralf W. Grosse-Kunstleve | last post: by
4 posts views Thread by David Coffin | last post: by
4 posts views Thread by marek.rocki | last post: by
7 posts views Thread by Andrew Robert | last post: by
24 posts views Thread by Peter Maas | last post: by
84 posts views Thread by braver | last post: by
13 posts views Thread by Kurda Yon | last post: by
reply views Thread by suresh191 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.