TL;DR
This paper introduces SHAPEIT, a novel tool that automatically learns formal specifications for cyber-physical systems (CPS) from their real-valued time-series data. It achieves this by translating complex system behaviors into concise "linear shape expressions," which are essentially regular expressions describing patterns of parameterized lines, making system properties more understandable and reusable.
What Problem Does This Paper Address?
Engineering cyber-physical systems (CPS) is challenging because they often operate autonomously in complex and unpredictable environments. Formal specifications are crucial for understanding and verifying these systems, but creating them manually is time-consuming and error-prone, especially for systems with continuous, real-valued behaviors. Existing methods for specification mining often struggle with noisy, real-world data. This paper addresses the need for an automated approach to extract meaningful, declarative specifications from such data, bridging the gap between raw system behavior and formal understanding.
Methods
SHAPEIT employs a three-phase pipeline to mine specifications:
- Segmentation: The tool first approximates time-series data with piecewise-linear segments. It uses an algorithm that finds the minimal number of segments while ensuring that the mean squared error (MSE) of each segment's linear approximation stays below a user-defined threshold ($\epsilon_{max}$). This step effectively breaks down continuous signals into discrete linear pieces.
- Abstraction and Clustering: The linear segments (characterized by slope, offset, and duration) are then clustered into a finite set of "symbols." This is done using k-Means clustering, where each cluster represents a group of similar line segments. The number of clusters is determined by analyzing the Within-Cluster-Sum-of-Squares (WCSS) error. Each cluster is assigned a letter, forming a finite alphabet.
- Automata Learning and Translation: Sequences of these abstract symbols (derived from the segmented time-series) are used to train a deterministic finite automaton (DFA) using the RPNI (Regular Positive and Negative Inference) algorithm. Finally, the learned DFA is translated back into a linear shape expression (LSE), which is a regular expression composed of these abstract symbols and their associated constraints on line parameters.
Datasets
The paper evaluates SHAPEIT on two datasets:
- Wine Dataset: This dataset consists of time-series representing the food spectrograph of wines. The authors used a subset of this data, focusing on one class of wine with 57 traces, each containing 234 samples.
- Fish Dataset: This dataset comprises 350 time-series representing the contour shapes of seven different fish species. The authors used 26 shapes of the same species, each with 463 samples, to learn a specification.
Both datasets are publicly available from the UCR Time Series Classification Archive.
Key Insights and Ideas
- Bridging Continuous and Discrete: The core innovation is the ability to translate continuous, real-valued time-series data into discrete, symbolic representations (linear shape expressions) that are both formal and human-readable.
- Parameterization is Key: Linear shape expressions are not just about the shape of lines but also include symbolic constraints on their parameters (slope, offset, duration), allowing for more nuanced specifications.
- Hierarchical Abstraction: The multi-stage process (segmentation -> clustering -> automata learning) effectively abstracts away noise and variations in the raw data to reveal underlying behavioral patterns.
- Interpretability: The learned specifications offer insights into system behavior, making it easier to understand what constitutes "normal" or "expected" operation, as demonstrated by the interpretation of the fish contour.
Key Results
- SHAPEIT successfully learned linear shape expressions from time-series data for both the Wine and Fish datasets.
- The segmentation phase was found to be the most computationally expensive part of the pipeline, while clustering and automata learning were relatively negligible in terms of time.
- The sensitivity analysis showed that increasing the maximum error threshold ($\epsilon_{max}$) leads to shorter, less explanatory specifications, highlighting the trade-off between approximation accuracy and specification detail. For instance, reducing $\epsilon_{max}$ was necessary to detect smaller features in the data.
Limitations and Future Work
- Parameter Tuning: The tool requires two input thresholds: one for segmentation error ($\epsilon_{max}$) and one for WCSS error in clustering. Automating the tuning of these parameters is identified as future work.
- Generalization of Shape Expressions: The current work focuses on linear shape expressions. Future research aims to explore more general forms of shape expressions, potentially increasing explanatory power at the cost of higher computation.
- Online Processes: SHAPEIT currently handles offline data. Extending it to handle online, streaming processes is another direction for future work.
- Constraint Setting: The authors suggest adding the possibility to set constraints on line parameters directly as part of the specification mining process.
Summary updated