Xem mẫu
- ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG CĐ CÔNG NGHỆ THÔNG TIN
BÁO CÁO TỔNG KẾT
ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ
CẤP CƠ SỞ
NGHIÊN CỨU CÁC ĐỘ ĐO MÃ NGUỒN CHO
BÀI TOÁN DỰ ĐOÁN LỖI PHẦN MỀM
Mã số: T2018-07-07
Chủ nhiệm đề tài: ThS. Hà Thị Minh Phương
Đà Nẵng, 12/2018
- ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG CĐ CÔNG NGHỆ THÔNG TIN
BÁO CÁO TỔNG KẾT
ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ
CẤP CƠ SỞ
NGHIÊN CỨU CÁC ĐỘ ĐO MÃ NGUỒN CHO
BÀI TOÁN DỰ ĐOÁN LỖI PHẦN MỀM
Mã số: T2018-07-07
Xác nhận của cơ quan chủ trì đề tài Chủ nhiệm đề tài
Đà Nẵng, 12/2018
- MỤC LỤC
MỤC LỤC
MỤC LỤC........................................................................................................................................................... I
DANH MỤC HÌNH VẼ ........................................................................................................................................ 1
DANH MỤC TỪ VIẾT TẮT .................................................................................................................................. 2
THÔNG TIN KẾT QUẢ NGHIÊN CỨU .................................................................................................................. 3
MỞ ĐẦU .......................................................................................................................................................... 5
I. TỔNG QUAN TÌNH HÌNH NGHIÊN CỨU THUỘC LĨNH VỰC ĐỀ TÀI TRONG VÀ NGOÀI NƯỚC ..................... 5
1. NGOÀI NƯỚC ................................................................................................................................................ 5
2. TRONG NƯỚC................................................................................................................................................ 5
II. TÍNH CẤP THIẾT CỦA ĐỀ TÀI ..................................................................................................................... 5
III. MỤC TIÊU CỦA ĐỀ TÀI.............................................................................................................................. 5
IV. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU ................................................................................................... 6
1. ĐỐI TƯỢNG NGHIÊN CỨU ................................................................................................................................ 6
2. PHẠM VI NGHIÊN CỨU .................................................................................................................................... 6
V. NỘI DUNG NGHIÊN CỨU .......................................................................................................................... 6
CHƯƠNG 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM ........................................................................................ 7
1.1. TỔNG QUAN VỀ LỖI PHẦN MỀM ............................................................................................................... 7
1.2. MỐI LIÊN HỆ GIỮA ĐỘ ĐO VÀ LỖI PHẦN MỀM ......................................................................................... 8
1.3. ĐỘ ĐO PHẦN MỀM .................................................................................................................................... 8
1.3.1. Độ đo mã nguồn (Code Metrics) ................................................................................................... 8
1.3.2. Độ đo quy trình (Process Metrics) .............................................................................................. 11
1.4. ÁP DỤNG CÁC ĐỘ ĐO PHẦN MỀM .......................................................................................................... 11
1.5. KỸ THUẬT HỌC MÁY TRONG DỰ ĐOÁN LỖI PHẦN MỀM ........................................................................ 12
1.5.1. Cây quyết định (Decision Tree Classification) ............................................................................ 12
1.5.2. Naïve Bayes ................................................................................................................................. 13
1.5.3. K-nearest Neighbor ..................................................................................................................... 13
1.5.4. Support Vector Machine (SVM) .................................................................................................. 15
1.6. XỬ LÝ DỮ LIỆU ......................................................................................................................................... 16
1.6.1. Chuẩn hóa dữ liệu ....................................................................................................................... 16
1.6.2. Giảm tiếng ồn (Noise reduction)................................................................................................. 17
1.6.3. Lựa chọn thuộc tính (Attribute Selection) .................................................................................. 18
1.7. CÁC ĐÁNH GIÁ ĐỘ ĐO ................................................................................................................................... 18
1.7.1. Phân loại đo lường ..................................................................................................................... 18
1.7.2. Thảo luận về các độ đo ............................................................................................................... 22
CHƯƠNG 2: ĐỘ ĐO TRONG DỰ ĐOÁN LỖI PHẦN MỀM .............................................................................24
2.1. GIỚI THIỆU............................................................................................................................................... 24
2.2. ĐỘ ĐO HƯỚNG ĐỐI TƯỢNG (OBJECT ORITEND METRICS) .................................................................... 24
2.2.1. Độ đo kích thước (Size) ............................................................................................................... 25
2.2.2. Độ đo phụ thuộc (coupling) ........................................................................................................ 25
2.2.3. Độ đo gắn kết (cohesion) ............................................................................................................ 26
2.2.4. Độ đo thừa kế (Inheritcance Metrics) ........................................................................................ 26
2.2.5. Độ đo đa hình (Polymorphism Metrics) ..................................................................................... 27
2.2.6. Độ đo tái sử dụng (Reuse metrics) ............................................................................................. 27
CHƯƠNG 3: KẾT QUẢ THỰC NGHIỆM ........................................................................................................28
1.1. CÂU HỎI NGHIÊN CỨU ............................................................................................................................ 28
1.2. CÁC GIẢ THUYẾT NGHIÊN CỨU ............................................................................................................... 28
1.3. BIẾN PHỤ THUỘC (DEPENDENT VARIABLE) ....................................................................................................... 28
i
- MỤC LỤC
1.4. BIẾN ĐỘC LẬP (INDEPENDENT VARIABLES)........................................................................................................ 29
1.5. THU THẬP DỮ LIỆU ....................................................................................................................................... 29
KẾT LUẬN ........................................................................................................................................................33
KIẾN NGHỊ .......................................................................................................................................................33
TÀI LIỆU THAM KHẢO .....................................................................................................................................34
ii
- DANH MỤC HÌNH VẼ
DANH MỤC HÌNH VẼ
Hình 1.1 Tần suất sử dụng độ đo phần mềm trong các nghiên cứu .............................. 11
Hình 1.2 Cây quyết định đơn giản .................................................................................13
Hình 1.3 Ví dụ K-Nearest Neighbor..............................................................................14
Hình 1.4 Ví dụ về ROC .................................................................................................21
Hình 1.5 Đường cong Cost-effective curve...................................................................22
Hình 1.6 Tổng số các biện pháp đánh giá độ đo được sử dụng trong các nghiên cứu dự
đoán lỗi phần mềm (Nam, 2009) ...................................................................................23
Hình 3.1 Kỹ thuật phân tích của OSSGrab....................................................................29
Hình 3.2 Tìm kiếm đơn giản trong kho OSS .................................................................30
Hình 3.3 Tìm kiếm nâng cao trong kho OSS ................................................................ 31
Trang 1
- DANH MỤC TỪ VIẾT TẮT
DANH MỤC TỪ VIẾT TẮT
Từ viết tắt Tiếng Anh Tiếng Việt
OSS Open Source System Hệ thống mã nguồn mở
OO Object Oriented Hướng đối tượng
CK Chidamber-Kemerer Độ đo Chidamber-Kemerer
SVM Support Vector Machine Máy vector hỗ trợ
DT Decision Tree Cây quyết định
RF Random Forest Rừng ngẫu nhiên
Trang 2
- THÔNG TIN KẾT QUẢ NGHIÊN CỨU
ĐẠI HỌC ĐÀ NẴNG CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG CĐ CÔNG NGHỆ THÔNG TIN Độc lập – Tự do – Hạnh phúc
THÔNG TIN KẾT QUẢ NGHIÊN CỨU
1. Thông tin chung:
- Tên đề tài: Nghiên cứu các độ mã nguồn cho bài toán dự đoán lỗi phần
mềm
- Mã số: T2018-07-07
- Chủ nhiệm: HÀ THỊ MINH PHƯƠNG
- Thành viên tham gia: không
- Cơ quan chủ trì: Trường Cao đẳng Công nghệ thông tin – Đại học Đà Nẵng
- Thời gian thực hiện: từ tháng 04/2018 đến tháng 12/2018
2. Mục tiêu:
Nghiên cứu lý thuyết:
Tìm hiểu độ đo mã nguồn hướng cấu trúc
Tìm hiểu độ đo mã nguồn hướng đối tượng
Nghiên cứu áp dụng các độ hướng đối tượng vào việc dự đoán lỗi phần
mềm
Áp dụng lý thuyết vào xây dựng công cụ dự đoán lỗi phần mềm nhằm tạo điều kiện
để tiếp tục nghiên cứu và xây dựng các hệ thống dự đoán lỗi phần mềm dựa trên
máy học để dự đoán được số lỗi của phần mềm….
3. Tính mới và sáng tạo:
- Lỗi phần mềm sẽ tác động mạnh đến các hệ thống phần mềm trong quá trình
phát triển cũng như quá trình triển khai
- Để dự đoán được các khả năng xảy ra lỗi, tác giả đã nghiên cứu các độ đo
(metrics, từ đó có thể lựa chọn các độ đo có mối liên hệ với khả năng xả ra lỗi
với từng ngôn ngữ lập trình cụ thể.
4. Tóm tắt kết quả nghiên cứu:
- Trình bày tổng quan các độ đo trong bài toán giải quyết lỗi phần mềm cụ thể là
độ đo cấu trúc (Structure metrics) và độ đo hướng đối tượng (Object Oriented
metrics).
Trang 3
- THÔNG TIN KẾT QUẢ NGHIÊN CỨU
- Đề tài cũng trình bày việc mô phỏng thực nghiệm áp dụng các độ đo hướng đối
tượng trong việc đưa ra mỗi liên hệ giữa các độ đo trên với khả năng xảy ra lỗi
trong cáchệ thống mã nguồn mở OSS được viết bằng C++
5. Tên sản phẩm:
- Báo cáo tổng kết đề tài;
- Bài báo đăng trên kỷ yếu hội thảo cấp trường.
6. Hiệu quả, phương thức chuyển giao kết quả nghiên cứu và khả năng áp dụng:
- Về mặt giáo dục - đào tạo: phục vụ công tác giảng dạy, nghiên cứu.
- Về mặt khoa học: đóng góp đáng kể của đề tài là trình bày các độ đo liên quan
mật thiết đến lỗi phần mềm, qua đó có thể đưa ra được các độ đo có tính hiệu quả
trong việc nhận biết lỗi phần mềm.
- Về sản phẩm ứng dụng: xây dựng được các hệ thống dự đoán được lỗi phần
mềm trong công nghệ phần mềm.
7. Hình ảnh, sơ đồ minh họa chính:
Độ đo Lỗi CBO RFC NOC WMC LCOM
Lỗi 1 0.038 0.495 0.36 0.17 0.058
(0.84) (0.005) (0.05) (0369) (0.76)
CBO - 1 0.528 0.306 0.278 0.423
(0.003) (0.10) (0.137) (0.02)
RFC - - 1 0.38 0.533 0.244
(0.038) (0.002) (0.195)
NOC - 1 -0.305 -0.032
(0.101) (0.867)
WMC - - - - 1 0.544
(0.002)
LCOM - 1
Bảng 0.1: Phân tích tương quan Spearman giữa các độ đo
Đà Nẵng, ngày 08 tháng 12 năm 2018
Cơ quan chủ trì Chủ nhiệm đề tài
Hà Thị Minh Phương
Trang 4
- MỞ ĐẦU
MỞ ĐẦU
I. TỔNG QUAN TÌNH HÌNH NGHIÊN CỨU THUỘC LĨNH VỰC ĐỀ TÀI
TRONG VÀ NGOÀI NƯỚC
1. Ngoài nước
Độ đo (metric) đóng một vai trò rất quan trọng để phát triển một phần mềm có
chất lượng tốt. The IEEE Standard Glossary of Software Engineering Terms đã định
nghĩa độ đo như là thước đo định lượng đến một hệ thống, một thành phần hoặc một
quá trình có một thuộc tính nhất định. Có rất nhiều loại độ đo khác nhau được trình
bày trong các tài liệu để đo lường các sản phẩm phần mềm. Trong sự phát triển phần
mềm hiện nay, ngôn ngữ hướng đối tượng (Object Oriented) được sử dụng do các đặc
tính cơ bản của chúng như lớp, đối tượng, che dấu thông tin, thừa kế, đóng gói, trìu
tượng và đa hình. Ngoài ra, độ đo của hướng đối tượng có sẵn được sử dụng để đo
chất lượng của các hệ thống hướng đối tượng.
2. Trong nước
Hiện nay đã có nhiều nghiên cứu về độ đo hướng đối tượng trên các ngôn ngữ
lập trình như C++, Java,…. Các độ đo có ích cho việc đánh giá sự phát triển cơ trúc có
thể không ảnh hưởng đến thiết kế mà sử dụng ngôn ngữ OO. Có rất nhiều mô hình độ
đo hướng đối tượng có sẵn và một số tác giả đã đề xuất cách để đo lường giá trị của độ
đo mã nguồn hướng đối tượng. Một nghiên cứu ước tính tiết kiệm chi phí bảo trì sửa
chữa là 42% bằng cách sử dụng độ đo mã nguồn hướng đối tượng.
II. TÍNH CẤP THIẾT CỦA ĐỀ TÀI
Việc đo lường phần mềm có tầm quan trọng trong việc phát triển phần mềm.
Nhiều độ đo đã được đề xuất lien quan đến cấu trúc khác nhau như lớp, phụ thuộc,
thừa kế, che dầu thông tin và đa hình. Rất khó để xác định độ đo nào tốt nhất. Do đó,
rất khó cho các nhà quản lý và người thực hiện dự án lựa chọn các độ đo cho các hệ
thống hướng đối tượng. Trong đó, độ đo OO (Object Oriented) là độ đo trong một hệ
thống hướng đối tượng để xác định sự thành công hay thất bại của một quy trình, để
xác định có định lượng sự cải tiến trong một quy trình phần mềm. Độ đo này được sử
dụng để cải tiến kỹ thuật lập trình hướng đối tượng tăng tính tin cậy của mã nguồn.
Xét thấy như vậy, chúng tôi nghiên cứu các độ đo mã nguồn hướng đối tượng cũng
như so sánh với độ đo mã nguồn hướng cấu trúc. Từ đó có thể đưa ra được dự đoán lỗi
phần mềm dựa trên các độ đo trên.
III. MỤC TIÊU CỦA ĐỀ TÀI
Nghiên cứu lý thuyết:
Trang 5
- MỞ ĐẦU
Tìm hiểu độ đo mã nguồn hướng cấu trúc
Tìm hiểu độ đo mã nguồn hướng đối tượng
Nghiên cứu áp dụng các độ hướng đối tượng vào việc dự đoán lỗi phần
mềm
Áp dụng lý thuyết vào xây dựng công cụ dự đoán lỗi phần mềm nhằm tạo điều kiện
để tiếp tục nghiên cứu và xây dựng các hệ thống dự đoán lỗi phần mềm dựa trên
máy học để dự đoán được số lỗi của phần mềm….
IV. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU
1. Đối tượng nghiên cứu
- Độ đo mã nguồn cấu trúc và độ đo mã nguồn hướng đối tượng: Sách, báo, ..
- Giá trị các độ đo trên.
2. Phạm vi nghiên cứu
Nghiên cứu các độ đo mã nguồn dựa trên
- Tiếp cận dựa vào lý luận.
- Tiếp cận dựa vào thống kê.
- Tiếp cận dựa trên cả hai phương pháp trên.
V. NỘI DUNG NGHIÊN CỨU
1. Tìm hiểu độ đo mã nguồn hướng cấu trúc và độ đo mã nguồn hướng đối tượng
2. Nghiên cứu và phân tích các giá trị của các độ đo trên trong dự đoán lỗi phần
mềm
3. Xây dựng công cụ dự đoán lỗi phần mềm dựa trên độ đo mã nguồn hướng đối
tượng
4. Viết báo cáo tổng kết đề tài.
Trang 6
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
1.1. TỔNG QUAN VỀ LỖI PHẦN MỀM
Trong lĩnh vực công nghệ phần mềm, các hệ thống phần mềm được sản xuất và
bảo trì bởi con người vì vậy việc duy trì phần mềm rất phức tạp, lỗi luôn luôn xuất
hiện tại các hệ thống này. Hầu hết các công ty phần mềm chi tiêu rất nhiều tiền và
nhân lực để phát hiện lỗi trong một hệ thống phần mềm trước khi được triển khai cho
khách hàng. Phần mềm càng phức tạp thì lỗi càng xuất hiện nhiều. Lỗi tác động tới
phần mềm hoặc hệ thống đang xây dựng hoặc vận hành theo nhiều cách khác nhau. Do
vậy để giảm thiểu các hậu quả do lỗi gây ra để tiết kiệm chi phí thì các nhà phát triển
cố gắng phát hiện lỗi trong giai đoạn sớm. Theo các thống kê, lỗi phần mềm tạo thành
một gánh nặng rất lớn cho công ty phần mềm phát triển. Việc xác minh phần mềm là
một quá trình khó khăn. Để quản lý tốt hơn lỗi lập trình do con người tạo ra, nhân sự
kiểm thử phần mềm được phát triển lên số lượng lớn. Do đó, việc xác định các mô-đun
bị lỗi sớm sẽ hỗ trợ sự phát triển của các hệ thống đáng tin cậy thông qua việc cải tiến
lập lịch và kiểm soát chất lượng phần mềm. Thông tin bị lỗi có thể cung cấp dữ liệu có
giá trị để cải thiện hiệu quả lỗi phần mềm. Từ những yếu tố trên các phương pháp dự
đoán lỗi phần mềm được ra đời. Như nhiều nghiên cứu cho thấy các phần mềm kiểm
thử trung bình tiêu thụ ít nhất 50% hiệu suất trong phát triển [1, 2], việc xác định các
mô-đun bị lỗi có thể có tác động tiết kiệm chi phí đáng kể đối với phát triển phần
mềm.
Một loạt các mô hình dự đoán lỗi đã được đề xuất [3,4]. Thông thường chúng ta
phát triển các mô hình dự đoán lỗi phần mềm theo hướng thống kê các mô-đun bị lỗi
có khả năng xảy ra trong quá trình triển khai phần mềm hoặc trong một khoảng thời
gian cụ thể sau khi triển khai. Các mô hình dự báo dựa trên dữ liệu lỗi đã được thu
thập và lựa chọn mô hình đánh giá chất lượng phù hợp, định lượng đánh giá một số
khía cạnh của chất lượng hệ thống. Chất lượng hệ thống, chẳng hạn như bảo trì [5],
được mô tả nhiều nhất về độ đo phức tạp trong bài toán dự đoán lỗi. Nhiều nghiên
cứu nghiên cứu Basili et al. [6], Emam al. [7], Gyimothy[8], và Olague [9], cho thấy
rằng các mô hình dự đoán lỗi thống kê có thể cung cấp đánh giá hợp lý khi dự đoán
các mô-đun hệ thống bị lỗi bằng cách sử dụng các độ đo hướng đối tượng (Object
Oriented). Tuy nhiên, khi các độ đo thì có hiệu quả khác nhau từ nhiều dự án khác
nhau, việc dự đoán lỗi là khó khăn để đạt được. Mô hình dự đoán thu được từ một dự
án này hiếm khi mang lại hiệu quả trong việc dự đoán các mô-đun dễ bị lỗi thuộc các
dự án khác bởi vì không có dữ liệu lịch sử lỗi [10].
Trang 7
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
Theo Zhang [11] trong khi một số ít lỗi là do các trình biên dịch tạo ra, nhiều lỗi
xuất phát từ lỗi do các lỗi do lập trình viên trong quá trình thiết kế và lập trình tạo ra.
Những vấn đề này không chỉ làm giảm chất lượng của phần mềm mà còn đẩy chi phí
kiểm tra [12]. Thật vậy, nhiều công ty phát triển phần mềm bao gồm Microsoft đã
dành một lượng tiền lớn và nỗ lực để thử nghiệm các sản phẩm phần mềm của họ
trước khi phát hành chúng cho khách hàng[13]. Bằng cách tập trung vào các trường
hợp bị lỗi, các công ty phát triển phần mềm có thể giảm chi phí và nâng cao hiệu quả
tổng thể của quá trình thử nghiệm thông qua phân bổ tài nguyên thông tin.
1.2. MỐI LIÊN HỆ GIỮA ĐỘ ĐO VÀ LỖI PHẦN MỀM
Quá trình xác định các mô-đun phần mềm dễ bị lỗi tại giai đoạn đầu được gọi là
dự đoán lỗi phần mềm. Nhiều nghiên cứu đã được công bố trong tài liệu, hầu hết trong
số họ nhằm mục đích xây dựng mô hình dự đoán lỗi bằng cách sử dụng các độ đo phần
mềm (ví dụ: số dòng mã lệnh – Line Of Code LOC), dữ liệu lịch sử và thuật toán phân
loại để khai thác dữ liệu. Với sự phát triển không ngừng của máy tính và dữ liệu, các
kĩ thuật học máy đang từng bước được áp dụng rộng rãi trong mọi lĩnh vực của cuộc
sống, trong đó có lĩnh vực phát triển phần mềm. Cho đến hiện nay, đã có một số công
trình nghiên cứu áp dụng các kĩ thuật học máy vào dự đoán lỗi như Naïve Bayes, rừng
ngẫu nhiên (Random Forest), Máy vector hỗ trợ SVM, ... Một số nghiên cứu đã cài đặt
và đánh giá hiệu quả của các kĩ thuật trên trong dự đoán lỗi cho các phần mềm mã
nguồn Java, dựa trên các độ đo trích xuất từ mã nguồn phần mềm..
1.3. ĐỘ ĐO PHẦN MỀM
Độ đo phần mềm có thể được coi là một độ đo định lượng gán các ký hiệu hoặc
số cho các đặc điểm của các trường hợp được dự đoán [14]. Trên thực tế, chúng là các
tính năng các thuộc tính, mô tả nhiều thuộc tính như độ tin cậy, nỗ lực, độ phức tạp và
chất lượng của các sản phẩm phần mềm. Những độ đo này đóng một vai trò quan trọng
trong việc xây dựng một bộ dự báo lỗi phần mềm hiệu quả. Chúng có thể được chia
thành hai loại chính: độ đo mã nguồn và độ đo quá trình [15].
1.3.1. Độ đo mã nguồn (Code Metrics)
Độ đo mã nguồn (Code Metrics)
Độ đo mã nguồn còn được gọi là độ đo sản phẩm, được thu thập trực tiếp từ mã
nguồn hiện tại. Những độ đo này đo độ phức tạp của mã nguồn dựa trên giả định rằng
các thành phần phần mềm phức tạp có nhiều khả năng chứa lỗi hơn. Trong suốt lịch sử
kỹ thuật phần mềm, nhiều độ đo mã khác nhau đã được sử dụng để dự đoán lỗi phần
mềm.
Trang 8
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
Kích thước (Size): độ đo đầu tiên là độ đo kích thước được giới thiệu bởi
Akiyama [16]. Để dự đoán số lỗi, tác giả sử dụng số dòng mã lệnh làm độ đo duy nhất.
Sau đó, nhiều nghiên cứu dự đoán lỗi phần mềm đã áp dụng độ đo này để xây dựng
các dự đoán [17,18,19,20]. Tuy nhiên, chỉ sử dụng độ đo này quá đơn giản để đo độ
phức tạp của sản phẩm phần mềm.
Halstead và McCabe: Vì lý do này, các độ đo hữu ích, được sử dụng rộng rãi và
dễ sử dụng khác đã được áp dụng để tạo ra các tiên đoán lỗi [17,21,22]. Các độ đo này
được gọi là các thuộc tính mã tĩnh được giới thiệu bởi McCabe (1976) và Halstead
(1977). Các thuộc tính Halstead được chọn dựa trên độ phức tạp đọc của mã nguồn.
Chúng được xác định bằng cách sử dụng một số độ đo cơ bản được thu thập từ phần
mềm bao gồm:
Ký hiệu Mô tả
µ1 Số toán tử riêng
µ2 Số toán hạng riêng
N1 Tổng số toán tử
N2 Tổng số toán hạng
µ1∗ Số lượng nhỏ nhất số toán tử
µ∗2 Số lượng nhỏ nhất số toán
hạng
Bảng 1.1 Độ đo Halstead
Bốn độ đo đầu tiên tự giải thích trong khi µ1∗ và µ∗2 là toán tử tiềm năng và toán
hạng được đếm trong một cá thể phần mềm. Ví dụ, µ1∗ = 2 là số lượng toán tử tối thiểu
cho hàm mặc định với tên hàm. Độ đo Halstead được xác định bằng cách sử dụng các
độ đo ở trên bao gồm:
Tên Mô tả
Length: N = N1+N2 Độ dài chương trình
Vocabulary: µ= µ1+ µ2 Kích thước
Volume V = N log2 µ Thông tin nội dung của chương
trình
Measure D= (N1/2) * (N2/2) Độ khó của chương trình
Measure E= D*V Yêu cầu thực thi chương trình
^
Measure B= 𝐸 (2/3)/3000 Số lượng lỗi mong muốn trong
chương trình
Measure T=E/18 Thời gian để thực thi chương trình
Bảng 1.2 Mô tả độ đo Halstead
Các thuộc tính của McCabe là các độ đo chu trình thể hiện sự phức tạp của một
sản phẩm phần mềm. Khác với các thuộc tính Halstead, các thuộc tính của McCabe đo
độ phức tạp của cấu trúc mã nguồn. Chúng thu được bằng cách tính số lượng các thành
phần, vòng cung và nút được kết nối trong các biểu đồ luồng điều khiển của mã nguồn.
Trang 9
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
Mỗi nút của biểu đồ luồng biểu diễn một câu lệnh chương trình trong khi một cung là
luồng của kiểm soát từ một câu lệnh khác.
Các độ đo của McCabe, Halstead và của Akiyama là những độ đo tiêu biểu của
các độ đo hướng phương thức.
Độ đo hướng lớp
Bên cạnh các độ đo hướng phương thức, từ khi các ngôn ngữ lập trình hướng đối
tượng trở nên phổ biến, các độ đo hướng lớp cũng đã được đề xuất và tiêu biểu nhất là
độ đo của Chidamber-Kemerer (CK) [23]. Các độ đo này được thiết kế từ những đặc
trưng hướng đối tượng như tính phụ thuộc (coupling), tính gắn kết (cohension), tính
thừa kế (inheritance), tính che giấu dữ liệu (information hide). Các độ đo CK bao gồm
số phương thức có trọng số trong lớp, độ sâu của cây thừa kế, số con, tính liên kết giữa
các lớp đối tượng, tính đáp ứng của một lớp, sự thiếu hụt tính gắn kết trong phương
thức.
Ký hiệu Mô tả
WMC Weighted methods per class
DIT Depth of inheritance tree
NOC Number of children
CBO Coupling between object
classes
RFC Response for a class
LCOM Lack of cohesion of methods
Bảng 1.3. Độ đo Chidamber & Kemerer, 1994 (CK)
Các độ đo trong bảng 3 được mô tả như sau:
Weighted methods per class (WMC): Độ đo này đo lường sự phức tạp của một
lớp riêng lẻ. Nó là một tổng trọng số của tất cả các phương thức trong một lớp.
Depth of inheritance tree(DIT): Độ đo này đo chiều dài của đường dẫn trong
cây thừa kế dài nhất ở một lớp. Nếu cây thừa kế cho lớp được đo sâu hơn thì sẽ
khó ước lượng được hành vi của lớp.
Number of children (NOC): Độ đo này tính số lượng các lớp con kế thừa ngay
từ lớp hiện tại.
Coupling between object classes (CBO): Độ đo này đo lường sự phụ thuộc của
một lớp đối với những người khác bằng cách đếm số lượng các lớp khác phụ
thuộc với lớp được đo. Một lớp phụ thuộc với các lớp khác nếu nó gọi các biến
hoặc các hàm của các lớp khác [24].
Response for a class (RFC): độ đo đếm số phương thức có khả năng được thực
thi để đáp ứng với một thông điệp nhận được bởi một đối tượng của một lớp
[25]
Lack of cohesion of methods (LCOM): Độ đo này là hiệu số cặp phương thức
không chia sẻ biến thành viên từ số cặp phương thức chia sẻ ít nhất một biến
thành viên.
Trang 10
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
1.3.2. Độ đo quy trình (Process Metrics)
Ngoài các độ đo mã nguồn trên trên, lịch sử của dự đoán lỗi phần mềm cũng đã
chứng kiến sự xuất hiện của các độ đo quy trình. Giống như các độ đo mã nguồn, các
độ đo quy trình cũng được sử dụng rộng rãi để xây dựng các mô hình dự đoán lỗi [26]
Tuy nhiên, thay vì được tính trực tiếp từ mã nguồn hiện tại, các độ đo quy trình được
tạo từ các kho phần mềm như hệ thống theo dõi lỗi và các hệ thống kiểm soát phiên
bản. Các độ đo này tập trung vào các thuộc tính liên quan đến quá trình phát triển phần
mềm; ví dụ, thay đổi mã nguồn, chi phí hoặc hiệu quả của các phương pháp được sử
dụng.
1.4. ÁP DỤNG CÁC ĐỘ ĐO PHẦN MỀM
Hình 1.1 cho thấy tần suất sử dụng các độ đo phần mềm trong tài liệu. Như sự
xuất hiện trước đó của độ đo phần mềm trong lịch sử dự đoán lỗi phần mềm, không
ngạc nhiên khi các độ đo mã nguồn được sử dụng thường xuyên hơn so với các độ đo
quá trình[15]. Hơn nữa, khi một loại độ đo mới được tạo ra, nó thường được so sánh
với các độ đo mã nguồn để làm sáng tỏ hiệu suất. Trong khi đó, các độ đo quy trình đã
được giới thiệu sau khi các kho phần mềm bao gồm các hệ thống theo dõi lỗi, các thay
đổi mã nguồn, lưu trữ thư, khai thác dữ liệu và các hệ thống kiểm soát phiên bản được
sử dụng rộng rãi.
Hình 1.1 Tần suất sử dụng độ đo phần mềm trong các nghiên cứu
Trong lĩnh vực dự đoán lỗi phần mềm, cũng có rất nhiều cuộc tranh luận về loại
độ đo nào hoạt động tốt hơn. Trong khi Menzies [18] nói rằng các độ đo mã nguồn
tĩnh vẫn hiệu quả để tạo ra các yếu tố dự báo lỗi; Rahman và Devanbu [27] tin rằng
gần đây, các độ đo quy trình hữu ích hơn do sự trì trệ của các độ đo mã nguồn. Trên
thực tế, hiệu quả của các độ đo quy trình để dự đoán lỗi phần mềm đã được xác nhận
trong một số nghiên cứu [27,28,29]. Mặc dù vậy, chỉ sử dụng các độ đo phần mềm là
Trang 11
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
không đủ để xây dựng các yếu tố dự đoán hiệu quả. Trong văn học, nhiều nhà nghiên
cứu đã chứng minh rằng các yếu tố dự đoán lỗi phần mềm hoạt động tốt hơn khi sử
dụng các kỹ thuật học máy để học từ dữ liệu lịch sử [15].
1.5. KỸ THUẬT HỌC MÁY TRONG DỰ ĐOÁN LỖI PHẦN MỀM
Học máy là một ngành khoa học khám phá việc xây dựng và nghiên cứu các kỹ
thuật cho phép các chương trình máy tính học hỏi từ dữ liệu mà không được lập trình
rõ ràng [30]. Về cơ bản, máy học tập cung cấp các chương trình máy tính với khả năng
bắt chước quá trình học tập của con người. Quá trình này là quan sát hiện tượng và
tổng quát từ các quan sát [31]. Học máy thường được chia thành hai loại chính: học
tập có giám sát và không giám sát. Trong học tập không giám sát, các thuật toán được
sử dụng để tìm hiểu các yếu tố dự đoán từ dữ liệu không được dán nhãn. Trong khi đó,
học tập có giám sát học các mô hình dự đoán dựa trên một tập hợp dữ liệu đầu vào với
thông tin nhãn.
Trong học tập có giám sát, các kết quả đầu ra có thể là các số thực trong các hồi
quy hoặc các nhãn lớp trong phân loại. Khi phân loại đầu vào thành hai hoặc nhiều
lớp, việc học được giám sát đôi khi được gọi là phân loại. Có một loạt các kỹ thuật
phân loại đã được khai thác rộng rãi trong các tài liệu để ghi nhãn các thể hiện phần
mềm là lỗi hoặc không lỗi.
1.5.1. Cây quyết định (Decision Tree Classification)
Cây quyết định là một trong những thuật toán dự đoán phổ biến được áp dụng
cho một loạt các tác vụ trong thống kê, khai phá dữ liệu và học máy. Thuật toán này
nhằm mục đích xây dựng một cây quyết định để phân loại một cá thể đích dựa trên các
tính năng đầu vào. Nó cũng có thể được biểu diễn như là câu lệnh if..else để tăng
cường khả năng đọc của con người Một ví dụ về cây quyết định, để hỗ trợ quá trình ra
quyết định, được trình bày trong hình 1.2. Cây quyết định trước hết được xây dựng
bằng cách phân loại các đặc điểm từ gốc xuống một số lá. Mỗi nút lá đại diện cho một
thử nghiệm trên một đối tượng địa lý trong khi mỗi nhánh là kết quả có thể có của
phép thử. Để gắn nhãn một thể hiện, các phép thử được thực hiện tại mỗi nút từ gốc
đến các nút lá thông qua các nhánh thích hợp [32].
Trang 12
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
Hình 1.2 Cây quyết định đơn giản
Có nhiều mô hình được phát triển bằng cách sử dụng cây quyết định để dự đoán
các lỗi phần mềm [18,33,34]. Người học J48, là một triển khai JAVA của thuật toán
C4.5 [35], có thể được xem là thuật toán được sử dụng rộng rãi nhất. Là một thuật toán
cây quyết định bình thường, J48 phân tách đệ quy một tập dữ liệu dựa trên các thử
nghiệm về các giá trị tính năng để tách các kết quả có thể có.
1.5.2. Naïve Bayes
Một cách khác để xây dựng các mô hình dự đoán lỗi phần mềm là sử dụng một
kỹ thuật học máy rất hữu ích, Naïve Bayes. Kỹ thuật này là một trong các phân loại
xác suất dựa trên định lý Bayes với các giả định độc lập giữa các thuộc [36]. Không có
ước lượng tham số lặp phức tạp, một trình phân loại Naïve Bayes dễ xây dựng và phù
hợp với dữ liệu đầu vào. Mặc dù đơn giản, các nghiên cứu so sánh của Langley và
Sage [37] đã chỉ ra rằng Naïve Bayes có hiệu quả đối với các tập dữ liệu lớn và thường
hoạt động tốt hơn các trình phân loại phức tạp hơn như cây quyết định trong các miền
học được giám sát.
1.5.3. K-nearest Neighbor
Ngoài cây quyết định J48 và Naïve Bayes, K-Nearest Neighbor [38], một trong
những thuật toán dựa trên khoảng cách đơn giản, cũng thường được áp dụng cho phân
loại mẫu. Trong lĩnh vực dự đoán lỗi phần mềm, nhiều nghiên cứu cũng đã sử dụng K-
Nearest Neighbor để phân loại các bộ dữ liệu thử nghiệm [39]. Mặc dù sự đơn giản
của nó, Weinberger và Saul nói rằng thuật toán K-Nearest Neighbor thường hoạt động
tốt và tạo ra kết quả cạnh tranh trong thực tế. Đáng chú ý, thuật toán có thể được cải
thiện đáng kể khi kết hợp với kiến thức trước thu được từ giai đoạn học dữ liệu [40].
Trang 13
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
Hình 1.3 Ví dụ K-Nearest Neighbor
Thuật toán K-Nearest Neighbor phân loại một cá thể mới dựa trên việc đo sự
giống nhau giữa nó và mọi cá thể hiện có khác. Sự tương tự được đo bằng các hàm
khoảng cách như khoảng cách Manhattan [41], khoảng cách Euclide [42] và khoảng
cách Mahalanobis [43]. Khi nói đến K-Nearest Neighbor, số lượng cá thể gần nhất
được sử dụng để dự đoán có thể ảnh hưởng đến hiệu suất dự đoán. Thông thường, con
số này là số lẻ nếu phân loại các cá thể thử nghiệm thành hai loại. Các trường hợp thử
nghiệm sẽ được dán nhãn dựa trên đa số phiếu. Khoshgoftaar [44] và Ganesan[45] đã
xây dựng các hệ thống lý luận dựa trên trường hợp (Case Base Reasoning CBR) để
phân loại các thành phần phần mềm bằng cách chỉ chọn k=1 là đơn vị lân cận gần
nhất. El-Emam và cộng sự, vào năm 2001, đã cải thiện bộ phân loại CBR bằng cách sử
dụng đa số phiếu trong các trường hợp của ba và năm cá thể gần nhất. Trong khi lựa
chọn một số lượng nhỏ các cá thể gần nhất có thể dẫn đến một tác động lớn hơn đến
phân loại tiếng ồn, sẽ làm tăng chi phí tính toán. Do đó, một cách tiếp cận đơn giản là
đặt số lượng hàng xóm gần nhất thành căn bậc hai của số lượng các cá thể huấn
luyện(k=√n).
Một phần mở rộng đơn giản khác, có thể cải thiện độ chính xác của các mô hình
dự báo, là áp dụng các trọng số. Lý do cho việc sử dụng trọng số là mức độ khác nhau
về sự giống nhau giữa cá thể được phân loại và hàng xóm của nó. Như vậy, thay vì
đưa ra trọng số bằng nhau cho tất cả các láng giềng gần nhất [45], trọng số của các cá
thể huấn luyện được thiết lập khác nhau tùy thuộc vào khoảng cách của chúng đến cá
thể thử nghiệm [44]. Có nhiều cách để đạt được trọng lượng. Theo đề xuất của
Cunningham và Delany [46], một kỹ thuật khá chung là sử dụng nghịch đảo của
khoảng cách là trọng lượng của từng trường hợp. Điều này có nghĩa là những người
hàng xóm gần gũi hơn có trọng lượng cao hơn những người cha. Một cách khác để đặt
trọng số dựa trên số lượng cá thể của mỗi lớp trong dữ liệu huấn luyện. Bằng cách chia
Trang 14
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
đơn giản số lượng hàng xóm gần nhất của một lớp cho số lượng cá thể của lớp này
trong tập dữ liệu huấn luyện, phương pháp này có thể trở thành một giải pháp tốt để
giảm thiểu vấn đề mất cân bằng lớp.
1.5.4. Support Vector Machine (SVM)
SVM là một trình phân loại khác thường được sử dụng trong nhiều ứng dụng.
SVM là một kỹ thuật học tập dựa trên lõi do Boser, Guyon và Vapnik đề xuất vào năm
1992, về cơ bản đề cập đến các vấn đề nhận dạng mẫu hai lớp [47]. Để thực hiện phân
loại, thuật toán SVM tìm thấy siêu kết nối tối ưu phân tách tất cả các cá thể của một
lớp từ lớp kia. Siêu kết nối tối ưu, được xác định bởi một số vectơ hỗ trợ [48], thu
được khi tối đa hóa chiều rộng của lề giữa hai lớp. Các vectơ hỗ trợ là các điểm dữ liệu
nằm trên ranh giới của đường biên.
Ánh xạ tập dữ liệu vào không gian nhiều chiều, bản chất của phương pháp SVM
là chuyển không gian dữ liệu ban đầu thành một không gian mới hữu hạn chiều mà ở
đó cho khả năng phân lớp dễ dàng hơn. Một quả bất kì nằm trên mặt bàn sẽ được gắn
với một tọa độ cụ thể. Ví dụ, quả táo nằm cách mép trái 2cm và cách mép dưới 5cm
được thể hiện trên trục tọa độ (x, y) tương ứng là (2, 5). x và y chính là tọa độ trong
không gian hai chiều của quả táo. Khi đưa lên chiều thứ 3 là z(x, y), ta có thể tính
được tọa độ của z trong không gian 3 chiều dựa vào tọa độ x,y ban đầu. Điểm làm
SVM hiệu quả hơn các phương pháp khác chính là việc sử dụng Kernel Method giúp
cho SVM không còn bị giới hạn bởi việc phân lớp một cách tuyến tính, hay nói cách
khác các siêu phẳng có thể được hình thành từ các hàm phi tuyến.
Smola [30] lập luận rằng chức năng cơ sở xuyên tâm là hạt nhân phổ biến nhất
được sử dụng trong SVM vì mang lại hiệu suất tốt hơn so với những người khác. Xét
về dự đoán, sử dụng SVM mang lại một số lợi thế [47] khiến SVM trở thành một trình
phân loại hữu ích để dự đoán các lỗi phần mềm.
Ưu điểm của SVM
• Xử lý trên không gian số chiều cao: SVM là một công cụ tính toán hiệu quả
trong không gian chiều cao, trong đó đặc biệt áp dụng cho các bài toán phân loại văn
bản và phân tích quan điểm nơi chiều có thể cực kỳ lớn
• Tiết kiệm bộ nhớ: Do chỉ có một tập hợp con của các điểm được sử dụng trong
quá trình huấn luyện và ra quyết định thực tế cho các điểm dữ liệu mới nên chỉ có
những điểm cần thiết mới được lưu trữ trong bộ nhớ khi ra quyết dịnh
• Tính linh hoạt - phân lớp thường là phi tuyến tính. Khả năng áp dụng Kernel
mới cho phép linh động giữa các phương pháp tuyến tính và phi tuyến tính từ đó khiến
cho hiệu suất phân loại lớn hơn.
Trang 15
- Chương 1: TỔNG QUAN VỀ ĐỘ ĐO PHẦN MỀM
Nhược điểm của SVM là gì?
• Bài toán số chiều cao: Trong trường hợp số lượng thuộc tính (p) của tập dữ liệu
lớn hơn rất nhiều so với số lượng dữ liệu (n) thì SVM cho kết quả khá tồi
• Chưa thể hiện rõ tính xác suất: Việc phân lớp của SVM chỉ là việc cố gắng tách
các đối tượng vào hai lớp được phân tách bởi siêu phẳng SVM. Điều này chưa giải
thích được xác suất xuất hiện của một thành viên trong một nhóm là như thế nào. Tuy
nhiên hiệu quả của việc phân lớp có thể được xác định dựa vào khái niệm margin từ
điểm dữ liệu mới đến siêu phẳng phân lớp mà chúng ta đã bàn luận ở trên.
1.6. XỬ LÝ DỮ LIỆU
Các kỹ thuật tiền xử lý dữ liệu rất quan trọng và được sử dụng rộng rãi trong học
máy, nền tảng của hầu hết các nghiên cứu dự đoán lỗi phần mềm Nam [15]. Có nhiều
yếu tố ảnh hưởng tiêu cực đến hiệu suất của thuật toán học máy như thông tin không
đáng tin cậy và không liên quan hoặc dữ liệu nhiễm ồn [49]. Những vấn đề này có thể
được giải quyết bằng cách sử dụng tiền xử lý dữ liệu cung cấp các kỹ thuật bao gồm
làm sạch dữ liệu, chuẩn hóa, lựa chọn thuộc tính và trích xuất. Vì sự khác biệt trong
việc lựa chọn mô hình, đối tượng và độ đo giữa các nghiên cứu, kỹ thuật tiền xử lý dữ
liệu có thể hoặc không được sử dụng và chúng được áp dụng theo nhiều cách khác
nhau tùy thuộc vào từng nghiên cứu.
1.6.1. Chuẩn hóa dữ liệu
Chuẩn hóa dữ liệu là một nhiệm vụ tiền xử lý cơ bản trong học máy và khai thác
dữ liệu [50], nhằm cải thiện hiệu suất của các mô hình phân loại bằng cách đưa ra
trọng số bằng nhau cho tất cả các thuộc tính của tập dữ liệu. Có rất nhiều phương pháp
chuẩn hóa có thể sử dụng được.
Một trong số đó là sử dụng bộ tiền xử lý nhật ký lọc được trình bày bởi Menzies
[18] để bình thường hóa các giá trị của các thuộc tính mã tĩnh có phân phối số mũ.
Trong phương pháp này, bộ lọc logarit được sử dụng để thay thế tất cả các giá trị số n
với logarit của n. Các thí nghiệm được thực hiện bởi Menzies [18] cho thấy rằng sau
khi được lọc, các giá trị này trở nên thậm chí nhiều hơn và do đó dễ dàng hơn cho các
mô hình dự đoán hoạt động trên chúng. Phương pháp lọc log cũng đã được áp dụng
trong một số nghiên cứu khác có cùng chủ đề thí nghiệm [21].
Ngoài kỹ thuật lọc log, các phương pháp chuẩn hóa dữ liệu khác là sự khác biệt
[51] và tính năng nhân rộng [52]. Các phương thức này chuyển đổi các giá trị của một
tập dữ liệu gốc thành một phạm vi từ 0 đến 1 và đảm bảo rằng mỗi thuộc tính nhận
được một trọng số bằng nhau. Trong khi trước đây là phân chia đơn giản mọi giá trị số
của từng thuộc tính theo difference=x_max - x_min, sau đó trừ giá trị nhỏ nhất từ mỗi
Trang 16
nguon tai.lieu . vn