Change search
ReferencesLink to record
Permanent link

Direct link
Automatic learning of state machines for fault detection systems in discrete event based distributed systems
KTH, School of Electrical Engineering (EES), Communication Networks.
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The electronic components in modern automobiles build up a distributed system with so called electronic control units connected via bus systems. As more safety- and security-relevant functions are implemented in such systems, the more important fault detection becomes. A promising approach to fault detection is to build a system model from state machines and compare its predictions with properties observed in a real system. In the automobile, potential are communication characteristics between the distributed control units. Especially, the sequence of transmitted messages can be used as the basis for supervising the communication. This thesis investigates if data gathered during system tests can be used to create state-machine system models. Such an automatically created model reflects the observed normal system behavior and can potentially be used for fault detection purposes. The task can be seen as learning a state machine from a single long message sequence. Today’s automata learning algorithms are not designed for such singlemessage- sequence input data. Especially, learning without interaction between the original system and the learning algorithm is in general a NPcomplete task. Additionally, if only positive data from the normal behaving system is available, the task is further complicated. The well-known Angluin’s L∗ state-machine learning algorithm works in general independent from the type of input data. In order for this algorithm to be applicable, certain queries have to be answered. This work proposes a statistical approach to answer such queries. The implemented adapted Angluin algorithm showed the potential of automatic model building in fault detection systems and, in particular, the possibility of learning state machines from a single positive data stream.

Place, publisher, year, edition, pages
2011. , 87 p.
EES Examensarbete / Master Thesis, XR-EE-LCN 2011:002
National Category
Engineering and Technology
URN: urn:nbn:se:kth:diva-53513OAI: diva2:470204
Educational program
Master of Science - Electrophysics
Available from: 2012-01-19 Created: 2011-12-28 Last updated: 2012-03-16Bibliographically approved

Open Access in DiVA

fulltext(892 kB)560 downloads
File information
File name FULLTEXT01.pdfFile size 892 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Communication Networks
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 560 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 146 hits
ReferencesLink to record
Permanent link

Direct link