بخشی از مقاله
چکیده :یکی از روشهای متداول ارزیابی قابلیت امنیت و اطمینان سیستمها طراحی و تحلیل درخت خطای آنهاست. آنالیز درخت خطا به دو صورت کمی و کیفی صورت میگیرد که در تمامی مراحل آنالیز خصوصا آنالیز کیفی از روابط ساده یا معادلات پیچیده ریاضیات استفاده میشود. در سیستمهای بزرگ و پیچیده آنالیز درخت بدلیل حجم بالای درخت خطا کار دشواری است. از این رو شخص تحلیلگر در تلاش برای کاهش حجم محاسبات میکوشد حجم درخت خطا را کم کند. در این مقاله روشهایی که به هدف کاهش حجم درخت خطا با استفاده از روابط ساده جبر بول در مقالات ارائه شده بیان نموده و با مثالهای متنوع تشریح مینماییم.
-1 مقدمه ای بر مفهوم درخت خطا
روش آنالیز درخت خطا1یکی از روشهای تجزیه و تحلیل قابلیت اطمینان و امنیت سیستمهاست. در حقیقت یک درخت خطا بطور فشرده ترکیبات مختلفی از رویدادهای2 ممکن در یک سیستم را که موجب بوجود آمدن یک رویداد نامطلوب منظور در سطح سیستم میشوند نمایش میدهد. این شیوه شامل دو مرحله میباشد: ساخت درخت خطا از روی مدل اولیه سیستم وسپس تجزیه و تحلیل آن بصورت کمی یا کیفی. رویداد نامطلوب در سطح سیستم3 نامیده میشود، که یک مخاطره یا یک حالت غیر مطلوب را در سیستم نشان میدهد و هدف از حل درخت خطا اینست که احتمال وقوع آن رویداد را پیش بینی کنیم.
درزمان ساخت درخت خطا رویداد سطح سیستم بعنوان ریشه یک درخت درنظر گرفته میشود و هر عاملی که کوچکترین تاثیری در بوجود آمدن این خطا داشته باشد، بعنوان گره درپایین ترین سطح درخت وارد شده و تاثیر آن بر رویداد سطح سیستم بصورت یک سری عبارات منطقی با استفاده از گیتهای منطقی در درخت ظاهر میشوند. سپس به هر رویداداحتمالی نسبت داده میشود. این احتمال یک عدد واقعی است که بیانگر احتمال وقوع آن رویداداست و با استفاده از درخت منطقی، احتمال وقوع آن بدست می آید.
همانطور که گفته شد جهت نمایش ارتباط منطقی رویدادها و روند تاثیر آنها روی سیستم از گیتهای منطقی متنوعی استفاده میشود. ورودی این گیتها میتواند هر یک از انواع رویدادها و حتی خروجی انواع گیتهای دیگر باشد. این گیتها را در دو گروه طبقه بندی می کنند. گروه اول که در ادامه آنها را معرفی میکنیم در درخت خطای استاندارد - استاتیک - بکار میروند. آنها عملکردی ثابت در کل زمان سیستم دارند و گیتهای استاتیک نامیده میشوند.گروه دوم گیتهای دینامیک هستند که موضوع بحث این مقاله نمیباشند.
گیتهای استاتیک NOTgate , ORgate, Exclusive-ORgate , ANDgate, ORgate عملکرد منطقی متعارف خود را دارند. البته معمولا از گیت NOT در درخت استفاده نمیشود زیرا ورود منطق معکوس ممکن است باعث گسستگی درخت شود. این کار آنالیز درخت را پیچیده میکند. اما از آنجایی که نیاز به کار کردن معکوس در یک درخت بسیار نادراست، این محدودیت برای آنالیز سیستمهای واقعی قابل چشم پوشی است. در شکل 1 نمونه ای از یک درخت خطای ساده از ترکیب گیتهای استاتیک مشاهده مینمایید.
جهت پیاده سازی عملکرد خطای سیستمهایی با رفتار متغیر در زمان در درخت خطا نمی توان از گیتهای استاتیک استفاده کرد. برای این سیستمها گیتهای خاصی طراحی شده که در مقاله[1] چگونگی عملکرد و موارد استفاده آنها شرح داده شده. این گیتها، گیتهای دینامیک نامیده میشوند و وجود حداقل یکی از این گیتها درساختار یک درخت، آن را تبدیل به درخت خطای دینامیک میکند. این درخت نیاز به روش آنالیز متفاوتی نیز دارد.
-2 روشهای آنالیز درخت خطا
آنالیز کمی و کیفی دو شیوه آنالیز درخت خطا میباشد. در روش آنالیز کیفی تمامی ترکیبات مختلف خطای اجزاء که موجب وقوع رویداد سطح سیستم میشوند تشخیص داده شده وCutSet نامیده میشود. آنالیز کمی داده هایی تولید میکند که معرف قابلیت اطمینان سیستم است. بطور مثال فرکانس وقوع رویداد سطح سیستم و یا میزان غیر قابل دسترس بودن سیستم درهر دو روش آنالیز درخت خطا، مستقیم و غیر مستقیم، فرض بر اینست که احتمال رخداد رویدادهای پایه درطول زمان عملکرد سیستم مقدار ثابتی است.
یافتن CutSet و MinimalCutSetها یا به اختصار CS و MCS معمولا هدف اصلی در آنالیز درخت خطا میباشد. که هم به منظور آنالیز کیفی و هم آنالیز کمی آن انجام میشود .[2-4]در یک درخت خطا هر مسیر ممکن رسیدن از رویدادهای پایه به رویدادسیستمی را یک CutSet - CS - گویند. لذا یک CS شامل یک ترکیب ممکن از تمام رویدادهای پایه در درخت است که رویداد سیستمی را میسازند. دو روش عمده که در آنالیز درخت خطا به منظور یافتن MCSها انجام میگیرد[5-6] استفاده از الگوریتم [7] MOCUSو دیگری روش رسم - Binary Decitsion [8] Diagram - BDD برای درخت میباشد.
استفاده از روش رسم BDD زمان محاسبات و حافظه مورد نیاز جهت پردازش را کاهش میدهد. در این روش ابتدا درخت خطا تبدیل به BDD شده و سپس MCS ها مستقیما از آن بدست می آید. BDD یک گراف بدون دور بدون جهت است و ترکیبی از نقاط ترمینالی و غیر ترمینالی است. نقاط ترمینالی مقادیر 0و1 میگیرند.هر نقطه معادل یک رویدادپایه در درخت خطا است و مقدار1 آن بیانگر وقوع آن رویداد - خراب شدن جزء مربوطه - و مقدار0 آن گویای عدم وقوع آن رویداد - سالم بودن جزء - است . برای یافتن یک CS کافیست از گره ریشه شروع کرده و به سمت پایین تمام مسیرهایی که برچسب 1 دارند و به یک نقطه ترمینالی 1 منتهی میشوند را ثبت کنیم. این مسیر ها همان CSها هستند.در شکل نمونه ای از دیاگرامBDD برای درخت خطای شکل1 ملاحظه مینمایید.
-3 شرح تکنیک پیشنهادی جهت ساده کردن درخت خطا
از آنجایی که رسم درخت خطای ساده تر موجب رسم دیاگرامBDD و یا پیاده سازی سریعتر الگوریتم MOCUS میگردد، محققان تلاش میکنند روشهایی برای طراحی ساده تر درخت خطا بیابند و یا درخت خطای بدست آمده را با حفظ منطق درخت، خلاصه تر و کوتاه تر کنند. خلاصه کردن درخت به مفهوم کاهش تعداد گیتهای تشکیل دهنده آن و نیز کاهش تعداد رویدادهای پایه با حذف رویدادهای تکراری میباشد. درادامه یک روش سه مرحله ای بر مبنای جبر بول - گردآوری شده از مقالات - برای ساده سازی درخت خطای سیستمها ارائه خواهیم نمود.[9-10]
دراین تکنیک [11] پیش از ساخت BDD، درخت خطا را در دو فاز ساده میکنیم . در فاز اول ساختار درخت را بدون از دست دادن منطق آن خلاصه میکنیم و در فاز دوم بدون دستکاری ساختار درخت آن را به ماژولهایی کاملا مستقل تقسیم میکنیم.به این فاز در انتهای بخش سه بیشتر میپردازیم. فاز اول میتواند تا %50 اندازه BDD حاصل از درخت را کاهش دهد . اینکار در سه مرحله صورت انجام میشود. برای روشن تر شدن این مراحل یک درخت خطای فرضی را که بصورت پیچیده ای در شکل3 نشان داده شده است مرحله به مرحله ساده میکنیم.
-1-3 مرحله اول: ادغام طبقات مشابه
کاهش تعداد گیتها با حذف گیتهای مشابه که بدنبال هم قرار دارند و ترکیب منطقی در یک گیت. اینکار را برمبنای رابطه جبری زیر انجام خواهیم داد - 1 - - x1+x2 - + - x3+x4 - = - x1+x2+x3+x4 - نمود عملی این رابطه در درخت خطا به اینصورت است که طبقات مختلف درخت میتوانند برای ساده تر شدن گیتهای مشابه را ادغام کنند، اما تنها در صورتیکه خروجی یک گیت ورودی گیت دیگری باشد.
دراینصورت بطور مثال به جای استفاده از سه گیت OR دو ورودی در سمت چپ رابطه بالا از یک گیت چهارورودی در سمت راست رابطه استفاده میکنیم. این مثال در درخت پیچیده شکل3 در بخش G1 قابل مشاهده است. پس از اعمال رابطه جبری فوق میتوانید بخش G1 در درخت خطای ساده شده شکل 4 مشاهده کنید.
-2-3 مرحله دوم:ادغام زیر درختها
ادغام کردن رویدادهایی که همیشه در کنار یکدیگر و با یک منطق واحد - گیت رابط آنها - با هم ارتباط دارند و تشکیل یک رویداد پیچیده از آنها. همانگونه که در ریاضیات برای ساده تر شدن یک رابطه از توابع تودر تواستفاده میشود در این مرحله میتوان نتایج بدست آمده از یک بخش درخت را به جای تکرار عملیات در بخشهای دیگر استفاده کرد.
