Kỹ thuật C-Reduce có thể dùng với bất kỳ ngôn ngữ nào

• C-Reduce là công cụ rút gọn mã tái hiện lỗi trình biên dịch C, nhưng cũng có thể áp dụng cho các ngôn ngữ khác nếu có điều kiện xác định, cách tái hiện nhanh và tệp nguồn có thể chỉnh sửa
• Ví dụ là quá trình rút gọn một lỗi phát sinh khi chạy scrapscript trong RustPython, trong đó interesting.sh tìm một thông báo lỗi cụ thể để xác định lỗi có tái hiện hay không
• Chỉ cần chạy creduce --not-c interesting.sh scrapscript.py, kích thước tệp đã giảm nhanh chóng, và có thể thấy tiến trình ban đầu gần như giảm 50%
• --not-c là tùy chọn tránh các lượt rút gọn dành riêng cho C, giúp giảm thời gian chạy không cần thiết với đầu vào như Python
• Nếu có thể tạo một script ngắn mô tả điều kiện tái hiện lỗi, các báo cáo lỗi cho ngôn ngữ không phải C cũng có thể được C-Reduce làm nhỏ hơn và dễ xử lý hơn

---

Điều kiện để dùng C-Reduce với đầu vào không phải C

• C-Reduce là công cụ tối thiểu hóa mã tái hiện lỗi trình biên dịch C do Regehr và các cộng sự tạo ra
• Khi một tệp C 10.000 dòng gây lỗi Clang, có thể dùng công cụ này để tự động rút gọn thay vì gửi nguyên tệp khổng lồ đó
• Dù trông giống một công cụ chuyên cho C, nó vẫn có thể dùng với đầu vào ở ngôn ngữ khác nếu có các điều kiện sau

  • Điều kiện xác định

    • Một cách tái hiện tương đối nhanh, giúp tăng tốc độ rút gọn
    • Một hoặc nhiều tệp nguồn có thể chỉnh sửa mà C-Reduce có thể rút gọn
    • Điều kiện xác định cũng có thể được mô phỏng theo xác suất bằng cách dùng wrapper vòng lặp

Ví dụ rút gọn tái hiện lỗi RustPython

• Một lỗi đã xảy ra khi chạy scrapscript trong RustPython, và để báo cáo lỗi này, script interesting.sh đã được viết
• Script chạy scrapscript.py bằng đường dẫn tuyệt đối của binary RustPython, rồi tìm chuỗi sau trong đầu ra, bao gồm cả lỗi tiêu chuẩn
  • tried to push value onto stack but overflowed max_stackdepth
• Lệnh chạy như sau
  • creduce --not-c interesting.sh scrapscript.py
• C-Reduce chạy song song các interestingness test và nhanh chóng giảm kích thước tệp
  • Tiến trình ví dụ được hiển thị ở các mức như 0,5%, 9,2%, 18,1%, 47,5%
  • Trong vài giây, tệp đã được giảm gần 50%
  • Đến thời điểm kết thúc bài viết, mức rút gọn đạt 96,9%
• Nếu không dùng --not-c, C-Reduce sẽ sử dụng nhiều pass dành riêng cho C
  • Với đầu vào Python, các pass này có thể làm chậm thời gian chạy
  • Khả năng cao là bản thân kết quả sẽ không thay đổi đáng kể
• Nội dung liên quan sau đó được chuyển sang trang Delta debugging

[GN⁺]

Ý kiến trên Hacker News

• Vì họ không chia sẻ tệp đã được thu nhỏ nên tôi tự chạy thử. Sau khi build RustPython, lấy scrapscript.py, rồi đổi đường dẫn trong interesting.sh và chạy bằng nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py, cuối cùng nó dừng ở khoảng 96,4%, 7347 byte, kết quả nằm tại https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

  • Chợt nghĩ, có người lo rằng trong quá trình thu nhỏ, chương trình có thể bị hỏng và thực hiện thao tác phá hoại trên máy cục bộ. Nếu chạy bộ thu nhỏ như một Nix derivation source-to-source thì có lẽ sẽ ngăn được hành vi nguy hiểm và cũng dễ triển khai lên remote builder hơn
  • Nhân tiện, nếu chạy shrinkray khoảng 10 phút thì có thể giảm xuống còn 162 byte: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
    Để lâu hơn có thể còn tốt hơn chút nữa, nhưng trông gần như bị kẹt nên tôi chán và dừng lại

• John Regehr, tác giả của C-Reduce, cũng khuyên nên thử Shrinkray cho mục đích này. Ông nói Shrinkray được thiết kế để hoạt động độc lập với định dạng, và là công cụ phù hợp ngay cả trong những trường hợp C-Reduce làm không tốt: https://mastodon.social/@regehr/113489759789563570

  • Đây có phải repository chính thức của Shrinkray không? https://github.com/DRMacIver/shrinkray
  • Cũng muốn nhắc đến cvise: https://github.com/marxin/cvise
    Đây là một lựa chọn thay thế bằng Python hoạt động khá tốt cả với các ngôn ngữ không phải C

• Có một bài báo năm 2012 của John Regehr và các tác giả khác giải thích cách nó hoạt động: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

  • Tôi đã đọc bài này mà vẫn chưa hình dung được làm sao có thể làm được. Nó có vẻ như hiểu token hóa, gộp dòng, loại bỏ token, v.v. đối với một ngôn ngữ lập trình bất kỳ; không biết có bài báo nào khác chỉ giải thích riêng thuật toán này không
  • Bài báo này không nói về toàn bộ C-Reduce, mà về 3 bộ thu nhỏ test case chuyên biệt theo miền được thêm vào dự án
    Theo tôi nhớ, phần lớn các phép thu nhỏ không chuyên biệt theo miền của C-Reduce gần như chỉ là brute force đơn giản

• Tôi vừa mới biết đến C-Reduce mà đã bị cuốn vào rồi. Cảm giác giống như lần đầu phát hiện ra git bisect
  Phải cất nó vào một góc trong đầu để sau này gặp đúng tình huống thì dùng

  • Ở công việc đầu tiên sau khi tốt nghiệp đại học, khi ở trong nhóm compiler C/C++, tôi từng làm việc kiểu này thủ công. Khá ngạc nhiên là có thể tự động hóa cùng việc đó
  • Tôi từng gặp một vấn đề có vẻ là bug compiler trong cc65, compiler C cho vi xử lý 6502. Mục tiêu là những máy như C64, NES, Apple 1
    Có lẽ tôi sẽ thử thiết lập. Vì VICE hỗ trợ chức năng “xuất” ra tệp của hệ điều hành host, có vẻ có thể chạy test trong emulator
  • Dùng cùng với bộ sinh input kiểm thử ngẫu nhiên thì rất tuyệt

• Delta debugging không phải khái niệm mới: https://en.wikipedia.org/wiki/Delta_debugging
  Bản triển khai delta debugging do tôi tạo, delta, đã hơn 19 năm tuổi: https://github.com/dsw/delta
  Vào thời Microsoft còn gọi open source là “ung thư”, Microsoft Research đã cử người tới tận văn phòng tôi để đề nghị tôi công khai nó, nên tôi đã phát hành dưới dạng open source. Trong phần giới thiệu LLVM của Latner cũng nhắc tới “công cụ delta debugging tiêu chuẩn”, nên đây là một công cụ khá nổi tiếng: https://aosabook.org/en/v1/llvm.html

  • C-Reduce tinh vi hơn một chút so với delta debugging đơn thuần. Theo phần tóm tắt của bài báo năm 2012 “Test-Case Reduction for C Compiler Bugs”, kết quả của C-Reduce trung bình nhỏ hơn hơn 25 lần so với các bộ thu nhỏ khác hoặc bộ thu nhỏ mà các nhà phát triển compiler thường dùng nhất trước đó
    Tức là kết luận ở đây là để thu nhỏ chương trình hiệu quả thì cần nhiều hơn delta debugging đơn giản. Tất nhiên C-Reduce giờ cũng đã là công cụ 12 năm tuổi
    Đồng thời, công cụ LLVM được liên kết là BugPoint chỉ dành riêng cho LLVM IR, trong khi C-Reduce có vẻ tổng quát hơn. Các công cụ và kỹ thuật tự động tối thiểu hóa test case vẫn còn xa lạ với đa số lập trình viên, nên bài viết này có thể hữu ích dù là ý tưởng đã được biết đến từ lâu trong lĩnh vực đó

• Tìm thấy một bài có ví dụ trước/sau: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
  Dù vậy tôi vẫn chưa hiểu rõ làm sao nó biết nên loại bỏ gì ở mỗi vòng lặp. Chắc hẳn phải có token hóa ở mức nào đó, nhưng không biết cơ chế đó hoạt động ra sao trên nhiều ngôn ngữ lập trình

• creduce rất tuyệt
  Khi phát triển backend cho một target LLVM khá lạ, tôi từng viết script test dùng CSmith để sinh các chương trình kiểm thử ngẫu nhiên trong nhiều giờ. Nếu xảy ra crash, nó tự động chạy C-Reduce và để lại tệp cho tôi kiểm tra, thực sự rất hữu ích

• Hoạt động tốt cả với SQL. Tôi đang dùng trong công việc thực tế, và biết đến nó qua https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...

• Nếu không giải thích lý do nó hoạt động được cả với các ngôn ngữ ngoài C thì đây là một tuyên bố khó tin. Tôi không nghĩ là nói dối, nhưng việc làm được mà không có LLM khiến tôi khá bối rối

  • Nói ngắn gọn, một số pass rút gọn được khái quát hóa khá tốt cho các ngôn ngữ họ C, và những pass này thuộc nhóm hiệu quả nhất
    Ví dụ, cách token hóa đầu vào theo kiểu C rồi ngẫu nhiên bỏ các khối dài khoảng 1~13 token hoạt động tốt trong việc loại bỏ các định danh bổ sung hoặc thuộc tính không cần thiết, vì hầu hết ngôn ngữ giống C có quy tắc token hóa tương tự. Pass loại bỏ theo đơn vị ngoặc cân bằng (), {}, [] cũng hữu ích trong gần như mọi ngôn ngữ. Việc loại bỏ chú thích và khoảng trắng cũng hiệu quả vì nhiều ngôn ngữ dùng kiểu /* */, // giống C
    Thực tế, không có nhiều pass chỉ dành riêng cho C/C++. Theo kinh nghiệm, một trong những điểm yếu lớn của creduce là nó làm rất tệ bước rút gọn để loại bỏ template, tức một việc trông có vẻ tương đối dễ tự động hóa
  • Tôi khuyên nên đọc lướt bài báo PLDI mà asmeurer đã liên kết. Phần tóm tắt khá tốt
    Một số biến đổi khá đặc thù cho C vì dùng frontend Clang, còn một số thì khá tổng quát nên có khả năng hoạt động với hầu hết ngôn ngữ họ Algol. Vì đây là công cụ dạng mô-đun, nếu muốn bạn cũng có thể thêm các biến đổi hiểu ngôn ngữ khác
  • Cái này gần với khoa học máy tính kiểu cũ hơn. Hy vọng HN chưa quên mất truyền thống khoa học máy tính đó
    Ý ở đây là những thứ như thuật toán, chứ không phải học máy đáng sợ gì cả. Nó cũng bao gồm kiểu dùng Prolog cho AI, nhưng có nhược điểm nhỏ là không hoạt động tốt cho mục đích tạo AI
  • Nếu không hiểu cách nó hoạt động, tôi không biết dùng theo cách này có an toàn không. Liệu creduce có thể chạy script đầu vào đã bị biến đổi rồi xóa file của tôi hoặc ăn mất bữa trưa của tôi không?
  • Nếu đoán mà chưa đọc bài báo, tôi nghĩ nó giống một fuzzer áp dụng các đột biến theo hướng giảm kích thước đầu vào

• So với dustmite thì thế nào? https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...