เทคนิค C-Reduce ที่ใช้ได้กับทุกภาษา

 (bernsteinbear.com)
1 คะแนน โดย GN⁺ 2024-11-28 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • C-Reduce เป็นเครื่องมือสำหรับย่อโค้ดที่ใช้จำลองบั๊กของคอมไพเลอร์ C แต่ถ้ามีเงื่อนไขที่กำหนดได้แน่นอน การจำลองที่ทำได้รวดเร็ว และไฟล์ซอร์สที่แก้ไขได้ ก็สามารถนำไปใช้กับภาษาอื่นได้เช่นกัน
  • ตัวอย่างคือกระบวนการย่อบั๊กที่เกิดขึ้นระหว่างรัน scrapscript บน RustPython โดย interesting.sh จะค้นหาข้อความผิดพลาดที่กำหนดเพื่อใช้ตัดสินว่ายังจำลองบั๊กได้หรือไม่
  • เพียงรัน creduce --not-c interesting.sh scrapscript.py ขนาดไฟล์ก็ลดลงอย่างรวดเร็ว และเห็นความคืบหน้าช่วงแรกที่ลดลงเกือบ 50%
  • --not-c เป็นออปชันที่ใช้หลีกเลี่ยง reduction pass ที่มีไว้สำหรับ C โดยเฉพาะ จึงช่วยลดเวลาในการรันที่ไม่จำเป็นเมื่ออินพุตเป็น Python เป็นต้น
  • ถ้าสามารถสร้างเงื่อนไขที่ทำให้บั๊กเกิดซ้ำได้เป็นสคริปต์สั้น ๆ ก็สามารถใช้ C-Reduce ทำให้บั๊กรายงานของภาษาที่ไม่ใช่ C มีขนาดเล็กลงและจัดการได้ง่ายขึ้น

เงื่อนไขในการใช้ C-Reduce กับอินพุตที่ไม่ใช่ C

  • C-Reduce เป็นเครื่องมือสำหรับ ย่อโค้ดจำลองบั๊กของคอมไพเลอร์ C ให้เล็กที่สุด ที่สร้างโดย Regehr และเพื่อนร่วมงาน
  • เมื่อไฟล์ C ขนาด 10,000 บรรทัดทำให้เกิดบั๊กใน Clang ก็สามารถใช้เครื่องมือนี้เพื่อลดขนาดไฟล์โดยอัตโนมัติ แทนที่จะส่งไฟล์ขนาดมหึมานั้นไปตรง ๆ
  • แม้จะดูเหมือนเป็นเครื่องมือสำหรับ C โดยเฉพาะ แต่ก็ใช้กับอินพุตของภาษาอื่นได้ หากมีเงื่อนไขต่อไปนี้

    • เงื่อนไขที่กำหนดได้แน่นอน

      • วิธีจำลองบั๊กซ้ำที่ค่อนข้างรวดเร็ว ซึ่งช่วยให้การย่อทำได้เร็วขึ้น
      • ไฟล์ซอร์สที่แก้ไขได้อย่างน้อยหนึ่งไฟล์ที่ C-Reduce สามารถย่อได้
      • เงื่อนไขแบบกำหนดแน่นอนนี้สามารถเลียนแบบแบบความน่าจะเป็นได้ด้วยการใช้ loop wrapper

ตัวอย่างการย่อเคสจำลองบั๊กของ RustPython

  • ระหว่างรัน scrapscript บน RustPython ได้เกิดบั๊กขึ้น และเพื่อรายงานบั๊กนี้จึงมีการเขียนสคริปต์ interesting.sh
  • สคริปต์จะรัน scrapscript.py ด้วย absolute path ของไบนารี RustPython แล้วค้นหาสตริงต่อไปนี้จากเอาต์พุตรวมถึง standard error
    • tried to push value onto stack but overflowed max_stackdepth
  • คำสั่งที่ใช้รันมีดังนี้
    • creduce --not-c interesting.sh scrapscript.py
  • C-Reduce จะรัน interestingness test แบบขนานและค่อย ๆ ลดขนาดไฟล์ลงอย่างรวดเร็ว
    • ตัวอย่างความคืบหน้าจะแสดงเป็น 0.5%, 9.2%, 18.1%, 47.5% เป็นต้น
    • ภายในไม่กี่วินาที ไฟล์ก็ถูกย่อลงเกือบ 50%
    • ตอนที่บทความเขียนจบ กระบวนการย่อไปถึง 96.9% แล้ว
  • หากไม่ใช้ --not-c C-Reduce จะใช้ pass ที่มีไว้สำหรับ C โดยเฉพาะจำนวนมาก
    • สำหรับอินพุต Python pass เหล่านี้อาจทำให้เวลาในการรันช้าลง
    • แต่มีแนวโน้มว่าจะไม่เปลี่ยนผลลัพธ์สุดท้ายอย่างมีนัยสำคัญ
  • เนื้อหาที่เกี่ยวข้องถูกย้ายไปยังหน้า Delta debugging ในภายหลัง

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-11-28
ความคิดเห็นจาก Hacker News

  • เพราะไม่ได้แชร์ไฟล์ที่ย่อแล้วไว้ เลยลองรันเอง โดยบิลด์ RustPython และนำ scrapscript.py มา จากนั้นเปลี่ยนพาธใน interesting.sh แล้วรันด้วย nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py สุดท้ายมันหยุดอยู่แถว ๆ 96.4%, 7347 ไบต์ และผลลัพธ์อยู่ที่ https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

    • นึกขึ้นมาได้ว่ามีคนกังวลว่าโปรแกรมอาจพังระหว่างกระบวนการย่อ แล้วไปทำ งานที่เป็นอันตราย กับเครื่องโลคัลได้ ถ้ารันตัวลดรูปเป็น Nix derivation แบบ source-to-source ก็น่าจะกันพฤติกรรมเสี่ยงได้ และกระจายไปยัง remote builder ได้ง่ายด้วยหรือเปล่า
    • อนึ่ง shrinkray ถ้าปล่อยรันราว 10 นาทีจะย่อได้ถึง 162 ไบต์: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
      ถ้าปล่อยไว้นานกว่านี้อาจดีขึ้นอีกนิด แต่ดูเหมือนแทบไม่คืบแล้ว เลยเบื่อและหยุดมันไป

  • แม้แต่ John Regehr ผู้เขียน C-Reduce ก็แนะนำให้ลอง Shrinkray สำหรับงานแบบนี้ โดยบอกว่า Shrinkray ถูกสร้างมาให้ทำงานได้โดยไม่ขึ้นกับฟอร์แมต และเป็นเครื่องมือที่เหมาะในกรณีที่ C-Reduce ทำได้ไม่ดี: https://mastodon.social/@regehr/113489759789563570

    • รีโพซิทอรีนี้เป็นรีโพซิทอรีทางการของ Shrinkray ไหม? https://github.com/DRMacIver/shrinkray
    • อยากพูดถึง cvise ด้วย: https://github.com/marxin/cvise
      มันเป็น ทางเลือกแบบ Python ที่ทำงานได้ค่อนข้างดีกับภาษาที่ไม่ใช่ C ด้วย

  • มีบทความวิชาการที่อธิบายวิธีทำงาน เขียนโดย John Regehr และผู้เขียนร่วมในปี 2012: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

    • อ่านบทความนี้แล้วก็ยังไม่ค่อยเข้าใจว่ามันเป็นไปได้อย่างไร ดูเหมือนมันจะเข้าใจ การ tokenization, การรวมบรรทัด, การลบโทเคน ฯลฯ สำหรับภาษาโปรแกรมใด ๆ ก็ได้ เลยสงสัยว่ามีบทความอีกฉบับที่อธิบายเฉพาะอัลกอริทึมนี้หรือไม่
    • บทความนี้ไม่ได้ว่าด้วย C-Reduce ทั้งหมด แต่พูดถึง ตัวลดรูป test case แบบเฉพาะโดเมน 3 ตัวที่เพิ่มเข้าไปในโปรเจกต์
      เท่าที่จำได้ การย่อแบบไม่เฉพาะโดเมนส่วนใหญ่ของ C-Reduce ค่อนข้างใกล้เคียงกับ brute force แบบเรียบง่าย

  • เพิ่งรู้จัก C-Reduce เมื่อกี้ แต่ติดใจเข้าแล้ว ให้ความรู้สึกคล้ายตอนค้นพบ git bisect ครั้งแรก
    คงต้องเก็บไว้ในมุมหนึ่งของหัว เพื่อใช้ในวันที่เจอสถานการณ์ที่เหมาะ

    • ตอนอยู่ทีมคอมไพเลอร์ C/C++ ในงานแรกหลังเรียนจบมหาวิทยาลัย ผมเคยทำงานแบบนี้ด้วยมือ การที่ทำสิ่งเดียวกันแบบอัตโนมัติได้ถือว่าน่าทึ่งมาก
    • เคยเจอสิ่งที่ดูเหมือนเป็นบั๊กของคอมไพเลอร์ใน cc65 ซึ่งเป็น C compiler สำหรับโปรเซสเซอร์ 6502 เป้าหมายคือ C64, NES, Apple 1 และอื่น ๆ
      กำลังคิดว่าจะลองตั้งค่าดู เพราะ VICE รองรับการ “เขียนออก” ไปยังไฟล์ของระบบปฏิบัติการโฮสต์ จึงน่าจะรันทดสอบในอีมูเลเตอร์ได้
    • ใช้คู่กับ ตัวสร้างอินพุตทดสอบแบบสุ่ม ได้ยอดเยี่ยม

  • delta debugging ไม่ใช่แนวคิดใหม่: https://en.wikipedia.org/wiki/Delta_debugging
    delta ซึ่งเป็น implementation ของ delta debugging ที่ผมทำ มีอายุมากกว่า 19 ปีแล้ว: https://github.com/dsw/delta
    ตอนที่ Microsoft เรียกโอเพนซอร์สว่าเป็น “มะเร็ง” Microsoft Research ถึงกับส่งคนมาที่ออฟฟิศผมเพื่อขอให้เผยแพร่มัน แล้วผมก็ปล่อยเป็นโอเพนซอร์ส เครื่องมือนี้ยังเป็นที่รู้จักพอสมควร เพราะในบทแนะนำ LLVM ของ Latner ก็พูดถึง “เครื่องมือ delta debugging มาตรฐาน” เช่นกัน: https://aosabook.org/en/v1/llvm.html

    • C-Reduce ซับซ้อนกว่าการทำ delta debugging แบบธรรมดาเล็กน้อย ตามบทคัดย่อของบทความปี 2012 ชื่อ "Test-Case Reduction for C Compiler Bugs" ผลลัพธ์จาก C-Reduce มีขนาดเล็กกว่าตัวลดรูปอื่น ๆ หรือแม้แต่ตัวลดรูปที่นักพัฒนาคอมไพเลอร์ใช้กันมากที่สุดในตอนนั้นโดยเฉลี่ย มากกว่า 25 เท่า
      นั่นหมายความว่าการย่อโปรแกรมอย่างมีประสิทธิภาพต้องการมากกว่าแค่ delta debugging แบบง่าย ๆ แน่นอนว่า C-Reduce เองก็เป็นเครื่องมืออายุ 12 ปีแล้วเช่นกัน
      ในขณะเดียวกัน BugPoint ซึ่งเป็นเครื่องมือของ LLVM ที่ลิงก์ไว้ ก็ใช้ได้เฉพาะกับ LLVM IR เท่านั้น ขณะที่ C-Reduce ดูจะใช้งานได้ทั่วไปมากกว่า เครื่องมือและเทคนิคสำหรับย่อ test case อัตโนมัติยังคงไม่คุ้นเคยสำหรับนักพัฒนาส่วนใหญ่ ดังนั้นแม้แนวคิดนี้จะเป็นที่รู้จักในวงการมานานแล้ว โพสต์นี้ก็ยังอาจมีประโยชน์

  • เจอบทความที่มีตัวอย่างก่อนและหลัง: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
    ถึงอย่างนั้นก็ยังไม่เข้าใจนักว่าในแต่ละรอบมันรู้ได้อย่างไรว่าควร ลบอะไร น่าจะมีการ tokenization อยู่บ้าง แต่ไม่แน่ใจว่ามันทำงานข้ามหลายภาษาโปรแกรมได้อย่างไร

  • creduce ยอดเยี่ยมมาก
    ตอนพัฒนา LLVM target backend แปลก ๆ ผมเคยใช้สคริปต์ทดสอบที่สร้างโปรแกรมสุ่มด้วย CSmith ต่อเนื่องเป็นชั่วโมง ๆ พอเกิด crash มันก็จะรัน C-Reduce อัตโนมัติแล้วทิ้งไฟล์ไว้ให้ตรวจสอบ ซึ่งช่วยได้มากจริง ๆ

  • ใช้ได้ดีกับ SQL ด้วย ใช้อยู่ในงานจริง และได้รู้จักผ่าน https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...

  • ถ้าไม่อธิบายว่าทำไมมันถึงใช้กับภาษาอื่นนอกจาก C ได้ ก็เป็นคำกล่าวอ้างที่เชื่อได้ยาก ไม่ได้คิดว่าโกหก แต่พอได้ยินว่าทำแบบนั้นได้โดย ไม่ใช้ LLM ก็ยังอึ้งอยู่

    • พูดสั้น ๆ คือมีบาง reduction pass ที่ทำให้เป็นทั่วไปกับภาษาตระกูล Cได้ค่อนข้างดี และ pass พวกนี้ก็อยู่ในกลุ่มที่มีประสิทธิภาพที่สุดด้วย
      ตัวอย่างเช่น หลังจาก tokenize อินพุตแบบภาษา C แล้วสุ่มทิ้งชิ้นส่วนยาวประมาณ 1~13 หน่วย วิธีนี้ใช้ได้ผลดีกับการลบ qualifier หรือ attribute ที่ไม่จำเป็น เพราะภาษาส่วนใหญ่ที่คล้าย C มีกฎการ tokenize คล้ายกัน อีกทั้ง pass ที่ลบหน่วยวงเล็บที่สมดุลอย่าง (), {}, [] ก็มีประโยชน์กับแทบทุกภาษา การลบคอมเมนต์และช่องว่างก็ได้ผลเช่นกัน เพราะหลายภาษาใช้สไตล์ /* */, // แบบเดียวกับ C
      จริง ๆ แล้ว pass ที่เฉพาะกับ C/C++ อย่างมากมีไม่เยอะ จากประสบการณ์ จุดอ่อนใหญ่ข้อหนึ่งของ creduce คือมันทำขั้นตอนย่อที่ลบเทมเพลตได้แย่มาก ทั้งที่เป็นงานที่ดูเหมือนจะทำให้เป็นอัตโนมัติได้ค่อนข้างง่าย
    • แนะนำให้ลองเปิดดูบทความ PLDIที่ asmeurer ลิงก์ไว้ สรุปไว้ดีมาก
      การแปลงบางอย่างค่อนข้างเฉพาะกับ C เพราะใช้ Clang frontend ส่วนบางอย่างก็ทั่วไปพอสมควร จึงมีโอกาสสูงว่าจะใช้ได้กับภาษาตระกูล Algol โดยรวม และเพราะเป็นเครื่องมือแบบแยกส่วน ถ้าต้องการก็เพิ่มการแปลงที่เข้าใจภาษาอื่นได้
    • นี่ใกล้เคียงกับ วิทยาการคอมพิวเตอร์ แบบยุคก่อนมากกว่า หวังว่า HN คงยังไม่ได้ลืมวิทยาการคอมพิวเตอร์แบบดั้งเดิมไปหมดแล้ว
      ที่พูดถึงตรงนี้คือพวกอัลกอริทึม ไม่ใช่แมชชีนเลิร์นนิงชวนหลอนอะไรแบบนั้น จะนับพวกใช้ Prolog ทำ AI ด้วยก็ได้ แต่ก็มีข้อเสียเล็กน้อยคือมันทำงานได้ไม่ค่อยดีนักถ้าจุดประสงค์คือสร้าง AI
    • ถ้าไม่เข้าใจว่ามันทำงานอย่างไร ก็ไม่รู้เหมือนกันว่าใช้แบบนี้จะปลอดภัยหรือเปล่า creduce อาจรันสคริปต์อินพุตที่ถูกดัดแปลงแล้วลบไฟล์ของฉัน หรือกินข้าวกลางวันฉันไปเลยก็ได้งั้นหรือ?
    • เดาเอาโดยยังไม่ได้อ่านบทความ มันน่าจะคล้าย fuzzer ที่ใช้การกลายพันธุ์ซึ่งมุ่งไปในทางลดขนาดอินพุต

  • ถ้าเทียบกับ dustmite เป็นอย่างไร? https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...