Robust UDP Challenge - 網路程式設計概論
<h1 id="recap">前情提要</h1> <p>這學期修習黃俊穎老師開設的網路程式設計概論(網程設),前半學期教了如何用 TCP 從簡單的 socket 應用,到實作較為複雜的 IRC 伺服器。</p> <p>這次第 12 周的實驗內容讓大家用兩週的時間,寫出能抵抗惡劣網路環境的 UDP 程式,完整傳送 1,000 個平均 16 KB 的檔案。</p> <h2 id="limit">實驗限制</h2> <p>這次評測端使用 <a href="https://man7.org/linux/man-pages/man8/tc-netem.8.html" target="_blank">tc-netem (8)</a> 製造出不穩定的網路環境,限制如下:</p> <ul> <li>封包有 40% 機率會遺失、10% 機率損毀</li> <li>延遲 50 ms - 150 ms</li> <li>網速上限 10 Mbps</li> <li>封包大小上限 1,500 bytes</li> </ul> <p>在這樣的環境下,如果不特別做處理,基本上是傳不了檔案的,也因此是考驗各組技術的地方。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/netem-ping.png" alt="使用 ping 測試的結果(封包來回需乘二)" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">使用 ping 測試的結果(封包來回需乘二)</td> </tr> </tbody> </table> <h2 id="init">最初的想法</h2> <p>在開始寫程式之前,當然是要先設計自己的通訊協定原型。原本規劃好了整套如何取得目錄、如何得知檔名及內容的協議,不過愈想愈覺得在這次的實驗中,分檔案慢慢傳反而沒效率。</p> <p>因此後來決定把寫好的協議及寫到一半的程式碼全部刪掉,從頭開始設計當成單一檔案傳輸的方法。</p> <h1 id="format">封包結構</h1> <p>實驗環境 MTU 只允許每個封包傳送至多 1,500 bytes 的內容,因此會需要切成不同區塊,本次設計的封包結構前 2 bytes 是區塊編號。<br /> 每個小封包扣掉 IP 層標頭的 20 bytes 及 UDP 層標頭的 8 bytes,再扣掉 2 bytes 的區塊編號後,共有 1,470 bytes 可供存放資料。</p> <p>在我的作法中,是先合併出一個大封包。大封包最前面的數字是總區塊數,後面接著 1,000 個數字是各檔案的尺寸,再來各檔案內容直接連接在後,以節省填充內容佔用的空間。</p> <p>也因為老師保證檔案大小在 32,000 bytes 以下,最極端的例子封包數也不會超過 22,000 個,因此只需要 2 bytes 的空間(-32768 ~ 32767)即可儲存。後面再接上所有檔案,合併後一個大封包總共約 16 MB 大小。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/udp-header.png" alt="本次定義的標頭檔" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">本次定義的標頭檔</td> </tr> </tbody> </table> <h1 id="logic">傳送邏輯</h1> <p>在相當穩定的環境下,我們可以只傳送不確認;在反應迅速的環境下,我們可以等收到確認封包再進行下一步;但在這次既慢又不穩的環境下,兩種做法效率都不會太好。</p> <p>因此我採用的方式是發送端自行估算在恰好頂到速度上限時,每隔多久可以發送一個封包。<br /> 而接收端確認的方式,則是定期告訴發送端目前順利收到哪些封包了。</p> <h2 id="sender">發送端詳細邏輯</h2> <p>對發送端來說,如果封包傳得太急,會踩到 10 Mbps 速率上限,導致緩衝區愈來愈長,封包需要排隊才能送出。<br /> 如果因此造成多餘的延遲,讓確認封包也塞在緩衝區,最終導致無謂的時間浪費和送出更多重複的區塊,因此我們要找出適當的發送頻率以達到最佳平衡。</p> <p>以我的實作來說,每個封包都是吃滿 1,500 bytes 上限,多數流量來自發送端,來自接收端的確認封包佔少數。<br /> 在撰寫本文之前,埋頭寫程式都沒去認真計算理論值,經過測試得出發送端大約需延遲 0.756 毫秒,恰好是碰到速率上限的甜蜜點。</p> <p>對於總共 16 MB 的檔案,為了符合最大傳輸上限 1,500 bytes 限制,分割後大約有 11,500 個區塊需要傳輸。<br /> 最開始接收端什麼都沒有,因此先全部都發送一輪(約需 8.5 秒),之後再透過接收端回傳的確認封包,看哪些區塊未順利送達,再次依序發送。</p> <p>理想狀況中,每輪需要發送的區塊數量減半,所需時間也跟著減半。不過加上考慮延遲後,大約第六七輪開始,確認封包會來不及回傳。</p> <h2 id="receiver">接收端詳細邏輯</h2> <p>發送確認封包的方式有許多不同做法,依筆者心中的效率簡單排序,由低到高大致為:</p> <ol> <li>收到每個區塊時,都單獨回傳確認(可能較差)</li> <li>收到數個區塊後,用一個封包,批量進行確認</li> <li>每隔一段時間,用多個封包,回傳伺服器的完整狀態</li> <li>每隔一段時間,用多個封包,回傳所有收過的區塊編號</li> <li>每隔一段時間,用一個封包,回傳新收到了哪些區塊</li> <li>每隔一段時間,用一個封包,以 bitset 回傳伺服器狀態(可能較佳)</li> </ol> <p>因此在最終的版本中,我是以 bitset 形式回傳接收端的狀態,每次只需要一個封包即可完成。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/status-bitset.png" alt="使用 bitset 儲存、傳送狀態" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">使用 bitset 儲存、傳送狀態</td> </tr> </tbody> </table> <p>有思考過在最後剩下不到 500 個未完成區塊的時候,或許直接回傳近期收到的區塊編號可以再更節省流量,不過感覺實作相對麻煩就作罷了。</p> <h1 id="delay">延遲詳細計算</h1> <p>已知條件為:</p> <ul> <li>每個封包 1,500 bytes</li> <li>速率上限 10 Mbps</li> <li>約有 40% 機率遺失封包、10% 機率損毀</li> </ul> <p>根據定義可以計算:<br /> <code class="language-plaintext highlighter-rouge">(封包大小 1,500 bytes) * (單位轉換 8 bit / byte) * (成功率 60%) = 平均封包大小 7,200 bits</code><br /> <code class="language-plaintext highlighter-rouge">(速度 10 Mbps) / (封包 7,200 bits) = 每秒可傳送 1,388.88 個封包</code><br /> <code class="language-plaintext highlighter-rouge">1 / (每秒 1,388.88 封包) = 每封包間隔 0.72 毫秒</code></p> <p>雖然理論值是這樣,不過因為 <code class="language-plaintext highlighter-rouge">tc-netem</code> 實作的關係,似乎 0.75 毫秒才是最佳延遲,實驗及試算了好久都不知道怎麼得出正確數字。</p> <!-- 另外如果採用接收端定期回傳狀態的方式,可推算幾個搭配組合: `1 / (1/.75 - 1/.754) = 141.4 ms` `1 / (1/.75 - 1/.762) = 47.6 ms` `1 / (1/.75 - 1/.780) = 19.5 ms` 即為發送端以 0.754 毫秒間隔發送封包時,接收端可以用 142 毫秒間隔回傳狀態而不造成壅塞。 同理,`(發送端間隔 0.762 ms, 接收端間隔 48 ms)` 及 `(發送端間隔 0.780 ms, 接收端間隔 20 ms)` 也是不錯的組合,可以視情況選擇當下最佳策略。 --> <h1 id="compress">檔案壓縮</h1> <p>原先在 Discord 嘴砲說想直接用外部函式庫完成這次實驗,想說既然都讓老師把檔案亂度增加了,那應該是不需要玩壓縮的技巧。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/discord-compress.png" alt="於 Discord 詢問使用壓縮函式庫" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">於 Discord 詢問使用壓縮函式庫</td> </tr> </tbody> </table> <p>不過後來得知檔案內容只包含可視字元,轉換為 ASCII 是 <code class="language-plaintext highlighter-rouge">0x21</code> 到 <code class="language-plaintext highlighter-rouge">0x7E</code> 的區段,在每個 byte 中 256 種可能中只佔了 94 種。</p> <p>在此假設檔案亂度不低,也就是外部壓縮函式庫幫助有限,因此採用類似 <code class="language-plaintext highlighter-rouge">base64_decode()</code> 的方式將檔案從可視字元區段映射到整個空間。</p> <p>最簡單的做法當然是取消最前面固定為 0 的位元,只要透過簡單的位元運算,就讓每 8 個可視字元字映射到 7 bytes,節省 12.5% 空間。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/conv-table.png" alt="每 8 個可視字元可映射至 7 bytes" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">每 8 個可視字元可映射至 14 bytes</td> </tr> </tbody> </table> <p>經過計算後,發現可以透過運算,把每 17 個可視字元映射到 14 bytes,省下了 17.6% 的空間。而運算過程中,剛好勉強低於 <code class="language-plaintext highlighter-rouge">__int128</code> 的上限,實作起來不算複雜。</p> <p>如此讓每個封包 1,470 bytes 的內容實際可塞下 1,785 個可視字元,封包總數量減少到 9,500 個。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/compress-printable.png" alt="把每 17 個可視字元映射到 14 bytes" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">把每 17 個可視字元映射到 14 bytes</td> </tr> </tbody> </table> <p>在最極端狀況下,每個封包其實可以塞下 1,794 個可視字元:<br /> <code class="language-plaintext highlighter-rouge">(log(256) / log(94)) * 1470 = 1794</code><br /> 雖然可以省下 18.1% 的空間,不過實作起來會困難許多,因此沒有採用此方法。</p> <h1 id="speed-up">減少多餘等待時間</h1> <p>在經過分析後,發現原本的程式最前面將檔案合併成大封包,再分割成 9,500 個區塊的過程中,大約會耗費 500 毫秒的時間,因此改為邊切割邊發送第一輪封包。</p> <p>而接收端如果在結束前才一次寫入,會耗費大約 350 毫秒的時間,發現後改為判斷接收完一個檔案就寫入一次。</p> <p>另外由於評測的機制是發送端結束後,會強制關閉接收端並開始比對檔案。因此發送端不能太快結束,但太晚結束又會影響表現。<br /> 後來測試出接收端在剩下大約 5 - 10 個區塊未完成時,提前傳送關閉指令是較為折衷的作法。</p> <h1 id="dynamic-delay">動態調整發送間隔</h1> <p>為了進一步最佳化性能,在接收端回傳狀態封包時,也順便帶上當下的時間戳。<br /> 發送端可以用來計算單向的延遲,判斷緩衝區是否已被塞滿。</p> <p>原本有實作根據延遲時間自動調整間隔的功能,不過由於延遲是隨機在 50 - 150 毫秒之間飄動,事後證實效益不大。<br /> 後來改為使用理論值來計算發送間隔,可以達到較穩定的效果。</p> <h1 id="no-udp">沒用到 UDP 的玩法</h1> <p>從看到實驗限制後,就有想到或許可以透過指令列參數,利用側通道傳送資料,不過覺得做起來稍嫌麻煩,因此一直沒有動工。</p> <p>在正規作法進步到 13.08 秒,想不到可以怎麼繼續加速後,就決定來實作看看,完成後還真的得到比當時第一名還快 70 倍的破表分數。<br /> 雖然有股想要壓到 0.02 秒以下的衝動,不過畢竟初衷只是確認可行性,還是決定先就此打住。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/cmdline-rank.png" alt="當下計分板 0.18 秒成績" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">當下計分板 0.18 秒成績</td> </tr> </tbody> </table> <h2 id="judge">評測方式</h2> <p>評測平台會建立 <code class="language-plaintext highlighter-rouge">/sender_dir/</code> 及 <code class="language-plaintext highlighter-rouge">/receiver_dir/</code> 兩個資料夾,並將發送端及接收端的執行檔分別置於 <code class="language-plaintext highlighter-rouge">/sender_dir/sender_bin</code> 及 <code class="language-plaintext highlighter-rouge">/receiver_dir/receiver_bin</code>。<br /> 在 <code class="language-plaintext highlighter-rouge">/sender_dir/files/</code> 資料夾放有 1,000 個隨機檔案,執行結束後會檢查是否成功傳輸至 <code class="language-plaintext highlighter-rouge">/receiver_dir/files/</code> 資料夾。</p> <p>以發送端來說,先使用 <code class="language-plaintext highlighter-rouge">chroot("/sender_dir/")</code> 防止執行環境存取外部檔案後,再執行 <code class="language-plaintext highlighter-rouge">/sender_bin --read-from="/files" --send-to="localhost:4242"</code> 指令啟動。<br /> 接收端則是以 <code class="language-plaintext highlighter-rouge">chroot("/receiver_dir/")</code> 限制環境後,再執行 <code class="language-plaintext highlighter-rouge">/receiver_bin --listen-port="4242" --store-to="/files"</code> 指令,將透過 UDP 協定收到的封包儲存至 <code class="language-plaintext highlighter-rouge">/receiver_dir/files/</code>。</p> <p>本題是限制網路層的傳輸速度,應該有不少做法作法可以繞過,我只挑自己較為熟悉的一種來實作。</p> <h2 id="cmdline">cmdline 簡介</h2> <p>我是從 2021 年 4 月在調研 ldapsearch 資安漏洞時,翻閱原始碼而接觸到這件事的,不過後來發現因為有盡最大努力側面修補,攻擊雖然可行但時間點需要抓得很精確,因此後續不了了之。<br /> 知道 cmdline 這種玩法後一直覺得很酷,或許寫成一篇科普短文也還不錯,但這裡為了篇幅就只講重點。</p> <p>熟悉 Linux 的大家應該都用過 <code class="language-plaintext highlighter-rouge">ps aux</code> 指令,但知道其中實作方式的人可能不多。<br /> 在 Linux 系統根目錄底下有個特殊的 <code class="language-plaintext highlighter-rouge">/proc/</code> 資料夾,存放核心(kernel)的相關資訊,而底下以程序編號(Process ID)命名的資料夾則存放各程序的狀態。<br /> 例如 <code class="language-plaintext highlighter-rouge">/proc/[PID]/fd/</code> 底下以數字命名的檔案,會連結(symbolic link)到程式開啟的各個檔案;而 <code class="language-plaintext highlighter-rouge">/proc/[PID]/cmdline</code> 檔案則寫著被執行時的參數,以 <code class="language-plaintext highlighter-rouge">0x00 (NUL)</code> 字元區隔。</p> <p>這個 cmdline 檔案雖然無法直接修改,但程式可以透過 <code class="language-plaintext highlighter-rouge">prctl()</code>、<code class="language-plaintext highlighter-rouge">pthread_setname_np()</code> 更動,或直接修改 <code class="language-plaintext highlighter-rouge">main()</code> 函式收到的 <code class="language-plaintext highlighter-rouge">char *argv[]</code> 內容也會反映在上面。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/ps-cmdline.png?" alt="透過 cmdline 查看指令參數" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">透過 cmdline 查看指令參數</td> </tr> </tbody> </table> <h2 id="side-channel">作法說明</h2> <p>在通常狀況下,<code class="language-plaintext highlighter-rouge">main()</code> 收到的 <code class="language-plaintext highlighter-rouge">char *argv[]</code> 長度也就幾十、至多幾百個字,如果要拿來傳資料顯然效率不足。<br /> 這時可以透過上面提過的函式更動,不過在此為了簡單實作,採用之前學過的 <code class="language-plaintext highlighter-rouge">exec()</code> 呼叫自己,並在 <code class="language-plaintext highlighter-rouge">argv[1]</code> 傳遞一個很長很長的參數,目的是擴充 <code class="language-plaintext highlighter-rouge">cmdline</code> 檔案大小,才塞得下整個檔案內容。</p> <p>在完成後就能自由運用 <code class="language-plaintext highlighter-rouge">argv[1]</code> 參數了,開始每隔 0.1 毫秒更新一次 <code class="language-plaintext highlighter-rouge">argv[1]</code>,依序將檔案內容放上。這會同步到 <code class="language-plaintext highlighter-rouge">/proc/[PID]/cmdline</code>,也就是 <code class="language-plaintext highlighter-rouge">ps aux</code> 指令會看到的結果。</p> <p>而接收端則是先等候一小段時間,先確保傳送端已啟動後,持續檢查位於 <code class="language-plaintext highlighter-rouge">/proc/[PID]/cmdline</code> 檔案的參數內容,如果有異動就寫入 <code class="language-plaintext highlighter-rouge">/receiver_bin/files/[ID]</code> 目標檔案。</p> <table> <thead> <tr> <th style="text-align: center"><img src="https://img.sean.taipei/2022/12/argv-cmdline.png" alt="使用 argv / cmdline 繞過限制傳送" /></th> </tr> </thead> <tbody> <tr> <td style="text-align: center">使用 argv / cmdline 繞過限制傳送</td> </tr> </tbody> </table> <p>使用這個方法,理論上可以再 <code class="language-plaintext highlighter-rouge">fork()</code> 出不同程序(process)同步執行,用到本題上限的 15 個程序可以加速不少。</p> <p>也可以把間隔時間依照檔案大小自動調整,或是讓接收端發出訊號,減少不必要的等待時間。</p> <h1 id="epilogue">後記</h1> <p>寫這個實驗的過程中,心中一直被「執行效能」的想法所侷限,但仔細思考後認知到在這個場景下,最珍貴的資源是網路而不是 CPU 效能,有許多顯然花費不合理運算的事情實際上卻可以增進執行效率。</p> <p>老師在隔週的課堂也說了,原先沒想到大家會把時間用在最佳化上面,因此乾脆將一堂實驗課讓出來,給同學們分享各自作法的機會。<br /> 雖然有做好 <a href="https://hackmd.io/@Sean64/netprog-udp" target="_blank">簡報</a>, 不過由於剛好要 <a href="/2022/01/ceh" target="_blank">參與資安檢測</a>, 當周課堂無法出席報告,經過老師同意只好以 <a href="https://youtu.be/fY5yiRY0N6k" target="_blank">預錄影片</a> 代替。</p> <p>感謝 <a href="https://thect.cc/" target="_blank">Thect</a>、 <a href="https://imych.one/" target="_blank">yc油成</a>、 <a href="https://jerry.tw/" target="_blank">Jerry Hsu</a>、 <a href="https://github.com/andy89923" target="_blank">CTFang</a>、 <a href="https://siriuskoan.one/" target="_blank">Sirius Koan</a>、 <a href="https://blog.twinklestar03.com/" target="_blank">TwinkleStar03</a> 等朋友協助審閱文章提供建議,指出盲點讓文意更通順。<br /> 對於文章有任何想法,都歡迎來 <a href="https://twitter.com/Sea_n64/status/1603240158937387008" target="_blank">Twitter</a>、 <a href="https://facebook.com/Sean0604/posts/3366877213584114" target="_blank">Facebook</a> 留言交流,或是在課堂實體捕捉我。</p> <p>如果想嘗試的朋友,老師也在課後將 <a href="https://zoolab-org.github.io/lab_robust_udp/">實驗題目規格</a> 公開,歡迎參考練習。</p> <style> .post table td { color: #666; } .post table td a { color: #6bf; } .post table td a:hover, .post table td a:active, .post table td a:focus { color: #8cf; } </style>