點我展開解答
subtask=0
首先,既然輸出 secret 的方式是 puts,而 puts 是 buffered I/O,所以或許可以想辦法拿到 buffer 的內容。
在通常狀況下要拿到 C stdio 的 buffer 內容還算簡單,C 裡面有提供一個 setbuf 函數,只要自己開一塊記憶體然後 setbuf,之後 buffer 的內容就會在那一塊記憶體裡面。然而我們目前只有 meow 一個函數可以用,看起來好像沒辦法一開始先 setbuf,而且 call meow 的時機點 secret1 根本還沒被 output,那該怎麼處理呢?
其實我們是可以在 main 函數執行前後做事情的!main 之前的部分,當我們用 C++ 宣告一個全域變數,這個變數的 constructor 就會在 main 之前執行;或者 C 也可以用 __attribute__ ((constructor))
做到這件事。main 之後的部分一樣可以用全域變數的 destructor,或者用 C 提供的 atexit 函數註冊需要在 exit 前(main 執行完之後)執行的程式。
知道這兩件事情拿這個 subtask 就很簡單了。在 main 之前先 setbuf,然後 main 之後把 buffer 裡面的兩個字串反過來,這樣就 AC 了!
加分題 subtask=1
這個 subtask 因為最後有 flush 的關係,我們沒有辦法在 atexit 拿到 secret1 了。有人或許會想到可以直接換成改程式輸出的檔案,這招在以前的 TIOJ 是有效的,但是提示也告訴你 strict mode 是個有點邪惡的東西 (?)
如果照提示去 TIOJ web server repo 搜尋「strict mode」、或者直接在 tioj-judge repo 看 README,會找到 strict mode 的說明。其中一個功能是輸出不再是一個檔案而是一個 pipe,這代表資料一但 flush 出去就沒辦法修改了!
然而換個方式想,如果不是對 output 做事情,而是對 input 呢?因為是用 scanf 讀檔,所以如果能讓 scanf 吃到 subtask=0 就跟前面一個 subtask 做法一樣了!而要動 input buffer 也十分簡單,直接呼叫 ungetc 把 0 塞進去就可以了。
加分題 subtask=1 另解一
這個做法會利用一些對執行檔的知識。在執行檔中,字串常數會被放在執行檔中的 data section(具體來說是 ELF 的 .rodata section),而在執行時執行檔本身也在記憶體當中。因此,我們可以嘗試在記憶體裡面找這兩個 secret string 到底放在哪裡,然後拿指標指向 secret string,就可以手動 puts 了。這件事情可以放在 constructor 裡面,輸出完直接 exit 掉,這樣就不會執行 main 而輸出多餘的東西了。
但是 data section 具體來說在哪裡呢?最簡單的方法是自己隨便宣告一個有初始化的陣列(例如const char arr[]="1";
之類的),這個陣列會被放在 data section 當中。然後就在這個指標前後戳一戳,找到長度為 30 或 24 的字串各一個就可以了!因為 C string 都會以 NUL byte 做結尾,然後這題沒有刻意在 data section 裡面放一些奇怪的東西,所以只要判斷長度基本上就可以找到正確的 secret。
加分題 subtask=1 另解二
這個做法就比較偏黑魔法一些(?
既然問題在 fflush,那有沒有辦法改一些 stdout 內部的東西讓它不要 fflush 呢?如果去看一下 libc stdio 裡面的實作,會發現 stdout 的 struct 裡面跟 buffer 有關的東西有幾個:_IO_write_base
、_IO_write_end
和_IO_write_ptr
,前兩個是 buffer 的頭尾、最後一個是代表現在 buffer 被填滿到哪個地方。基本上在寫東西進 buffer 的時候就是動 _IO_write_ptr
,然後在 flush 的時候就是把從 _IO_write_base
到 _IO_write_ptr
的部分輸出出來。因此如果我們把 _IO_write_base
暫時往後挪到最後 _IO_write_ptr
會在的地方(其實就是原本的 _IO_write_base
加上兩個 secret 和兩個換行字元的長度),這樣 flush 就相當於沒有做事了!如此只要在 constructor 或在 meow 裡面做這件事,就可以在 atexit 裡面自己把 buffer 裡面的東西重排後輸出了。
加分題 subtask=2
這個 subtask 就更邪惡了。連 output 具體來說是用什麼方法都沒有告訴你,這該怎麼辦呢?
既然沒辦法改程式輸出的檔案,有沒有辦法讓程式 output 到一個檔案,然後在 atexit 再輸出到真正的 output 呢?我們可以把原本在 stdout 的 pipe 透過 dup system call 放到別的 file descriptor 去,然後把 stdout 換成一個自己開的檔案,這樣在 atexit 就可以從那個檔案拿到所有的輸出了。
然而 strict mode 還有另外一個限制:它會把 permission 設成讓程式沒有辦法新增任何檔案!不過這個問題也不算太難解決,畢竟 strict mode 本身就是用 pipe 實作的,何不自己也開一個 pipe 呢?因此就把一個 pipe 的 input 端放到 stdout,最後再從 pipe 的 output 端把資料讀出來改完輸出就可以了。
不過你如果直接這樣寫然後改最前面的順序的話還是會得到 WA,因為 mysterious 裡面除了 puts 等類的 buffer I/O 以外,還有一些 write,所以這些 write 的 output 會跑到所有用 puts 輸出的資料(包含 secret1&2)的前面。不過這也不要緊,因為在 fflush 之後 buffer 裡面的資料還是會留著,而 mysterious 裡面沒有 fflush,所以拿 buffer 裡面的資料跟 pipe 裡面的資料對比一下就可以知道哪個部分開始是 puts 產生的資料,而 puts 資料的一開始就是要交換順序的兩個 secret 了。
這個做法有個限制是輸出的量不能超過 pipe buffer size(64 KiB),不過這題 mysterious 的輸出沒有很多,所以不會有問題。
加分題 subtask=2 另解一
subtask=1 的另解二其實也可以直接用到這個 subtask 上。只要想辦法 assert 出 buffered output 部分的總輸出量(可以利用時間或記憶體一次得到更多資訊),就同樣可以讓 fflush 失效了。因為 unbuffered 的部分本來就會在最前面,所以不用動它直接讓它輸出出去沒有問題,一樣在 atexit 之後把 buffered 的部分讀出來重排之後輸出即可。
加分題 subtask=2 另解二
這個是最黑魔法的做法,但也是最通用的做法,就算 mysterious 輸出爆 pipe、爆 buffer 或者交替做 fflush 等奇怪的事情都還是可以不做任何修改直接用。
其實如果 mysterious 沒有宣告成 static、可以拿到 mysterious 的 function pointer 的話,這題就會很簡單了:先用 subtask=1 的做法先 puts 好 secret 1&2,然後直接 call mysterious 就解決了。不幸的是,因為 mysterious 被宣告成 static,compiler 會直接把它 inline 優化掉放在 main 裡面,所以根本就不存在 mysterious 這個函數的 function pointer!
那麼我們可不可以把 main 函數改成 mysterious 呢?畢竟一方面 main 拿掉前面的部分就是 mysterious,而且 main 函數的 function pointer 非常好拿,直接 forward declare int main();
就可以直接取它的位址了。答案也是肯定的,不過這裡就會需要來看一小點 assembly。
因為我們只想要 mysterious 的部分,所以最簡單的作法是把 main 函數中 puts secret1&2 的部分拿掉。如果把題敘給的程式拿來,隨便填入 secret1&2 和 mysterious,然後自己把程式 compile 出來(因為是用 strict mode,所以實際上會用 static compile,但因為這裡只是要看一下程式長什麼樣子所以不太有差)用 objdump 之類的工具看一下,會發現 main 函數的開頭大概會像這樣:
00000000004019c0 <main>:
4019c0: f3 0f 1e fa endbr64
4019c4: 48 83 ec 18 sub $0x18,%rsp
4019c8: 48 8d 3d 41 46 0b 00 lea 0xb4641(%rip),%rdi # 4b6010 <_ZL7secret2>
4019cf: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
4019d6: 00 00
4019d8: 48 89 44 24 08 mov %rax,0x8(%rsp)
4019dd: 31 c0 xor %eax,%eax
4019df: e8 dc 2a 01 00 call 4144c0 <_IO_puts>
4019e4: e8 a7 01 00 00 call 401b90 <_Z4meowv>
4019e9: 48 8d 3d 40 46 0b 00 lea 0xb4640(%rip),%rdi # 4b6030 <_ZL7secret1>
4019f0: e8 cb 2a 01 00 call 4144c0 <_IO_puts>
(接下來是 scanf 和 mysterious 裡面的東西)
會發現 call_meow 和 AC 兩個函數也被優化掉了,所以 main 函數看起來就是 call puts(secret2)、call meow() 然後 call puts(secret1)(分別是 4019df、4019e4、4019f0 那行),所以需要想辦法把兩個 puts 改成不會做事情的程式。最簡單的方法是把它全部覆蓋成 NOP instruction,這在 x86_64 裡面是 0x90 這個 byte。
所以理論上,只要從 main 函數的 function pointer 開始找,找到前三個 call instruction 然後把它們全部改成 0x90,這樣就相當於直接把第 19 行拿掉了。也就是說,只要把前一個 subtask 的程式拿來,在輸出 secret1&2 後把 main 改掉,然後不要 exit 讓程式繼續執行下去,就能拿到整題 AC 100 了!
不過最後還有一個問題:如果你直接用一個指標指進 main 裡面然後嘗試改它的值,你會拿到一個 SIG(實際上是 Segmentation Fault),因為執行檔部分的 page 預設是不能寫入的。然而這個可以被 mprotect system call 改變,只要把包含 main 的那個 page 設成 PROT_READ | PROT_WRITE | PROT_EXEC
就可以寫入這段記憶體了。一個細節是呼叫 mprotect 的參數必須要剛好是 page 開頭,所以呼叫 mprotect 的參數要是 (void*)((long)main / 4096 * 4096)
。
還有一個實作上的小問題是要怎麼找到前三個 call instruction。理論上這會需要寫一個簡易的 x86 parser,不過因為剛好這題前面的 instruction 裡面都不包含 0xe8 這個 byte(0xe8 是 call 的 opcode),所以只要找 0xe8 這個 byte 然後把它起算的 5 bytes 改成 0x90 就可以了。另外,在讀寫 main 的時候最好把指標宣告成 volatile,否則有可能會被邪惡的編譯器優化把奇怪的東西優化掉(?
加分題 subtask=2 另解三
另外一個可行的想法是我們或許可以中斷程式的執行,想辦法卡在 mysterious 還沒有執行的時候去改 buffer,再讓程式正常執行下去,而 signal 就是一個中斷程式執行的好方法。不過因為執行的時候不允許 multithread,唯一可以延遲送 signal 給自己的方法就只有 alarm 了。具體來說,我們可以先設一個 signal handler 之後,用 setitimer 設一個頻率很高的 alarm,在 handler 執行時如果發現 main 已經 puts 完 secret1(可以從 buffer 長度檢查),就照 subtask=0 的做法改完 buffer 後讓 main 繼續跑完。這樣子如果在改 buffer 的時間點還沒跑到 mysterious,就可以得到正確的 output。
新功能
這題主要用到的新功能有兩個:
(1) 每個題目現在都有自己的討論區了!
(2) 整個 submission 的 verdict 可以略過某些 testdata,所以像這題後面兩個 subtask 就算沒有做,整題也可以 AC。
(1) 可以選擇 strict mode,這樣就不能對輸入輸出檔做一些奇怪的事情。
(2) 以前 Interactive library 只能寫一個 header,現在可以寫實作檔然後跟 submission link 在一起執行。
(3) 這題是採用 bytewise compare,即輸出任何多餘空白換行都會視為 WA。以前要做這件事要自己寫一個 special judge,現在只要加一個參數給 default compare program 就好了。