Tài liệu Dự đoán lỗi phần mềm dựa trên độ đo mã nguồn sử dụng kỹ thuật học kết hợp

1 MỤC LỤC MỤC LỤC ............................................................................................................................ 1 DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT VÀ CỤM TỪ ......................................... 3 DANH MỤC CÁC BẢNG ................................................................................................... 6 DANH MỤC CÁC HÌNH VÀ ĐỒ THỊ ............................................................................... 7 TỔNG QUAN....................................................................................................................... 8 1. Đặt vấn đề ...................................................................................................................... 8 2. Mục tiêu và nội dung nghiên cứu .................................................................................. 9 3. Đối tượng và phạm vi nghiên cứu.................................................................................. 9 4. Phương pháp nghiên cứu ............................................................................................... 9 5. Ý nghĩa khoa học và thực tiễn........................................................................................ 9 CHƯƠNG I: ĐỘ ĐO MÃ NGUỒN VÀ BÀI TOÁN DỰ ĐOÁN LỖI ............................. 11 1.1 Bài toán dự đoán lỗi .............................................................................................. 11 1.2 Quản lý lỗi phần mềm ........................................................................................... 11 1.3 Hướng tiếp cận dự đoán lỗi phần mềm. ................................................................ 12 1.4 Độ đo mã nguồn .................................................................................................... 13 CHƯƠNG II: CÁC KỸ THUẬT HỌC MÁY .................................................................... 18 2.1 Học có giám sát .................................................................................................... 19 2.1 Học không có giám sát .......................................................................................... 21 2.2 Các yếu tố cần xem xét khi lựa chọn và áp dụng thuật toán học máy .................. 23 2.3 Thuật toán Cây quyết định .................................................................................... 24 CHƯƠNG III: DỰ ĐOÁN LỖI PHẦN MỀM DỰA TRÊN HỌC MÁY .......................... 29 3.1 SDP dựa trên học máy .......................................................................................... 29 3.2 Tiền xử lý dữ liệu .................................................................................................. 29 3.3 Kỹ thuật Ensemble learning .................................................................................. 30 3.4 Các thuật toán Ensembles learning cho SDP ........................................................ 31 3.5 Đánh giá phương pháp dự đoán (Prediction Method evaluation) ......................... 39 CHƯƠNG IV: ĐÁNH GIÁ THỰC NGHIỆM CÁC PHƯƠNG PHÁP HỌC KẾT HỢP . 43 4.1 Tập dữ liệu dự đoán lỗi phần mềm ....................................................................... 43 4.2 Xây dựng mô hình................................................................................................. 43 4.3 Tiêu chí đánh giá hiệu suất số liệu phần mềm ...................................................... 45 4.4 Kết quả thực nghiệm ............................................................................................. 45 4.5 Xây dựng website hỗ trợ dự đoán lỗi .................................................................... 51 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ......................................................................... 53 TÀI LIỆU THAM KHẢO .................................................................................................. 56 2 DỰ ĐOÁN LỖI PHẦN MỀM DỰA TRÊN ĐỘ ĐO MÃ NGUỒN SỬ DỤNG KỸ THUẬT HỌC KẾT HỢP Học viên: Nguyễn Mậu Hải, Chuyên ngành: Khoa học máy tính Mã số: 8480101, Khóa: K35 – KHMT, Trường Đại học Bách khoa - ĐHĐN Tóm tắt – Lỗi phần mềm gây ảnh hưởng đến thời gian, chất lượng, chi phí, công sức và sự lãng phí các nguồn lực. Phát hiện lỗi trong giai đoạn đầu của quá trình phát triển phần mềm để khắc phục và sữa chữa sớm là một trong những đòi hỏi để cải thiện chất lượng, làm tăng hiệu quả phát triển phần mềm. Có nhiều nghiên cứu, áp dụng các kỹ thuật Học máy để xây dựng công cụ dự đoán lỗi nhưng vẫn còn nhiều vấn đề hạn chế hoặc có thể chỉ phát huy ở một khía cạnh nào đó trong kỹ thuật phát triển phần mềm. Luận án này cũng nhìn nhận tổng quan trong lĩnh vực quản lý lỗi phần mềm và dự đoán lỗi, tìm hiểu các thuật toán Học máy, đồng thời áp dụng kỹ thuật học kết hợp (ensemble learning) để dự đoán, phát hiện lỗi giúp khắc phục sớm nhằm cải thiện chất lượng phần mềm. Các kỹ thuật học máy liên quan đến dự đoán lỗi được giới thiệu, đặc biệt là học có giám sát. Các thuật toán Dicision Tree, Random Forest, Boosting, Bagging, AdaBoost được nghiên cứu để áp dụng. Các kỹ thuật học kết hợp được triển khai bằng các mô hình. Kỹ thuật Stacking được xây dựng dựa trên các mô hình emsembles như bộ học cơ sở và sau đó sử dụng Meta-Classifier tổng hợp kết quả và đưa ra kết quả cuối cùng. Việc đánh giá mô hình và độ tin cậy của thuật toán được thực hiện dựa trên các phép đo F1, ROC, AUC và thời gian huấn luyện. Với những kết quả trên, tác giả hướng thử nghiệm và tối ưu hóa, tiến đến xây dựng một công cụ dự đoán lỗi để áp dụng trong thực tế sản xuất phần mềm của doanh nghiệp. Từ khóa – Dự đoán lỗi phần mềm, học kết hợp, độ đo mã nguồn, số liệu phần mềm, kiểm thử phần mềm. SOFTWARE DEFECT PREDICTION BASED ON THE SOURCE CODE MEASUREMENT METHOD USING THE ENSEMBLES LEARNING Abstract - Software defect affect time, quality, cost, effort and waste of resources. Detecting errors in the early stages of software development to repair and fix early is one of the requirements to improve quality, increase efficiency software development. There are many studies, using machine learning techniques to build software defect prediction tools, but there are still many problems or can be only promote in a certain aspect in software development techniques. This thesis also provides an overview in the fields of software error management and defects prediction, understanding machine learning algorithms and applying techniques of ensemble learning to predict and detect errors. fix early to improve software quality. Machine learning techniques related to software defects prediction are introduced, especially supervised learning. Decision Tree, Random Forest, Boosting, Bagging, AdaBoost algorithms are studied to apply. Ensemble learning techniques are deployed by models. The Stacking technique is built upon the emsembles models as the base learner and then uses the Meta-Classifier to summarize the results to produce the result final. The evaluation of the model and the reliability of the algorithm is done based on F1, ROC, AUC and training time measurements. With the above results, the author directs testing and optimization, proceeding to build an error prediction tool to apply in actual software production of enterprises. Key words – Software defect prediction; ensembles learning; source code measurement, software metrics; software testing. 3 DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT VÀ CỤM TỪ Tiếng Anh Tiếng Việt Analysis of variance Phân tích phương sai Bar chart Biểu đồ thanh Binomial distribution Phân phối nhị phân Box plot Biểu đồ hình hộp Categorical variable Biến thứ bậc Clock chart Biểu đồ đồng hồ Coefficient of correlation Hệ số tương quan Coefficient of determination Hệ số xác định bội Coefficient of heterogeneity Hệ số bất đồng nhất Combination Tổ hợp Confidence interval Khoảng tin cậy Continuous variable Biến liên tục Correlation Tương quan Covariance Hợp biến Cross Project Defect Prediction - CPDP Dự đoán lỗi liên dự án Cross-over experiment Thí nghiệm giao chéo Cumulative probability distribution Hàm phân phối tích lũy Data mining Khai phá dữ liệu Decision Tree Cây quyết định Degree of freedom Bậc tự do Determinant Định thức Discrete variable Biến rời rạc Dot chart Biểu đồ điểm DS Cây quyết định Ensembles Learning Học kết hợp Estimate Ước số Estimator Bộ ước tính Factorial analysis of variance Phân tích phương sai cho thí nghiệm giai Feature Đặc trưng 4 Fixed effects Ảnh hưởng bất biến Forcement Learning Học tăng cường Frequency Tần số Function Hàm Heterogeneity Không đồng nhất Histogram Biểu đồ tần số Homogeneity Đồng nhất Hypothesis test Kiểm định giả thiết Inverse matrix Ma trận nghịch đảo K-NN K - Hàng xóm gần nhất Latin square experiment Thí nghiệm hình vuông Latin Least squares method Phương pháp bình phương nhỏ nhất Linear Logistic regression analysis Phân tích hồi qui tuyến tính logistic Linear regression analysis Phân tích hồi qui tuyến tính Machine Learning Học máy Matrix Ma trận Maximum likelihood method Phương pháp hợp lí cực đại Mean Số trung bình Median Số trung vị Meta-analysis Phân tích tổng hợp Missing value Giá trị không Model Mô hình Multiple linear regression analysis Phân tích hồi qui tuyến tính đa biến NB Naïve Bayer Normal distribution Phân phối chuẩn Object Đối tượng Parameter Thông số Permutation Hoán vị Pie chart Biểu đồ hình tròn Poisson distribution Phân phối Poisson Polynomial regression Hồi qui đa thức 5 Probability Xác suất Probability density distribution Hàm mật độ xác suất P-value Trị số P Quantile Hàm định bậc Random effects Ảnh hưởng ngẫu nhiên Random Forest Rừng ngẫu nhiên Random variable Biến ngẫu nhiên Relative risk Tỉ số nguy cơ tương đối Repeated measure experiment Thí nghiệm tái đo lường Residual Phần dư Residual mean square Trung bình bình phương phần dư Residual sum of squares Tổng bình phương phần dư Scalar matrix Ma trận vô hướng Scatter plot Biểu đồ tán xạ Semi-Supervised Learning Học bán giám sát Significance Có ý nghĩa thống kê Simulation Mô phỏng Software Defect Prediction Dự đoán lỗi phần mềm Standard deviation Độ lệch chuẩn Standard error Sai số chuẩn Standardized normal distribution Phân phối chuẩn chuẩn hóa Supervised Learing Học có giám sát Survival analysis Phân tích biến cố SVM Máy véc tơ hỗ trợ Traposed matrix Ma trận chuyển vị Unsupervised Learning Học không có giám sát Variable Biến (biến số) Variance Phương sai Weight Trọng số Weighted mean Trung bình trọng số With-in Project Defect Prediction - WPDP Dự đoán lỗi bên trong dự án 6 DANH MỤC CÁC BẢNG Bảng 1. Số liệu dùng để đo lường các đặc trưng lỗi phần mềm......................................... 15 Bảng 2. Kết quả các thuật toán học kết hợp và Cây quyết định. ........................................ 46 Bảng 3. Kết quả F1 của các thuật toán Stacking ................................................................ 47 Bảng 4. Kết quả AUC của các thuật toán Stacking ............................................................ 48 Bảng 5. Kết quả thời gian huấn luyện của các thuật toán Stacking ................................... 49 7 DANH MỤC CÁC HÌNH VÀ ĐỒ THỊ Hình 1. Các nhóm tham số khác nhau về độ đo trong công nghệ phần mềm .................... 13 Hình 2. Thuật toán học máy ............................................................................................... 18 Hình 3. Cây thể hiện sự sống trên tàu Titanic .................................................................... 25 Hình 4. Phân loại Bagging trên tập dữ liệu Iris với hai bộ ước tính cơ sở: DS và k-NN... 33 Hình 5. Các cây trong Rừng ngẫu nhiên ............................................................................ 34 Hình 6. AdaBoost sử dụng sô bộ ước tính cơ sở khác nhau. ............................................. 36 Hình 7. Stacking sử dụng nhiều loại bộ học khác nhau. .................................................... 38 Hình 8. Mô tả trực quan đường cong ROC ........................................................................ 41 Hình 9. Mô hình Boosting cho thuật toán AdaBoost và Gradient Boosting. ..................... 44 Hình 10. Mô hình Bagging cho thuật toán Random Forest và Bagging. ........................... 44 Hình 11. Mô hình stacking ................................................................................................. 45 Hình 12. Đường cong ROC ứng với từng thuật toán học kết hợp. .................................... 50 Hình 13. Giao diện ứng dụng web hỗ trợ dự đoán lỗi ........................................................ 51 Hình 14. Báo cáo kết quả dự đoán lỗi phần mềm .............................................................. 52 8 TỔNG QUAN 1. Đặt vấn đề Dự đoán lỗi phần mềm (Software Defect Prediction – SDP) đóng một vai trò quan trọng trong hoạt động nghiên cứu lĩnh vực kỹ thuật phần mềm. Lỗi phần mềm là một lỗi, lỗ hổng, sai sót, sự cố hoặc sai lầm được tạo ra trong phần mềm gây ra một kết quả sai khác ngoài mong đợi. Các yếu tố liên quan lỗi phần mềm không được phát hiện trong giai đoạn đầu của việc phát triển phần mềm gây nguy cơ ảnh hưởng lớn đến thời gian, chất lượng, chi phí, công sức và sự lãng phí các nguồn lực. Lỗi có thể xảy ra trong bất kỳ giai đoạn nào của quá trình phát triển phần mềm. Các nhà sản xuất phần mềm luôn cố gắng tập trung vào chất lượng phần mềm, đặc biệt là trong giai đoạn đầu của quá trình phát triển. Mục tiêu chính là để xác định và sửa chữa các lỗi trong giai đoạn đầu của vòng đời phát triển phần mềm (SDLC). Để cải thiện chất lượng của phần mềm, các kỹ thuật Học máy đã được áp dụng để xây dựng dự đoán về lỗi của các thành phần phần mềm bằng việc khai phá dữ liệu trong quá khứ của phần mềm, các thành phần và các vấn đề liên quan đến lỗi của chúng. Các dự án phát triển phần mềm đang ngày càng lớn, phức tạp, tốn kém và trở nên khó dự đoán. Một trong nhiều vấn đề cần quan tâm là các dự án phần mềm khi gia tăng quy mô và độ phức tạp, nó làm tăng khả năng rủi ro và do vậy ảnh hưởng đến chi phí hoặc tiến độ của chính các dự án. Việc phát hiện các lỗi tiềm ẩn trong phần mềm có ý nghĩa rất lớn, giúp cải thiện thời gian, giảm chi phí và nâng cao năng lực cạnh tranh trong phát triển phần mềm. Trường hợp không kiểm soát tốt lỗi, doanh nghiệp buộc phải tăng cường các khả năng khác, bao gồm: đánh giá mã tập trung, tăng cường kiểm tra đơn vị mã nguồn và tăng khả năng giám sát nhân lực phát triển ở nhiều cấp độ. Xuất phát từ việc nhìn nhận, các nhà phát triển phần mềm rất mong đợi và có nhu cầu về công cụ dự đoán các lỗi tốt hơn. Bằng việc xác định xu hướng, tôi mong muốn đi sâu tìm hiểu các vấn đề này thông qua phân tích, đánh giá thuật toán và các mô hình. Theo hiểu biết của tôi, cho đến nay vẫn chưa có nghiên cứu nào đáp ứng tốt mục tiêu dự đoán chính xác số lượng lỗi phần mềm với thời gian phù hợp. Mặc dù nhiều nghiên cứu gần đây đã chứng minh kết quả đầy hứa hẹn của Học máy khi sử dụng để dự đoán tỷ lệ lỗi phần mềm dựa trên các phép đo phân tích tình trạng như độ phức tạp của mã nguồn và kích thước mã,… Tuy nhiên về tiêu chuẩn áp dụng cho ngành vẫn còn chậm. Hầu hết các dự án phát triển phần mềm vẫn sử dụng các phương pháp dự đoán lỗi truyền thống, phần lớn tập trung vào mối quan hệ giữa số dòng mã với số lượng lỗi trong một ứng dụng. Trong khi mối tương quan giữa hai phép đo này đã được chứng minh có độ lệch đáng kể và dẫn đến kết quả chưa được đánh giá cao. 9 Rõ ràng, rất cần có một giải pháp mới, hiệu quả hơn nhằm hỗ trợ các nhóm phát triển phần mềm đo lường hiệu quả về chất lượng, điều đó đề cập đến việc cần thiết phải có công cụ dự đoán lỗi phần mềm. 2. Mục tiêu và nội dung nghiên cứu Nghiên cứu, đánh giá các thuật toán học máy và các thuật toán ứng dụng trong dự đoán lỗi phần mềm, tiến tới xây dựng công cụ dự đoán lỗi dựa trên học máy. Để làm được điều đó, tác giả cần có sự hiểu biết sâu về vấn đề này thông qua tìm hiểu một cách thấu đáo lý thuyết và kết hợp thực nghiệm. Nội dung nghiên cứu bao gồm tất cả các vấn đề có liên quan bản chất của lỗi phần mềm, các phương pháp dự đoán lỗi phần mềm hiện tại, kỹ thuật phân tích và xử lý số liệu phần mềm, Nền tảng học máy, các thuật toán học máy và kỹ thuật ensemble learning dùng để dự đoán lỗi phần mềm. 3. Đối tượng và phạm vi nghiên cứu Phạm vi dự đoám lỗi phần mềm khá rộng đòi hỏi sự đầu tư nhiều về nguồn lực và thời gian. Luận văn này đi sâu vào tìm hiểu lý thyết về phân tích dự đoán và lựa chọn dự đoán lỗi trên các file phần mềm được phát triển bằng ngôn ngữ Java. Điều này được thực hiện trong phạm vi nghiên cứu các thuật toán phân tích dự đoán, các mô hình áp dụng, các phương pháp đánh giá các mô hình và nghiên cứu kỹ thuật ensemble dùng để dự đoán lỗi. 4. Phương pháp nghiên cứu Dựa trên lý thuyết về phân tích và thống kê, tác giả tìm hiểu cơ sở lý thuyết về các học máy đối với bài toán dự đoán và tìm hiểu các thuật toán ứng dụng tương ứng dựa trên quy trình kỹ thuật dự đoán lỗi phần mềm. Từ cơ sở lý thuyết đó, tác giả tiến hành lựa chọn xây dựng mô hình dựa trên thuật toán dự đoán lỗi (dựa trên thư viện sklearn) và lập trình ứng dụng bằng ngôn ngữ Python. Kết quả được đánh giá thông qua các phép hiệu suất đo mô hình và độ chính xác dự đoán, đồng thời cũng xét đến thời gian huấn luyện đối với từng mô hình sử dụng kỹ thuật ensembles learning cụ thể. 5. Ý nghĩa khoa học và thực tiễn - Áp dụng lý thuyết phân tích và dự đoán trong các lĩnh vực của đời sống. - Áp dụng kỹ thuật học máy và các thuật toán để dự đoán lỗi phần mềm. - Đóng góp bổ sung kết quả nghiên cứu và thực nghiệm, đóng góp công cụ phân tích sử dụng kỹ thuật học máy và các mô hình thuật toán ứng dụng. - Tạo ra công cụ để giúp các nhà phát triển cải thiện chất lượng phần mềm, kiểm soát tiến trình, giảm thiểu rủi ro và tăng tính khả thi cho các dự án. 10 - Giúp cho các Công ty phần mền kiểm soát tốt nguồn lực, giảm thiểu chỉ phí đầu tư, rút ngắn thời gian, đảm bảo tính cạnh tranh và nâng cao hiệu quả kinh doanh. 6. Cấu trúc luận văn Luận văn được trình bày bao gồm 04 chương, với nội dung cụ thể như sau: Chương 1 trình bày lý thuyết về độ đo mã nguồn và bài toán dự đoán lỗi. Phần này nêu bài toán dự đoán lỗi và phương thức quản lý lỗi phần mềm xuất phát từ hướng tiếp cận dựa trên các tiêu chí độ đo mã nguồn. Chương II trình bày tổng quan về các kỹ thuật học máy, trong đó tập trung vào các kỹ thuật học có giám sát. Từ cơ sở lý thuyết, phần này cũng nêu rõ các yếu tố cần xem xét khi lựa chọn và áp dụng thuật toán học máy để đáp ứng giải quyết vấn đề cụ thể. Thuật toán Cây quyết định là một trong những thuật toán cơ bản cũng được làm rõ để nghiên cứu ứng dụng cho bài toán dự đoán lỗi. Chương III trình bày tổng quan phương pháp dự đoán lỗi phần mềm dựa trên học máy với các vấn đề liên quan đến việc thu thập và xử lý dữ liệu. Dữ liệu dùng trong Luận văn này được lấy từ kho PROMISE (địa chỉ: http://promise.site.uottawa.ca/SERepository), trước khi đưa vào mô hình, tác giả thực hiện công việc tiền xử lý để chuẩn hóa dữ liệu. Các kỹ thuật ensembles learning cũng được xem xét, đặt biệt là các biến thể của cây quyết định được thể hiện thông qua Random Forest, Boosting, Bagging, AdaBoost, Gadient Descent Tree và Stacking dùng cho dự đoán lỗi phần mềm. Bên cạnh đó việc đánh giá mô hình cũng được trình bày để xác định hiệu suất, độ chính xác và độ tin cậy của mô hình. Chương IV trình bày việc thực hiện bài toán dự đoán lỗi phần mềm trong đó lựa chọn phương pháp dự đoán lỗi trên các tập tin được viết bằng ngôn ngữ Java. Tập dữ liệu được lấy trên kho dữ liệu PROMISE dùng để huấn luyện mô hình và sử dụng thư viện sklearn để cài đặt thuật toán. Các mô hình học máy được xây dựng từ các biến thể Cây quyết định bằng kỹ thuật học kết hợp với các tham số được để mặc định (quy định bởi thư viện sklearn). Kết quả đánh giá dựa trên các phép đo F1, ROC, AUC và thời gian huấn luyện để đánh giá các mô hình. Một website được xây dựng để người dùng chọn file (ngôn ngữ Java) và cho phép chọn kỹ thuật ensembles learning phù hợp để dự đoán. Phần cuối là kết luận về các kết quả đã đạt được và hướng phát triển của luận văn. 11 CHƯƠNG I: ĐỘ ĐO MÃ NGUỒN VÀ BÀI TOÁN DỰ ĐOÁN LỖI 1.1 Bài toán dự đoán lỗi Lỗi phần mềm là lỗi, sai sót, nhầm lẫn, sự cố hoặc sự thiếu chính xác trong phần mềm khiến nó tạo ra một kết quả sai hoặc sự cố không lường trước được. Lỗi là thuộc tính cố hữu của một hệ thống, chúng xuất hiện từ khâu thiết kế hoặc khâu sản xuất hoặc môi trường bên ngoài. Lỗi phần mềm là lỗi lập trình gây ra hiệu năng khác so với dự tính. Phần lớn các lỗi là từ mã nguồn hoặc thiết kế, một số trong số đó là từ mã không chính xác được tạo từ trình biên dịch. Đối với các nhà phát triển phần mềm và khách hàng, lỗi phần mềm là một vấn đề nguy hiểm. Các lỗi phần mềm không chỉ làm giảm chất lượng phần mềm, tăng chi phí mà còn làm trì hoãn tiến độ phát triển, thậm chí có thể hủy bỏ cả dự án. Dự đoán lỗi phần mềm được đề xuất nhằm để giải quyết rắc rối này. Để dự đoán lỗi phần mềm (Software Defect Prediction – SDP) hiệu quả có thể phải từ quá trình kiểm thử hiệu năng của phần mềm và trực tiếp phân bổ tài nguyên. Để phần mềm phát triển đạt chất lượng, các lỗi phần mềm phải được phát hiện và sửa lỗi ở giai đoạn đầu của chu kỳ phát triển phần mềm (Software Development Life Cycle – SDLC). 1.2 Quản lý lỗi phần mềm Mục đích chính của việc quản lý lỗi phần mềm là để kiểm soát, làm tăng chất lượng của phần mềm bằng cách xác định và sửa chữa các lỗi trong giai đoạn sớm của SDLC. Các giai đoạn khác nhau của SDLC bao gồm thu thập các yêu cầu, phân tích, thiết kế, viết mã, thử nghiệm, triển khai và giai đoạn cuối cùng là công việc bảo trì. SDP đóng vai trò quan trọng trong việc phát triển phần mềm chất lượng cao. Xác định các lỗi trong giai đoạn đầu của SDLC là một công việc rất phức tạp, do đó cần được áp dụng các phương pháp hiệu quả để thực hiện. Các giai đoạn chính trong việc kiểm soát lỗi bao gồm: ✓ ✓ ✓ ✓ ✓ Xác định các lỗi; Phân loại các lỗi; Phân tích các lỗi; Dự đoán các lỗi; Loại bỏ các lỗi. Có thể hiểu rằng, đầu tiên là xác định sự xuất hiện của các lỗi trong phần mềm. Kiểm tra mã, xây dựng một mô hình mẫu và thử nghiệm để xác định lỗi bên trong phần mềm. Sau khi xác định được các lỗi, ta cần tiến hành phân loại, phân tích, dự đoán và phát hiện để sửa chữa nó. 12 1.3 Hướng tiếp cận dự đoán lỗi phần mềm. Qua việc nghiên cứu các kỹ thuật dự đoán đã được áp dụng và thử nghiệm, chúng ta nhận thấy có ba phương pháp chủ yếu thường được sử dụng để thực hiện đánh giá các mô hình dự đoán. Dự đoán lỗi bên trong dự án (With-in Project Defect Prediction - WPDP) Dự đoán lỗi liên dự án (Cross Project Defect Prediction - CPDP), liên quan đến 2 trường hợp: ✓ CPDP đối với các tập dữ liệu đồng nhất (Homogeneity). ✓ CPDP đối với tập dữ liệu không đồng nhất, phức tạp (Hetrogeneous) 1.3.1 Dự đoán lỗi bên trong dự án Mô hình dự đoán có thể được xây dựng bằng cách thu thập dữ liệu lịch sử từ một dự án phần mềm và dùng nó để dự đoán các lỗi trong cùng dự án được gọi là WPDP. WPDP hoạt động tốt nếu có đủ thông tin về lịch sử dữ liệu nhằm giúp đào tạo cho mô hình. Turhan, Burak và cộng sự đề xuất mô hình dự đoán lỗi dự đoán lỗi phần mềm đối với các vùng trọng điểm của phần mềm phát triển với tồn tại dữ liệu nội bộ (dự đoán lỗi bên trong dự án). Để áp dụng mô hình này, họ khuyến nghị các công ty phát triển phần mềm nên tạo một kho dữ liệu và lưu trữ các dữ liệu dự án và các thông tin liên quan đến lỗi từ dự án trong suốt quá trình phát triển [19]. Nhược điểm của WPDP là: ✓ Không phải lúc nào tất cả các dự án đều có thể thu thập dữ liệu lịch sử đó; ✓ Không thể đạt được độ chính xác 100% khi sử dụng WPDP. Zimmerman và cộng sự nhận định rằng, dự đoán lỗi thực hiện tốt hơn trong các dự án là khi có đủ dữ liệu để đào tạo cho mô hình [3]. Nghĩa là, để xây dựng mô hình dự đoán lỗi, chúng ta cần truy cập dữ liệu lịch sử. Trường hợp dữ liệu bị thiếu thì ta có thể áp dụng Dự đoán lỗi liên dự án (CCDP). Mặt khác, dữ liệu lịch sử thường không thể có đối với các dự án mới và áp dụng đối với nhiều công ty phát triển phần mềm. Trong trường hợp này, dự đoán lỗi sẽ rất khó để có được thành công. Để giải quyết vấn đề này, chúng ta cũng phải cần áp dụng CCDP. 1.3.2 CPDP đối với các tập dữ liệu đồng nhất (Homogeneity) CPDP đối với tập dữ liệu đồng nhất được sử dụng theo phương pháp tương tự như một dự án không có đủ dữ liệu lịch sử để đào tạo mô hình. Do vậy, mô hình dự đoán được phát triển cho một dự án và nó được áp dụng cho một số dự án khác hoặc trên toàn dự án. Nghĩa là, nó thực hiện cùng một mô hình dự đoán từ dự án này áp dụng sang dự án khác. Hạn chế của việc áp dụng CPDP là nó mong muốn các dự án có tập số liệu tương đồng (tập 13 số liệu phải bằng nhau giữa các dự án). Kết quả là, kỹ thuật áp dụng cho CPDP rất phức tạp khi liên quan đến các dự án với bộ dữ liệu không giống nhau [20]. 1.3.3 CPDP đối với tập dữ liệu không đồng nhất (Hetrogeneous) Để đối phó với sự không phù hợp nêu trên khi chỉ sử dụng bộ dữ liệu tương tự cho CPDP, kỹ thuật dự đoán lỗi không đồng nhất (Hetrogeneous Defect Prediction – HDP) đã được đề xuất để dự đoán các lỗi trên các dự án phần mềm với các bộ số liệu không cân bằng. 1.4 Độ đo mã nguồn Độ đo phần mềm là thành phần thuộc tính có thể định lượng hoặc đếm được mà chúng có thể được dùng để đo lường và dự đoán chất lượng của phần mềm. Một độ đo là một chỉ số mô tả một tính năng cụ thể của phần mềm. Xác định và đo lường số liệu phần mềm rất quan trọng vì nhiều lý do, bao gồm để ước thời gian thực thi, đo lường hiệu quả của quy trình phần mềm, ước tính các nỗ lực cần thiết cho quy trình, giảm bớt lỗi trong quá trình phát triển phần mềm, giám sát và kiểm soát quá trình thực thi dự án. Ba nhóm tham số được dùng để đo lường như mô tả trong Hình 1. Hình 1. Các nhóm tham số khác nhau về độ đo trong công nghệ phần mềm Độ đo quy trình nhằm đánh giá hiệu quả các số liệu và giá trị của quy trình phần mềm, xác định sự hình thành của quy trình, nỗ lực cần có trong quy trình, hiệu quả của việc giảm thiểu lỗi trong quá trình phát triển, v.v. Độ đo sản phẩm dùng để xác định số liệu sản phẩm trong các giai đoạn khác nhau từ giai đoạn lập yêu cầu đến triển khai phát triển phần mềm hoặc bản thân nội tại phần mềm. Độ đo dự án là các phép đo của dự án phần mềm, chúng được dùng để theo dõi và kiểm soát việc thực hiện dự án qua các phiên bản. Mục đích dùng độ đo phần mềm là: • Đo lường kích thước, chất lượng phần mềm. • Đánh giá mức độ phức tạp. • Xác định ngày phiên bản. 14 • Ước lượng về tài nguyên, chi phí và tiến độ. Như vậy, có thể nói rằng để xây dựng một phần mềm dự đoán lỗi phải được thực hiện với một phạm vi rộng, đồng thời việc thu thập thông tin và xử lý các số liệu phục vụ cho việc xây dựng mô hình dự đoán cần có sự đầu tư rất lớn. Trong phạm vi luận văn này, tôi chỉ tập trung vào việc nghiên cứu về độ đo sản phẩm phần mềm và dùng nó để dự đoán lỗi, bao gồm tập các số liệu hướng lớp được xác định từ mã nguồn. Độ đo mã tĩnh Độ đo mã tĩnh là số liệu có thể được trích xuất trực tiếp từ mã nguồn, chẳng hạn như số dòng mã (LOC) và độ phức tạp theo chu kỳ. Source Lines of Code (SLOC) là một nhóm các số liệu tập trung vào số lượng dòng mã trong các tệp mã nguồn. SLOC chứa các số liệu khác nhau: LOC vật lý (SLOCP), tổng số dòng mã LOC, dòng trống (BLOC), các dòng comment (CLOC), các dòng có chứa comment (SLOC-L) và các dòng lệnh thực thi [6]. Lượng phức tạp của chu trình (Cyclomatic Complexity Number - CCN) hay còn được gọi là số liệu McCabe là phép đo độ phức tạp của cấu trúc module quyết định được Thomas McCabe đề xuất [15]. CCN xác định số lượng rẽ nhánh độc lập và được tính như sau: bắt đầu từ 0, CCN tăng thêm sau một lần gọi phương thức tách luồng điều khiển. Trường hợp này được dùng đối với các câu lệnh If, Then, While, Case, Catch, &&, | |, Or, ? được phát hiện trong mã nguồn. Các số liệu mã tĩnh khác bao gồm số các lệnh của trình biên dịch và số lượng khai báo dữ liệu. Độ đo hướng đối tượng: Số liệu hướng đối tượng là một danh mục con của số liệu mã tĩnh, vì số liệu này cũng được trích xuất từ chính mã nguồn. Bộ số liệu hướng đối tượng (OO) được Chidamber-Kemerer (C&K) sử dụng gồm có 8 số liệu khác nhau: sáu số liệu được định nghĩa từ bộ số liệu C&K ban đầu và hai số liệu bổ sung là Weighted Methods per Class (WMC), Depth of Inheritance Tree (DIT), Number of Children (NOC). Coupling Between Objects (CBO), Response for Class (RFC), Lack of Cohesion in Methods (LCOM) [6]. Các số liệu OO bổ sung gồm Afferent couplings (Ca), Number of Public Methods (NPM). Ngoài ra, QMOOD cũng là một trong những mô hình đánh giá chất lượng của phần mềm hướng đối tượng. Các số liệu được dùng để đánh giá sự tác động đến các thuộc tính chất lượng của phần mềm như SIZE, NOC, DIT, DAM, CBO, CAM, MOA, MFA, NOP, RFC, WMPC. Do vậy, các số liệu QMOOD cũng được áp dụng trong phạm vi nghiên cứu này để hỗ trợ việc dự đoán chất lượng phần mềm. 15 Sau đây là bảng tổng hợp các số liệu dùng để đo lường phần mềm hướng lớp được dùng trong luận văn này: Bảng 1. Số liệu dùng để đo lường các đặc trưng lỗi phần mềm Tên số liệu Định nghĩa Weighted Giá trị của WMC bằng với số lượng các phương thức trong lớp (mặc methods per class định trọng số bằng nhau cho tất cả các phương thức) (WMC) Depth of Inheritance Tree (DIT) Các số liệu DIT cung cấp cho mỗi lớp một phép đo của các mức thừa kế từ các đối tượng phân cấp cao nhất. Number of Children (NOC) Chỉ số NOC đơn giản là các phép đo lớp con trực tiếp của lớp. Coupling between object classes (CBO) Số liệu CBO đại diện cho số lượng các lớp được liên kết với một lớp nhất định (khớp nối và khớp nối hướng tâm). Khớp nối này có thể xảy ra thông qua gọi phương thức, truy nhập trường, thừa kế, phương thức đối số, kiểu trả về và ngoại lệ. Response for a Class (RFC) Số liệu RFC dùng để đo số phương thức khác nhau có thể được thực hiện khi một đối tượng của lớp đó nhận được yêu cầu. Xuất phát ý tưởng ta muốn tìm mỗi phương thức của lớp, các phương thức mà lớp sẽ gọi và số lần lặp cho mỗi phương thức được gọi, tính toán khả năng phương thức tiếp tục được gọi của đồ thị gọi phương thức. Tuy nhiên, quá trình này có thể khó thỏa mãn độ chính xác không cao. Ckjm tính toán một xấp xỉ để giải quyết bằng cách đơn giản thiết lập với việc kiểm tra các lần gọi phương thức trong quan hệ phương thức lớp. Giá trị của RFC là tổng số phương thức được gọi trong phạm vi phương thức lớp và số lượng các phương thức lớp. Đây là cách đơn giản hóa được sử dụng trong mô tả của Chidamber và Kemerer. Lack of cohesion in methods (LCOM) Số liệu LCOM đếm tập hợp phương thức có trong một lớp mà nó không liên quan đến việc chia sẻ một số trường trong lớp. Định nghĩa của số liệu này (sử dụng trong ckjm) xem xét tất cả các cặp phương thức lớp. Một trong số các cặp có phương thức truy nhập ít nhất một trường chung của lớp, trong khi các cặp khác hai phương 16 thức không chia sẻ bất kỳ truy cập trường chung nào. Việc thiếu sự gắn kết trong các phương thức sau đó được tính bằng cách trừ số lượng các cặp phương thức không chia sẻ một trường truy cập vào số lượng các cặp phương thức mà chúng được thực hiện. Lack of cohesion in methods (LCOM3) m - số phương thức trong một lớp. a - số thuộc tính trong một lớp µ(A)- số phương thức truy cập vào thuộc tính A Afferent couplings (Ca) Số liệu Ca thể hiện cho số lượng các lớp phụ thuộc vào lớp được đo Efferent couplings (Ce) Số liệu Ce thể hiện cho số lớp học mà lớp đo được phụ thuộc vào. Number of Public Số liệu NPM chỉ đơn giản là đếm tất cả các phương thức trong một Methods (NPM) lớp được chỉ định là công khai. Số liệu này còn được gọi là kích thước giao diện lớp (CIS) Data Access Metric (DAM) Số liệu này là tỷ lệ các thuộc tính riêng (protected) trên tổng số thuộc tính được chỉ định trong lớp. Measure of Aggregation (MOA) Số liệu này đo lường một phần trong toàn bộ quan hệ, thực hiện bằng cách sử dụng các thuộc tính. Số liệu này là số lượng các trường của lớp mà kiểu được định nghĩa bởi người dùng. Measure of Functional Abstraction (MFA) Số liệu này là tỷ lệ của số phương thức được thừa kế bởi một lớp trên tổng số phương thức có thể truy cập bởi các phương thức thành viên của lớp. Các Constructor như Java.lang.Object (như mức cha) được bỏ qua. Cohesion Among Số liệu này tính các quan hệ giữa các phương thức của một lớp dựa Methods of Class trên danh sách các tham số của các phương thức. Số liệu này được (CAM) tính toán bằng cách sử dụng tổng hợp các loại tham số phương thức khác nhau trong mỗi phương thức chia cho số các kiểu tham số phương thức khác nhau trong toàn bộ lớp nhân với số lượng các phương thức. 17 Inheritance Coupling (IC) Số liệu này cung cấp số lớp cha mà một lớp nhất định được kết hợp. Một lớp được kết hợp với lớp cha nếu một trong những phương thức thừa kế của nó phụ thuộc vào các phương thức mới hoặc được xác định lại trong lớp. Lớp được kết hợp với lớp cha nếu thỏa mãn một trong các điều kiện sau: • Một trong các phương thức thừa kế của nó sử dụng một thuộc tính mà nó được định nghĩa lại trong Phương thức mới. • Một trong những phương thức được thừa kế gọi một phương thức được định nghĩa lại. • Một trong những phương thức được thừa kế được gọi bởi một phương thức được định nghĩa lại và sử dụng tham số mà nó được định nghĩa trong Phương thức được định nghĩa lại. Coupling Số liệu đo lường tổng số các phương pháp mới hoặc định nghĩa lại Between Methods mà tất cả các phương thức thừa kế được kết hợp. Có một liên kết khi (CBM) ít nhất một trong các điều kiện mà định nghĩa số liệu IC được đưa ra. Average Method Complexity (AMC) Số liệu này đo trung bình kích thước phương thức cho mỗi lớp. Kích thước của một phương thức bằng số mã nhị phân Java trong phương thức. McCabe's cyclomatic complexity (CC) CC bằng số lượng đường dẫn khác nhau trong một phương thức (hàm) cộng với 1. Độ phức tạp chu kỳ được định nghĩa là: CC = E – N + P E - số cạnh của đồ thị N - số lượng các nút của đồ thị P - số lượng thành phần kết nối CC chỉ là số liệu kích thước phương thức. Các mô hình xây dựng để dự đoán kích thước lớp. Do đó, số liệu phải được chuyển đổi thành một số liệu kích thước lớp. Hai số liệu được bắt nguồn: • Max (CC) - giá trị lớn nhất của CC trong số các phương pháp của lớp được xét. • Avg (CC) – trung bình số học của giá trị CC trong lớp được xét. Lines of Code (LOC) Số liệu LOC dựa trên mã nhị phân Java. Nó là tổng số trường, số phương thức và số lệnh trong tất cả các phương thức của lớp được xét. 18 CHƯƠNG II: CÁC KỸ THUẬT HỌC MÁY Để nâng cao hiệu quả và chất lượng phát triển phần mềm và dự đoán lỗi, các kỹ thuật khai phá dữ liệu khác nhau có thể được áp dụng các thuật toán khác nhau để giải quyết vấn đề. Các kỹ thuật SDP sử dụng kỹ thuật học phổ biến và các thuật toán học máy được mô tả trong Hình 2. Hình 2. Thuật toán học máy Các kỹ thuật khai phá dữ liệu khác nhau được áp dụng để dự đoán lỗi phần mềm. Trong khai phá dữ liệu, học máy có thể chia làm 2 loại: • Học có giám sát (Supervised Learning). • Học không giám sát (Unsupervised Learning). Ngoài ra, còn có kỹ thuật học tăng cường (Reinforce Learning) và học bán giám sát (Semi-Supervised Learning). Tuy nhiên, tôi chỉ quan tâm đến 2 kỹ thuật nêu trên để đi sâu nghiên cứu nhằm nắm bắt kỹ thuật, áp dụng trong luận văn của mình. 19 2.1 Học có giám sát Học có giám sát là hoạt động học máy để suy luận một đặc trưng từ dữ liệu huấn luyện được dán nhãn. Các dữ liệu huấn luyện bao gồm một tập hợp các mẫu huấn luyện. Trong học có giám sát, mỗi mẫu là một cặp đôi, gồm một đối tượng đầu vào (thường là vectơ) và giá trị đầu ra mong muốn (được gọi là tín hiệu giám sát). Thuật toán học có giám sát sẽ phân tích dữ liệu huấn luyện và tạo ra một hàm suy luận, có thể được sử dụng để ánh xạ các mẫu mới. Một kịch bản tối ưu sẽ cho phép thuật toán xác định chính xác các nhãn lớp cho các trường hợp không cụ thể. Điều này đòi hỏi thuật toán học máy phải khái quát hóa từ dữ liệu huấn luyện đến các tình huống không cụ thể theo một cách "hợp lý" (xu hướng quy nạp). Hoạt động xảy ra tương tự suy luận của con người và động vật và thường được xem là khái niệm nhận thức từ việc học. Để áp dụng Học có giám sát giúp giải quyết một vấn đề nhất định, chúng ta phải thực hiện các bước sau: Bước 1. Xác định loại hình các mẫu huấn luyện: trước khi làm bất cứ điều gì, người dùng nên quyết định loại hình dữ liệu nào sẽ được sử dụng làm tập huấn luyện. Ví dụ trường hợp phân tích chữ viết tay, chúng ta có thể phải xác định dữ liệu là toàn bộ các ký tự, từ hoặc dòng chữ viết tay. Bước 2. Thu thập bộ dữ liệu huấn luyện: tập huấn luyện cần phải đại diện, là đặc trưng trong thế giới thực. Do đó, một tập hợp các đối tượng đầu vào được thu thập và các đầu ra tương ứng cũng được thu thập từ người dùng, các chuyên gia hoặc từ các phép đo. Bước 3. Xác định biểu diễn đầu vào đặc trưng của chức năng đã được huấn luyện. Độ chính xác của đặc trưng được huấn luyện có sự phụ thuộc chặt chẽ vào cách thể hiện đối tượng đầu vào. Thông thường, đối tượng đầu vào được chuyển đổi thành một vectơ đặc trưng, trong đó có một số đặc trưng mô tả về đối tượng. Số lượng các đặc trưng không nên quá lớn vì sẽ làm tăng số chiều của dữ liệu nhưng cũng nên chứa đủ thông tin để đảm bảo dự đoán đầu ra chính xác. Bước 4. Xác định cấu trúc của chức năng được huấn luyện và thuật toán học máy tương ứng. Ví dụ, các nhà kỹ thuật có thể chọn sử dụng thuật toán Máy vectơ hỗ trợ (SVM) hoặc Cây quyết định (DS). Bước 5. Hoàn thành thiết kế: chạy các thuật toán học máy trên tập huấn luyện được thu thập. Một số thuật toán học có giám sát yêu cầu người dùng xác định các tham số nhất định để kiểm soát. Các thông số này có thể tùy chọn hoặc điều chỉnh được nhằm giúp tối ưu hóa hiệu suất trên một tập hợp con (còn gọi là tập xác nhận) của tập huấn luyện hoặc thông qua xác thực chéo. 20 Bước 6. Đánh giá tính chính xác của chức năng đã được huấn luyện: sau khi điều chỉnh tham số và huấn luyện, hiệu suất của hàm kết quả phải được đo trên tập kiểm tra độc lập, tách biệt với tập huấn luyện. Một số lượng lớn các thuật toán học có giám sát được đề xuất, mỗi thuật toán đều có điểm mạnh và điểm yếu và không có thuật toán học máy duy nhất nào hoạt động tốt nhất trên mọi vấn đề trong học máy có giám sát. Có bốn vấn đề chính cần lưu ý trong học máy có giám sát: Sự đánh đổi giữa độ lệch và phương sai (Bias-variance tradeoff) Vấn đề đầu tiên là sự đánh đổi giữa độ lệch (bias) và phương sai (variance). Giả sử rằng chúng ta có sẵn một số bộ dữ liệu dùng để huấn luyện khác nhau và đều được đánh giá tốt. Một thuật toán học máy đưa ra kết quả lệch theo một đầu vào cụ thể x nếu khi huấn luyện trên mỗi bộ dữ liệu này về mặt hệ thống là nó không chính xác khi dự đoán đầu ra cho x. Một thuật toán học máy có phương sai cao cho một đầu vào cụ thể x nếu nó dự đoán các giá trị đầu ra khác nhau khi được đào tạo trên các tập huấn luyện khác nhau. Lỗi dự đoán của trình phân loại đã huấn luyện có liên quan đến độ lệch và phương sai của thuật toán học. Như vậy, ta đã thấy ở đây đã có sự đánh đổi giữa độ lệch và phương sai. Một thuật toán học máy có độ lệch thấp cần phải linh hoạt để có thể phù hợp với dữ liệu. Nhưng nếu thuật toán học máy linh hoạt quá thì nó chỉ sẽ phù hợp với từng bộ dữ liệu huấn luyện khác nhau và do đó có thể làm phương sai cao. Một khía cạnh quan trọng của nhiều phương pháp dùng trong học máy có giám sát là chúng có thể điều chỉnh sự đánh đổi giữa độ lệch và phương sai này (tự động điều chỉnh hoặc cung cấp một tham số độ lệch/phương sai do người dùng định nghĩa). Độ phức tạp của hàm và số lượng dữ liệu huấn luyện Vấn đề thứ hai là lượng dữ liệu huấn luyện có liên quan đến độ phức tạp của hàm (hàm phân loại hoặc hàm hồi quy). Nếu hàm đơn giản thì không đòi hỏi sự linh hoạt của thuật toán học máy với độ lệch cao và phương sai thấp sẽ có khả năng chỉ đào tạo với một lượng dữ liệu nhỏ. Trường hợp hàm phức tạp (chẳng hạn do sự liên quan, tương tác phức tạp giữa nhiều đặc trưng đầu vào khác nhau và hoạt động khác giữa các thành phần khác nhau của không gian đầu vào) thì chức năng sẽ có thể phải được huấn luyện với một lượng dữ liệu rất lớn và sử dụng một thuật toán học máy linh hoạt với độ lệch thấp và phương sai cao. Tuy nhiên, các thuật toán học máy được xem là tốt sẽ tự động điều chỉnh sự đánh đổi độ lệch/phương sai dựa trên lượng dữ liệu có sẵn và độ phức tạp cụ thể của hàm để huấn luyện. Kích thước của không gian đầu vào