臺灣博碩士論文加值系統

過去的數十年，電腦一直作為主要的運算裝置。X86是一個被大量電腦採用的指令集架構，其擁有的二元碼資源非常豐富。最近幾年，其他裝置如行動裝置正蓬勃發展，但以前為X86所撰寫的程式卻無法直接運行於其中。不過有些程式卻能夠倖免於難，以動態程式語言開發而成的網路應用程式即是一個例子。由於網路的蓬勃發展，網路應用程式的數量正快速成長中。
為了方便開發效能良好的網路應用程式，Mozilla和Google於2017年合作主導開發了WebAssembly，期盼以之取代JavaScript程式中運算密集的部分。WebAssembly如今已經成為W3C的一項標準，Microsoft、Apple等瀏覽器開發公司也紛紛跟進支援。
本篇論文主要是擴充一個現有的X86二元碼轉譯器HBT-86，以支援WebAssembly後端。我們將HBT-86使用的LLVM版本更新至3.8版，使其產生的LLVM IR可以進一步被Emscripten轉譯為WebAssembly。我們也提供了一個執行環境用以運行轉譯後的WebAssembly程式。除此之外，我們設計函式邊界復原方法以保留程式原本的結構，並可以減少優化所需的時間。
實驗結果顯示，使用動態連結的來源二元碼在復原函式邊界後，優化時間平均減少15.75%，使用靜態連結則平均可減少57.53%；而程式的大小及執行時間僅分別多出2.09％及1.28％。而由X86來源二元碼轉譯出的WebAssembly目標碼的執行時間則只為直接從高階語言編譯而成的WebAssembly的3.53倍，但可使X86程式具有可攜性。

The computers have become the main computing devices in the past few decades, and a huge number of application programs have been developed to execute on computers. The X86 is an instruction set architecture adopted by most of the computers, and its binary resources are very rich. Some other devices such as mobile devices are flourished in recent years, but the X86 programs written before usually cannot be run in these devices directly. However, some of programs are prevent from such disasters, and the web applications developed in dynamic programming languages is one of them. Since the internet is booming, the number of web applications is growing rapidly.
In order to facilitate the development of web applications with excellent performance, the leading browser development companies, Mozilla and Google, co-developed the WebAssembly in 2017. The main purpose of WebAssembly is to replace JavaScript in the computationally intensive part of a web application. WebAssembly has become one of the W3C standards, and other companies such as Microsoft and Apple have also followed up to support it.
In this thesis, we modify an existing X86 binary translator, HBT-86, to support the WebAssembly as one of its target binaries. We update the HBT-86 from LLVM version 3.4 to 3.8 so that it may generate the LLVM IR that can be translated to WebAssembly by Emscripten. We also provide a runtime environment to execute the emulated WebAssembly program. Moreover, we design a function boundary recovery mechanism to reconstruct the structure of the source program and to reduce the optimization time in static binary translation process.
The experiment shows that the optimization time can be reduced 15.75% with the function boundary recovery for the dynamically linked source binary, and 57.53% for static linked source binary. However, the code size and execution time will increase 2.09% and 1.28% respectively as the cost. The execution time of the WebAssembly program translated from a X86 source binary is 3.53 times of that of the WebAssembly compile from high-level language in average, but it makes X86 programs portable.

摘要 i
Abstract ii
致謝 iv
Contents v
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Objective 2
1.3 Organization of this thesis 2
Chapter 2 Background and Related Work 3
2.1 Background 3
2.2 Related Work 8
Chapter 3 Design and Implementation 9
3.1 System Overview 9
3.2 Function Boundary Recovery 10
3.3 Updating the HBT-86 16
3.4 Modifying Runtime 19
Chapter 4 Experiment Result 21
4.1 Experiment Environment 21
4.2 Effects of Function Boundary Recovery 21
4.3 Analysis of Translated WebAssembly 29
Chapter 5 Conclusions and Future Work 31
5.1 Conclusions 31
5.2 Future Work 31
Reference 33

[1] Sites, R. L., Chernoff, A., Kirk, M. B., Marks, M. P., & Robinson, S. G., "Binary translation," in Communications of the ACM, pp. 69-81, 1993.
[2] Cifuentes and Malhotra, "Binary translation: static, dynamic, retargetable?" in Proceedings of International Conference on Software Maintenance, pp. 340-349, Monterey, CA, USA, 1996.
[3] Jim Smith and Ravi Nair, "Virtual Machines: Versatile Platforms for Systems and Processes, " Elsevier, 2005.
[4] Hookway, Raymond J., and Mark A. Herdeg, "Digital FX! 32: Combining emulation and binary translation," in Digital Technical Journal 9, pp. 3-12, 1997.
[5] Baraz, Leonid, et al, "IA-32 execution layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium/spl reg/-based systems," in Proceedings. 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003.
[6] Bellard, Fabrice, "QEMU, a fast and portable dynamic translator," in USENIX Annual Technical Conference, FREENIX Track, Vol. 41, 2005.
[7] Bor-Yeh Shen, Wei-Chung Hsu and Wuu Yang, "An LLVM-based Hybrid Binary Translation System," in International Symposium on Industrial Embedded Systems, Karlsruhe, Germany, 2012.
[8] I-Chun Liu, "OS Supports of an LLVM-Based Retargetable Hybrid Binary Translator For X86 ISA," Master Thesis, National Chiao Tung University, 2013.
[9] Chris Lattner and Vikram Adve, "LLVM: A compilation framework for lifelong program analysis & transformation," in Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p. 75, IEEE Computer Society, Washington, DC, 2004.
[10] Haas, Andreas, et al., "Bringing the web up to speed with WebAssembly," in Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 185–200, New York, USA, 2017.
[11] "Asm.js," [Online] Available: http://asmjs.org/. [Accessed 16 July 2020]
[12] B. Yee et al., "Native Client: A Sandbox for Portable, Untrusted x86 Native Code," in 30th IEEE Symposium on Security and Privacy, pp. 79-93, Berkeley, CA, 2009.
[13] Shih-Hsin Chen, "x87 Instruction Set Architecture and ARM Target System Supports for a Retargetable Hybrid Binary Translator Based on LLVM," Master Thesis, National Chiao Tung University, 2015.
[14] Hung, Yu-Ting, "X86-64 Instruction Set Architecture Supports for an LLVM-Based Retargetable Hybrid Binary Translator," Master Thesis, National Chiao Tung University, 2017.
[15] Liu, Shang-Wen, "Supporting Advanced Vector Extensions (AVX) on HBT-86," Master Thesis, National Chiao Tung University, 2016.
[16] Hong-Wei Liu, "Patchouli: A Knowledge-Based Binary Translation Framework for x86 Executable to Web Applications," Master Thesis, National Chiao Tung University, 2016.
[17] Bao, Tiffany, et al, "BYTEWEIGHT: Learning to Recognize Functions in Binary Code," in 23rd USENIX Security Symposium, p. 845, San Diego, CA, 2014.
[18] Alon Zakai. 2011. "Emscripten: an LLVM-to-JavaScript compiler," in Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion, pp. 301–312, New York, USA, 2011.
[19] S. Tilkov and S. Vinoski, "Node.js: Using JavaScript to Build High-Performance Network Programs," in IEEE Internet Computing, vol. 14, no. 6, pp. 80-83, Nov.-Dec. 2010.
[20] CHEN, Jiunn-Yeu, "On the Binary Translation of ARM/Thumb mixed ISA Binaries," PhD Thesis, National Chiao Tung University, 2015.
[21] "LLVM 3.8.0," [Online] Available: https://releases.llvm.org/3.8.0/docs/index.html. [Accessed 16 July 2020]
[22] Powers, Bobby, John Vilk, and Emery D. Berger, "Browsix: Bridging the gap between unix and the browser," in ACM SIGPLAN Notices 52.4, pp. 253-266, 2017.