Self-reproducing program in Ken Thompson's Turing paper

Discussion in 'C Programming' started by lovecreatesbea...@gmail.com, May 10, 2007.

  1. Guest

    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, 2007
    #1
    1. Advertising

  2. <> 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?


    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.
    Christopher Benson-Manica, May 10, 2007
    #2
    1. Advertising

  3. On May 10, 11:23 am, ""
    <> 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?


    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
    William Hughes, May 10, 2007
    #3
  4. Bill Pursell Guest

    Bill Pursell, May 10, 2007
    #4
  5. "" <> writes:
    > 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) <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"
    Keith Thompson, May 10, 2007
    #5
  6. Lew Pitcher Guest

    On May 10, 11:23 am, ""
    <> 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?


    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
    Lew Pitcher, May 10, 2007
    #6
  7. Richard Bos Guest

    Lew Pitcher <> wrote:

    > 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
    Richard Bos, May 11, 2007
    #7
  8. Army1987 Guest

    "Lew Pitcher" <> ha scritto nel messaggio
    news:...
    > On May 10, 11:23 am, ""
    > <> 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?

    >
    > 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]);
    }
    Army1987, May 11, 2007
    #8
  9. Tor Rustad Guest

    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
    Tor Rustad, May 17, 2007
    #9
  10. Tor Rustad Guest

    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>
    Tor Rustad, May 17, 2007
    #10
  11. Tor Rustad <torust_at_online.no> writes:
    > 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) <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"
    Keith Thompson, May 18, 2007
    #11
  12. Tor Rustad Guest

    [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>
    Tor Rustad, May 18, 2007
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ralf W. Grosse-Kunstleve
    Replies:
    16
    Views:
    561
    Lonnie Princehouse
    Jul 11, 2005
  2. Ralf W. Grosse-Kunstleve
    Replies:
    18
    Views:
    582
    Bengt Richter
    Jul 11, 2005
  3. Ralf W. Grosse-Kunstleve
    Replies:
    2
    Views:
    390
    Dan Sommers
    Jul 12, 2005
  4. Sweety

    Is any self reproducing code in C ?

    Sweety, Aug 23, 2004, in forum: C Programming
    Replies:
    6
    Views:
    401
    bogonic
    Aug 26, 2004
  5. pemo
    Replies:
    2
    Views:
    490
    Richard Bos
    Jan 18, 2006
Loading...

Share This Page