{'fraction_non_alphanumeric': 0.03484844106683619, 'fraction_numerical': 0.008148640448464183, 'mean_word_length': 4.465571699305117, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Passive Online Technique for Learning Hybrid Automata from Input/Output Traces

Specification synthesis is the process of deriving a model from the input-output traces of a system. It is used extensively in test design, reverse engineering, and system identification. One type of the resulting artifact of this process for cyber-physical systems is hybrid automata. They are intuitive, precise, tool independent, and at a high level of abstraction, and can model systems with both discrete and continuous variables. In this paper, we propose a new technique for synthesizing hybrid automaton from the input-output traces of a non-linear cyber-physical system. Similarity detection in non-linear behaviors is the main challenge for extracting such models. We address this problem by utilizing the Dynamic Time Warping technique. Our approach is passive, meaning that it does not need interaction with the system during automata synthesis from the logged traces; and online, which means that each input/output trace is used only once in the procedure. In other words, each new trace can be used to improve the already synthesized automaton. We evaluated our algorithm in two industrial and simulated case studies. The accuracy of the derived automata show promising results.


I. INTRODUCTION
Learning the behavior of systems has been growing significantly over the last few years. The behavior of a system could be represented by different artifacts, such as automata [1], [2] or formal languages [3]- [5]. Automata-based models are precise and intuitive artifacts. These tool-neutral models provide an abstract comprehension of the system's behavior. Traditionally, automata-based models are constructed by software engineers as a system specification artifact. However, in some cases, the engineers have a system without a model, and need to derive an automaton representing its behavior. With the advances emerging in statistical analysis and process mining areas, there are approaches proposed in this field that automatically mine these artifacts by observing and analyzing the input-output traces of the System Under Learning (SUL).
Traditional automata-based models, such as DFAs or NFAs are versatile artifacts for modeling systems with discrete state space. They have been extensively used for modeling in areas, such as web services [6] or network protocols [7], [8]. However, today's software systems mostly consist of both continuous and discrete state space. Typically, these systems evolve continuously during the time, until an event happens, which takes them to another state, where the behavior of their continuous part changes differently. The behavior of this type of systems could be modeled by hybrid automata.
Learning these models has several advantages such as understanding the behavior of complex systems [9], [10], automatically generation of software specifications and source codes [7], [11], model-based testing of systems without models [12], [13], and verification and validation [8]. Moreover, since these models predict the system's outputs in an explainable and transparent manner, learning them could be considered as an explainable machine learning method. For example, the authors in [9] extract DFA from recurrent neural networks (RNNs) and provide an interpretable model of RNNs. In [14], the authors exploit Fisher Information analysis and Cramer Rao bound theorem to construct a linear hybrid automaton and model the behavior of an Artificial Pancreas. We can categorize approaches for auotmata learning in two different ways [15]: 1) Active vs passive: Active learning algorithms directly interact with SUL, and hence, they could request any traces of inputs, along with their outputs. In passive learning, on the other hand, algorithms can only employ available traces of a system to synthesize an automaton. 2) Online vs offline: Online methods are allowed to access each trace only once. On the other hand, in offline methods, we are able to observe and process the whole data several times.
of passive learning strategies. Active learning methods have also several challenges. Interaction with SUL may be timeconsuming or even impossible in particular applications. This is due to the fact that traces need to be independent, meaning that the system requires to be reset for each new input/output trace [18]. These are the reasons we have chosen to propose a passive approach to be more practical. Active learning algorithms intrinsically have an online manner, but passive approaches could be online or offline. Online methods are more preferable due to their ability to work in real-time or semi-real-time situations. Moreover, they are generally have less time and memory complexity. They can also be used in incremental synthesis, where each new trace can refine the already synthesized automaton. To the best of our knowledge, our technique is the first passive online approach for synthesizing hybrid automata from input/output traces.
In [1], a passive offline approach for mining hybrid automata is proposed. The discrete state space is constructed by clustering input-output traces, and the continuous part is modeled by applying statistical methods. In [2], a passive online algorithm to mine linear hybrid automata is presented. The idea is to construct a logical formula corresponding to the synthesis of linear hybrid automata problem, and try to solve that using SMT solver. Our research is different in that our goal is to learn automata for non-linear systems, where the continuous behavior of the system is approximated by an n-degree polynomial equation in each state. Our idea is to use Dynamic Time Warping (DTW) to find similarity between signal segments, and using this measure, we cluster the segments of input/output traces. These clusters make the states of the hybrid automata. To find the continuous behavior of the system, we use polynomial regression method.
The rest of the paper is organized as follows. In Section II-B, we provide preliminaries of our research, including hybrid automata and basics of dynamic time warping analysis. In Section III, we formalize the problem of synthesizing hybrid automata. A motivating example is presented in Section IV. Our Passive Online Strategy for Extracting Hybrid Automata based on DTW technique (POSEHAD) is discussed in Section V. The results are presented in Section VI on two case studies of engine-timing hybrid system and the Electronic Control Unite (ECU) of Anti-lock Brake System (ABS). The related work are briefly discussed in Section VII. The concluding remarks and future work are presented in Section VIII.

II. PRELIMINARIES
In this section, we briefly present the preliminary concepts of the paper. The definitions related to the problem input, its output, and the underlying technique of our proposed method are presented in Sections II-A, II-B, and II-C, respectively.

A. Trace Modeling
As mentioned, our input is a set of input/output traces of the system. Here, we give a brief definition of these traces.
Definition 1: Trace of Signal: A trace of signal with the sampling period c is a finite sequence of pairs of timestamps and values (t 1 , v 1 ) · · · (t p , v p ), such that: [1, p] : v i is the value of the signal S at time t i As mentioned, our input is a set of n input signals {I 1 , · · · , I n }, and m output signals {O 1 , · · · , O m }. An input/output trace, represented by w consists of input and output signals.
Definition 2: Input/Output Trace: An input/output trace is represented by a sequence of tuples: where each tuple consists of a timestamp, and the values of input and output signals at that time.
Definition 3: Segmented Input/Output Trace: A segmented input/output trace ψ w k,j of a trace w (k, j ∈ [1, p], k < j) is a subsequence of w: The final output of our algorithm is a hybrid automaton. To give an intuition, consider the automaton of a thermostat system depicted in Fig. 1. Similar to every state-transition model, a hybrid automaton consists of a set of states and a set of transitions. As an example, the automaton in Fig. 1 has two states, on and off, and two transitions between them. In a hybrid automaton, there is also a set of continuous variables. For instance, in the example automaton, the temperature of the environment is a continuous variable denoted by x. A hybrid automaton specifies the valuation of the continuous variables at each state by a predicate. For example, in Fig. 1, the change rate of x at state off is denoted byẋ = −0.1x, whereẋ is the first derivation of the variable x with respect to time. Similarly, the change rate of the variable x at state on is specified aṡ primed variables, represents the values of variables after the discrete changes. • G = (V, E) is a finite directed multigraph, where the vertices V are called the control modes, and the edges E are called the control switches. In Fig. 1, there are two control modes V ∈ {on,off} and two switches E ∈ {on → off, off → on}. • f low is a labeling function V → pred that assigns to each control mode v ∈ V a flow condition f low(v).
Each flow condition f low(v) is a predicate whose free variables are from X∪Ẋ. In Fig. 1, the continuous change of x at mode on is represented by {ẋ = 5 − 0.1x} • jump is an edge labeling function E → pred that assigns to each control switch e ∈ E a predicate jump(e).
Each jump condition jump(e) is a predicate whose free variables are from X ∪ X . Each label can be a jump condition or a variable assignment. In Fig. 1, predicate x > 21 is a jump condition on the control switch on → off and x = 20 is an assignment to the variable x. Note that control modes that are the destination of control switches without a source control mode are the initial control modes, and the assignments of these control switches represent the initial values of the variables.

C. Dynamic Time Warping Analysis
Our synthesis algorithm is based on Dynamic Time Warping (DTW). It was first introduced in [20] to detect similarity between two nonlinear time series. The technique has been widely used in several areas, such as speech, handwriting and gesture recognition, signal processing, data mining, and time series clustering. DTW employs dynamic programming to calculate the optimal match between two given time series X = (x 1 , ..., x N ) and Y = (y 1 , ..., y M ) with the both time and storage complexity of O(N M ) [21]. As an example, consider two time series X and Y that are depicted in the right plot of Fig. 5. DTW tries to find the most similar corresponding data points between the two time series. The left plot in Fig. 5 demonstrates the alignment matrix of time series X and Y . This matrix indicates the corresponding data points in time series X and Y . The diagonality in the emerging path shows the similarity between the two time series.
Given two sequences X and Y , the algorithm constructs a distance matrix C for their alignment: , and finally it finds a path with minimum distance from p 1 = (1, 1) to p k = (N, M ). The optimal distance of time series X and Y is calculated by Eq. 2.
DTW analysis not only calculates the minimum distance between two time series, but it also determines the corresponding data points in the two time series. We denote the first elements of path P as P i = (i p1 , i p2 , ..., i p k ) and the second elements of path P as P j = (j p1 , j p2 , ..., j p k ). Then we could measure the diagonality of path P as follows:

III. PROBLEM STATEMENT
Based on the previous definitions, the problem of mining hybrid automaton is formally defined as follow: Given is a set of training input/output traces Φ r = {w r1 , w r2 , · · · , w rn } and a set of test input/output traces Φ t = {w t1 , w t2 , ..., w tm } of a black-box system. Our goal is to design a passive online algorithm that synthesizes a hybrid automaton H modeling the behavior of the system based on Φ r . The precision of the synthesized automaton is evaluated by the following cost function: , where H(w I ti ) denotes the resulting output signals, when the input signals of trace w ti (w I ti ) are given to the automaton H.

IV. MOTIVATING EXAMPLE
Consider an engine timing system, having three input signals: (1) input throttle, which is the desired speed of the system in Rounds Per Minute (RPM), (2) load torque in joules per radian, and (3) time as an independent input signal. It has one output signal, called speed engine in RPM. Our goal is to model the behavior of the speed engine based on the system's input signals using a hybrid automaton. One input/output trace of this system is illustrated in Fig. 2.

V. POSEHAD ALGORITHM
In this section, we present a Passive Online Strategy for Extracting Hybrid Automata based on DTW (POSEHAD). POSEHAD consists of the following steps: 1) Signal segmentation: Traces are processed one by one due to the online manner of this approach. The first step of processing each new input/output trace w is to segment it by a change point detection algorithm, as discussed in Section V-A. As a result, we have a set of segmented input/output traces corresponding to w. 2) Signal similarity detection: Having a set of segmented input/output traces corresponding to w, we need a similarity detection criterion to categorize the similar segments into a set of states. This step is discussed in Section V-B. 3) Extracting the discrete state space: So far, we have a set of segments of w and a similarity detection index. The next step is to mine the discrete parts of automaton by identifying its states and transitions. The algorithm takes each segment and calculates the similarity between this segment and the existing set of states. If there are states which similarity with the segment exceeds a predefined threshold, then (1) the state with maximum similarity will be chosen, (2) the segment will be appended to that state, and (3) the transitions will be updated. If no similar state is found, then (1) a new state will be created, (2) the segment will be added to that state, and (3) the set of transitions will be updated. The details of this step are presented in Section V-C 4) Mining Jump Conditions: We utilize the updated sets of states and transitions to mine the jump conditions of hybrid automaton. This step is discussed in Section V-D. 5) Discovering the flow conditions: The algorithm takes segments of each state and extracts the flow conditions, as discussed in Section V-E.

A. Signal segmentation
The first preprocessing step of our technique is signal segmentation, where we divide each input/output trace into multiple segments. There are different approaches for signal segmentation, each proposed for a specific type of signal. Note that we assume that the SUL has synchronous behavior, meaning that each change in inputs affects the outputs with a negligible delay. Our goal is to find a set of change points, where each point demonstrates a drastic change in at least one input or output trace. In this work, we utilize windowsliding change-point detection algorithm [22] to perform segmentation. This method considers an immediate past and an immediate future window with size W for each data point in a signal with N data points. It then computes the discrepancy of each data point based on these two windows and finally considers data points with maximum discrepancy as a change point in a signal. Eq. 5 takes an input/output trace w and returns a set of change-points belonging to w denoted by CP w .
Using CP w , the input/output trace is divided into a set of segmented traces. All the segmented input/output traces related to w (as defined in Definition 3) are denoted by Ψ w , as shown in Eq. 6.
For each change point, a neighborhood is defined as follows. This neighborhood is used to find the transition jumps, as discussed in Section V-D.
, the change-point neighborhood of cp is a vicinity of v data-points, represented by a finite sequence of tuples: , · · · , (t cp , I 1 cp , · · · , I n cp , O 1 cp−k · · · , O m cp ), · · · , (t cp+v , I 1 cp+k , · · · , I n cp+k , O 1 cp+k · · · , O m cp+k ) Fig. 2: Segmentation of an input/output trace w of the engine timing system based on window-sliding algorithm Fig. 2 illustrates Ψ w of one input/output trace (w) of the engine-timing case study. The topmost trace is the working time considered as an input signal. The second sampled trace shows the input throttle. The third trace is the input load torque, and the last trace is the output engine speed. Note that all the input and output traces of a sample will participate in segmentation, and each change point demonstrates a drastic change in at least one trace.

B. Signal similarity detection
After segmentation, we need a mechanism to find a similarity index between segmented input/output traces with nonlinear behavior, so that we can categorize them. There are three major challenges in this regard: 1) Unequal lengths of segments: Different criteria, such as euclidean distance and correlation coefficient [23] are suggested to find similarity between two time series. However, these measures can only evaluate the similarity between two equal time series, and hence, we cannot use them due to the unequal length of segments. 2) Online clustering of segments: In [1], statistical measures, such as the average slope or the mean of each segment are used to cluster segments. Our constraint in using this approach is that in an online manner, we do not have access to all signals at the time of clustering. At each point, we have a clustering for signals that we have seen so far, and each new trace will be added to the clustering, once it is received and processed. 3) Nonlinearity of signals: In [2], the similarity between segments is calculated based on the coefficients of linear segments. This is based on the assumption that all segments have a linear behavior, and segments with equal slopes (with a degree of freedom) will be placed in one state of the synthesized linear hybrid automaton. For non-linear behaviors (that we model with quadratic polynomials), we could not use equation's coefficients because of non-orthogonal basis appeared in quadratic or higher order polynomials. Our method in this paper for signal similarity detection is based on Dynamic Time Warping (DTW). We have selected this technique for the following reasons: 1) This method can find the similarity between two time series with unequal lengths. 2) The algorithm intrinsically finds the geometrical similarities between two time series that could not be done based on equation's coefficients. We use both the distance dist DT W and the diagonality rate diag DT W to define a similarity index between two segmented traces, ψ and ψ .
Both of these criteria are necessary for finding the similarity between two signals. To clarify, consider two time series with small ranges as depicted in Fig. 3. The distance measure alone can not distinguish their difference, since the distance can be small due to the small ranges. On the other hand, based on Fig. 4, if we only consider the diagonallity rate as a metric, we will not be able to discriminate between two equal time series with different ranges.  Fig. 6 depicts two dissimilar segmented traces. The non-diagonal shape of the path line in the left figure demonstrates that there is no one-to-one correlation between the two signals.

C. Extracting the discrete state space
Algorithm 1 exhibits the procedure of mining hybrid automaton. The algorithm runs for each new unprocessed input/output trace w. After performing segmentation on w, the segmented traces Ψ w are given to the algorithm. The  other inputs to the algorithm are distance threshold (θ dist ), diagonality threshold (θ diag ), and the states and transitions of the automaton that have been synthesized so far. The algorithm returns the updated set of states and transitions as output. For the first sample, we pass an empty set of states and transitions to the algorithm.
The set of states is a dictionary, where the keys are state names, and the value of each key state is a set of similar segments, called state segments that are assigned to that state. The set of transitions is a dictionary, where each key contains two states (determining the source and the target of the transition), and each value is a set of change-point neighborhoods (as defined in Definition 5) corresponding to that transition. This set is called transition segments and it demonstrates the behavior of input signals during traversal between two states.
In line 2 of Algorithm 1, at the beginning, the current state is assigned to null. In line 3, the algorithm iterates over each segment of the trace w. In line 4, we calculate the change-point neighborhood of the first element in the segment seg (seg[0]). Note that seg[0] is actually the change-point of the segment seg, and the function changepoint neighborhood returns the neighborhood of the given change-point. The change-point neighborhood will later be assigned to the transition segments of the corresponding transition. In lines 5-13, if the set of states is empty, a new state is created, and the current segment will be added to it. The set of transitions, and the transitions' confidence level will also be updated. For each transition, we assign a probability to each input signal called confidence level. It determines how much that signal is responsible for triggering the transition. The details will be discussed in Section V-D. In lines 15-17, a candidate state will be initialized by infinite distance and zero diagonality rate. In lines 18-24, if the set of states is not empty, the algorithm iterates over each state and calculates the distance and diagonality between the current segment and the state. If the distance of the current state is less than candidate dist and the diagonality rate of the current state is more than candidate diag, this state will be selected as the candidate state.
In lines 25-31, the algorithm checks if the candidate state passes the distance and diagonality thresholds. If so, the current segment will be added to the state segments of that state. Accordingly, the set of transitions will be updated, and the transition from the current state to the candidate state will be added to it. In lines 32-40, if the current segment does not match with any state, then it will be added to a new created state. The set of transitions and the transition's confidence level will also be updated.
As an example, for the engine timing hybrid system, we fed 10 input/output traces to our procedure. For each trace, we segmented it, and gave the segments, along with our specified thresholds to Algorithm. 1. At the end, the set of states and transitions are used to construct the discrete part of an automaton, as depicted in Fig. 7. As mentioned, for each state, there is a set of segments, called state segments. Consider state '7' in Fig. 7, for example. There are 8 state segments for this state, as depicted in Fig. 8. In this figure, each column corresponds to one segment belonging to state '7'. Note that each segment consists of all input and output traces. Similarly, for each transition tran, we have a set of equallength change point neighborhoods, called transition segments. They are utilized to detect which input signal is responsible for that transition. For example, there are 8 transition segments corresponding to the transition 0 → 1, which are illustrated in Fig. 9. Each column depicts the input/output trace of one transition segment.

D. Mining jump conditions
In line 44 of Algorithm 1, the jumps of synthesized transitions are mined using the transition segments and state segments. The cause of each jump may be due to the behavior of the input signals, which we call the input event jump, and/or due to the system staying in a state for a certain amount of time, called time condition. These categories do not form a mutually exclusive dichotomy. We discuss mining these two types of transition jumps in Sections V-D1 and V-D2.
1) Input events: When a transition is created between two states, a confidence level for each input signal is assigned, which indicates how much that signal is responsible for triggering the transition. Initially, the confidence level of all input signals of a transition are set as one. For each new transition segment added to a transition set, we update the confidence level of each signal based on the euclidean distance between new change-point neighborhood and the current transition segments. The less similar an input trace of the new transition segment to all the previous corresponding traces in the transition segments, the less confidence level will be assigned to that input signal. Note that we are able to utilize euclidean distance due to the equal length of transition segments.
Consider transition 0 → 1 of the automaton in Fig. 7 as an example. The transition segments belonging to this transition are depicted in Fig. 9. Note that we only consider the input signals (not the output), since only input signals can trigger transitions. When the first sample is fed to the algorithm, the transition segments of this transition consists of only the first column of Fig. 9 and the confidence level of this transition is assigned to {1.0, 1.0, 1.0} for the input signals of time, input throttle, and input torque, respectively. After feeding all input/output traces, there are 8 change-point neighborhoods added to this transition segments set, and the final confidence level for this transition is updated to {0.168, 1.0, 0.985}. These values indicates that the input throttle (the second input signal) is the most effective one for transition 0 → 1. Intuitively, when we look at Fig. 9, it could be seen that in different samples, this transition happens in different time and torque values based on the first and third row respectively, but when this transition happens, the input throttle always has the same manner based on the second row.
During the update transitions set phase in Algorithm 1, these confidence levels will be gradually updated with new input/output traces. When we want to represent our automaton using the output of Algorithm 1, we just need to select an input signal with the maximum confidence level for each transition a → b to model the transition's jump condition. It is also worth mentioning that since we are modeling deterministic systems, if there are more than one transitions going out of a state with overlapping conditions, we distinguish them by adding more input signals to the conditions (making "and" conditions).
2) Time conditions: The intuitive meaning of a time condition is that the transition is triggered, when the system stays in a state for a specific amount of time. For mining these conditions, the elapsing time of the system being in the source state of the transition is calculated according to state segments. Then the time causality of a transition is found by computing the variance of state segments durations. For instance, consider transition 10 → 13 in Fig. 7. It could be inferred from the jump condition 'time:0.054' that if the system remains in state '10' for a period of '0.054'(based on time normalization between zero and one), the transition 10 → 13 will be triggered because of this time condition.

E. Mining the flow conditions
In line 47 of Algorithm 1, the flow conditions of the synthesized states are mined. As mentioned earlier, we approximate the continuous state of a nonlinear hybrid automaton by an n-degree polynomial. We employ the polynomial regression method to estimate the parameters of that equation, based on the state segments of each state. For extracting the flow conditions, the partial derivative of inputs is calculated from the polynomial equation.
Consider state '7' of the automaton in Fig 7 as an example. All the state segments corresponding to this state are presented in Fig. 8. The algorithm applies polynomial regression to find the equation of the output signal based on the input signals:

VI. EXPERIMENTAL RESULTS
We evaluate our proposed framework on two case studies. The first one is our example of engine timing system, which is available as a built-in hybrid model in the Simulink toolbox. Our second case study is the Electronic Control Unit (ECU) of an Anti-lock Brake System (ABS), which data is taken from the automobile industry. We have employed the sliding window change-point detection technique implemented in rupture python library [22] to perform signal segmentation.

A. Engine timing system
To generate the traces of our example of engine timing system, we utilized the built-in hybrid model in the Simulink toolbox. To evaluate our algorithm, we generated 10 training input/output traces, trying to cover the whole state space of system by different permutations of input signals. We fed input/output traces to Algorithm 1 one after another. The final synthesized hybrid automaton is depicted in Fig. 7.
To evaluate the synthesized automaton, we fed a set of test input/output traces to the synthesized hybrid automaton and compared the predicted outputs with the real outputs. The value of the cost function introduced in Eq. 4 using the set of test input/output traces was equal to "0.0266". Predicted and real outputs for a test trace are demonstrated in Fig. 10, which shows a high precision of the synthesized automaton.

B. ECU of Anti-Lock Brake System
We selected the ECU of ABS as our second case study to learn its behavior and evaluate the POSEHAD algorithm. ABS aims to prevent the car from slipping in adverse weather conditions when the driver pushes the braking pedal. ECU receives each wheel's velocity and the brake signal at each moment and then controls the pressure applied to each hydraulic valves in the Hydraulic Control Unit (HCU) of ABS.
As presented in Fig. 11, the ECU consists of brake (br), front left wheel speed (fl s), front right wheel speed (fr speed), rear left wheel speed (rl s), rear right wheel speed (rl s), and time as input signals. For each wheel, it has a normally open valve and a normally close valve, as output  Each trace in this case study consists of 100,000 data points taking a value of zero or one to construct a square wave with variable frequency. Due to the microscopic granularity of these traces, we applied a preprocessing phase to convert each trace from time-value to time-frequency as presented in Fig. 12. Fig. 12: Converting a trace of (time,value) to a trace of (time,frequency) For each output signal, a hybrid automaton is learned using the POSEHAD algorithm. Fig. 13 presents an example of input/output traces in the training set of fl nc.  Fig. 14. Based on a set of test input/output traces and Eq. 4, the cost of the predicted outputs was equal to "0.247". Finally, we performed a reverse transformation from pairs of (time, frequency) to the pairs of (time, value) to have output traces in the domain of input signals. The final synthesized hybrid automaton that has modeled the behavior of the front left normally open valve is illustrated in Fig. 15. The label of each transition denotes the jump condition, along with the number of training traces taking that transition. For example, label ['brake:0.0->1.0'](6) assigned to transition 2 → 3 demonstrates that there are 6 input/output traces in the training sample that move from state 2 to state 3. The condition of this transition is changing the brake input signal from zero to one. Specification mining has been extensively studied in several papers [24]- [26]. In [24], the authors proposed a deep specification miner for extracting Finite State Automata (FSA) models. They used each execution trace to construct a prefix tree acceptor (PTA), and merge PTAs of different traces to synthesize a number of FSAs. Our work is different in that we deal with mining the specifications of embedded control systems with both continuous and discrete variables.
Another line of work related to this research is system identification [27]- [30]. These works attempt to model a system with a set of differential equations and estimate their parameters to identify hybrid system's behavior. They tackle the problem from the control system perspective. The main challenge of these approaches is that the model complexity needs to be known [30].
Automata learning is a field of studies with a wellestablished and extensive research history [9], [10], [15], [18]. The closest articles to our work are those that model the behavior of hybrid systems using a hybrid automaton [1], [2], [14]. In [1], the authors proposed a passive offline framework for learning hybrid automata. Compared to their approach, our algorithm is online, meaning that it could refine the synthesized hybrid automata by new input/output traces. The other point is that their method for mining the discrete state space requires a large amount of training data. They also modeled the continuous state space of the system by linear equations. In contrast, our method could approximate the nonlinear behaviors with an n-degree polynomial equation. The authors of [2] proposed a passive online algorithm to mine linear hybrid automata. They assumed that each trace could be segmented into a set of piecewise linear functions (PLFs). PLFs with similar slopes are then clustered into states. The main difference between this paper and our work is that our algorithm is able to model systems with non-linear behaviors.

VIII. CONCLUSION AND FUTURE WORK
In this paper, we proposed an algorithm for learning a hybrid automaton from the input/output traces of a black-box system. We employed a similarity detection technique in an online manner to address the challenges related to clustering nonlinear behaviors of hybrid systems. The main feature of our proposed algorithm is its ability to perform in an online and passive way. Having online behavior allows the algorithm to work in real-time situations. With a passive technique, we don't face the limitations related to active interaction with the system under learning. Our experiments on a simulated hybrid system and a real-world safety-critical system show promising results.
As for the future work, we plan to identify systems with non-polynomial behaviors. Furthermore, in complex systems, jump conditions may be triggered by a complex predicate of different input signals. Our plan is to consider this type of systems for learning. The other limitation of this work is our assumption on synchronicity of the system under learning. Mining asynchronous behaviors is another line of future work.