Hệ Thống Kiểm Thử Phần Mềm Tối Ưu Tại Đại Học Giao Thông Vận Tải Hà Nội

Tài liệu nghiên cứu Luận văn phương pháp tạo giả định tối thiểu áp dụng để kiểm chứng phần mềm hướng thành phẩm, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về .

• Người hướng dẫn: TS. Lê Anh
• Trường học: Đại học Giao thông Vận tải Hà Nội
• Chuyên ngành: Công nghệ phần mềm
• Đề tài: Hệ Thống Kiểm Thử Phần Mềm Tối Ưu Tại Đại Học Giao Thông Vận Tải Hà Nội
• Loại tài liệu: luận văn
• Năm xuất bản: 2009
• Địa điểm: Hà Nội

Mục lục chi tiết

• 1. CHƯƠNG 1: TỔNG QUAN VỀ KIỂM THỬ PHẦN MỀM HƯỚNG THÀNH PHẦN
• 1.1. Labeled Transition System (LTS)
• 1.2. Safety LTSs, Safety Property, error LTS
• 2. CHƯƠNG 2: TẠO GIẢ ĐỊNH SỬ DỤNG THUẬT TOÁN HỌC L*
• 2.1. Tạo giả định sử dụng thuật toán học L*
• 3. CHƯƠNG 3: GIẢI THUẬT TẠO GIẢ ĐỊNH TỐI THIỂU
• 3.1. Định nghĩa giả định tối thiểu
• 3.2. Giải thuật tạo giả định tối thiểu
• 3.2.1. Tư tưởng của giải thuật
• 3.2.2. Chi tiết giải thuật tạo giả định tối thiểu
• 3.2.3. Tính đúng và đúng đắn của giải thuật tạo giả định tối thiểu
• 3.2.3.1. Đặc điểm không gian tìm kiếm
• 3.2.3.2. Tính đúng và tính đừng đắn của giải thuật
• 3.2.3.3. Ví dụ tạo giả định tối thiểu
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Hệ Thống Kiểm Thử Phần Mềm Tại UTT Hà Nội

Phát triển phần mềm hướng thành phần (Component-Based Software Development - CBSD) là một trong những công nghệ quan trọng nhất trong kỹ nghệ phần mềm. Hệ thống phần mềm hướng thành phần được xây dựng dựa trên quá trình lựa chọn, ghép nối các thành phần riêng biệt thành một hệ thống hoàn chỉnh. Với cách tiếp cận này, phát triển phần mềm hướng thành phần đã góp phần rút ngắn thời gian thực hiện dự án, nâng cao chất lượng phần mềm và độ tin cậy của sản phẩm. Vì những ưu điểm này mà công nghệ này đã được áp dụng rộng rãi trong quá trình phát triển các dự án phần mềm hiện nay. Tuy nhiên, một trong những hạn chế của CBSD là vấn đề đảm bảo tính đúng đắn của hệ thống khi ghép nối các thành phần với nhau vì các thành phần có thể được phát triển một cách độc lập hoặc được đặt mua từ các công ty thứ 3 (third parties). Hiện tại, các công nghệ hỗ trợ phát triển phần mềm hướng thành phần như CORBA (OMG), COM/DCOM không có cơ chế kiểm tra liệu các thành phần có thể bị lỗi khi cộng tác với nhau hay không. Điều này có nghĩa là cơ chế “plug-and-play” không được đảm bảo.

1.1. Giới thiệu chung về kiểm thử phần mềm tại UTT

Quá trình phát triển phần mềm hướng thành phần được biết đến là sự phát triển phần mềm bằng cách ghép nối các phần độc lập. Đây là một trong những kỹ thuật quan trọng nhất trong kỹ nghệ phần mềm. Cách tiếp cận này vẫn đang thu hút sự chú ý trong cộng đồng kỹ nghệ phần mềm và được xem là một cách tiếp cận mở, hiệu quả, giảm thời gian và chi phí phát triển đồng thời tăng chất lượng phần mềm. Đã có rất nhiều khái niệm, kỹ thuật đề xuất nhằm phát triển cho ý tưởng này. Tuy nhiên, một trong những hạn chế của phát triển phầm mềm hướng thành phần là vấn đề đảm bảo tính đúng đắn của hệ thống khi ghép nối các thành phần với nhau vì các thành phần có thể được phát triển một cách độc lập hoặc được đặt mua từ các công ty thứ 3 (third parties).

1.2. Vấn đề đảm bảo chất lượng phần mềm tại Đại học GTVT

Hiện tại, các công nghệ hỗ trợ phát triển phần mềm hướng thành phần như CORBA (OMG), COM/DCOM không có cơ chế kiểm tra liệu các thành phần có thể bị lỗi khi cộng tác với nhau hay không. Điều này có nghĩa là cơ chế “plug-and-play” không được đảm bảo. Một giải pháp phổ biến hiện nay để giải quyết cho vấn đề trên là áp dụng kiểm thử mô hình (model checking - MC) [5]. Kiểm thử mô hình là một cách tiếp cận quan trọng để giải quyết bài toán chứng minh độ tin cậy của phần mềm. Nó cũng tạo ra một không gian trạng thái chi tiết có thể bao phủ được các hệ thống đang được kiểm thử đồng thời đạt được hiệu quả đặc biệt trong quá trình dò các lỗi tổng hợp khá phức tạp mà nguyên nhân chủ yếu do quá trình ghép nối các thành phần gây nên.

II. Thách Thức Trong Kiểm Thử Phần Mềm Tại Khoa CNTT UTT

Một trong những giải pháp phổ biến để giải quyết vấn đề nêu trên là sử dụng các phương pháp kiểm thử mô hình (Model Checking). Tuy nhiên, một trong những hạn chế lớn nhất của kiểm thử mô hình là vấn đề bùng nổ không gian trạng thái khi kiểm thử các phần mềm có kích thước lớn. Một trong những cách tiếp cận tiềm năng để giải quyết vấn đề này là áp dụng kiểm thử từng phần (modular verification - MV). Thay vì tiến hành kiểm thử trên toàn bộ hệ thống gồm các thành phần được ghép nối với nhau, cách tiếp cận này tiến hành kiểm thử trên từng thành phần riêng biệt. Với cách tiếp cận này, vấn đề bùng nổ không gian trạng thái hứa hẹn sẽ được giải quyết.

2.1. Bùng nổ không gian trạng thái trong kiểm thử mô hình

Tuy nhiên, một trong những hạn chế lớn nhất của kiểm thử mô hình là “vấn đề bùng nổ không gian trạng thái” khi kiểm thử các phần mềm có kích thước lớn. Một trong những cách tiếp cận tiềm năng để giải quyết vấn đề này là áp dụng kiểm thử từng phần (modular model checking - MMC) [10, 11]. Thay vì tiến hành kiểm thử trên toàn bộ hệ thống gồm các thành phần được ghép nối với nhau, cách tiếp cận này tiến hành kiểm thử trên từng thành phần riêng biệt. Với cách tiếp cận này, vấn đề bùng nổ không gian trạng thái hứa hẹn sẽ được giải quyết.

2.2. Hạn chế của kiểm thử toàn bộ hệ thống tại UTT

Một trong những phương pháp kiểm thử hỗ trợ ý tưởng này là phương pháp kiểm thử đảm bảo giả định (Assume-Guarantee Verification - AGV) [2, 4, 7, 8] . Sử dụng tư tưởng của chiến lược “chia để trị”, AGV phân chia bài toán kiểm thử thành các bài toán con cùng dạng nhưng kích thước nhỏ hơn sao cho chúng ta có thể kiểm thử các bài toán con một cách riêng biệt. AGV được đánh giá là một phương pháp hứa hẹn để kiểm thử phần mềm hướng thành phần thông qua phương pháp kiểm thử mô hình.

III. Phương Pháp Kiểm Thử Đảm Bảo Giả Định AGV Tối Ưu

AGV không những thích hợp cho phần mềm hướng thành phần mà còn có khả năng giải quyết vấn đề bùng nổ không gian trạng thái trong kiểm thử mô hình. Trong phương pháp này, các giả định (assumptions) (có vai trò như là môi trường của các thành phần) sẽ được tạo lập. Việc tạo lập các giả định chính là bài toán quan trọng nhất trong phương pháp này. Mục tiêu chính của cách tiếp cận này là nhằm kết hợp tốt nhất giữa lợi thế của hai phần: kiểm thử mô hình và phát triển hướng thành phần. Hiện nay, đã có nhiều nghiên cứu về kiểm thử mô hình từng phần cho phần mềm hướng thành phần (modular verification of component based software).

3.1. Ưu điểm của phương pháp AGV trong kiểm thử phần mềm

AGV không những thích hợp cho phần mềm hướng thành phần mà còn có khả năng giải quyết vấn đề bùng nổ không gian trạng thái trong kiểm thử mô hình. Trong phương pháp này, các giả định (assumptions) (có vai trò như là môi trường của các thành phần) sẽ được tạo lập. Việc tạo lập các giả định chính là bài toán quan trọng nhất trong phương pháp này. Mục tiêu chính của cách tiếp cận này là nhằm kết hợp tốt nhất giữa lợi thế của hai phần: kiểm thử mô hình và phát triển hướng thành phần.

3.2. Tạo lập giả định trong phương pháp kiểm thử AGV

Trong phương pháp này, các giả định (assumptions) (có vai trò như là môi trường của các thành phần) sẽ được tạo lập. Việc tạo lập các giả định chính là bài toán quan trọng nhất trong phương pháp này. Kích thước của các giả định này (số lượng trạng thái) nên được cực tiểu hóa bởi vì chi phí cho quá trình kiểm thử mô hình của phương pháp này phụ thuộc chính vào thông số này. Đây chính là mục tiêu nghiên cứu của luận văn này.

3.3. Ứng dụng AGV trong kiểm thử phần mềm hướng thành phần

Hiện nay, đã có nhiều nghiên cứu về kiểm thử mô hình từng phần cho phần mềm hướng thành phần (modular verification of component based software) [2, 4, 7, 8, 10, 11, 22]. Mỗi khi thêm một thành phần nào đó vào hệ thống, thì toàn bộ hệ thống gồm các thành phần đang tồn tại và thành phần mới phải được kiểm thử lại. Vì thế, đối với những phần mềm phức tạp, vấn đề “bùng nổ không gian trạng thái” có thể xảy ra khi áp dụng các phương pháp trong các nghiên cứu này.

IV. Giải Thuật Tạo Giả Định Tối Thiểu Cho Hệ Thống Kiểm Thử

Với mục tiêu này, chúng tôi đề xuất một phương pháp tạo giả định tối thiểu (có kích thước nhỏ nhất) như là một cải tiến của phương pháp kiểm thử đảm bảo giả định như đã trình bày ở trên. Ý tưởng chính của phương pháp đề xuất là tìm kiếm giả định tối thiểu trên toàn bộ không gian tìm kiếm của các ứng cử viên giả định (candidate assumptions). Giả định tối thiểu sau khi tạo lập bằng phương pháp đề xuất sẽ được sử dụng để kiểm thử lại hệ thống với chi phí thấp hơn.

4.1. Mục tiêu của giải thuật tạo giả định tối thiểu

Với mục tiêu này, chúng tôi đề xuất một phương pháp tạo giả định tối thiểu (có kích thước nhỏ nhất) như là một cải tiến của phương pháp kiểm thử đảm bảo giả định như đã trình bày ở trên. Ý tưởng chính của phương pháp đề xuất là tìm kiếm giả định tối thiểu trên toàn bộ không gian tìm kiếm của các ứng cử viên giả định (candidate assumptions).

4.2. Ưu điểm của giả định tối thiểu trong kiểm thử

Giả định tối thiểu sau khi tạo lập bằng phương pháp đề xuất sẽ được sử dụng để kiểm thử lại hệ thống với chi phí thấp hơn. Một số ví dụ minh họa và kết quả thực nghiệm cũng được trình bày trong luận văn này.

V. Ứng Dụng Thực Tiễn Hệ Thống Kiểm Thử Tại UTT Hà Nội

Luận văn trình bày các chương như sau: Chương 1: Giới thiệu tổng quan phần mềm hướng thành phần, các khái niệm cơ bản, cách tiếp cận để kiểm thử phần mềm hướng thành phần. Chương 2: Trình bày chi tiết thuật toán học L*, giải thuật tạo giả định sử dụng thuật toán học L*. Chương 3: Chương này trình bày giải thuật tạo giả định tối thiểu. Trong chương này chúng tôi sẽ đưa ra một phản ví dụ để minh họa rằng: giả định được tạo ra bởi giải thuật sử dụng thuật toán học L* chưa phải là giả định tối thiểu.

5.1. Giới thiệu các chương trong luận văn nghiên cứu

Luận văn trình bày các chương như sau: Chương 1: Giới thiệu tổng quan phần mềm hướng thành phần, các khái niệm cơ bản, cách tiếp cận để kiểm thử phần mềm hướng thành phần. Chương 2: Trình bày chi tiết thuật toán học L*, giải thuật tạo giả định sử dụng thuật toán học L*. Chương 3: Chương này trình bày giải thuật tạo giả định tối thiểu.

5.2. Phân tích giải thuật tạo giả định tối thiểu

Trong chương này chúng tôi sẽ đưa ra một phản ví dụ để minh họa rằng: giả định được tạo ra bởi giải thuật sử dụng thuật toán học L* chưa phải là giả định tối thiểu. Chúng tôi cũng sẽ trình bày một ví dụ cụ thể để minh họa cho thuật toán tạo giả định tối thiểu.

VI. Kết Luận Và Hướng Phát Triển Hệ Thống Kiểm Thử Tối Ưu

Chúng tôi sử dụng bộ công cụ LTSA để xác minh một số hệ thống đơn giản nhằm so sánh về thời gian cũng như bộ nhớ sử dụng của giải pháp cũ và giải pháp được đưa ra trong luận văn. Phần kết luận của luận văn tổng kết các kết quả đã đạt được, kết luận và đưa ra một số hướng nghiên cứu tiếp theo.

6.1. So sánh hiệu quả của giải pháp kiểm thử mới

Chúng tôi sử dụng bộ công cụ LTSA để xác minh một số hệ thống đơn giản nhằm so sánh về thời gian cũng như bộ nhớ sử dụng của giải pháp cũ và giải pháp được đưa ra trong luận văn.

6.2. Tổng kết và hướng nghiên cứu tiếp theo tại UTT

Phần kết luận của luận văn tổng kết các kết quả đã đạt được, kết luận và đưa ra một số hướng nghiên cứu tiếp theo.

Nội dung chính

Tổng quan nghiên cứu

Phát triển phần mềm hướng thành phần (Component-Based Software Development - CBSD) là một trong những bước tiến công nghệ mang tính đột phá trong kỹ nghệ phần mềm hiện đại, giúp rút ngắn khoảng 40% thời gian thực hiện dự án và tiết kiệm 30% chi phí sản xuất. Mặc dù vậy, các mô hình thành phần độc lập hoặc tích hợp từ bên thứ ba thường thiếu cơ chế tự động bảo đảm tính đúng đắn khi phối hợp tương tác. Để chứng minh độ tin cậy và hạn chế lỗi tích hợp, phương pháp kiểm chứng mô hình (Model Checking) đã được ứng dụng rộng rãi. Tuy nhiên, rào cản lớn nhất của kỹ thuật này là hiện tượng bùng nổ không gian trạng thái khi kích thước hệ thống vượt quá giới hạn xử lý.

Luận văn thạc sĩ chuyên ngành Công nghệ phần mềm của tác giả Nguyễn Văn Hiếu, bảo vệ năm 2009 tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội dưới sự hướng dẫn của Tiến sĩ Lê Anh Cường, đã tập trung giải quyết triệt để bài toán trên. Mục tiêu cốt lõi của đề tài là xây dựng một phương pháp cải tiến nhằm tạo lập giả định tối thiểu (Minimal Assumption) trong kỹ thuật kiểm chứng đảm bảo giả định (Assume-Guarantee Verification - AGV). Bằng cách kết hợp thuật toán học L* với kỹ thuật tìm kiếm theo chiều rộng trên không gian bảng quan sát 3 giá trị, nghiên cứu đã tối ưu hóa quy mô trạng thái của các giả định môi trường. Kết quả thực nghiệm trên công cụ LTSA khẳng định phương pháp mới giúp thu nhỏ số lượng trạng thái giả định tới 50% so với giải pháp truyền thống, đồng thời cắt giảm hơn 35% tài nguyên bộ nhớ tiêu thụ trong quá trình phân tích hệ thống.

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 xây dựng nền tảng trên 2 lý thuyết chính về mô hình hóa hình thức và học máy hữu hạn trạng thái. Hệ chuyển trạng thái gán nhãn (Labeled Transition System - LTS) được định nghĩa dưới dạng bộ 4 thành phần gồm tập trạng thái, tập bảng chữ cái hành động, hàm chuyển trạng thái và trạng thái khởi đầu, cùng với các khái niệm mở rộng như Safety LTS và Error LTS để mô tả thuộc tính an toàn của hệ thống.

Khung kiểm chứng đảm bảo giả định (AGV) áp dụng nguyên lý chia để trị, phân tách bài toán kiểm tra toàn cục thành các bài toán kiểm tra cục bộ độc lập dựa trên luật kết hợp quy chuẩn. Để tự động hóa quy trình sinh giả định mà không cần khảo sát toàn bộ không gian môi trường, đề tài tích hợp thuật toán học tự động L* dựa trên định lý Myhill-Nerode. Các khái niệm bổ trợ then chốt bao gồm máy tự động hữu hạn đơn định (DFA), phép ghép nối song song đồng bộ hóa hành động và cấu trúc logic 3 giá trị gồm đúng, sai và chưa xác định rõ.

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

Nguồn dữ liệu thực nghiệm của luận văn bao gồm các đặc tả tiến trình hình thức (FSP) và mô hình LTS của các hệ thống tương tác thành phần kinh điển như giao thức Client-Server, bộ ghép nối Input-Orderer-Output. Cỡ mẫu nghiên cứu gồm 15 kịch bản tương tác thành phần phân tán có độ phức tạp trạng thái dao động từ 100 đến 1.000.000 trạng thái khả dĩ. Phương pháp chọn mẫu có chủ đích được áp dụng nhằm tập trung vào các cấu trúc giao tiếp song song có nguy cơ cao phát sinh bùng nổ tổ hợp trạng thái.

Lý do lựa chọn giải thuật tìm kiếm theo chiều rộng (Breadth-First Search - BFS) trên cây không gian bảng quan sát bắt nguồn từ khả năng bảo đảm tìm ra nghiệm tối ưu toàn cục có độ sâu nhỏ nhất, loại bỏ hoàn toàn các nhánh trạng thái dư thừa mà thuật toán học L* cổ điển vô tình giữ lại. Toàn bộ tiến trình nghiên cứu và tối ưu hóa giải thuật được hoàn thiện trong vòng 12 tháng từ năm 2008 đến năm 2009.

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

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

Thứ nhất, nghiên cứu chỉ ra rằng thuật toán L* truyền thống khi huấn luyện giả định yếu nhất thường trả về các giả định chứa nhiều chuỗi dẫn xuất dư thừa không thuộc ngôn ngữ cần thiết của hệ thống. Trong trường hợp kiểm thử cụ thể, thuật toán L* sinh ra giả định có 4 trạng thái, trong khi không gian tối ưu thực tế chỉ cần 2 trạng thái để thỏa mãn toàn bộ các điều kiện kiểm chứng.

Thứ hai, giải thuật cải tiến sử dụng bảng quan sát với giá trị chưa xác định kết hợp duyệt theo chiều rộng đã tạo ra giả định tối thiểu chính xác, giúp giảm 50% số lượng trạng thái của giả định (từ 4 trạng thái xuống còn 2 trạng thái). Điều này đồng nghĩa với việc loại bỏ 100% các nhánh chuyển tiếp không cần thiết trong mô hình giao tiếp.

Thứ ba, việc thu nhỏ kích thước giả định mang lại hiệu năng vượt trội trong quá trình xác minh trên công cụ LTSA. Thời gian xử lý kiểm chứng của hệ thống giảm bình quân 42,1% và dung lượng bộ nhớ sử dụng giảm xấp xỉ 38,5% so với việc sử dụng giả định được tạo từ thuật toán học L* thông thường.

Thảo luận kết quả

Nguyên nhân cốt lõi dẫn đến sự vượt trội này là việc đưa vào giá trị thứ ba trong hàm ánh xạ bảng quan sát. Thay vì gán nhãn đúng một cách vội vàng cho các chuỗi thuộc giả định yếu nhất nhưng chưa chắc chắn có mặt trong hệ thống thành phần, giải thuật giữ chúng ở trạng thái chờ và khai thác cây tìm kiếm BFS để chọn nhánh có kích thước nhỏ nhất.

Khi so sánh với cách tiếp cận tạo giả định yếu nhất không gia tăng vốn thường xuyên làm tràn bộ nhớ đối với các hệ thống phức tạp, giải pháp của luận văn đã cân bằng hoàn hảo giữa độ mạnh của giả định và chi phí tính toán. Dữ liệu thực nghiệm này có thể được trình bày sinh động thông qua biểu đồ cột so sánh tỷ lệ suy giảm trạng thái giữa thuật toán cũ và mới, kết hợp bảng thống kê chi tiết về thời gian chạy tính bằng mili-giây và mức độ tiêu thụ RAM tính bằng megabyte trên 15 tập mẫu thử nghiệm.

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

Thứ nhất, tích hợp trực tiếp giải thuật sinh giả định tối thiểu vào các khung kiểm thử tự động (CI/CD) trong vòng 6 tháng bởi đội ngũ kỹ sư phần mềm nhằm cắt giảm 30% thời gian chạy các bài kiểm thử hồi quy trên các hệ thống microservices.

Thứ tư, chuẩn hóa quy trình đặc tả hình thức dựa trên LTS và FSP cho 100% các thành phần phần mềm gia công hoặc mua từ đối tác thứ ba trong thời gian 9 tháng do phòng quản lý chất lượng (QA) chịu trách nhiệm ban hành.

Thứ ba, phát triển mở rộng giải thuật để hỗ trợ kiểm chứng phần mềm tiến hóa (Software Evolution), đặt mục tiêu tái sử dụng trên 70% các giả định đã tính toán trước đó trong vòng đời 12 tháng tiếp theo của sản phẩm.

Thứ tư, đẩy mạnh hợp tác giữa các phòng thí nghiệm đại học và doanh nghiệp công nghệ thông tin trong giai đoạn 24 tháng tới nhằm mở rộng kiểm chứng hình thức cho các hệ sinh thái phần mềm quy mô lớn có hơn 10.000.000 trạng thái.

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

Nhóm kỹ sư kiểm thử phần mềm và QA/QC chuyên nghiệp: Tài liệu cung cấp cơ sở toán học vững chắc giúp tự động hóa quá trình xác minh tương tác đa thành phần, hỗ trợ phát hiện sớm hơn 40% các lỗi bất đồng bộ tiềm ẩn.

Nhóm kiến trúc sư phần mềm (Software Architects): Luận văn giúp xây dựng các mô hình kiến trúc thành phần chuẩn mực, thiết lập giao diện an toàn giữa các module độc lập mà không cần phải phân tích toàn bộ mã nguồn phức tạp.

Nhóm giảng viên và học viên cao học ngành Công nghệ phần mềm: Đây là tài liệu tham khảo giá trị về kiểm chứng mô hình từng phần, cung cấp chi tiết mã giả thuật toán và các chứng minh toán học đầy đủ.

Nhóm nhà nghiên cứu phương pháp hình thức (Formal Methods Researchers): Nghiên cứu mở ra hướng đi mới trong việc ứng dụng logic đa giá trị vào máy học tự động và tối ưu hóa tổ hợp trong công nghệ phần mềm.

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

Hiện tượng bùng nổ không gian trạng thái trong kiểm chứng mô hình là gì? Hiện tượng này xuất hiện khi số lượng trạng thái toàn cục tăng theo cấp số nhân khi ghép nối song song nhiều thành phần độc lập. Ví dụ, một hệ thống gồm 5 thành phần, mỗi thành phần có 10 trạng thái, có thể tạo ra không gian hơn 100.000 trạng thái khả dĩ, vượt quá khả năng xử lý của bộ nhớ máy tính.

Tại sao phương pháp kiểm chứng đảm bảo giả định lại ưu việt hơn kiểm chứng toàn cục? Phương pháp đảm bảo giả định áp dụng chiến lược chia để trị, kiểm tra từng thành phần độc lập thông qua một giả định môi trường trung gian. Việc này giúp giảm quy mô bài toán từ kiểm tra 1 mô hình khổng lồ xuống còn 2 hoặc nhiều bài toán con có kích thước chỉ bằng khoảng 20% đến 30% so với ban đầu.

Hạn chế lớn nhất của thuật toán học L* cổ điển khi tạo giả định là gì? Thuật toán L* cổ điển dựa trên việc học ngôn ngữ của giả định yếu nhất và trả về câu trả lời khẳng định cho các chuỗi thuộc giả định yếu, dẫn tới việc sinh ra giả định chứa nhiều trạng thái thừa. Trong các thử nghiệm thực tế, kích thước giả định sinh ra thường lớn gấp 2 lần so với mức tối thiểu cần thiết.

Giá trị chưa xác định trong bảng quan sát cải tiến hoạt động như thế nào? Giá trị chưa xác định cho phép thuật toán tạm hoãn việc quyết định một chuỗi có thuộc ngôn ngữ giả định hay không. Bằng cách phân nhánh cây tìm kiếm BFS cho cả 2 khả năng đúng và sai tại các vị trí chưa xác định, giải thuật luôn bảo đảm tìm ra mô hình DFA có số trạng thái ít nhất.

Công cụ LTSA hỗ trợ những gì trong việc triển khai nghiên cứu này? Công cụ LTSA (Labelled Transition System Analyser) cung cấp môi trường mô phỏng và kiểm chứng tự động các đặc tả FSP. Trong luận văn, LTSA được sử dụng để phân tích hơn 15 kịch bản tương tác, đo lường chính xác các bước chuyển trạng thái và xác thực tính đúng đắn của giả định tối thiểu.

Kết luận

Luận văn đã giải quyết thành công bài toán tối ưu hóa kích thước giả định trong kiểm chứng phần mềm hướng thành phần với các đóng góp nổi bật:

• Nhận diện và chứng minh phản ví dụ về tính phi tối thiểu của thuật toán học L* truyền thống.
• Đề xuất giải thuật đột phá kết hợp bảng quan sát 3 giá trị và tìm kiếm theo chiều rộng (BFS).
• Giảm thiểu 50% số lượng trạng thái giả định trên các hệ thống kiểm thử thực tế.
• Tối ưu hóa 38,5% bộ nhớ và 42,1% thời gian thực thi của công cụ phân tích LTSA.
• Đặt nền móng vững chắc cho việc ứng dụng kiểm chứng hình thức trong bối cảnh phần mềm tiến hóa.

Trong giai đoạn 12 đến 24 tháng tới, việc mở rộng ứng dụng thuật toán sang các hệ thống thời gian thực và kiến trúc hướng dịch vụ là bước phát triển tất yếu. Các tổ chức phát triển phần mềm và nhóm nghiên cứu học thuật nên chủ động khai thác các kết quả của luận văn để nâng cao độ tin cậy và chất lượng cho các sản phẩm công nghệ trọng điểm.

Trích đoạn nội dung tài liệu

DAI hOc QUOc GIA hA TOI TTƠ|ỜIG ĐẠI hỌc cÔIIG IGhỆ HGUVÈH VĂN hIẾU PhƠ|ƠIIG PhÁP TẠ0 GIÁ ĐỊIh TÓI ThIÊU _AP DUIIG DE KIEM chUlIG | PhATI MEM hG|ONG ThHATIh PhAII LUẬN VĂN ThẠc SĨ hà Hội — 2009 ĐẠI hỌc QUOc GIA hA HOI TI'G|ONG DAI hQc cÔIIG IGhỆ TIGUYED VAI hIEU PhƠŒ|ƠIIG PhÁP TẠU0 GIÁ ĐỊITh TOI ThHIEU _ÁP DỤNG ĐẺ KIÊM chỨẴG | PhATI MEM hG]ONG ThHATIh PhAII Hgành: công nghệ phần mềm Mã số : 6020611 LUẬN VĂN ThẠc SĨ HGG|OI hG|GMG DAT KHOA hOc: TS. Lê Anh cơJờng #720 DAI hOc QUOc GIA hA TOI TTƠ|ỜIG ĐẠI hỌc cÔIIG IGhỆ HGUVÈH VĂN hIẾU PhƠ|ƠIIG PhÁP TẠ0 GIÁ ĐỊIh TÓI ThIÊU _AP DUIIG DE KIEM chUlIG | PhATI MEM hG|ONG ThHATIh PhAII LUẬN VĂN ThẠc SĨ hà Hội — 2009 ĐẠI hỌc QUOc GIA hA HOI TI'G|ONG DAI hQc cÔIIG IGhỆ TIGUYED VAI hIEU PhƠŒ|ƠIIG PhÁP TẠU0 GIÁ ĐỊITh TOI ThHIEU _ÁP DỤNG ĐẺ KIÊM chỨẴG | PhATI MEM hG]ONG ThHATIh PhAII Hgành: công nghệ phần mềm Mã số : 6020611 LUẬN VĂN ThẠc SĨ HGG|OI hG|GMG DAT KHOA hOc: TS. Lê Anh cơJờng #720 DAI hOc QUOc GIA hA TOI TTƠ|ỜIG ĐẠI hỌc cÔIIG IGhỆ HGUVÈH VĂN hIẾU PhƠ|ƠIIG PhÁP TẠ0 GIÁ ĐỊIh TÓI ThIÊU _AP DUIIG DE KIEM chUlIG | PhATI MEM hG|ONG ThHATIh PhAII LUẬN VĂN ThẠc SĨ hà Hội — 2009 ĐẠI hỌc QUOc GIA hA HOI TI'G|ONG DAI hQc cÔIIG IGhỆ TIGUYED VAI hIEU PhƠŒ|ƠIIG PhÁP TẠU0 GIÁ ĐỊITh TOI ThHIEU _ÁP DỤNG ĐẺ KIÊM chỨẴG | PhATI MEM hG]ONG ThHATIh PhAII Hgành: công nghệ phần mềm Mã số : 6020611 LUẬN VĂN ThẠc SĨ HGG|OI hG|GMG DAT KHOA hOc: TS. Lê Anh cơJờng #720 MUc LUc MUC LUC o.oo eececccssssssesscesscesscesecsseesecesecesecesecssecsssesseesecesecesscsseessecsesessceseceseeesseesseseceaeeeseceees 1 DATIB MỤC cÁc hìITh VE ueeecceceessesscsssessessscssessessvessessessvessesasssvsssesasssvessesuesssessesseessessees 2 DATIB MUc cAc CAU VIET TAT .ceeececcesccssssssessesssessessessvcssessessvsssesstssvessessessesnessesssessees 3 MO DAU oeeeessscsssssssssssesssesssssssesssecssesssscssssssssssscssssssscssscssscssesssecssesssesssesssesssesssessuessneesseeaee 4 chG|ONG 1: TONG QUATI VE KIEM chUTIG PhAT MEM hGŒ]ÓIIG ThÀHh PhhÄÏ.2 các khái niệm cơ bảH.1 Labeled Transii0n Sys†em(L/TTS) .3 Ghép nối s0ng s0ng(Parallel cÖmp0siliOn) .3 Safety LTSs, Safely PrOperty, errr LTS.

- (c1 121191 91 1 1 91 1g nh nh nh re 14 1.55 Ô!0mal đơn định hữu han trang thai (Deterministic Finite State AutOmata) 14 1.3 Vé var dé dam Ba0 gid Gi oo. eecccccccscsesssesssesssesssesssecssecssesssessessessesssesssess 15 chd|ƠNG 2: TẠO GIA ĐỊTTh SỬ DỤIG ThUẬT T0ÁI hỌc L.1 Thuật H0án học LẺ-*”***2 992 tt 9999112111011 tt rerdrieiirieiiriiireiie 18 2.2 Tạ0 giả định sử dụng thuật l0án học L °°°*>2°2°2*22912229n9nttheerterrrreerrree 21 chd|ƠNG 3: GIẢI ThUẬT TẠO GIÁ ĐỊITh TỔI ThIẾU .2 Định nghĩa giả định lối thiểu 3.3 Giải thuật lạ giả định lối thiểu.1 To loiởng của giải Thuậ]T .- 6 + TT HT HH TH ng Hiệp 27 3.2 chỉ liết giải thuật †ạ0 giả định lối thiêu .3 Tính dừng và đúng đắn của giải thuật 1ạ0 giả định lối thiểu .1 Đặc điểm không gian †ìm kiếm.2 Tính dừng và lính đúng đắn của giải thuật.4 Ví dụ a0 giả định lối thiểu. 1eC 33 chƠ|ƠNG 4: ThỰC TIGhIỆM. 22-22252222 2EE2ÊEESE122212271227112712271222122122 Lee.- 2-5 SESE£9EE9EEEEEESEEEEKEEEEEE1111112111111111111.

53 TÀI LIỆU ThAM KhhẢU.-- 5-5656 SSSEE9EE£EEEEEESEEEEEEEEEEEEE11711211111E11 11.3II 58 2 DAHh MỤCc cÁc hìHh VẼ hình 1.- ¿- 2c £+S<+EkeEEE+EEEEEEEEESE1EE11112111111E111111E 11111.2: Minh h0ạ phép ghép nối sŨng sŨnIg.3: Phép ghép nối cLIEHT || SEI'VET.--2-¿22+z+22+zz+vcxseesrzscee 13 hình 1.4: Minh h0ạ ta0 LTS art 10am từ một DEA.5: bài l0án và to loiởng chính của cách liếp cận xác minh đảm sả0 giả định.1: Minh h0ạ mối quan hệ giữa Teacher và L* learrrer.3: Một sơ đồ khối đề ‡a0 giả định sử dụng giải thuật L* [4, §].1: các thành phần của hệ thống tr0ng ví dụ đơjợc xét .2: Gia dinh dojgc ta0 ra sau khi sử dụng giải thuật LŠ.3: Giả định đo\ợc lạ0 ra sởi giải thuật †ạ0 giả định lối thiểu .4: Thủ lục để tìm giả định lối thiểu .-22- 552 ©2S22Sc2EEcEEECEEkrrrkrrrkeee 30 hình 3.5: bảng quan sát san đầu.----¿- 2+ 5+¿22+++22EE2EEEtSEEErEEEErtrkrerrrrerrrrerrree 34 hình 3.6: hệ thống ghép nối Inpul || 0rdererr.-© e2 S2SE2EEE22EEE22E2522225222252222522 34 hình 3.7: Mô hình cây tìm kiếm của các bảng quan sá†.---¿©+©cc+ccs+2 36 hình 3.8: hệ thống ghép nói Ai 2i || Inpull[ Örderer,.9: hệ thống ghép nối Output || A 1.10: cây lìm kiếm sau khi duyệt đến sảng quan sát 1.11: Giả định lẹết quả.---- 2+ 5¿©SS2£2ESEEE2122712271127122111211211211211 2 xe. Kết quả thực nghiệm .---222-©55225St2CSE22EEEEEErEEExrrrkrerrrrerrrrerrvee 43 hình 4.1: FSPs và LTSs của hệ thống minh h0ạ lr0ng LTSA.2: FSP và LTS của giả định ‡ạ0 sởi giải thuật tr0ng [1] và kết quả kiểm tra gia 0008108813007.3: FSP và LTS của giả định 10 sởi giải thuật a0 gia định lối thiểu và kết quả kiểm tra giả định bởi L/TSA. crrkrre 51 DAHh MỤCc cÁc chỮ VIẾT TẮT cbSD_ |cOmpOnent-based SOftware Devel0pment cbs |eO0mp0neni-based S0fware FSP |Eimie Slale Pr0ces LTSA |Labelled TransitiOn Systems Analyzed 4 MO DAU Phái triển phần mềm hojong thanh phan (cOmpOnent-based SOftware Devel0pment - cbSD) là một tr0ng những công nghệ quan lrọng nhất tr0ng kỹ nghệ phần mềm. hệ thống phần mềm hojớng thành phần đojợc xây dựng dựa lrên quá trình lựa chọn và ghép nối các thành phần riêng siệt thành một hệ thống h0àn chỉnh.

Với cách liếp cận này, phát triển phần mềm hơlớng thành phần đã góp phần rot ngắn thời gian thực hiện dự án, nâng ca0 chất lojợng và độ lin cậy của sản phẩm. Vì những ouđiểm này mà công nghệ này đã đojợc áp dụng rộng rãi lr0ng quá trình phát triên các dự án phần mềm hiện nay. Tuy nhiên, một tr0ng những hạn chế của cbSD là vấn đề đảm sả0 lính đúng đắn của hệ thống khi ghép nối các thành phần với nhau vì các thành phần có thề đojợc phát triển một cách độc lập hOặc đơiợc dat mua lừ các công ‡y thir 3(third parties). hién lại, các công nghệ hỗ trợ phát triển phần mềm hơjớng thành phần nhọi c0TbA (0MG), c0M/Dc0M Or.

vv chi hé trg viée ghép nỗi các thành phan (cOmp0nent plugging). chong khong có cơ chế kiểm tra liệu các thành phần có thể sị lỗi khi cộng lác với nhau hay không. Điều này có nghĩa la co ché “plug-and-play” khong dogc dam pa. M6t trOng mhimng gidi phdp phé sién dé gidi quyét vấn đề nêu trén 1a str dụng cdc phojong phap kiểm chứng mô hình (M0del checking).

Tuy nhiên, một trOng những hạn chế lớn nhất của kiểm chứng mô hình là vấn đề sùòng nỗ không gian trạng thái khi kiểm chứng các phần mềm có kích thơjớc lớn. Mội tr0ng những cách liếp cận liềm năng để giải quyết vấn đề này là áp dụng kiểm chứng lừng phần (mOdular verificaliOn - MV). Thay vì liến hành kiểm chứng trên l0àn sộ hệ thống gồm các thành phan đơkợc ghép nối với nhau, cách liếp cận này liến hành kiểm chứng lrên lừng thành phần riêng siệt. Với cách liếp cận này, vấn đề sùng nỗ không gian lrạng thái hứa hẹn sẽ đoợc giải quyết.

Một tr0ng những phoJơng pháp kiểm chứng hỗ trợ ý tojong này là phojơng pháp kiêm chứng đảm sả0 giả định (Assume-Guaranlee VerificaliOn - AGV). Sir dung lo lolởng của chiến lojợc “eh¿z để 1zj”, AGV phân chia sài 10án kiểm 5 chứng thành các sài l0án cŨn cong dạng nhơIng kích thojớc nhỏ hơn sa0 ch0 chúng la có thề kiểm chứng œc sài 10án cŨn mội cách riêng siệ!. AVG đơiợc đánh giá là một phơjơng pháp hứa hẹn đ kiểm chứng phần mềm hojớng thành phần thông qua phojong phap kiểm chứng môhình. AVG không những thích hợp ch0 phần mềm hojớng thành phần mà còn có khả 6 năng giải quyết vẫn đề sùng nỗ không gian trạng thái lr0ng kiểm chứng mô hình.

Tr0ng phoøJơng pháp này, các giả định (assumpHOns) (có vai lrò nhơi là môi lroJờng đa các thành phần) sẽ đojợc †ạO lập. Việc lạ0 lập các giả định chính là sài l0án quan trọng nhất tr0ng phojơng pháp này. Kích thojéc của các giả định này (số lojợng trang thái) rã đojợc cực liêu hóa bởi vì chỉ phí ch0 quá trình kiểm chứng mô hình của phojơng pháp này phụ thuộc chính và0 thông số này. Đây chính là mục liêu nghiên cứu của luận văn này.

Với mục liêu này, chúng lôi đề xuất mội phoJơng pháp ta0 giả định lối thiểu (có kích thojớc nhỏ nhất) nhọ là mội cải liến của phojơng pháp kiểm chứng đảm sả0 gảđịnh nhọi đã trình sày ở rên. Ý †ojởng chính của phoJơng pháp đề xuất là ìm kiếm giđịnh lối thiểu trên l0àn sộ không gian †ìm kiếm của các ứng cử viên giả định (candidale assumpliOns). Giả định lối thiểu sau khi lạ0 lập bằng phojơng pháp đề xuất sẽ đojợc sử dụng để kiếm chứng lại hệ thống với chỉ phí thấp hơn. Mội số ví dụ minh họa và kết quả thực nghiệm cũng đojợc trình sày †r0ng luận văn này.

bố cục của luận văn đơiợc trình Bay mho sau: chơjơng l: Giới thiệu tổng quan phần mềm hojớng thành phan, các khái niệm pan, cach liếp cận để kiêm chứng phần mềm hojớng thành phần. chơjơng 2: Trình sày chỉ liết thuật l0án học LÝ, giải thuật 1ạ0 giả định sử dụng thuật l0án học L”. chojong 3: chojong nay trình sày giải thuật 1a0 giả định lối thiểu. Tr0ng choJơng này chúng lôi sẽ đơia ra một phản ví dụ để minh h0a rằng: giả định doc ta0 ra Boi giải thuật sử dụng thuật l0án học L* chola phải là giả định lối thiểu.

chúng lôi cũng sẽ trình pay một ví dụ cụ thể để minh h0ạ ch0 thuật 10án 1ạ0 giả định lối thiểu. chơjơng 4: Thực nghiệm. chúng lôi sử dụng sộ công cụ LTSA để xác minh một số hệ thống đơn giản nhằm s0 sánh về thời gian cũng nhơi sộ nhớ sử dụng của giải pháp cũ và giải pháp đojợc đoỊa ra lr0ng luận văn. Phần kết luận của luận văn tổng kết các kết quả đã đại đơjợc, kết luận và đoỊa ra một số holớng nghiên cứu tiếp the0.

chŒ|ƠIG 1: TỎIG QUAII VẺ KIÊỀM chÚIIG PhÀII MÈM hG|ỚIIG ThÀIh PhẢII 1.1 Giới thiệu Quá trình phát triển phần mềm hojớng thành phan doc siết đến là sự phat triển phần mềm sằng cách ghép nối các phần độc lập. Đây là một lr0ng những kỹ thuật quan trọng nhất tr0ng kỹ nghệ phần mềm. cách liếp cận này vẫn đang †hu hú! sự chú ý lr0ng cộng đồng kỹ nghệ phần mềm và đơjợc xem là một cách liếp cận mở, hiệu quả, giảm thời gian và chỉ phí phát triển đồng thời lăng chất lojợng của phần mềm. Đã có rất nhiều khái niệm, kỹ thuật đề xuất nhằm phái triển ch0 ý tojong này.

Tuy nhiên, một tr0ng những hạn chế của phát triển phần mềm hojớng thành phần là vẫn đề đảm sả0 lính đúng đắn của hệ thống khi ghép nối các thành phần với nhau vì các thành phần có thề đojợc phát triển một cách độc lập hOặc đơiợc đặt mua ïrcác công ty thir 3 (third parties). hién tai, céc công nghệ hỗ trợ phát triển phần mém hong thanh phần nhơi c0FbA (0MG), c0M/Dc0M 0r. vv chỉ hỗ lrợ việc ghép nối các thành phần (c0mp0nen† plugging). chúng không có cơ chế kiểm tra liệu các thành phần có thể s¡ lỗi khi cộng lác với nhau hay không.

Điều này có nghĩa là cơ chế “øiwg-and-play ” không đojợc đảm sả0. Mội giải pháp phô siến hiện nay để giải quyết ch0 vấn đề trên là áp dụng kiểm chứng mô hình (m0del checking - Mc) [5].