ScratchABlock

ถาม : เหตุใดจึงจำเป็นต้องมีตัวถอดรหัสตัวอื่น โดยเฉพาะอย่างยิ่งตัวถอดรหัสที่พิการ

ตอบ : ความจริงอันน่าเศร้าก็คือโปรแกรมถอดรหัสส่วนใหญ่นั้นพิการ หลายๆ คนไม่สามารถถอดรหัสโครงสร้างเล็กๆ น้อยๆ ได้ ส่วนคนอื่นๆ ไม่สามารถถอดรหัสโครงสร้างขั้นสูงไปกว่านี้ได้ และสิ่งที่ดูเหมือนจะสามารถจัดการกับสิ่งเหล่านั้นได้ พิการโดยการสนับสนุนเฉพาะสถาปัตยกรรมและระบบปฏิบัติการที่น่าเบื่อเท่านั้น และเกือบทุกการเขียนในลักษณะที่ปรับแต่งหรือเพิ่มสถาปัตยกรรมใหม่นั้นมีความซับซ้อน ตัวถอดรหัสเป็นเครื่องมือสำหรับวิศวกรรมย้อนกลับ แต่ในทางกลับกัน หากคุณต้องการใช้ตัวถอดรหัสทั่วไปอย่างมีประสิทธิผลหรือทำให้เหมาะกับความต้องการของคุณ ขั้นแรกคุณจะต้องทำวิศวกรรมย้อนกลับตัวถอดรหัสเองก่อน และอาจใช้เวลาหลายเดือน (หรือหลายปี) ได้อย่างง่ายดาย .

ScratchABlock แตกต่างอย่างไร?

ส่วนกลางของตัวถอดรหัส (และเฟรมเวิร์กการเปลี่ยนแปลงโปรแกรม) คือ Intermediate Representation (IR) ตัวถอดรหัสควรทำงานบน IR และควรใช้เป็นอินพุต และการแปลงแอสเซมเบลอร์ของสถาปัตยกรรมเฉพาะไปเป็น IR นี้ควรแยกตัวจากตัวถอดรหัสอย่างดี ไม่เช่นนั้นก็ต้องใช้ความพยายามเป็นพิเศษในการเพิ่มการรองรับสถาปัตยกรรมอื่น (ซึ่งในทางกลับกันจะจำกัด ฐานผู้ใช้ของตัวถอดรหัส)

การคอมไพล์เป็นงานที่ซับซ้อน ดังนั้นจึงควรมีความเข้าใจอย่างง่ายเกี่ยวกับกระบวนการถอดรหัส ซึ่งหมายความว่า IR ที่ใช้โดยตัวถอดรหัสควรเป็นมิตรกับมนุษย์ เช่น ใช้ไวยากรณ์ที่โปรแกรมเมอร์คุ้นเคย แมปกับแอสเซมเบลอร์เครื่องจักรทั่วไปให้มากที่สุดเท่าที่จะเป็นไปได้ เป็นต้น

ข้อกำหนดข้างต้นควรจะชัดเจนในตัวเอง ถ้าไม่เช่นนั้นก็สามารถเรียนรู้ได้จากหนังสือเกี่ยวกับเรื่องนี้ เช่น

“ผู้เขียนคอมไพเลอร์ยังต้องการกลไกที่ช่วยให้มนุษย์ตรวจสอบโปรแกรม IR ได้อย่างง่ายดายและโดยตรง การคำนึงถึงผลประโยชน์ของตนเองควรตรวจสอบให้แน่ใจว่าผู้เขียนคอมไพเลอร์ให้ความสนใจในประเด็นสุดท้ายนี้”

(คีธ คูเปอร์, ลินดา ทอร์ซอน, “วิศวกรรมคอมไพเลอร์”)

อย่างไรก็ตาม โปรเจ็กต์ตัวถอดรหัส รวมถึง OpenSource ละเมิดข้อกำหนดเหล่านี้เป็นประจำ: โปรเจ็กต์เหล่านี้เชื่อมโยงอย่างแน่นหนากับสถาปัตยกรรมเครื่องเฉพาะ ไม่อนุญาตให้ป้อน IR เข้าไป และบ่อยครั้งจะไม่เปิดเผยหรือจัดทำเอกสารให้ผู้ใช้เห็นเลย

ScratchABlock เป็นความพยายามที่จะปฏิเสธแนวทางปฏิบัติดังกล่าวและพัฒนากรอบงานการคอมไพล์ตามข้อกำหนดข้างต้น โปรดทราบว่า ScratchABlock ถือได้ว่าเป็นโครงการการเรียนรู้/วิจัย และนอกเหนือจากความตั้งใจดีและการวิจารณ์โครงการอื่นๆ แล้ว อาจไม่ได้ให้ประโยชน์แก่ผู้ใช้ทั่วไปมากเกินไป - ในปัจจุบันหรืออาจเป็นไปได้เลย ก็สามารถวิพากษ์วิจารณ์ได้ในหลายด้านอย่างแน่นอน

ส่วนลงสู่พื้นโลก

ScratchABlock เปิดตัวภายใต้เงื่อนไขของ GNU General Public License v3 (GPLv3)

ScratchABlock เขียนด้วยภาษา Python3 และทดสอบกับเวอร์ชัน 3.3 ขึ้นไป แม้ว่าอาจใช้งานได้กับ 3.2 หรือต่ำกว่าก็ตาม (ใช้ไม่ได้กับเวอร์ชัน Python2 รุ่นเก่า) มีการพึ่งพาบางประการ:

• PyYAML, https://pypi.python.org/pypi/PyYAML
• การทดสอบจมูก https://pypi.python.org/pypi/nose (จำเป็นสำหรับการทดสอบหน่วยเท่านั้น)

บน Debian/Ubuntu Linux sudo apt-get install python3-yaml python3-nose สามารถติดตั้งได้ด้วย หรือคุณสามารถติดตั้งสิ่งเหล่านี้ผ่านตัวจัดการแพ็คเกจ pip ของ Python เอง (ควรใช้ได้กับระบบปฏิบัติการใด ๆ ): pip3 install -r requirements.txt

ScratchABlock ใช้แอสเซมเบลอร์ PseudoC เป็น IR มันเป็นภาษาแอสเซมเบลอร์ที่แสดงออกมามากที่สุดเท่าที่จะเป็นไปได้โดยใช้ไวยากรณ์ภาษา C ที่คุ้นเคย แนวคิดก็คือโปรแกรมเมอร์ C ทุกคนจะเข้าใจมันอย่างสังหรณ์ใจ (ตัวอย่าง) แต่มีความพยายามอย่างต่อเนื่องในการจัดทำเอกสาร PseudoC อย่างเป็นทางการมากขึ้น

โปรดทราบว่าตามข้อกำหนดที่อธิบายไว้ในส่วนก่อนหน้าของเอกสาร และปฏิบัติตาม "กระบวนทัศน์ Unix" ที่รู้จักกันดี ScratchABlock ดำเนินการ "สิ่งหนึ่ง" - วิเคราะห์และแปลงโปรแกรม PseudoC และ ไม่ เกี่ยวข้องอย่างชัดเจนกับการแปลงคำสั่งเครื่องของสถาปัตยกรรมเฉพาะ ลงใน PseudoC (อย่างน้อยก็ตอนนี้) นั่นหมายความว่า ScratchABlock ไม่ได้บังคับให้คุณใช้ตัวแปลง/ตัวยกใดๆ คุณสามารถใช้อะไรก็ได้ที่คุณต้องการ ข้อแม้: คุณจะต้องมีอันหนึ่งจึงจะใช้งานได้ ดูส่วนท้ายของเอกสารเพื่อดูคำแนะนำบางประการในเรื่องนั้น

ซอร์สโค้ดและสคริปต์อินเทอร์เฟซอยู่ในรูทของที่เก็บ สคริปต์ที่สำคัญที่สุดคือ:

• apply_xform.py - ไดรเวอร์ส่วนกลาง อนุญาตให้ใช้ลำดับของการแปลง (หรือโดยทั่วไป สคริปต์การวิเคราะห์/การแปลงระดับสูง) กับไฟล์เดียวหรือไดเร็กทอรีของไฟล์ ("ไดเร็กทอรีโครงการ")

• inter_dataflow.py - โปรแกรมควบคุมการวิเคราะห์โฟลว์ข้อมูลระหว่างขั้นตอน (ทั่วโลก) (WIP)

• script_*.py - สคริปต์การวิเคราะห์/การเปลี่ยนแปลงระดับสูงสำหรับ apply_xform.py ( --script switch)

• script_i_*.py - สคริปต์การวิเคราะห์สำหรับ inter_dataflow.py

• run_tests - ตัวรันชุดทดสอบการถดถอย ชุดทดสอบส่วนใหญ่จะอยู่ในระดับสูง ซึ่งประกอบด้วยการรัน Apply_xform.py พร้อมการส่งผ่านไฟล์ที่แตกต่างกัน และตรวจสอบผลลัพธ์ที่คาดหวัง

ไดเร็กทอรีย่อยอื่น ๆ ของที่เก็บ:

• tests_unit - การทดสอบหน่วยคลาสสิกสำหรับโมดูล Python ที่เขียนด้วย Python

• tests - ชุดทดสอบหลัก แม้ว่าจะมีลักษณะบูรณาการ แต่มักจะทดสอบการส่งผ่านหนึ่งไฟล์ในไฟล์ธรรมดาไฟล์เดียว ดังนั้นจึงเป็นไปตามปรัชญาการทดสอบหน่วย การทดสอบจะแสดงเป็นไฟล์อินพุต PseudoC ในขณะที่ผลลัพธ์ที่คาดหวัง - เป็น PseudoC พร้อมคำอธิบายประกอบแบบบล็อกพื้นฐานและ (ถ้ามี) CFG ในรูปแบบ .dot เมื่อดูกรณีทดสอบเหล่านี้ การพยายามแก้ไขและเห็นผลลัพธ์เป็นวิธีที่ดีที่สุดในการเรียนรู้วิธีการทำงานของ ScratchABlock

• docs - ชุดเอกสารที่เพิ่มมากขึ้น ตัวอย่างเช่น มีข้อกำหนดของภาษาแอสเซมเบลอร์ PseudoC ที่ทำหน้าที่เป็นตัวแทนระดับกลาง (IR) สำหรับ ScratchABlock และการสำรวจว่าทำไม IR อื่นที่มีอยู่จึงไม่ถูกเลือก

แนวทางปัจจุบันของ ScratchABlock คือการขยายคอลเลกชันอัลกอริธึมคู่ที่ค่อนข้างหลวม ("ผ่าน") สำหรับการวิเคราะห์และการแปลงโปรแกรม ครอบคลุมการทดสอบ และอนุญาตให้ผู้ใช้เข้าถึงได้ง่าย ความมหัศจรรย์ของการถอดรหัสประกอบด้วยการใช้อัลกอริธึมเหล่านี้ตามลำดับสิทธิ์และจำนวนครั้งที่ถูกต้อง จากนั้น เพื่อปรับปรุงประสิทธิภาพของการแยกคอมไพล์ การส่งผ่านเหล่านี้มักจะต้องมีการเชื่อมต่อที่แน่นมากขึ้น การสำรวจทิศทางเหล่านั้นถือเป็นเรื่องสำคัญลำดับถัดไปหลังจากดำเนินการสินค้าคงคลังของบัตรตามที่อธิบายไว้ข้างต้น

อัลกอริทึมและการแปลงที่ดำเนินการโดย ScratchABlock:

• อัลกอริธึมกราฟ:

  • การสร้างและการสืบค้น (รุ่นก่อน ผู้สืบทอด ฯลฯ)
  • Traversal (การค้นหาเชิงลึกก่อน (DFS), ลำดับหลัง)
  • ต้นไม้ Dominator/เขตแดนการครอบงำ
  • การแยกโหนด

• แบบฟอร์มมอบหมายงานเดี่ยวแบบคงที่ (SSA):

  • การก่อสร้าง

• การวิเคราะห์การไหลของข้อมูล:

  • เฟรมเวิร์กอัลกอริทึมกระแสข้อมูลซ้ำทั่วไป
  • ต้นไม้โดมิเนเตอร์
  • การเข้าถึงคำจำกัดความ
  • ตัวแปรสด
  • การสร้างห่วงโซ่การป้องกันการใช้งาน

• การขยายพันธุ์:

  • คงที่
  • สำเนา
  • การอ้างอิงหน่วยความจำ
  • นิพจน์

• การกำจัดโค้ดที่ไม่ทำงาน (DCE)

• การเขียนใหม่:

  • ของตัวแปรสแต็ก
  • ของเขตข้อมูลโครงสร้าง (TODO)
  • การแปลงสภาพเสมือน (TODO)

• โครงสร้างการไหลควบคุม:

  • การกำจัดการกระโดดข้ามการกระโดด
  • ทางออกเดียว
  • วนไซต์ลงจอดเดี่ยว
  • บันได if/if-else/if-elif-else
  • โฟลว์ควบคุม "และ" (ถ้า (a && b))
  • การเลือกที่ผิดปกติผ่านการแยกโหนด
  • ในขณะที่/ทำ-ในขณะที่/วนซ้ำไม่สิ้นสุด
  • โครงสร้างลูปทั่วไป (TODO)
  • การกำจัดบล็อกพื้นฐานที่ไม่สามารถเข้าถึงได้ (TODO)

• รูปแบบเอาต์พุต:

  • หลอกซี
  • PseudoC พร้อมบล็อกพื้นฐานที่มีคำอธิบายประกอบ
  • ค
  • .dot (สำหรับโฟลว์ควบคุม (CFG) และกราฟอื่นๆ)
  • YAML (สำหรับฐานข้อมูลคุณสมบัติฟังก์ชัน)

เครื่องมือพันธมิตรของ ScratchABlock คือ ScratchABit ซึ่งเป็นตัวแยกส่วนแบบโต้ตอบที่มีจุดประสงค์เพื่อดำเนินงานระดับต่ำสุดของกระบวนการถอดรหัสคอมไพล์ เช่น การแยกโค้ดออกจากข้อมูล และการระบุขอบเขตของฟังก์ชัน โดยปกติแล้ว ScratchABit จะทำงานร่วมกับไวยากรณ์แอสเซมเบลอร์สถาปัตยกรรมดั้งเดิม แต่สำหรับสถาปัตยกรรมบางตัว (โดยปกติจะเป็น RISC ที่ซื่อสัตย์) หากมีปลั๊กอินที่เหมาะสม ปลั๊กอินก็สามารถส่งออกไวยากรณ์ PseudoC ซึ่งสามารถทำหน้าที่เป็นอินพุตไปยัง ScratchABlock ได้