Research    Publications    Funding    Professor    People    Course

Sun Geol Baek, Dong Hyun Kang, Sungkil Lee, Young Ik Eom

Journal of Systems and Software, 140, 17–31, 2018.
Abnormal messages propagated from faulty operations in a vehicular system may severely harm the system, but they cannot be easily detected when their information is not known in advance. To support an efficient detection of faulty message patterns propagated in the in-vehicle network, this paper presents a novel graph pattern matching framework built upon a message log-driven graph modeling. Our framework models the unknown condition as a query graph and the reference database of normal operations as data graphs. The analysis of the faulty message propagation requires to consider the sequence of events in the distance measure, and thus, the conventional graph distance measures cannot be directly used for our purpose. We hence propose a novel distance metric based on the maximum common subgraph (MCS) between two graphs and the sequence numbers of messages, which works robustly even for the abnormal faulty patterns and can avoid false negatives in large databases. Since the problem of MCS computation is NP-hard, we also propose two efficient filtering techniques, one based on the lower bound of MCS distance for a polynomial-time approximation and the other based on edge pruning. Experiments performed on real and synthetic datasets to assess our framework show that ours significantly outperforms the previously existing methods in terms both of performance and accuracy of query responses.
@ARTICLE{baek18:graph, title={{Efficient Graph Pattern Matching Framework for Network-Based In-Vehicle Fault Detection}}, author={Sun Geol Baek and Dong Hyun Kang and Sungkil Lee and Young Ik Eom}, journal={{Journal of Systems and Software}}, volume={140}, pages={17--31}, year={2018} }

27336, College of Software, Sungkyunkwan University, Tel. +82 31-299-4917, Seobu-ro 2066, Jangan-gu, Suwon, 16419, South Korea
Campus map (how to reach CGLab)