Các Phương Pháp Hình Thức Trong Phần Mềm

Các phương pháp hình thức áp dụng logic toán học vào việc đặc tả, phát triển và kiểm định phần mềm, cho phép chứng minh các thuộc tính của một hệ thống thay vì chỉ kiểm thử.

Definition

Các phương pháp hình thức là các kỹ thuật dựa trên toán học để đặc tả, phát triển và kiểm định các hệ thống phần mềm, trong đó các đặc tả được thể hiện bằng các ngôn ngữ hình thức và các thuộc tính được thiết lập bằng chứng minh hoặc khám phá trạng thái toàn diện.

Scope

Chủ đề này bao gồm các ngôn ngữ đặc tả hình thức như Z, B và TLA+; ngữ nghĩa tiên đề và logic Hoare để lập luận về tính đúng đắn của chương trình; kiểm tra mô hình để xác minh các hệ thống trạng thái hữu hạn và đồng thời; chứng minh định lý và các trợ lý chứng minh; và việc sử dụng các phương pháp hình thức trong phần mềm an toàn và bảo mật quan trọng.

Core questions

• Làm thế nào để hành vi phần mềm có thể được đặc tả một cách rõ ràng trong một ngôn ngữ hình thức?
• Làm thế nào để chứng minh tính đúng đắn của chương trình đối với một đặc tả?
• Kiểm tra mô hình xác minh toàn diện các hệ thống trạng thái hữu hạn và đồng thời như thế nào?
• Chi phí và lợi ích của các phương pháp hình thức biện minh cho việc sử dụng chúng ở đâu?

Key theories

Logic Hoare và ngữ nghĩa tiên đề

Hoare đã giới thiệu một logic về các điều kiện tiên quyết và hậu điều kiện, trong đó tính đúng đắn của các cấu trúc chương trình được thể hiện bằng các tiên đề và quy tắc suy luận, cung cấp cơ sở để chứng minh rằng các chương trình đáp ứng các đặc tả của chúng.

Kiểm tra mô hình

Kiểm tra mô hình tự động và toàn diện khám phá các trạng thái có thể đạt được của một mô hình trạng thái hữu hạn để xác minh các thuộc tính logic thời gian, phát hiện các bế tắc và vi phạm mà việc kiểm thử có thể bỏ sót.

Clinical relevance

Các phương pháp hình thức cung cấp sự đảm bảo mạnh mẽ nhất về tính đúng đắn và được áp dụng ở những nơi mà sự cố là không thể chấp nhận được — hàng không, tín hiệu đường sắt, giao thức bảo mật và phần cứng — mặc dù chi phí của chúng giới hạn việc sử dụng chủ yếu cho các thành phần quan trọng chứ không phải toàn bộ các hệ thống lớn.

Evidence & guidelines

Các cuộc khảo sát về thực tiễn công nghiệp ghi nhận việc áp dụng thành công các phương pháp hình thức trong các lĩnh vực quan trọng về an toàn, và các tiêu chuẩn như DO-178C và Common Criteria công nhận các kỹ thuật hình thức ở các cấp độ đảm bảo cao nhất.

History

Kiểm định chương trình được Floyd và Hoare thành lập vào cuối những năm 1960, kiểm tra mô hình được Clarke, Emerson và Sifakis phát triển vào đầu những năm 1980 (đoạt giải Turing), và các công cụ cùng trợ lý chứng minh đã đưa kiểm định hình thức vào sử dụng công nghiệp cho các hệ thống quan trọng.

Debates

Khả năng mở rộng và chi phí của các phương pháp hình thức

Một cuộc tranh luận dai dẳng liên quan đến việc liệu các phương pháp hình thức có thể mở rộng một cách kinh tế cho phần mềm công nghiệp lớn hay không; những tiến bộ trong tự động hóa và các phương pháp hình thức nhẹ đã mở rộng khả năng ứng dụng, nhưng việc kiểm định toàn diện các hệ thống lớn vẫn còn tốn kém.

Key figures

• C. A. R. Hoare
• Edsger Dijkstra
• Edmund Clarke
• Leslie Lamport

Seminal works

• hoare1969
• clarke1999
• woodcock2009

Frequently asked questions

Các phương pháp hình thức có thay thế việc kiểm thử không?

Thông thường là không. Các phương pháp hình thức đưa ra những đảm bảo mạnh mẽ về một mô hình hoặc đặc tả, nhưng các giả định, môi trường và các khía cạnh không được mô hình hóa vẫn cần kiểm thử; trên thực tế, hai phương pháp này bổ sung cho nhau, với các phương pháp hình thức tập trung vào các thuộc tính quan trọng nhất.

Tại sao các phương pháp hình thức không được sử dụng ở mọi nơi?

Chúng đòi hỏi chuyên môn và nỗ lực chuyên biệt mà khó có thể biện minh cho hầu hết phần mềm, nơi việc kiểm thử mang lại sự tự tin đầy đủ với chi phí thấp hơn; các phương pháp hình thức tập trung vào những nơi mà hậu quả của sự cố đủ nghiêm trọng để đảm bảo đầu tư.