Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Automatic Transformation of Timed Petri Nets into Event-B for Formal Verification
Year (A.D.)
2017
Document Type
Thesis
First Advisor
วิวัฒน์ วัฒนาวุฒิ
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิศวกรรมซอฟต์แวร์
DOI
10.58837/CHULA.THE.2017.1387
Abstract
โดยทั่วไปการออกแบบซอฟต์แวร์เป็นขั้นตอนที่สำคัญในกระบวนการพัฒนาซอฟต์แวร์ ความถูกต้องของพฤติกรรมของระบบซอฟต์แวร์แบบเรียลไทม์มีความสัมพันธ์กับเวลาของการทำงานของระบบ หากพบข้อผิดพลาดหลังจากการพัฒนาซอฟต์แวร์จะทำให้มีผลกระทบที่ต้องสูญเสียอย่างมาก จึงเป็นสิ่งสำคัญที่ต้องทำการทวนสอบแบบจำลองของการออกแบบ เพื่อหาจุดผิดพลาดก่อนที่จะลงเมื่อพัฒนาซอฟต์แวร์ วิทยานิพนธ์นี้จึงนำเสนอทางเลือกในการทวนสอบเชิงรูปนัยโดยใช้ไทมด์เพทริเน็ตในการสร้างแบบจำลองเชิงรูปนัย ซึ่งในปฏิบัติแล้วไทมด์เพทริเน็ตเป็นวิธีการเชิงรูปนัยที่ใช้สัญลักษณ์กราฟิกสำหรับจำลองโครงสร้างของระบบ ซึ่งทำให้สามารถเข้าใจพฤติกรรมของระบบได้ง่าย แต่ไทมด์เพทริเน็ตยังขาดการแสดงส่วนของข้อมูลที่ใช้ภายในระบบและยังไม่ได้มีการปรับแต่งใดๆ หากระบบมีขนาดใหญ่และมีความซับซ้อนมาก อาจจะเกิดปัญหาการระบบของสถานะได้ State explosion อีกทางเลือกของวิธีการเชิงรูปนัยพบว่าอีเวนท์บี เป็นวิธีการเชิงรูปนัยที่นิยมสำหรับการทวนสอบการทำงานของระบบโดยสนใจข้อมูลภายในระบบอีกทั้งสนับสนุนการปรับแต่งของระบบซอฟต์แวร์แบบเรียลไทม์ โดยใช้วิธีการพิสูจน์ทฤษฎีทางคณิตศาสตร์ ซึ่งจะทำให้ไม่เกิดปัญหาการระเบิดของสถานะในระหว่างการทวนสอบ อย่างไรก็ตามการเขียนอีเวนท์บีไม่ง่ายนักเนื่องจากต้องมีทักษะทางด้านคณิตศาสตร์สำหรับการเขียนอีเวนท์บีเพื่อทวนสอบระบบ งานวิทยานิพนธ์นี้จึงเสนอเครื่องมือการแปลงไทมด์เพทริเน็ตให้เป็นอีเวนท์บีโดยอัตโนมัติสำหรับการทวนสอบเชิงรูปนัย โดยสนใจแบบจำลองไทมด์เพทริเน็ตที่มีค่าน้ำหนักโทเค็นที่มีค่าเท่ากับ 1 เท่านั้น และกฎการแปลงส่วนประกอบไทมด์เพทริเน็ตให้เป็นอีเวนท์บีทั้งหมด 7 ข้อ ข้อมูลนำเข้าเครื่องมือการแปลงจะเป็นแบบจำลองไทมด์เพทริเน็ตที่อยู่ในรูปแบบแฟ้มเอกสารเอกซ์เอ็มแอล และเครื่องมือจะดำเนินการแปลงโดยใช้กฎการแปลงที่ได้นิยามขึ้นมา เพื่อแปลงแบบจำลองไทมด์เพทริเน็ตให้เป็นอีเวนท์บีได้โดยอัตโนมัติ เมื่อได้ผลลัพธ์การแปลงอีเวนท์บีเรียบร้อยแล้ว จะดำเนินการทวนสอบด้วยเครื่องมือโรดิน เพื่อตรวจสอบความถูกต้องของวิธีการแปลงโดยใช้เครื่องมือการแปลงและทวนสอบการทำงานของระบบ
Other Abstract (Other language abstract of ETD)
Software design is typically an important step in the software development process. The correctness of the behavioral of real-time software system relies on both the result of its computation and the clock times. If errors are found after the software development process, it will definitely cause significant loss to the software developer. To prevent such loss and reduce development effort, it is practically crucial to verify the design model and find errors before the development software process starts. This study, we focus on formal methods between two well-known verification methods: (i) timed Petri net and (ii) Event-B. Timed Petri net method can be used to create verification model by leveraging a graphical framework to make ease for understanding in term of behavior for software. However, it still lacks the illustration of the internal data and refinement process. If the system is effectively large and complicated, the corresponding verification model can introduce a problem of the state explosion. Alternatively, formal verification by using Event-B specification method provides an efficient automatic theorem proving tool by using mathematical logic proving that will not cause the problem of state explosion. However, writing an Event-B specification, to verify software, from scratch is non-trivial and requires a strong background in mathematics. This thesis proposes an automatic tool for transformation from timed Petri net into Event-B for formal verification. This thesis focuses on timed Petri net model that has the weight of token as one. Seven mapping rules required to transform timed Petri net into Event-B. The input of our automatic tool supports timed Petri net model described in XML format. The tool applies mapping rules and automatically transforms timed Petri net into Event-B. We use Rodin tool to verify the correctness of the generated Event-B specification and to further verify the behavior of the corresponding system.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
ศักดิ์สุภาวัฒนกุล, ชลิกา, "การแปลงไทมด์เพทริเน็ตให้เป็นอีเวนท์บีโดยอัตโนมัติสำหรับการทวนสอบเชิงรูปนัย" (2017). Chulalongkorn University Theses and Dissertations (Chula ETD). 1877.
https://digital.car.chula.ac.th/chulaetd/1877