Để khắc phục khuyết điểm này, một trong những phương pháp đáng chú ý là áp dụng kỹ thuật sinh test-case trong kiểm thử phần mềm để chỉ tạo ra các dữ liệu đầu vào vừa đủ khi thực hiện kiể
TỔNG QUAN VỀ ĐỀ TÀI
Tổng quan
Trong những năm gần đây, với sự phát triển của ngành công nghệ phần mềm, bước kiểm tra chương trình ngày càng khẳng định vị trí quan trọng của nó trong quy trình phát triển phần mềm Tuy nhiên, các phương pháp kiểm thử truyền thống có nhược điểm là tiêu tốn nhiều chi phí và phụ thuộc quá nhiều vào chủ quan quan sát và đánh giá của kiểm thử viên (testers) Ngoài ra, thao tác kiểm thử đôi lúc gây ra những lỗi nghiêm trọng cho hệ thống liên quan do chương trình được kiểm thử phải được thực thi nhằm sinh ra kết quả
Nhằm khắc phục những nhược điểm trên, nhiều hướng nghiên cứu gần đây tập trung nhiều vào các phương pháp kiểm tra hình thức (formal method) như kiểm tra mô hình (model checking) hay kiểm tra dựa trên chứng minh (theorem proving) Nhìn chung, cả hai phương pháp đều là những công cụ hữu hiệu giúp xác định tính đúng đắn của một chương trình mà không cần phải thực thi nó trong môi trường thực tế Trong hai phương pháp trên, phương pháp model checking có ưu thế là có thể giúp sinh phản ví dụ, do đó giúp cho lập trình viên có thể tra vết và khắc phục lỗi một cách hiệu quả hơn Tuy nhiên, model checking cũng có nhược điểm là dễ gặp phải vấn đề bùng nổ số trạng thái bởi model checker phải thực hiện vét cạn tất cả các giá trị có thể của tham số đầu vào (xem thêm mục 2.2.3 ) Để khắc phục khuyết điểm này, một trong những phương pháp đáng chú ý là áp dụng kỹ thuật sinh test-case trong kiểm thử phần mềm để hướng dẫn các model checker chỉ cần kiểm tra trên một tập dữ liệu vừa đủ nhỏ mà vẫn có thể bao quát được các lỗi có thể xảy ra khi thực hiện kiểm tra chương trình bằng phương pháp model checking Một trong những hướng tiếp cận hiệu quả trong việc áp dụng nguyên tắc kiểm tra trên là kỹ thuật concolic testing (xem thêm mục 2.2 )
Ngoài việc bùng nổ trạng thái đã được giải quyết khá hiệu quả bằng cách áp dụng kỹ thuật concolic testing, trong thực tế khi sử dụng model checking để kiểm tra chương trình, chúng có một số khuyết điểm quan trọng khác như sau:
(i) chỉ làm việc trên miền số rời rạc;
(ii) toàn bộ chương trình phải được mô hình hoá để kiểm tra Đối với khuyết điểm (i), nhiều hướng nghiên cứu đã được đưa ra dựa trên việc trừu tượng hóa chương trình để biến đổi các kiểu dữ liệu khác về dạng số nguyên [3][4][5][6] Trong khi đó, giải pháp cho những khó khăn ở dạng (ii) tuy gặp rất nhiều trong thực tế nhưng vẫn chưa được quan tâm nghiên cứu nhiều Theo đó, khi kiểm tra một chương trình dựa trên phương pháp model checking (và cả theorem proving), ta luôn đặt giả định về tính đầy đủ mã nguồn của chương trình Trên thực tế, điều này không luôn luôn đúng bởi trong nhiều trường hợp ta không được cung cấp đầy đủ mã nguồn như các lời gọi hàm, thủ tục trong thư viện của ngôn ngữ lập trình, hoặc các lời gọi hàm, thủ tục được cung cấp bởi các thư viện của các bên thứ ba Trong các trường hợp trên, việc thiếu mã nguồn của các hàm, thủ tục được gọi khiến cho các model checkers (và các theorem provers) không thể
“hiểu” được ngữ nghĩa hình thức của chương trình và điều này dẫn đến thất bại trong việc xác định chương trình có lỗi hay không
Từ những nhận xét trên, ta thấy rằng có một nhu cầu cấp thiết trong việc hỗ trợ các model checkers và theorem provers nhằm kiểm tra các chương trình có hỗ trợ các lời gọi hàm, thủ tục mà mã nguồn không có sẵn Trong luận văn này, chương trình dạng này được gọi là chương trình chưa hoàn chỉnh (incomplete programs) Luận văn đã nghiên cứu và đề ra một phương pháp giúp kiểm tra các chương trình chưa hoàn chỉnh bằng cách biến đổi các chương trình chưa hoàn chỉnh thành một tập các chương trình tự hoàn chỉnh (self-complete programs) Đồng thời, để chứng minh rằng phép biến đổi chương trình đề ra là đúng đắn, luận văn đã chứng minh rằng phép biến đổi sẽ thỏa mãn tính chất của một consistent abstract interpretation đối với tập test-case đã được xây dựng.
Mục tiêu nghiên cứu của luận văn
Từ việc nhận thấy tính cần thiết của việc kiểm tra các chương trình chưa hoàn chỉnh, luận văn đã tập trung nghiên cứu các phương pháp có thể biến đổi chương trình để “giúp” các model checkers và các theorem provers có thể kiểm tra
Trang 3 các chương trình dạng này Để đạt được điều này, luận văn cần nghiên cứu và giải quyết các vấn đề chính sau:
Nghiên cứu cách rút trích các ràng buộc và ngữ nghĩa luận lý của một hàm, thủ tục được đặc tả bằng ngôn ngữ ACSL (ANSI/ISO C Specification Language) để phục vụ quá trình nghiên cứu sau này
Nghiên cứu cách sinh test-case cho một chương trình dựa vào việc phân tích các luồng thực thi của chương trình
Nghiên cứu cách sinh test-case và biến đổi chương trình chưa hoàn chỉnh thành chương trình tự hoàn chỉnh cho các chương trình có chứa các lời gọi hàm thư viện trong trình biên dịch của chương trình nguồn
Nghiên cứu cách sinh test-case và biến đổi chương trình chưa hoàn chỉnh thành chương trình tự hoàn chỉnh cho các chương trình có chứa các lời các lời gọi thủ tục mà ngữ nghĩa luận lý được đặc tả bằng ngôn ngữ ACSL
Nghiên cứu cách sinh test-case và biến đổi chương trình chưa hoàn chỉnh thành chương trình tự hoàn chỉnh cho các chương trình có chứa các lời các lời gọi hàm mà ngữ nghĩa luận lý được đặc tả bằng ngôn ngữ ACSL
Nghiên cứu lý thuyết về abstract interpretation để chứng minh biến đổi được sử dụng trong chương trình là một consistent abstract interpretation.
Đóng góp chính của luận văn
Trong luận văn này, học viên đã đề xuất một framework để kiểm tra các chương trình chưa hoàn chỉnh Với đề xuất này, luận văn có những đóng góp chính sau:
(i) Đề xuất phương pháp giải quyết khó khăn trong việc phân tích các lời gọi hàm / thủ tục bằng cách kết hợp các đặc tả của hàm / thủ tục với luồng thực thi của chương trình để tạo ra tập các ràng buộc và test-case đủ để bao quát hết các khả năng có thể xảy ra của chương trình
(ii) Sử dụng phương pháp thực thi với dữ liệu thực để thay thế các lời gọi hàm / thủ tục bằng kết quả tương ứng với tập dữ liệu đang kiểm tra
Theo đó, chương trình chưa hoàn chỉnh sẽ được biến đổi thành chương trình tự hoàn chỉnh (self-complete program) và có thể kiểm tra được bằng phương pháp kiểm tra mô hình
(iii) Về mặt lý thuyết, luận văn đã đóng góp bằng hai bài báo khoa học đã được xuất bản là: a Le V Tien, Quan T Tho, and Le D Anh, “Specification-based Verification of Incomplete Programs”, in Third International Conference on Advances in Computing, Control, and Telecommunication Technologies (ACT-2011), Jakarta, Indonesia, 2011 b Thai, V.D.; Quan, T.T ; Le, T.V ; Ngo, B.T., “An Approximation-Based Abstract Interpretation Framework for Formal Verification of Floating-Point Programs”, in Computing and Communication Technologies, Research, Innovation, and Vision for the Future (RIVF), 2012 IEEE RIVF International Conference, Ho Chi Minh City, Vietnam, 2012 Đồng thời, luận văn cũng chứng minh rằng framework được đề xuất tương ứng với một consistent abstract interpretation Điều đó có nghĩa là: các lỗi xảy ra trong chương trình gốc cũng sẽ được tìm thấy trong chương trình đã được biến đổi khi áp dụng các phương pháp kiểm tra hình thức một cách đúng đắn Giải pháp đề xuất đã được thực hiện kiểm tra trên dữ liệu các bài tập lập trình đơn giản cho sinh viên của Khoa khoa học và kỹ thuật máy tính, trường Đại học Bách Khoa TP Hồ Chí Minh Luận văn cũng đã xây dựng thêm một ứng dụng minh họa trên nền tảng mạng xã hội (social network) nhằm mục tiêu thu hút tinh thần tự học của sinh viên cao hơn nhờ vào các hoạt động tương tác trong quan hệ bạn bè trên mạng xã hội.
Cấu trúc luận văn
Luận văn bao gồm 6 chương và được trình bày như sau:
Chương 1: Tổng quan về đề tài
Chương 2: Cơ sở lý thuyết
Chương 3: Giải pháp kiểm tra chương trình chưa hoàn chỉnh
Chương 4: Hiện thực ứng dụng kiểm tra mô hình cho các chương trình chưa hoàn chỉnh
Chương 5: Kết quả thực nghiệm và đánh giá
Chương 6: Kết luận và hướng phát triển
CƠ SỞ LÝ THUYẾT
Kiểm tra hệ thống (system verification)
Ngày nay, các hệ thống công nghệ thông tin và truyền thông (hệ thống ICT – ICT systems [23]) ngày càng được sử dụng phổ biến Với sự phát triển của công nghệ và internet, các hệ thống này ngày càng phức tạp và xuất hiện ở mọi lĩnh vực của đời sống Theo số liệu thống kê năm 1995 [23], mỗi người tiếp xúc trung bình với 25 thiết bị ICT mỗi ngày Các dịch vụ như chuyển tiền điện tử hay mua sắm từ xa đã dần trở thành hiện thực và ngày càng phổ biến Số tiền hàng ngày được sử dụng qua kênh Internet lên đến 1012 triệu đô la Mỹ Khoảng 20% chi phí sản xuất các sản phẩm vận tải hiện đại như xe hơi, tàu cao tốc, máy bay là dành cho hệ thống xử lý thông tin Các hệ thống ICT phổ biến và có mặt ở tất cả mọi nơi Chúng điều khiển thị trường chứng khoán, đóng vai trò trung tâm chuyển mạch điện thoại, đóng vai trò trọng yếu trong công nghệ internet, và đóng nhiều vai trò quan trọng trong các hệ thống y khoa Sự phổ biến của các hệ thống này càng làm tăng tính ảnh hưởng của chúng tới các hoạt động của xã hội con người Để đánh giá các hệ thống này, ngoài các tiêu chí về hiệu suất như thời gian xử lý nhanh, khả năng xử lý với lượng dữ liệu lớn, một trong những tiêu chí quan trọng cần được xem xét là hệ thống có chứa lỗi hay không
Xét trên tầm ảnh hưởng của các hệ thống ICT, mặc dù các lỗi trong phần cứng và phần mềm có thể không làm nguy hại tới cuộc sống của con người, tuy nhiên chúng sẽ gây những hậu quả xấu về tài chính cho các nhà sản xuất Hệ thống ICT hoạt động đúng là điều kiện cần thiết cho sự tồn tại của một công ty Trong lịch sử đã có nhiều thiệt hại tài chính to lớn gây ra bởi các lỗi xuất hiện trong các hệ thống này Một lỗi trong phép chia với số thực trong bộ xử lý Intel Pentium II ở đầu thập niên 90 gây thiệt hại 475 triệu đô la Mỹ để thay thế các bộ xử lý bị lỗi, đồng thời gây ảnh hưởng nặng nề đến danh tiếng của Intel Trục trặc trong hệ thống xử lý hành lý xách tay làm sân bay Denver phải dời ngày mở cửa sau 9 tháng
Trang 7 với thiệt hại ước tính 1.1 triệu đô la Mỹ mỗi ngày Một công ty hàng không lớn cũng có thể bị phá sản nếu gặp lỗi trong hệ thống đặt vé trực tuyến Đó là một số thí dụ về thiệt hại nặng nề gây ra bởi việc các hệ thống ICT có tồn tại lỗi
Trong nhiều trường hợp, những lỗi hệ thống có thể gây nên những thảm họa lớn Một lỗi tai hại trong phần mềm điểu khiển phóng tên lửa Ariane-5 và máy bay Airbus đã gây nên những thảm họa to lớn làm chấn động toàn thế giới cho đến ngày nay Người ta cũng dùng các phần mềm trong việc điều khiển hoạt động của các hệ thống cần an toàn tuyệt đối như điều khiển nhà máy điện nguyên tử, nhà máy điện hạt nhân, hệ thống quản lý và cảnh báo giao thông, hệ thống cảnh báo bão và sóng thần… Rõ ràng rằng, lỗi xảy ra trong các phần mềm này có thể gây ra những hậu quả to lớn khó lường Thí dụ như lỗi phần mềm trong bộ phận điều khiển của máy chữa bệnh bằng tia bức xạ Thera-25 đã làm chết sáu bệnh nhân ung thư từ năm 1985 đến 1987 mà nguyên nhân là bởi những bệnh nhân này đã bị điều trị quá liều bức xạ
Từ việc ứng dụng ngày càng rộng rãi các hệ thống xử lý thông tin, ta có thể nói rằng: Tính ổn định là vấn đề cốt yếu trong quá trình thiết kế hệ thống
Tầm quan trọng, cũng như tính phức tạp của các hệ thống ICT ngày càng phát triển nhanh chóng Các hệ thống ICT hiện nay không còn là một cá thể độc lập nữa mà thường được nhúng trong một môi trường lớn hơn, có kết nối và tương tác với nhiều thành phần và hệ thống khác nhau Điều đó đồng nghĩa với việc chúng càng dễ xảy ra lỗi, bởi số lượng lỗi có thể bùng nổ rất nhanh chóng so với số thành phần trong hệ thống Điều đó đặt ra nhu cầu thiết yếu trong việc kiểm tra hệ thống một cách toàn diện
Các kỹ thuật kiểm tra hệ thống (system verification) ngày càng được áp dụng nhiều vào việc thiết kế hệ thống ICT Về cơ bản, kiểm tra hệ thống là việc xác minh thiết kế hoặc sản phẩm được xem xét có các thuộc tính cần thiết hay không Các thuộc tính cần kiểm chứng thường được định nghĩa từ bản đặc tả hệ thống Tài liệu này sẽ mô tả hệ thống sẽ phải làm gì, và không nên làm gì và đó là nền tảng cho mọi hoạt động kiểm tra Một lỗi sẽ được tìm thấy khi hệ thống không đáp ứng một trong các tính chất được đặc tả Hệ thống sẽ được xem là “đúng” khi
Trang 8 nó thỏa mãn mọi tính chất rút ra từ bản đặc tả Lược đồ của quá trình kiểm tra được minh họa như Hình 2.1 1
Hình 2.1: Lược đồ của quá trình kiểm tra
Quá trình kiểm tra một hệ thống sẽ bao gồm kiểm tra phần cứng và kiểm tra phần mềm Trong luận văn này chủ yếu đề cập đến các kiến thức về kiểm tra phần mềm
2.1.1 Kiểm thử phần mềm (software testing)
Kiểm thử phần mềm (software testing) [7] là hoạt động khảo sát thực tiễn sản phẩm hay dịch vụ phần mềm trong đúng môi trường chúng dự định sẽ được triển khai nhằm cung cấp cho người có lợi ích liên quan những thông tin về chất lượng của sản phẩm hay dịch vụ phần mềm ấy Mục đích của kiểm thử phần mềm là tìm ra các lỗi hay khiếm khuyết phần mềm nhằm đảm bảo hiệu quả hoạt động tối ưu của chúng trong nhiều ngành khác nhau
Tùy thuộc vào phương pháp kiểm thử được sử dụng, quá trình kiểm thử phần mềm có thể được thực thi tại bất kỳ giai đoạn nào trong quy trình phát triển
1 Hình vẽ lấy từ [23], trang 8
Trang 9 phần mềm Tuy nhiên, hầu hết các công việc kiểm thử đều được thực hiện sau khi các yêu cầu đều đã được định nghĩa, phân tích và hiện thực (coding)
Có 2 phương pháp kiểm thử chính là: kiểm thử tĩnh (static testing) và kiểm thử động (dynamic testing)
Kiểm thử tĩnh là phương pháp kiểm thử phần mềm đòi hỏi phải duyệt lại các yêu cầu và các đặc tả bằng tay, thông qua việc sử dụng giấy, bút để kiểm tra logic, lần từng chi tiết mà không cần thực thi chương trình
Kiểm thử động là phương pháp kiểm thử thông qua việc thực thi chương trình trên một máy tính cụ thể nhằm kiểm tra các kết quả đầu ra cũng như tác động thực tế của chương trình Trong kiểm thử động, phần mềm phải thực sự được biên dịch/thông dịch và thực thi trên môi trường thực tế Quy trình kiểm thử động bao gồm việc thực thi phần mềm, nhập các giá trị đầu vào và kiểm tra xem liệu đầu ra có như mong đợi hay không Các phương pháp kiểm thử động phổ biến bao gồm: kiểm thử đơn vị (unit tests), kiểm thử tích hợp (intergration tests), kiểm thử hệ thống (system tests) và kiểm thử chấp nhận sản phẩm (acceptance tests)
Trong kiểm thử phần mềm, có ba chiến lược kiểm thử thông dụng nhất là kiểm thử hộp đen (black-box testing), kiểm thử hộp trắng (white-box testing), và kiểm thử hộp xám (gray-box testing) Kiểm thử hộp đen là kiểu kiểm thử dựa vào các đặc tả đầu vào và đầu ra của chương trình mà hoàn toàn không quan tâm đến cấu trúc bên trong của nó trong khi kiểm thử hộp trắng là kiểu kiểm thử dựa vào cấu trúc logic và thuật toán bên trong của chương trình Kiểm thử hộp xám đòi hỏi phải có sự truy cập tới cấu trúc dữ liệu và giải thuật bên trong cho những mục đích thiết kế các test cases, nhưng là kiểm thử ở mức người sử dụng (hay mức hộp đen)
2.1.2 Kiểm tra phần mềm (software verification)
Kiểm thử phần mềm là một khâu cần thiết để nâng cao chất lượng của hệ thống Tuy nhiên, các phương pháp kiểm thử truyền thống đều có nhược điểm chung là chi phí khá cao (do cần tiêu tốn nhiều nhân lực cho công việc kiểm thử) và không an toàn (do trong hầu hết các trường hợp, các kiểm thử viên phải thực thi phần mềm cần kiểm thử trên hệ thống thực để quan sát các kết quả trả về) Do đó,
Trang 10 một xu hướng nhằm kiểm định chất lượng sản phẩm phần mềm được quan tâm phát triển trong thời gian gần đây là kiểm tra phần mềm
Lý thuyết về kiểm tra mô hình (model checking)
Trong quá trình thiết kế phần cứng và phần mềm cho các hệ thống phức tạp, thời gian và công sức dành cho quá trình kiểm tra lớn hơn nhiều so với thời gian dành cho việc xây dựng hệ thống Nhiều kỹ thuật được đề ra nhằm giảm thiểu công sức của việc kiểm tra trong khi vẫn tăng độ bao quát của nó Các phương pháp kiểm tra hình thức giúp cho việc kiểm tra có thể thực hiện ngay trong quá trình thiết kế, và đã chứng minh tính hiệu quả của nó trong việc thu giảm thời gian của quá trình kiểm tra
Về cơ bản, các phương pháp kiểm tra hình thức có thể được xem như việc
“áp dụng các mô hình tính toán cho việc mô hình hóa và phân tích các hệ thống công nghệ thông tin và truyền thông” Mục tiêu của các phương pháp này là xác minh tính đúng đắn của hệ thống với những phương pháp toán học chặt chẽ Chính
VERIFYING (USING PROVERS/MODEL CHECKERS)
Trang 12 vì tiềm năng to lớn này, các phương pháp này ngày càng được dùng rộng rãi trong việc kiểm tra các hệ thống phần cứng và phần mềm phức tạp Ngoài ra, các phương pháp kiểm tra hình thức còn được khuyên dùng cho các hệ thống tối cần thiết an toàn Các khuyến khích này được đưa ra bởi nhiều tổ chức có uy tín như Ủy ban Kỹ thuật điện Quốc gia (IEC - International Electrotechnical Commission),
Cơ quan Quản lý Hàng không Châu Âu (ESA - European Space Agency) Kết quả báo cáo của một nghiên cứu về các phương pháp kiểm tra hình thức được thực hiện bởi Cục Hàng không Liên bang (FAA - Federal Aviation Authority) và Cục Quản trị Hàng không và Không gian Quốc gia (NASA - National Aeronautics and Space Administration) đã chỉ ra rằng: “Các phương pháp hình thức nên được giảng dạy cho mọi nhà khoa học máy tính cũng như các kỹ sư phần mềm, cũng như việc giảng dạy toán ứng dụng chuyên ngành phù hợp cho mọi kỹ sư.”
Trong suốt hai thập kỷ qua, các nghiên cứu về phương pháp hình thức đã giúp phát triển được nhiều kỹ thuật kiểm tra tiềm năng giúp phát hiện sớm các lỗi sai của các hệ thống Những kỹ thuật này được phát triển cùng với những công cụ phần mềm mạnh mẽ giúp cho việc tự động hóa nhiều bước trong quá trình kiểm tra Các nghiên cứu cũng đã chỉ ra rằng quá trình kiểm tra hình thức sẽ giúp phát hiện được các lỗi sớm trong các hệ thống như hệ thống phóng tên lửa Ariane-5, bộ vi xử lý Intel Pentium II, máy điều trị bằng tia bức xạ Therac-25, …
Các kỹ thuật kiểm tra mô hình dựa vào việc mô hình hóa các hành vi có thể của hệ thống trong một hô hình toán học chính xác và không nhập nhằng Các nghiên cứu cũng chỉ ra rằng viêc mô hình hóa chính xác một hệ thống sẽ giúp phát hiện các sơ sót trong hệ thống như thiếu tính hoàn bị, tồn tại nhập nhằng, và thiếu nhất quán trong các bản đặc tả Những lỗi này trước kia thường chỉ được phát hiện ở các giai đoạn sau của quá trình thiết kế Các mô hình hệ thống thường đi kèm với các thuật toán giúp khảo sát tất cả các trạng thái của mô hình hệ thống Điều này là nền tảng cho tất cả các kỹ thuật kiểm tra, từ việc tìm kiếm vét cạn (với phương pháp kiểm tra mô hình) cho đến thực nghiệm với một tập dữ liệu giới hạn của mô hình (phương pháp giả lập), hay thực nghiệm với dữ liệu thực tế (quá trình kiểm thử) Với sự phát triển không ngừng của thuật toán và cấu trúc dữ liệu, cộng với
Trang 13 khả năng tính toán ngày càng nhanh và bộ nhớ ngày càng lớn của các máy tính, nếu cách đây một thập kỷ các kỹ thuật kiểm tra mô hình chỉ hoạt động được trên các thí dụ rất đơn giản thì giờ đây nó đã có thể được áp dụng trong các thiết kế thực tế
Kiểm tra mô hình (model checking [8]) là một kỹ thuật kiểm tra thực hiện duyệt qua tất cả các trạng thái có thể của hệ thống theo phương thức vét cạn Tương tự như một chương trình chơi cờ trên máy tính cần kiểm tra tất cả những bước có thể đi, một model checker (phần mềm thực hiện việc kiểm tra mô hình) cũng sẽ thực hiện kiểm tra tất cả các trạng thái có thể xảy ra của đối tượng cần kiểm tra một cách có hệ thống
Model checking được phát triển bởi Clarke và Emerson trong những năm đầu của thập niêm 1980 Trong model checking, hệ thống / chương trình được kiểm tra sẽ được chuẩn hóa thành các mô hình toán học Các mô hình này thường ở dạng cấu trúc Kripke [9] Về cơ bản, một cấu trúc Kripke được xem như một automat hữu hạn không đơn định mà trong đó temporal logic [10] được áp dụng để kiểm tra một đặc tính nào đó của chuỗi dữ liệu nhập
Các kỹ thuật model checking được áp dụng rộng rãi trong việc kiểm tra các giao thức và thiết kế phần cứng bởi chúng có thể kiểm tra xem hệ thống có vận hành đúng như mong đợi hay không mà không cần phải thực thi hệ thống Trong thời gian gần đây, với xu hướng phát triển của việc ứng dụng phương pháp kiểm tra hình thức vào công nghệ phần mềm, nhu cầu sử dụng model checking trong quá trình kiểm tra phần mềm ngày càng tăng cao Một số model checker nổi bật đáng chú ý là Spin [12], Java Pathfinder [13], NuSMV [14] và PAT [15]
2.2.1 Mô hình hoạt động của model checking
Mô hình hoạt động của kỹ thuật model checking được minh họa như hình dưới:
Hình 2.4: Mô hình hoạt động của model checking
Một quá trình của model checking bao gồm các giai đoạn chính sau:
Mô hình hóa (Modeling phase): o Mô hình hóa hệ thống cần kiểm tra, sử dụng ngôn ngữ đặc tả cho từng model checker o Kiểm tra và đánh giá nhanh mô hình hệ thống bằng cách thực thi một số giả lập o Chuẩn hóa thuộc tính cần kiểm tra dùng ngôn ngữ đặc tả thuộc tính
Thực thi (Running phase): thực thi model checker để kiểm tra tính hợp lệ của các thuộc tính trong mô hình hệ thống
Phân tích (Analysis phase): phân tích kết quả kiểm tra như sau: o Thuộc tính đã kiểm tra có hợp lệ không? Nếu thỏa mãn thì tiếp tục chuyển sang xét các thuộc tính khác o Nếu thuộc tính cần xét không hợp lệ, cần thực hiện những bước sau:
Phân tích phản ví dụ được tạo ra
Cải tiến mô hình, thiết kế hệ thống
Thực hiện lặp lại toàn bộ quy trình
Satisfied Violated + Counter example Simulation Location error
Trang 15 o Nếu xảy ra lỗi tràn bộ nhớ, cần tìm cách thu giảm mô hình và thử lại
2.2.2 Các đặc điểm của model checking
So với các kỹ thuật kiểm tra khác, model checking có những ưu điểm đáng chú ý sau:
Model checking là phương pháp kiểm tra dựa vào mô hình có thể áp dụng rộng rãi cho nhiều lĩnh vực ứng dụng như hệ thống nhúng, công nghệ phần mềm và thiết kế phần cứng Ưu điểm lớn của việc kiểm tra dựa vào mô hình là ta không cần thật sự thực thi những đoạn mã cần kiểm tra, do đó có thể loại trừ rủi ro gây ra bởi các đoạn mã độc hại
Model checking hỗ trợ kiểm tra từng phần, nghĩa là các thuộc tính có thể được kiểm tra độc lập lẫn nhau, do đó cho phép việc kiểm tra chỉ cần tập trung vào các thuộc tính quan trọng trước Kiểm tra theo hướng model checking không cần một tập đặc tả yêu cầu đầy đủ
Model checking thực hiện kiểm tra toàn bộ các luồng thực thi của chương trình, do đó không cần thao tác xác định vùng có nhiều khả năng xảy ra lỗi nhất như khi thực hiện kiểm thử hay thực thi giả lập
Kỹ thuật concolic testing
Concolic (là sự kết hợp của hai từ concrete và symbolic) testing là kỹ thuật kết hợp việc thực thi chương trình với dữ liệu cụ thể (concrete execution) với việc thực thi dựa trên mô phỏng ký tự (symbolic execution [16]) Đây là kỹ thuật sinh test-case hiệu quả được sử dụng phổ biến trong thời gian gần đây So với kỹ thuật kiểm thử hộp trắng truyền thống, kỹ thuật concolic testing nhận được nhiều sự quan tâm nhờ khả năng thu gọn số lượng đường điều kiện (path condition) cần kiểm tra, nhờ đó giúp khắc phục sự bùng nổ trạng thái trong phương pháp kiểm tra mô hình
Lấy thí dụ, với chương trình được đưa ra trong Bảng 2.2, ta sẽ có hai nhánh điều kiện chính là (x!=y) và (2*x = x+10) Với phương pháp kiểm thử hộp trắng truyền thống, ta sẽ có ba đường điều kiện cần kiểm tra Khi áp dụng kỹ thuật
Bảng 2.2: Thí dụ minh họa cho concolic testing void foo (int x, int y)
Trang 19 concolic testing, trước tiên ta sẽ chọn các giá trị ngẫu nhiên cho x và y, thí dụ x=1 và y=2 Với việc thực thi concrete execution, chương trình sẽ đi qua dòng 0 bởi điều kiện x!=y là đúng, tuy nhiên không thể đi qua dòng 1 do điều kiện 2*x = x+10 không được thỏa mãn Song song với concrete execution, quá trình symbolic execution cũng có cùng luồng thực thi, tuy nhiên kỹ thuật này xem x và y như các biến ký tự thay vì là các giá trị cụ thể Điều kiện (x!=y) (2*x != x+10) được gọi là một đường điều kiện Để quá trình kiểm tra đi theo một đường thực thi khác trong lượt kiểm tra tiếp theo, phương pháp concolic testing lấy điều kiện cuối cùng nhất, ở đây là 2*x != x+10, và thực hiện phủ định nó, với điều kiện trên sẽ tạo thành 2*x = x+10 Tiếp theo, quá trình này sẽ sử dụng một bộ kiểm tra tự động dựa trên chứng minh (automated theorem prover) để tìm các giá trị thích hợp cho các biến x và y thỏa mãn điều kiện mới được tạo ra là (x!=y) (2*x=x+10) Giả sử các giá trị được tạo ra lần lượt là x và y=5 Tiếp tục thực thi chương trình trên bộ giá trị mới này, ta sẽ gặp trạng thái lỗi Như vậy, ta chỉ cần khảo sát qua hai đường điều kiện với thí dụ trên nếu sử dụng kỹ thuật concolic testing
Về cơ bản, giải thuật thực hiện concolic testing gồm có những bước chính sau: i Phân loại tập các biến để tạo ra tập biến đầu vào Các biến này sẽ được xem như là các biến ký tự trong suốt quá trình symbolic execution Tất cả các biến còn lại sẽ được xem như các giá trị thực ii Cải tiến chương trình sao cho mỗi thao tác có thể ảnh hưởng đến giá trị một biến ký tự hoặc một đường điều kiện đều được lưu lại ở một tập tin lưu vết Làm thao tác tương tự với trường hợp xảy ra lỗi iii Chọn một tập đầu vào ngẫu nhiên để bắt đầu quá trình kiểm tra iv Thực thi chương trình v Thực thi symbolic execution trên tập tin lưu vết, tạo tập các ràng buộc ký tự (bao gồm các đường điều kiện) vi Thực hiện đảo dấu đường điều kiện cuối cùng chưa từng được đảo dấu để có thể thực hiện một được thực thi mới Nếu không có đường điều kiện nào có thể đảo dấu, dừng quá trình kiểm tra
Trang 20 vii Gọi một bộ hỗ trợ chứng minh tự động (automated theorem prover) để tạo dữ liệu đầu vào mới Nếu không có dữ liệu đầu vào nào thỏa mãn tập ràng buộc hiện tại, trở lại bước (vi) để thử luồng thực thi tiếp theo viii Trở lại bước iv
Tuy nhiên, trong thực tế cũng có những biến thể của quá trình trên như được liệt kê ở dưới đây:
Giải thuật trên thực hiện quá trình tìm kiếm theo chiều sâu trên tập các cây chứa các luồng thực thi có thể có Trong thực tế, các chương trình có thể có các đường điều kiện rất lớn hay thậm chí là vô hạn – trường hợp rất phổ biến khi kiểm thử trên các cấu trúc dữ liệu có kích thước hay độ dài không giới hạn Để tránh mất quá nhiều thời gian trong một mảng nhỏ của chương trình, quá trình tìm kiếm nên có giới hạn độ sâu sẽ xét đến
Quá trình thực thi với symbolic execution và các automated theorem prover đều có giới hạn trong lớp các ràng buộc mà chúng có thể biểu diễn và xử lý Lấy thí dụ với một automated theorem prover dựa trên toán học tuyến tính sẽ không giải quyết được các đường điều kiện không tuyến tính như xy = 6 Mỗi khi gặp dạng điều kiện như trên, quá trình symbolic execution sẽ thay thế giá trị thực của một trong các biến vào biểu thức ràng buộc để đơn giản hóa nó Một phần quan trọng trong việc thiết kế một hệ thống concolic testing là tạo một bộ ký tự đại diện đủ chính xác để biểu diễn các ràng buộc cần thiết
Xét trên khía cạnh đối lập, kỹ thuật concolic testing cũng có một số hạn chế như sau:
Nếu hành vi của chương trình là không đơn định, kỹ thuật này có thể đi theo nhiều luồng thực thi khác nhau thay vì chỉ một Điều này có thể dẫn đến quá trình tìm kiếm không bao giờ dừng lại và mức độ bao quát chương trình thấp
Ngay cả đối với các chương trình đơn định, một số yếu tố trong chương trình cũng có thể làm giảm mức độ bao quát của kỹ thuật này như: hiển thị ký tự thiếu chính xác, như việc thất bại trong việc tìm vùng tiềm năng trong cần xét trong một cây thực thi lớn hay vô hạn
Chương trình hoàn toàn trộn lẫn trạng thái với các biến, như các phép toán mã hóa cơ bản, tạo nên rất nhiều kiểu biểu diễn ký tự mà chúng không thể giải được trong thực tế Lấy thí dụ với điều kiện "if (md5_hash(input) == 0xdeadbeef)" cần một theorem prover để dịch ngược hàm MD5 2 , và như ta đã biết thì thực tế ta không thể tìm ra prover nào có thể thực hiện việc trên Các nghiên cứu nổi tiếng dựa trên ý tưởng này trong thời gian gần đây có thể kể đến là DART [24], SYNERGY [25], DUALIZER [26] hay DASH [27].
Lý thuyết về diễn dịch trừu tượng (abstract interpretation)
Diễn dịch trừu tượng (abstract interpretation [17][18][19][20]) là phương pháp hình thức hóa các tư tưởng trừu tượng hóa của các cấu trúc toán học vào các đặc tả tính chất và các phương thức chứng minh trong các hệ thống máy tính Phần cơ sở lý thuyết này sẽ mô tả sơ lược về abstract interpretation, đồng thời đưa ra một số các yếu tố quan trọng trong lý thuyết này
2.4.1 Một số khái niệm sơ bộ
2.4.1.1 Một số khái niệm về lý thuyết lattice
Một thứ tự bán phần (partial order) là một quan hệ có tính phản xạ, đối xứng và có tính truyền Một poset là một cặp X, với X là một tập hợp và là quan hệ thứ tự bán phần trên X Một lược đồ Hasse có thể được dùng để diễn tả một poset X, với cung với a b và c X: a b c
Một lattice X, , , là một poset X, với mọi a, b có least upper bound (lub) a b và một greatest lower bound (glb) a b Một complete lattice là một poset X, với mọi tập con Y X đều có một lub Y Một complete lattice cũng có glb (được định nghĩa: X = {y | x X : y x}) tương ứng Một
2 http://en.wikipedia.org/wiki/MD5
Trang 22 complete lattice có hai phần tử và lần lượt tương ứng với X và X Theo đó, một complete lattice được xác định bởi X, , , , ,
Một chuỗi các poset X, là một tập con C X sao cho x y hoặc y x với mọi x, y trong X
2.4.1.2 Một số khái niệm về lý thuyết category
Một hàm f: X Y với hai toán tử g: X X và h: Y Y sao cho h(f(x)) f(g(x)) với mọi x X được gọi là một morphism hay homomorphism
Một hàm f: X Y được gọi là một monotone nếu X, và Y, là các poset và x X, y Y, x y f(x) f(y) Một ánh xạ monotone còn được gọi là bảo toàn thứ tự
Một hàm f: X Y được gọi là continuous nếu X, và Y, là các poset và với mọi chuỗi C của X sao cho tồn tại C thì sẽ tồn tại f(C), và ta có f( C) f(C)
2.4.1.3 Một số khái niệm về lý thuyết fixpoint
Cho f là một hàm của tập X, ta có các định nghĩa sau cho poset X, : fixpoints: fp(f) được định nghĩa bởi {x X | f(x) = x} prefixpoints: prefp(f) được định nghĩa bởi {x X | x f(x)} postfixpoints: postfp(f) được định nghĩa bởi {x X | f(x) x}
Least fixpoint, lfp, của một hàm f trên tập X thỏa mãn f(lfp) = lfp và x X:
(f(x)=x) (lfp x) Greatest fixpoint, gfp, cũng có thể được định nghĩa tương tự Định lý Knaster Tarski Fixpoint: Một ánh xạ monotone f trên một complete lattice X, , , , , có một least fixpoint và một greatest fixpoint là lfp = postfp(f) và gfp = prefp(f)
2.4.1.4 Kết nối Galois Định nghĩa: X, và Y, là các poset; một cặp : X Y và : Y X là một kết nối Galois (Galois connection) nếu và chỉ nếu { m X, n Y, (m) n m (n)} và được ký hiệu là
Trang 23 Định lý: chỉ tồn tại nếu và chỉ nếu: là monotone, và là monotone, và x X, x ( (x)), và y Y, ( (y)) y
2.4.2 Sơ lược về abstract interpretation
Abstract interpretation diễn tả các mối quan hệ trong các miền mà dữ liệu được tổ chức thành các tập lattices [17][21], nghĩa là giữa các phần tử của cùng miền dữ liệu có một quan hệ thứ tự bán phần Xem xét hai miền giá trị: miền cụ thể (concrete) và miền trừu tượng (abstract) như trong Hình 2.7 Ta định nghĩa hai hàm: hàm trừu tượng hóa và hàm cụ thể hóa , trong đó hàm trừu tượng hóa sẽ ánh xạ một đối tượng cụ thể sang một đối tượng trừu tượng và hàm sẽ thực hiện điều ngược lại: ánh xạ một đối tượng trừu tượng sang đối tượng cụ thể mà nó biểu diễn
Hình 2.7: Thí dụ đơn giản về abstract interpretation
Trong Hình 2.7, miền giá trị cụ thể là tập các số nguyên và miền giá trị trừu tượng là tập các khoảng số Quan hệ thứ tự bán phần trong các tập này là quan hệ tập con Ta định nghĩa (X) là Interval(min(X),max(X)), và (Interval(a,b)) là {x: x
I and {a x b} Đối tượng cụ thể {1,3,5} theo đó được ánh xạ vào Interval(1,5) thông qua hàm và Interval(1,5) ánh xạ vào đối tượng cụ thể
Một abstract interpretation được gọi là nhất quán (consistent abstract interpretation) nếu ( (y))=y, y Abstract Lấy thí dụ với abstract interpretation như ở Hình 2.7, ta có ( (y))=y với y là một giá trị khoảng bất kỳ, thí dụ
( ([1,5])) = [1,5] Ta nói rằng khi một abstract interpretation là nhất quán, dữ liệu của chúng sẽ tiến đến điểm dừng (fixed points), nghĩa là chúng sẽ không thay đổi dù cho ta có tiếp tục thực hiện phép toán cụ thể hóa thêm bao nhiêu lần nữa
Một tính chất của abstract interpretation là khi thao tác cụ thể hóa được thực hiện thêm lần nữa thì tập giá trị cụ thể sẽ tập giá trị cụ thể ban đầu, với là thứ tự bán phần được định nghĩa trong miền Concrete Lấy thí dụ trong Hình 2.7, với là quan hệ tập con được ký hiệu ; ta có {1,2,3,4,5} {1,3,5} Theo đó nếu một giá trị nào đó trong tập dữ liệu cụ thể gây ra lỗi cho chương trình, giá trị này cũng luôn xuất hiện trong tập giá trị thực sau khi được cụ thể hóa lần nữa Điều này giúp cho việc phát hiện lỗi thành công nếu việc kiểm tra tập được cụ thể hóa lại được thực hiện đúng đắn
Trong lĩnh vực kiểm tra chương trình, một chương trình cụ thể có thể được trừu tượng hóa thành chương trình trừu tượng để giúp quá trình kiểm tra được thực thi hiệu quả hơn Trong trường hợp này, miền trừu tượng phải thỏa mãn các điều kiện sau: (i) là tập lattice, nghĩa là có thể định nghĩa được một quan hệ thứ tự bán phần trên miền trừu tượng; (ii) điều kiện kiểm tra cũng được xét đến trong miền trừu tượng; (iii) miền trừu tượng hỗ trợ diễn dịch; nghĩa là phương thức chuyển đổi giá trị dữ liệu trong miền trừu tượng là được định nghĩa tốt (well-defined); và (iv) sự ánh xạ giữa chương trình cụ thể và chương trình trừu tượng sẽ tạo thành một consistent abstract interpretation
2.4.3 Các khái niệm trong abstract interpretation
Ngữ nghĩa của ngôn ngữ lập trình định ra ngữ nghĩa của các chương trình viết bằng ngôn ngữ đó Ngữ nghĩa của một chương trình cung cấp mô hình toán học chính quy cho mọi trạng thái có thể xảy ra của một hệ thống máy tính đang chạy chương trình này trong các môi trường có thể có Những phần tiếp theo sẽ
Trang 25 giải thích tại sao ngữ nghĩa của một chương trình có thể được xem như một lời giải của một biểu thức fixpoint Sau đó, để so sánh ngữ nghĩa, ta sẽ chứng minh rằng mọi ngữ nghĩa của một chương trình có thể được tổ chức phân cấp thông qua trừu tượng hóa
Theo nghiên cứu tại [21] của P Cousot, ngữ nghĩa lưu vết (trace semantics) là ngữ nghĩa chính xác nhất khi quan sát việc thực thi chương trình Theo quan sát trên một khoảng thời gian rời rạc, việc thực thi một chương trình có sự tương tác nhất định với môi trường của nó là một tập các trạng thái bắt đầu từ trạng thái khởi đầu, sau đó chuyển dịch từ một trạng thái sang trạng thái tiếp theo bằng cách thực thi một thao tác nguyên tử hoặc một sự chuyển dịch, và kết thúc ở trạng thái kết thúc bình thường hoặc kết thúc ở một trạng thái lỗi hoặc ở trong trạng thái không thể kết thúc (trong đó các phần tử lưu vết là vô hạn), như minh họa ở Hình 2.8 (các hình vẽ từ 2.8-2.16 được lấy từ [37]).
Hình 2.8: Minh họa của lưu vết tính toán
2.4.3.3 Ngữ nghĩa lưu vết fixpoint nhỏ nhất
Theo [21], ta định nghĩa ngữ nghĩa lưu vết ở dạng fixpoint là lời giải nhỏ nhất của phương trình ở dạng X = F(X), trong đó X là tập các lưu vết hữu hạn và các lưu vết vô hạn
Tóm lược một số công trình nghiên cứu liên quan
Trong công nghệ phần mềm, lợi ích của việc thực hiện unit testing là không thể bàn cãi, tuy nhiên trên thực tế, nó lại rất ít khi được thực hiện đầy đủ bởi người lập trình bởi chi phí và thời gian bỏ ra cho nó quá lớn, và bởi một phần do tâm lý của người lập trình thường mong muốn việc kiểm thử (hộp đen) sẽ được thực hiện ở các giai đoạn sau bởi các kiểm thử viên Từ thực tế trên, một vấn đề bức thiết được đặt ra là phải tự động hóa được quá trình kiểm thử này Phương thức đơn giản nhất để thực hiện mục tiêu trên là tạo ra một bộ kiểm thử ngẫu nhiên, tuy nhiên phương pháp này có nhiều hạn chế do độ phủ trên các luồng thực thi của chương trình thấp Do đó, mục tiêu chính của công cụ DART (Directed Automated Random Test [24]) là nhằm tự động hóa quá trình unit testing một cách hiệu quả mà không cần phải tốn công sức để viết test-case và viết mã chương trình Đầu tiên, DART sử dụng phân tích tĩnh để tạo dữ liệu test-case ngẫu nhiên, sau đó sử dụng phân tích động để đánh giá mã nguồn và hướng dẫn các luồng thực thi sau đi vào những luồng chương trình chưa được thực thi Kỹ thuật DART bao gồm ba bước chính là (i) rút trích giao diện (interface extraction) một cách tự động từ mã nguồn, (ii) tạo test-case ngẫu nhiên từ đặc tả trên, và (iii) sinh test-case động để hướng việc thực thi đến các luồng chương trình chưa được xét trước đó
Việc rút trích giao diện trong DART được thực hiện bằng cách phân tích cấu trúc mã nguồn của chương trình để định ra một giao diện (interface) và kiểu của giao diện này Thông tin về giao diện này bao gồm các tham số của một phương thức chính định nghĩa bởi người dùng cũng như mọi hàm hay biến nằm ngoài phương thức chính này
Sau khi giao diện đã được rút trích, một tập giá trị đầu vào ngẫu nhiên sẽ được tính toán dựa vào thông tin các kiểu dữ liệu của giao diện Tập giá trị ngẫu nhiên này được xem là test-case đầu tiên cần kiểm tra
Tiếp đó, thông qua việc thực thi động, các điều kiện của từng nhánh thực thi đều được lưu lại Sau khi một thao tác thực thi hoàn tất, điều kiện của nhánh thực thi cuối cùng của chương trình sẽ được phủ định và được tính toán để ra test-case
Trang 36 cho lần thực thi tiếp theo Theo cách này, lần thực thi tiếp theo sẽ chắc chắn đi theo một luồng thực thi chương trình khác với lần trước đó
Nhìn chung, DART có những ưu điểm chính là giúp cho quá trình unit testing được thực hiện hoàn toàn tự động mà không cần phải tạo test-case bằng tay, không tạo ra cảnh báo sai (nghĩa là nếu chương trình không gây ra lỗi thì chắc chắn DART sẽ không đưa ra cảnh báo lỗi), tuy nhiên DART có thể không dừng Đồng thời, một lưu ý trong DART là các lời gọi hàm bên ngoài (external functions) được xem như là một hộp đen, nghĩa là DART đơn giản là giả lập một giá trị ngẫu nhiên phù hợp với kiểu trả về của hàm đó chứ không thực sự quan tâm đến ngữ nghĩa của hàm này
Chủ đề chính của công trình nghiên cứu trong Synergy [25] là kiểm tra xem một chương trình có thỏa mãn một thuộc tính an toàn định trước hay không Một nhận xét được đưa ra trong công trình này là: testing (tìm test-case và đường thực thi không thỏa mãn một thuộc tính định trước) sẽ phát huy ưu điểm khi việc tìm ra lỗi là dễ và không dễ để thực hiện chứng minh, còn verification (tìm một bằng chứng (proof) để chứng minh rằng mọi đường thực thi của chương trình đều thỏa mãn một thuộc tính nào đó) sẽ là giải pháp tối ưu khi dễ tìm thấy bằng chứng và việc tìm ra lỗi là không dễ
Do đó, Synergy thực hiện việc kết hợp under-approximate (thao tác testing) và over-approximate (thao tác verification) Quá trình over-approximation được dùng để giúp dẫn hướng quá trình under-approximation tìm ra lỗi nhanh hơn, đồng thời under-approximation được dùng để giúp thao tác over-approximation tìm ra bằng chứng hiệu quả hơn Nói cách khác, Synergy dẫn hướng việc testing giúp tìm ra lỗi một cách hiệu quả hơn Đồng thời, khi một phần nào đó của chương trình dễ dàng chứng minh được là an toàn, Synergy sẽ nhanh chóng tập trung quá trình testing vào những vùng chương trình khác
Trên thực tế, Synergy là sự kết hợp của nhiều giải thuật khác nhau: (i) phương thức tìm counter-example trong SLAM, BLAST [34], (ii) phương pháp
Trang 37 dẫn hướng kiểm tra trong DART [24], và (iii) giải thuật cải tiến phân vùng như trong nghiên cứu của Lee-Yannakakis [35]
Lược đồ hoạt động của Synergy được mô hình hóa như Hình 2.17 3
Hình 2.17: Sơ đồ phác thảo giải thuật xử lý trong Synergy
Theo sơ đồ trên, giải thuật trong Synergy được bắt đầu bằng việc khởi tạo các test-case ngẫu nhiên và các bằng chứng ban đầu Trong suốt quá trình thực thi, Synergy sẽ tiến hành thực thi testing để tìm ra lỗi, và nếu thất bại sẽ thực hiện verification để tìm ra bằng chứng cho tính đúng đắn của chương trình Nếu cả hai quá trình trên đều thất bại, Synergy sẽ tiếp tục xét xem còn đường thực thi nào chưa được xét đến trong quá trình testing hay không, nếu có sẽ tiếp tục quay lại
3 Hình vẽ đượ c lấy từ http://research.microsoft.com/en-us/projects/yogi/synergy-fse2006.pptx
Trang 38 đầu quá trình để tiếp tục thao tác testing và verification, nếu không sẽ tiến hành việc cải tiến bằng chứng và quay lại bước ban đầu Giải thuật sẽ dừng khi quá trình testing tìm ra lỗi, hoặc khi quá trình verification tìm ra một bằng chứng chứng minh rằng chương trình không xảy ra lỗi
Phương pháp đề ra trong Dualizer [26] là mở rộng bộ phân tích tĩnh (static analyzer) vốn thường dùng để chứng minh tính đúng đắn để có thể tìm ra lỗi Phương pháp này dựa trên việc phân tích over-approximation và việc phân tích kép đồng thời (dual simultaneous analyses)
Trong Dualizer, ngoài việc áp dụng nguyên lý phân tích dựa trên over- approximation, việc phân tích một trạng thái chương trình sẽ được tiến hành đồng thời với việc phân tích các trạng thái bổ sung với nó Thí dụ khi phân tích để kết luận một chương trình có lỗi hay không, việc phân tích sẽ được tiến hành đồng thời cả việc tìm các điều kiện để chương trình không có lỗi và điều kiện để chương trình xảy ra lỗi Sau đó, các kết luận trên chương trình theo ngữ nghĩa thực sẽ được đưa ra dựa vào phạm vi bao phủ / giao nhau của cả hai trường hợp chương trình trừu tượng có lỗi và không
Thí dụ với trường hợp cần phân tích chương trình có lỗi hay không, ta phân tích trên chương trình đã được over-approximation để tìm ra các luồng thực thi dẫn đến các trạng thái OK (không có lỗi) và ERR (có lỗi) như Hình 2.18 4
Hình 2.18: Minh họa phân tích Must-May trong Dualizer
Từ miền kết quả của ERR và OK như trên, ta có thể đưa ra các kết luận về tính chắc chắn – có thể (must-may) của chương trình chính như sau:
4 Hình vẽ đượ c lấy từ http://www.mpi-sws.org/~cpopeea/research/dual.sac10.ppt
NEVER_BUG = OK not ERR: chương trình thực không có lỗi hoặc không dừng
MUST_BUG = ERR not OK: chương trình thực chắc chắn có lỗi hoặc không dừng
MAY_BUG = OK ERR: chương trình thực có thể có lỗi, không lỗi, hoặc không dừng
Trong nghiên cứu của Dash [27], một giả thuyết định được đặt ra là nếu ta xem quá trình testing là một hoạt động thuộc về "hộp trắng", và ta có thể “quan sát” được những gì xảy ra trong chương trình (với symbolic execution), ta có thể (i) tạo test-case hướng đến việc tìm ra lỗi, hoặc (ii) chứng minh được rằng một tính chất là đúng với mọi dữ liệu đầu vào
GIẢI PHÁP KIỂM TRA CHƯƠNG TRÌNH CHƯA HOÀN CHỈNH
Chương trình chưa hoàn chỉnh (incomplete program)
Để làm rõ hơn về khái niệm chương trình chưa hoàn chỉnh (incomplete program) được sử dụng trong luận văn này, ta hãy xét đến quá trình kiểm tra một chương trình như ở Bảng 3.1 Trong chương trình gốc như ở mục (a), chương trình chính sẽ lần lượt gọi hai hàm func1 và func2 Trong đó, func1 là một hàm chứa ngữ nghĩa đơn giản và hàm func2 thực hiện một thao tác quan trọng cần được kiểm tra kỹ Giả thiết rằng khi giá trị T-error được truyền vào func2 thì mô hình giả lập của chương trình có thể phát hiện ra lỗi thật tương ứng của hệ thống nhờ vào phương pháp model checking
Thông thường, để kiểm tra một chương trình bằng phương pháp model checking, ta cần chuyển đổi chương trình chứa các lời gọi hàm thành chương trình không chứa các lời gọi hàm như chương trình ở mục (b) Khi sử dụng kỹ thuật concolic testing trên chương trình đã chuyển đổi, ta dễ dàng nhận thấy có bốn đường ràng buộc chính là (i) a>10 (ii) a< a>5; (iii) a0; và (iv) a10) return 2*n; else if (n0) b = func1(a); func2(b); return OK;
(a) Modular program void main() { int a=1,b-1; read_from_input(&a); if (a>0) { if (a>10) b = 2*a; else if (a10 => \result==2*n); ensures (n \result ==T_error); ensures ((n< && n>=5) => \result==n)*/ int func1(int n); void main() { int a=1,b=1; read_from_input(&a); if (a>0) b = func1(a); func2(b); return OK;
Trang 45 cần thiết để kiểm tra chương trình theo model checking khi cần cung cấp đầu vào cho mô hình tương ứng
Nhằm làm rõ hơn, ta xem xét quá trình thực hiện concolic testing cho chương trình trong mục (c) Ta sẽ sinh được hai test-cases tương ứng với hai ràng buộc a>0 và a0) b = 7;
(b) Simulated program with test-case a = 7 void main()
{ int a=1,b=1; a = 3; //test-case 3 if (a>0) b = T-error;
(c) Simulated program with test-case a = 3 void main() { int a=1,b=1; a = 7; //test-case 4 if (a>0) b = unknown;
(d) Simulated program with test-case a = 7
Trang 46 kiện như trong Bảng 3.1 (c) Bằng cách kết hợp ngữ nghĩa của tiền và hậu điều kiện với các ràng buộc trong luồng thực thi của chương trình, ta có thể tạo đủ các ràng buộc cần thiết để tạo test-case Lấy thí dụ với chương trình như trong Bảng 3.1 (c), khi phân tích các luồng ràng buộc chính của chương trình, ta được ( 1 ): a>0 và ( 2 ): a10; ( 2 ): a< a>5; và ( 3 ): a0
Tiếp đó, kết hợp các ràng buộc đã có ở trên theo luồng thực thi chính của chương trình, ta sẽ được các ràng buộc kết hợp hợp lệ sau: ( 1 1 ): a>10; ( 1 2 ): a< a>5; ( 1 3 ): a0 và ( 2 ): a 0), trả về kết quả x * (x + 1)
Ngược lại, trả về kết quả x * (x + 1) (x 2 + x + 1) Ở đoạn chương trình trên, pow là hàm toán học dùng để tính giá trị lũy thừa của một số, và được định nghĩa trong thư viện math.h của trình biên dịch C Khi thực hiện kiểm tra đoạn chương trình trên, do các công cụ kiểm tra tự động
Bảng 3.3: Minh họa chương trình chứa lời gọi hàm thư viện int foo (int x)
(theorem provers và model checkers) không hiểu ý nghĩa của lời gọi hàm này, nên sẽ trả về kết quả báo chương trình có lỗi, không thể kiểm tra được Để thực hiện kiểm tra chương trình dạng này, các thao tác để biến chương trình chưa hoàn chỉnh thành chương trình mô hình tự hoàn chỉnh như sau:
Tại bước sinh test-case dựa vào đặc tả của chương trình
(Specification-based Test-case Generation): để thực hiện việc sinh test-case của chương trình, ta sẽ thực hiện duyệt qua các luồng thực thi chính của chương trình, rút trích các ràng buộc chính như đã mô tả ở phần 3.2.1 Khi gặp các lời gọi hàm thư viện, bộ Specification Logic Extraction sẽ thực hiện thực thi động (concrete execution) lời gọi hàm này và lưu lại kết quả tương ứng Như thế, toàn bộ luồng thực thi của chương trình sẽ được duyện qua và ta sẽ sinh được các bộ test-case tương ứng
Giả sử tại bước này, ta sinh được 2 test-case là x = 2 và x = -4 ứng với chương trình ở Bảng 3.3 Ứng với bộ giá trị này, ta cũng lưu lại kết quả thực thi động của lời gọi hàm pow(2, 2) = 4 và pow(-4, 4) = 256
Tại bước chuyển đổi mã nguồn (Code Transformation): ứng với từng bộ test-case, ta sẽ thực hiện thay thế các lời gọi hàm với các kết quả tương ứng Như đã mô tả trong phần 3.2.2 , việc thay thế này thực hiện ứng với từng bộ test-case như sau: o Với test-case x = 2, ở bước thay thế các lời gọi hàm đến được, ta thay thế dòng 2: y = pow(x, 2) thành y = 4 Sau đó, tại bước thay thế các lời gọi hàm không dến được, ta thay thế dòng 4: y = pow(x, 4) thành y = 0 Do thực chất lời gọi hàm ở dòng 4 là không đến được với test-case x = 2, do đó việc thay thế lời gọi hàm bằng một giá trị bất kỳ sẽ không làm thay đổi ngữ nghĩa của chương trình o Với test-case x = -4, ở bước thay thế các lời gọi hàm đến được, ta thay thế dòng 4: y = pow(x, 4) thành y = 256 Sau đó, tại bước thay thế các lời gọi hàm không dến được, ta thay thế dòng 2: y = pow(x, 2) thành y=0
Vậy ứng với chương trình gốc ở Bảng 3.3, ta có hai đoạn chương trình chưa hoàn chỉnh tương ứng như ở Bảng 3.4 Ở bước thông dịch hướng mô hình (Model-oriented Transaltion), các chương trình tự hoàn chỉnh ở trên sẽ được biến đổi sang ngôn ngữ mô hình tương ứng (ở đây là ngôn ngữ Promela) Ta có chương trình ở ngôn ngữ Promela ở Bảng 3.5 tương ứng với chương trình tự hoàn chỉnh ở Bảng 3.4
Bảng 3.5: Mô hình tương ứng của chương trình chứa lời gọi hàm thư viện proctype m_foo(int m1_x; chan c)
:: else -> lb_4: m1_y = 0; fi; c ! (m1_x + m1_y); goto lb_2; lb_2: skip;
(a) Model description for test-case x = 2 proctype m_foo(int m1_x; chan c) { lb_1: skip; int m1_y; if :: m1_x > 0 -> lb_3: m1_y = 0;
:: else -> lb_4: m1_y = 256; fi; c ! (m1_x + m1_y); goto lb_2; lb_2: skip;
} (b) Model description for test-case x = -4
Bảng 3.4: Chương trình tự hoàn chỉnh của chương trình chứa lời gọi hàm thư viện int foo (int x)
(a) Self-complete program with test-case x = 2 int foo (int x) {
} (b) Self-complete program with test-case x = -4
3.3.2 Chương trình chứa các lời gọi thủ tục
Loại chương trình chưa hoàn chỉnh thứ hai sẽ được xét đến là các chương trình có chứa các lời gọi thủ tục, và ngữ nghĩa của các thủ tục này được định nghĩa bằng ngôn ngữ mô tả ACSL Một chương trình chưa hoàn chỉnh dạng này được minh họa như ở Bảng 3.6
Với chương trình ở Bảng 3.6, nếu ta chỉ sinh ra 2 test-case ứng với luồng thực thi chương trình là x = 1 (ứng với việc không thỏa điều kiện x > 5) và x = 6 (ứng với việc không thỏa điều kiện x > 5), ta sẽ thiếu test-case cần thiết cho trường hợp khi có thực hiện lời gọi hàm func1 nhưng không thỏa tiền điều kiện tương ứng (trong trường hợp không thỏa tiền điều kiện, chương trình sẽ gây ra lỗi) Đồng thời, do chương trình có chứa lời gọi thủ tục func1, các công cụ kiểm tra tự động sẽ đưa ra thông báo lỗi cú pháp và từ chối thực hiện kiểm tra Để thực hiện kiểm tra chương trình dạng này, các thao tác để biến chương trình chưa hoàn chỉnh thành chương trình mô hình tự hoàn chỉnh như sau:
Tại bước sinh test-case dựa vào đặc tả của chương trình
(Specification-based Test-case Generation): như đã mô tả ở phần 3.2.1 , trong quá trình thực thi symbolic execution, khi gặp các lời gọi thủ tục, bộ
Specification Logic Extraction sẽ thực hiện rút trích các ràng buộc từ đặc tả
ACSL của thủ tục để kết hợp với các ràng buộc từ chương trình chính Ứng với chương trình ở Bảng 3.6, các bước thực hiện sinh test-case bao gồm các luồng thực thi sau: o Tại lần sinh test-case đầu tiên, test-case x = 1 được sinh ra và ràng buộc thỏa mãn là (not (x>5)) được lưu lại
Bảng 3.6: Minh họa chương trình chứa lời gọi thủ tục int foo (int x)
Trang 54 o Ở lần sinh test-case thức hai, với việc đảo dấu biểu thức ràng buộc được thỏa mãn ở bước 1, ta được test-case x = 6 (thỏa mãn x>5) Với test-case này, lời gọi thủ tục func1(x) ở dòng 1 sẽ được thực thi, do đó tiền điều kiện của hàm này (x>0 && x5 && (x>0 && x5 nhưng không thỏa mãn x>0 && x skip; fi; c ! (m1_x + 5); goto lb_2; lb_2: skip;
Tại bước sinh test-case dựa vào đặc tả của chương trình
(Specification-based Test-case Generation): tương tự như thao tác sinh test- case cho lời gọi thủ tục ở phần 3.3.2 , ta sẽ có các test-case tương ứng là x=1, x=6 và x Đồng thời, thông qua việc rút trích và phân tích kết quả trả về của đặc tả hàm bằng ngôn ngữ ACSL, ta cũng lưu các kết quả trả về của các lời gọi hàm tương ứng ở dòng 1 là func1(6) = 26, func1(10) = 90 Tại bước chuyển đổi mã nguồn (Code Transformation): ứng với bộ ba test-cases ở trên, ta sẽ có ba chương trình tự hoàn chỉnh được sinh ra như ở Bảng 3.10
Tại bước thông dịch hướng mô hình (Model-oriented Transaltion): với ba chương trình ở Bảng 3.10, ta có các chương trình mô hình ở Bảng 3.11
Bảng 3.10: Chương trình tự hoàn chỉnh ứng với chương trình chứa lời gọi hàm int foo (int x)
(a) with test-case x = 1 int foo (int x) {
} (b) with test-case x = 6 int foo (int x) {
Chứng minh tính đúng đắn của giải pháp đề xuất
Ở chương này, luận văn sẽ chứng minh tính đúng đắn của giải pháp đã được đề nghị ở chương trước bằng cách vận dụng lý thuyết về abstract interpretation đã được đề cập trong mục 2.4
Với giải pháp được đưa ra ở mục 3.2 , ta gọi chương trình chưa hoàn chỉnh là P, và tập chương trình tự hoàn chỉnh là {P’} Giải pháp tạo chương trình tự hoành chỉnh đã đưa ra thực chất là một abstract interpretation với là hàm sinh ra test-case và giá trị tương ứng cho các lời gọi hàm/thủ tục, còn là thao tác tạo các chương trình chưa hoàn chỉnh bằng cách thay thế các giá trị tương ứng của các biến đầu vào cùng giá trị thực của lời gọi hàm/thủ tục Một cách hình thức, gọi X là tập các tham số đầu vào của hàm cần kiểm tra, C(X) là tập các lời gọi hàm/thủ tục trong chương trình, ta có các công thức sau:
Lấy thí dụ với đoạn chương trình như ở Bảng 3.13 (tương tự như đoạn chương trình ở Bảng 3.3), như chương trình đã phân tích ở 3.3.1 ta có các test-case tương ứng là x=2 và x=-4, do đó:
(P(X, C(X))) là hai đoạn chương trình (a) và (b) tương ứng với các test-case x=2 và x=-4 ở Bảng 3.4
Như đã đề cập ở mục 2.4.1 , trong lĩnh vực kiểm tra chương trình, một chương trình cụ thể có thể được trừu tượng hóa thành chương trình trừu tượng để giúp quá trình kiểm tra được thực thi hiệu quả hơn khi phép biến đổi trừu tượng thỏa mãn các điều kiện sau:
(i) miền trừu tượng là tập lattice, nghĩa là có thể định nghĩa được một quan hệ thứ tự bán phần trên miền trừu tượng;
(ii) điều kiện kiểm tra cũng được xét đến trong miền trừu tượng;
(iii) miền trừu tượng hỗ trợ diễn dịch; nghĩa là phương thức chuyển đổi giá trị dữ liệu trong miền trừu tượng là được định nghĩa tốt (well- defined); và
(iv) sự ánh xạ giữa chương trình cụ thể và chương trình trừu tượng sẽ tạo thành một consistent abstract interpretation
Ta sẽ lần lượt chứng minh rằng các điều kiện trên đều được thỏa mãn trong giải pháp được đề ra trong các phần tiếp sau
3.4.1 Miền trừu tượng là một lattice
Qua phép biến đổi , tập các lời gọi hàm ở chương trình cụ thể sẽ được biến đổi thành tập các tập hợp số nguyên, hoặc tập rỗng nếu chương trình gốc không chứa lời gọi hàm nào hoặc các lời gọi hàm không có kết quả trả về (các lời gọi thủ tục) Do đó, trên miền trừu tượng ta sẽ có các phần tử là các tập hợp các số nguyên
Trên tập hợp này, ta dễ dàng nhận thấy phép toán tập con (subset) là một phép toán thỏa mãn thứ tự riêng phần (partial order)
Bảng 3.13: Một chương trình chưa hoàn chỉnh int foo (int x)
Trên miền trừu tượng gồm tập các tập hợp số nguyên, xét hai phần tử bất kỳ a và b, ta luôn có least upper bound là a b, và greatest lower bound là a b
Từ những nhận xét trên, theo lý thuyết về lattice ở mục 2.4.1.1 , ta kết luận miền trừu tượng là một lattice
3.4.2 Điều kiện kiểm tra được xét đến trong tập trừu tượng
Trong luận văn này, ta xét đến cách biến đổi chương trình chưa hoàn chỉnh thành chương trình tự hoàn chỉnh bằng cách thay thế các lời gọi hàm / thủ tục đến được bằng các giá trị thích hợp, và thay thế các lời gọi hàm / thủ tục không đến được bằng giá trị bất kỳ Ta dễ dàng nhận thấy rằng đối với các lời gọi hàm / thủ tục không đến được trong một lần thực thi nào đó, việc tồn tại của hàm / thủ tục đó không làm thay đổi ngữ nghĩa của chương trình, do đó chúng được gán bằng một giá trị bất kỳ
Từ nhận xét trên, ta thấy việc thay thế không làm thay đổi bản chất ngữ nghĩa của chương trình, do đó điều kiện kiểm tra của chương trình gốc (chưa hoàn chỉnh) hoàn toàn được giữ nguyên và có thể áp dụng vào các chương trình tự hoàn chỉnh
3.4.3 Miền trừu tượng hỗ trợ diễn dịch
Trong mục 3.3 , luận văn đã mô tả cụ thể cách sinh các giá trị tương ứng cho các lời gọi hàm / thủ tục, tức là cách sinh ra các giá trị tương ứng cho miền trừu tượng Do đó, ta nói miền trừu tượng đã nêu hỗ trợ diễn dịch
3.4.4 Phép xấp xỉ là một consistent abstract interpretation
Sau lần xấp xỉ đầu tiên, các chương trình mới được tạo ra sẽ không chứa bất cứ một lời gọi hàm hay lời gọi thủ tục nào Do đó, nếu ta tiến hành phép xấp xỉ trên tập chương trình mới, ta sẽ được chính tập chương trình mới này, bởi sẽ không có tập test-case nào mới được sinh ra và không có lời gọi hàm nào được thay thế bằng giá trị thực tương ứng
Xét chương trình ở Bảng 3.13, sau lần xấp xỉ đầu tiên, ta sẽ được hai chương trình mới ở Bảng 3.4 Tiến hành xấp xỉ hai chương trình mới được sinh ra một lần nữa, ta vẫn sẽ được hai chương trình như ở Bảng 3.4, tức là chính nó
Từ nhận xét trên, ta thấy phép xấp xỉ đã đưa ra thỏa mãn điều kiện ( (y)) y, điều đó dẫn đến kết luận phép xấp xỉ này là một consistent abstract interpretation
Do phương pháp xấp xỉ được đề nghị ở chương này thỏa mãn 4 điều kiện đã được nêu ở trên, do đó ta có thể khẳng định rằng mọi lỗi xảy ra ở chương trình gốc ban đầu cũng sẽ xuất hiện ở một trong các chương trình tự hoàn chỉnh đã được tạo ra, với giả thuyết rằng tập test-case được sinh ra là đủ để bao phủ các trường hợp gây ra lỗi này
HIỆN THỰC ỨNG DỤNG KIỂM TRA MÔ HÌNH CHO CÁC CHƯƠNG TRÌNH CHƯA HOÀN CHỈNH
Tổng quan về ứng dụng
Mục tiêu của luận văn trong việc xây dựng ứng dụng minh họa là tạo nên một chương trình hỗ trợ sinh viên trong việc kiểm tra các bài lập trình cơ bản Một hệ thống tương tự là hệ thống Prove 6 được xây dựng bởi nhóm nghiên cứu SAVE 7 Mặc dù kết quả công việc hoàn toàn có thể tích hợp trực tiếp vào hệ thống Prove, luận văn vẫn quyết định xây dựng một ứng dụng mới dựa trên nền tảng mạng xã hội nhằm: (i) minh họa rõ hơn kết quả nghiên cứu của luận văn là tập trung vào việc hỗ trợ kiểm tra mô hình cho các chương trình chưa hoàn chỉnh, (ii) tận dụng những tính năng của mạng xã hội để có thể thu hút sự quan tâm và tăng sự hứng thú của sinh viên nhờ tốc độ lan truyền thông tin mạnh mẽ trên mạng xã hội thông qua các mối quan hệ bạn bè, và (iii) đề xuất ý tưởng xây dựng một mạng xã hội lĩnh vực hẹp (niche social network [22]) hỗ trợ cho giáo dục
Trong những năm gần đây, với sự bùng nổ về số lượng người dùng trên các mạng xã hội phổ thông như Facebook 8 , Twitter 9 , Google+ 10 , LinkedIn 11 ,
6 http://elearning.cse.hcmut.edu.vn/provegroup/
7 http://www.cse.hcmut.edu.vn/~save/
PInterest 12 , …, ngày càng có nhiều ý tưởng sử dụng mạng xã hội làm kênh truyền thông cũng như cho các mục đích thương mại Đối với các mục đích giáo dục, mạng xã hội là kênh thông tin rất tốt để thông tin kịp thời đến sinh viên, là nơi giao tiếp và chia sẻ kinh nghiệm giữa các sinh viên cùng cũng như khác lớp, khóa thông qua các hội nhóm, cũng là nơi mà sinh viên có thể tìm thấy các thông tin học thuật, giải trí thông qua các diễn đàn thảo luận, … Nhìn chung, việc tập trung thông tin vào một hệ thống mà các đối tượng tham gia (sinh viên, giảng viên, giáo vụ, đoàn hội, …) có thể tương tác lẫn nhau sẽ đem lại lợi ích to lớn trong việc học tập cũng như giải trí của sinh viên Do đó, ứng dụng minh họa trong luận văn này được xây dựng như một phần của mạng xã hội nhằm tận dụng những ưu điểm đã đề cập ở trên
Nhìn chung, trong ứng dụng được xây dựng sẽ có ba dạng người dùng chính là sinh viên, giảng viên, và người quản trị Các chức năng chính của ba dạng người dùng này được mô tả như trong Hình 4.1, Hình 4.2 và Hình 4.3
Rate An Assignment Comment On
Hình 4.1: Các chức năng chính của người dùng Sinh viên
Trang 65 Đối với đối tượng người dùng sinh viên, ngoài các chức năng chính của một mạng xã hội (như đăng ký, đăng nhập, kết bạn, tạo trang chủ tài khoản, gửi tin nhắn, tạo và xem blog, chia sẻ hình ảnh, chia sẻ nhạc và video, tạo và tham gia các sự kiện, tạo nhóm người dùng, …), người dùng sinh viên còn có các chức năng chính trong ứng dụng hỗ trợ kiểm tra chương trình tự động như sau: (i) Duyệt các bài tập hiện hành trên hệ thống, (ii) Xem thông tin chi tiết của một bài tập, (iii) Gửi bài lập trình để nhờ hệ thống kiểm tra, (iv) Tìm kiếm bài tập theo từ khóa, (v) Đánh giá một bài tập theo hệ thống đánh giá từ một đến năm sao, và (vi) Bình luận về một bài tập
Hình 4.2: Các chức năng chính của người dùng Giảng viên Đối với người dùng là giảng viên, ngoài các chức năng tương tác tương tự như đối với sinh viên, người dùng giảng viên còn có thêm chức năng quản lý kho bài tập của mình Việc quản lý này bao gồm các thao tác: xem, tạo, sửa, và xóa các bài tập do mình tạo ra
Loại người dùng cuối cùng trong hệ thống, cũng là người dùng nhiều quyền hạn nhất, đó là người quản trị hệ thống Trong ứng dụng minh họa này, ngoài các chức năng như của người dùng sinh viên và giảng viên, người quản trị còn có thể thực hiện thao tác xem/xóa/sửa trên tất cả các bài tập được tạo ra, đồng thời cũng có thể đánh dấu một bài tập nào đó là đặc sắc (featured assignments, các bài tập
Trang 66 này sẽ luôn được hiển thị đầu tiên ở trang chủ của ứng dụng và trang chủ của module kiểm tra chương trình) Ngoài ra, người quản trị cũng có thể quản lý mọi đối tượng chính trên mạng xã hội: từ các nội dung được tạo ra cho đến người dùng, cấu hình các hệ thống liên quan, …
Back-end Social Network Actions
Hình 4.3: Các chức năng chính của người Quản trị hệ thống
Kiến trúc tổng quát
Như đã đề cập ở trên, ứng dụng minh họa của luận văn được xây dựng dựa trên nền tảng mạng xã hội Cụ thể hơn, ứng dụng được hiện thực như một module của một trong những nền tảng tạo mạng xã hội mã nguồn mở nổi tiếng nhất là Boonex Dolphin 13 phiên bản 7.0.9 Mục đích của việc xây dựng ứng dụng dựa trên mã nguồn mở giúp việc nâng cấp và mở rộng hệ thống được dễ dàng hơn, đồng thời hệ thống cũng sẽ được thừa kế các cập nhật từ cộng đồng một cách thường xuyên hơn Luận văn đã chọn Boonex Dolphin để xây dựng ứng dụng bởi đây là một trong những phần mềm mã nguồn mở về xây dựng mạng xã hội phổ biến nhất (có 3,270,792 lượt tải về tính đến ngày 16/06/2012), với đầy đủ tính năng của một
13 http://www.boonex.com/dolphin
Trang 67 mạng xã hội, cộng đồng phát triển ứng dụng đông đảo (có 1243 modules và templates được phát triển bởi 286 nhà phát triển thứ ba, tính đến ngày 16/06/2012), và đây là một trong những số ít nền tảng mã nguồn mở hỗ trợ đầy đủ các ứng dụng trên nền mobile (cung cấp ứng dụng cho các dòng điện thoại, máy tính bảng dùng hệ điều hành iOS và Android)
Về cơ bản, ứng dụng được xây dựng sẽ có kiến trúc tổng quát như Hình 4.4
Specification-based Test-case Generation
Verficiation Module Social Network’s Features
Hình 4.4: Kiến trúc tổng quát của ứng dụng
Theo đó, chức năng kiểm tra chương trình được xây dựng như một module trong nền tảng mạng xã hội Boonex Dolphin, bên cạnh các chứng năng mạng xã hội khác như bạn bè, tin nhắn, chia sẻ hình ảnh, nhạc, video, … Toàn bộ hệ thống Boonex Dolphin sẽ được chạy trên phần mềm máy chủ web Apache HTP server có hỗ trợ biên dịch ngôn ngữ PHP và sử dụng cơ sở dữ liệu MySQL Khi thực hiện thao tác kiểm tra một chương trình chưa hoàn chỉnh, module Kiểm tra chương trình sẽ tương tác với hệ thống Kiểm tra chương trình chưa hoàn chỉnh được viết trên nền tảng Java để thực hiện các thao tác chính như đã đề cập ở mục 3.2 là sinh test-case dựa vào đặc tả, chuyển đổi chương trình chưa hoàn chỉnh thành chương trình tự hoàn chỉnh, và chuyển đổi chương trình sang ngôn ngữ mô hình ANTRL
Trang 68 và SPIN cũng là một bộ phận quan trọng trong hệ thống nhằm hỗ trợ việc phân tích mã nguồn ngôn ngữ và thực thi thao tác kiểm tra mô hình
Một luồng thực thi của chương trình được minh họa như Hình 4.5
Web Browser Web Server DB Server
2: Get Assignments 3: List Assignments 4: List Assignments
6: Get Assignment Detail 7: Returned Assignment 8: Returned Assignment
11: Return Testcases + Self-complete codes
12: Verify Self-complete Models 13: Verification Result 14: Verification Result
Hình 4.5: Một luồng thực thi chính của chương trình
Luồng thực thi này bao gồm các quá trình như sau: Đầu tiên, người dùng (sinh viên) sẽ sử dụng trình duyệt web để duyệt qua các bài tập đang có trong hệ thống (quá trình từ 1 – 4)
Khi đã chọn được một bài tập lập trình vừa ý, người dùng bấm chọn xem chi tiết bài tập đó (quá trình từ 5 – 8)
Sau khi đọc yêu cầu của đề bài, người dùng sẽ tiến hành viết code ngay trên trình duyệt để giải quyết yêu cầu được đề tra trong đề bài Khi người dùng đã cảm thấy thỏa mãn với lời giải của mình, người dùng sẽ gửi lời giải lên cho hệ thống để bắt đầu tiến hành quá trình kiểm tra (quá trình 9)
Khi nhận được lời giải từ phía người dùng, module Kiểm tra chương trình (trong Boonex Dolphin) sẽ dựa vào các thông tin bài tập để tạo ra chương trình mã nguồn cùng các đặc tả của các hàm/thủ tục cần thiết và gửi đến Hệ thống kiểm tra chương trình chưa hoàn chỉnh (hệ thống trên nền Java) (quá trình 10)
Tại quá trình 10 và 11: hệ thống kiểm tra chương trình chưa hoàn chỉnh sẽ tiến hành phân tích chương trình chưa hoàn chỉnh được gửi đến Quá trình này bao gồm ba thao tác chính đã được mô tả ở Hình 3.1 Kết thúc quá trình này, hệ thống sẽ gửi trả về module Kiểm tra chương trình (trong Boonex Dolphin) bộ kết quả bao gồm (i) các test-cases đã được sinh ra dựa vào việc phân tích chương trình và đặc tả, (ii) các chương trình mã nguồn tự hoàn chỉnh, và (iii) mô hình tương ứng ở ngôn ngữ Promela của các chương trình chưa hoàn chỉnh ở trên
Sau khi nhận được bộ dữ liệu trả về, module Kiểm tra chương trình sẽ tiến hành thực thi quá trình kiểm tra mô hình nhờ vào SPIN model checker (quá trình 12 và 13)
Tại thời điểm nhận được kết quả kiểm tra từ SPIN, module Kiểm tra chương trình sẽ phân tích kết quả này và báo về cho người dùng các test- cases đã được kiểm tra cùng với kết quả đúng/sai tương ứng Ở phần tiếp theo, luận văn sẽ điểm qua một số tính năng chính của ứng dụng thông qua các ảnh chụp màn hình
Một số hình ảnh của ứng dụng
Hình 4.6: Trang chủ của ứng dụng Ở trang chủ của ứng dụng như Hình 4.6, ta có thể thấy các thông tin chung trong mạng xã hội như các bài tập mới nhất, các hoạt động mới nhất, thành viên nổi bật, các thông tin thống kê, …
Hình 4.7: Trang chủ của module Verification
Trong trang chủ của module như Hình 4.7, người dùng có thể thấy tổng quát các tính năng được hỗ trợ trong module này Mặc định, người dùng có thể thấy các danh mục bài tập, các bài tập đặc sắc, các bài tập mới nhất, …
Hình 4.8: Trang nhập mã nguồn và kiểm tra kết quả
Khi bấm vào link của một bài tập, người dùng sẽ được dẫn đến trang xem và làm bài tập như ở Hình 4.8 Tại đây, người dùng sẽ thấy các thông tin chi tiết liên quan đến bài tâp bao gồm đề bài, mô tả chi tiết, các hàm ACSL được sử dụng, và một ô nhập liệu để người dùng nhập lời giải và kiểm tra Sau khi bấm nút submit, bài làm của người dùng sẽ được kiểm tra tự động và trả về kết quả trong cùng màn hình Trên màn hình này, người dùng cũng có thể bình luận, cũng như đánh giá chất lượng của bài tập đang xem
Hình 4.9: Trang tìm kiếm bài tập theo tag
Một bài tập thường sẽ liên quan đến một từ khóa nào đó, và từ khóa quan trọng có thể được nhập vào ở dạng các tag của bài tập Một bài tập có thể liên quan đến nhiều tags Người dùng có thể tìm kiếm các bài tập liên quan đến một tag cụ thể nào đó Như thí dụ ở Hình 4.9, các bài tập được đánh dấu tag là “triangle” được hiển thị theo kết quả tìm kiếm của người dùng
Hình 4.10: Trang hiển thị bài tập theo danh mục
Các bài tập trong hệ thống được chia theo nhiều danh mục khác nhau Ở dữ liệu mẫu của ứng dụng, luận văn đã chia các bài tập thành các mức độ khác nhau là dễ, trung bình và khó Người dùng có thể dễ dàng tìm kiếm các bài tập trong từng mức độ cụ thể bằng cách bấm vào danh mục tương ứng ở trang chủ của module Hình 4.10 thể hiện việc hiển thị các bài tập trong danh mục “Intermediate Level”
Ngoài ra, người dùng cũng có thể tìm kiếm theo nhiều điều kiện khác như: các bài tập mới nhất, các bài tập đặc sắc, các bài tập được xem nhiều nhất, …
Hình 4.11: Một trang quản trị thông tin trong module Verification
Ngoài các chức năng chính của ứng dụng được thể hiện ở phía người dùng, người quản trị có thể truy cập các chức năng quản trị hệ thống trong mục quản trị hệ thống Hình 4.11 minh họa một màn hình quản trị các cấu hình chung của module Verification được hiện thực trên nền tảng Boonex Dolphin
KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ
Kết quả thực nghiệm
Dữ liệu được sử dụng thực nghiệm trong luận văn này được thu thập từ tập bài tập đã được sử dụng cho hệ thống Prove phiên bản 7.0 (ngày thu thập dữ liệu: 15/04/2011) cùng một số bài tập lập trình cơ bản được thu thập từ nhiều nguồn khác nhau trên Internet Có tổng số 14 bài tập đã được sử dụng để tiến hành thực nghiệm Chi tiết các bài tập này có thể tìm thấy trong phần phụ lục của luận văn này
Tập dữ liệu trên sau khi thu thập về đã được cải tiến để phù hợp với mục đích minh họa cho chương trình chưa hoàn chỉnh Theo đó, dữ liệu thô đã được thêm các thông tin sau: Đặc tả ACSL cho các hàm được phép sử dụng trong mã nguồn của sinh viên: mục đích của phần này là cho phép sinh viên có thể sử dụng các lời gọi hàm / thủ tục để tạo ra chương trình chưa hoàn chỉnh và để minh họa hệ thống có thể xử lý được các chương trình dạng này o Lấy thí dụ với bài toán “Cho biết ba số nhập vào có phải là ba cạnh của một tam giác không”, luận văn đã thêm phần đặc tả cho hàm isAllPositive cho phép kiểm tra cả ba số có phải là số nguyên dương hay không như Bảng 5.1
Bảng 5.1: Một đặc tả ACSL mẫu trong thực nghiệm
*/ int isAllPositive(int x, int y, intz);
Mô tả hàm ở ngôn ngữ C, với phần nội dung cho phép người dùng nhập liệu: dữ liệu nhập vào của người dùng và phần mô tả này sẽ được kết hợp lại để tạo thành một chương trình (chưa hoàn chỉnh) ở ngôn ngữ C o Tiếp tục với thí dụ bài toán kiểm tra tam giác như ở trên, lời mô tả mẫu sẽ có dạng như Bảng 5.2 Phần {user_code} sẽ được thay thế bằng phần dữ liệu nhập vào của sinh viên
Lời giải mẫu: một lời giải mẫu của từng bài tập được nhập vào hệ thống để làm dữ liệu đối chiếu với kết quả trả về từ chương trình được gửi bởi người dùng Lời giải này là một hàm viết bằng ngôn ngữ C đầy đủ, nghĩa là không chứa lời gọi hàm / thủ tục chưa hoàn chỉnh o Tiếp tục với thí dụ bài toán kiểm tra tam giác như ở trên, lời giải mẫu sẽ có dạng như Bảng 5.3 Phần lời giải này sẽ được dùng để kiểm tra kết quả thực thi động với lời giải của sinh viên
Tập dữ liệu trên đã được nhập vào chương trình minh họa (như đã mô tả ở chương 6) và thực hiện kiểm tra với nhiều kiểu viết chương trình khác nhau Các kiểu viết chương trình này bao gồm:
Bảng 5.3: Một lời giải mẫu trong thực nghiệm int isTriangle(int x, int y, int z)
Bảng 5.2: Một mô tả hàm mẫu trong thực nghiệm int isTriangle(int x, int y, int z)
(i) Kiểu viết đầy đủ, tức không sử dụng lời gọi hàm thư viện hoặc lời gọi hàm đặc tả trong ngôn ngữ ACSL o Thí dụ với chương trình tính giá trị tuyệ đối, chương trình dạng này được minh họa ở Bảng 5.4
(ii) Kiểu viết có sử dụng lời gọi hàm thư viện toán học của ngôn ngữ C o Thí dụ với đề bài yêu cầu viết hàm tính có số mũ x 2 + x, chương trình của sinh viên có thể sử dụng hàm pow của ngôn ngữ C như minh họa ở Bảng 5.5
(iii) Kiểu viết có sử dụng lời gọi hàm được đặc tả bằng ngôn ngữ ACSL o Lấy thí dụ với hàm tính biểu thức có số mũ ở trên, giả sử có hàm calculateSquare được đặc tả bằng ngôn ngữ ACSL để tính bình phương của một số, chương trình dạng này được minh họa như Bảng 5.6
Bảng 5.5: Một lời giải có sử dụng hàm thư viện int calculateFormulae(int x)
Bảng 5.4: Một lời giải không sử dụng lời gọi hàm int calculateAbs(int x)
(iv) Kiểu viết hỗn hợp: có sử dụng kết hợp lời gọi hàm thư viện của ngôn ngữ C và lời gọi hàm được đặc tả bằng ngôn ngữ ACSL o Tiếp tục với thí dụ yêu cầu tính biểu thức có kết quả trả về x 3 + x 2 + x, kiểu viết hỗn hợp được minh họa ở
Chi tiết về số lượng bài tập và các cách viết được thử nghiệm trên mỗi bài tập như Bảng 5.8 Tổng cộng có 14 chương trình viết theo kiểu (i), 4 chương trình được viết theo kiểu (ii), 14 chương trình được viết theo kiểu (iii), và 3 chương trình được viết theo kiểu (iv)
Bảng 5.7: Một lời giải có sử dụng kiểu viết hỗn hợp int calculateFormulae(int x)
Bảng 5.6: Một lời giải có sử dụng hàm đặc tả bằng ACSL int calculateFormulae(int x)
Thực nghiệm được tiến hành trên tập bài tập trong phần phụ lục Tiêu chí đánh giá kết quả dựa trên số test-case được tạo ra, và dựa trên kết quả kiểm tra đúng/sai với từng test-case Việc thực nghiệm được tiến hành so sánh làm hai giai đoạn là tạo test-case và thực thi động, với các cách tiếp cận là theo phương pháp DART, theo cách làm của hệ thống Prove, và theo cách làm bằng tay Trong đó:
Khi so sánh quá trình tạo test-case cho đoạn chương trình, luận văn tiến hành so sánh với kết quả tạo test-case của DART và phương pháp làm unit test bằng tay mà không so sánh với Prove Lý do là do việc sinh test- case trong hệ thống Prove được thực hiện không hoàn toàn tự động, do người tạo bài tập phải nhập đoạn mã Promela mô tả các điều kiện và số lượng test-case được tạo ra cho từng bài tập, do đó số lượng và chất lượng test-case trong hệ thống Prove hoàn toàn phụ thuộc vào người định nghĩa đoạn mã này Kết quả so sánh được mô tả như trong Bảng 5.9, Bảng 5.10, Bảng 5.11, và Bảng 5.12
Khi so sánh khả năng thực thi động trên chương trình với test-case đã được tạo ra, luận văn so sánh kết quả với hệ thống Prove bởi cách tiếp cận trong việc so sánh với một lời giải mẫu là như nhau Kết quả là tất cả các test-case được tạo ra đều được thực thi thành công trên cả hai hệ thống khi xử lý theo kiểu viết (i) (như thống kê ở Bảng 5.13), tuy nhiên đối với các kiểu viết (ii), (iii), và (iv) thì thành phần model checking hệ thống Prove thất bại trong quá trình thực thi động do không hiểu các lời gọi hàm này
Bảng 5.8: Thống kê các kiểu viết áp dụng cho các bài tập
Hình 5.1: Biểu đồ minh họa số lượng test-case sinh ra với kiểu viết (i)
Bảng 5.10: Số lượng test-case sinh ra với kiểu viết (ii)
Bảng 5.9: Số lượng test-case sinh ra với kiểu viết (i)
Hình 5.2: Biểu đồ minh họa số lượng test-case sinh ra với kiểu viết (ii)
Hình 5.3: Biểu đồ minh họa số lượng test-case sinh ra với kiểu viết (iii)
Bảng 5.11: Số lượng test-case sinh ra với kiểu viết (iii)
Hình 5.4: Biểu đồ minh họa số lượng test-case sinh ra với kiểu viết (iv)
Từ kết quả thực nghiệm trên, ta có một số nhận xét như sau:
Trong một số trường hợp test-case, đặc biệt là khi chương trình chứa các lời gọi hàm được đặc tả bởi ngôn ngữ ACSL Lấy thí dụ với chương trình ở Bảng 5.6, do DART không thể sinh ra test-case để đi hết các nhánh của điều kiện isPositive(x), do đó chỉ có thể sinh ra một test-case ngẫu nhiên và sẽ chỉ đi được một luồng thực thi của chương trình cần xét
Bảng 5.13: Số lượng test-case thực thi thành công với kiểu viết (i)
Bảng 5.12: Số lượng test-case sinh ra với kiểu viết (iv)
Trong một số trường hợp, việc sinh test-case bằng phương pháp thủ công (manual) cũng không bảo đảm phát hiện ra các lỗi có thể có của chương trình Lấy thí dụ với đoạn chương trình tìm giá trị tuyệt đối ở Bảng 5.4, khi tạo test-case bằng phương pháp thủ công, ta sẽ có hai luồng thực thi ứng với x>=0 và x
