Skip to main content
SUPERVISOR
الهام محمودزاده (استاد راهنما) علی ابن نصیر (استاد راهنما)
 
STUDENT
Hassan Mousavi
حسن موسوی

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1396

TITLE

Model Extraction and Verification of Contiki's scheduling algorithm
the reliability is of particular importance. On the other hand, due to the high interaction of the systems with hardware, how to manage interrupts, memory limitations and light weight of operations should be considered. One of the most used operating systems in this field is Contiki. In fact, Contiki is a lightweight, open source operating system in C. In addition, high portability and the ability to run on a variety of platforms and event-oriented features are also important features of Contiki. In this project, we have analyzed one of the most critical components of Contiki called the scheduling algorithm and then formally reviewed it. To this end, first we have analyzed the scheduling algorithm source code and also the interaction with other parts of the operating system in detail. Also, we have driven a state machine-based ion of the scheduler’s modes of operation along with the control flow ions of the scheduler’s most important functions. Meanwhile, in the current research, models of process, process list, event and event queue, which are the most important coordination structures of scheduling functions, are presented. We then have extracted a set of transformation rules to generate the formal specifications of the scheduler in Promela and accordingly, the Promela model is generated. After that, expected properties of the proper functionality of scheduler are analyzed and then converted into formal Linear Time Logic formulas. Finally, the formulas are applied to the Contiki scheduler algorithm using SPIN model checker and formally verified. As a result, in this project, three flaws were found in the Contiki’s scheduler and accordingly, the source code are fixed. Model Extraction، Formal Verification، Scheduler
امروزه اینترنت اشیاء و سیستم های رایافیزیکی مورد استقبال ویژه ای قرار گرفته است. با توجه به اینکه سیستم ها عملکردهای حساسی را انجام می دهند، قابلیت اطمینان آنها اهمیت ویژه ای دارد. از طرفی به دلیل تعامل فراوان سیستم های مورد استفاده در اینترنت اشیاء و رایافیزیکی با سخت افزار، چگونگی مدیریت وقفه ها، محدودیت حافظه و سبک وزن بودن عملیات بایستی مورد توجه قرار گیرد. یکی از سیستم عامل هایی که در این زمینه بسیار مورد استفاده قرار می گیرد، Contikiمیباشد. در واقع Contikiسیستم عاملی سبک وزن و متن باز به زبان Cاست. همچنین قابلیت حمل بالا، قابلیت اجرا شدن بر روی زیرساخت های متنوع و رویداد محور بودن از ویژگ ?های مهم Contikiاست. ما در این پایان نامه یکی از قسمت های مهم Contikiبنام الگوریتم زمانبند را مورد تحلیل و سپس وارسی رسمی قرار داده ایم. به این منظور پس از تحلیل مفصل کد الگوریتم زمانبند و نحوه تعامل آن با سایر قسمت های سیستم عامل، ما در این پایان نامه علاوه بر استخراج ماشین حالت انتزاعی الگوریتم زمانبند، روندنمای انتزاعی توابع مهم فراخوانی شده در هر وضعیت زمانبند را نیز استخراج کرده ایم. در عین حال، در پژوهش جاری مدل های انتزاعی از فرآیند، لیست فرآیند، رویداد و صف رویداد که از مهمترین ساختارهای هماهنگی توابع زمانبند هستند، نیز ارائه شده است. سپس به منظور وارسی رسمی زمانبند، قوانین تبدیل کد Cبه Promelaاستخراج و بر طبق آن کد الگوریتم زمانبند به Promelaتبدیل شده است. پس از آن مشخصه های مورد انتظار برای عملکرد صحیح سیستم عامل مورد تحلیل و در نهایت به فرمول های رسمی منطق زمانی خطی تبدیل شده است. همچنین، فرمول های مشخص شده بر روی الگوریتم زمانبند Contikiبا استفاده از SPINاعمال و مورد وارسی رسمی قرار گرفته است. در نتیجه در این پایان نامه سه خطا در زمانبند سیستم عامل Contikiیافته شده و خطاهای به دست آمده اصلاح گردیده است. استخراج مدل، وارسی رسمی، زمانبند

ارتقاء امنیت وب با وف بومی