Cải tiến công cụ sinh dữ liệu thử Java PathFinder bởi tối ưu các ràng buộc

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

22
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Cải tiến công cụ sinh dữ liệu thử Java PathFinder bởi tối ưu các ràng buộc đề xuất việc áp dụng thuật toán tối ưu các ràng buộc - biểu diễn các lộ trình thực thi mã nguồn, nhằm giảm thời gian thực thi nhưng vẫn đảm bảo hiệu quả bao phủ. Giải pháp cải tiến được thử nghiệm trên tập các chương trình Java khác nhau và cho kết quả rất khả quan.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cải tiến công cụ sinh dữ liệu thử Java PathFinder bởi tối ưu các ràng buộc

104 Lê Thị Mỹ Hạnh, Trần Hoàng Dũng, Nguyễn Thanh Bình CẢI TIẾN CÔNG CỤ SINH DỮ LIỆU THỬ JAVA PATHFINDER BỞI TỐI ƯU CÁC RÀNG BUỘC IMPROVING THE JAVA PATHFINDER TOOL FOR GENERATING TEST DATA BY OPTIMIZING CONSTRAINTS Lê Thị Mỹ Hạnh1, Trần Hoàng Dũng2, Nguyễn Thanh Bình1 1 Trường Đại học Bách khoa, Đại học Đà Nẵng; ltmhanh@dut.udn.vn, ntbinh@dut.udn.vn 2 Trường Cao đẳng Lương thực - Thực phẩm; dungdnt@gmail.com Tóm tắt - Sinh dữ liệu thử là một trong các giai đoạn quan trọng Abstract - Test data generation is one of the most important and và quyết định trong kiểm thử phần mềm. Các kỹ thuật sinh dữ liệu crucial phases in software testing. Structural test data generation thử cấu trúc dựa trên mã nguồn để tạo ra dữ liệu thử nhằm phát techniques are based on source code to create test data, which hiện lỗi của người lập trình. Kỹ thuật sinh dữ liệu thử sử dụng thực can uncover programmer's faults. A test data generation technique thi ký hiệu được cài đặt trong công cụ Java PathFinder để sinh dữ using symbolic execution is implemented in the Java PathFinder liệu thử cho các chương trình Java. Tuy nhiên, hiệu năng công cụ tool to generate test data for Java programs. However, Java Java PathFinder còn hạn chế, đó là thời gian thực thi khá lớn. PathFinder has a performance limitation: execution time is quite Trong bài báo này, chúng tôi đề xuất việc áp dụng thuật toán tối ưu big. In this paper, we propose applying an optimization algorithm các ràng buộc - biểu diễn các lộ trình thực thi mã nguồn, nhằm for constraints - representing execution paths in programs - in order giảm thời gian thực thi nhưng vẫn đảm bảo hiệu quả bao phủ. Giải to reduce the execution time but ensure the coverage pháp cải tiến được thử nghiệm trên tập các chương trình Java khác effectiveness. The experiment on different Java programs shows a nhau và cho kết quả rất khả quan. promising result of the proposed solution. Từ khóa - kiểm thử; sinh dữ liệu thử; thực thi ký hiệu; Java Key words - testing; test data generation; symbolic execution; PathFinder; tối ưu ràng buộc Java PathFinder; constraint optimization 1. Đặt vấn đề Mục tiêu quan trọng của thực thi ký hiệu trong kiểm thử Với sự phát triển nhanh chóng của công nghệ thông tin phần mềm là để khám phá càng nhiều đường dẫn thực thi trong vài thập kỷ gần đây, công nghiệp phần mềm đang dần chương trình khác nhau trong một khoảng thời gian nhất trở thành ngành mũi nhọn ở hầu hết các quốc gia trên thế định; và với mỗi đường dẫn (1) tạo ra một tập hợp các giá giới, kéo theo là sự mở rộng về quy mô cũng như chất trị đầu vào cụ thể để thực thi đường dẫn đó, và (2) kiểm tra lượng của các sản phẩm phần mềm. Tuy nhiên, một phần sự hiện diện của các loại lỗi khác nhau như lỗi chưa bắt mềm không bao giờ là hoàn hảo, và các vấn đề về hỏng hóc ngoại lệ, lỗ hổng bảo mật, và thất lạc bộ nhớ... Một trong phần mềm luôn là một nguy cơ lớn; những lỗi phần mềm những thế mạnh chính của thực thi ký hiệu là khả năng sinh dù là nhỏ nhất cũng có thể gây ra thiệt hại và ảnh hưởng các dữ liệu thử cụ thể, cho phép tạo ra các bộ dữ liệu thử nghiêm trọng. Do đó hoạt động kiểm thử phần mềm được có độ bao phủ cao. Hơn nữa, theo quan điểm tìm kiếm lỗi, đặt ra như một nhu cầu cấp thiết, giúp ngăn chặn và khắc kỹ thuật này cung cấp cho các nhà phát triển các dữ liệu phục các lỗi tiềm ẩn bên trong phần mềm chưa được phát đầu vào cụ thể gây ra lỗi, có thể được sử dụng để xác nhận hiện. Nhằm giảm chi phí cho việc kiểm thử thủ công khi và gỡ rối các lỗi độc lập với các công cụ thực thi ký hiệu các phần mềm đang dần trở nên phức tạp hơn, đồng thời sinh ra nó. tăng tính hiệu quả và tin cậy của quá trình kiểm thử, hệ Đã có nhiều công trình nghiên cứu áp dụng phương thống kiểm thử phần mềm dựa trên cơ chế sinh dữ liệu thử pháp thực thi ký hiệu để sinh dữ liệu thử cho các ngôn ngữ tự động đang được quan tâm và tập trung nghiên cứu. lập trình như .NET, C, Java và cho ra đời nhiều công cụ Nhiều cách tiếp cận cho việc sinh dữ liệu thử tự động kiểm thử như CREST, jCUTE, KLEE, Java PathFinder... đã được đề xuất, trong đó phân tích tĩnh dựa trên thực thi Trong phạm vi bài báo này, chúng tôi triển khai cách ký hiệu (SE - Symbolic Execution) [1, 2] được xem là một tiếp cận sinh dữ liệu thử dựa trên thực thi ký hiệu cho ngôn phương pháp hiệu quả, có thể phát hiện các lỗi phức tạp ngữ Java; đây là một ngôn ngữ lập trình đa nền tảng và có mà các phương pháp thông thường tốn nhiều công sức để phạm vi sử dụng rất lớn trong ngành công nghiệp phần xử lý. Ý tưởng của thực thi ký hiệu là sử dụng các giá trị mềm. Ngoài việc áp dụng kỹ thuật thực thi ký hiệu và giải tượng trưng, thay vì phân tích chương trình với các giá trị ràng buộc sử dụng công cụ tạo dữ liệu thử tự động, cụ thể đầu vào cụ thể. Như vậy, kết quả của một phương thức là Java PathFinder (JPF) [3], chúng tôi cũng sẽ đề xuất cải được biểu diễn như một hàm số với tham số là các giá trị tiến kỹ thuật tối ưu các ràng buộc biểu diễn tập các lộ trình. đầu vào tượng trưng đó. Bằng cách thực thi với đầu vào tượng trưng thay vì vét cạn các giá trị cụ thể của đầu vào, Bố cục của bài báo như sau: Tổng quan về phương pháp phương pháp này cung cấp một cách thức để làm giảm sinh dữ liệu thử dựa trên thực thi ký hiệu được giới thiệu ở bớt vấn đề bùng nổ trạng thái. Bên cạnh đó, thực thi kí Mục 2; Mục 3 giới thiệu về công cụ Java PathFinder; Mục 4 hiệu cũng rất được quan tâm trong những năm gần đây trình bày giải pháp tối ưu tập ràng buộc; kết quả thử nghiệm bởi khả năng sinh ra các giá trị đầu vào kiểm thử cao và và đánh giá giải pháp được trình bày ở Mục 5; Mục 6 là tìm lỗi sâu trong các ứng dụng phức tạp. những kết luận và hướng phát triển của giải pháp đề xuất.
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 5(114).2017-Quyển 1 105 2. Sinh dữ liệu thử dựa trên thực thi ký hiệu triển cho việc sinh dữ liệu thử, mà là kiểm chứng hình thức Trong hoạt động kiểm thử phần mềm, các ca kiểm thử và nâng cao hiểu biết của chương trình thông qua gỡ lỗi thường được tạo ra một cách thủ công, gây tốn kém về chi biểu tượng. Tuy nhiên, cách tiếp cận này có rất nhiều vấn phí cũng như thời gian. Thực thi kí hiệu (Symbolic đề [5], bao gồm: 1) Độ phức tạp của biểu thức ký hiệu tăng execution) [4] được biết đến là một kỹ thuật nổi tiếng với nhanh; 2) Xử lý các cấu trúc dữ liệu phức tạp là khó khăn; khả năng tự động sinh những bộ dữ liệu thử có độ phủ cao 3) Các vòng lặp phụ thuộc vào các biến đầu vào nên khó với các tiêu chí kiểm thử, nhằm phát hiện những lỗi sâu để xử lý. trong các hệ thống phần mềm phức tạp. a: X, b: Y PC: true Ý tưởng chính của thực thi ký hiệu là thực thi chương 2 trình với các giá trị ký hiệu, thay vì các giá trị cụ thể của các a: X, b: Y, min: X tham số đầu vào, kết quả là giá trị đầu ra được tính toán bởi 3 PC: true 3 chương trình và được biểu diễn bởi một biểu thức ký hiệu. a: X, b: Y, min: X Ví dụ, đầu ra cho một đoạn mã chương trình như "int sum a: X, b: Y, min: X PC: Y
106 Lê Thị Mỹ Hạnh, Trần Hoàng Dũng, Nguyễn Thanh Bình là hạn chế của công cụ JPF. 5. Kết quả thử nghiệm Vì vậy, trong bài báo này, chúng tôi nghiên cứu giải pháp Chúng tôi tiến hành thử nghiệm công cụ JPF được cải cải tiến công cụ JPF bằng cách tối ưu các ràng buộc biểu diễn tiến trên các chương trình Java khác nhau, với mục đích tập các lộ trình. Chúng tôi đề xuất áp dụng thuật toán [7] để đánh giá độ bao phủ lộ trình của dữ liệu thử được sinh ra, tối ưu các ràng buộc nhằm đảm bảo các yêu cầu sau: cũng như hiệu quả của việc cài đặt thuật toán tối ưu các • Giảm số lượng các ràng buộc đưa vào bộ giải các ràng buộc. ràng buộc nhằm giảm chi phí thời gian tính toán; Danh sách các chương trình Java được sử dụng để thử • Đảm bảo sự bao phủ lộ trình của các dữ liệu thử nghiệm được trình bày trong Bảng 1. được sinh ra. Bảng 1. Danh sách các chương trình Java Thuật toán tối ưu các ràng buộc thực hiện giảm miền Chương trình Mô tả các ràng buộc cần giải quyết bởi việc loại bỏ các ràng buộc Kiểm tra ba số nguyên có tạo nên dựa trên thông tin thực thi ký hiệu động. Thuật toán tối ưu Triangle tam giác đều, cân hay thường. các ràng buộc đã được thử nghiệm và đánh giá hiệu quả tốt [7]. Xếp học lực sinh viên dựa trên RankStudent điểm thi. Thuật toán tối ưu các ràng buộc được trình bày trong Hình 3. Trước hết, thuật toán tìm ràng buộc mục tiêu trong ràng CheckValidColor Kiểm tra bộ ba giá trị màu. buộc lộ trình bởi hàm getTargetConstraint(). Sau đó, các biến CompareTwoNumbers So sánh hai số nguyên. mục tiêu của ràng buộc lộ trình được xác định bởi SwapBiggerNumber Hoán đổi số lớn hơn. getSymVars(). Đối với mỗi biến mục tiêu, xác định các ràng buộc có phụ thuộc trực tiếp và gián tiếp với biến mục tiêu đó Kiểm tra một số nguyên thuộc các CheckNumber bởi các hàm tương ứngformGroupsofX() và khoảng cho trước. getDependencies(); trong tập các phụ thuộc, xác định phần tử CheckBit Kiểm tra giá trị ba bít. có số phụ thuộc nhỏ nhất và phần tử có số phụ thuộc lớn nhất; QuadraticEqualtion Giải phương trình bậc hai. đối với mỗi phẩn tử được chọn, các biến được thay thế bởi giá trị cụ thể tạo ra ràng buộc mới; và ràng buộc mới được gửi tới Fibonacci Tính số Fibonacci. bộ giải ràng buộc. Nếu bộ giải cho kết quả thỏa mãn (sat), thì GreatestCommonDivisor Tìm ước số chung lớn nhất. vòng lặp dừng và cho kết quả dữ liệu thử; ngược lại, nếu kết Sum Tính tổng n-1 số tự nhiên đầu tiên. quả không thỏa mãn (unsat), thì vòng lặp tiếp tục đối với các biến mục tiêu khác. Factorial Tính giai thừa. Input: Ràng buộc lộ trình (PC), Giá trị biến ký hiệu, Bộ giải Chúng tôi phân tích mã nguồn các chương trình Java để ràng buộc (solver) xác định số lượng lộ trình cũng như dữ liệu thử được sinh Ouput: result = sat, unsat, unknown ra để thực thi lộ trình tương ứng. Đối với vòng lặp (gồm Constraint cur = getTargetConstraint(index, pc) các chương trình Fibonacci, GreatestCommonDivisor, List targetsymlist = getSymVars(cur) Sum, Factorial), chúng tôi tính một lộ trình đi qua vòng lặp result = unknown và một lộ trình không đi qua vòng lặp. Công cụ sinh ra số for i = 1 to length(targetsymlist) do groups[] = formGroupsofX(i, targetsymlist) dữ liệu phần lớn bằng hoặc nhiều hơn số lộ trình (Bảng 2). List dependencies = [] Đối với vòng lặp, có dữ liệu không thực thi vòng lặp, một for a = 0 to length(groups) do số dữ liệu thực thi vòng lặp một lần và một số dữ liệu thực dependencies[a] = getDependencies(groups[a], pc) thi vòng lặp nhiều lần. end Kết quả thử nghiệm cho thấy dữ liệu thử sinh ra cho int selectDep[0] = findSmallestDepIndex(dependencies) mỗi chương trình đều thực thi tất cả các lộ trình của chương int selectDep[1] = findLargestDepIndex(dependencies) for b = 0 to length(selectedDep) do trình đó. List grpDep = dependencies[(selectDep[b])] Bảng 2. Thống kê dữ liệu thử được sinh ra List symbolicVars = join(groups(selectDep[b]), grpDep) Chương trình Số lộ trình Số dữ liệu thử newPC = modifyPC(symbolicVars, concreteValues,pc) output = callSolver(solver, newPC) Triangle 9 10 if output = “sat” then RankStudent 4 4 return output CheckValidColor 7 7 end elseif output = “unsat” then CompareTwoNumbers 3 3 result = output SwapBiggerNumber 2 2 end CheckNumber 5 5 end CheckBit 8 5 end QuadraticEqualtion 3 3 Hình 3. Thuật toán tối ưu ràng buộc lộ trình Fibonacci 3 6 Thuật toán được cài đặt tích hợp vào công cụ JPF nhận GreatestCommonDivisor 3 7 đầu vào gồm tập các ràng buộc lộ trình, thực hiện tối ưu Sum 2 6 các ràng buộc lộ trình và sử dụng bộ giải ràng buộc Choco [8] để sinh dữ liệu thử tương ứng. Factorial 2 6
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 5(114).2017-Quyển 1 107 Để đánh giá hiệu quả của thuật toán tối ưu các ràng buộc, Để minh họa rõ hơn, đồ thị trong Hình 4 cho thấy thời chúng tôi thực hiện sinh dữ liệu thử cho các chương trình gian thực thi trung bình sinh dữ liệu thử của các chương Java trên trong hai trường hợp: không cài đặt thuật toán tối trình có vòng lặp giảm 2% và của các chương trình không ưu và có cài đặt thuật toán tối ưu. Bảng 3 trình bày thời gian có vòng lặp giảm 31%. thực thi sinh dữ liệu thử trong hai trường hợp trên cùng máy Như vậy, việc áp dụng tối ưu các ràng buộc trong sinh tính có cấu hình CPU Core i7 và bộ nhớ 4GB RAM. dữ liệu thử dựa trên thực thi ký hiệu cho công cụ Java Bảng 3. So sánh thời gian thực thi PathFinder đảm bảo độ bao phủ lộ trình, nghĩa là khả năng Thời gian thực thi (miliseond) phát hiện lỗi, đồng thời giảm được thời gian thực thi. Chương trình Không cài đặt Có cài đặt thuật 6. Kết luận thuật toán tối ưu toán tối ưu Triangle 833 495 Sinh dữ liệu thử đảm bảo độ bao phủ mã nguồn đóng vai trò quan trọng trong việc phát hiện lỗi của lập trình viên. RankStudent 152 111 Trong bài báo này, chúng tôi đã tìm hiểu và phân tích hạn CheckValidColor 277 170 chế của công cụ sinh dữ liệu Java PathFinder dựa trên thực CompareTwoNumbers 112 76 thi ký hiệu cho mã nguồn Java.Từ đó, chúng tôi đã đề xuất SwapBiggerNumber 116 87 áp dụng thuật toán tối ưu các ràng buộc và tích hợp vào CheckNumber 223 135 công cụ Java PathFinder nhằm cải tiến thời gian sinh dữ CheckBit 213 142 liệu thử. Kết quả thử nghiệm cho thấy, thời gian thực thi QuadraticEqualtion 603 531 khi áp dụng thuật toán tối ưu các ràng buộc đều giảm nhưng vẫn đảm bảo độ bao phủ các lộ trình. Fibonacci 625 607 GreatestCommonDivisor 633 618 Trong tương lai, chúng tôi sẽ tiếp tục nghiên cứu việc giảm thời gian thực thi sinh dữ liệu thử đối với chương Sum 599 584 trình có vòng lặp và hướng đến việc áp dụng các thuật Factorial 590 587 toán học máy để tiếp tục cải tiến sinh dữ liệu dựa trên Từ Bảng 3, chúng ta có thể nhận thấy thời gian thực thi khi mã nguồn. áp dụng thuật toán tối ưu các ràng buộc đều giảm. Tuy nhiên, thời gian thực thi giảm rất đáng kể đối với chương trình không TÀI LIỆU THAM KHẢO sử dụng vòng lặp, ngược lại, đối với các chương trình có sử [1] Cristian Cadar and Koushik Sen, “Symbolic execution for software dụng vòng lặp (Fibonacci, GreatestCommonDivisor, Sum, testing: three decades later”, Commununications of the ACM 56, Factorial) thì thời gian thực thi giảm khá ít. Đây cũng chính là February. 2013, pp. 82-90. hạn chế mà chúng tôi hướng đến giải quyết trong thời gian đến. [2] Cristian Cadar, Patrice Godefroid, Sarfraz Khurshid, Corina Pasareanu, Koushik Sen, Nikolai Tillmann, Willem Visser, Không thuật toán tối ưu Có thuật toán tối ưu Symbolic Execution for Software Testing in Practice – Preliminary Assessment, Proceedings of the 33rd International Conference on 900 Software Engineering, 2011. 800 [3] W. Visser, K. Havelund, G. Brat, S.-J. Park, and F. Lerda, “Model Checking Programs”, Automated Software Engineering Journal, 700 10(2), April. 2003. 600 [4] J. C. King, Symbolic execution and program testing, Communication ACM, 19(7), 1976, pp. 385–394. 500 [5] D. Coward, Symbolic execution and testing, Inf. Softw. Technol., 400 33(1), 1991, pp. 53–64. 300 [6] Corina S. Pǎsǎreanu, Peter C. Mehlitz, David H. Bushnell, Karen Gundy-Burlet, Michael Lowry, Suzette Person, and Mark Pape, 200 Combining unit-level symbolic execution and system-level concrete execution for testing nasa software, In Proceedings of 100 the 2008 International Symposium on Software testing and analysis (ISSTA '08), ACM, New York, NY, USA, 2008, pp. 0 15-26. [7] Ikpeme Erete and Alessandro Orso, Optimizing Constraint Solving to Better Support Symbolic Execution, Proceedings of the 2012 IEEE Fourth International Conference on Software Testing, Verification and Validation, 2012. [8] http://www.choco-solver.org. [9] Ngô Pô Na, Xây dựng công cụ sinh dữ liệu thử tự động cho chương Hình 4. Đồ thị so sánh thời gian thực thi trình Java, Luận văn Thạc sỹ, Đại học Đà Nẵng, 2017. (BBT nhận bài: 20/03/2017, hoàn tất thủ tục phản biện: 25/04/2017)