Tổng quan nghiên cứu

Trong kỷ nguyên số hóa, các hệ thống công nghệ thông tin và truyền thông giữ vai trò quyết định trong mọi hạ tầng trọng yếu. Theo các báo cáo thống kê ngành công nghệ, ước tính mỗi người tiếp xúc trung bình với khoảng 25 thiết bị kỹ thuật số mỗi ngày, và hơn 20% chi phí sản xuất các phương tiện hiện đại như máy bay, ô tô được dành riêng cho hệ thống xử lý thông tin. Tuy nhiên, sai sót phần mềm luôn tiềm ẩn nguy cơ gây thiệt hại thảm khốc. Điển hình trong lịch sử, sự cố lỗi dấu phẩy động của chip vi xử lý Intel Pentium đã gây thiệt hại 475 triệu USD, sự cố phần mềm điều khiển hành lý tại sân bay Denver gây tổn thất khoảng 1,1 triệu USD mỗi ngày làm chậm tiến độ 9 tháng, hay thảm họa y tế từ máy xạ trị Therac-25 trong giai đoạn năm 1985 đến năm 1987 đã khiến 6 bệnh nhân tử vong do phơi nhiễm bức xạ quá liều.

Nhằm loại bỏ triệt để các lỗi nguy hiểm mà không cần thực thi trực tiếp mã nguồn trong môi trường nhạy cảm, phương pháp kiểm tra hình thức, tiêu biểu là kiểm tra mô hình (Model Checking), đã trở thành chuẩn mực kiểm định quan trọng. Dẫu vậy, kiểm tra mô hình truyền thống luôn đối mặt với vấn nạn bùng nổ không gian trạng thái; đơn cử chỉ với hai biến số nguyên 16-bit thông thường, không gian kiểm tra đã có thể vượt mức 4 tỷ trạng thái khả dĩ. Nghiêm trọng hơn, các kỹ thuật kiểm định tự động hiện hành luôn đặt giả định bắt buộc là toàn bộ mã nguồn phải đầy đủ và khép kín. Trên thực tế phát triển phần mềm, giả định này hầu như không khả thi khi chương trình thường xuyên sử dụng các lời gọi hàm thư viện chuẩn, thư viện liên kết động của bên thứ ba hoặc các hàm thành phần chưa được phát triển hoàn thiện. Tình trạng thiếu vắng mã nguồn khiến bộ kiểm tra mô hình không thể xác định ngữ nghĩa hình thức, dẫn đến việc gián đoạn quy trình thẩm định an toàn.

Nhằm giải quyết triệt để rào cản kỹ thuật này, luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Lê Văn Tiến, dưới sự hướng dẫn khoa học của Tiến sĩ Quản Thành Thơ tại Trường Đại học Bách Khoa thuộc Đại học Quốc gia Thành phố Hồ Chí Minh (thực hiện trong giai đoạn từ tháng 07 năm 2011 đến tháng 07 năm 2012), đã đề xuất giải pháp kiểm tra mô hình dựa trên đặc tả hình thức cho các chương trình chưa hoàn chỉnh. Mục tiêu trọng tâm của nghiên cứu là xây dựng khung làm việc tự động chuyển đổi các chương trình chưa hoàn chỉnh thành các chương trình tự hoàn chỉnh có khả năng kiểm định được, kết hợp kỹ thuật kiểm thử concolic với ngôn ngữ đặc tả chuẩn ANSI/ISO C Specification Language. Ý nghĩa khoa học của đề tài không chỉ nằm ở việc giải quyết trọn vẹn bài toán kiểm tra tĩnh cho mã nguồn mở rộng mà còn thiết lập nền tảng chứng minh toán học vững chắc, giúp nâng tỷ lệ bao quát kiểm định lên mức tối đa mà vẫn kiểm soát chặt chẽ tài nguyên tính toán.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên sự giao thoa của ba nền tảng lý thuyết kiểm định hình thức và phương pháp tính toán tiên tiến:

Lý thuyết kiểm tra mô hình: Phương pháp này chuẩn hóa hệ thống phần mềm thành các mô hình toán học dựa trên cấu trúc Kripke (hệ thống chuyển trạng thái tự động không đơn định) và sử dụng logic thời gian (Temporal Logic) để duyệt vét cạn toàn bộ các không gian trạng thái nhằm kiểm tra thuộc tính an toàn.

Lý thuyết diễn dịch trừu tượng (Abstract Interpretation): Được đề xuất bởi Patrick Cousot, lý thuyết này cung cấp mô hình toán học chặt chẽ để xấp xỉ hóa ngữ nghĩa của chương trình thông qua cấu trúc dàn (Lattice), quan hệ thứ tự bán phần, lý thuyết điểm bất động (Fixpoint Semantics) và phép kết nối Galois. Nghiên cứu vận dụng cấu trúc này để chứng minh tính nhất quán giữa ngữ nghĩa của chương trình gốc và chương trình đã được xấp xỉ hóa.

Kỹ thuật kiểm thử Concolic (Concolic Testing): Sự kết hợp đột phá giữa thực thi dữ liệu cụ thể (Concrete Execution) và thực thi ký tự tượng trưng (Symbolic Execution). Concolic testing sử dụng bộ giải ràng buộc tự động (Automated Theorem Prover) để lần lượt đảo dấu các đường điều kiện, hỗ trợ sinh tập dữ liệu kiểm thử tối giản nhưng bao quát toàn bộ các nhánh rẽ thực thi của chương trình.

Ngôn ngữ đặc tả ACSL (ANSI/ISO C Specification Language): Ngôn ngữ đặc tả hình thức hướng hợp đồng (Design by Contract) dành cho mã nguồn C, cho phép biểu diễn các tiền điều kiện, hậu điều kiện, các điều kiện bất biến và phạm vi tác động của hàm/thủ tục khi không có mã nguồn cài đặt chi tiết.

Phương pháp nghiên cứu

Nghiên cứu áp dụng quy trình thực nghiệm kết hợp chứng minh giải tích toán học chặt chẽ trong suốt mốc thời gian 12 tháng (từ ngày 04/07/2011 đến ngày 02/07/2012).

Nguồn dữ liệu và phân loại mẫu: Bộ dữ liệu thực nghiệm gồm các bài tập lập trình ngôn ngữ C được thu thập trực tiếp từ hệ thống kiểm tra và chấm bài tự động PROVE của Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa Thành phố Hồ Chí Minh. Cỡ mẫu nghiên cứu bao gồm hàng chục bài toán lập trình đại diện được phân chia thành 4 nhóm cấu trúc mẫu điển hình: nhóm chương trình không sử dụng lời gọi hàm, nhóm chương trình có gọi hàm thư viện chuẩn, nhóm chương trình chứa các lời gọi thủ tục được đặc tả bằng ACSL, và nhóm chương trình hỗn hợp chứa cả hàm thư viện lẫn đặc tả ACSL.

Phương pháp chọn mẫu: Phương pháp chọn mẫu phi xác suất có chủ đích (Purposive Sampling) được áp dụng nhằm chọn lọc các cấu trúc giải thuật có độ phức tạp phân nhánh cao, các hàm chứa biểu thức toán học phi tuyến và các mẫu mã nguồn khuyết thiếu hàm thành phần nghiêm trọng nhằm thử thách tối đa năng lực của bộ sinh test-case và bộ kiểm định mô hình.

Quy trình và phương pháp phân tích: Quy trình thực nghiệm triển khai qua 4 bước khép kín:

  • Trích xuất tự động ngữ nghĩa hình thức và các ràng buộc logic từ tệp đặc tả ACSL của các hàm chưa hoàn thiện.
  • Phân tích đồ thị luồng điều khiển của chương trình chính, áp dụng Concolic testing để sinh bộ ca kiểm thử đủ điều kiện bao phủ tất cả các nhánh rẽ khả dĩ.
  • Áp dụng kỹ thuật biến đổi mã nguồn cục bộ (Code Transformation), thay thế các lời gọi hàm khuyết mã bằng kết quả thực thi cụ thể tương ứng với từng ca kiểm thử, tạo thành chương trình tự hoàn chỉnh.
  • Chuyển đổi chương trình tự hoàn chỉnh sang mô hình kiểm tra tương thích và thực thi kiểm tra mô hình tự động.

Lý do lựa chọn phương pháp: Việc phối hợp phân tích động thông qua Concolic testing và phân tích tĩnh qua Abstract Interpretation giải quyết triệt để hiện tượng bùng nổ không gian trạng thái, đồng thời đảm bảo mọi lỗi tiềm ẩn trong chương trình gốc đều được phát hiện một cách nhất quán trên mô hình trừu tượng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Nghiên cứu đã đạt được các kết quả mang tính đột phá trong việc tự động hóa kiểm định mã nguồn C chưa hoàn chỉnh:

Khắc phục triệt để hiện tượng bùng nổ trạng thái: Kỹ thuật Concolic testing kết hợp giải ràng buộc ACSL đã giảm không gian kiểm thử từ hơn 4 tỷ trạng thái lý thuyết đối với các biến dữ liệu xuống chỉ còn từ 2 đến 6 ca kiểm thử trọng yếu cho mỗi hàm rẽ nhánh phức tạp. Bộ sinh test-case tự động định hướng chính xác các đường điều kiện biên mà không cần duyệt vét cạn toàn bộ miền giá trị.

Chuyển đổi thành công 100% các dạng chương trình khuyết thiếu: Hệ thống đã chuyển đổi hoàn toàn tự động 3 nhóm chương trình chưa hoàn chỉnh điển hình (chứa lời gọi hàm thư viện, chứa thủ tục đặc tả ACSL, và chứa hàm trả về giá trị đặc tả ACSL) thành các chương trình tự hoàn chỉnh. Toàn bộ mã nguồn sau chuyển đổi đều tương thích hoàn toàn với các công cụ Model Checker hiện hành.

Đạt độ bao phủ kiểm định trên 90%: Kết quả kiểm tra thực nghiệm trên tập bài tập sinh viên cho thấy tỷ lệ thực thi thành công và độ bao phủ nhánh rẽ của các ca kiểm thử sinh ra đạt mức xấp xỉ 90% đến 95% trên các tập bài toán hỗn hợp, phát hiện chính xác các lỗi tiềm ẩn như chia cho 0, tràn mảng và sai logic so với bản đặc tả yêu cầu.

Đóng góp học thuật quốc tế: Các luận điểm khoa học của luận văn đã được bình duyệt và công bố tại 2 hội nghị khoa học quốc tế uy tín gồm Hội nghị quốc tế ACT-2011 tổ chức tại Jakarta, Indonesia và Hội nghị quốc tế IEEE RIVF 2012 tổ chức tại Thành phố Hồ Chí Minh.

Thảo luận kết quả

Cơ chế mang lại thành công của giải pháp đề xuất bắt nguồn từ việc thiết lập được một quan hệ xấp xỉ nhất quán trong không gian trừu tượng. Bằng các chứng minh toán học giải tích, tác giả đã khẳng định mô hình chương trình tự hoàn chỉnh thỏa mãn các tiêu chuẩn của một Consistent Abstract Interpretation. Điều này đồng nghĩa với việc không gian trạng thái của chương trình tự hoàn chỉnh bao hàm toàn bộ hành vi của chương trình gốc; mọi phản ví dụ (counterexample) hoặc trạng thái lỗi được phát hiện trên mô hình tự hoàn chỉnh đều phản ánh đúng bản chất lỗi trong mã nguồn ban đầu.

So với các công cụ kiểm thử tự động nổi tiếng thế giới như DART của Bell Labs, SYNERGY của Microsoft Research hay DASH, giải pháp trong luận văn thể hiện sự vượt trội rõ rệt khi đối mặt với các hàm chưa có mã nguồn cài đặt. Trong khi DART buộc phải dừng hoặc gán giá trị ngẫu nhiên kém chính xác khi gặp hàm ngoài, hệ thống đề xuất tận dụng triệt để hợp đồng logic từ ACSL để hướng dẫn bộ sinh ca kiểm thử đi sâu vào các nhánh điều kiện ẩn bên trong hàm.

Dữ liệu thực nghiệm của luận văn có thể được tổng hợp trực quan qua các bảng dữ liệu so sánh số lượng test-case tạo ra giữa các phương pháp và biểu đồ cột thể hiện độ bao phủ luồng thực thi qua 4 nhóm bài tập, minh chứng rõ nét cho việc giảm thiểu từ 70% đến 80% thời gian xử lý của bộ kiểm tra mô hình so với phương pháp vét cạn truyền thống.

Đề xuất và khuyến nghị

Nhằm phát huy tối đa giá trị thực tiễn của công trình nghiên cứu, 4 nhóm giải pháp chiến lược được đề xuất như sau:

Tích hợp toàn diện module vào hệ sinh thái kiểm định trực tuyến PROVE: Nhóm nghiên cứu SAVE cần tiến hành đóng gói giải pháp thành dịch vụ kiểm tra tự động hoàn chỉnh trong vòng 6 tháng tới, đặt mục tiêu xử lý tự động 100% các bài nộp lập trình của sinh viên mà không bị gián đoạn bởi các thư viện ngoài.

Mở rộng năng lực phân tích cú pháp đặc tả ACSL cho các kiểu dữ liệu phức tạp: Các nhà nghiên cứu phát triển công cụ cần tiếp tục cải tiến bộ parser trong thời gian 12 tháng, tập trung hỗ trợ phân tích cấu trúc con trỏ đa cấp, cấu trúc mảng động và các phép toán số thực dấu phẩy động phức tạp, hướng tới nâng cao độ bao quát ngữ nghĩa hình thức đạt mức 95%.

Chuẩn hóa quy trình đặc tả giao diện theo mô hình Design by Contract trong công nghiệp phần mềm: Các doanh nghiệp gia công và phát triển phần mềm nhúng, phần mềm điều khiển an toàn cao cần áp dụng ngôn ngữ đặc tả ACSL vào quy trình thiết kế giao diện hàm ngay từ giai đoạn đầu trong vòng 18 tháng tới, nhằm giảm thiểu khoảng 40% chi phí phát hiện và khắc phục lỗi ở giai đoạn tích hợp hệ thống.

Phát triển nền tảng học tập tương tác kết hợp mạng xã hội: Ban quản trị các cơ sở đào tạo đại học chuyên ngành công nghệ thông tin cần phối hợp triển khai mô hình học tập kết hợp mạng xã hội tích hợp cơ chế kiểm định mô hình tự động trong vòng 12 tháng, với mục tiêu nâng cao 35% mức độ tương tác và tính chủ động tự học lập trình đúng chuẩn của sinh viên.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu học thuật và kỹ thuật chuyên sâu mang lại giá trị thiết thực cho 4 nhóm đối tượng chính:

Giảng viên và nhà nghiên cứu chuyên ngành Khoa học máy tính: Cung cấp nguồn học liệu tham khảo xuất sắc về phương pháp kiểm tra hình thức, lý thuyết dàn trong Abstract Interpretation và kỹ thuật phân tích mã nguồn nâng cao để phục vụ giảng dạy và mở rộng các đề tài nghiên cứu cấp cao.

Kỹ sư kiểm thử phần mềm và kỹ sư phát triển hệ thống an toàn cao: Cung cấp giải pháp kỹ thuật cụ thể để ứng dụng kiểm định mã nguồn C trong các dự án phần mềm nhúng hàng không, viễn thông, thiết bị y tế và ô tô tự hành, nơi mã nguồn thường xuyên tích hợp thư viện đóng gói từ các nhà cung cấp thứ ba.

Học viên cao học và sinh viên ngành Công nghệ phần mềm: Giúp tiếp cận trực quan cách thức hiện thực hóa các lý thuyết toán học trừu tượng (như điểm bất động, kết nối Galois, logic thời gian) thành các công cụ phần mềm thực thi mạnh mẽ trong thực tế.

Nhà phát triển hệ thống giáo dục trực tuyến và chấm bài tự động: Cung cấp kiến trúc tham chiếu để xây dựng các máy chấm bài thông minh, có khả năng chỉ ra vị trí dòng lệnh chứa lỗi logic và tự động sinh phản ví dụ minh họa giúp người học sửa lỗi nhanh chóng.

Câu hỏi thường gặp

Chương trình chưa hoàn chỉnh là gì và tại sao việc kiểm tra chúng lại phức tạp? Chương trình chưa hoàn chỉnh là chương trình chứa các lời gọi hàm hoặc thủ tục bị khuyết thiếu mã nguồn cài đặt chi tiết (chỉ có khai báo nguyên mẫu hoặc hàm thư viện đóng gói). Các công cụ kiểm tra mô hình truyền thống bắt buộc phải duyệt toàn bộ cây thực thi mã nguồn, do đó khi thiếu mã nguồn hàm con, hệ thống kiểm định sẽ không thể suy diễn ngữ nghĩa và buộc phải dừng phân tích.

Kỹ thuật Concolic Testing giải quyết vấn đề bùng nổ trạng thái bằng cách nào? Thay vì phải duyệt qua toàn bộ miền giá trị khả dĩ lên đến hàng tỷ trạng thái, Concolic Testing kết hợp chạy thử mã nguồn với dữ liệu cụ thể và theo dõi đường đi tượng trưng bằng ký tự. Bằng cách phủ định điều kiện nhánh rẽ cuối cùng và nhờ bộ giải định lý tự động tìm nghiệm mới, kỹ thuật này chỉ sinh ra số lượng ca kiểm thử tối thiểu vừa đủ để đi qua toàn bộ các nhánh rẽ của chương trình.

Ngôn ngữ ACSL đóng vai trò gì trong giải pháp của luận văn? Ngôn ngữ ACSL đóng vai trò như một hợp đồng logic chính thức mô tả chính xác tiền điều kiện, hậu điều kiện và phạm vi biến đổi trạng thái của các hàm bị thiếu mã nguồn. Dựa vào bản đặc tả ACSL, hệ thống tự động trích xuất các ràng buộc logic để hướng dẫn bộ sinh ca kiểm thử và bộ biến đổi mã nguồn hoạt động chính xác.

Tại sao giải pháp chuyển đổi chương trình đảm bảo tính đúng đắn về mặt toán học? Tính đúng đắn được chứng minh dựa trên lý thuyết Diễn dịch trừu tượng (Abstract Interpretation). Tác giả đã chứng minh toán học rằng việc thay thế lời gọi hàm bằng các giá trị cụ thể trong ca kiểm thử tạo thành một phép trừu tượng hóa nhất quán (Consistent Abstract Interpretation), đảm bảo mọi lỗi tiềm ẩn trong chương trình gốc đều được bảo toàn và phát hiện đầy đủ trên chương trình tự hoàn chỉnh.

Kết quả của luận văn có thể áp dụng cho các ngôn ngữ lập trình khác ngoài C không? Hoàn toàn có thể mở rộng. Mặc dù luận văn hiện thực thực nghiệm trên ngôn ngữ C và đặc tả ACSL, khung phương pháp luận kết hợp giữa Concolic Testing, Abstract Interpretation và Design by Contract hoàn toàn có thể áp dụng tương tự cho các ngôn ngữ khác như Java (với ngôn ngữ đặc tả JML) hoặc C# (với Code Contracts).

Kết luận

Luận văn thạc sĩ của tác giả Lê Văn Tiến đã giải quyết thành công một trong những thách thức lớn nhất của lĩnh vực kiểm định hình thức phần mềm hiện đại với các dấu ấn nổi bật:

  • Đề xuất khung phương pháp luận đột phá cho phép kiểm tra mô hình các chương trình C chưa hoàn chỉnh thông qua đặc tả hình thức ACSL.
  • Tự động hóa hoàn toàn quy trình chuyển đổi mã nguồn khuyết thiếu thành chương trình tự hoàn chỉnh sẵn sàng cho việc kiểm định mô hình.
  • Ứng dụng xuất sắc kỹ thuật Concolic Testing giúp triệt tiêu hiện tượng bùng nổ trạng thái, tối ưu hóa từ hàng tỷ trạng thái xuống một số lượng hữu hạn các ca kiểm thử trọng yếu.
  • Thiết lập chứng minh toán học vững chắc khẳng định giải pháp đạt tiêu chuẩn Diễn dịch trừu tượng nhất quán (Consistent Abstract Interpretation).
  • Đóng góp 2 công bố khoa học quốc tế tại các hội nghị chuyên ngành uy tín và ứng dụng thành công vào hệ thống chấm bài tự động thực tế.

Trong lộ trình phát triển 12 đến 24 tháng tới, hướng nghiên cứu sẽ tiếp tục được mở rộng để phân tích các hệ thống phần mềm đa luồng, xử lý triệt để các cấu trúc dữ liệu con trỏ phức tạp và số thực dấu phẩy động. Các nhà nghiên cứu, kỹ sư phần mềm và các tổ chức công nghệ được khuyến khích tiếp cận, khai thác và tích hợp khung giải pháp này nhằm nâng cao tối đa độ tin cậy và chất lượng cho các hệ sinh thái phần mềm trọng yếu.