یک هیوریستیک جدید برای تشخیص بن بست در تحلیل ایمنی سیستم های نرم افزاری

تحلیل ایمنیِ سیستم های نرم افزاری، خصوصاً از نوع بحرانی-ایمنی، باید بطور دقیق انجام شود چون که وجود حتی یک خطای کوچک در چنین سیستم هایی ممکن است نتایج فاجعه باری داشته باشد ضمناً چنین تحلیلی باید قبل از پیاده سازی یعنی در مرحله طراحی و در سطح مدل انجام شود. وارسی مدل یک روش دقیق و مبتنی بر ریاضی است که ایمنی سیستم های نرم افزاری را با دریافت مدلی از آن و بررسی تمام حالت های قابل دسترس مدل انجام می دهد. با توجه به پیچیدگی بعضی سیستم ها و مدل های آن، وارسی مدل ممکن است با مشکل انفجار فضای حالت مواجه شود. بنابراین، وارسی مدل بجای تایید ایمنی چنین سیستم هایی، آنها را با یافتن خطاهایی از جمله بن بست رد میکند. اگر چه قبلا هیوریستیکی برای یافتن بن بست در فضای حالت مدل ارائه شده و آن را در چندین الگوریتم جستجوی مکاشفه ای ساده و تکاملی بکار برده اند ولی سرعت تشخیص آن پایین بوده است. در این مقاله، یک هیوریستیک جدید برای یافتن بن بست در فضای حالت مدل ارائه کرده و سرعت تشخیص آن را، با بکار بردن در الگوریتم های جستجوی مکاشفه ای ساده از جمله عمقی تکرار شونده a* و جستجوی پرتو و الگوریتم های تکاملی مختلف از جمله ژنتیک، بهینه سازی ازدحام ذرات و بهینه سازی بیزی با روش قبلی مقایسه می کنیم. نتایج مقایسه تایید می کنند که هیوریستیک جدید می تواند حالت بن بست را در زمان کمتری نسبت به هیوریستیک قبلی پیدا کند.

a new heuristic for deadlock detection in safety analysis of software systems

the safety analysis of software systems, especially safetycritical ones, should be performed exactly because even a minor failure in these systems may result in disaster consequences. also, such analysis must be done before implementation, i.e. the design step and in the model level. model checking is an exact and mathematicalbased way that gets a model of a system and analyzes it through exploring all reachable states of the model. due to the complexity of some systems and their models, this way may face the state space explosion problem, i.e. it cannot explore all available states. a solution to solve this problem in these systems is that model checking tries to refute them, instead of verifying them, by finding errors such as deadlock (if available).although, a heuristic has been previously proposed to find a deadlock in the model's state space and it has been applied in several simple heuristic search and evolutionary algorithms, its detection speed has been low. in this paper, we propose a novel heuristic to detect a deadlock in the model's state space, and test and compare its detection speed by applying it in several simple heuristic search algorithms such as iterative deepening a*, beam search, and evolutionary algorithms such as genetic, particle swarm optimization, and bayesian optimization. comparison results confirm that the new heuristic can detect a deadlock in less time than the previous heuristic.