Theppitak's blog

My personal blog.

25 มิถุนายน 2547

Self Source Printing Program

เห็นเรื่อง Obfuscated C จาก blog คุณพูลลาภ แล้ว ทำให้นึกถึง brain teaser ข้อหนึ่งที่เคยเล่นกันสมัยเรียนตรี คือโปรแกรมที่ print source code ตัวเอง

เริ่มจาก พี่ปริญญาโทยกเอา Russel’s paradox มาเกริ่นก่อน ว่า logic ใดๆ ที่ย้อนเข้าหาตัวเองแบบนิเสธ จะกลายเป็น paradox (เรียกว่าเป็นความไม่สมบูรณ์ของระบบ) เช่น บอกว่า “ช่างตัดผมคนเดียวในหมู่บ้าน จะไม่โกนหนวดให้กับคนที่โกนหนวดเอง” เมื่อย้อนถามว่า “ถ้าเช่นนั้น ช่างตัดผมคนนี้ จะโกนหนวดตัวเองหรือเปล่า?” ก็จะหาคำตอบไม่ได้ทันที หรืออีกตัวอย่างหนึ่งคือ คำพูดที่ว่า “ผมโกหกเสมอ” เป็นจริงหรือเท็จ? เรื่องนี้ พอเข้าเนคเทค ก็มีน้องคนหนึ่งมาชวนคุยอีก คราวนี้โยงไปถึง Gödel ด้วย สนุกดีเหมือนกัน

สิ่งที่ Bertrand Russel เสนอคือ “ถ้า A เป็นเซ็ตของเซ็ตที่ไม่รวมตัวเอง ถามว่า จริงๆ แล้ว A รวมตัวเองหรือไม่?” หรือเขียนเป็นทางการหน่อยก็ “ถ้า A = { x | x ∉ x } ถามว่า จริงๆ แล้ว A ∈ A หรือไม่” ซึ่งตอบลำบาก เพราะถ้า A ∉ A ก็แปลว่า A สอดคล้องกับเงื่อนไขของเซ็ต และได้ว่า A ∈ A ในทางกลับกัน ถ้า A ∈ A ก็ขัดกับเงื่อนไขของเซ็ต ซึ่งหมายความว่า A ∉ A)

เกริ่นมาจนงงขนาดนี้ (เหมือนนักเล่นกล ต้องอ้างสิ่งลึกลับไว้ก่อน) แล้วก็ถามว่า “ถ้าเช่นนั้น โปรแกรมที่พิมพ์ซอร์สโค้ดตัวเองมีอยู่จริงหรือไม่?” กล่าวคือ สมมุติโปรแกรมที่ว่าคือ self.c มันควรทำเช่นนี้ได้ โดยห้ามอ่าน external input ใดๆ :

$ cc -o self self.c
$ ./self | diff -u - self.c
$ ./self > clone.c
$ cc -o clone clone.c
$ ./clone | diff -u - clone.c
$ ...

เขียนกันไปเขียนกันมา จะพบปัญหาไก่กับไข่อย่างแท้จริง แต่ก็มี trick บางอย่างทำให้ดิ้นออกมาได้ เรียกว่าได้แบบแฮ็กๆ โปรแกรมไม่ portable อะไร ใครอยากลองเขียนก็ลองดูได้ แต่ถ้าเขียน C program ที่ portable ได้ ช่วยบอกผมด้วย

11 ความเห็น:

  • 25 มิถุนายน 2547 เวลา 12:19 , Blogger Thep แถลง…

    ตัวอย่าง non-portable program (ASCII-assumed) :

    char*a="main() {printf(";
    char*b="char*a=%c%s%c;%cchar*b=%c%s%c;%cchar*c=%c%s%c;%c%sb%s%c";
    char*c=",34,a,34,10,34,b,34,10,34,c,34,10,a,c,10);}";
    main() {printf(b,34,a,34,10,34,b,34,10,34,c,34,10,a,c,10);}

     
  • 25 มิถุนายน 2547 เวลา 13:58 , Anonymous ไม่ระบุชื่อ แถลง…

    พวก script language น่าจะ self-printing codeได้ง่ายๆนะ
    อย่าง shell-scriptหรือ perl

    densin

     
  • 25 มิถุนายน 2547 เวลา 17:23 , Anonymous ไม่ระบุชื่อ แถลง…

    เอามาจากเวบของ Doug Ross<?$p = '<?$p = %c%s%c; printf($p,39,$p,39);?>'; printf($p,39,$p,39);?>

     
  • 27 มิถุนายน 2547 เวลา 01:17 , Anonymous ไม่ระบุชื่อ แถลง…

    อานนท์ said…

    ที่ว่า ไม่ portable นี่ คือ เกี่ยวกับ รหัส ascii รึเปล่า ครับ?

    เรื่อง การ ใช้ escape character ของ \" \n น่า จะ แก้ หยั่งงี้ ได้ (คิด นาน เหมือนกัน, ขับ มอไซค์ ไป คิด ไป).


    char a[]="char a[]=\"%s\";\nmain(){\n char b[sizeof(a)*2];\n char*p1=a;char*p2=b;for(;*p1;++p1,++p2){\n if(*p1=='\\\"'||*p1=='\\\\'){*p2='\\\\';*++p2=*p1;}\n else if(*p1=='\\n'){*p2='\\\\';*++p2='n';}\n else *p2=*p1;\n };*p2='\\0';\n printf(a,b);\n};\n";
    main(){
    char b[sizeof(a)*2];
    char*p1=a;char*p2=b;for(;*p1;++p1,++p2){
    if(*p1=='\"'||*p1=='\\'){*p2='\\';*++p2=*p1;}
    else if(*p1=='\n'){*p2='\\';*++p2='n';}
    else *p2=*p1;
    };*p2='\0';
    printf(a,b);
    };


    ans@localhost:~ >gcc self_print.c
    ans@localhost:~ >md5sum self_print.c
    d57dffcb87406715729c5f7786256bfe self_print.c
    ans@localhost:~ >./a.out | md5sum
    d57dffcb87406715729c5f7786256bfe -
    ans@localhost:~ >./a.out | cmp self_print.c -
    ans@localhost:~ >


    indent ผมใช้ 3 space อะ, แต่ html มันไม่แสดง.

     
  • 27 มิถุนายน 2547 เวลา 01:44 , Anonymous ไม่ระบุชื่อ แถลง…

    อานนท์ said…

    char a[]="char a[]=\"%s\";\nmain(){\n char ...";
    ประโยค ข้างบน อันนี้ ก็ อยู่ บรรทัด เดียว กัน หมด, ไม่ได้ ปัด ขึ้น บรรทัด ใหม่ อย่าง ที่ เห็น ใน html

     
  • 27 มิถุนายน 2547 เวลา 01:59 , Anonymous ไม่ระบุชื่อ แถลง…

    อานนท์ said...

    จริง ๆ ตอน ที่ เขียน โปรแกรม ข้างบน นี้, ตอน เขียน ประโยค ที่ ว่า *p1=='\"', ก็ เพิ่ง สังเกต ว่า '\"' มัน เขียน '"' หยั่งงี้ ก็ ได้ นี่ หว่า.
    ก็ เลย ได้ วิธี ที่ ง่าย กว่าเดิม, ใน กรณี ที่ เรา ไม่ใช้ newline แล้ว ก็ ไม่ใส่ newline ตรงท้าย บรรทัด สุดท้าย ของ โปรแกรม ด้วย.

    char*a="char*a=%c%s%c;char c='%c';main(){printf(a,c,a,c,c);};";char c='"';main(){printf(a,c,a,c,c);};

     
  • 27 มิถุนายน 2547 เวลา 09:55 , Blogger Thep แถลง…

    เย่.. ปรบมือให้กับคุณอานนท์ ☺ จริงๆ โปรแกรมแบบบรรทัดเดียวผมก็เขียนไว้เหมือนกัน แต่ยังไม่สั้นเท่าของคุณอานนท์ ก็ติดปัญหาตรงที่ diff มันจะฟ้องตอนเปรียบเทียบ ว่าต่างกันเรื่อง newline at end of line น่ะครับ

     
  • 28 มิถุนายน 2547 เวลา 17:45 , Anonymous ไม่ระบุชื่อ แถลง…

    char*a="char*a=%c%s%c;%cchar c='%c'; char n='%cn'; char b='%c%c';%cmain(){%c printf(a,c,a,c,n,c,b,b,b,n,n,n,n);%c};%c";
    char c='"'; char n='\n'; char b='\\';
    main(){
    printf(a,c,a,c,n,c,b,b,b,n,n,n,n);
    };

    เอา ใหม่, คราวนี้ มี newline ได้ ด้วย, แถม ไม่ต้อง วน loop parse string อะไร น่าเบื่อ ๆ.

     
  • 28 มิถุนายน 2547 เวลา 17:58 , Anonymous ไม่ระบุชื่อ แถลง…

    อานนท์ Said...

    อ้าว, อัน ข้างบน นี้ ลืม ใส่ ชื่อ.

     
  • 28 มิถุนายน 2547 เวลา 18:07 , Anonymous ไม่ระบุชื่อ แถลง…

    อานนท์ said...

    self source printing, จริง ๆ ผม เขียน ไม่ได้ หรอก นะ, ถ้า ไม่ได้ เห็น ไอเดีย ของ โปรแกรม คุณเทพ.
    (จริง ๆ ก่อนหน้านี้ เคย เห็น ของ รุ่นน้อง มา ก่อน, ซึ่ง ก็ ใช้ วิธี เดียว กับ คุณเทพ แหละ)

     
  • 2 ธันวาคม 2557 เวลา 14:08 , Blogger nz แถลง…

    เพิ่งรู้ว่าปัญหาแนวนี้มีชื่อเฉพาะเรียกว่า Quine https://en.wikipedia.org/wiki/Quine_%28computing%29

     

แสดงความเห็น (มีการกลั่นกรองสำหรับ blog ที่เก่ากว่า 14 วัน)

<< กลับหน้าแรก

hacker emblem