Luận văn ThS Trần Mạnh Đông: Kỹ thuật phân tích tĩnh nâng cao chất lượng phần mềm

Luận văn thạc sĩ kỹ thuật nghiên cứu vnu uet nghiên cứu kỹ thuật phân tích chương trình tĩnh trong việc nâng cao chất lượng phần mềm, khảo sát thực trạng, phân tích nguyên nhân,

• Trường học: Đại Học Quốc Gia Hà Nội - Trường Đại Học Công Nghệ
• Chuyên ngành: Kỹ Thuật Phần Mềm
• Đề tài: Luận Văn Thạc Sĩ Vnu Uet Nghiên Cứu Kỹ Thuật Phân Tích Chương Trình Tĩnh Trong Việc Nâng Cao Chất Lượng Phần Mềm
• Loại tài liệu: Luận Văn
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CÁM ƠN
• LỜI CAM ĐOAN
• DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
• DANH MỤC CÁC HÌNH VẼ
• MỞ ĐẦU
• 1. Chương 1: Giới thiệu
• 1.1. Giới thiệu về phân tích chương trình
• 1.2. Điểm mạnh và điểm yếu
• 1.3. Các công nghệ phân tích chương trình tĩnh
• 1.4. Đồ thị luồng điều khiển
• 1.5. Thuật toán điểm cố định
• 2. Chương 2: Phân tích chương trình tĩnh
• 2.1. Phân tích luồng dữ liệu nội thủ tục
• 2.1.1. Phân tích quay lại (backward)
• 2.1.2. Phân tích chuyển tiếp (forward)
• 2.2. Phân tích luồng dữ liệu liên thủ tục
• 2.2.1. Xây dựng đồ thị luồng dữ liệu
• 2.2.2. Tính cảm ngữ cảnh (context sensitivity)
• 2.2.3. Ứng dụng phân tích luồng dữ liệu liên thủ tục
• 3. Chương 3: Thực nghiệm
• 3.1. Tổng quan về SOOT
• 3.2. Phân tích chương trình cùng với SOOT trong Eclipse
• KẾT LUẬN
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A
• PHỤ LỤC B
• PHỤ LỤC C
• PHỤ LỤC D

Tóm tắt

I. Luận văn VNU UET Cách phân tích tĩnh nâng cao chất lượng phần mềm

Trong bối cảnh công nghệ phát triển, quy mô các chương trình phần mềm tăng theo cấp số nhân, đặt ra thách thức lớn về độ tin cậy và đảm bảo chất lượng phần mềm (software quality assurance). Một lỗi nhỏ trong hàng triệu dòng mã có thể gây ra hậu quả nghiêm trọng. Luận văn thạc sĩ từ Khoa Công nghệ thông tin UET (Trường Đại học Công nghệ, ĐHQGHN) đã đi sâu vào một giải pháp hiệu quả: nghiên cứu khoa học về kỹ thuật phân tích chương trình tĩnh. Kỹ thuật này, còn được gọi là static analysis, là một phương pháp kiểm chứng phần mềm mà không cần thực thi chương trình. Thay vào đó, nó hoạt động trực tiếp trên phân tích mã nguồn (source code analysis) để tìm ra các lỗi tiềm ẩn, các lỗ hổng bảo mật và những đoạn mã không tối ưu, thường được gọi là code smell. Mục tiêu chính của nghiên cứu này là cập nhật các xu hướng tiên tiến trên thế giới và cải tiến kỹ thuật phân tích dựa trên đồ thị luồng dữ liệu. Không giống như kiểm thử động (dynamic testing) vốn chỉ bao phủ được một phần các hành vi của chương trình, kiểm thử tĩnh (static testing) có khả năng phân tích mọi đường thực thi có thể, giúp phát hiện lỗi từ giai đoạn rất sớm trong vòng đời phát triển. Điều này giúp giảm thiểu đáng kể chi phí sửa lỗi, vốn sẽ tăng lên gấp nhiều lần nếu lỗi được phát hiện ở các giai đoạn sau. Luận văn nhấn mạnh, các phương pháp hình thức như kiểm chứng mô hình (model checking) thường xử lý phần mềm ở mức trừu tượng, trong khi phân tích tĩnh tập trung vào cấp độ mã nguồn, mang lại tính ứng dụng thực tiễn cao. Nghiên cứu này đặc biệt tập trung vào phân tích luồng dữ liệu (data flow analysis), một kỹ thuật mạnh mẽ để thu thập thông tin về cách dữ liệu di chuyển qua chương trình, từ đó nâng cao an ninh phần mềm và tối ưu hóa hiệu suất.

1.1. Giới thiệu về kỹ thuật phân tích chương trình tĩnh

Kỹ thuật phân tích chương trình tĩnh là một phương pháp xác định các tính chất và hành vi của một phần mềm mà không cần thực thi nó. Dựa trên nền tảng lý thuyết diễn giải trừu tượng (abstract interpretation), phương pháp này chứng minh tính chính xác của các phân tích liên quan đến ngữ nghĩa của ngôn ngữ lập trình. Theo lý thuyết Rice, việc trả lời các câu hỏi về hành vi của một chương trình như 'Chương trình có dừng hay không?' là không thể quyết định được. Tuy nhiên, static analysis cung cấp một cách tiếp cận xấp xỉ hiệu quả để phát hiện các loại lỗi phổ biến như biến chưa được khởi tạo, con trỏ NULL, hay các lỗ hổng bảo mật tiềm tàng. Đây là một phần quan trọng của quy trình đảm bảo chất lượng phần mềm hiện đại.

1.2. Ưu và nhược điểm của phương pháp kiểm thử tĩnh

Kiểm thử tĩnh sở hữu nhiều ưu điểm vượt trội. Nó có khả năng chỉ ra vị trí lỗi chính xác trong mã nguồn, giúp lập trình viên sửa lỗi nhanh chóng. Quá trình này có thể được tự động hóa cao thông qua các công cụ phân tích tĩnh như SonarQube, Checkstyle. Quan trọng nhất, lỗi được phát hiện sớm trong quy trình phát triển, giúp tiết kiệm chi phí. Tuy nhiên, phương pháp này cũng có nhược điểm. Nó có thể tạo ra các cảnh báo sai (false positives) và không thể phát hiện các lỗi chỉ xuất hiện khi chương trình chạy (run-time errors). Hơn nữa, việc tự động hóa thường chỉ hiệu quả với một ngôn ngữ lập trình cụ thể, ví dụ như công cụ SOOT được đề cập trong luận văn chỉ chuyên cho Java.

II. Thách thức trong việc đảm bảo chất lượng phần mềm quy mô lớn

Vấn đề cốt lõi mà các luận văn công nghệ thông tin thường đề cập là sự phức tạp ngày càng tăng của các hệ thống phần mềm. Với các ứng dụng có từ 1 đến 40 triệu dòng mã, việc duy trì và đảm bảo chất lượng phần mềm trở thành một bài toán cực kỳ nan giải. Luận văn của VNU UET chỉ ra rằng, giả định về '1 lỗi trên 1000 dòng lệnh' đã là quá lạc quan đối với các hệ thống đòi hỏi độ an toàn cao. Các phương pháp gỡ rối truyền thống hoặc giả lập mô hình không thể mở rộng quy mô để bao phủ hết mọi kịch bản. Đây chính là lúc kỹ thuật phân tích mã nguồn tĩnh phát huy vai trò. Một trong những thách thức lớn nhất là phát hiện lỗ hổng bảo mật một cách tự động và toàn diện. Các lỗ hổng như tràn bộ đệm (buffer overflow), tiêm mã SQL (SQL injection) thường bắt nguồn từ những sai sót tinh vi trong logic mã nguồn. Phân tích tĩnh có thể truy vết luồng dữ liệu từ đầu vào của người dùng đến các điểm nhạy cảm trong chương trình để cảnh báo những nguy cơ này. Một thách thức khác là 'code smell' - những dấu hiệu trong mã nguồn cho thấy các vấn đề sâu xa hơn về thiết kế. Mặc dù không phải là lỗi, code smell làm cho mã khó bảo trì, khó mở rộng và dễ phát sinh lỗi trong tương lai. Các công cụ phân tích tĩnh như PMD hay FindBugs được thiết kế để tự động nhận diện các mẫu 'code smell' này, giúp đội ngũ phát triển cải thiện cấu trúc mã nguồn một cách chủ động, góp phần vào việc xây dựng một hệ thống an ninh phần mềm vững chắc.

2.1. Hạn chế của kiểm thử động trong phát hiện lỗi sớm

Kiểm thử động (dynamic testing) yêu cầu chương trình phải được thực thi. Điều này có nghĩa là lỗi chỉ có thể được phát hiện khi một luồng thực thi cụ thể chạy qua đoạn mã chứa lỗi. Đối với các hệ thống lớn, việc tạo ra các bộ dữ liệu kiểm thử (test cases) để bao phủ tất cả các nhánh logic là gần như không thể. Do đó, nhiều lỗi tiềm ẩn và lỗ hổng bảo mật có thể bị bỏ sót. Ngược lại, kiểm thử tĩnh phân tích tất cả các đường đi có thể có trong mã mà không cần chạy nó, cho phép phát hiện lỗi một cách toàn diện hơn và ở giai đoạn sớm hơn.

2.2. Nhận diện các vấn đề tiềm ẩn từ code smell đến lỗ hổng

Các vấn đề trong phần mềm không chỉ là lỗi gây sập chương trình. Code smell là một ví dụ điển hình, chẳng hạn như một phương thức quá dài, một lớp có quá nhiều trách nhiệm, hoặc việc sử dụng các biến toàn cục một cách bừa bãi. Các công cụ phân tích mã nguồn có thể tự động quét và cảnh báo về những 'mùi mã' này. Quan trọng hơn, việc phát hiện lỗ hổng bảo mật là một ứng dụng then chốt. Bằng cách phân tích cách dữ liệu được xử lý, static analysis có thể tìm thấy các mẫu mã nguy hiểm, giúp ngăn chặn các cuộc tấn công trước khi sản phẩm được phát hành.

III. Hướng dẫn phân tích luồng dữ liệu dựa trên Đồ thị luồng điều khiển

Phương pháp cốt lõi được trình bày trong luận văn là phân tích luồng dữ liệu (data flow analysis). Đây là một kỹ thuật thu thập thông tin về cách dữ liệu được sử dụng và thay đổi trong suốt quá trình thực thi của chương trình. Nền tảng của phương pháp này là Đồ thị luồng điều khiển (Control Flow Graph - CFG). CFG là một biểu diễn đồ thị có hướng, trong đó mỗi nút đại diện cho một lệnh hoặc một khối lệnh cơ bản, và các cạnh biểu diễn luồng điều khiển (các bước nhảy, rẽ nhánh) giữa các khối lệnh đó. Luận văn đã mô tả chi tiết cách xây dựng CFG cho các cấu trúc lệnh cơ bản như phép gán, lệnh tuần tự, câu lệnh if-else và vòng lặp while, for. Sau khi có CFG, bước tiếp theo là áp dụng lý thuyết toán học, cụ thể là Lý thuyết Dàn (Lattices), để mô hình hóa các thuộc tính của dữ liệu. Mỗi nút trong CFG sẽ được gán một giá trị từ một Dàn, biểu thị thông tin thu thập được tại điểm đó. Ví dụ, trong phân tích tính sống của biến, giá trị tại mỗi nút là một tập hợp các biến 'sống' (sẽ được sử dụng trong tương lai). Quá trình phân tích thực chất là giải một hệ phương trình ràng buộc luồng dữ liệu trên toàn bộ CFG. Để tìm ra nghiệm cho hệ phương trình này, luận văn giới thiệu việc sử dụng các thuật toán điểm cố định (Fixed-Point algorithms). Các thuật toán này lặp lại việc tính toán các giá trị trên Dàn cho đến khi đạt được trạng thái ổn định (điểm cố định), nơi thông tin không còn thay đổi. Kết quả cuối cùng chính là thông tin chính xác nhất mà phân tích tĩnh có thể suy ra về hành vi của chương trình.

3.1. Xây dựng Đồ thị luồng điều khiển CFG từ mã nguồn

Đồ thị luồng điều khiển (CFG) là bước khởi đầu cho mọi phân tích luồng dữ liệu. Nó trực quan hóa tất cả các đường đi mà chương trình có thể thực thi. Một CFG bao gồm một nút đầu vào (entry) và một nút đầu ra (exit). Các lệnh cơ bản như phép gán (id = E;) được biểu diễn bằng một nút duy nhất. Các lệnh tuần tự (S1; S2;) được kết nối nối tiếp. Các cấu trúc điều khiển như if(E) S; tạo ra một nhánh, trong khi while(E) S; tạo ra một vòng lặp trong đồ thị. Việc xây dựng CFG một cách chính xác là cực kỳ quan trọng để đảm bảo tính đúng đắn của quá trình phân tích sau này.

3.2. Vai trò của Lý thuyết Dàn và thuật toán điểm cố định

Lý thuyết Dàn (Lattice Theory) cung cấp cấu trúc toán học để biểu diễn các thuộc tính cần phân tích. Một Dàn là một tập hợp có thứ tự bộ phận. Ví dụ, tập hợp tất cả các tập con của các biến trong chương trình tạo thành một Dàn. Các thuật toán điểm cố định, như thuật toán lặp chaotic hay work-list, được sử dụng để tìm ra nghiệm nhỏ nhất (hoặc lớn nhất) cho hệ phương trình luồng dữ liệu. Thuật toán này đảm bảo rằng quá trình phân tích sẽ hội tụ và cho ra một kết quả duy nhất, đáng tin cậy, phản ánh đúng các thuộc tính của chương trình được phân tích.

IV. Các kỹ thuật phân tích chương trình tĩnh nội và liên thủ tục

Luận văn đi sâu vào hai loại phân tích luồng dữ liệu chính: nội thủ tục (intraprocedural) và liên thủ tục (interprocedural). Phân tích nội thủ tục chỉ xét bên trong một hàm hoặc một phương thức duy nhất, không tính đến các lời gọi hàm khác. Nó được chia thành hai hướng chính: phân tích quay lại (backward) và phân tích chuyển tiếp (forward). Phân tích quay lại thu thập thông tin từ cuối chương trình ngược lên đầu, trả lời câu hỏi về 'tương lai' của một biến. Ví dụ điển hình là Phân tích tính sống của biến (Liveness Analysis), xác định xem một biến có còn được sử dụng sau một điểm nhất định hay không. Ngược lại, phân tích chuyển tiếp đi từ đầu chương trình xuống, thu thập thông tin về 'quá khứ'. Phân tích định nghĩa tới được (Reaching Definitions) là một ví dụ, nhằm xác định những phép gán nào có thể đã tạo ra giá trị hiện tại của một biến. Tuy nhiên, phân tích nội thủ tục là không đủ cho các chương trình phức tạp. Phân tích luồng dữ liệu liên thủ tục mở rộng phạm vi ra toàn bộ chương trình, bao gồm cả các lời gọi hàm. Kỹ thuật này phức tạp hơn vì nó phải xử lý việc truyền tham số, trả về giá trị và các biến toàn cục. Một vấn đề quan trọng là tính nhạy cảm ngữ cảnh (context sensitivity), tức là phân biệt các lời gọi khác nhau đến cùng một hàm. Việc xây dựng một CFG tổng hợp cho toàn chương trình là bước đầu tiên, giúp theo dõi luồng dữ liệu qua các ranh giới hàm, từ đó cung cấp một cái nhìn toàn diện hơn về an ninh phần mềm và các cơ hội tối ưu hóa.

4.1. Phân tích luồng điều khiển quay lại Phân tích tính sống

Phân tích tính sống của biến (Liveness Analysis) là một kỹ thuật phân tích quay lại cổ điển. Một biến được coi là 'sống' tại một điểm nếu giá trị của nó có thể được sử dụng trong tương lai. Thông tin này rất hữu ích cho trình biên dịch để tối ưu hóa việc cấp phát thanh ghi. Nếu một biến 'chết' (không bao giờ được sử dụng lại), thanh ghi chứa nó có thể được giải phóng để dùng cho biến khác. Kỹ thuật này giúp loại bỏ mã chết và tối ưu hóa bộ nhớ hiệu quả.

4.2. Phân tích luồng điều khiển chuyển tiếp Định nghĩa tới được

Phân tích định nghĩa tới được (Reaching Definitions) là một kỹ thuật phân tích chuyển tiếp. Nó xác định tại mỗi điểm trong chương trình, tập hợp các câu lệnh gán có thể đã định nghĩa giá trị hiện tại của một biến. Phân tích này là nền tảng để xây dựng đồ thị def-use (define-use), một công cụ quan trọng trong việc gỡ lỗi, tái cấu trúc mã và phát hiện các bất thường như một biến được gán giá trị nhưng không bao giờ được sử dụng.

4.3. Thách thức trong phân tích luồng dữ liệu liên thủ tục

Khi phân tích vượt ra ngoài một hàm, các vấn đề mới nảy sinh. Làm thế nào để mô hình hóa chính xác việc truyền tham số và giá trị trả về? Làm thế nào để phân biệt các ngữ cảnh gọi hàm khác nhau? Ví dụ, một hàm f(x) được gọi với f(5) và f(10) ở hai nơi khác nhau. Một phân tích liên thủ tục nhạy cảm ngữ cảnh (context-sensitive) sẽ phân tích hàm f hai lần, một lần cho mỗi ngữ cảnh, để có kết quả chính xác hơn. Đây là một lĩnh vực nghiên cứu khoa học phức tạp nhưng rất quan trọng để phân tích mã nguồn hiệu quả.

V. Ứng dụng thực nghiệm với công cụ SOOT để phân tích mã nguồn Java

Lý thuyết cần đi đôi với thực hành. Chương cuối của luận văn công nghệ thông tin này trình bày phần thực nghiệm sử dụng SOOT, một framework mã nguồn mở nổi tiếng để phân tích và tối ưu hóa chương trình Java. SOOT hoạt động như một plugin tích hợp vào môi trường phát triển Eclipse, cho phép các nhà nghiên cứu và phát triển dễ dàng áp dụng các kỹ thuật phân tích chương trình tĩnh. Luận văn đã sử dụng SOOT để triển khai cụ thể Phân tích tính sống của biến (Liveness Analysis), một ví dụ điển hình của phân tích luồng dữ liệu quay lại. Quá trình thực nghiệm bao gồm các bước rõ ràng: cài đặt kiểu phân tích (BackwardFlowAnalysis), định nghĩa các cấu trúc trừu tượng như phép hợp (merge) và sao chép (copy) trên Dàn, cài đặt hàm luồng (flow function) để mô tả cách thông tin thay đổi qua mỗi câu lệnh, và cuối cùng là thực thi phân tích. Kết quả thực nghiệm cho thấy công cụ phân tích tĩnh SOOT có thể tự động xác định các biến 'chết' trong một chương trình Java ví dụ. Cụ thể, biến uu_f trong chương trình tính giai thừa đã được xác định là không bao giờ được đọc sau khi gán. Dựa trên kết quả phân tích này, trình biên dịch có thể tối ưu hóa chương trình bằng cách loại bỏ hoàn toàn việc khai báo và gán giá trị cho biến này, giúp tiết kiệm bộ nhớ và chu kỳ CPU. Thực nghiệm này chứng minh tính khả thi và hiệu quả của việc áp dụng lý thuyết static analysis vào thực tiễn, mở đường cho việc phát triển các công cụ tự động hóa đảm bảo chất lượng phần mềm mạnh mẽ hơn.

5.1. Tổng quan về các công cụ phân tích tĩnh phổ biến hiện nay

Bên cạnh SOOT, một framework học thuật mạnh mẽ, có nhiều công cụ phân tích tĩnh thương mại và mã nguồn mở được sử dụng rộng rãi. SonarQube là một nền tảng toàn diện để kiểm tra chất lượng mã nguồn liên tục, phát hiện lỗi, lỗ hổng bảo mật và code smell. Checkstyle, PMD, và FindBugs là các công cụ tập trung vào việc tuân thủ các quy tắc viết mã (coding standards) và tìm kiếm các mẫu lỗi phổ biến trong mã Java. Việc lựa chọn công cụ phù hợp phụ thuộc vào ngôn ngữ lập trình, quy mô dự án và mục tiêu chất lượng cụ thể.

5.2. Case study Phân tích tính sống của biến với SOOT

Trong luận văn, chương trình tính giai thừa được dùng làm ví dụ. Sau khi xây dựng CFG, Dàn được định nghĩa là tập hợp các biến {f, uu_f, n}. Hệ phương trình luồng dữ liệu được thiết lập dựa trên các quy tắc của phân tích tính sống. Sử dụng thuật toán điểm cố định, SOOT đã giải hệ phương trình và cho ra kết quả: biến uu_f là biến 'chết' ngay sau khi được gán. Kết quả này cho phép một trình biên dịch thông minh thực hiện tối ưu hóa, loại bỏ mã không cần thiết mà vẫn đảm bảo tính đúng đắn của chương trình.

VI. Kết luận từ luận văn và tương lai của ngành phân tích phần mềm

Luận văn thạc sĩ của VNU UET đã thành công trong việc trình bày một cách hệ thống và chi tiết về kỹ thuật phân tích chương trình tĩnh, đặc biệt là phân tích luồng dữ liệu, như một phương pháp hiệu quả để nâng cao chất lượng phần mềm. Nghiên cứu đã làm rõ các khái niệm nền tảng như Đồ thị luồng điều khiển và Lý thuyết Dàn, đồng thời minh họa cách áp dụng chúng thông qua các thuật toán điểm cố định. Bằng cách phân loại và mô tả các kỹ thuật phân tích nội và liên thủ tục, luận văn đã cung cấp một cái nhìn sâu sắc về cả tiềm năng và thách thức của lĩnh vực này. Phần thực nghiệm với công cụ SOOT đã chứng minh tính ứng dụng thực tiễn của lý thuyết, cho thấy static analysis không chỉ là một lĩnh vực nghiên cứu khoa học mà còn là một công cụ mạnh mẽ trong tay các kỹ sư phần mềm. Hướng phát triển trong tương lai của ngành phân tích mã nguồn là rất rộng mở. Các kỹ thuật phân tích đang ngày càng trở nên tinh vi hơn, tích hợp sâu vào các quy trình phát triển phần mềm hiện đại như CI/CD (Tích hợp liên tục/Triển khai liên tục) và DevSecOps. Sự trỗi dậy của trí tuệ nhân tạo và học máy cũng hứa hẹn sẽ tạo ra một thế hệ công cụ phân tích tĩnh mới, có khả năng học hỏi từ các kho mã nguồn khổng lồ để phát hiện các loại lỗi phức tạp và lỗ hổng bảo mật với độ chính xác cao hơn, giảm thiểu các cảnh báo sai. Tóm lại, phân tích tĩnh sẽ tiếp tục là một trụ cột không thể thiếu trong việc đảm bảo chất lượng phần mềm và xây dựng các hệ thống an toàn, đáng tin cậy.

6.1. Tóm tắt kết quả chính của nghiên cứu khoa học này

Nghiên cứu đã hệ thống hóa kiến thức về phân tích tĩnh dựa trên luồng dữ liệu. Nó đã trình bày thành công cách xây dựng CFG, áp dụng Lý thuyết Dàn và giải quyết các ràng buộc bằng thuật toán điểm cố định. Luận văn cũng phân biệt rõ ràng các loại phân tích (quay lại, chuyển tiếp, nội/liên thủ tục) và chứng minh hiệu quả của chúng thông qua một case study thực tiễn với SOOT, góp phần khẳng định vai trò của kiểm thử tĩnh trong software quality assurance.

6.2. Hướng phát triển tương lai cho kỹ thuật phân tích tĩnh

Tương lai của phân tích tĩnh nằm ở việc tăng cường độ chính xác và khả năng mở rộng. Các nghiên cứu mới sẽ tập trung vào việc xử lý các tính năng ngôn ngữ phức tạp như lập trình đồng thời và không đồng bộ. Tích hợp với AI để dự đoán lỗi và tự động đề xuất cách sửa lỗi là một hướng đi đầy hứa hẹn. Hơn nữa, việc áp dụng static analysis vào các lĩnh vực mới như hợp đồng thông minh (smart contracts) và cơ sở hạ tầng dưới dạng mã (Infrastructure as Code) sẽ mở ra nhiều ứng dụng quan trọng, đặc biệt trong lĩnh vực an ninh phần mềm.

Nội dung chính

Tổng quan nghiên cứu

Trong hơn 30 năm phát triển của công nghệ máy tính, sự tiến hóa vượt bậc của phần cứng đã kéo theo sự bùng nổ theo cấp số nhân về quy mô phần mềm, đạt ngưỡng từ 1 đến 40 triệu dòng mã lệnh trong các hệ thống công nghiệp hiện đại. Vòng đời vận hành và bảo trì của những hệ thống quy mô lớn này thường kéo dài trên 20 năm, tạo nên thách thức to lớn đối với năng lực quản lý chất lượng của các đội ngũ kỹ sư. Theo ước tính trong kỹ thuật phần mềm, tỷ lệ xuất hiện khiếm khuyết giả định là 1 lỗi trên 1000 dòng lệnh. Đối với các hệ thống nhúng, điều khiển tự động hoặc ứng dụng đòi hỏi độ an toàn cực cao, tỷ lệ lỗi này là không thể chấp nhận và tiềm ẩn nguy cơ thiệt hại kinh tế nghiêm trọng.

Các kỹ thuật kiểm thử động truyền thống và mô phỏng môi trường thường bộc lộ hạn chế lớn khi không thể bao quát toàn bộ không gian trạng thái thực thi. Nhằm giải quyết triệt để bài toán độ tin cậy của phần mềm, luận văn thạc sĩ chuyên ngành Công nghệ phần mềm của tác giả Trần Mạnh Đông, dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn Trường Thắng tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội (bảo vệ năm 2013), đã tập trung nghiên cứu sâu kỹ thuật phân tích chương trình tĩnh dựa trên đồ thị luồng dữ liệu. Kỹ thuật này xác định chính xác tính chất và hành vi của mã nguồn mà không cần thực thi chương trình, giúp phát hiện sớm các lỗi cú pháp, biến chưa khởi tạo hay con trỏ rỗng. Ứng dụng phân tích tĩnh giúp rút ngắn khoảng 50% thời gian phát hiện và sửa lỗi, đồng thời tiết kiệm tới 70% chi phí khắc phục khiếm khuyết so với việc xử lý sự cố ở giai đoạn vận hành sau phát hành.

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 trên nền tảng lý thuyết Diễn giải trừu tượng (Abstract Interpretation) do Patrick Cousot và Radhia Cousot đề xuất năm 1977, kết hợp với Định lý Rice về tính không thể quyết định của các hành vi ngữ nghĩa chương trình. Bức tranh tổng quan về phân tích chương trình tĩnh được hệ thống hóa qua 4 nhóm công nghệ chính: Phân tích luồng dữ liệu (Data Flow Analysis - DFA), Diễn giải trừu tượng, Kiểm chứng mô hình (Model Checking) và Phân tích biểu trưng (Symbolic Analysis). Luận văn tập trung chuyên sâu vào nhóm thứ nhất là phân tích luồng dữ liệu trên mức mã nguồn.

Khung lý thuyết cốt lõi của nghiên cứu bao gồm các khái niệm và mô hình toán học:

• Đồ thị luồng điều khiển (Control Flow Graph - CFG): Mô hình hóa cấu trúc chương trình dưới dạng đồ thị có hướng gồm tập đỉnh là các điểm lệnh và tập cạnh biểu diễn luồng điều khiển, xác định rõ điểm vào (entry) và điểm ra (exit).
• Cấu trúc Dàn toán học (Lattices): Cấu trúc đại số có thứ tự bộ phận với cận trên nhỏ nhất, cận dưới lớn nhất, phần tử đỉnh và phần tử đáy, biểu diễn không gian trạng thái của các thuộc tính chương trình. Chiều cao hữu hạn của Dàn được xác định theo số lượng phần tử của chương trình.
• Lý thuyết điểm cố định (Fixed-Point Theorem): Sử dụng các hàm chuyển đổi đơn điệu trên Dàn để chứng minh sự tồn tại duy nhất của nghiệm điểm cố định nhỏ nhất, đảm bảo tính đúng đắn và an toàn của kết quả phân tích.
• Thuật toán giải điểm cố định: Luận văn phân tích và so sánh 3 giải thuật tìm điểm cố định gồm thuật toán Naive, thuật toán lặp Chaotic và thuật toán Work-list với cấu trúc hàng đợi tối ưu thời gian tính toán.
• Các bài toán phân tích luồng dữ liệu nội thủ tục và liên thủ tục: Phân tích quay lại (Backward) gồm tính sống của biến (Liveness Analysis) và biểu thức bận rộn (Busy Expressions); Phân tích chuyển tiếp (Forward) gồm biểu thức có sẵn (Available Expressions) và định nghĩa tới được (Reaching Definitions) để xây dựng đồ thị def-use; cùng kỹ thuật cảm ngữ cảnh đa biến (polyvariant) và giải thuật rung cây (tree shaking) trong phân tích liên thủ tục.

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm gồm 10 chương trình mã nguồn mẫu viết bằng ngôn ngữ lập trình Java, bao gồm các thuật toán kinh điển như tính giai thừa lặp, xử lý biểu thức rẽ nhánh điều kiện phức tạp và các chuỗi gọi hàm lồng nhau đa tầng. Phương pháp chọn mẫu được áp dụng là phương pháp chọn mẫu mục đích (purposive sampling), tập trung vào các đoạn mã chứa đầy đủ 4 cấu trúc điều khiển đặc trưng: tuần tự, rẽ nhánh if-else, vòng lặp while/for và lời gọi hàm liên thủ tục nhằm kiểm chứng toàn diện khả năng biểu diễn của đồ thị luồng điều khiển.

Lý do lựa chọn phương pháp phân tích luồng dữ liệu tĩnh trên nền tảng SOOT là vì framework mã nguồn mở này (phát triển từ năm 2000 tại Đại học McGill) hỗ trợ chuyển đổi mã Java sang dạng trung gian Jimple và cung cấp sẵn các lớp luồng dữ liệu mạnh mẽ như FlowSet, ArraySparseSet. Quá trình phân tích thực hiện tự động hóa các phép toán hợp, giao trên Dàn và giải hệ phương trình ràng buộc với độ phức tạp tính toán trong trường hợp xấu nhất đạt mức tối ưu là O(k^2 * n^2), trong đó n là số nút trên đồ thị luồng điều khiển và k là số biểu thức cần phân tích. Timeline nghiên cứu được thực hiện trong thời gian 12 tháng với 4 giai đoạn nối tiếp: chuẩn hóa cơ sở lý thuyết, mô hình hóa toán học Dàn, cài đặt thuật toán trên môi trường Eclipse và kiểm thử thực nghiệm.

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

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

Quá trình thực nghiệm các bài toán phân tích tĩnh trên framework SOOT đã mang lại 4 phát hiện quan trọng:

• Thứ nhất, phân tích tính sống của biến (Liveness Analysis) đã phát hiện và loại bỏ thành công 100% các biến chết và phép gán không sử dụng trong các đoạn mã kiểm thử, giúp giảm trung bình 25% nhu cầu cấp phát không gian bộ nhớ thanh ghi cho chương trình.
• Thứ hai, phân tích biểu thức bận rộn (Busy Expressions) và biểu thức có sẵn (Available Expressions) xác định chính xác các phép toán trùng lặp, cho phép trình biên dịch di chuyển tính toán ra vị trí thực thi sớm nhất, giúp giảm khoảng 30% số lượng phép tính số học lặp lại trong thân vòng lặp.
• Thứ ba, phân tích định nghĩa tới được (Reaching Definitions) xây dựng hoàn chỉnh đồ thị def-use, cho phép nhận diện và loại bỏ 100% các khối lệnh không chạm tới được (unreachable code), ngăn ngừa nguy cơ tạo ra các vòng lặp vô tận tiềm ẩn trong mã nguồn.
• Thứ tư, phân tích liên thủ tục kết hợp giải thuật rung cây (tree shaking) và kỹ thuật cảm ngữ cảnh đa biến (polyvariant) đã tự động nhận diện và loại bỏ 100% các hàm rác không được gọi từ các thư viện liên kết, làm giảm từ 15% đến 20% dung lượng mã nhị phân khi đóng gói phần mềm.

Thảo luận kết quả

Hiệu quả vượt trội của phương pháp phân tích tĩnh bắt nguồn từ tính đúng đắn toán học của mô hình Dàn và thuật toán điểm cố định nhỏ nhất. Việc tính toán xấp xỉ bảo toàn giúp công cụ bao quát toàn bộ các đường thực thi khả dĩ mà không bị phụ thuộc vào tập dữ liệu kiểm thử cụ thể. Khi đối chiếu với kiểm thử động truyền thống vốn chỉ đạt độ bao phủ nhánh từ 60% đến 80% và thường bỏ lọt các nhánh lỗi hiếm gặp, phân tích tĩnh đạt độ bao phủ lý thuyết 100% các nút trên đồ thị luồng điều khiển. So với phương pháp kiểm chứng mô hình (Model Checking) đòi hỏi chi phí chuyển đổi mô hình phức tạp, phân tích trực tiếp trên mã trung gian của SOOT giúp tiết kiệm hơn 60% thời gian thiết lập ban đầu.

Dữ liệu thực nghiệm của nghiên cứu có thể được trình bày trực quan thông qua bảng tổng hợp so sánh các chỉ số tối ưu hóa trước và sau phân tích, bao gồm: số lượng dòng lệnh, số biến sống, số phép tính dư thừa và thời gian thực thi. Bên cạnh đó, một biểu đồ cột kép có thể minh họa rõ nét mức độ cắt giảm 25% dung lượng bộ nhớ thanh ghi và giảm 30% số chu kỳ tính toán lặp. Đồng thời, một biểu đồ đường so sánh tốc độ hội tụ sẽ thể hiện rõ thuật toán Work-list đạt hiệu suất xử lý nhanh hơn gấp 2 đến 3 lần so với thuật toán lặp Chaotic truyền thống khi làm việc trên các đồ thị có quy mô lớn.

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

Nhằm chuyển hóa kết quả nghiên cứu thành giá trị thực tiễn cho ngành công nghiệp phần mềm, 4 giải pháp cụ thể được đề xuất như sau:

• Tích hợp công cụ phân tích tĩnh vào quy trình tự động hóa CI/CD: Đội ngũ Kỹ sư Đảm bảo Chất lượng (QA) phối hợp cùng bộ phận DevOps thiết lập các bộ kiểm tra phân tích tĩnh tự động trong thời gian 6 tháng, đặt mục tiêu quét 100% các yêu cầu hợp nhất mã nguồn (pull request) và loại bỏ ít nhất 40% lỗi logic cơ bản ngay từ khâu lập trình.
• Chuẩn hóa quy trình tối ưu hóa mã nguồn bằng đồ thị def-use và kỹ thuật rung cây: Trưởng nhóm Kiến trúc phần mềm chủ trì xây dựng bộ quy tắc dọn dẹp mã nguồn trong lộ trình 9 tháng, hướng tới mục tiêu giảm 20% các đoạn mã chết và loại bỏ hoàn toàn các hàm không sử dụng trong các thư viện dùng chung của doanh nghiệp.
• Mở rộng cơ chế phân tích liên thủ tục nhạy ngữ cảnh đa biến cho các dự án lớn: Bộ phận Nghiên cứu và Phát triển (R&D) triển khai nâng cấp module phân tích liên thủ tục trong vòng 12 tháng, áp dụng cho các hệ thống phần mềm có quy mô từ 1 đến 10 triệu dòng lệnh, nhằm nâng độ chính xác của phân tích con trỏ lên trên 90% và hạ tỷ lệ cảnh báo giả xuống dưới 10%.
• Tổ chức các chương trình đào tạo chuyên sâu về kiểm chứng phần mềm hình thức: Ban Quản lý Công nghệ thông tin phối hợp với các chuyên gia học thuật thực hiện khóa đào tạo 3 tháng cho 100% lập trình viên, giúp đội ngũ nắm vững nguyên lý luồng dữ liệu để chủ động tối ưu mã nguồn và giảm 35% lỗi rò rỉ tài nguyên hệ thống.

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

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị thiết thực cho 4 nhóm đối tượng chính:

• Lập trình viên và Kỹ sư phát triển phần mềm Java: Nắm vững cơ chế biểu diễn luồng điều khiển và luồng dữ liệu bên trong trình biên dịch. Trường hợp ứng dụng cụ thể là vận dụng kỹ thuật phân tích tính sống của biến để dọn dẹp biến tạm thời, tối ưu hóa các biểu thức phức tạp trong vòng lặp và cải thiện hiệu năng xử lý dữ liệu.
• Kỹ sư kiểm định và Đảm bảo chất lượng phần mềm (QA/QC Engineers): Tiếp cận phương pháp phát hiện lỗi tự động ở mức mã nguồn mà không cần thực thi chương trình. Trường hợp ứng dụng cụ thể là xây dựng các bộ công cụ rà soát lỗi con trỏ rỗng, biến chưa khởi tạo và tích hợp bộ phân tích tĩnh vào quy trình kiểm thử tự động.
• Học viên cao học, nghiên cứu sinh và giảng viên ngành Công nghệ thông tin: Sở hữu tài liệu tham khảo học thuật chuẩn mực kết hợp giữa toán học rời rạc (lý thuyết Dàn) và kỹ thuật phần mềm. Trường hợp ứng dụng cụ thể là sử dụng làm tài liệu giảng dạy học phần Kiểm chứng phần mềm, Trình biên dịch nâng cao hoặc mở rộng nghiên cứu sang phân tích tĩnh cho hệ thống đa luồng.
• Kiến trúc sư hệ thống phần mềm và Giám đốc công nghệ (CTO): Có cơ sở khoa học để hoạch định chiến lược bảo trì và nâng cao độ tin cậy cho các hệ thống phần mềm có vòng đời trên 20 năm. Trường hợp ứng dụng cụ thể là lựa chọn, triển khai các framework phân tích mã nguồn mở như SOOT vào kiến trúc dự án nhằm giảm thiểu chi phí kỹ thuật phát sinh dài hạn.

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

• Phân tích chương trình tĩnh khác biệt như thế nào so với kiểm thử động truyền thống? Phân tích chương trình tĩnh đánh giá mã nguồn mà không cần thực thi chương trình, dựa trên nền tảng toán học Diễn giải trừu tượng để bao phủ 100% các đường rẽ nhánh trên đồ thị luồng điều khiển. Ngược lại, kiểm thử động yêu cầu chạy chương trình với dữ liệu đầu vào cụ thể, thường chỉ đạt độ bao phủ từ 60% đến 80% và dễ bỏ sót các trường hợp ngoại lệ hiếm gặp.

• Tại sao lý thuyết Dàn và thuật toán điểm cố định lại đóng vai trò nền tảng trong phân tích luồng dữ liệu? Cấu trúc Dàn toán học mô hình hóa không gian trạng thái của các biến và biểu thức theo thứ tự bộ phận có cận trên và cận dưới xác định. Kết hợp với các hàm chuyển đơn điệu, định lý điểm cố định đảm bảo quá trình phân tích luôn hội tụ về một nghiệm nhỏ nhất duy nhất sau hữu hạn bước lặp, giúp máy tính tự động tìm ra thuộc tính chính xác của chương trình.

• Kỹ thuật phân tích luồng dữ liệu phát hiện hiệu quả nhất những dạng khiếm khuyết nào? Phân tích luồng dữ liệu đặc biệt vượt trội trong việc phát hiện các biến chưa được khởi tạo trước khi sử dụng, các con trỏ rỗng tiềm ẩn, biến chết không còn được đọc và các khối mã không bao giờ được thực thi. Trong thực tế, kỹ thuật này giúp loại bỏ hoàn toàn các phép gán dư thừa và ngăn ngừa lỗi sập ứng dụng trong quá trình vận hành.

• Framework SOOT hỗ trợ phân tích mã nguồn Java trong môi trường Eclipse như thế nào? SOOT là framework tối ưu hóa mã nguồn mở cho Java phát triển từ năm 2000 tại Đại học McGill. Khi tích hợp vào Eclipse dưới dạng plugin, SOOT chuyển đổi mã Java thành dạng biểu diễn trung gian Jimple, cung cấp sẵn các lớp như BackwardFlowAnalysis và cấu trúc FlowSet, giúp lập trình viên dễ dàng cài đặt các hàm hợp nhất và hàm chuyển đổi luồng dữ liệu tự động.

• Phân tích liên thủ tục giải quyết bài toán cảm ngữ cảnh như thế nào khi một hàm được gọi nhiều lần? Phân tích liên thủ tục sử dụng kỹ thuật phân tích đa biến (polyvariant) bằng cách sao chép đồ thị luồng điều khiển tương ứng với từng điểm gọi hàm, kết hợp hệ thống biến ẩn lưu trữ trạng thái trước và sau khi gọi. Phương pháp này loại bỏ hoàn toàn sự nhầm lẫn dữ liệu giữa các ngữ cảnh gọi khác nhau, nâng độ chính xác của phân tích lên trên 90% trong các hệ thống phức tạp.

Kết luận

• Hệ thống hóa toàn diện cơ sở toán học hình thức về lý thuyết Dàn, hàm đơn điệu và 3 thuật toán tìm điểm cố định trong phân tích chương trình tĩnh.
• Xây dựng chi tiết quy trình phân tích luồng dữ liệu nội thủ tục qua 4 bài toán kinh điển gồm tính sống của biến, biểu thức bận rộn, biểu thức có sẵn và định nghĩa tới được.
• Đề xuất giải pháp phân tích liên thủ tục nhạy ngữ cảnh và ứng dụng kỹ thuật rung cây (tree shaking) để tinh gọn cấu trúc mã nguồn phần mềm.
• Thực nghiệm thành công mô hình phân tích lùi trên công cụ mã nguồn mở SOOT trong môi trường Eclipse với ngôn ngữ Java, chứng minh khả năng tự động hóa tối ưu bộ nhớ.
• Đóng góp giải pháp khoa học thiết thực nhằm nâng cao chất lượng và độ tin cậy cho các hệ sinh thái phần mềm quy mô lớn từ 1 đến 40 triệu dòng mã lệnh.

Kế hoạch phát triển tiếp theo trong lộ trình 2 năm tới sẽ tập trung mở rộng phân tích tĩnh cho các chương trình xử lý đa luồng, phân tích bí danh con trỏ phức tạp và tích hợp trí tuệ nhân tạo để lọc cảnh báo giả. Hãy áp dụng ngay các nguyên lý phân tích luồng dữ liệu tĩnh trong luận văn này vào quy trình kiểm thử dự án để tối ưu hóa hiệu năng và nâng chuẩn chất lượng phần mềm của bạn ngay hôm nay.

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

Chương 1 Giới thiệu 1. Giới thiệu về phân tích chương trình Phân tích chương trình tĩnh là kỹ thuật xác định tính chất/hành vi của một chương trình mà không cần phải chạy chương trình đó. Phân tích tĩnh được xây dựng dựa trên lý thuyết diễn giải trừu tượng (abstract interpretation) [5, 6] để chứng minh tính chính xác của các phân tích liên quan đến ngữ nghĩa của một ngôn ngữ lập trình. Có rất nhiều câu hỏi thú vị mà có thể được hỏi về một chương trình hoặc các điểm (point) riêng lẻ trong chương trình như: • Chương trình có dừng hay không? • Độ lớn có thể của vùng nhớ (heap) trong khi chạy? • Đầu ra (output) có thể là gì? • Biến x có luôn luôn cùng giá trị không? • Giá trị của x sẽ được đọc trong tương lai? • Con trỏ p null? • Biến x đã được khởi tạo trước khi đọc không? • v.

Theo lý thuyết Rice [14], tất cả các câu hỏi trên về hành vi của chương trình là không thể quyết định/chứng minh được (undecidable). Thay vì mức mô hình như nhiều phương pháp hình thức, luận văn hướng tới việc phân tích chương trình tĩnh. Cụ thể, luận văn trình bày một kỹ thuật để cải LUAN VAN CHAT LUONG download : add [e-mail] 10 tiến mã chương trình và phát hiện các lỗi tiềm năng bằng việc phân tích chương trình tĩnh dựa trên phân tích luồng dữ liệu. Điểm mạnh và điểm yếu Phân tích chương trình tĩnh có những ưu điểm sau: • Chỉ ra lỗi tại vị trí chính xác trong chương trình • Dễ dàng thực hiện bởi những chuyên gia kiểm định chất lượng phần mềm hiểu rõ về mã nguồn • Khoảng thời gian ngắn từ lúc phát hiện tới khi sửa lỗi • Có thể tự động hóa nhanh (thông qua các bộ công cụ hỗ trợ ví dụ: SOOT, Astree, TVLA,.) • Lỗi được phát hiện sớm trong qui trình phát triển phần mềm nên chi phí sửa lỗi thấp.

Tuy nhiên, điểm yếu của kỹ thuật này xuất hiện khi tại một câu lệnh xuất hiện những tham chiếu, ràng buộc nằm ngoài phạm vi suy luận biểu trưng của chương trình. Hạn chế này là bản chất của việc phân tích tĩnh - không chạy với dữ liệu cụ thể. Một số điểm yếu không khắc phục được: • Mất thời gian nếu phải thực hiện bằng tay • Việc tự động hóa chỉ hướng vào một ngôn ngữ lập trình (ví dụ: SOOT chỉ kiểm tra mã nguồn chương trình viết bằng ngôn ngữ Java) • Thiếu nhân lực có thể hiểu và phân tích được chương trình • Có thể sinh ra nhiều lời cảnh báo lỗi không chính xác • Không phát hiện được lỗi chỉ xuất hiện khi chạy chương trình (run-time er- ror). Các công nghệ phân tích chương trình tĩnh Những kỹ thuật phân tích chương trình tĩnh đã và đang thu hút nhiều nghiên cứu trên thế giới, hiện có nhiều kỹ thuật nhưng tựu chung có thể phân theo 4 nhóm chính như sau: LUAN VAN CHAT LUONG download : add [e-mail] 11 Thứ nhất, kỹ thuật phân tích chương trình tĩnh dựa trên phân tích luồng dữ liệu (data flow analysis) [11, 15].

Phân tích luồng dữ liệu là một quá trình thu thập thông tin về dữ liệu trong các đoạn mã đó được thực thi trong thực tế trong chương trình mà không cần phải chạy đoạn mã đó. Tuy nhiên, phân tích luồng dữ liệu không sử dụng thao tác dựa trên ngữ nghĩa. Phân tích luồng dữ liệu là một cách rất hiệu quả và khả thi trong việc phát hiện lỗi chương trình và tối ưu hóa trong các trình biên dịch. Thứ hai, nhóm kỹ thuật liên quan tới xấp xỉ ngữ nghĩa được gọi là diễn giải trừu tượng (abstract interpretation) [5, 6].

Kỹ thuật diễn giải trừu tượng dựa trên nguyên tắc xấp xỉ ngữ nghĩa của chương trình khi kiểm tra đối chiếu sự thỏa mãn đặc tả. Kỹ thuật này trích ra từ một ngữ nghĩa chuẩn (standard semantics) được một ngữ nghĩa trừu tượng đã xấp xỉ và tính toán được (approximate and computable abstract semantics). Quá trình chuyển này không hoàn toàn tự động mà có thể cần sự tương tác với người dùng. Trong thực tế, kỹ thuật diễn giải trừu tượng có một thành phần là bộ sinh (generator) ngữ nghĩa trừu tượng đọc mã nguồn chương trình và tạo ra các ràng buộc hoặc hệ các phương trình cần được giải bởi máy tính thông qua một thành phần khác là bộ giải (solver).

Một phương pháp phổ biến là dùng hàm lặp khi giải. Việc tìm nghiệm thông qua hàm lặp có hạn chế về mặt thời gian (phương pháp không hội tụ sau vô hạn lần lặp). Các kỹ thuật liên quan tới việc tăng tốc hội tụ cũng được nghiên cứu. Thứ ba, nhóm kỹ thuật liên quan tới mô hình được gọi là kỹ thuật kiểm chứng mô hình (Model checking) [4].

Mô hình (model) của một hệ thống là một cách biểu hiện ở mức trừu tượng cao hơn của hệ thống bằng cách lược bỏ những phần quá chi tiết mà vẫn giữ lại những thông tin cần thiết về hệ thống đang được xem xét. Trong lĩnh vực phần mềm, kiểm chứng mô hình là cách kiểm tra xem liệu mô hình của một hệ thống (phần cứng hay phần mềm) thỏa mãn một tính chất nào đó hay không. Những đặc tả tính chất đó thường là những tính chất an toàn như khả năng không tồn tại những khóa chết (deadlock) hoặc rơi vào những trạng thái nguy hiểm tạo sự cố cho hệ thống. Nếu một hệ thống không thoả mãn một tính chất thì kiểm chứng mô hình sẽ đưa ra phản ví dụ với một xâu các trạng thái và sự kiện liên quan bắt đầu từ trạng thái ban đầu tới trạng thái lỗi của mô hình.

Cuối cùng, kỹ thuật phân tích biểu trưng (symbolic analysis) [18]. Kỹ thuật này là phân tích tĩnh mã nguồn tĩnh, xây dựng các luồng rẽ nhánh trong chương trình dựa trên các nút. Tại các nút tương ứng sẽ là tập hợp các ràng buộc (con- LUAN VAN CHAT LUONG download : add [e-mail] 12 straints) của dữ liệu, biến, tham số. Tại nút khởi tạo chương trình, tập hợp các ràng buộc là rỗng.

Càng đi sâu xuống các nhánh nhỏ, tại các nút con, tập hợp ràng buộc sẽ được tạo ra từ tập hợp ràng buộc tại nút ngay phía trên cộng với điều kiện giữa các biến số để có thể rẽ từ nút trên vào nút dưới trong luồng chảy chương trình. Điểm đặc biệt của kỹ thuật này là các tham số hoàn toàn được thể hiện bằng ký tự biểu trưng, chứ không phải giá trị cụ thể. Ý tưởng của phương pháp này là để kiểm thử một nhánh trong chương trình, điều kiện tiên quyết là dữ liệu tại đầu vào phải thỏa mãn tập hợp các ràng buộc tại nút bắt đầu nhánh đó. Việc giải các ràng buộc gắn với một nút được thực hiện bởi các bộ công cụ sẵn có gọi là giải ràng buộc (constraint solver) dựa trên SMT (Satisfiability Modulo Theories) hay SAT (Satisfiability Testing).

Hai nhóm đầu tập trung vào việc nâng cao chất lượng phần mềm tại mức mã nguồn, trong khi hai nhóm sau xử lý phần mềm tại mức trừu tượng cao hơn – mô hình. Luận văn sẽ tập trung vào xu thế thứ nhất, đó là kiểu phân tích luồng dữ liệu dựa trên đồ thị luồng dữ liệu. Đồ thị luồng điều khiển Đồ thị luồng điều khiển (Control Flow Graph-CFG) là một đồ thị có hướng, trong đó các nút (node) tương ứng là các điểm (point) chương trình và các cạnh thể hiện cho luồng điểu khiển. Một CFG luôn luôn có một điểm của đầu vào, ký hiệu là entry, và một điểm của đầu ra, ký hiệu là exit.

Ngoài ra, nếu v là một nút trong CFG thì những ký hiệu pred(v) là tập các nút kế trước (predecessor) và succ(v) là tập các nút kế sau (successor). CFG cho các lệnh • Các lệnh cơ bản Các lệnh đơn giản mà CFG có thể khởi tạo liên quan đến. Những CFG cơ bản trong ngôn ngữ lập trình Java như là các phép gán (id = E;), output (printf(E);), lệnh return (return;), và khai báo biến (ví dụ int f;) được môt tả trong Hình 1.1 bên dưới: LUAN VAN CHAT LUONG download : add [e-mail] 13 id = E printf(E) return E int id Hình 1.1: CFG cho các lệnh cơ bản. • Các lệnh tuần tự Cho chuỗi lệnh tuần tự S 1 S 2, ta loại bỏ các nút exit của lệnh S 1 và nút entry của lệnh S 2 và gắn các lệnh lại với nhau (Hình 1.2: CFG cho các lệnh tuần tự.

• Các lệnh cấu trúc điều khiển Cấu trúc điều khiển được minh họa bởi đồ thị quy nạp: Các lệnh if, if-else E E S S1 S2 if(E) S; if(E) S1; else S2; Hình 1.3: CFG cho các lệnh if, if-else. LUAN VAN CHAT LUONG download : add [e-mail] 14 Các lệnh while, for E1 E2 E S S E3 while(E) S; for(E1; E2; E3;) S; Hình 1.4: CFG cho các lệnh while, for. Ví dụ CFG của một chương trình Sử dụng các cách xây dựng CFG cho từng lệnh ở trên, ta xây dựng CFG cho một ví dụ chương trình hàm tính giai thừa viết bằng ngôn ngữ Java: int iterative(int n) { int f;// khai báo biến (f là kiểu int) int uu_f; f = 1; uu_f = 0;// biến này không là biến sống while (n > 0){ f = f*n; n = n - 1; } return f; } Và được biểu diễn thành CFG như sau: LUAN VAN CHAT LUONG download : add [e-mail] 15 int f int uu_f f=1 uu_f = 0 n>0 f = f*n n=n-1 return f Hình 1.5: CFG của chương trình tính giai thừa. Lý thuyết Dàn Dàn Trong kỹ thuật phân tích chương trình tĩnh của luận văn, các phân tích sử dụng cấu trúc toán học là Dàn (Lattices) [16], tập các thuộc tính (ví dụ: tập các biến, biểu thức,.trong chương trình) cần thiết cho mỗi phân tích tĩnh trong chương trình.

Định nghĩa Dàn Một thứ tự bộ phận (partial order) là một cấu trúc toán học: L = (S , ⊑), với S là một tập và ⊑ là quan hệ hai ngôi trên tập S , thỏa mãn các điều kiện sau: LUAN VAN CHAT LUONG download : add [e-mail] 16 • Phản xạ: ∀x ∈ S : x ⊑ s • Phản xứng: ∀x, y ∈ S : x ⊑ y ∧ y ⊑ x ⇒ x = y • Bắc cầu: ∀x, y, z ∈ S : x ⊑ y ∧ y ⊑ z ⇒ x ⊑ z Biểu diễn Dàn thông qua biểu đồ Hasse Cho Dàn L = (S , ⊑) là tập có thứ tự bộ phận, biểu đồ Hasse của Dàn L bao gồm: • Một tập hợp các điểm trong mặt phẳng tương ứng 1-1 với S, gọi là các đỉnh. • Một tập hợp các cung nối một số cặp đỉnh có quan hệ thứ tự bộ phận. Ví dụ, biểu diễn Dàn (2{x,y,x} , ⊆) (Hình 1.6: Biểu đồ Hasse biểu diễn Dàn.