Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

Derivation of input sequences for distinguishing states of a finite state machine (FSM) specification is well studied in the context of FSM-based functional testing. We present three heuristics for the derivation of distinguishing sequences for nondeterministic FSM specifications. The first is based on a cost function that guides the derivation process, and the second is a genetic algorithm that evolves a population of individuals of possible solutions (or input sequences) using a fitness function and a crossover operator specifically tailored for the considered problem. The third heuristic is a mutation based algorithm that considers a candidate distinguishing sequence, and if the candidate is not a distinguishing sequence, then the algorithm tries to find a solution by appropriately mutating the candidate. Experiments are conducted to assess the performance of the proposed heuristics in addition to an existing algorithm, called exact algorithm, that derives distinguishing sequences of optimal length. Performance is assessed with respect to execution time, virtual memory consumption, and quality (length) of obtained sequences. Experiments are conducted using randomly generated machines with various numbers of states, inputs, outputs, and degrees of nondeterminism. Further, we assess the impact of varying the number of states, inputs, outputs, and degree of nondeterminism. Finally, in addition to the three proposed heuristics, we present a parallel multithreaded implementation of the exact algorithm using Open Multi-Processing. Experiments are conducted to assess the performance of the parallel implementation as compared to the sequential using both execution time speedup and efficiency.

روابط وملفات

التعريف والنوع

رقم الوثيقة

0dcce601-6ebb-493e-9046-75dd25494f24

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل ماجيستير

نوع الملف

pdf text

أسماء الملفات

45718_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":"Abdul Rahim Haddad","title_ar":"اعداد","title_en":"Preparation"},{"name_ar":"Khaled El Fakih ","title_ar":"اشراف","title_en":"Supervision"}]

اللغة

English

المصدر والدورية

اسم المصدر

Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines

المحتوى والصفحات

عدد الصفحات

0

إشراف وإعداد

الإشراف

Khaled El Fakih

الإعداد

Abdul Rahim Haddad

الاقتباسات الببليوغرافية