›
›

Đồ án Nâng cao chất lƣợng phần mềm bằng các kỹ thuật program slicing - Nguyễn Sỹ Linh

pdf 52 trang huongle 3010
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Nâng cao chất lƣợng phần mềm bằng các kỹ thuật program slicing - Nguyễn Sỹ Linh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_nang_cao_chat_long_phan_mem_bang_cac_ky_thuat_program.pdf

Nội dung text: Đồ án Nâng cao chất lƣợng phần mềm bằng các kỹ thuật program slicing - Nguyễn Sỹ Linh

  1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o ĐỒ ÁN TỐT NGHIỆP Ngành Công nghệ Thông tin
  2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o NÂNG CAO CHẤT LƢỢNG PHẦN MỀM BẰNG CÁC KỸ THUẬT PROGRAM SLICING ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Sinh viên thực hiện: Nguyễn Sỹ Linh Giáo viên hƣớng dẫn: Th.S Nguyễn Trịnh Đông
  3. NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP Sinh viên: Nguyễn Sỹ Linh Mã số: 1351010032 Lớp: CT1301 Ngành: Công nghệ thông tin Tên đề tài: NÂNG CAO CHẤT LƢỢNG PHẦN MỀM BẰNG CÁC KỸ THUẬT PROGRAM SLICING
  4. NHIỆM VỤ ĐỀ TÀI 1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp a. Nội dung: - Nắm đƣợc các khái niệm cơ bản về program slicing - Nắm đƣợc các phƣơng pháp trong program slicing - Thử nghiệm trên một số chƣơng trình đơn giản b. Các yêu cầu cần giải quyết 2. Các số liệu cần thiết để thiết kế, tính toán 3. Địa điểm thực tập
  5. CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Ngƣời hƣớng dẫn thứ nhất: Họ và tên: Nguyễn Trịnh Đông Học hàm, học vị: Thạc sĩ Cơ quan công tác: Khoa Công nghệ Thông tin – Trƣờng Đại Học Dân Lập Hải Phòng Nội dung hƣớng dẫn: Ngƣời hƣớng dẫn thứ 2: Họ và tên: Học hàm, học vị: Cơ quan công tác: Nội dung hƣớng dẫn: Đề tài tốt nghiệp đƣợc giao ngày tháng năm 20 Yêu cầu phải hoàn thành trƣớc ngày tháng năm20
  6. Đã nhận nhiệm vụ: Đ.T.T.N Đã nhận nhiệm vụ: Đ.T.T.N Sinh viên Cán bộ hƣớng dẫn Đ.T.T.N Hải Phòng, ngày tháng năm 20 HIỆU TRƢỞNG GS.TS.NGƢT Trần Hữu Nghị
  7. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN 1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp: 2. Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã đề ra trong nhiệm vụ đề tài tốt nghiệp) Nguyễn Sỹ Linh-Ct1301 7
  8. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3. Cho điểm của cán hộ hƣớng dẫn: (Điểm ghi bằng số và chữ) Ngày tháng năm 20 Cán bộ hƣớng dẫn chính (Ký, ghi rõ họ tên) Nguyễn Sỹ Linh-Ct1301 8
  9. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM PHẢN BIỆN ĐỀ TÀI TỐT NGHIỆP 1. Đánh giá chất lƣợng đề tài tốt nghiệp (về các mặt nhƣ cơ sở lý luận, thuyết minh chƣơng trình, giá trị thực tế, ) Nguyễn Sỹ Linh-Ct1301 9
  10. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2. Cho điểm của cán bộ phản biện (Điểm ghhi bằng số và chữ) Ngày tháng năm 20 Cán bộ chấm phản biện (Ký, ghi rõ họ tên) Nguyễn Sỹ Linh-Ct1301 10
  11. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng LỜI CẢM ƠN Trƣớc hết em xin bày tỏ tình cảm và lòng biết ơn đối với thầy Nguyễn Trịnh Đông – Khoa Công nghệ Thông tin – Trƣờng Đại học Dân Lập Hải Phòng, ngƣời đã dành cho em rất nhiều thời gian quý báu, trực tiếp hƣớng dẫn tận tình giúp đỡ, chỉ bảo em trong suốt quá trình làm đồ án tốt nghiệp. Em xin chân thành cảm ơn tất cả các thầy cô giáo trong khoa Công nghệ Thông tin - Trƣờng ĐHDL Hải Phòng, chân thành cảm ơn các thầy giáo, cô giáo tham gia giảng dạy và truyền đạt những kiến thức quý báu trong suốt thời gian em học tập tại trƣờng, đã đọc và phản biện đồ án của em giúp em hiểu rõ hơn các vấn đề mình nghiên cứu, để em có thể hoàn thành đồ án này. Em xin cảm ơn GS.TS.NGƢT Trần Hữu Nghị Hiệu trƣởng Trƣờng Đại học Dân lập Hải Phòng, Ban giám hiệu nhà trƣờng, Bộ môn tin học, các Phòng ban nhà trƣờng đã tạo điều kiện tốt nhất trong suốt thời gian học tập và làm tốt nghiệp. Tuy có nhiều cố gắng trong quá trình học tập, trong thời gian thực tập cũng nhƣ trong quá trình làm đồ án nhƣng không thể tránh khỏi những thiếu sót, em rất mong đƣợc sự góp ý quý báu của tất cả các thầy giáo, cô giáo cũng nhƣ tất cả các bạn để kết quả của em đƣợc hoàn thiện hơn. Em xin chân thành cảm ơn! Hải Phòng, ngày tháng năm 2013 Sinh viên Nguyễn Sỹ Linh Nguyễn Sỹ Linh-Ct1301 11
  12. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng MỤC LỤC LỜI CẢM ƠN 1 MỤC LỤC 12 DANH MỤC HÌNH ẢNH 13 DANH MỤC CÁC TỪ VIẾT TẮT 14 GIỚI THIỆU 15 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN TRONG PROGRAM SLICING 16 1.1 Các định nghĩa 16 1.2 Static slicing 17 1.3 Dynamic slicing 18 Chƣơng 2: CÁC KĨ THUẬT DÙNG TRONG PHƢƠNG PHÁP STATIC SLICING 20 2.1.Static slicing đơn thủ tục. 20 2.1.1. Slicing dựa vào đồ thị luồng điều khiển 20 2.1.2.Slicing dựa vào đồ thị phụ thuộc 23 2.2.static slicing đa thủ tục. 26 2.2.1.Slicing dựa theo đồ thị luồng điều khiển 26 2.2.2. Đồ thị phụ thuộc 29 Chƣơng 3: CÁC KỸ THUẬT DÙNG TRONG PHƢƠNG PHÁP DYNAMIC SLICING 36 3.1: Phƣơng thức dynamic chƣơng trình đơn thủ tục 36 3.1.1: Các khái niệm luồng động 36 3.1.2.Đồ thị phụ thuộc 39 3.2. Dynamic slicing đa thủ tục 42 Chƣơng 4: THỰC NGHIỆM TRÊN CÁC CHƢƠNG TRÌNH SLICER 44 4.1 Chƣơng trình StaticSlicer 44 4.2. Chƣơng trình Kaveri 47 KẾT LUẬN 51 TÀI LIỆU THAM KHẢO 52 Nguyễn Sỹ Linh-Ct1301 12
  13. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng DANH MỤC HÌNH ẢNH Hình 1: (a) Chƣơng trình mẫu, (b) slice slicing của chƣơng trình với tiêu chuẩn (10, product) 18 Hình 2: (a) chƣơng trình mẫu, (b) Dynamic slicing với tiêu chuẩn (n=2, 81, x) 19 Hình 3: Đồ thị CFG của chƣơng trình mẫu trong Hình 1(a) 21 Hình 4: Kết quả của thuật toán của Weiser với chƣơng trình trong Hình 1(a) và slice slicing với tiêu chuẩn C = (10, product) 22 Hình 5: Ví dụ về đồ thị phụ thuộc chƣơng trình 25 Hình 6: Slice slicing của chƣơng trình trong Hình 5 với tiêu chuẩn slicing write(i).25 Hình 7: PDG của chƣơng trình mẫu trong Hình 1(a) 26 Hình 8: (a)Chƣơng trình mẫu.(b)Slice slicing theo weiser.(c)Slice slicing theo HRB 27 Hình 9: Chƣơng trình có cấu trúc đa thủ tục mẫu. 28 Hình 10: Chƣơng trình mẫu mà thủ tục P bị slicing n lần với thuật toán của weiser29 Hình 11: Chƣơng trình có cấu trúc đa thủ tục mẫu khác 31 Hình 12: Đồ thì SDG của chƣơng trình đa thủ tục mẫu trong Hình 11 33 Hình 13: SDG của chƣơng trình mẫu trong Hình 9 35 Hình 14: (a)Đƣờng đi của chƣơng trình mẫu trong Hình 2(a).(b)các khái niệm luồng động cho đƣờng đi đó. 36 Hình 15: (a) Đƣờng đi của chƣơng trình mẫu trong Hình 2(a) với đầu vào n = 1.(b) Các khái niệm luồng động cho đƣờng đi này.(c) Slice dynamic slicing với tiêu chuẩn (n = 1, 88, x).(d) Slice slicing không dừng thu đƣợc nếu bỏ qua quan hệ IR 38 Hình 16: (a) Chƣơng trình mẫu.(b)Đƣờng đi với đầu vào n = 2. 39 Hình 17: Chƣơng trình Qn có O(2n) slice dynamic slicing khác nhau 41 Hình 18: (a) PDG của chƣơng trình trong Hình 2(a), (b)PDG của chƣơng trình trong Hình 16(a), (c)DDG của chƣơng trình Hình 16(a). 42 Nguyễn Sỹ Linh-Ct1301 13
  14. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng DANH MỤC CÁC TỪ VIẾT TẮT Tên viết tắt Diễn giải PDG ( Program Dependence Graph) Đồ thị phụ thuộc chƣơng trình. CFG (Control Flow Graph) Đồ thị luồng điều khiển . REF (is the set of variables whose values Là tập các biến có giá trị đƣợc sử dụng. are used) DEF (is the set of variables whose values Là tập các biến có giá trị đƣợc thay đổi. are changed) INFL (range of influence) Tầm ảnh hƣởng. MOD (variables that may be modified) Biến có thể sửa đổi. USE (variables that may be used) Biến có thể sử dụng. SDG (System Dependence Graph) Đồ thị phụ thuộc hệ thống. DU (Definition- Use) Quan hệ Định nghĩa – Sử dụng. TC (Test- Control) Quan hệ Kiểm thử- Điều khiển. IR (Identity- Relation) Quan hệ Định danh. DDG (Dynamic Dependence Graph) Đồ thị phụ thuộc động. RDDG (Reduced Dynamic Dependence Đồ thị phụ thuộc dynamic rút gọn. Graph) DDSG (Dynamic Denpendence Synthesis Đồ thị tổng hợp phụ thuộc động. Graph) Nguyễn Sỹ Linh-Ct1301 14
  15. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng GIỚI THIỆU Trong sản xuất phần mềm, rất nhiều hoạt động đƣợc thực hiện nhƣ khảo sát, phân tích, thiết kế, Trong đó kiểm thử, bảo trì phần mềm là những công việc có tầm quan trọng nhằm đảm bảo phần mềm hoạt động chính xác, hiểu quả. Tìm hiểu về Program Slicing là một trong những phƣơng pháp nâng cao chất lƣợng phần mềm. Trong quá trình tìm hiểu tài liệu, em đã nghiên cứu, tìm hiểu và trình bày trong đồ án các phƣơng pháp áp dụng trong Progam Slicing nhằm làm rõ một số kỹ thuật đƣợc áp dụng trong đó. Các tác giả nhƣ Weiser, Ottenstein, B. Korel, J. Laski, Horwitz,Reps,Binkley . Là những ngƣời tiên phong nghiên cứu về lĩnh vực này. Các tác giả đã đƣa ra các khái niệm nhƣ Static Slicing, Dynamic Slicing, đồ thị phụ thuộc chƣơng trình, đồ thị phụ thuộc luồng điều khiển,đồ thị phụ thuộc hệ thống Từ đó hình thành một lĩnh vực nghiên cứu mới trong việc đảm bảo chất lƣợng phần mềm. Với kiến thức nhƣ vậy, trong đồ án này em cũng chỉ bƣớc đầu tìm hiểu các kỹ thuật đã đƣợc đề xuất để từ đó hình dung rõ hơn về một khía cạnh trong lĩnh vực sản xuất phần mềm. Do vậy, em chọn đề tài: “Nâng cao chất lƣợng phần mềm bằng kỹ thuật Program Slicing”. Đồ án đƣợc trình bày nhƣ sau: Giới thiệu: GIỚI THIỆU VỀ BÀI TOÁN PROGRAM SLICING Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN TRONG PROGRAM SLICING Trình bày các khái niệm cơ bản đƣợc ứng dụng trong kỹ thuật Program Slicing. Chƣơng 2: CÁC KỸ THUẬT DÙNG TRONG PHƢƠNG PHÁP STATIC SLICING Trong chƣơng này trình bày về các kỹ thuật trong Static Slicing nhƣ: Phƣơng pháp đơn thủ tục và đa thủ tục. Chƣơng 3: CÁC KỸ THUẬT DÙNG TRONG PHƢƠNG PHÁP DYNAMIC SLICING Trong chƣơng này trình bày về các kỹ thuật trong Dynamic Slicing nhƣ: Phƣơng pháp đơn thủ tục và đa thủ tục. Chƣơng 4: THỰC NGHIỆM TRÊN CÁC CHƢƠNG TRÌNH SLICER Chƣơng này trình bày các công cụ trợ giúp trong việc nghiên cứu và tìm hiểu các kỹ thuật Program Slicing. Kết luận: Trình bày các kết quả tìm hiểu trong quá trình thực hiện đồ án. Cuối cùng là phần Tài liệu tham khảo. Nguyễn Sỹ Linh-Ct1301 15
  16. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN TRONG PROGRAM SLICING Theo Weiser [Wei1] Program slicing là một phƣơng pháp đƣợc thực hiện giống nhƣ các lập trình viên có kinh nghiệm gỡ rối chƣơng trình. Khi thực hiện các kỹ thuật trong gỡ rối chƣơng trình, các lập trình viên thƣờng lựa chọn các điểm cần quan tâm gọi là Fix point. Để từ đó dừng chƣơng trình hoặc cô lập một số lệnh để gỡ rối. Công việc gỡ rối này đòi hỏi rất nhiểu công sức cũng nhƣ thời gian. Nếu con ngƣời thực hiện thì có thể lại mắc những lỗi khác. Do vậy, có nhiều quan điểm ủng hộ việc tích hợp program slicer và môi trƣờng gỡ rối. Từ chƣơng trình gốc, kỹ thuật program slicing sẽ tính toán để lựa chọn một tập các câu lệnh liên quan đến một biến hoặc một nhóm các biến nào đó để kiểm soát. Bắt đầu từ một tập hợp các hành vi của chƣơng trình, cắt giảm chƣơng trình mẫu tối thiểu mà vẫn tạo ra hành vi đó. Chƣơng trình rút gọn, đƣợc gọi là một "slice", là một chƣơng trình độc lập đảm bảo tính toàn vẹn của chƣơng trình ban đầu. Một slice của chƣơng trình P, với tiêu chuẩn slicing(n, v) trong đó n là vị trí của câu lệnh trong chƣơng trình (n=1, ,tổng số câu lệnh) và v là biến trong câu lệnh n, chỉ bao gồm các câu lệnh cần thiết của P để nắm bắt đƣợc hành vi của v tại câu lệnh n. Công việc tính toán đƣợc gọi là program slicing. Dƣới đây là một số khái niệm hay dùng trong kĩ thuật program slicing. 1.1 Các định nghĩa Định nghĩa 1: Đồ thị có hƣớng G Đồ thị có hƣớng G là một cặp có thứ tự G:=(V, A), trong đó: - V, tập các đỉnh hoặc nút, - A, tập các cặp có thứ tự chứa các đỉnh, đƣợc gọi là các cạnh có hƣớng hoặc cung. Một cạnh e = (x, y) đƣợc coi là có hƣớng từ x tới y; x đƣợc gọi là điểm đầu/gốc và y đƣợc gọi là điểm cuối/ngọn của cạnh. Định nghĩa 2: Đồ thị luồng điều khiển Một đồ thị luồng điều khiển của chƣơng trình P là một đồ thị trong đó mỗi nút tƣơng ứng với một câu lệnh trong P và mỗi cạnh thể hiện cho Nguyễn Sỹ Linh-Ct1301 16
  17. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng một luồng điều khiển trong P. Đồ thị luồng điều khiển(CFG) chứa hai nút đặc biệt là Start va Stop lần lƣợt thể hiện cho nút bắt đầu và kết thúc chƣơng trình. Định nghĩa 3: Lát cắt chƣơng trình thực thi Với câu lệnh thứ n và biến v, Một slice S của chƣơng trình P đối với tiêu chuẩn slicing(n, v) là một chƣơng trình thực thi bất kì với các đặc tính sau đây: - S có thể thu đƣợc bằng cách không xoá hoặc xoá nhiều câu lệnh từ P. - Khi P dừng với một đầu vào cho trƣớc thì S cũng phải dừng với đầu vào đó, P và S cùng tính toán ra một giá trị của các biến trong V khi câu lệnh tƣơng ứng với nút n đƣợc thực hiện . 1.2 Static slicing Theo Weiser, static slicing đƣợc tính toán bằng cách xác định liên tiếp các tập hợp các biến liên quan của các câu lệnh theo sự phụ thuộc dữ liệu và phụ thuộc luồng điều khiển. Trong phƣơng pháp này, chỉ những thông tin tĩnh đƣợc sử dụng tức là chỉ xem xét mã nguồn mà không quan tâm đến quá trình thực thi chƣơng trình nên slices slicing của Weiser đƣợc gọi là static slicing. Một phƣơng pháp khác của Ottenstein sử dụng đồ thị phụ thuộc chƣơng trình PDG (Program) để thực hiện chƣơng trình. PDG là một đồ thị có hƣớng với các đỉnh tƣơng ứng với các câu lệnh và tính chất điều khiển , các cạnh tƣơng ứng là phụ thuộc dữ liệu và phụ thuộc điều khiển giữa các câu lệnh. Tiêu chuẩn slicing đƣợc xác định là một đỉnh trong PDG mà slices clicing bao gồm tất cả các đỉnh trong PDG mà từ đỉnh của tiêu chuẩn slicing có thể đi tới. Một phƣơng pháp khác đƣợc đƣa ra bởi Bergeretti và Carre sử dụng quan hệ luồng thông tin từ một chƣơng trình hƣớng cú pháp. Các phƣơng pháp này tính toán tập các câu lệnh và xác định điều khiển bằng cách duyệt ngƣợc chƣơng trình bắt đầu từ tiêu chuẩn slicing nên slices slicing sinh ra gọi là static slicing ngƣợc. Bergeretti và Carre sau đó giới thiệu static slicing tiến gồm tất cả các câu lệnh và tính chất điều khiển phụ thuộc vào tiêu chuẩn slices. Một câu lệnh bị phụ thuộc vào tiêu chuẩn slices nếu các giá trị đƣợc tính toán tại câu lệnh đó phụ thuộc vào giá trị đƣợc tính toán tại tiêu chuẩn slices, hoặc giá trị đƣợc tính toán tại tiêu chuẩn slices có tính chất quyết định sự thi hành của câu lệnh đó. Nguyễn Sỹ Linh-Ct1301 17
  18. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 1: (a) Chƣơng trình mẫu, (b) slice slicing của chƣơng trình với tiêu chuẩn (10, product) Static slicing có thể đƣợc sử dụng để xác định các bộ phận của chƣơng trình có tiềm năng đóng góp vào sự tính toán của các chức năng đƣợc lựa chọn cho tất cả các chƣơng trình đầu vào có thể. Static slicing là hữu ích để đạt đƣợc một sự hiểu biết chung của các bộ phận của chƣơng trình đóng góp vào sự tính toán để các chức năng đƣợc lựa chọn. Mặc dù static slicing có nhiều lợi thế trong quá trình theo dõi chƣơng trình, static slicing thƣờng xuyên vẫn còn chƣơng trình con lớn vì tính toán không chính xác của những slice. Ngoài ra static slicing không thể đƣợc sử dụng trong quá trình theo dõi về thực hiện chƣơng trình. 1.3 Dynamic slicing Khái niệm dynamic slicing ban đầu đƣợc giới thiệu bởi Kroel và Laski là một biến thể của phƣơng pháp phân tích luồng ngƣợc của Balzer. Phân tích luồng ngƣợc quan tâm đến luồng thông tin trong chƣơng trình với một giá trị đầu vào cụ thể. Ngƣời dùng duyệt đồ thị biểu diễn phụ thuộc điều khiển và phụ thuộc dữ liệu giữa các câu lệnh trong chƣơng trình. Ví dụ nhƣ giá trị đƣợc tính tại câu lệnh n phụ thuộc vào giá trị tính toán tại câu lệnh t thì ngƣời dùng phải duyệt ngƣợc từ đỉnh tƣơng ứng với câu lệnh n đến đỉnh của câu lệnh t. Lịch sử thực hiện là đƣờng đi chứa một chuỗi các sự xuất hiện của các câu lệnh và tính chất điều khiển. Trong phƣơng pháp dynamic slicing thì chỉ có các sự phụ thuộc xuất hiện trên một lịch sử thực hiện cụ thể của chƣơng trình mới đƣợc cho vào slice slicing. Một tiêu chuẩn slice là bộ ba (x, Iq, V)trong đó x thể hiện đầu vào của chƣơng trình, sự xuất hiện của câu lệnh Iq là thành phần thứ q trong đƣờng đi, V là tập hợp các biến trong chƣơng trình. Sự khác biệt giữa static slicing và Nguyễn Sỹ Linh-Ct1301 18
  19. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng dynamic slicing là dynamic slicing sử dụng với giả thiết có đầu vào cố định cụ thể còn static slicing không quan tâm đến đầu vào. Hình 2: (a) chƣơng trình mẫu, (b) Dynamic slicing với tiêu chuẩn (n=2, 81, x) Ví dụ 1.3.1: Trong Hình 2 chỉ ra slice dynamic slicing của chƣơng trình mẫu với tiêu chuẩn slicing C = (n = 2, 81, x) trong đó 81 thể hiện lần xuất hiện thứ nhất của câu lệnh 8 trong lịch sử thực hiện của chƣơng trình. Với đầu vào n = 2 thì thứ tự thực hiện các câu lệnh của chƣơng trình là {11, 22, 33, 44, 65, 76, 37, 48, 59, 710, 311, 812}, các chỉ số bên trên chỉ thứ tự câu lệnh thực hiện(trong thứ tự này thì câu lệnh số 8 xuất hiện lần đầu ở vị trí thứ 12). Với đầu vào n = 2 thì vòng lặp thực hiện hai lần với các phép gán là x: = 18 và x: = 17. Trong vòng lặp lần thứ hai thì câu lệnh gán x: = 17 đƣợc thực hiện thay thế cho phép gán trong câu lệnh x: = 18 thực hiện trong vòng lặp thứ nhất nên câu lệnh gán x: = 18 trong nhánh else của câu lệnh if không có trong slice slicing. Trong khi đó thì slice static slicing với tiêu chuẩn C = (8, x) bao gồm toàn bộ chƣơng trình. Nguyễn Sỹ Linh-Ct1301 19
  20. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Chƣơng 2: CÁC KĨ THUẬT DÙNG TRONG PHƢƠNG PHÁP STATIC SLICING 2.1.Static slicing đơn thủ tục. 2.1.1. Slicing dựa vào đồ thị luồng điều khiển Phƣơng pháp static sling dựa trên đồ thị luồng điều khiển đƣợc giới thiệu bởi Weiser. Một tiêu chuẩn slice trong phƣơng pháp này là một bộ C=(n, V)trong đó n là một nút trong đồ thị luồng điều khiển CFG của chƣơng trình và V là một tập con các biến của chƣơng trình. Một slice slicing S đối với tiêu chuẩn C=(n, V) là một tập con các câu lệnh trong P thỏa mãn tính chất: khi P dừng với một giá trị đầu vào cho trƣớc thì S cũng dừng với đầu vào đó, P và S cùng tính toán ra một giá trị của các biến trong V khi câu lệnh tƣơng ứng với nút n đƣợc thực hiện. Đồ thị luồng điều khiển CFG là một đồ thị có hƣớng với mỗi nút biểu diễn một câu lệnh hay tính chất điều khiển trong chƣơng trình. Một cạnh từ nút i đến nút j thể hiện cho luồng điều khiển từ i đến j. Đồ thị CFG chứa hai nút đặc biệt là Start và Stop lần lƣợt thể hiện cho nút bắt đầu và kết thúc chƣơng trình. Tại nút i tồn tại hai tập hợp đó là: Tập DEF (i) bao gồm tất cả các biến mà giá trị của nó bị thay đổi tại nút i. Tập REF(i) bao gồm tất cả các biến đƣợc tham chiếu tại nút i. Trong đồ thị luồng điều khiển thì luồng điều khiển có hai loại là phụ thuộc dữ liệu và phụ thuộc điều khiển. Nút j là phụ thuộc luồng vào nút i nếu tồn tại một biến x sao cho: x DEF(i) x REF(j) Tồn tại một đƣờng đi từ i đến j mà không có sự ghi dữ liệu lên biến x. Một nút i trong đồ thị CFG là nút cha của một nút j nếu tất cả mọi đƣờng đi từ nút i đến nút Stop đều phải qua nút j. Một nút j là phụ thuộc điều khiển vào nút i nếu: Tồn tại một đƣờng đi P từ i đến j mà có u ≠ i, j trong P là cha của j i không phải là cha của j Trong chƣơng trình có cấu trúc thì các câu lệnh trong các nhánh của câu lệnh if và while là phụ thuộc điều khiển vào tính chất điều khiển. Nguyễn Sỹ Linh-Ct1301 20
  21. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 3: Đồ thị CFG của chƣơng trình mẫu trong Hình 1(a) Ví dụ 2.1.1.1: Hình 3 chỉ ra CFG của chƣơng trình trong Hình 1(a). Nút 7 là phụ thuộc luồng vào nút 4 vì nút 4 định nghĩa biến product, nút 7 tham chiếu biến product và tồn tại đƣờng đi 4 5 6 7 không có định nghĩa biến product. Nút 7 là phụ thuộc điều khiển vào nút 5 vì tồn tại đƣờng đi 5 6 7 có nút 6 là cha của nút 7 và nút 5 không là cha của nút 7. Slice slicing nhỏ nhất đƣợc tính bằng cách tính các tập biến liên quan ở từng nút trong đồ thị CFG. Đầu tiên, các biến liên quan trực tiếp đƣợc xác định bằng cách lấy ra các phụ thuộc dữ liệu. Ký hiệu i CFG j thể hiện cho tồn tại một cạnh trong CFG từ nút i đến nút j. Với tiêu chuẩn cắt C = (n, V), tập các biến liên quan trực tiếp tại nút i của CFG kí hiệu là (i). Ta duyệt ngƣợc đồ thị CFG để tìm ra các biến liên quan. Tập đƣợc xác định nhƣ sau: 0 RC (i) = V khi i=n. 0 0 Với mọi i CFG j, RC (i) chứa tất cả các biến v sao cho v RC (j) và v 0 DEF(i), hoặc v REF(i) và DEF(i) ∩ RC (j) ≠ φ. k+1 Tập các câu lệnh liên quan trực tiếp S C là một tập các nút i xác định một biến v liên quan tại nút liền kề sau j và i trong CFG: Các biến đƣợc tham chiếu trong tính chất điều khiển của câu lệnh if hay while là liên quan gián tiếp nếu tồn tại ít nhất một câu lệnh trong thân của nó là liên quan. Nguyễn Sỹ Linh-Ct1301 21
  22. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Tầm ảnh hƣởng IFNL(b) của câu lệnh nhánh b là liên quan gián tiếp nếu có i và i nằm trong tầm ảnh hƣởng IFNL(b) của b. Các câu lệnh nhánh liên quan do ảnh hƣởng của chúng lên nút i nằm trong đƣợc xác định nhƣ sau: k+1 k Tập các biến liên quan gián tiếp S C chứa các nút trong B C cùng với nút i xác định một biến liên quan đến một liền kề sau j: k+1 k+1 Các tập R C và S C là các tập không giảm lần lƣợt của các biến và câu k+1 lệnh trong chƣơng trình. Quá trình tính toán trên đƣợc tiếp tục đến khi S C cố định. k+1 Các câu lệnh trong S C thu đƣợc là các câu lện có trong slice slicing mong muốn . Hình 4: Kết quả của thuật toán của Weiser với chƣơng trình trong Hình 2(a) và slice slicing với tiêu chuẩn C = (10, product) Thuật toán static program slicing sử dụng đồ thị luồng dữ liệu của Weiser tính toán ra slice static slicing theo các bƣớc sau: Bƣớc 1: Xác định các cạnh phụ thuộc luồng và phụ thuộc điều khiển để vẽ đồ thị luồng điều khiển cho chƣơng trình. Bƣớc 2: Xác định các tập biến và các tập câu lệnh liên quan trực tiếp và gián tiếp đến câu lệnh và biến trong câu lệnh slice thông qua việc tính 0 0 k+1 k+1 toán các tập hợp R C , S C , R C , S C Nguyễn Sỹ Linh-Ct1301 22
  23. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Bƣớc 3: Lặp lại các bƣớc tính toán các tập liên quan ở bƣớc 2 trên để k+1 k+1 tính toán tập cố định S C . Các câu lệnh trong S C là các câu lệnh có trong slice program slicing mong muốn. Ví dụ 2.1.1.2: Xét chƣơng trình trong Hình 3(a) với tiêu chuẩn slice(10, product). Hình 4 chỉ ra các tập DEF, REF, INFL và tập các biến liên quan tính theo thuật toán của Weiser. Đồ thị CFG của chƣơng trình chỉ ra trong Hình 3.Từ các 0 0 1 thông tin trên hình vẽ ta tính đƣợc S C = {2, 4, 7, 8}, B C ={5}, S C ={1, 2, 4, 5, 7, 1 8}. Trong ví dụ này, tập cố định của tập các câu lệnh liên quan gián tiếp S C đạt đƣợc là tƣơng ứng với slice program slicing trong hình1(b). Câu lệnh write(product) không có trong slice slicing. Thật ra câu lệnh xuất ra không có trong slice slicing vì: (i) DEF của nó rỗng nên không có câu lệnh nào phụ thuộc dữ liệu vào nó và (ii) không có câu lệnh nào phụ thuộc điều khiển vào một câu lệnh xuất. 2.1.2.Slicing dựa vào đồ thị phụ thuộc Ottenstein đƣa kĩ thuật static program slicing đơn thủ tục dựa trên đồ thị phụ thuộc chƣơng trình. Các câu lệnh của chƣơng trình tạo thành các đỉnh của đồ thị phụ thuộc, các cạnh tƣơng ứng với phụ thuộc dữ liệu và phụ thuộc điều khiển giữa các câu lệnh. Đồ thị PDG của chƣơng trình P kí hiệu là GP là một đồ thị có hƣớng mà các đỉnh của Gp biểu diễn các câu lệnh và tính chất điều khiển xuất hiện trong chƣơng trình P, trong GP có một đỉnh đặc biệt gọi là đỉnh vào. GP là một đa đồ thị nên có thể có nhiều hơn một cạch giữa hai đỉnh. Đồ thị GP chứa một cạch phụ thuộc điều khiển từ đỉnh u đến đỉnh v kí hiệu là u cv nếu xảy ra một trong các điều sau đây: u là đỉnh vào và v biểu diễn cho một câu lệnh của P không lồng trong bất kỳ vòng lặp hay điều kiện nào. Các cạnh này đƣợc dán nhãn True. u biểu diễn cho một tính chất điều khiển và v biểu diễn một câu lệnh của P ở ngay trong vòng lặp hay điệu kiện biểu diễn bởi u. Nếu u là tính chất điều khiển của một vòng lặp while thì cạch u cv đƣợc gán nhãn True, nếu u là tính chất của một câu lệnh điệu kiện thì cạch u cv là đƣợc gán nhãn True hay False lần lƣợt tùy theo v xuất hiện trong nhánh then hay nhánh else. Một cạnh phụ thuộc dữ liệu từ đỉnh u đến đỉnh v hàm ý chỉ ra sự tính toán của chƣơng trình có thế bị thay đổi nếu thứ tự tƣơng đối của các thành phần đại diện của u và v bị đảo ngƣợc lại. Các cạn h phụ thuộc dữ liệu của PDG đƣợc xác định bằng cách sử dụng phân tích luồng dữ liệu. Một PDG chứa một cạnh phụ thuộc luồng từ đỉnh u đến đỉnh v ký hiệu là u fv nếu thỏa mãn các điều kiện sau đây: Nguyễn Sỹ Linh-Ct1301 23
  24. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 1. u là đỉnh định nghĩa biến x. 2. v là một đỉnh sử dụng biến x. 3. Đƣờng đi từ u đến v không có định nghĩa nào của x. Các phụ thuộc luồng đƣợc chia thành hai loại là lặp mang và lặp độc lập. Một phụ thuộc luồng lặp mang u f v đƣợc truyền bởi vòng lặp L, ký hiệu là u lc(L)v nếu ngoài có 3 điều kiện (1), (2), (3) trên thì phải thỏa mãn thêm các điều kiện sau: 4. Có một đƣờng đi thỏa mãn điều kiện thứ (3)bên trên và bao gồm một cạnh ngƣợc đến tính chất điều khiển của vòng lặp L. 5. Cả hai u và v đều nằm trong vòng lặp L. Một phụ thuộc luồng u f v là lặp độc lập kí hiệu là u li v ngoài các điều kiện (1), (2), (3) bên trên thì phải thỏa mãn thêm các điều kiện sau: 6. Có một đƣờng đi thỏa mãn điều kiện thứ (3)ở trên và không có cạnh ngƣợc đến tính chất điều khiểu của vòng lặp L. 7. Cả hai u và v đều nằm trong vòng lặp L. Horwitz và Reps đã chỉ ra rằng các biến thể PDG là đầy đủ tức là nếu hai chƣơng trình có cùng PDG thì chúng tƣơng đƣơng nhau. Điều đó có nghĩa là khi cho cùng một trạng thái đầu vào thì chúng tính ra cùng giá trị cho tất cả các biến hay chúng cùng chạy mà không kết thúc. Ví dụ 2.1.2.1: Hình 5 chỉ ra một chƣơng trình và biểu đồ phụ thuộc vào chƣơng trình đó. Các mũi tên đậm thể hiện các cạnh phụ thuộc điều khiển, mũi tên nhạt thể hiện các cạnh phụ thuộc luồng lặp độc lập, mũi tên nhạt với dấu gạch ngang thể hiện các cạnh phụ thuộc luồng lặp mang. Nguyễn Sỹ Linh-Ct1301 24
  25. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 5: Ví dụ về đồ thị phụ thuộc chƣơng trình Tiêu chuẩn slicing đối với phƣơng pháp static slicing sử dụng đồ thị phụ thuộc PDG chính là một đỉnh trong PDG. Ta kí hiệu các slice slicing của GP đối với đỉnh s ký hiệu slice(G, s). Slice(G, s) chứa tất cả các đỉnh có thể đi tới đỉnh s thông qua các cạnh phụ thuộc luồng hay cạnh phụ thuộc điều khiển. Tập các đỉnh của Slice(G,s) kí hiệu là V(Slice(G, s)) đƣợc xác định nhƣ sau: V(Slice(G, s))={v | v V(G) v *cf s}. Tập các cạnh của Slice(G, s) kí hiệu là E(Slice(G, s)) đƣợc xác định nhƣ sau: E(Slice(G, s))={v fu | (v fu) E(G) v, u V(Slice(G, s))} {(v cu) E(G) v, u V(Slice(G, s))}. Ví dụ 2.1.2.2: Hình 6 chỉ ra slice slicing của chƣơng trình theo đồ thị phụ thuộc của chƣơng trình trong Hình 5 với tiêu chuẩn slice write(i). Hình 6: Slice slicing của chƣơng trình trong Hình 5 với tiêu chuẩn slicing write(i). Nguyễn Sỹ Linh-Ct1301 25
  26. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ví dụ 2.1.2.3: Trong Hình 7 chỉ ra đồ thị PDG của chƣơng trình trong Hình 1(a). Trong hình này thì cạnh đậm biểu diễn phụ thuộc điều khiển cà cạnh nhạt biểu diễn phụ thuộc luồng. Các ô màu đậm chỉ ra các đỉnh trong slice slicing với tiêu chuẩn write(product). Hình 7: PDG của chƣơng trình mẫu trong Hình 1(a) 2.2.static slicing đa thủ tục. 2.2.1.Slicing dựa theo đồ thị luồng điều khiển Weiser chỉ ra hai bƣớc để tính toán slice program slicing đa thủ tục dựa theo đồ thị luồng điều khiển nhƣ sau: Bƣớc một: trong chƣơng trình có nhiều thủ tục thì slice slicing đƣợc tính toán với thủ tục P chứa tiêu chuẩn slicing ban đầu. Ảnh hƣởng của lời gọi thủ tục lên tập các biến liên quan đƣợc tính bằng cách sử dụng thông tin tổng hợp đa thủ tục. Với một thủ tục P, thông tin này chứa tập MOD(P) của các biến bị thay đổi bởi P và tập USE(P) của các biến đƣợc sử dụng bởi P. Một lời gọi đến thủ tục P đƣợc xem nhƣ là nó xác định mọi biến trong MOD(P) và sử dụng mọi biến trong USE(P) nơi mà tham số thực thay thế cho tham số hình thức. Thuật toán của Weiser không chính xác do lấy các câu lệnh mà tham số ra phụ thuộc vào tham số vào. Nguyễn Sỹ Linh-Ct1301 26
  27. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ví dụ 2.2.1.1: Trong Hình 8(a) chỉ ra một chƣơng trình mẫu chỉ rõ vấn đề trên. Thuật toán slicing đa thủ tục sẽ tính ra slice slicing đƣợc thể hiện ở Hình 8(b) bằng cạch sử dụng các tập MOD(P) và USE(P). Slice slicing này chứa câu lệnh a:=17 là do sự phụ thuộc giả giữa biến a trƣớc lời gọi và biến d sau lời gọi. Hình 8: (a)Chƣơng trình mẫu. (b)Slice slicing theo weiser. (c)Slice slicing theo HRB Bƣớc hai: Tiêu chuẩn slicing mới đƣợc sinh ra cho hai loại thủ tục: (i) những thủ tục Q đƣợc gọi bởi P và (ii) những thủ tục R gọi đến P. Bƣớc hai này sẽ đƣợc lặp lại đến khi không còn tiêu chuẩn mới đƣợc sinh ra. Việc sinh các tiêu chuẩn mới đƣợc hình thức hóa bằng công thức UP(C) và DOWN(C) ánh xạ một tập tiêu chuẩn C trong thủ tục P đến lần lƣợt các tập tiêu chuẩn trong các thủ tục R gọi P và trong các thủ tục Q đƣợc gọi bởi P. Tập UP(C) ={(nQ, vQ)} trong đó nQ là câu lệnh cuối cùng của Q và vQ là biến có liên quan trong P và trong phạm vi ảnh hƣởng của Q (tham số hình thức thay thế cho tham số thực). Tập DOWN(C) ={(nR, vR)} trong đó nR là một lời gọi P trong R và vR là tập biến liên quan trong câu lệnh đầu tiên của P trong tầm phạm vi ảnh hƣởng của R(tham số thực thay thế cho tham số hình thức). Tập kín (UP DOWN)*(C) chứa các tiêu chuẩn slice cần thiết để tính toán một slice slicing với tiêu chuẩn slicing ban đầu C. Ta slicing chƣơng trình theo tập tiêu chuẩn này sẽ đƣợc slice program slicing mong muốn Nguyễn Sỹ Linh-Ct1301 27
  28. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 9: Chƣơng trình có cấu trúc đa thủ tục mẫu. Ví dụ 2.2.1.2: Slice slicing đƣợc tính toán với giá trị cuối của biến product trong chƣơng trình ở Hình 9. Giả sử ta phải slicing với tiêu chuẩn ban đầu là (10, product). Trong bƣớc 1 của thuật toán Weiser slice slicing gồm tất cả các dòng của chƣơng trình Main trừ dòng 3 và dòng 6. Lời gọi thủ tục Multiply(product, i) và Add(i, 1) cũng có trong slice slicing vì: (i)các biến product và i liên quan đến các lời gọi thủ tục đó , (ii) sử dụng phân tích luồng thông tin đa thủ tục ta có MOD(Add) = {a}, USE(Add) = {a, b}, MOD(Multiply) = {c}, USE(Multiply) = {c, d}. Với tiêu chuẩn ban đầu trong chƣơng trình Main, ta có UP({10, product}) = DOWN({10, product}) chứa tiêu chuẩn (11, {a}) và (17, {c, d}). Kết quả của việc cắt thủ tục Add với thủ tục(11, {a}) và thủ tục Multiply với tiêu chuẩn (17, {c, d}) chính là cả hai thủ tục đó. Lƣu ý rằng các lời gọi Add ở dòng 15, 16 sinh ra tiêu chuẩn mới (11, {a, b}) và sau đó slicing lại thủ tục Add. Horwitz, Reps và Binkley đã chỉ ra rằng phƣơng pháp slicing đa thủ tục của Weiser không chính xác vì phƣơng pháp này gặp vấn đề về ngữ cảnh gọi. Vấn đề ngữ cảnh gọi gặp phải khi tính toán xuống các thủ tục Q đƣợc gọi bởi thủ tục P. Nhƣng khi duyệt ngƣợc đồ thị luồng điều khiển thì sẽ đi lên mọi thủ tục gọi Q mà không chỉ có P. Điều này tƣơng đƣơng với các đƣờng thực hiện vào Q từ P và ra Q từ một thủ tục P’ khác. Các đƣờng thực hiện đó là không thực thi đƣợc nên phƣơng pháp slicing này sẽ tạo ra slice slicing không chính xác . Ví dụ 2.2.1.3: Trong Hình 9 chỉ ra vấn đề ngữ cảnh gọi. Khi dòng 11 có trong slice slicing, tiêu chuẩn mới đƣợc sinh ra cho tất cả lời gọi đến Add. Các lời gọi đó là các lời gọi tại các dòng 8, 15, 16 và cũng có lời gọi Add(sum, i) ở dòng 6. Tiêu chuẩn mới (6, {sum, i}) đƣợc sinh ra sẽ cho câu lệnh 3 và 6 vào trong slice slicing là cho slice slicing chƣơng trình thu đƣợc toàn bộ chƣơng trình. Nguyễn Sỹ Linh-Ct1301 28
  29. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Vấn đề ngữ cảnh gọi của thuật toán Weiser sẽ đƣợc giải quyết nếu các tiêu chuẩn trong tập UP chỉ đƣợc quan tâm khi có các thủ tục gọi đến thủ tục P chứa tiêu chuẩn khởi tạo. Khi không có thủ tục nào gọi đến thủ tục P thì chỉ có tập DOWN là cần thiết cho việc tính toán slice slicing. Hình 10: Chƣơng trình mẫu mà thủ tục P bị slicing n lần với thuật toán của Weiser Ví dụ 2.2.1.4: Trong Hình 10, L kí hiệu cho số dòng của câu lệnh write(z) và M là số dòng câu lệnh cuối của thủ tục P. Tính toán slice slicing với tiêu chuẩn (L, {z} yêu cầu n vòng lặp trong thân của vòng lặp while. Trong vòng lặp thứ i thì các biến x1, ., xi sẽ liên quan tại đỉnh gọi gây ra bao gồm tiêu chuẩn (m, {y1, ., yi}) trong DOWN(Main). Nếu ta không chú ý khi lấy nhóm tiêu chuẩn trong DOWN(Main) thì thủ tục P sẽ bị slicing n lần. 2.2.2. Đồ thị phụ thuộc Horwitz, Reps và Binkley sử dụng phƣơng pháp slicing dựa vào đồ thị phụ thuộc hệ thống SDG để slicing chƣơng trình đa thủ tục có cấu trúc. Từ “hệ thống” trong khái niệm đồ thị phụ thuộc hệ thống dùng để nhấn mạnh một chƣơng trình có nhiều thủ tục. Một SDG chứa một PDG của chƣơng trình chính và các đồ thị phụ thuộc thủ tục của mỗi thủ tục đƣợc kết nối bởi các cạnh phụ thuộc lƣờng và cạnh phụ thuộc điều khiển giữa các thủ tục. Với mỗi câu lệnh gọi thì tƣơng ứng có một đỉnh gọi trong SDG. Tham số truyền đƣợc biểu diễn bằng cách sử dụng bốn loại đỉnh tham số. Nguyễn Sỹ Linh-Ct1301 29
  30. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ở phƣơng diện thủ tục gọi, tham số truyền đƣợc biểu diễn bằng đỉnh thực trong và đỉnh thực ngoài mô hình việc sao chép các biến thực lần lƣợt đến từ các biến tạm, đƣợc phụ thuộc điều khiển vào các đỉnh gọi Ở phƣơng diện các thủ tục đƣợc gọi, tham số truyền đƣợc biểu diễn bằng đỉnh hình thức trong và hình thức ngoài mô hình việc sao chép các biến hình thức lần lƣợt đến từ các biến tạm, đƣợc phụ thuộc điều khiển vào đỉnh vào của thủ tục. Tại các câu lệnh gọi thủ tục thì các tham số truyền theo tham trị đƣợc xây dựng theo các bƣớc sau: Thủ tục gọi sao chép các tham số thực trong của nó đến các biến tạm trƣớc khi gọi nó. Các tham số hình thức trong của thủ tục gọi đƣợc khởi tạo tƣơng ứng với các biến tạm. Trƣớc khi trở lại, thủ tục đƣợc gọi sao chép giá trị cuối cùng của tham số hình thức ngoài đến các biến tạm. Sau khi trở lại, thủ tục gọi cập nhật các tham số thực ngoài bằng cách sao chép các giá trị tƣơng ứng với các biến tạm. Đồ thị phụ thuộc thủ tục tạo thành một SDG bằng cách sử dụng ba loại cạnh mới sau: 1. Cạnh gọi là các cạnh phụ thuộc điều khiển giữa đỉnh gọi trong đỉnh gọi và đỉnh vào thủ tục tƣơng ứng trong đồ thị phụ thuộc thủ tục. 2. Cạnh tham số trong giữa các đỉnh hình thức trong tại thủ tục đƣợc gọi và đỉnh thực trong tại đỉnh gọi 3. Cạnh tham số ngoài giữa các đỉnh hình thức ngoài tại thủ tục đƣợc gọi và đỉnh thực ngoài tại đỉnh gọi. Cạnh gọi là một loại cạnh mới của cạnh phụ thuộc điều khiển. Cạnh tham số trong và cạnh tham số ngoài là hai loại cạnh mới của cạnh phụ thuộc dữ liệu. Thuận lợi của phƣơng pháp tính này là các cạnh phụ thuộc luồng có thể đƣợc tính toán theo cách thông thƣờng nhƣ cách phân tích luồng dữ liệu trong đồ thị luồng điều khiển của thủ tục. Đồ thị luồng điều khiển chứa các nút tƣơng tự nhƣ các đỉnh thực trong, đỉnh thực ngoài, đỉnh hình thức trong, đỉnh hình thức ngoài của đồ thị phụ thuộc thủ tục. Một đồ thị luồng dữ liệu của thủ tục bắt đầu với một chuỗi các câu lệnh gán sao chép các giá trị từ các biến tạm gọi đến các tham số hình thức và kết thúc với một chuỗi các câu lệnh gán sao chép giá trị từ tham số hình thức trở lại các biến tạm. Mỗi câu lệnh gọi trong thủ tục đƣợc biểu diễn trong đồ thị luồng điều khiển bằng một chuỗi các câu lệnh gán sao chép giá trị từ tham số thực đến các biến Nguyễn Sỹ Linh-Ct1301 30
  31. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng tạm gọi, tiếp theo là một chuỗi các câu lệnh gán sao chép giá trị trở lại các biến tạm từ các tham số thực. Hình 11: Chƣơng trình có cấu trúc đa thủ tục mẫu khác Gọi GP là đồ thị phụ thuộc thủ tục của thủ tục P. Các đỉnh tham số liên kết với lời gọi từ thủ tục P đến thủ tục Q đƣợc xác định nhƣ sau: Trong GP, các đỉnh bên dƣới của đỉnh gọi trong đỉnh gọi biểu diễn lời gọi đến Q, có một đỉnh thực trong tƣơng ứng với tham số thực e của lời gọi đến Q. Đỉnh thực trong đƣợc gán nhãn r_in: =e trong đó r là tên tham số hình thức tƣơng ứng. Với mỗi tham số thực a là một biến có một đỉnh thực ngoại đƣợc gán nhãn a: = r_out trong đó r là tham số hình thức tƣơng ứng. Gọi GQ là đồ thị phụ thuộc thủ tục của thủ tục Q. Các đỉnh tham số liên kết với đỉnh vào của thủ tục Q và kết thúc thủ tục Q đƣợc xác định nhƣ sau: 1. Với mỗi tham số hình thức r của Q thì GQ chứa một đỉnh hình thức trong và một đỉnh hình thức ngoài. Các đỉnh đó đƣợc gán nhãn theo thứ tự là r: =r_in và r_out: =r. Nguyễn Sỹ Linh-Ct1301 31
  32. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ví dụ 2.2.2.1: Hình 12 thể hiện đồ thị phụ thuộc hệ thống của chƣơng trình mẫu trong Hình 11. Đồ thị này gồm các đồ thị phụ thuộc thủ tục đƣợc kết nối với nhau thông qua các cạnh tham số trong, tham số ngoài, và cạnh gọi. Các cạnh điều khiển trong hình không có nhãn vì ta mặc định chúng có nhãn True. Vấn đề ngữ cảnh gọi của phƣơng pháp static program slicing đa cấu trúc của Weiser có thể đƣợc mnh họa đồ thị thể hiện trong Hình 12. Trong hình này có một đƣờng đi từ đỉnh của thủ tục Main gán nhãn i: =y_out mặc dù giá trị của i sau lời gọi đến thủ tục A độc lập vơi giá trị của sum trƣớc khi gọi. Đƣờng đi cụ thể nhƣ sau: Main: x_in: =sum A: x: = x_in A: a_in: =x Add: a: = a_in Add: a: =a+b Inc: z: =a_out Inc: z_out: = z A: y: = z_out A: y_out: = y Main: i: =y_out. Nguyễn Sỹ Linh-Ct1301 32
  33. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 12: Đồ thì SDG của chƣơng trình đa thủ tục mẫu trong Hình 11 Nguyên nhân gây ra vấn đề này là không phải tất cả các đƣờng đi trong đồ thị tƣơng ứng với đƣờng đi có thể thực thi. Ví dụ nhƣ đƣờng đi từ đỉnh x_in: = sum Nguyễn Sỹ Linh-Ct1301 33
  34. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng của thủ tục Main đến đỉnh i: =y_out của Main tƣơng ứng với thủ tục Add đƣợc gọi bởi thủ tục A, nhƣng trở lại thủ tục Increment. Để khắc phục vấn đề này, chúng ta thêm một loại cạnh bổ sung vào đồ thị phụ thuộc hệ thống biểu diễn phụ thuộc ngoài do ảnh hƣởng của các lời gọi thủ tục. Ví dụ, đối với đồ thị thể hiện trong Hình 12, có cạnh phụ thuộc ngoài từ đỉnh x_in: = sum của thủ tục Main đến đỉnh sum: = x_out của Main. Sự phụ thuộc này tồn tại vì giá trị của biến sum sau khi gọi đến A phụ thuộc vào giá trị của sum trƣớc khi các cuộc gọi đến A. Giả sử ta phải tính toán slice slicing chƣơng trình theo đỉnh s nằm trong thủ tục P. Phƣơng pháp static slicing đa thủ tục sử dụng đồ thị phụ thuộc hệ thống tính toán slice slicing bằng cách duyệt đồ thị SDG theo hai bƣớc: Bƣớc một: Xác định các đỉnh trong thủ tục P mà s đi tới nhƣng chƣa đi vào trong các thủ tục Q đƣợc gọi bởi P. Các cạnh phụ thuộc đa thủ tục ngoài chỉ từ đỉnh gọi đến đỉnh vào của thủ tục nhƣng chƣa thật sự đi vào thủ tục đƣợc gọi. Bƣớc hai: Thuật toán cắt tiếp tục với các đỉnh vào của các thủ tục đƣợc gọi đã chỉ ra ở bƣớc một và xác định các đỉnh còn lại trong slice slicing. Ví dụ 2.2.2.2: Hình 13 chỉ ra đồ thị SDG cho chƣơng trình đa thủ tục trong Hình 9. Trong hình này, phân tích luồng thông tin đa thủ tục đƣợc sử dụng để loại bỏ các đỉnh của tham số thứ hai của thủ tục Add và Multiply. Trong hình thì cạch nhạt thể hiện phụ thuộc luồng, cạnh đậm thể hiện phụ thuộc điều khiển, nét đứt nhạt thể hiện các lời gọi, phụ thuộc tham số trong và phụ thuộc tham số ngoài, nét đứt đậm thể hiện phụ thuộc luồng đa thủ tục ngoài. Nguyễn Sỹ Linh-Ct1301 34
  35. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình2.2.2. 1: SDG của chƣơng trình mẫu trong Hình 2.2.1.2 Nguyễn Sỹ Linh-Ct1301 35
  36. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Chƣơng 3: CÁC KỸ THUẬT DÙNG TRONG PHƢƠNG PHÁP DYNAMIC SLICING 3.1: Phương thức dynamic chương trình đơn thủ tục 3.1.1: Các khái niệm luồng động Trong phƣơng pháp dynamic slicing chƣơng trình có cấu trúc đơn thủ tục, Korel và Laski coi lịch sử thực hiện chƣơng trình là một đƣờng đi chứa một chuỗi các sự xuất hiện của các câu lệnh và tính chất điều khiển. Các nhãn bên trên đƣợc sử dụng để phân biệt các lần xảy ra khác nhau của một câu lệnh trong lịch sử thực hiện. Giả sử có lịch sử thực hiện sau { 11, 22, 33, 44, 75, 46, 87} thì câu lệnh 4 xuất hiện hai lần ở vị trí thứ 4 và thứ 6 trong lịch sử thực hiện. Hình 14: (a)Đƣờng đi của chƣơng trình mẫu trong Hình 2(a). (b)các khái niệm luồng động cho đƣờng đi đó. Ví dụ 3.1.1.1: Hình 14 thể hiện đƣờng đi của chƣơng trình trong Hình 2(a) với đầu vào n = 2. Đƣờng đi của lịch sử thực hiện của chƣơng trình là{11, 22, 33, 44, 65, 76, 37, 48, 59, 710, 311, 812}. Một tiêu chuẩn dynamic slicing trong kĩ thuật slicing này là một bộ ba (x, Iq, V)trong đó x thể hiện đầu vào của chƣơng trình, sự xuất hiện của câu lệnh Iq là thành phần thứ q trong lịch sử thực hiện. V là tập con các biến trong chƣơng trình. Các slice dynamic slicing phải thỏa mãn các yêu cầu sau: (i) câu lệnh tƣơng ứng với tiêu chuẩn Iq phải có trong slice slicing, và (ii) nếu một vòng lặp xảy ra trong slice slicing thì nó đƣợc thực hiện cùng số lần nó đƣợc thực hiện trong chƣơng trình ban đầu. Nguyễn Sỹ Linh-Ct1301 36
  37. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Korel và Laski giới thiệu ba khái niệm luồng động hình thức hóa sự phụ thuộc giữa các lần xảy ra của các câu lệnh trong đƣờng đi: 1. Quan hệ định nghĩa, sử dụng (DU): là một liên kết sử dụng của một biến với định nghĩa cuối cùng của nó. 2. Quan hệ kiểm tra, điều khiển (TC):là liên kết giữa sự xuất hiện của tính chất điều khiển và câu lệnh, xảy ra trên đƣờng đi phụ thuộc điều khiển vào nó, quan hệ này chỉ có trong kiểu hƣớng cú pháp chỉ xây dựng cho chƣơng trình có cấu trúc. 3. Quan hệ định danh (IR): là liên kết giữa sự xuất hiện khác nhau của cùng một câu lệnh. Ví dụ 3.1.1.2: Hình 14(b) chỉ ra các khái niệm luồng dynamic cho đƣờng đi trong Hình 14(a). Các slice dynamic slicing đƣợc tính toán bằng cách xác định liên tiếp tập Si của các câu lệnh liên quan trực tiếp và gián tiếp. Với tiêu chuẩn (x, Iq, V) thì phép tính khởi tạo S0 chứa định nghĩa cuối cùng của các biến trong V trên đƣờng đi cũng nhƣ kiểm tra các hành động trên đƣờng đi mà ở đó Iq phụ thuộc điều khiển. Tính toán Si+1 đƣợc xác định nhƣ sau: Slice dynamic slicing thu đƣợc dễ dàng từ tập cố định SC của quá trình trên. p Slice slicing gồm tất cả các câu lệnh X mà có thể thực hiện X xuất hiện trong SC và câu lệnh i tƣơng ứng với tiêu chuẩn Iq. Ví dụ 3.1.1.3: Ta tính slice dynamic slicing cho đƣờng đi trong Hình 14 với tiêu chuẩn (n = 2, 812, {x}). Lúc đầu tập S0 chứa định nghĩa cuối cùng của x là S0 = {59}. Tiếp theo ta sẽ tính đƣợc A1 = {37, 48}, A2 = {76, 11, 33, 311, 44} và A3 = {27, 710}. Từ đó theo quá trình trên ta tính đƣợc: 1 2 3 4 6 7 8 9 10 11 12 SC = {1 , 2 , 3 , 4 , 7 , 3 , 4 , 5 , 7 , 3 , 8 } Vì vậy slice dynamic slicing với tiêu chuẩn (n= 2, 812, {x}) chứa mọi câu lệnh của chƣơng trình trừ câu 5 tƣơng ứng với câu 65 trong đƣờng đi. Slice slicing của chƣơng trình này đƣợc chỉ ra trong Hình 2(b). Nguyễn Sỹ Linh-Ct1301 37
  38. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 15: (a) Đƣờng đi của chƣơng trình mẫu trong Hình 2(a) với đầu vào n= 1. (b) Các khái niệm luồng động cho đƣờng đi này. (c) Slice dynamic slicing với tiêu chuẩn (n = 1, 88, x). (d) Slice slicing không dừng thu đƣợc nếu bỏ qua quan hệ IR Vai trò của quan hệ định danh IR là duyệt chƣơng trình theo cả hai hƣớng và cho vào tất cả các câu lệnh và tính chất điều khiển cần thiết để đảm bảo kết thúc các vòng lặp trong slice slicing. Ví dụ 3.1.1.4: Chúng ta xem xét vai trò của quan hệ định danh IR. Xét đƣờng đi của chƣơng trình mẫu trong Hình 2(a) với đầu vào n = 1 thể hiện trong Hình 15(a). Các khái niệm luồng dynamic với đƣờng đi đó và slice slicing với tiêu chuẩn (n= 1, 88, {x}) đƣợc thể hiện trong Hình 15(b) và 15(c). Slice slicing thu đƣợc là một chƣơng trình kết thúc. Tuy nhiên nếu ta tính các slice slicing không sử dụng quan hệ định danh IR thì sẽ thu đƣợc một chƣơng trình không kết thúc thể hiện trong Hình 15(d). Lý do của hiện tƣờng này là quan hệ DU và TC chỉ duyệt đƣờng đi theo hƣớng ngƣợc lại. Nguyễn Sỹ Linh-Ct1301 38
  39. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 16: (a) Chƣơng trình mẫu. (b)Đƣờng đi với đầu vào n = 2. Tuy nhiên duyệt quan hệ IR theo hƣớng ngƣợc lại làm cho slice slicing chứa các câu lệnh không cần thiết để đảm bảo sự kết thúc. Ví dụ 3.1.1.5: Hình 16(a) chỉ ra một phiên bản sửa đổi của chƣơng trình trong Hình 2(a). Hình 16(b) thể hiện đƣờng đi của chƣơng trình đó. Từ đƣờng đi đó ta có(76, 711)phụ thuộc IR, (65, 76) thuộc DU và (510, 711) thuộc TC. Do đó cả câu lệnh 5 và 6 đều có trong slice slicing mặc dù câu lệnh 6 không cần thiết để tính giá trị cuối cùng của z hay để kết thúc vòng lặp. 3.1.2.Đồ thị phụ thuộc Agrawal và Horgan phát triển một hƣớng tiếp cận sử dụng đồ thị phụ thuộc để tính toán slice dynamic slicing. Thuật toán đầu tiên của họ tính toán slice dynamic slicing không chính xác nhƣng nó có ích để hiểu các thuật toán sau này. Hƣớng tiếp cận đầu tiên sử dụng đồ thị PDG đánh dấu các đỉnh là “đã thực hiện” cho tập các đỉnh đƣợc đƣa ra. Một slice dynamic slicing đƣợc tính toán thông qua cách tính một slice sitatic slicing cho đồ thì con chỉ gồm các đỉnh đƣợc đánh dấu của PDG. Giải pháp này không chính xác vì nó không tính đến tình huống tồn tại một cạnh luồng trong PDG giữa hai đỉnh đƣợc đánh dáu v1 và v2 nhƣng có định nghĩa của v1 không đƣợc sử dụng tại v2. Mặt khác, khi ta biểu diễn một đỉnh đƣợc Nguyễn Sỹ Linh-Ct1301 39
  40. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng đánh dấu trong nhiều vòng lặp sẽ đƣợc biểu diễn trong tất cả các vòng lặp tiếp theo thậm chí khi các sự phụ thuộc không đƣợc lặp lại. Ví dụ 3.1.2.1: Hình 18(a) chỉ ra đồ thì PDG của chƣơng trình mẫu ở Hình 2(a). Giả sử ta muốn tính một slice dynamic slicing với giá trị cuối cùng của x cho đầu vào n =2. Tất cả các đỉnh của PDG đƣợc thực hiện vì mọi đỉnh của PDG đều đƣợc đánh dấu. Thuật toán static slicing ở phần 2.1.2 sẽ tính ra slice dynamic slicing là toàn bộ chƣơng trình mẫu. Tuy nhiên, ta nhận thấy câu lệnh gán x: = 18 là không liên quan. Phép gán này đƣợc cho vào slice slicing vì tồn tại một cạnh phụ thuộc luồng từ đỉnh x = 18 đến đỉnh write(x) nhƣng không biểu diễn một sự phụ thuộc trong vòng lặp thứ hai. Chính xác hơn thì sự phụ thuộc này chỉ xuất hiện trong vòng lặp khi biến điều khiển i có giá trị lẻ. Giải pháp thứ hai cũng dựa trên đồ thì PDG có các đỉnh phân biệt trong đồ thì phụ thuộc tƣơng ứng với mỗi lần xuất hiện của câu lệnh trong đƣờng đi. Loại đồ thị này gọi là đồ thị phụ thuộc động DDG.Một tiêu chuẩn dynamic slicing đƣợc xác định là một đỉnh trong DDG và một slice dynamic slicing đƣợc tính toán bằng cách lấy tất cả các đỉnh DDG mà từ đỉnh tiêu chuẩn có thể đi tới. Một câu lệnh hay tính chất điều khiển có trong slice slicing nếu tiêu chuẩn đƣợc xem xét từ ít nhất một đỉnh trong sự xuất hiện của nó. Nhƣợc điểm của đồ thị PDG là số đỉnh bằng số câu lệnh thực thi không bị ràng buộc. Ví dụ 3.1.2.2: Hình 18(c) chỉ ra đồ thị DDG cho chƣơng trình mẫu ở Hình 16(a). Tiêu chuẩn slicing tƣơng ứng với đỉnh có nhãn write(z) và mọi đỉnh từ đỉnh này có thể đi tới đƣợc in đậm.Ta thấy là tiêu chuẩn không đƣợc xem xét từ đỉnh có nhãn x; = 18 cho nên câu lệnh gán tƣơng ứng không có trong slice slicing. Nguyễn Sỹ Linh-Ct1301 40
  41. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 17: Chƣơng trình Qn có O(2n) slice dynamic slicing khác nhau Trong giải pháp thứ ba, Agarwal và Horgan đề xuất cách giảm số đỉnh trong DDG bằng cách kết hợp các đỉnh có phụ thuộc ngoài ánh xạ đến cùng một tập các lệnh. Nói theo cách khác, một đỉnh mới chỉ đƣợc xem xét nếu nó tạo ra slice dynamic slicing mới. Rõ ràng thì cách kiểm tra này làm tăng số lần thực thi. Đồ thị kết quả đƣợc gọi là đồ thị phụ thuộc dynamic rút gọn RDDG của một chƣơng trình. Slice dynamic slicing tính toán sự dụng RDDG có cùng độ chính xác nhƣ khi tính bằng DDG. Thuật toán dùng đồ thị RDDG không có tất cả đƣờng đi thực hiện. Trong đồ thị này cần phải lƣu ý những vấn đề sau: Với mỗi biến, đỉnh tƣơng ứng đến định nghĩa cuối cùng của nó. Với mỗi tính chất, các đỉnh tƣơng ứng đến thực hiện cuối cùng của nó. Với mỗi đỉnh trong RDDG thì các slice dynamic chứa đỉnh đó. Ví dụ 3.1.2.3: Trong đồ thị DDG ở Hình 18(c) thì đỉnh có nhãn i = i+1 và hai đỉnh bên phải có nhãn while (i<=n) là read(n) và i: = 1 có cùng phụ thuộc ngoài dynamic. Các đỉnh phụ thuộc vào các câu lệnh 1, 2, 3 và 8 của chƣơng trình thể hiện ở Hình 16(a). Đồ thị RDDG cho chƣơng trình này với đầu vào n = 2 thu đƣợc bằng cách gộp bốn đỉnh bên trong đồ thị DDG thành một đỉnh. Nguyễn Sỹ Linh-Ct1301 41
  42. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Hình 18: (a) PDG của chƣơng trình trong Hình 2(a).(b)PDG của chƣơng trình trong Hình 16(a).(c)DDG của chƣơng trình Hình 16(a). 3.2. Dynamic slicing đa thủ tục Agrawal, Demillo và Spafford xem xét phƣơng pháp dynamic slicing đa thủ tục với các cơ chế truyền tham số khác nhau. Giả sử thủ tục P với các tham số hình thức f1, , fn đƣợc gọi bởi tham số thực a1, , an . Điều chú ý trong hƣơng tiếp cận này là phụ thuộc dữ liệu động dựa trên các định nghĩa và các sử dụng của vùng nhớ đã sử dụng. Theo cách này ta tránh đƣợc hai bấn đề: (i)cách sử dụng biến toàn cục trong các thủ tục không gây ra lỗi, (ii) không có yêu cầu phân tích các bí danh. Tham số truyền tham trị đƣợc tạo ra bằng một chuỗi các câu lệnh gán f1: = a1, ., fn: = an đƣợc thực hiện trƣớc khi vào thủ tục. Để xác định các ô nhớ cho việc ghi hành động chính xác thì tập USE cho các tham số thực ai đƣợc xác định trƣớc khi vào thủ tục, tập DEF cho các tham số hình thức fi đƣợc xác định sau khi vào thủ tục. Với tham số truyền tham trị kết quả, các phép gán của tham số hình thức đến tham số thực phải đƣợc thực hiện khi ra khỏi thủ tục. Tham số truyền tham chiếu không yêu cầu các chi tiết hành động đến slice dynamic slicing nhƣ cùng ô nhớ liên kết tƣơng ứng giữa tham số thực và tham số hình thức ai và fi. Nguyễn Sỹ Linh-Ct1301 42
  43. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Một hƣớng tiếp cận khác của dynamic slicing đa thủ tục đƣợc giới thiệu bởi Kamkar, Shahmehri và Fritzson trong nghiên cứu các xác định tập các đỉnh gọi trong chƣơng trình ảnh hƣởng đến giá trị của một biến tại một đỉnh gọi cụ thể. Trong khi thực hiện, một đồ thị tổng hợp phụ thuộc động DDSG đƣợc xây dựng, các đỉnh trong đồ thị chỉ ra các thể hiện thủ tục tƣơng ứng với sự kích hoạt thủ tục đƣợc chú thích bằng các tham số của nó. Các cạnh của đồ thị tổng hợp tƣơng ứng với lời gọi thủ tục hay các cạnh phụ thuộc tổng hợp. Một tiêu chuẩn slicing đƣợc xác định là một cặp chứa một thể hiện thủ tục và một tham số ra hoặc vào của thủ tục liên kết. Sau khi xây dựng đồ thị tổng hợp, một slice slicing với tiêu chuẩn slicing đƣợc xác định qua hai bƣớc. Đầu tiên các phần của đồ thị tổng hợp có thể đi tới đỉnh tiêu chuẩn đƣợc xác định, đồ thị con đƣợc sinh ra là một slice slicing thực thi. Các đỉnh của slice slicing thực thi là một thể hiện thủ tục cụ thể vì các tham số có thể bị slicing đi. Một slice slicing chƣơng trình đa thủ tục chứa tất cả các đỉnh gọi trong chƣơng trình mà có một thể hiện cụ thể xuất hiện trong slicing thực thi. Có ba phƣơng pháp để ta có thể xây dựng một đồ thị tổng hợp. Trong phƣơng pháp tiếp cận đầu tiên, các phụ thuộc dữ liệu đơn thủ tục đƣợc xác định một cách static tạo ra slice slicing không chính xác nếu có các câu lệnh điều kiện. Trong hƣớng tiếp cận thứ hai, tất cả các phụ thuộc đƣợc xác định lúc thực thi. Muốn có slice slicing chính xác thì các phụ thuộc của một thủ tục P phải đƣợc tính mỗi khi P đƣợc gọi. Cách tiếp cận thứ ba kết hợp sự hiệu quả của hƣớng tiếp cận static thứ nhất cùng sự chính xác của hƣớng tiếp cận dynamic thứ hai bằng cách tính toán các phụ thuộc bên trong các khối cơ bản static và các phụ thuộc dynamic giữa các khối. Trong mọi cách tiếp cận trên thì các phụ thuộc điều khiển đƣợc xác định static. Nguyễn Sỹ Linh-Ct1301 43
  44. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Chƣơng 4: THỰC NGHIỆM TRÊN CÁC CHƢƠNG TRÌNH SLICER Trong chƣơng này em xin trình bày về hai chƣơng trình đƣợc sử dụng minh họa cho hai phƣơng pháp StaticSlicing và Dynamic Slicing. 4.1 Chương trình StaticSlicer Bài toán cho chƣơng trình nhƣ sau: (1)begin (2) c = 1 ; (3) b = (2 * a) ; (4) x = 3 ; (5) z = 90 ; (6) if (b > c ) then (7) begin (8) z = (z + x) ; (9) while ( z > 30) do (10) begin (11) x = (y + 1) ; (12) y = (((y - z) + 3) * y) ; (13) z = (z - 3) ; (14) end; (15) od; (16) end; (17) else (18) begin (19) z = (z - x) ; (20) end; (21) fi; (22) tmpvar = x; (23) emptyline=1; (24)end; Xét tiêu chuẩn slicing (n, {v}) = (19, {z}). n = 19 là vị trí của câu lệnh, v = z là biến của câu lệnh n Nguyễn Sỹ Linh-Ct1301 44
  45. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng (1) begin (2) c = 1 ; (3) b = (2 * a) ; (4) x = 3 ; (5) z = 90 ; (6) if (b > c ) then (7) begin (8) z = (z + x) ; (9) while ( z > 30) do (10) begin (11) x = (y + 1) ; (12) y = (((y - z) + 3) * y) ; (13) z = (z - 3) ; (14) end; (15) od; (16) end; (17) else (18) begin (19) z = (z - x) ; (20) end; (21) fi; (22) tmpvar = x; (23) emptyline=1; (24)end; Nguyễn Sỹ Linh-Ct1301 45
  46. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Nguyễn Sỹ Linh-Ct1301 46
  47. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 4.2. Chương trình Kaveri Yêu cầu để chạy chƣơng trình Kaveri: Eclipse: Eclipse phiên bản 3.0.x. Indus Plug-in: Indus Plug-in phiên bản 0.6.x GroovyMonkey phiên bản 0.6.x Khi cài xong chƣơng trình sẽ có giao diện nhƣ sau: Bài toàn nhƣ sau: Chƣơng trình tính Tổng giai thừa các số từ 1 đến n. Để cấu hình các slice slcing ta vào Indus Configuration trên thanh menu. Nguyễn Sỹ Linh-Ct1301 47
  48. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ta có code java của bài toán: import java.io.*; public class Giaithua { public static int n,Sn; public Giaithua() { // TODO Auto-generated constructor stub } / * @param args */ public static void main(String[] args) { int i=0; int j=0; int Ketqua=0; System.out.print("Nhap so n: "); try{ n = System.in.read(); } catch(IOException ex) { System.out.println("Khong doc duoc thong tin"); } for(i=1;i Show View -> Other -> Kaveri ->Jimple View. Khi đó ta sẽ có bảng dùng để thêm vào các tiêu chuẩn slicing. Nguyễn Sỹ Linh-Ct1301 48
  49. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ta dùng các nút trong bảng Jumple Statement để thêm vào các tiêu chuẩn.Thứ tự các nút từ trái qua phải là: Track Java Statements: Câu lệnh đƣợc chọn chỉ hiện thị khi bật hoặc tắt nút này. Add as criteria (Pre-Execution): Thêm các tiêu chuẩn của câu lệnh liên quan tới chƣơng trình cần slicing. Tiêu chuẩn đƣợc thêm vào dùng để điều khiển câu lệnh khi đƣợc bật nút. Add as criteria (Post-Execution): Thêm các tiêu chuẩn của câu lệnh liên quan tới chƣơng trình cần slicing. Tiêu chuẩn bổ sung thêm giá trị của biểu thức nếu đƣợcbật nút. Remove Criteria: Loại bỏ các câu lệnh có liên quan đến tiêu chuẩn của bài toán. Add as Java criteria (Pre-Execution): Nút này tƣơng tự nhƣ nút Add as criteria (Pre-Execution) nhƣng dùng để thêm tất cả các tiêu chuẩn một lần bật nút. Add as Java criteria (Post-Execution): Nút này tƣơng tự nhƣ nút Add as criteria (Post-Execution) nhƣng dùng để thêm tất cả các tiêu chuẩn một lần bật nút. Remove all Criteria: Loại bỏ tất cả các câu lệnh liên quan tới tiêu chuẩn của bài toán. Để xem các tiêu chuẩn ta vào Window -> Show View -> Other -> Kaveri - >Slice information View. Nguyễn Sỹ Linh-Ct1301 49
  50. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Để xem các phụ thuộc của tiêu chuẩn đƣợc chọn ta vào Window -> Show View -> Other -> Kaveri ->Dependence Tracking View. Chạy Kaveri: Kích chuột phải vào Java file hoặc Java project trong navigator hoặc package explorer trong giao diện của Eclipse và chọn Indus -> Slice Java file or Indus -> Slice project. Tại đây ta có thể chọn các tiêu chuẩn để thực hiện slicing từ các bƣớc trên.Sau khi chọn xong các tiêu chuẩn ta kích vào run để chạy chƣơng trình slicing cho bài toán. Nguyễn Sỹ Linh-Ct1301 50
  51. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng KẾT LUẬN Với một yêu cầu lớn vậy em chỉ có thể quan tâm đƣợc các vấn đề liên quan tới lập trình, lệnh trong chƣơng trình, coding và kiểm thử, kiểm chứng. Để thực hiện đƣợc các vấn đề trên đòi hỏi rất nhiều thời gian, phải theo dõi chặt chẽ các biến hay các câu lệnh. Đối với một chƣơng trình nhỏ thì vấn đề này có thể dễ dàng thực hiện đƣợc nhƣng với những chƣơng trình lớn có hàng nghìn câu lệnh, nhiều biến chạy suốt dọc chƣơng trình thì việc theo dõi một biến trở nên khó khăn không thể làm đƣợc hoặc làm đƣợc nhƣng tốn rất nhiều thời gian. Vì vậy đã có rất nhiều các kĩ thuật ra đời nhằm giải quyết vấn đề trên.Trong đó có kĩ thuật Program Slicing Program slicing là một kĩ thuật lấy từ chƣơng trình ra chả các câu lệnh ảnh hƣởng đến một giá trị tính toán cụ thể tại các điểm đƣợc quan tâm gọi là các tiêu chuẩn slicing. Program slicing đã và đang đƣợc triển khai và áp dụng trong nhiều lĩnh vực công nghệ phần mềm nhƣ hỗ trợ gỡ rối chƣơng trình kiểm thử, bảo trì phần mềm . Hiện nay có nhiều phƣơng pháp slicing khác nhau nhƣng thƣờng dùng kỹ thuật static slicing và dynamic slicing trên những chƣơng trình có cấu trúc. Các kỹ thuật slicing thông dụng hiện nay để sử dụng luồng dữ liệu và đồ thị phụ thuộc chƣơng trình để tính toán ra các slice slicing. Ngoài ra trong một số trƣờng hợp cụ thể ta có thể sử dụng các kỹ thuật program slicing khác nhƣ slicing dựa trên luồng thông tin, dựa trên quan hệ phụ thuộc. Nguyễn Sỹ Linh-Ct1301 51
  52. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng TÀI LIỆU THAM KHẢO [Wei1] M. Weiser. Program slicing. [Wei2] M. Weiser Program slices: formal, psychological, and practical investigations of an automatic program abstraction method . PhD thesis, University of Michigan, Ann Arbor, 1979. [3] K.J. Ottenstein and L.M. Ottenstein. The program dependence graph in a software development environment. In Proceedings of the ACM SIGSOFT/SIGPLANSoftware Engineering Symposium on Practical Software Development Environments. [4] J.-F. Bergeretti and B.A. Carre. Information- ow and data- ow analysis of while programs. ACM Transactions on Programming Languages and Systems. [5] B. Korel and J. Laski. Dynamic slicing of computer programs. Journal of Systems and Software. [6] S. Horwitz and T. Reps. The use of program dependence graphs in software engineering. In Proceedings of the14th International Conference on Software Engineering. [7] S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems. [8] H. Agrawal and J.R. Horgan. Dynamic program slicing. In Proceedings of the ACM SIGPLAN’90 Conference on Programming Language Design and Implementation. [9] H. Agrawal, R.A. DeMillo, and E.H. Spafford. Dynamic slicing in the presence of unconstrained pointers. In Proceedings of the ACM Fourth Symposium on Testing, Analysis, and Verification (TAV4). [10] Frank Tip, A Survey of Program Slicing Techniques, Nguyễn Sỹ Linh-Ct1301 52