เป็นคำถามที่สงสัยตั้งแต่เด็กๆ ว่าโปรแกรมเราเขียนใน Python แล้วเวลารันต้องใช้ Python interpreter ที่โหลดในเน็ตมา ตัวไฟล์ Python interpreter มันสร้างขึ้นมาได้ยังไง
คำตอบก็ไปดูง่ายๆ คือ CPython ที่โหลดในเว็บมันเขียนด้วยภาษา C ก็เลยใช้ C compiler สร้างไฟล์นั้นขึ้นมา แล้วใครสร้างไฟล์ของ C compiler?
Linux from Scratch
ตอนประมาณ ม. ต้นเคยทำ Linux from Scratch ซึ่งเป็นหนังสือที่สอนวิธีสร้าง Linux ตั้งแต่ต้นด้วยตนเอง ไม่ได้สร้างมาจาก Linux อื่นๆ ที่มีอยู่แล้ว เขาจะมีแผ่นซีดีมาให้ซึ่งมีโปรแกรมพื้นฐานให้ประมาณหนึ่ง (Linux จอดำ) จากนั้นให้เรา compile โปรแกรมต่างๆ
ในเล่มบอกว่าตัว C compiler ที่ใช้คือโปรแกรม GCC ซึ่งเขียนด้วยภาษา C โดยให้เราเอา C compiler ในแผ่นซีดี compile GCC source code ก็แปลว่าต้องมี C compiler ก่อน จึงจะคอมไพล์ C compiler ได้ ก็เลยเป็นปัญหาไก่กับไข่ แต่มันตอบคำถามหนึ่งคือถ้าเราสร้างคอมพิวเตอร์สถาปัตยกรรมใหม่ (new computer architecture) ขึ้นมาเราจะเอา C compiler มาจากไหน โดยวิธีที่เขาเขียน สมมุติว่าผมสร้างเครื่องสถาปัตยกรรม whs32 ขึ้นมา และใช้เครื่อง amd64 เป็นเครื่อง desktop ให้ทำดังนี้
- แก้ไขโค้ด gcc เพิ่มให้สามารถ generate machine code ของ whs32 ได้
- เอา compiler ในเครื่อง amd64 ที่ generate machine code ของ amd64 มา compile gcc ตัวใหม่ เรียกว่า stage1 ซึ่งยังรันบน amd64 แต่ให้ผลลัพท์เป็นโค้ดที่รันใน whs32 (gcc สามารถเลือกให้ output machine code เป็นสถาปัตยกรรมเครื่องใดๆ ก็ได้ ไม่จำเป็นต้องเป็นเครื่องที่รันอยู่)
- เอา stage1 ที่รันในเครื่อง amd64 มา compile ตัวเอง จะได้ gcc อีกตัวเรียกว่า stage2 ซึ่งรันบน whs32 และให้ผลลัพท์เป็นโค้ดที่รันใน whs32
- เอา stage2 รันบนเครื่อง whs32 มา compile ตัวเองใหม่ จะได้ stage3 เป็นอันเสร็จ
- ที่ต้องทำ stage3 เพราะว่า stage2 อาจจะมีการอ้างอิง library, path ต่างๆ บนเครื่อง amd64 ทำให้ไปใช้งานจริงบนเครื่องอื่นไม่ได้ วิธีแก้ไขคือปิดฟีเจอร์ที่ไม่จำเป็นใน stage2 ออกไปก่อนเพื่อให้ compiler จบในตัว แล้วค่อย compile stage3 ที่มีฟีเจอร์ครบถ้วนในระบบจริง
- เวลา gcc compile ตัวเอง แบบไม่ข้ามสถาปัตยกรรม มันจะ compile 3 ครั้ง
- ใช้ stage2 compile ตัวเองจาก source code เรียกว่า stage3.1
- ใช้ stage3.1 compile ตัวเองอีก 2 ครั้ง เรียกว่า stage3.2 และ stage3.3
- ตรวจสอบว่า stage3.2 = stage3.3 เพื่อทดสอบว่า compiler ทำงานได้ถูกต้อง
- ใช้ stage3.3 เป็นผลลัพท์ stage3
สรุปแล้วเราก็พอเข้าใจว่าถ้าสร้างชิพใหม่ขึ้นมาเราจะเอา compiler มาจากไหน แต่ compiler ตัวแรกมาจากไหน…? ก่อนจะเล่าต่อไป ขอไปเล่าเรื่องอื่นก่อนแล้วกัน
Why does this matter
Ken Thompson ผู้สร้างระบบปฏิบัติการ Unix และภาษา Go เคยตีพิมพ์ paper เรื่อง Reflection on trusting trust (1984) ว่าคุณจะรู้ได้อย่างไรว่า compiler ที่คุณใช้ไม่มี backdoor จริง
สมมุติว่ามี compiler ตัวหนึ่งซึ่งมันจะ detect source code pattern อย่างหนึ่งแล้วแทรก backdoor ลงไป และ detect source code ตัวเองเพื่อแทรกโค้ดตัวมันเองเข้าไป ถ้าเรา compile compiler ตัวนี้แล้วก็จะทำให้ backdoor ฝังอยู่ใน compiler ซึ่ง compile compiler ใหม่ก็ไม่หาย แต่ตรวจสอบหา backdoor ใน source code ไม่พบ ถ้าอย่างนั้นแล้วคุณจะแน่ใจได้อย่างไร ว่าระบบที่ใช้งานอยู่ไม่มี backdoor
ปรากฏว่ามีผู้พบว่า Ken Thompson เคยโจมตีด้วยท่านี้จริง โดยเขาเล่าในปี 1995 ว่าหลายสิบปีก่อนเขาสร้าง compiler แบบนี้จริงแล้วส่งให้แผนก UNIX support ติดตั้ง binary เข้าไปในระบบโดยอ้างว่ามีฟีเจอร์ใหม่ที่ไม่สามารถใช้ compiler เก่า compile source code ใหม่ได้ ใน compiler ใหม่นี้มีการฝัง backdoor ของโปรแกรม login
ไว้
ต่อมามีผู้พบว่า symbol table (function list) ของ compiler มันแปลกๆ ก็เลยสั่งให้ compiler print assembly ออกมาซึ่งระบบแทรก backdoor ไม่ได้เขียนไว้รองรับคำสั่งนี้ แล้วเอา assembly ไปแปลงเป็น machine code ทำให้ backdoor หายไป
ในปัจจุบันจึงเป็นคำถามว่าถ้าหากเรามี backdoor ที่ซับซ้อนกว่าที่ Ken เคยสร้างไว้จริง เราจะมั่นใจได้อย่างไรว่าระบบคอมพิวเตอร์มีความปลอดภัยเพราะถึงแม้จะอ่านโค้ดทุกบรรทัดก็ไม่ได้แปลว่าจะเป็นโค้ดทั้งหมดของโปรแกรม
Go
Compiler ของภาษา Go เขียนขึ้นด้วยภาษา C ในตอนแรก จากนั้นถูกใช้เครื่องมือแปลงภาษา C เป็น Go ภายหลัง ทำให้ Go compiler ในปัจจุบันเขียนด้วยภาษา Go ดังนั้นทีมงาน Go จึงแนะนำวิธีสร้าง Go compiler ดังนี้
- ดาวน์โหลดซอร์สโค้ด Go 1.4 ซึ่งเป็นรุ่นสุดท้ายที่เขียนด้วยภาษา C
- Compile Go 1.4
- Compile Go 1.17.13 ด้วย Go 1.4
- Compile Go 1.20
- Compile Go รุ่นต่อๆ ไป โดยทีมงาน Go กำหนดว่า minimum compiler version ที่ใช้ compile รุ่นล่าสุดได้คือ version ที่ออกเมื่อประมาณ 1 ปีที่แล้ว
อีกวิธีหนึ่งที่ทำได้คือมีอีกโปรแกรมที่ compile ภาษา Go ได้นั่นคือ gccgo ซึ่งเขียนด้วยภาษา C และรองรับโค้ด Go ในระดับหนึ่ง สามารถใช้ gccgo compile Go รุ่นใหม่ได้เลย
Reproducible builds
ในปัจจุบัน Linux distribution หลายตัวเข้าร่วมโครงการ Reproducible builds ซึ่งเป็นอีกวิธีหนึ่งที่พอจะแก้ปัญหาความปลอดภัยด้านบนได้บ้าง โดย Linux distro จะทำให้ผลลัพท์ของการสร้าง package นั้นสามารถทำซ้ำได้ไฟล์เดียวกัน 100% ซึ่งใครก็สามารถทำซ้ำ ตรวจสอบได้ตลอดเวลาเพื่อยืนยันว่า package นั้นเกิดจาก source code จริงๆ เพราะ Linux บางตัวไม่มีระบบ CI/CD กลางเนื่องจากเป็นค่าใช้จ่าย แต่ให้ผู้สร้างแพคเกจ compile บนเครื่องตัวเอง เซ็นแล้วอัพโหลดไปแจกจ่าย
ขณะที่เขียนนี้ Package ทั้งหมดของ Linux ต่อไปนี้สามารถทำซ้ำ ตรวจสอบได้ด้วยตนเอง
- Arch Linux 78.5%
- Debian amd64 90.8%
- openSUSE 94%
รวมถึง Go compiler 1.21 ด้วยที่ตัวที่ให้โหลดในหน้าเว็บ สามารถทำซ้ำได้ด้วยตนเอง
ฟังดูเหมือนว่าง่ายๆ ว่าโค้ดเดิมก็ควรจะได้ผลลัพท์เดิมเสมอ แต่ในความเป็นจริงแล้วอาจจะมีปัจจัยต่างๆ ที่ทำให้ได้ผลลัพท์ต่างกันไป เช่น
- File metadata ไม่ตรงกัน ทำให้เวลาสร้าง/แตก zip แล้วไม่ตรง เช่น ชื่อเจ้าของไฟล์ สิทธิ์ หรือเวลาสร้างไฟล์
- สถาปัตยกรรมไม่ตรงกัน เช่น compile ครั้งแรกใช้เครื่อง 32 bit ต่อมาใช้เครื่อง 64 bit แต่ compile เป็นโปรแกรม 32 bit ทั้งคู่ อาจจะได้ผลลัพท์ต่างกันเพราะมีการบันทึกค่าไว้
- มีการฝังวันเวลาที่ compile เข้าไปในโปรแกรม (เช่นคำสั่ง version/about) ทำให้ได้ผลลัพท์ไม่ตรงกัน ซึ่งต้องลบโค้ดออกหรือกำหนดเป็นวันเวลาที่ fix ไว้
- มีการฝัง path ที่ compile เข้าไปในโปรแกรม (เช่นใน stack trace เวลา crash) เวลาทำซ้ำอาจจะทำที่ path อื่น หรือระบุ path คนละแบบกัน (absolute/relative) ซึ่งจะต้องบันทึก path ไว้หรือให้ compiler normalize path ได้
- มีการฝังข้อมูลเครื่องที่ compile เข้าไปในโปรแกรม เช่น username, hostname, timezone, language
- Library ที่ใช้ไม่ตรงกัน เช่น มีการใช้ library ในเครื่องที่ไม่แจ้งไว้ พอคนอื่นไป compile แล้วหาไม่เจอ, ใช้ version ไม่ตรงกัน, compiler คนละตัวกัน
- ในโค้ดมีการสุ่ม เช่นอ่านข้อมูลจาก filesystem หรือ HashMap มาแล้วไม่ได้ sort แต่ละครั้งจึงได้ลำดับสลับกัน
ดังนั้นผู้สร้างแพคเกจจะต้องตรวจหาปัญหาเหล่านี้และแก้ไขให้เรียบร้อย ซึ่งบางครั้ง compiler เองก็อาจจะเป็นที่มาของปัญหาเหล่านี้ได้เช่นกัน ไม่ใช่เฉพาะแค่ใน source code
เนื่องจาก Linux หลายตัวสามารถสร้างได้จาก source code อยู่แล้ว (ถึงอาจจะไม่ได้เท่ากันทุก bytes) ดังนั้นบริษัทใหญ่ๆ หลายที่จึงสร้าง Linux ของตัวเองซึ่งโปรแกรมส่วนมากก็เอามาจาก Linux อื่นๆ แต่ compile เองจะได้ไม่ต้องไว้ใจคนอื่น และอาจจะ modify ตามที่ตัวเองสนใจได้ด้วย เช่น
- Microsoft CBL Mariner ซึ่งใช้ใน WSL มาจาก VMware Photon, Fedora, Openmamba
- Amazon Linux ซึ่งมาจาก Fedora คละรุ่น
- TencentOS มาจาก CentOS/Red Hat Enterprise Linux
Guix Bootstrap
ที่เล่าไปด้านบนก็คือวิธีบริหารความเสี่ยงที่ใช้กันทั่วไปว่า Linux ที่ใช้งานอยู่นั้นเชื่อถือได้ แต่ยังอยู่บนข้อจำกัดว่าระบบที่ใช้งานอยู่เชื่อถือได้ และ C compiler ปัจจุบันเชื่อถือได้ ถ้าเราต้องการ C compiler ที่เชื่อถือได้จะทำอย่างไรดี
Guix เป็น Linux distribution ของโครงการ GNU ซึ่งมองว่าระบบ Linux นั้นสามารถ reproducible ได้จาก source code โดยขั้นตอนการ reproduce ก็เป็น source code เช่นเดียวกันซึ่งเขียนด้วยภาษา Scheme การติดตั้งแพคเกจต่างๆ ก็คือให้มัน reproduce build ของโปรแกรมนั้นๆ ขึ้นมา
ในขณะนี้ Guix ใช้โครงการ bootstrap-seeds เป็นจุดเริ่มต้น โดย bootstrap-seed ทำงานดังนี้
- กำหนดไฟล์ hex0 เป็นการแสดงเลขฐาน 2 ในรูปแบบเลขฐาน 16 (เช่นในไฟล์เขียนว่าว่า
F0
ให้ output11110000
) และรองรับการใส่ comment - สร้างโปรแกรมสำหรับแปลงไฟล์ hex0 ซึ่งเขียนด้วย machine code ของเครื่อง x86 ในรูปแบบไฟล์ hex0 โดย Guix จะใช้ไฟล์ hex0-seed ขนาด 357 bytes ที่แปลงมาสำเร็จรูปแล้ว แต่เราจะแปลงเองด้วยมือก็ได้
- Compile โปรแกรม hex1 ซึ่งเขียนด้วย hex0 โดย hex1 เป็นภาษาที่ปรับปรุงขึ้นมาจาก hex0 สามารถใช้ label สำหรับ jump ได้ (ก็คือต้องสามารถแทรก relative offset ของจุดที่แปะ label ไว้ในไฟล์จากจุดปัจจุบันได้)
- Compile โปรแกรม hex2 ซึ่งเขียนด้วย hex1 โดย hex2 จะเพิ่มความสามารถที่ label มีหลายตัวอักษรได้และสามารถหาตำแหน่งแบบ absolute ของ label ได้
- Compile โปรแกรม M0 ซึ่งเขียนด้วย hex2 ซึ่งสามารถกำหนด macro ได้ (ชุดคำสั่งที่ให้พิมพ์ซ้ำ)
- Compile โปรแกรม cc ซึ่งเขียนด้วย M0 เป็น C compiler แบบง่ายๆ ที่ใช้ชุดคำสั่งได้จำกัด
- Compile โปรแกรม M2-Planet ซึ่งเขียนด้วยภาษา C เท่าที่โปรแกรม cc รองรับ เป็น C compiler ที่รองรับชุดคำสั่งได้มากขึ้น
- Compile โปรแกรม GNU Mes ซึ่งเป็น C compiler และ interpreter ของภาษา Scheme (ที่ Guix ใช้) โดยสามารถคอมไพล์ได้จาก M2-Planet
- Compile โปรแกรม TinyCC (fork) ซึ่งสามารถใช้ compile GCC และไลบรารีอื่นๆ ที่ใช้งานใน Linux ปกติได้
(ในนี้ไม่รวมถึง tool อื่นๆ ที่ใช้ประกอบการรัน tool ข้างบน เช่น cat
, shell, debug tool, linker, C standard library เป็นต้น)
หลังจากเรามี GCC และ library อื่นๆ แล้วก็สามารถ compile โปรแกรมอื่นๆ ไปเรื่อยๆ จนถึงโปรแกรมที่เราต้องการได้ เช่น Python interpreter โดยถ้าเราเชื่อว่า source code ทั้งหมดที่ใช้น่าเชื่อถือ ไม่มี backdoor แล้วกระบวนการนี้ก็ทำให้เรามั่นใจได้ว่าสามารถสร้างระบบ Linux ขึ้นมาได้โดยไม่ต้องใช้ compiler ตั้งต้น
ในปัจจุบันข้อจำกัดของระบบนี้คือต้องเชื่อได้ว่า Kernel ที่รันอยู่น่าเชื่อถือ เพราะเรารัน hex0 บน Kernel ปัจจุบัน ในอนาคตทีมงาน bootstrappable.org มีความคิดที่จะพัฒนา CPU architecture “Knight” ซึ่งสามารถออกแบบเป็นวงจร FPGA ได้เพื่อใช้สร้าง hex0 โดยไม่ต้องใช้คอมพิวเตอร์ และ builder-hex0 ที่เป็น OS พื้นฐานสามารถรัน hex0 ได้ในตัว
The original C compiler
แล้ว C compiler ตัวแรกสร้างมาจากไหน?
Dennis Richie (RIP) เขียนบันทึกไว้ว่า UNIX ตัวแรกถูกสร้างขึ้นโดย Ken Thompson (จำชื่อนี้ได้ไหม) ในปี 1968 โดยใช้โปรแกรม assembler (คล้ายๆ M0) ของเครื่อง GE-635 สร้างแถบกระดาษสำหรับเครื่อง PDP-7 จนมีโปรแกรมพื้นฐานพร้อมใช้งาน ได้แก่ Kernel, editor, shell, คำสั่ง rm, cat, cp และ assembler จากนั้นก็เริ่มพัฒนาบนเครื่อง PDP-7 ต่อ
ในปีต่อมา Doug McIlroy สร้างภาษา TMG (TransMoGrifiers) สำหรับ UNIX บน PDP-7 ขึ้นมาเป็นภาษาโปรแกรมระดับสูงตัวแรก แล้ว Ken ก็สร้างภาษา B ขึ้นโดยเขียนในภาษา TMG โดยอ้างอิงแบบมาจากภาษา BCPL ของ Martin Richards หลังจากสร้างขึ้นสำเร็จก็ได้เขียนภาษา B ใหม่อีกครั้งหนึ่งในภาษา B เอง
ในปี 1971 Dennis Richie พบว่าภาษา B เริ่มตามไม่ทันเครื่องคอมพิวเตอร์ที่อัพเกรดเป็นรุ่น PDP-11 จึงปรับปรุงภาษาขึ้นเป็นภาษา NB (New B) พร้อมกับคอมไพเลอร์ตัวใหม่ ซึ่งต่อมาก็ได้เปลี่ยนชื่อเป็น C
สำหรับ GCC ผมยังไม่เห็นประวัติว่าใช้ compiler ใดสร้างขึ้น แต่โปรแกรมส่วนมากของโครงการ GNU ถูกสร้างขึ้นบนเครื่อง UNIX ก็เป็นไปได้ว่าอาจจะใช้ C compiler ของ Dennis Richie