CHƯƠNG II    KỸ THUẬT PHÁT SINH KHÔNG GIAN ĐẦU VÀO    CHO KIỂM THỬ MỜ TRONG ỨNG DỤNG WEB

Chương này trình bày các vấn đề lý thuyết liên quan đến:

2.1 CÁC KỸ THUẬT PHÁT SINH KHÔNG GIAN ĐẦU VÀO

2.1.1 Không gian đầu vào của ứng dụng (Application Input Space)

 

Số đầu chuyển 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Chuyển mạch 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 Chuyển mạch 2 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 Chuyển mạch 3 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 Chuyển mạch 4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Phạm vi của tất cả các hoán vị có thể của đầu vào mà một ứng dụng có thể nhận được, gọi là không gian đầu vào của nó. Hãy xem xét một ứng dụng đơn giản nhận đầu vào từ bốn thiết bị chuyển mạch nhị phân.

 

 

 

 

 

 

Hình 2.1: Mô hình mô phỏng trực quan của không gian đầu vào của bốn thiết bị chuyển mạch nhị phân

Giả sử rằng, chúng ta cần kiểm tra độ bền vững của ứng dụng. Mục tiêu của chúng ta lúc này là liệt kê các không gian đầu vào với mục đích phát hiện ra bất kỳ trường hợp thử nghiệm mà gây ra thất bại cho ứng dụng. Giả sử, do một lỗi phần mềm, ứng dụng sẽ thất bại khi thiết bị chuyển mạch được thiết lập với giá trị 1011 như trong hình 2.2.

Fuzzing nhằm mục đích tự động tạo ra và gửi dữ liệu kiểm thử sẽ kích hoạt lỗi phần mềm đầu vào liên quan đến. Thách thức đối với các giai đoạn phát sinh dữ liệu của fuzzer là tạo ra dữ liệu kiểm thử bao gồm các trường hợp kiểm tra sẽ kích hoạt các lỗ hổng xuất hiện trong ứng dụng đích ở trường này, sự kết hợp  với trạng thái 1011.

 

 

 

 

 

 

 

 

 

Hình 2.2: Sơ đồ giới thiệu không gian đầu vào với 4 bộ chuyển mạch nhị phân với 1 lỗi ở trạng thái (1011)

2.1.2  Các phương pháp tiếp cận phát sinh không gian đầu vào

Hiện nay, có 2 phương pháp chính để tạo không gian đầu vào cho dữ liệu kiểm thử:  zero knowledge và analysis-based.

2.1.2.1 Zero knowledge

Đối với phương pháp tiếp cận zero knowledge có 3 kỹ thuật chính để tạo ra dữ liệu kiểm thử đầu vào [21]:

• Phát sinh dữ liệu ngẫu nhiên (Random data generation)

• Phát sinh dữ liệu dựa vào Brute-Force

• Phát sinh đột biến dữ liệu

a.      Phát sinh dữ liệu ngẫu nhiên

Kiểm thử mờ với dữ liệu ngẫu nhiên tạo ra được gọi là "fuzzing mù", là kỹ thuật kiểm thử hộp đen mà các chương trình được kiểm tra bằng cách tạo ra đầu vào ngẫu nhiên, độc lập. Kết quả đầu ra được so sánh với thông số kỹ thuật phần mềm để xác minh rằng sản lượng kiểm tra được thông qua hoặc thất bại. Trong trường hợp không có thông số kỹ thuật các trường hợp ngoại lệ của ngôn ngữ được sử dụng có nghĩa là nếu một ngoại lệ phát sinh trong quá trình thực hiện kiểm thử, nghĩa là có một lỗi trong chương trình.

Tuy nhiên, nhược điểm chủ yếu trong tiếp cận ngẫu nhiên để tạo ra dữ liệu thử nghiệm là kém hiệu quả. Chẳng hạn, ở ví dụ trên hình 2.1, xác suất để kích hoạt thành công 1/16. Ứng dụng thực tế thường có một không gian đầu vào rất lớn, và cơ hội tạo ra ngẫu nhiên một trường hợp kiểm tra đó sẽ kích hoạt một thất bại được giảm đáng kể.

Để kích hoạt tính dễ tổn thương, chúng ta sẽ cần phải đạt được hai mục tiêu:

1. Đảm bảo rằng các khu vực dễ bị tổn thương của các mã được thực thi.

2. Đảm bảo rằng đầu vào phù hợp được truyền cho phần dễ bị tổn thương, như vậy các lỗ hổng sẽ được kích hoạt.

Cả hai của các bên trên được thực hiện thông qua đầu vào, do đó đầu vào bao gồm hai thành phần cơ bản:

1. Dữ liệu được điều hướng thông qua các đường dẫn mã có điều kiện, để thiết lập một trạng thái ứng dụng riêng biệt.

2. Các dữ liệu được chuyển vào các ứng dụng để xử lý một lần trạng thái ứng dụng riêng biệt mà nó đạt tới.

Giá trị tĩnh (Static Values)

Giá trị tĩnh (còn được gọi là "con số ma thuật ') trong các dữ liệu định dạng nhị phân và các giao thức mạng là vấn đề đối với các kỹ thuật phát sinh ngẫu nhiên. Sự hiện diện của các giá trị tại các vị trí đặc trưng thường được thử nghiệm trong các giao thức mạng hoặc file nhị phân để phát hiện dữ liệu hư hỏng, hoặc chỉ đơn giản là một phương tiện để xác định các định dạng dữ liệu và từ các định dạng khác của nó. Xác suất của việc tạo ra một cách ngẫu nhiên một giá trị tĩnh hợp lệ là một hàm của kích thước của giá trị, nhưng làm như vậy tại một vị trí trong một chuỗi giá trị là rất nhỏ.

Hãy xem xét những giá trị tĩnh được sử dụng trong file class Java. Trừ bốn byte đầu tiên của một lớp file Java  được thiết lập giá trị 'CAFEBABE', các file sẽ bị từ chối bởi lớp file loader.

Xác suất của việc tạo ra một cách ngẫu nhiên các giá trị 'CAFEBABE' là 2³² (giả sử, sử dụng 4-byte ký tự đại diện). Xác suất của việc tạo ra một cách ngẫu nhiên các giá trị 'CAFEBABE' tại một địa điểm riêng biệt trong một trường hợp thử nghiệm là một chức năng của chiều dài của chuỗi và là nhỏ; do đó một tỷ lệ lớn các trường hợp kiểm thử sẽ không mang lại thông tin hữu ích được tạo ra. Điều này có thể được gọi là hiệu quả dữ liệu kiểm thử.

Cấu trúc dữ liệu

Ngoài con số ma thuật, ứng dụng đầu vào là đối tượng không thay đổi đến một mức độ cao của cấu trúc. Có lẽ đặc điểm cấu trúc phổ biến nhất phát sinh từ nhu cầu đầu vào để phân loại và gắn nhãn khu vực riêng biệt trong các hình thức của tiêu đề.

Lấy ví dụ, các tiêu đề Portable Executable (PE), được sử dụng để xác định các file  mà phù hợp với cấu trúc Portable Executable. Trong số các file mà phù hợp với cấu trúc PE là files  *.exe, *.dll, và *.cpl. Các tiêu đề PE cho phép hệ điều hành Windows loader đến bản đồ files PE vào bộ nhớ. Kể từ khi tiêu đề PE nằm ở phần khởi đầu của tất cả PE files, 15 byte đầu tiên của file *.cpl được hiển thị sử dụng một ứng dụng chỉnh sửa nhị phân như hình 2.3 cho thấy sự bắt đầu của tiêu đề PE.

Hình  2.3: 15 bytes đầu tiên của file Access.cpl

Nếu tiêu đề PE bị thay đổi, các cửa sổ loader có thể từ chối file, và các dữ liệu trong các file có thể không được nạp vào bộ nhớ. Ví dụ thực tế này đặt ra một vấn đề quan trọng: dữ liệu mà thường đi qua các mức xác thực trước khi chuyển đến cốt lõi của một ứng dụng để xử lý. Nơi kết nối mạng được sử dụng, xác nhận có thể xảy ra trong quá trình chuyển đổi trước khi dữ liệu đã đạt đến ứng dụng.

Encapsulation

Nhiều giao thức dữ liệu phổ biến là tự chứa trong các giao thức khác. Giao thức mạng mà gói gọn các giao thức lớp cao hơn là một ví dụ về điều này. Nếu đầu vào không phù hợp với cấu trúc đã định nghĩa ở các mức thấp nhất, nó sẽ bị loại và không được đi qua lên đến mức trên.

Các mức độ cao của cấu trúc đó là thường có mặt trong các dữ liệu đầu vào ứng dụng thêm trọng yếu không thể dự phòng đến không gian đầu vào ứng dụng. Điều này có giảm không gian đầu vào, nhưng theo một cách phức tạp. Biểu đồ không gian đầu vào này đòi hỏi một sự hiểu biết chi tiết về các ứng dụng, định dạng của dữ liệu. Tuy nhiên, như chúng ta sẽ thấy trong kỹ thuật fuzzing đột biến dữ liệu,  bằng cách lấy mẫu một ví dụ đầu vào (hoặc tốt hơn nữa là một loạt các mẫu) khi ứng dụng đang được sử dụng, người ta có thể thu được một hình ảnh " subordinate " hợp lệ của không gian đầu vào, với rất ít sự nổ lực.

Hãy để chúng tôi sửa đổi kịch bản của chúng tôi để phản ánh thực tế là dữ liệu đầu vào ứng dụng thường có cấu trúc. Hãy để chúng tôi nói rằng các ứng dụng kiểm tra tất cả các đầu vào và từ chối bất cứ 4 bộ chuyển mạch được thiết lập đến zero, đại diện cho một kiểm tra giá trị tĩnh.

Hình 2.4: Mô hình không gian đầu vào của 4 bộ chuyển mạch ở trạng thái bị lỗi.

Hình 2.4 Minh họa các ảnh hưởng của từ chối đầu vào, nơi mà các bộ chuyển mạch thứ tư được thiết lập đến zero: ảnh hưởng không gian đầu vào là giảm (trong trường hợp này giảm một nửa) như là kết quả của một kiểm tra giá trị tĩnh, mặc dù không gian đầu vào tuyệt đối vẫn giữ nguyên.

Kể từ khi lỗi phát sinh ngẫu nhiên được tính toán cho bất kỳ cấu trúc trong dữ liệu đầu vào, một tỷ lệ lớn các dữ liệu thử nghiệm ngẫu nhiên tạo ra sẽ bị từ chối ở mọi điểm nơi kiểm thử xảy ra. Khi quy mô của không gian đầu vào tăng, tỷ lệ bị từ chối đến trường hợp thử nghiệm được chấp nhận sẽ tăng đáng kể.

b.      Phát sinh Brute Force

Phát sinh Brute Force liên quan đến chương trình tạo ra mỗi hoán vị có thể của không gian đầu vào. Cách tiếp cận này đòi hỏi phải có kiến thức về mục tiêu, ngoại trừ kích thước không gian đầu vào cần được biết để hạn chế sinh dữ liệu.

Ví dụ, hãy xem xét các giao thức truyền siêu văn bản được định nghĩa trong RFC 2616. Có một số lượng hạn chế của các phương thức như GET, HEAD, TRACE, OPTIONS và như vậy. Trừ khi giao thức Transfer Protocol Hyper Text (HTTP) yêu cầu tiền cố định theo một trong các phương pháp cần thiết, yêu cầu sẽ bị từ chối.

Điều quan trọng cần nhấn mạnh ở đây là khi nào brute force data generation  là khả thi? Chúng ta biết rằng cần có thời gian hữu hạn cho mỗi trường hợp kiểm thử. Để thực hiện Brute force fuzz tất cả các giá trị của một số nguyên 32 bit, yêu cầu tổng cộng 4.294.967.295 trường hợp kiểm thử, giả sử mỗi trường hợp kiểm thử cần 1/100gy thì sẽ mất 500 ngày để xử lý từng trường hợp kiểm thử.

Brute force data generation được áp dụng thành công trong các lĩnh vực của mật mã để liệt kê các không gian khóa, nhưng có rất nhiều sự khác nhau giữa không gian khóa và không gian đầu vào. Ngay cả những khóa không gian lớn nhất cũng nhỏ hơn đáng kể với không gian đầu vào. Do đó, phát sinh Brute force không được áp dụng nhiều trong fuzzing để sinh dữ liệu kiểm thử cho không gian đầu vào.

Các thuật toán phát sinh dữ liệu ngẫu nhiên được sử dụng phổ biến như hoán vị ngẫu nhiên và kết hợp(Permutation andCombination), phân vùng số nguyên ngẫu nhiên (RandomIntegerPartition),v.v… [22]    

Tóm lại, phát sinh ngẫu nhiên là một phương pháp hợp lệ để tạo ra các dữ liệu kiểm thử và đã được sử dụng để xác định các lỗ hổng bảo mật trong các ứng dụng phần mềm kể từ năm 1989 đến nay. Lợi ích chính của phá sinh ngẫu nhiên là nó đòi hỏi ít hoặc không có phân tích các mục tiêu ứng dụng hoặc dữ liệu mà nó xử lý nên có thể nhanh cho quá trình fuzzing khởi đầu.

Những nhược điểm chính của kỹ thuật phát sinh ngẫu nhiên là:

-         Nghèo tính hiệu: tiềm năng cho một tỷ lệ rất lớn các trường hợp thử nghiệm để không mang lại thông tin có giá trị.

-         Độ bao phủ mã (code coverage) nghèo kết quả và không thể xâm nhập sâu vào trạng thái ứng dụng.

-         Không đảm bảo rằng không gian đầu vào sẽ được hoàn toàn liệt kê

-         Không có dấu hiệu rõ ràng của khi fuzzing hoàn tất.

c.      Data Mutation Fuzzing

Để giải quyết những mức độ cao của cấu trúc được tìm thấy trong dữ liệu đầu vào.  Một cách tiếp cận khác hoàn toàn phát sinh dữ liệu kiểm thử hoàn toàn ngẫu nhiên hoặc brute force là đột biến dữ liệu. Đột biến dữ liệu liên quan đến việc thu thập dữ liệu đầu vào ứng dụng trong khi các ứng dụng đang sử dụng, sau đó chọn lọc đột biến các dữ liệu bị bắt bằng cách sử dụng các kỹ thuật ngẫu nhiên hoặc brute force. Bằng cách sử dụng dữ liệu được lưu giữ như là cơ sở để tạo ra dữ liệu kiểm thử phù hợp với các không gian đầu vào.

Kiểm thử mờ đột biến cũng như kiểm thử mờ ngẫu nhiên và brute force có thể được thực hiện ở nhiều tầng khác nhau: nó có thể được áp dụng ở tầng ứng dụng (thường ở dạng đột biến files) và nó có thể được áp dụng tại tầng mạng (trong các hình thức đột biến các giao thức mạng).

Vị trí và giá trị dữ liệu

Vị trí và giá trị dữ liệu là 2 khái niệm được sử dụng nhiều trong kỹ thuật đột biến. Một vị trí dữ liệu là một địa chỉ duy nhất mà có thể được sử dụng để xác định một mục dữ liệu duy nhất (ký tự, byte, bit, v.v…) trong một mảng tuần tự của các mục như vậy. Một giá trị dữ liệu đơn giản chỉ là các giá trị được lưu trữ tại một vị trí dữ liệu đặc biệt .

Hình 2.5: 15 byte đầu tiên của Access.cpl với vị trí dữ liệu '6' được nhấn mạnh.

Trong hình  2.5, chúng ta thấy 15 byte đầu tiên của Access.cpl như đã thấy trong hình vẽ 2.3. Tuy nhiên, trong hình vẽ 2.5, vị trí dữ liệu 6 đã được đánh dấu màu đỏ. Các giá trị tại vị trí dữ liệu này là hệ thập lục phân 00.

Đột biến dữ liệu có thể được định nghĩa là thay đổi giá trị dữ liệu tại các địa điểm dữ liệu đặc biệt. Kỹ thuật Random và brute force có thể được áp dụng cho cả hai lựa chọn vị trí và cách thức mà các giá trị được tổ chức tại các địa điểm được lựa chọn được thay đổi.

Điều quan trọng là cần lưu ý rằng sự đột biến liên quan đến việc thay đổi có chọn lọc: chỉ là một tập hợp con của các vị trí cần được lựa chọn cho thay đổi trong bất kỳ một trường hợp nào. Bằng cách này cấu trúc của dữ liệu nguồn được duy trì.

·        Đột biến dữ liệu Brute Force

Trong dữ liệu đột biến, kỹ thuật brute force có thể được áp dụng cho một trong hai lựa chọn vị trí hoặc giá trị thay đổi, hoặc đồng thời cả hai.

Lựa chọn vị trí cho đột biến dữ liệu Brute Force

Cách tiếp cận này giúp lập trình di chuyển thông qua các nguồn dữ liệu, xác định về việc áp dụng các thay đổi giá trị của mỗi vị trí của dữ liệu nguồn. Do đó, một danh sách các vị trí  dễ bị tổn thương của các nguồn dữ liệu có thể được xác định mà không cần bất kỳ kiến ​​thức của các định dạng hoặc nội dung của dữ liệu. Cách tiếp cận này là hoàn toàn hợp lệ, nhưng có một nguy cơ của một “bùng nổ tổ hợp”, nếu nhiều giá trị thay đổi sẽ được áp dụng cho mỗi vị trí dữ liệu. Kết quả là, các kỹ thuật brute force là sử dụng thực tế để kiểm thử, nhưng thường chỉ khi kết hợp với phạm vi giới hạn về:

-         Dãy giá trị thay đổi được sử dụng

-         Số các vị trí được thay đổi

Trong  Blind Data Mutation File Fuzzing, vị trí được chọn sẽ được ghi đè bởi chỉ có một giá trị:zero. Cách tiếp cận thứ hai liên quan đến việc chọn vùng hữu hạn của các vị trí trong các nguồn dữ liệu, giới hạn phạm vi của vị trí được liệt kê.

Brute Force đối với thay đổi giá trị

Một cách tiếp cận khác để brute force là chọn một vị trí dữ liệu duy nhất (hoặc nhiều địa điểm) và liệt kê tất cả các giá trị có thể là vị trí đó có thể được. Tất nhiên,  yêu cầu của phương pháp này sẽ được quyết định bởi tính chất của các loại dữ liệu ở các vị trí trong vấn đề, vì các kiểu dữ liệu sẽ quyết định số lượng các giá trị mà sẽ cần phải được liệt kê - tức là nếu kiểu dữ liệu vị trí là một byte, sau đó 255 trường hợp thử nghiệm sẽ được yêu cầu.

·        Đột biến dữ liệu ngẫu nhiên

Đối với nhiều người, đột biến ngẫu nhiên là mô hình chăc chắn cho fuzzing: đột biến ngẫu nhiên được áp dụng cho các nguồn dữ liệu tốt được hình thành để phát sinh dữ liệu kiển thử  "bán hợp lệ" với một mức độ cao của cấu trúc, cùng với vùng dữ liệu được tạo ra một cách ngẫu nhiên. Đột biến ngẫu nhiên có thể tái tạo những giá trị tĩnh hợp lệ và cơ cấu đầu vào để thâm nhập vào các ứng dụng hoặc khu vực riêng biệt của các ứng dụng đích.

Tuy nhiên, đột biến ngẫu nhiên có nhiều hạn chế: chỉ phải gọi lại câu lệnh có điều kiện của Godefroid để nhận biết biến đổi ngẫu nhiên bị hạn chế liên quan đến mức độ mã nguồn được thử nghiệm. Ngoài ra, biến đổi ngẫu nhiên, như tất cả khác dạng của zero knowledge data generation, không thể tạo ra thủ tục Self-Referring Checks (SFCs) hợp lệ như checksums hoặc Cyclical Redundancy Checks ( CRCs ).

Hạn chế đột biến dữ liệu

Có 2 hạn chế chính đối với đột biến dữ liệu :

1. Nguồn dữ liệu không phải là một đại diện của không gian đầu vào hiệu quả. Đột biến dữ liệu không được bảo đảm để liệt kê các không gian đầu vào, từ các nguồn dữ liệu sẽ là một tập hợp con của không gian đầu vào. Tất nhiên, đột biến sẽ làm tăng kích thước của không gian dữ liệu mã nguồn đối với hiệu quả không gian đầu vào, nhưng đột biến thông thường (không có cơ chế thông minh ) không có khả năng tạo nên sự khác nhau giữa 2 tập con của không gian đầu vào [23].

2. Kiểm tra self-referring là rất khó có thể được đáp ứng.

Chúng ta đã thấy rằng dữ liệu đột biến có thể giải quyết một số vấn đề phải đối mặt bởi kiểm thử ngẫu nhiên và brute force ; cụ thể là duy trì con số ma thuật và cấu trúc dữ liệu đầu vào cơ bản. Nhưng đột biến dữ liệu không thể giải quyết tất cả các vấn đề: nó không thể vượt qua kiểm tra self-referential, dẫn đến số liệu kiểm thử hiệu quả nghèo và độ bao phủ mã thấp hơn kiểm tra và dữ liệu kiểm thử không được truyền thêm vào ứng dụng; và việc lựa chọn nguồn dữ liệu để biến đổi có thể hạn chế khả năng để tạo ra các dữ liệu thử nghiệm mà sẽ liệt kê các không gian đầu vào.

Đột biến dữ liệu có cơ hội cao hơn trong việc tìm kiếm các lỗ hổng với kiểm thử ngẫu nhiên hoặc brute force. Đột biến dữ liệu cũng đòi hỏi nỗ lực tối thiểu để khởi tạo kiểm thử, so với kiểm thử ngẫu nhiên hoặc brute force.

Bảng 2.1 Bảng so sánh các phương pháp tiếp cận khác nhau của fuzzing

Data Generation Method	Finite test data	Requires Analysis of Application	Likely to produce valid satatic numbers	Likely to mutation data structure	Likely to produce valid CRCs
Random Generation	N	N	N	N	N
Brute force Generation	Y	N	N	N	N
Data Mutation (random)	N	N	Y	Y	N
Data Mutation (Brute force)	Y	N	Y	Y	N
Analysis base data generation	Y	Y	Y	Y	Y

 

Kiểm thử đột biến là một trong những phương pháp kiểm tra hiệu quả nhất trong tìm kiếm lỗi bảo mật và các lỗ hổng trong phần mềm thương mại (Commercial Of The-Shelf -COTS). Nó đã mang lại thành công rất lớn trong bảo mật thử nghiệm thực tế và nó đã được sử dụng rộng rãi bởi các công ty phần mềm lớn như Adobe  và Google cho các mục đích đảm bảo chất lượng [11].

Hiệu quả của fuzzing phần lớn phụ thuộc vào cấu hình fuzzing mà là tập hợp các thông số để chạy một fuzzer. Các nghiên cứu gần đây của A. Rebert [12], cho thấy rằng số lượng các lỗi được tìm thấy trong một chương trình máy tính cùng có thể thay đổi đáng kể tùy thuộc vào file hạt (seed)sử dụng. Thách thức chính là làm thế nào để tìm sự một sự kết hợp của các thông số kỹ thuật fuzzing nhằm tối đa hóa số lượng các lỗi tìm thấy được với một nguồn lực hạn chế. Điều này được giải quyết bằng cách tối ưu hóa không gian tham số của fuzzing qua FCS (Fuzz Configuration Scheduling) qua việc kết hợp có thể có của các tham số và thông tin thu được từ thăm dò kết quả tối ưu hóa của fuzzing [25]. 

Ví dụ, các đột biến tỷ giữa số bit để sửa đổi và số lượng tổng số bit của một seed, mà nó dùng để xác định khoảng cách từ các hạt giống để thử nghiệm tạo ra các trường hợp kiểm thử, và do đó nó có thể có nhiều giá trị tùy ý. Các câu hỏi quan trọng là làm thế nào để rời rạc tham số liên tục. Fuzzers đột biến giải quyết vấn đề này bằng cách chọn chỉ một tỷ lệ đột biến duy nhất, hoặc bằng cách sử dụng tỷ lệ ngẫu nhiên từ một phạm vi cho trước. Tuy nhiên, có một thách thức cơ bản trong các phương pháp hiện có : giữa gán nhãn và lựa chọn tham số. Đầu tiên, nhà phân tích có để lựa chọn các thông số kỹ thuật fuzzing dựa trên chuyên môn của họ. Ví dụ, fuzzing chạy với một hoặc nhiều tỷ lệ đột biến và phải xác định những tham số trong mỗi lần chạy. Thứ hai, nếu không sử dụng tham số thì cần định khoảng thời gian chạy cho chương trình kiểm thử theo thực hiện lịch trình FCS (Fuzz Configuration Scheduling). Một công cụ kiểm thử sử dụng cách thứ hai như FuzzSim được giới thiệu ở [26]. Để giải quyết điều này nhóm nghiên cứu trường đại học CMU đã đưa ra cách chọn một tỷ lệ đột biến tối ưu từ một “cặp hạt chương trình” (program-seed pair) được đưa ra dựa trên xác suất tìm thấy tai nạn ở hệ thống SYMFUZZ [13].

Giả sử chúng ta đưa ra một chương trình và hạt giống 96-bits, bao gồm 32 bits ma thuật, tiếp theo là trường 32 bits số nguyên liên tiếp. Chúng ta cũng giả định rằng con số ma thuật là 4242424216 và hai giá trị số nguyên là số 0. Các chương trình bị treo khi một giá trị nhập hai điều kiện sau đây: (1) con số kỳ diệu vẫn 4242424216; và (2) trường thứ 3 là số nguyên âm.

Hệ thống SYMFUZZ  sử dụng fuzzing đột biến bao gồm hai bước sau đây. Đầu tiên, nó tạo ra các trường hợp thử nghiệm bằng flipping bit đầu vào của một hạt giống. Thứ hai, đánh giá một chương trình được kiểm tra bằng cách sử dụng các trường hợp thử nghiệm được tạo ra để xác định xem khả năng sụp đỗ của chương trình.

Kết quả đánh giá khi thực hiện SYMFUZZ của nhóm trên Linux Debian 7.4, cho thấy 114 tại nạn tìm thấy.

 

Program Crashes Bugs Seed Size (bits) Seed Type abcm2ps 299,204 34 35,404 abc autotrace 15,848 23 16,304 bmp bib2xml 603 2 177,152 bib catdvi 2,045,327 8 1,632 dvi figtppie 43,301 38 8,016 fig gif2png 21,600 3 1,816 gif pdf2svg 125 1 23,368 pdf mupdf 30 5 23,368 pdf Total 2,826,038 114

Bảng 2.2. Kết quả các tai nạn tìm thấy khi thực hiện trên các loại file

 

 

 

 

 

 

 

 

 

 

Một điều cần lưu ý ở đây, khác với fuzzing ngẫu nhiên, có độ phức tạp thuật toán O (N)  hoặc O(N), cụ thể  để tạo ra một số ngẫu nhiên giữa 0 và 2^N - 1 nơi mà mỗi bit mất O (1) thời gian. Tuy nhiên, không gian đầu vào cho thuật toán fuzzing đột biến là không nhỏ, nên thuật toán để thiết kế cho không gian đầu vào thường là K-neighbor.

2.1.2.2.Kiểm thử phân tích giao thức (Protocol Analysis Fuzzing)

Chúng tôi đã thấy các lợi ích và hạn chế của kiểm thử zero-knowledge.  Ở mục này, chúng ta sẽ tìm hiểu protocol analysis fuzzing, một phương pháp giải quyết được nhiều vấn đề mà kiểm thử zero-knowledge phải đối mặt, nhưng đòi hỏi nhiều trí thông minh và nỗ lực trên một phần của cả các thử nghiệm và các fuzzer. Nó cũng mất nhiều thời gian để bắt đầu, nhưng có thể dẫn đến nhiều hiệu quả kiểm tra dữ liệu, nghĩa là thời gian chạy có nghĩa là chạy thử nghiệm có thể ngắn hơn và nhiều hơn các khiếm khuyết phát hiện.

Kiểm thử phân tích giao thức liên quan đến việc thúc đẩy sự hiểu biết về các giao thức và định dạng dữ liệu nhận bởi các mục tiêu ứng dụng để 'thông minh' thông báo thử nghiệm thế hệ dữ liệu. Theo quan điểm của một số tác giả, có hai yêu cầu quan trọng cho fuzzing thông minh[21]:

1. Protocol structure và stateful message sequencing: khả năng để xác định một ngữ pháp trong đó mô tả các loại thông điệp hợp pháp và các luật thông điệp sắp xếp.

2. Data element isolation, tokenisation : Khả năng phân hủy một tin nhắn vào các yếu tố dữ liệu cá nhân và công suất liên quan đến biến đổi và sửa đổi các yếu tố dữ liệu trong sự cô lập và gắn với các loại hình của chúng.

Kiểm thử phân tích giao thức có thể được coi như  kiểm thử hộp đen. Kỹ thuật này được xem như là cơ chế mà một ứng dụng thực hiện một giao thức để xử lý các dữ liệu nhận được: một sự kết hợp của demarshaling (chủ yếu giải nén các luồng dữ liệu) và phân tích (phân tách các dữ liệu nhận được thành các thành phần riêng lẻ).

Kiểm thử thức có thể dẫn đến việc phát sinh dữ liệu kiểm thử với tiềm năng để thực hiện một tỷ lệ lớn các mã ứng dụng mục tiêu hơn so với phát sinh bằng phương pháp  zero-knowledge. Nó có thể được sử dụng để tạo ra các dữ liệu kiểm thử nghiệm ánh xạ đến không gian đầu và sẽ thâm nhập sâu hơn vào các trạng thái ứng dụng, qua static numbers, kiểm tra self-referring, các thành phần của cấu trúc và thậm chí thông qua nhiều cấp độ của trạng thái giao thức qua ngữ pháp dựa trên chuỗi thông điệp.

Tuy nhiên, có một cái giá phải trả kỹ thuật kiểm thử này như : đòi hỏi nỗ lực hơn bất kỳ các phương pháp tiếp cận zero-knowledge.

Fuzzing truyền thống thường sử dụng các khối để mô hình hóa chương trình đầu vào. Phương pháp này được chứng minh có những thành công nhất định, nhưng hiệu quả của nó là bị hạn chế khi áp dụng cho các chương trình kiểm thử mà xử lý đầu vào ngữ pháp, nơi mà các dữ liệu đầu vào là văn bản có thể đọc được với cấu trúc phức tạp, đặc biệt được biểu diễn bởi một ngữ pháp chính thức (formal grammar), chẳng hạn như  ngôn ngữ script  thực thi trên các ứng dụng Web .

Chính vì lý do này, kỹ thuật này được sử dụng để kiểm thử mờ bảo mật cho các ứng dụng Web thường để tạo dữ liệu kiểm thử hiệu quả cho không gian đầu vào. Một số bộ công cụ cho kiểm thử mờ cho ứng dụng Web được biết đến như : Burp Suite, Peach, Sulley Fuzzing WebScarab , BlendFuzz, Radamsa, Sulley, SPIKE, Grinder, NodeFuzz và BlendFuzzv.v…

Để hiểu hơn về kỹ thuật này, chúng ta hãy tìm hiểu công cụ BlendFuzz được nhóm tác giả DingningYang, YuqingZhang và QixuLiu công bố [23].  BlendFuzz là một khung hoạt động dựa trên mô hình cho kiểm thử mờ với đầu vào ngữ pháp. BlendFuzz  sử dụng một  ngữ pháp G (targetgrammar) và một một chương trình chấp nhận chuỗi trong ngôn ngữ L (G) (targetlanguage) là đầu vào của nó. Nó xây dựng đầu vào kiểm thử với cú pháp hợp lệ theo G . Điều này đảm bảo rằng các test case sinh ra thể đi qua khởi tạo lexing và giai đoạn parsing của chương trình kiểm thử. Khi đó, BlendFuzz tạo đầu vào kiểm thử ngữ pháp một cách hệ thống, nhờ đó các cấu trúc phức tạp (complex structures) được được bảo vệ càng nhiều càng tốt. Để đạt được điều này, khung bao gồm hai giai đoạn:

1.Model  inference:  Ở giai đoạn này, yêu cầu testercung cấp bộ kiểm thử phát triển bằng thủ công như một sự khởi đầu. Nó suy luận các luật ngữ pháp từ các test case trong bộ này và thu thập một tập hợp các cấu trúc ngôn ngữ được trích dẫn từ các test case. Ở giai đoan tiếp theo, nó sử dụng như một khối cơ bản để sinh ra các test case.

2.Grammar-aware  mutation:  Giai đoạn này tạo ra dữ liệu kiểm thử mới bằng cách áp dụng các đột biến với các test case hiện có. Lúc này, nó sẽ chọn một phân đoạn chuỗi ở một test case và thay thế nó bằng một phân đoạn khác từ các khối xây dựng, đại diện cho các thành phần ngữ pháp giống như một sự thay thế được, nhưng có một cấu trúc khác nhau. Hoạt động này được lặp đi lặp lại một cách hệ thống để tạo ra một tập hợp lớn các test case. với sự đa dạng về cấu trúc phong phú hơn so với các bộ kiểm thử thủ công ban đầu.

Ví dụ, chúng ta cần kiểm thử một chương trình tính toán. Chương trình này là một biểu thức số học được xem như là đầu vào của nó, mà cú pháp được mô tả bởi các ngữ pháp BNF sau đây:

expr→  expr+term|expr-term|term

term→  term* factor|term/factor|factor

factor→DIGIT|(expr)

Ngoài ra, giả sử rằng máy tính đã đi kèm với một bộ kiểm tra của hai biểu thức: 2-4 * 5 và (1 + 8) / 3. Tập hợp của các test case sẽđược gọi là hạt giống. Giai đoạnđầu tiên lược đồ phát sinh dữ liệu là mô hìnhsuy luận (model inference). Trong giai đoạn này, chúng ta hãy bắt đầu bằng việc xây dựng một phân tích cú pháp cho ngôn ngữ đích, đó là một phân tích cú pháp cho các biểu thức số học. Sau đó, áp dụng các phân tích cú pháp để tập hạt giống và có được một cây phân tích cho từng test case, nhưđược thể hiện trong hình 2.5.Trong hình này, các núttròn đại diện cho thuộc đầu cuối và được dán nhãn bằng chữ đầu tiên của tên biểu tượng, trong khi các nút vuông cho thiết bị đầu cuối và được dán nhãn với văn bản của tokentương ứng.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a.      Cây phân tích với “ 2-4*5”       b. Cây phân tích với “ (1+8)/3”                

Hình 2.6: Cây phân tích chotest case ở tậphạt giống

 

Từ hình 2.6, một quan sát đơn giản có thể được thực hiện mà một cây phân tích không chỉ là một đại diện cấu trúc của chuỗi đầu vào; đúng hơn, nó cũng mã hóa một phần thông tin về ngữ pháp của ngôn ngữ đích. Hãylấy node biểu thị bằng cách gọira 1 trong hình 25 (a) đểví dụ. Các dữ kiện sau đây về văn phạmmục tiêuGcó thể được suy ra từ các cấu trúc cây của nodeđó:

1)  Gcóđầu cuối term và factor.

2)  Gcó luật  term→term*factor.

3)  Sau 1 loạt bước dẫn xuất bắt đầu từ term

→term* factor,term  kết thúc tạo ra 1 phân đoạn chuỗi 4∗5.

Để có đượcmột bức tranh hoàn chỉnh hơn về ngữ pháp tổng thể, chúng tôi đi qua hai cây phân tích cú pháp trong hình 2.6và lặp lạisuy luận như mô tả ở trên cho mỗi nút mà được thăm.

Bảng 2.3tóm tắt các cấu trúc ngữ pháp đó được suy ra trong quá trình này. Cột đầu tiên liệt kê các ký hiệu nonterminal; cho mỗi hạng tử trong chúng, cột thứ hai cho các quy tắc ngữ pháp mà có thể được sử dụng để mở rộng biểu tượng đó, và cột thứ 3 danh sách các phân đoạn chuỗi mà là dẫn xuất theo các luật.

Bây giờ chúng ta có thể chuyển sang giai đoạn thứ hai, mà chúng tôi gọi là ngữ pháp nhậnthức đột biến(grammar-awaremutation). Trong giai đoạn này, chúng tôi sử dụng các thành phần ngữ pháp và danh sách các chuối phân đoạn liệt kê trong.Bảng 2.3tổ chức lại cấu trúc của các test case đã có để kiểm tra dữ liệu phức tạp hơn có thể được tạo ra. Lưu ý trong bảng 2.3rằng đối với một số nonterminal, nhiều phân đoạn chuỗi có thể được bắt nguồn bằng cách áp dụng các luật ngữ pháp khác nhau để biểu tượng đó. Chúng tasẽ đề cập tới những phân đoạn chuỗi như cú pháp tương thích, có nghĩa là nếu chúng ta thay thế một sự xuất hiện của một số đoạn trong một test case với một phân đoạn mà có nguồn gốc từ cùng một nonterminal, chuỗi kết quả là vẫn còn chính xác trong cú pháp. Ví dụ, hãy xem xét các nút trong hình 2.6được chỉ định bởi lời gọi1 và 2. Cả hai nútđại diện nonterminal term và  mả lấy được 4 * 5và (1 + 8) tương ứng. Do đó, hai phân đoạn là cú pháp tương thích, và chúng tôi có thể thay thế 4 * 5 trong 2-4 * 5 với phân đoạn  (1 + 8) để có được một test case mới 2 - (1 + 8).

Test case nàylà đảm bảo được đúng cú pháp, trong khi khác nhau trong cấu trúc từ trường hợp thử nghiệm hiện có.

Bảng 2.3Các cấu trúc văn phạm suy dẫn từ cây phân tích

 

Nonterminal	GrammarRule	StringFragment
Expr	expr→  expr+term expr→  expr-term expr→  term	1+8 2−4∗5 2,(1+8)/3,1
Term	term→  term* factor term→  term/factor term→  factor	4∗ 5 (1+8)/3 2,4,(1+8),1,8
Factor	factor→  DIGIT factor   (expr)	2,4,5,1,8,3 (1+8)

 

Trên đây chỉ là ví dụ đơn giản, trong thực tế điều này được thực hiện một cách có hệ thống hơn: Vớimỗinodetrên câyphân tích cú pháp, các cây con gốc được thay thếbởi các phân đoạn chuỗi cú pháptương thích của nó, với mỗi đột biến sinh ra mộtchuỗi kiểm thử mới. Những test case mớitạo ra được sau đó được các thao tác tương tự để có được các test case bổ sungvới các cấu trúc phức tạp hơn. Vòng lặp này có thể được tiếp tục cho một số tùy ý các bước lặp tùy thuộc vào nguồn lựckiểm thử.

Thuật toán

Chúng ta có thể tóm tắt các thuật toán thực hiện trongBlendFuzz để phát sinh đầu vào kiểm thử ngữ pháp như sau:

Định nghĩa:  Một chuỗinguồn DS(derivationsequence)là một chuỗicủa các bộ mà có dạng (r, c) trong đó r là một quy tắc ngữ pháp và c là một số nguyên. Hơn nữa, một chuỗi dẫn xuất luôn gắn liền với một nodetrongmột số cây phân tích cú pháp. Đối với một nodecâyphân tích cú pháp mà đại diện cho một biểu tượng thiết bị đầu cuối, chuỗi dẫn xuất của nó là một chuỗi rỗng []; nếu không, cho một nodenonterminaln với các nodekconc1,c2,...,ck ,  trình tự nguồn gốc cho n là đệ quy,định nghĩa là:

DSn=[(rn ,count)]+DSc1+DSc2+...+DSck

Ở đây, “+“ là viết tắt củachuỗi nối, rn làcác quy tắc ngữ pháp được sử dụng tại nút n và số lượng được định nghĩa là:           count =

Nhưmột ví dụ, xem xét các nút chỉ định bởi lời gọi 1 ở hình2.7(a). Chuỗi dẫn xuất của nó được mô tả tronghình 2.7(c) [(T →T∗F,3)(T→F,1)(F→ DIGIT,0)(F→DIIT,0)].

 

 

Hình 2.7:  Sơ đồ quan hệ giữa (a) Cây phân tích, (b)  Phân đoạn chuỗi,(c) chuỗi gốc

 

Thuật toánở giai đoạn này được mô tả như sau [24]:

Algorithm:Grammar-awaremutation

Input: ds, index

Output: TEST CASE

begin

fori=indextods.length()do

begin

forking_point =ds[i];

rule = forking_point.r;

nonterminal =rule.left hand side

foreachgrammarrulerassociatedwith nonterminal  do

begin

ifr=rulethen continue;

   ds    =randomlychooseaderivation sequencefromthoseassociatedwithr;

new  ds=dswithtuplesatrange

           [i,i+forking_point.c]  replacedbytuples inds ;

new  test_case  =new  ds.tostring();

TEST_CASES= TEST_CASES∪ {new  testcase};

grammar_aware_mutate(new  ds,i+1);

         end

     end

end