Deep Learning for System Trace Restoration

Ilia Sucholutsky, Apurva Narayan, Matthias Schonlau, Sebastian Fischmeister

TL;DR

This paper proposes using Long Short-Term Memory (LSTM) networks to accurately reconstruct missing data in discrete system traces, such as automotive CAN bus logs. By iteratively using its own predictions as inputs, the model can restore long sequences of lost events, significantly improving the performance of downstream analysis tools that typically require "perfect" data.

What Problem Does This Paper Address?

In safety-critical environments—like automotive systems, aviation, or medical devices—algorithms for anomaly detection and specification mining are often developed using "perfect" lab data. However, real-world data is rarely clean; it is plagued by noise, packet loss, and sensor failures.

When these algorithms encounter "imperfect" data in the field, they often fail. Traditional data imputation methods (like using global means or neighboring values) are too coarse for discrete, sequential data where the specific order of events is paramount. The authors tackle the challenge of restoring these discrete temporal traces so that high-level diagnostic tools can function reliably even when the underlying communication channel is lossy.

Methods

The authors implement a deep learning approach centered on Long Short-Term Memory (LSTM) networks, a type of Recurrent Neural Network (RNN) specifically designed to learn long-term dependencies in sequential data.

The Architecture

The model consists of a five-layer hidden structure:

  1. Two Densely-Connected Layers: These initial layers expand the input space.
  2. Two LSTM Layers: These are the "memory" of the system, unrolled for 40 steps to capture temporal patterns.
  3. One Densely-Connected Output Layer: This layer uses a sigmoid activation function to predict the next event.
The LSTM model architecture used for trace restoration.

The "Step-by-Step" Restoration

The core innovation is how the model is used for restoration. Instead of trying to predict a whole block of missing data at once (the "Direct Method"), the authors use a Step-by-Step approach. The model predicts the next single event, and then that prediction is fed back into the model as an input to predict the following event. This allows the network to generate arbitrarily long sequences of missing data.

Datasets

The study focuses on Automotive Controller Area Network (CAN) traces.

  • Source: Data was collected from a Lexus RX450h hybrid SUV.
  • Scope: To minimize variance during initial testing, they used 20 clean traces of a specific maneuver: the vehicle driving at 20 km/h and decelerating to a stop.
  • Preprocessing: Message IDs were one-hot encoded. The vocabulary consisted of 43 known message IDs plus one "other" category for rare events.

Key Insights and Ideas

  • Traces as Language: The authors treat system traces like natural language. If message IDs are "words" and sequences are "sentences," then restoring a trace is analogous to predicting the next word in a text—a task where LSTMs excel.
  • Robustness to Error: A surprising "aha moment" was the model's robustness. Even when the LSTM makes a mistake in its sequence generation, it often self-corrects or maintains the correct structural pattern, whereas traditional Markov Models "derail" completely after a single error.
  • Downstream Validation: Rather than just measuring prediction accuracy, the authors used Timed Regular Expression Mining (TREM) as a litmus test. They proved that restoring data isn't just a mathematical exercise; it has a tangible impact on the ability of engineers to extract system behaviors and rules from lossy logs.

Key Results

The LSTM-based approach significantly outperformed the standard Markov Model benchmark, especially as the length of the missing data increased.

  • Next-Event Accuracy: The model achieved nearly 90% accuracy in predicting the immediate next event.
  • Long-Sequence Stability: When predicting 20 steps into the future, the LSTM maintained an accuracy of 88.9%, while the Markov Model's performance plummeted to 37%.
  • Restoration Impact: In a scenario with 25% message loss, a specification mining tool (TREM) missed over 53% of the system's behavioral rules. After LSTM restoration, that loss was reduced to just 10.8%.
Visualization of true vs. predicted one-hot encoded events, showing the model's ability to capture complex temporal patterns.

Limitations and Future Work

While successful, the authors note several areas for improvement:

  • Generalization: The current model was trained on a single, specific maneuver. Future work needs to determine if a single model can handle the vast diversity of "normal" driving conditions.
  • Rare Events: The "other" node is a simple fix for unknown events, but it doesn't help reconstruct them. The authors suggest exploring different data embeddings to handle new events on the fly.
  • Bidirectional Context: The current model only looks at the past (one-directional). While this is great for real-time use, a bidirectional RNN—which looks at events both before and after a gap—could potentially offer even higher restoration accuracy for offline analysis.

Summary updated

Abstract

Most real-world datasets, and particularly those collected from physical systems, are full of noise, packet loss, and other imperfections. However, most specification mining, anomaly detection and other such algorithms assume, or even require, perfect data quality to function properly. Such algorithms may work in lab conditions when given clean, controlled data, but will fail in the field when given imperfect data. We propose a method for accurately reconstructing discrete temporal or sequential system traces affected by data loss, using Long Short-Term Memory Networks (LSTMs). The model works by learning to predict the next event in a sequence of events, and uses its own output as an input to continue predicting future events. As a result, this method can be used for data restoration even with streamed data. Such a method can reconstruct even long sequence of missing events, and can also help validate and improve data quality for noisy data. The output of the model will be a close reconstruction of the true data, and can be fed to algorithms that rely on clean data. We demonstrate our method by reconstructing automotive CAN traces consisting of long sequences of discrete events. We show that given even small parts of a CAN trace, our LSTM model can predict future events with an accuracy of almost 90%, and can successfully reconstruct large portions of the original trace, greatly outperforming a Markov Model benchmark. We separately feed the original, lossy, and reconstructed traces into a specification mining framework to perform downstream analysis of the effect of our method on state-of-the-art models that use these traces for understanding the behavior of complex systems.
BibTeX
@inproceedings{sucholutsky2019deep,
  author = {Ilia Sucholutsky and Apurva Narayan and Matthias Schonlau and Sebastian Fischmeister},
  title = {{Deep Learning for System Trace Restoration}},
  booktitle = {IJCNN},
  year = {2019},
  doi = {10.1109/ijcnn.2019.8852116},
}
Figure