Bộ rút gọn test case là công cụ gỡ lỗi bị đánh giá thấp

• Khi cần tìm phần gây ra sự cố trong một đầu vào lớn, bộ rút gọn test case sẽ tự động thu nhỏ đầu vào để việc gỡ lỗi trở nên dễ dàng hơn
• Bộ rút gọn nhận chương trình, đầu vào và bài kiểm tra tính thú vị, rồi lặp lại việc kiểm tra xem các đầu vào ứng viên ngắn hơn có tái hiện cùng một vấn đề hay không
• Ngay cả một bộ rút gọn xóa dòng đơn giản cũng có thể để lại chỉ một từ dài trong /usr/share/dict/words, và trong ví dụ C đã giảm từ 78 dòng xuống 54 dòng trong chưa đầy 10 giây
• Bài kiểm tra tính thú vị cần được viết chính xác và nhanh vì có các yếu tố như rút gọn quá mức, thực thi chậm, chạy vô hạn và môi trường chạy song song
• Ngoài độ dài đầu vào, việc đưa các chỉ số như tần suất phát sinh lỗi hoặc độ dài vết thực thi vào bài kiểm tra tính thú vị sẽ hữu ích cho việc gỡ lỗi bug không xác định và các log vết lớn

---

Thu nhỏ test case

• Khi chương trình bị crash với một đầu vào lớn và bạn không biết phần nào của đầu vào là nguyên nhân, việc thu nhỏ đầu vào sẽ giúp dễ xác định nguồn gốc vấn đề hơn
• Thu nhỏ thủ công là cách xóa một phần đầu vào trong trình soạn thảo văn bản rồi kiểm tra xem crash tương tự còn được giữ lại hay không
• Khi thu nhỏ thủ công, con người rất dễ bỏ lỡ nhiều cơ hội xóa, và sau khi xóa thì chương trình có thể kết thúc bình thường hoặc tạo ra một lỗi bình thường khác
• Nếu phải xóa đồng thời hai phần A và B ở xa nhau mới có tác dụng, không gian tìm kiếm sẽ tăng lên rất nhiều

Cấu trúc cơ bản của bộ rút gọn test case

• Bộ rút gọn test case là công cụ nhận chương trình, đầu vào và bài kiểm tra tính thú vị để làm cho đầu vào ngắn hơn
• Bài kiểm tra tính thú vị trả về 0 nếu đầu vào đã thu nhỏ vẫn tái hiện lỗi mà ta quan tâm, và trả về giá trị khác 0 nếu không
• Việc rút gọn 95~99% là chuyện thường gặp với bộ rút gọn test case, và có thể khiến việc gỡ lỗi dễ hơn rất nhiều
• Bộ rút gọn vẫn hoạt động dù không cần hiểu về mặt ngữ nghĩa phải loại bỏ phần nào của đầu vào

• Ví dụ bộ rút gọn đơn giản

  • Chương trình ví dụ đọc các dòng từ một tệp và in Word too long nếu có dòng dài hơn 25 ký tự
  • Bài kiểm tra tính thú vị trả về 0 nếu đầu ra của chương trình có Word too long, và trả về 1 nếu không có
  • Bộ rút gọn Python đơn giản đọc đầu vào theo từng dòng, ghi đầu vào ứng viên đã xóa một dòng vào tệp tạm rồi chạy bài kiểm tra tính thú vị
  • Nếu đầu vào ứng viên là thú vị thì thay đầu vào hiện tại bằng ứng viên đó, và khi không thể thu nhỏ thêm nữa thì in kết quả ra stdout
  • Kết quả chạy trên /usr/share/dict/words để lại duy nhất antidisestablishmentarianism

Bộ rút gọn mạnh hơn và Shrink Ray

• Ví dụ chương trình C 78 dòng xử lý vấn đề đầu ra khác nhau giữa cấu hình FAST=0 và FAST=1
• Bài kiểm tra tính thú vị chỉ vượt qua khi biên dịch với hai cấu hình, rồi đầu ra của FAST=0 là 0d754a56 còn đầu ra của FAST=1 khác giá trị đó
• Bộ rút gọn đơn giản có thể giảm đầu vào C 78 dòng xuống 54 dòng trong chưa đầy 10 giây, tương đương khoảng 30% theo số dòng
• Nếu thêm i=0 để mỗi khi tìm thấy một ứng viên thú vị thì quay lại xóa từ dòng đầu tiên, thời gian chạy tăng gần 10 lần nhưng giảm thêm được 3 dòng
• Shrink Ray cung cấp nhiều quy tắc rút gọn và chạy song song; khi thêm --no-clang-delta thì nó không dùng kiến thức chuyên biệt cho C
• Sau khoảng 15 phút, Shrink Ray đã giảm đầu vào hơn 60% theo số byte, và ở trường hợp khác thì sau khoảng 20 phút đã tìm được mức giảm 90% rồi tiếp tục xuống tới 99%
• Shrink Ray biết cú pháp chú thích chuẩn và thử loại bỏ chúng từ sớm, đồng thời cũng thử thu nhỏ các số nguyên thành giá trị nhỏ hơn

Khó khăn khi viết bài kiểm tra tính thú vị

• Bộ rút gọn test case tuân theo bài kiểm tra tính thú vị một cách máy móc, nên nếu bài kiểm tra cho qua sai thì sẽ xảy ra rút gọn quá mức, tức là rút xa hơn điểm bạn mong muốn
• Shrink Ray kiểm tra rõ ràng xem bài kiểm tra tính thú vị có chấp nhận đầu vào rỗng hay không, và tình huống này có thể xảy ra khá thường xuyên
• Trong ví dụ C, nếu chỉ kiểm tra hai đầu ra có khác nhau hay không thì những khác biệt đầu ra không quan trọng hoặc dễ gây hiểu lầm cũng có thể bị phân loại là đầu vào thú vị
• Kiểm tra test "$slow_out" = "0d754a56" xác nhận phiên bản chậm thực sự thực hiện hành vi mong đợi, từ đó giảm khả năng rút gọn quá mức

• Tốc độ và timeout

  • Nếu bài kiểm tra tính thú vị chạy nhanh, bộ rút gọn có thể chạy nó hàng trăm lần mỗi giây
  • Ngay cả ví dụ cỡ trung cũng có thể dẫn tới hàng trăm nghìn lần thử rút gọn, nên tối ưu bài kiểm tra tính thú vị ảnh hưởng lớn đến tổng thời gian
  • Có trường hợp tăng tốc bài kiểm tra tính thú vị khoảng 3 lần bằng cách tắt cơ chế tự động tạo core dump
  • Bộ rút gọn có thể xóa một dòng như i-=1, biến một chương trình vốn kết thúc được thành chương trình chạy vô hạn
  • Nếu chương trình chạy trong 0,1 giây nhưng timeout lại đặt thành 60 giây, toàn bộ quá trình rút gọn sẽ chậm đi rất nhiều
  • Với chương trình nhanh, người ta thường làm tròn timeout lên 1~2 giây; còn lại thì đặt khoảng 1,5~2 lần thời gian chạy ban đầu

• Chạy song song

  • Các bộ rút gọn như Shrink Ray chạy bài kiểm tra tính thú vị theo kiểu song song
  • Shrink Ray chạy từng bài kiểm tra tính thú vị trong thư mục tạm và tự động dọn dẹp thư mục đó
  • Nhưng chỉ thư mục tạm thôi đôi khi vẫn chưa đủ, và biện pháp cần thiết sẽ khác nhau tùy từng trường hợp

Dùng bài kiểm tra tính thú vị để ép tính xác định

• Mẩu ví dụ tạo lỗi chia cho 0 vì len([])==0, nhưng do điều kiện random.random() < 0.33 nên vấn đề chỉ xuất hiện ở khoảng một phần ba số lần chạy
• Bug không xác định khiến lỗi xuất hiện rồi biến mất ngẫu nhiên, làm việc kiểm chứng giả thuyết khó hơn và tốn thời gian hơn
• Nếu bộ rút gọn loại bỏ lời gọi random.random() hoặc thay đổi biểu thức điều kiện, lỗi không xác định có thể biến thành lỗi xác định
• Trong thực tế, tính không xác định thường do nhiều phần của đầu vào tương tác theo cách bất lợi, nên có thể khó loại bỏ
• Bộ rút gọn test case hoạt động giống một thuật toán leo đồi dùng độ dài đầu vào làm chỉ số thay thế cho “tốt hơn”
• Cách tiếp cận leo đồi dễ mắc kẹt ở điểm tối ưu cục bộ, và đầu vào ngắn hơn không phải lúc nào cũng tốt hơn cho việc truy tìm lỗi

• Cách chạy lặp lại

  • Khi xử lý bug không xác định, người ta dùng bài kiểm tra tính thú vị chạy đầu vào nhiều lần và chấp nhận đầu vào nếu lỗi quan tâm xuất hiện ít nhất một lần
  • Cách này có thể giúp tăng tần suất xuất hiện của lỗi
  • Một bài kiểm tra chỉ cần xuất hiện ít nhất một lần để vượt qua vẫn chấp nhận đầu vào không xác định, nên khi quá trình rút gọn diễn ra thì tính không xác định thậm chí có thể tăng lên
  • Cách nghiêm ngặt hơn là chỉ chấp nhận đầu vào khi lỗi xuất hiện trong cả n lần lặp
  • Bài kiểm tra nghiêm ngặt khiến xác suất đầu vào ban đầu vượt qua thấp, nên khó bắt đầu Shrink Ray; với điều kiện lặp 3 lần trong ví dụ thì xác suất vượt qua ban đầu là 3,6%
  • Một cách lách thực tế là bắt đầu với bài kiểm tra kiểu “lỗi xuất hiện ít nhất 1 lần trong n lần”, rồi khi có được đầu vào đã thu nhỏ mà lỗi xảy ra thường xuyên hơn thì chuyển sang bài kiểm tra “lỗi xuất hiện liên tiếp n lần”

Bộ đếm toàn cục và các chỉ số mục tiêu khác

• Can thiệp thủ công rất mạnh, nhưng bạn phải theo dõi Shrink Ray và rất dễ bỏ lỡ đúng thời điểm để can thiệp
• Nếu muốn dẫn bộ rút gọn bằng thuộc tính khác ngoài độ dài đầu vào, bạn có thể ép thuộc tính đó bên trong một bài kiểm tra tính thú vị duy nhất
• Trong gỡ lỗi yk, thứ quan trọng hơn độ dài đầu vào là độ dài vết thực thi, tức giá trị gần với số lệnh chương trình đã chạy
• Đầu ra YKD_LOG="$t:jit-asm" ghi IR vết dạng văn bản và lệnh máy vào tệp; đầu ra jit-asm ngắn hơn sẽ giúp gỡ lỗi dễ hơn
• wc -l đếm số dòng của tệp log và được dùng như một chỉ số thay thế gần đúng cho độ dài vết
• Bài kiểm tra tính thú vị sẽ coi đầu vào là không thú vị nếu số dòng vết hiện tại lớn hơn mức thấp nhất trước đó, và giá trị thấp nhất được lưu trong /tmp/global_best
• Cách này không an toàn trong rút gọn song song và bao hàm các giả định về cách bộ rút gọn được gọi, nhưng với một script ngắn dùng rồi bỏ thì đây được xem là sự không hoàn hảo có thể chấp nhận
• Trong một ca segfault của yk, cách rút gọn thông thường để lại vết dài 40K dòng, nhưng kỹ thuật này tạo ra vết 10.1K dòng thay vì đầu vào thu nhỏ hơn, và giúp xác định bug gốc trong vòng 30 phút

Tóm tắt chính

• Bộ rút gọn test case không chỉ hữu ích cho người viết compiler mà còn có thể dùng cho các vấn đề ngoài compiler
• Ngoài mục tiêu cơ bản là giảm độ dài đầu vào, bạn còn có thể dẫn hướng bằng các thuộc tính như tần suất lỗi, thời gian thực, mức độ không xác định và độ dài vết thông qua bài kiểm tra tính thú vị
• Độ chính xác, tốc độ chạy, timeout và độ an toàn khi chạy song song của bài kiểm tra tính thú vị quyết định hiệu quả thực tế của bộ rút gọn
• Dù gần như không cần hiểu ngữ nghĩa của đầu vào và chương trình, bộ rút gọn vẫn có thể giữ vấn đề ở dạng nhỏ hơn để tăng năng suất gỡ lỗi

[GN⁺]

Ý kiến trên Lobste.rs

• Thật sự tôi thắc mắc, có ai lại không công nhận giá trị của thu gọn test case tự động không? Từ “bị đánh giá thấp” nghe như thể có người không phải lúc nào cũng muốn thu gọn test case vậy
  Ngay cả khi có thể khoanh vùng bug ngay lập tức, chẳng phải vẫn cần các trường hợp đã được thu gọn để làm kiểm thử hồi quy sao?

  • Có lẽ đa số lập trình viên thậm chí chưa từng nghĩ về nó như một kỹ thuật
  • Câu đầu của bài viết là “Test-case reducers are less well known than they should be, [...]”, và với tư cách là người đã khuyên mọi người dùng fuzzing và kiểm thử dựa trên thuộc tính trong nhiều năm, đúng là như vậy thật
    Cả hai thường bao gồm việc thu gọn ca thất bại hay dạng “shrinking” nào đó, và nhờ vậy mà dùng thực tế hơn rất nhiều
  • Trong giới fuzzer thì người ta biết ở mức tương đối. Sau khi fuzzer tìm ra ca thất bại, nó sẽ tự động thu gọn, và phần đó hoạt động rất tốt
    Tuy vậy, theo trải nghiệm của tôi với fuzzing nói chung, đặc biệt là dùng AmericanFuzzyLop và AFL++, việc cấu hình quá đau đầu nên nhìn chung tôi hay tránh
    Hơn nữa, phần lớn bug tôi gặp không phải kiểu “đưa file đầu vào này vào là chạy sai”, mà gần hơn với “một người dùng nào đó ở đâu đó gặp hành vi sai”. Đôi khi có thể rút xuống thành “thực hiện một chuỗi bước trong điều kiện nhất định thì chạy sai”, nhưng 1) tôi không rõ áp dụng công cụ thu gọn test case tự động vào kiểu “người dùng làm việc gì đó theo thứ tự” như thế nào, và 2) một khi đã tìm được cách tái hiện cục bộ thì coi như 99% công việc debug đã xong
    Có lẽ tác giả sẽ xem thái độ này của tôi là “đánh giá thấp”
  • Có lẽ ngay cả số người biết thu gọn test case là gì cũng đã rất ít

• Bài viết và ví dụ này nói rằng bộ thu gọn nên được dùng rộng rãi hơn cả trong các tình huống không phải compiler, nhưng góc nhìn vẫn nghiêng khá nhiều về phía người viết compiler
  Như ~silentbicycle đã viết, phần lớn việc thu gọn test case diễn ra trong ngữ cảnh fuzzer hoặc kiểm thử dựa trên thuộc tính, nơi chức năng thu gọn được tích hợp sẵn trong một framework lớn hơn. Compiler là một trong số ít lĩnh vực đặc biệt mà bộ thu gọn test case độc lập thật sự hữu ích. Tôi cũng không rõ còn trường hợp nào khác mà bộ thu gọn độc lập lại giúp được nhiều hay không
  Phần về tính quyết định cũng thú vị. Ví dụ bắt đầu từ trường hợp tính quyết định đến từ file đầu vào gây bug, tức script, chứ không phải do đặc tính của chính chương trình có bug là interpreter. Bài viết không nói rõ liệu kỹ thuật “interestingness” có áp dụng được cho các tình huống không phải compiler, nơi chính chương trình có bug là không quyết định, hay không
  Một cách để biến bài toán kiểm thử cho phù hợp với fuzzing và thu gọn test case là tạo ra một tập lệnh mệnh lệnh có đánh số. Mỗi lệnh nên có một kiểm tra nhất quán nhẹ để phát hiện lỗi test, nhờ đó bắt được cả những trường hợp không crash ngay. Các kiểm tra nhất quán nặng hơn nên tách thành lệnh riêng để đỡ làm chậm việc kiểm thử. Với kiểm thử ngẫu nhiên đơn giản, test harness chỉ cần chọn lệnh ngẫu nhiên cho đến khi có gì đó hỏng; sau đó khi chuyển sang harness cho fuzzer thì chỉ cần dùng luồng byte đầu vào được fuzz để chọn lệnh. Như vậy bạn sẽ tự động có được những thứ hay ho như kiểm thử hồi quy có tính quyết định và thu gọn test case
  Tôi chưa từng thu được kết quả gì đáng kể khi bảo libfuzzer giảm test case một cách tường minh, có lẽ vì nó đã làm việc đó trong lúc tạo đầu vào rồi. Vì thế tôi cũng chưa có động lực thử thêm các phép kiểm tra interestingness giúp fuzzer đa dụng thu gọn test case. Không biết người khác có ai thành công với cách đó chưa

  • Hoàn toàn đồng ý. Tôi dùng cách này khá thường xuyên. Tạo một biểu diễn ký hiệu cho giao diện có trạng thái, thường là viết một interpreter đơn giản dựa trên switch-case hoặc match, rồi sinh ngẫu nhiên danh sách thao tác để chạy, sau đó thu gọn đầu vào đã kích hoạt assert bắt lỗi vi phạm tiền điều kiện/hậu điều kiện hoặc hỏng hóc nội bộ
    Gọi là kiểm thử dựa trên thuộc tính, fuzzing hay model checking nhẹ cũng được, nó có thể hiệu quả đáng ngạc nhiên trong việc tìm ra các bug sâu. Tôi đã thấy rất nhiều giao diện có trạng thái mà từng thao tác riêng lẻ thì đúng, nhưng giả định giữa chúng lại lệch nhau một chút; khi các thao tác này kết hợp theo cách không ngờ tới thì lỗi sẽ leo thang thành hỏng hóc nội bộ
    Sẽ rất hữu ích nếu chạy song song danh sách thao tác đó với một cài đặt đơn giản dùng bảng băm hoặc danh sách trong bộ nhớ, rồi kiểm tra xem kết quả có khớp nhau không. Nếu có khác biệt thì thường либо là bug, либо là một trường hợp biên cần được tài liệu hóa tốt hơn
  • Thỉnh thoảng tôi xử lý tối ưu hóa vận tải, và thường gặp những kịch bản khá phức tạp làm vỡ bất biến. Có một bộ thu gọn test case thì sẽ tuyệt vời, nhưng trước đây đành chấp nhận tự thu gọn thủ công[0]
    Đáng tiếc là file dữ liệu quá phức tạp nên có lẽ shrinkray khó mà xử lý được. Nó đọc dữ liệu dạng bảng từ nhiều “file” khác nhau, lại còn có phụ thuộc xa, nên có lẽ phải tự mã hóa kiến thức miền vào phương pháp thu gọn
    Nhìn vào tốc độ phát triển của AI, có lẽ lần tới gặp kịch bản như vậy tôi sẽ viết một bộ thu gọn tùy chỉnh
    [0] Nếu lôi bản thể học mơ hồ vào đây thì bài toán tối ưu là bài toán tìm kiếm nhằm tối thiểu hóa chi phí, mà điều đó về bản chất cũng giống compiler, nên đây không hẳn là ví dụ hoàn hảo

• Tôi đã đọc ba lần để tìm cách áp dụng thứ này cho các bài test viết bằng pytest
  Tôi muốn giảm độ phức tạp của test suite, nên lúc không làm việc sẽ đọc lại lần thứ tư

  • Nếu dùng Python, bước đầu tiên là đưa vào Hypothesis, vì nó đã tích hợp sẵn khả năng thu gọn test case

• Năm ngoái khi xem vấn đề thứ tự chạy test trong CI, tôi đã làm một công cụ giúp thu gọn danh sách test
  Về cơ bản, nó chạy thử bằng cách cắt đôi các dòng dần dần
  Bản thân script có khá nhiều bug, nhưng việc một danh sách 5000 test được rút xuống còn khoảng 4 test gây ra bug đồng thời của tôi thì rất ấn tượng
  Tôi thực sự tò mò không biết trong trường hợp của mình Shrink Ray có “chạy phát ăn ngay” hay không. Tôi thật lòng nghĩ rằng “thu gọn tập dòng dựa trên test” nên là một tính năng thuộc bộ công cụ dòng lệnh tiêu chuẩn

• Liên quan đến chủ đề này, kiểm thử dựa trên thuộc tính cũng dùng một cách tiếp cận khá tương tự là “thu gọn” không gian trạng thái của đầu vào được tạo ra để tạo phản ví dụ cho test
  Ưu điểm của kiểm thử dựa trên thuộc tính là có thể dẫn hướng và cấu trúc hóa không gian tìm kiếm. Bạn có thể biến đầu vào thành một tập các chuyển trạng thái điều khiển một máy trạng thái mô hình hóa chương trình
  Tôi luôn ngạc nhiên khi thấy kỹ thuật này vẫn bị dùng quá ít, ngay cả ở những lĩnh vực rất hợp như cơ sở dữ liệu và hệ phân tán. Ngay tuần trước tôi cũng dựng được một bài test như vậy ở $WORK chỉ trong chưa đến vài giờ, và nhanh chóng phát hiện hệ thống của chúng tôi không hội tụ. Bài test in ra một trace gọn gàng mà chỉ cần đưa cho đồng nghiệp xem là họ hiểu ngay
  Cá nhân tôi thấy đây là kỹ thuật kiểm thử có hiệu quả trên công sức bỏ ra tốt nhất khi debug các hệ thống phức tạp