Sự cố malloc làm hỏng JPGLoader của Serenity, hay: bí quyết trúng xổ số (2021)

 (sin-ack.github.io)
1 điểm bởi GN⁺ 2024-07-08 | 1 bình luận | Chia sẻ qua WhatsApp
  • Lỗi màu JPG trong SerenityOS trông giống vấn đề thứ tự đối số RGB/BGR, nhưng thực ra bắt nguồn từ việc JPGLoader giao các thành phần cần có thứ tự cho thứ tự lặp của HashTable
  • Việc đưa malloc_good_size() vào AK+LibC khiến Vector và HashTable tận dụng kích thước chunk malloc thực tế, dẫn đến số bucket của HashTable thay đổi và làm lộ một lỗi ẩn
  • Mã cũ tình cờ đọc các thành phần Y, Cb, Cr của JPG theo đúng thứ tự; nhờ kết quả int_hash và số bucket khớp một cách may mắn, lỗi xử lý luồng Huffman đã bị che giấu
  • Quá trình truy nguyên bắt đầu trong bối cảnh JPGLoader.cpp gần đây không thay đổi; khi bisect 1000 commit, do các thay đổi AK, phải nhiều lần rebuild toàn bộ hệ điều hành với quy mô khoảng 3400 file
  • Bản sửa cuối cùng là làm cho việc duyệt các thành phần diễn ra theo thứ tự xác định; cách chữa tạm chỉ đổi thứ tự đối số màu có thể tạo lại cùng vấn đề khi thứ tự thay đổi lần sau

Lỗi màu JPG trông như nhầm lẫn RGB/BGR

  • Khi mở ảnh JPG trong SerenityOS, màu sắc hiển thị sai
  • Nếu đổi thứ tự đối số của constructor Color trong JPGLoader.cpp, ảnh trông như trở lại bình thường
    • Mã cũ: truyền theo thứ tự Y, Cb, Cr
    • Thay đổi tạm thời: truyền theo thứ tự Cr, Cb, Y
  • Tuy nhiên, thay đổi không phải revert gần nhất của JPGLoader.cpp theo Git đã từ hơn một tháng trước, và còn nhớ rằng 1–2 tuần trước ảnh nền JPG vẫn hiển thị bình thường
  • Vì vậy khả năng cao đây không phải là lỗi thứ tự kênh màu đơn giản, mà là một thay đổi khác đã làm lộ lỗi vốn có

Bisect trở nên khó khăn do thay đổi AK

  • SerenityOS dùng thư viện chuẩn riêng có tên AK(Agnostic Kit)
    • AK đóng vai trò tương tự C++ STL, nhưng được thay đổi cùng mã hệ điều hành trong cùng repository
  • Khi AK thay đổi, phạm vi ảnh hưởng rất rộng
    • Thư viện chuẩn được hầu như mọi mã nguồn include
    • Vì định nghĩa template C++ phải nằm trong header, thay đổi header AK gây ra việc biên dịch lại trên diện rộng
  • Mỗi khi đi qua một commit có thay đổi AK, phải build lại toàn bộ hệ điều hành
    • Tại thời điểm viết bài, khoảng 3400 file
    • Trong lúc bisect phạm vi 1000 commit, đã thực hiện build toàn bộ 4–5 lần trên laptop Sandy Bridge Mobile đời 2011
  • ccache cũng không xử lý được trường hợp này, và do tốc độ thay đổi nhanh của dự án SerenityOS, AK thay đổi khoảng mỗi 100 commit một lần

Vấn đề ẩn bị malloc_good_size() làm lộ ra

  • Sau khi bisect 1000 commit, thay đổi làm hỏng màu JPG được tìm thấy không phải ở JPGLoader, mà ở phía AK+LibC
  • Commit làm lộ vấn đề là f89e8fb71a4893911ee5125f34bd5bbb99327d33
    • Tiêu đề: AK+LibC: Implement malloc_good_size() and use it for Vector/HashTable
    • Thời điểm viết: 15/05/2021
  • Commit này triển khai API malloc_good_size() của macOS
    • Trả về kích thước cấp phát thực tế cho kích thước cấp phát được yêu cầu
    • Ví dụ, nếu yêu cầu 35 byte nhưng nội bộ dùng chunk 64 byte, thì có thể tận dụng 29 byte còn dư
  • Sau thay đổi này, Vector, HashTable và các cấu trúc khác tận dụng nhiều hơn phần bộ nhớ khả dụng bên trong chunk malloc
  • Vì ở commit ngay trước đó ảnh JPG hiển thị bình thường, phạm vi được thu hẹp thành: thay đổi này đã làm lộ một vấn đề ẩn có sẵn

Quá trình giải mã đang dựa vào dung lượng HashTable

  • Ban đầu, nghi ngờ khả năng JPGLoader hoặc mã cấp cao hơn đang phụ thuộc sai vào dung lượng của Vector và ghi trực tiếp
  • Thay đổi liên quan có ở cả HashTable lẫn Vector, và cả hai đều được dùng trong mã JPGLoader
  • Khi thử ngẫu nhiên xóa dòng áp dụng kmalloc_good_size() ở phía HashTable rồi build lại, vấn đề biến mất
    • Đoạn mã bị xóa là phần điều chỉnh dung lượng bucket mới theo kích thước cấp phát thực tế
  • Kết quả này xác nhận rằng sự thay đổi số bucket của HashTable ảnh hưởng tới kết quả giải mã JPG
  • HashTable không phải container dùng như một luồng dữ liệu liên tục, nên về cấu trúc không được phụ thuộc vào dung lượng hay thứ tự lặp của nó

Cách các thành phần JPG được xử lý

  • JPGLoader cũ đọc thông tin thành phần trong đoạn Start of Frame của file JPG và lưu vào struct Component
  • Mỗi Component có serial_id biểu thị vị trí trong file JPG
    • Thứ tự thành phần JPG thông thường phải là Y, Cb, Cr
  • Các thành phần này được lưu trong HashTable
    • Sau đó được dùng để so với thứ tự thành phần trong đoạn Start of Scan nhằm kiểm tra xem có đúng thứ tự dự kiến không
  • Ở bước giải mã, mã duyệt qua các thành phần này và dùng thông tin cần thiết cho biến đổi macroblock
  • Vấn đề nằm ở việc đưa các thành phần có yêu cầu về thứ tự vào HashTable rồi duyệt bằng iterator mặc định

Khác biệt về thứ tự duyệt giữa commit lỗi và commit bình thường

  • Ở commit cho màu bị lỗi, log debug cho thấy các thành phần được duyệt theo thứ tự sau
    • 0
    • 2
    • 1
  • Ở commit bình thường ngay trước đó, thứ tự khác
    • 0
    • 1
    • 2
  • Khác biệt này liên quan đến kết quả trông như đảo kênh màu
  • Trong lúc thử đổi thủ công thứ tự thành phần cùng với CxByte, lỗi sau xuất hiện
    • Huffman stream exhausted. This could be an error!
    • Failed to build Macroblock 3277
  • Lỗi này cho thấy việc giải mã JPG nhạy với thứ tự luồng, và xác nhận thứ tự duyệt thành phần là nguyên nhân cốt lõi

Thứ tự HashTable tình cờ khớp

  • Nguyên nhân gốc là lưu các đối tượng cần có thứ tự vào HashTable rồi duyệt bằng iterator mặc định
  • Hash của ID thành phần JPG đi qua int_hash và được dùng để chọn bucket
  • Trước đó, hai sự tình cờ đã đồng thời khớp với nhau
    • Kết quả int_hash cho các giá trị 0, 1, 2 ổn định
    • Số bucket của AK::HashTable vừa đủ để các thành phần được đặt theo đúng thứ tự
  • Nhờ sự tình cờ này, JPGLoader đã đọc luồng Huffman cho từng thành phần theo đúng thứ tự, và lỗi bị che giấu ngay từ đầu
  • Khi việc đưa malloc_good_size() vào làm thay đổi số bucket của HashTable, thứ tự thành phần đổi theo, và ảnh xuất hiện với kênh đỏ và xanh dương bị hoán đổi

Bản sửa cuối cùng bằng cách duyệt xác định

  • Sau khoảng 10 giờ debug, commit sửa lỗi được tạo
  • Commit sửa lỗi là a10ad24c760bfe713f1493e49dff7da16d14bf39
    • Tiêu đề: LibGfx: Make JPGLoader iterate components deterministically
    • Thời điểm viết: 31/05/2021
  • Điểm cốt lõi của bản sửa là làm cho JPGLoader duyệt các thành phần theo thứ tự xác định
  • Cách chỉ đổi thứ tự đối số Color lúc đó cũng khiến ảnh trông như bình thường, nhưng nếu sau này thứ tự duyệt lại thay đổi do một thay đổi khác, nó vẫn có thể hỏng tiếp
  • Đây là một ví dụ trong đó vấn đề trông như lỗi hiển thị nhỏ lại lộ ra do sự kết hợp giữa phụ thuộc sai vào thứ tự duyệt container và thay đổi kích thước cấp phát

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-08
Ý kiến trên Hacker News

  • Đây là một trong những lý do khiến nhiều triển khai bảng băm đưa yếu tố ngẫu nhiên vào thuật toán
    Vì thứ tự phần tử thay đổi mỗi lần chạy, nếu vô tình phụ thuộc vào thứ tự thì vấn đề sẽ nhanh chóng lộ ra
    Nếu thuật toán băm cố định, có thể tạo các khóa dồn vào cùng một bucket để lợi dụng cho tấn công từ chối dịch vụ, và cách này cũng ngăn được khá tốt các vấn đề bảo mật như vậy

    • Ngày nay, ngược lại cũng có nhiều triển khai bảo đảm bảng băm luôn duyệt theo thứ tự chèn
      Tôi thích hướng này hơn, vì không phải lần nào cũng quyết định xem mình cần map có thứ tự hay map không có thứ tự
      Không ít lần tôi tưởng chỉ cần map không có thứ tự là đủ, rồi hóa ra sai vì những lý do tinh vi
    • Nếu yếu tố ngẫu nhiên là một seed có thể chỉ định, lưu lại, ghi log và tái hiện được thì ổn
      Nếu không, đó thật sự là một ý tưởng tệ, vì nó khiến việc debug các vấn đề khác khó hơn nhiều
      Tính ngẫu nhiên không phải bạn bè, mà là kẻ thù
      Khoảng 20 năm trước, từng có cách tấn công các web server Java bằng cách thao túng tham số URL để tất cả rơi vào cùng một bucket, gây ra một đợt tấn công từ chối dịch vụ lớn
      Nếu tôi nhớ đúng thì các web server PHP cũng gặp đúng vấn đề bảo mật đó
      Vấn đề được sửa bằng cách thêm seed vào bảng băm, và seed đó dĩ nhiên là thứ lập trình viên có thể kiểm soát. Vì tính ngẫu nhiên không phải bạn bè, mà là kẻ thù

  • Đây có vẻ là một trường hợp mà nếu debug thêm một chút thay vì mù quáng làm bisect kiểu tìm kiếm nhị phân thì đã tiết kiệm được thời gian
    Dù sao cuối cùng cũng vẫn phải thêm log in ra thứ tự các component

  • Debug cũng hay, nhưng commit message cũng xuất sắc
    Nó nén rất gọn nguyên nhân và nội dung sửa trong vài đoạn văn

  • Nếu chờ đủ lâu, C++ cũng sẽ có tính năng tương đương malloc_good_size
    https://github.com/cplusplus/papers/issues/18

  • Tiêu đề cần có [2021]

  • Đây không phải lỗi của Gunnar. Vấn đề nằm ở phía đã lưu dữ liệu có thứ tự vào một file băm
    Làm việc này suốt vài chục năm, tôi đã nhiều lần gặp tình huống bố trí bộ nhớ thay đổi làm lộ ra các bug ẩn
    Mỗi lần như vậy mất từ vài giờ đến vài ngày để debug
    Nếu lập trình không khó thì đã chẳng cần đến chúng ta. Chỉ là tôi không biết câu này còn trụ được bao lâu nữa trong thời đại mô hình ngôn ngữ lớn

    • Đúng vậy. Kể cả nếu đó là lỗi của Gunnar, có lẽ cũng không cần ghi hẳn vào commit message
      Gunnar đã cải thiện một thứ, và trong quá trình đó chỉ làm lộ ra vấn đề của đoạn code cũ vốn đã hỏng
      Vậy mà phần thưởng cho nỗ lực ấy lại là câu kiểu “Gunnar, I like you, but please don't make me go through this again. :^)”
    • Chừng nào mô hình ngôn ngữ lớn còn được huấn luyện bằng code có bug, chúng sẽ còn đề xuất code có bug
    • Đúng. Và trái với tiêu đề, đây cũng không phải lỗi của malloc()

  • Tôi hiểu là SerenityOS có tài nguyên test hoặc những người giúp nhau về PC

  • Việc build SerenityOS từ đầu 4–5 lần trên laptop Sandy Bridge Mobile đời 2011 cũng giống như cố phát triển Windows Vista trên một máy tính ra đời vào giai đoạn giữa Windows 3.1 và Windows 95

    • Xét theo khoảng cách thời gian thì đúng, nhưng xét theo hiệu năng thực tế thì khác
      CPU sau năm 2011 tương đối không thay đổi lớn đến vậy, còn từ Windows 3.1 đến Vista thì x64 đã phổ biến và CPU đa lõi đã trở thành thông dụng
    • So sánh hay đấy. CPU của lập trình viên đó khoảng 13 năm tuổi
      Vista được phát hành quốc tế vào đầu năm 2007, nên nếu tính CPU 13 năm tuổi tại thời điểm phát hành thì là CPU năm 1994, khoảng một năm sau khi Pentium đời đầu xuất hiện
      Khi đó vẫn còn nhiều người dùng chiếc 486 DX2-66 đáng tin cậy
      Việc một CPU 13 năm trước ngày nay vẫn có thể dùng cho một dự án hiện đại là khá ấn tượng. Hồi đó khó mà nói điều tương tự
      Hy vọng các CPU ra mắt hôm nay cũng vẫn dùng thỏa mãn được đến sau năm 2037
    • Suốt năm qua tôi dùng Lenovo i5 đời 2011 làm máy desktop chính, chạy Windows 11 với hai màn hình
      Visual Studio chạy tốt, Photoshop cũng vậy, chỉ có các công cụ AI trong hệ thống hơi ì một chút
      Có lẽ tôi đang mở khoảng 200 tab Chrome, cùng với Slack, WhatsApp và 3 trình duyệt để test
      CapCut thì tôi ước nhanh hơn một chút khi dựng 4K, nhưng vẫn đủ gánh các dự án 2K phức tạp
      Chỉ đến các dự án After Effects phức tạp thì mới hơi chạm giới hạn. Nó không thích mấy cái đó
      Tôi nên nâng cấp, nhưng với một hệ thống gần như nhặt ra từ thùng rác thì như vậy là khá ổn

  • Thấy “Alien Lenna” thì tôi có cảm giác déjà vu, và đúng là một bài tôi từng xem, thậm chí còn bình luận rồi
    https://news.ycombinator.com/item?id=27374942 (2021)