Cải thiện thuật toán kiểm thử: Phương pháp toán học trong kiểm thử phần mềm

Các phương pháp thiết kế thử nghiệm mới không phải lúc nào cũng xuất hiện đồng thời. Một phần đáng kể của thực tiễn kiểm tra hiện đại đã phát triển thông qua công việc thực nghiệm và lý thuyết tỉ mỉ trong việc điều chỉnh các mô hình toán học. Mặc dù không nhất thiết phải là một nhà toán học mới có thể trở thành một người thử nghiệm giỏi, nhưng việc hiểu nền tảng lý thuyết đằng sau các phương pháp thử nghiệm có thể mang lại lợi ích.

Tối đa hóa phạm vi bao phủ và giảm thiểu số lượng trường hợp thử nghiệm

Logic toán học có thể được áp dụng để tối ưu hóa phạm vi bao phủ mã cho hệ thống. Hãy xem xét một ví dụ đơn giản với câu lệnh "if" chứa hai nhánh và một công thức logic dài trong điều kiện:

 if ( (& a2) & (!(a2 || a4) ) || a3 ) { # action 1 } else { # action 2 }

Để bao quát cả hai nhánh, cần phải hiểu cấu trúc của công thức. Người ta có thể tự hỏi, có thể làm được gì? Bạn luôn có thể kiểm tra toàn bộ đoạn mã này (công thức logic), dẫn đến 16 lần kiểm tra. Tuy nhiên, con số này là khá nhiều và cần nỗ lực giảm số lượng xét nghiệm. Có thể giảm số lượng thử nghiệm bằng cách sử dụng phương pháp Điều kiện sửa đổi/Phạm vi quyết định (MC/DC) (mang lại 11-12 thử nghiệm). Nếu phạm vi bao phủ của chi nhánh đủ để kiểm tra rủi ro thì chỉ cần hai cuộc kiểm tra, nhưng vẫn chưa rõ đó là cuộc kiểm tra nào.

Để giải quyết vấn đề này, đại số boolean có thể được áp dụng vào công thức logic:

 if( (& a2) & (! (a2 || a4) ) || a3 ) = = ( (& a2) & ( (!a2 || !a4) ) || a3 ) = = ( a1 & a2 & !a2 & !a4 || a3 ) = = 0 || a3 = a3

Sau khi chuyển đổi công thức ban đầu, rõ ràng chỉ có một biến a3 thực sự ảnh hưởng đến giá trị đúng. Kết quả là, việc lấy các trường hợp thử nghiệm trở nên đơn giản hơn (một trường hợp có và trường hợp kia có a3 == false ). Hơn nữa, rõ ràng là mã không được tối ưu hóa, vì thật kỳ lạ khi có một biểu thức logic phức tạp chỉ phụ thuộc vào một biến. Thật không may, những tình huống như vậy khá phổ biến trong thực tế và ví dụ được cung cấp tương đối đơn giản.

Tóm lại là:

• 2 bài kiểm tra nếu sử dụng thử nghiệm toàn diện

• 2 lần kiểm tra bằng phương pháp MC/DC

• 2 bài kiểm tra nếu áp dụng phạm vi chi nhánh

  
  

Nói chung, các biểu thức logic có thể được đơn giản hóa (tối thiểu hóa) bằng cách sử dụng đại số, phương pháp toán học và thuật toán. Có ít nhất ba phương pháp tương tự. Các phép biến đổi trực tiếp bằng đại số boolean, như đã giải thích ở trên, luôn hoạt động. Có thể tìm thấy và áp dụng các phương pháp giảm thiểu biểu thức xem xét các đặc điểm của miền cụ thể không chỉ dựa vào toán học và logic mà còn dựa trên đặc thù của miền.

Tối ưu hóa kiểm tra theo cặp

Phương pháp thử nghiệm theo cặp liên quan đến việc tạo ra các bộ thử nghiệm theo cách mà thay vì thử nghiệm tất cả các kết hợp có thể có của các tham số đầu vào thông qua thử nghiệm toàn diện (có thể tốn thời gian và tốn nhiều tài nguyên), các bộ thử nghiệm được thiết kế sao cho mỗi giá trị tham số kết hợp với mọi giá trị tham số đầu vào. giá trị của các tham số được kiểm tra khác ít nhất một lần. Điều này làm giảm đáng kể số lượng các trường hợp thử nghiệm.

Đây là một phương pháp được thiết lập tốt và thường được sử dụng. Tuy nhiên, thật không may, phương pháp này không phải lúc nào cũng hiệu quả khi hệ thống trở nên phức tạp hơn. Câu hỏi đặt ra là liệu việc kiểm tra theo cặp có đủ để kiểm tra kỹ lưỡng một hệ thống phức tạp với nhiều tham số đầu vào không? Câu hỏi này đã thu hút nhiều chuyên gia và nhà nghiên cứu thử nghiệm, trong đó có Viện Tiêu chuẩn và Công nghệ Quốc gia (NIST) ở Hoa Kỳ.

• Pairwise finds 65-97% of errors
• 3-way finds 89-99% of errors
• 4-way finds 96-100% of errors
• 5-way finds 96-100% of errors
• 6-way finds 100% of errors

Theo các nghiên cứu, xét nghiệm theo cặp tìm thấy lỗi trong 65-97% trường hợp. Nếu chúng ta bắt đầu kết hợp không phải các cặp tham số mà là gấp ba hoặc gấp bốn lần, tức là sử dụng thử nghiệm k-way, chúng ta sẽ nhận được số lượng thử nghiệm lớn hơn nhưng cũng bắt được nhiều lỗi hơn.

Ví dụ: giả sử một hệ thống có hai tham số với ba giá trị mỗi tham số và ba tham số với hai giá trị mỗi tham số:

• Pairwise: 10 tests with 14% coverage
• 3-way: 18 tests with 25% coverage
• 4-way: 36 tests with 50% coverage
• 5-way: 72 tests with 100% coverage

Bạn có thể chọn mức độ bao phủ kiểm thử thỏa đáng và số lượng ca kiểm thử có thể chấp nhận được.

Nền tảng của cặp đôi là các mảng trực giao chứa n-bộ (cặp, bộ ba, bộ bốn, ...) của các giá trị có số lần bằng nhau.

Nền tảng thông thường cho thử nghiệm theo cặp và k-way là OA(N, V^k, t) , trong đó:

• N là số hàng

• k là số cột

• V là số giá trị khác nhau trong một cột

• t là cường độ (t=2 cho cặp)

  
  

Trong OA, mỗi tập hợp t cột bao gồm tất cả các bộ dữ liệu với số lần bằng nhau.

Thay vì sử dụng ma trận trực giao, tốt hơn nên sử dụng ma trận phủ. Các ma trận này khác với các ma trận trực giao ở chỗ mỗi tập hợp giá trị xuất hiện ít nhất một lần chứ không phải "số lần bằng nhau". Trong trường hợp này, có ít bài kiểm tra hơn một chút. Các trường hợp kiểm thử không chính xác có thể phát sinh khi bao phủ ma trận, nhưng nhìn chung, quá trình kiểm thử sẽ nhanh hơn nhiều. Do đó, quá trình thử nghiệm được đơn giản hóa đáng kể.

CA(N, V^k, t), trong đó:

• N là số hàng
• k là số cột
• V là số giá trị khác nhau trong một cột
• t là cường độ (t=2 cho cặp)

Trong CA, mỗi tập hợp t cột bao gồm tất cả các bộ giá trị ít nhất một lần. Việc sử dụng ma trận phủ cho phép chuyển từ thử nghiệm từng cặp sang thử nghiệm k chiều mà không làm tăng đáng kể số lượng thử nghiệm.

Trạng thái hệ thống và kiểm tra việc thay đổi trạng thái hệ thống

Thông thường (hầu như luôn luôn), một hệ thống có nhiều hơn hai trạng thái: "đang hoạt động" và "không hoạt động". Hãy xem xét một phần của các tiểu bang có đơn đặt hàng chứng khoán. Lệnh mua hoặc bán cổ phiếu phải trải qua một loạt trạng thái để giao dịch được hoàn thành. Đầu tiên, đơn hàng được tạo, sau đó được sàn giao dịch xác nhận, tiếp theo là nhiều giao dịch mua nhỏ và cuối cùng, số lượng cổ phiếu cần thiết được mua hoặc bán. Tất cả các trạng thái của một lệnh chứng khoán đều được phản ánh trong hệ thống giao dịch và tất nhiên tất cả các chuyển đổi và trạng thái phải được kiểm tra.

Hầu như luôn luôn, tất cả các trạng thái hoặc tất cả các chuyển đổi đều được kiểm tra, nhưng thường thì cả hai đều được xác minh. Có thể đạt được mức độ bao phủ toàn diện nhưng sẽ tốn thời gian, tốn kém và tốn nhiều tài nguyên.

Đồ thị và Automata hữu hạn

Chúng ta hãy xem xét bài toán người bán hàng du lịch (commi Voyager) và thuật toán de Bruijn. Chỉ cần hiểu rằng thuật toán cho phép thu được một tập hợp các đường dẫn ngắn tối ưu hoặc đủ tối ưu có thể đi qua trong biểu đồ để bao phủ nó hoàn toàn là đủ (nói đúng ra, bất kỳ thuật toán nào khác thực hiện được điều gì đó tương tự đều có thể được sử dụng hoặc người ta có thể phát minh ra một thuật toán tùy chỉnh).

• Đầu tiên, lấy các trạng thái ban đầu của hệ thống và xây dựng một biểu đồ mới trong đó các đỉnh tương ứng với các chuyển đổi trong biểu đồ gốc.
• Tiếp theo, che các đỉnh của biểu đồ mới, tức là các chuyển tiếp trong biểu đồ cũ.
• Một số đường dẫn rõ ràng và hóa ra khá ngắn (rất thuận tiện cho việc kiểm tra trạng thái và chuyển đổi của hệ thống).
• Tiếp tục xây dựng những con đường khác. Kết quả là chúng có thể trở nên quá dài (và điều đó không tốt).

Hãy xem xét ví dụ sau để phân tích tình huống:

Có ba người thử nghiệm. Người đầu tiên sẽ thực hiện bài kiểm tra đầu tiên, bài kiểm tra thứ hai – bài kiểm tra thứ hai, bài kiểm tra thứ ba – bài kiểm tra thứ ba. Hai bài kiểm tra đầu tiên sẽ hoàn thành hai bài kiểm tra đầu tiên khá nhanh vì các đường dẫn ngắn (so với bài kiểm tra thứ ba, vì hai bài kiểm tra đầu tiên ngắn), nhưng bài kiểm tra cuối cùng sẽ mất rất nhiều thời gian (vì bài kiểm tra thứ ba rất dài). dài).

Nếu thuật toán de Bruijn được áp dụng, chuỗi thứ ba có thể được "cắt" thành nhiều chuỗi ngắn hơn và việc thực hiện tất cả các thử nghiệm có thể được thực hiện song song một cách hiệu quả.

Chúng ta có thể kết thúc với nhiều thử nghiệm hơn, nhưng trong trường hợp thực hiện song song, việc thử nghiệm sẽ kết thúc nhanh hơn nhiều vì các thử nghiệm ngắn hơn.

Hơn nữa, với nhiều thử nghiệm hơn, việc thực hiện chúng sẽ linh hoạt hơn. Tất cả các bài kiểm tra có thể được chạy đồng thời hoặc các bài kiểm tra không thú vị và ít quan trọng hơn có thể bị loại bỏ. Mức độ ưu tiên cao hơn có thể được chỉ định cho các thử nghiệm vượt qua các trạng thái quan trọng nhất của hệ thống. Có nhiều cách để tận dụng kết quả của thuật toán.

Ngoài ra, thuật toán không sử dụng những thứ dành riêng cho miền; nó hoạt động với các trạng thái và chuyển tiếp hoàn toàn trừu tượng của hệ thống.

Trong kỹ thuật này, phần lớn phụ thuộc vào cách sử dụng thuật toán. Trong trường hợp cực đoan nhất, người kiểm tra có thể không biết gì về logic đằng sau việc chuyển đổi giữa các trạng thái. Trong tình huống như vậy, chuỗi chuyển đổi trạng thái dài sẽ bị thuật toán "cắt" thành nhiều chuỗi ngắn. Một số chuỗi này có thể trở nên vô nghĩa. Vì vậy, các chuỗi thu được cần được đánh giá về tính hợp lý và những chuỗi quan trọng, có ý nghĩa để thử nghiệm. Vô nghĩa và không quan trọng, nhưng những con đường thay đổi trạng thái của hệ thống có thể cung cấp sự hiểu biết về phần nào của hệ thống cần sửa đổi và sẽ hiển thị chính xác phần nào.

Các kết luận chính có thể được xem xét như sau:

• Các thuật toán để giảm thiểu các biểu thức logic cung cấp phạm vi kiểm tra tối đa với nỗ lực tối thiểu. Không phải lúc nào cũng cần sử dụng các thuật toán giảm thiểu - đôi khi việc này rất lãng phí thời gian; tồn tại những cách tiếp cận phổ quát.
• Phạm vi kiểm thử hoàn chỉnh có thể đạt được bằng một tập hợp nhỏ các trường hợp kiểm thử ngắn, dễ song song hóa, tự động hóa, linh hoạt và độc lập.
• Phân tích số liệu thống kê về việc sử dụng ứng dụng trong điều kiện thực tế cho phép tối ưu hóa và điều chỉnh các kỹ thuật thiết kế thử nghiệm hiện có và đạt được phạm vi thử nghiệm cần thiết, đảm bảo chất lượng ứng dụng.
• Việc sửa đổi thử nghiệm theo cặp cho phép thử nghiệm sâu hơn với phạm vi thử nghiệm lớn hơn các thuật toán tiêu chuẩn và với hầu hết các tài nguyên giống nhau.
• Một số thuật toán có thể có hiệu quả trong trường hợp các kỹ thuật thiết kế thử nghiệm tiêu chuẩn kém hiệu quả hơn.
• Có một số thách thức trong sự thất bại của kỹ thuật thiết kế thử nghiệm tổ hợp .
• Các thuật toán thu được có thể dễ dàng thích ứng với các hệ thống khác nhau và không yêu cầu kiến thức đặc biệt về miền.

Đối với những nhược điểm nhỏ, cần lưu ý:

• Một số thuật toán có hiệu quả và phù hợp không phải với mọi trường hợp; trong nhiều tình huống, các kỹ thuật thiết kế thử nghiệm tiêu chuẩn đều có hiệu quả tương đương hoặc đôi khi còn hiệu quả hơn.
• Việc áp dụng các thuật toán yêu cầu một số kiến thức toán học và đôi khi nhiều thời gian hơn cho ứng dụng của chúng nên nó cũng có thể trở thành yếu tố sống còn trong nhiều tình huống.