title: Hybrid Deep Neural Networks to Infer State Models of Black-Box Systems
authors: Mohammad Jafar Mashhadi Hadi Hemmati
text: 
  
  
  
  
  
  
  
    University of Calgary
  
    Calgary
    Canada
  
  
  mohammadjafar.mashha@ucalgary.ca
  
  
  
    University of Calgary
  
    Calgary
    Canada
  
  
  hadi.hemmati@ucalgary.ca
  
  
  
  
  
  
  
  
  
  
  
  
  <ccs2012>
     <concept>
         <concept_id>10010147.10010257.10010293.10010294</concept_id>
         <concept_desc>Computing methodologies Neural networks</concept_desc>
         <concept_significance>500</concept_significance>
         </concept>
     <concept>
         <concept_id>10011007.10011074.10011111.10003465</concept_id>
         <concept_desc>Software and its engineering Software reverse engineering</concept_desc>
         <concept_significance>500</concept_significance>
         </concept>
     <concept>
         <concept_id>10011007.10011074.10011075.10011076</concept_id>
         <concept_desc>Software and its engineering Requirements analysis</concept_desc>
         <concept_significance>500</concept_significance>
         </concept>
   </ccs2012>
  
  
  [500]Computing methodologies Neural networks
  [500]Software and its engineering Software reverse engineering
  [500]Software and its engineering Requirements analysis
  
  
  
  Inferring behavior model of a running software system is quite useful for several automated software engineering tasks, such as program comprehension, anomaly detection, and testing. Most existing dynamic model inference techniques are white-box, i.e., they require source code to be instrumented to get run-time traces. However, in many systems, instrumenting the entire source code is not possible (e.g., when using black-box third-party libraries) or might be very costly. 
  Unfortunately, most black-box techniques that detect states over time are either univariate, or make assumptions on the data distribution, or have limited power for learning over a long period of past behavior. To overcome the above issues, in this paper, we propose a hybrid deep neural network that accepts as input a set of time series, one per input/output signal of the system, and applies a set of convolutional and recurrent layers to learn the non-linear correlations between signals and the patterns, over time. We have applied our approach on a real UAV auto-pilot solution from our industry partner with half a million lines of C code. We ran 888 random recent system-level test cases and inferred states, over time. Our comparison with several traditional time series change point detection techniques showed that our approach improves their performance by up to 102%, in terms of finding state change points, measured by F1 score. We also showed that our state classification algorithm provides on average 90.45% F1 score, which improves traditional classification algorithms by up to 17%.
  
  
  
  
  Hybrid Deep Neural Networks to Infer State Models of Black-Box Systems
      Hadi Hemmati
      December 30, 2023
  ======================================================================
  
  
  
  
  
  § INTRODUCTION
  
  
  Automated specification mining or model inference <cit.> is the process of automatically reverse engineering a model of an existing software system. Behavioral models (e.g., state machines) are typically inferred from a running system by abstracting the execution traces. The inferred models are useful artifacts in many use cases where the actual behavior (abstracted as the inferred model) of the system is needed for analysis, such as debugging <cit.>, testing <cit.>, anomalous behavior detection <cit.>, and requirements engineering <cit.>. 
  
  Inferring a behavior model of a system in a black-box manner is particularly interesting. In many real-world applications, the large-scale system is built by integrating many off-the-shelf libraries that are only available as binaries (no source code access). Thus, from a system's point of view, knowing the exact behavior of the system including all the interactions between black-box units are needed for most run-time analysis. 
  
  Most current behavioral model inference techniques are dynamic analysis methods (usually are more accurate than static analysis for run-time behavior inference) that require source code instrumentation to collect execution traces <cit.>. These methods are usually helpful in unit-level analysis where the instrumentation is not expensive and access to the code is allowed for the unit under study. However, in the system-level, thorough instrumentation is more expensive (not limited to one unit) and might not be even possible for some units (black-box libraries). Therefore, for use cases such as system-level anomaly detection, testing, and debugging a black-box behavior model inference that works on readily available input/outputs of the system is crucial. 
  
  
  
  In this paper, we propose a dynamic analysis method to detect the internal state and the state changes in a black-box software system using deep learning. We collected the numerical values of the inputs and outputs of the system, in regular time intervals to create a multivariate time-series. A hybrid deep learning model (including convolution and recurrent layers) was then trained on these time-series to predict the state of the system at each point in time. The deep learning model automatically performs feature extraction making it way more effective and flexible compared to traditional methods. In addition, we do not make any assumption about statistical properties of the data which makes it applicable to a wide range of subjects.   
  
  We applied and evaluated this method on an auto-pilot software (AutoPilot) used in an Unmanned Aerial Vehicle (UAV) system developed by our industry partner
  
  Winnipeg based Micropilot Inc. Micropilot is the world-leader in professional UAV auto-pilot which develops both hardware and software for 1000+ clients (including NASA, Raytheon, and Northrop Grumman) in 85+ countries during the past 20+ years. 
  
  We evaluated the method from two perspectives: how well the model can detect the point in time when a state change happens? (RQ1: Change Point Detection (CPD)), and how accurately it can predict which state the system is in, during the execution? (RQ2: State Classification). In addition, in RQ3, we explored some simpler variations of our method (non-hybrid variations) to roughly see how each part contributes to the overall model performance.
  
  
  
  Comparing our approach with state-of-the-art alternatives, the results show that our approach performs better in both change point and state detection. We observed 88.00% to 102.20% improvement in the F1 score of our CPD, compared to traditional CPD techniques. In addition, we saw a 7.35% to 16.83% improvement in the F1 score of our state detection, compared to traditional classification algorithms on a sliding window, over the data.
  
  
  The contributions of this paper can be summarised as:
  
      
    * Introducing the first (to the best of our knowledge) deep learning architecture to infer behavior models from black-box software systems.
      
    * Empirically evaluating the model and achieving very high accuracy compared to baselines using a real-world and large-scale case study on a UAV auto-pilot system developed by our industry partner.
  
  
  Note that we have made all our source code, models, and execution scripts available online[https://github.com/sea-lab/hybrid-net], however, due to confidentiality, we can not make our dataset public. 
  
  The rest of this paper is organized as follows: In section <ref> we explain further how and in which contexts this research can be beneficial. Then in section <ref> we briefly explain some background material this work is based on. In section <ref>, we explain how our proposed model is designed. The way it was evaluated and the results are explained in section <ref>. Finally, related work reviewed in section <ref>, and some final remarks about the future work are made in section <ref>.
  
  
  § MOTIVATION
   
  
  Black-box components are ubiquitous in software development. Reusing high-quality black-box units generally offers a better overall system quality and a higher productivity <cit.>.  The black-box units can be as small as a reusable library, or as large as a framework (such as .NET before going open-source), or a complete piece of software such as a remotely hosted web service. There are also scenarios where the unit's source code is not black-box in general, but not accessible to a specific team that wishes to perform the dynamic analysis. 
  
  One particular interesting use case of system-level black-box analysis is inferring run-time state model of a control software systems, where inputs/outputs are signals to/from the system. These inputs/outputs are typically multivariate time series, which are already logged in such systems (no overhead for instrumentation). The goal is automatically detecting the high-level system state and its changes, over time.
  
  As discussed in section <ref>, we partnered with an auto-pilot manufacturer and performed this study on their auto-pilot software (called AutoPilot in this paper). The goal was to determine the state of AutoPilot from its input/output signals, over time. In this scenario, the inputs are the sensor readings going into AutoPilot and the outputs are command signals sent to controller motors of the aircraft, showing AutoPilot's reaction to each input at each state. A state in this example is the high-level stage of a flight and a state change happens when the current input values in the current state trigger a constraint in the implementation that changes the way the output signals are generated. 
  
  In this example, the training set will consist of input and output values recorded during one execution of the system, as a multivariate time series, along with state ids (as labels) per time stamp. One execution of the AutoPilot will be the whole flight process that may go through a “take-off” until a successful “landing”. Depending on the flight plan, AutoPilot goes through states such as “acceleration”, “take-off”, “climbing”, “turning”, “descending”, etc. 
  
  
  
  
  
  
  During a flight, the AutoPilot monitors changes in the input values and makes adjustments to its outputs in order to hold some invariants (predefined rules). 
  For example, if AutoPilot is in the “hold altitude” mode, it monitors the altimeter's readings and when it goes out of the acceptable range, proportionate adjustments to the throttle or the nose pitch will be made to get it back to the desired altitude. This is basically how a typical feedback loop controller, such as PID or its variations work <cit.>.
  When AutoPilot's state changes from “hold altitude” to “descend to X ft” state, the set of invariants that AutoPilot is trying to hold are changed. It means its reactions to variations in inputs will be different. In this example, a decreasing altimeter reading will not trigger an increase in the throttle anymore.
  
  Looking at the time series, a domain expert can identify what the state of AutoPilot is, at each point in time; the labeling process. Now the goal is to automate this task on a test set (in practice, future flights), assuming a training set is labeled by the experts (they only need to identify the state change time stamps, during a flight). 
  
  This problem can be tackled in two ways. The first solution is to identify the time stamp that the state change happens (i.e., Change Point Detection: RQ1); The more advanced solution is to predict the exact state per time stamp (i.e., State Classification: RQ2). The classic CPD techniques on time series <cit.> are mainly applicable on univariate data or put assumptions on the input/output distributions, thus not applicable in our case with multivariate inputs and no assumptions or knowledge about the states' distribution. The classic state classification techniques in time series are also weak in that 
  they fail to balance between considering long-term relations or acting locally. The ones that use a sliding window, for example, do not have a long-term memory. The ones that act on the whole data on the other hand are too coarse-grained and inaccurate for this task.
  
  Therefore, the motivation for this study is to provide a black-box technique that can be applicable on both CPD and state classification problems, and overcome the limitations of the existing techniques, in terms of capturing the non-linear correlation between multivariate inputs and outputs as well as learning patterns over a long period of time. Our proposal, which will be explained in detail in section <ref>, leverages the power of a deep neural network (DNN) with two types of layers that are particularly useful for this problem: a) convolutional layers which discover latent features from the data effectively through parameter sharing and b) recurrent layers that play a significant role in problems dealing with time series as they can learn long-term dependencies and seasonalities in the data. 
  
  Though our motivational example, as well as our case study, are from the UAV auto-pilot domain, our proposed method can be adapted to be applied to similar black-box control software systems in domains such as IoT, intelligent video surveillance, and self-driving cars.
  
  
  § BACKGROUND
   
  Unlike the numerous techniques in the literature for behavior model inference <cit.> which abstract a set of execution traces into states, our approach requires consuming a multivariate time-series and detect the state changes across time and predict the exact state labels. Thus, in this section, we briefly explain the two main sets of relevant existing techniques for “Change Point Detection” and “State Prediction” in time-series that can serve as background for our approach.  
  
  
  
  
  
   §.§ Change Point Detection
  
  A fundamental tool in time-series data analysis is Change Point Detection (CPD). It refers to the task of finding points of abrupt change in the underlying statistical model or its parameters that could be a result of a state transition <cit.>.
  
  
  
  
  There are plenty of CPD algorithms; many of which perform effectively on a subset of CPD problems with some assumptions. The assumptions can be of various types. For example, one may assume the time series has only one input variable (univariate) <cit.>, there is only one changing point <cit.>, or the number of change points is known beforehand <cit.>, or they might assume some statistical properties on the data <cit.>. These are limiting factors, since many of these assumptions do not necessarily hold in our case. CPD techniques are categorized into two main groups: a) online methods that process the data in real-time and b) offline methods that start processing the data after receiving all the values <cit.>. Since our model inference use case of CPD can afford waiting to collect all historical training data, we only considered offline techniques. 
  
  
  In general, CPD algorithms consist of two major components: a) the search method and b) the cost function <cit.>.
  Search methods are either exact or approximate. For instance, Pelt is the most efficient exact search method in the CPD literature, which uses pruning <cit.>. Approximate methods include window-based <cit.>, bottom-up <cit.>, binary segmentation <cit.>, and more. In the window-based segmentation a sliding window is rolled over the data and then sum of costs of left and right half-windows is subtracted from the cost of the whole window. When the difference gets significantly high it means that the discrepancy between left and right half of the window is high and therefore a change point probably lies right in the middle of the window. In the bottom-up method, the input signal is split into multiple smaller parts, then using a similarity measure adjacent segments are merged until no more merges are feasible. The binary segmentation method finds one change point and splits the input into two parts around that point and then recursively applies the same method on each part.
  
  The cost functions are also quite various, from simply subtracting each point from the mean to much more complex metrics, such as auto-regressive cost functions <cit.>, and kernel-based cost functions. Kernel-based costs can have a wide variety, since the kernel function can be almost arbitrary, however a handful of them such as linear and Gaussian kernels are among the most popular ones <cit.>.
  
  In the context of our paper, we need a CPD method with no assumption on data distribution, number of change points, etc. In addition, our CPD method should work on multivariate data, and be able to capture non-linear relations between signals. It also needs to be resilient to time lags between an input signal change and its effect on the output signal (and the systems state). There is no traditional CPD algorithms that covers all these requirements.
  Therefore, we propose a novel CPD techniques that is based on Hybrid DNNs and compare it with several existing CPD techniques as our baselines, which are explained in details in section <ref>.   
  
  
  
  
   §.§ Convolutional and Recurrent Neural Networks
  
  In both our problems (CPD and state classification), we can see that the changes in signals are more informative than their absolute values. Therefore, applying a derivation operation (or more generally a gradient) seems like necessary, at some point in the processing. Farid and Simoncelli listed some discrete derivation kernels in their study <cit.>, but to have a more generalized and more flexible notion of discrete derivatives, convolutions seems like a better choice to apply. 
  Nowadays, applying convolutional filters on signals is pretty much a standard process in signal processing studies that leverage deep learning <cit.>. Convolutional neural networks (CNNs) can learn to find features in a multidimensional input while being less sensitive to the exact location of the feature in the input <cit.>. In the forward pass of a convolutional layer, multiple filters are applied to the input. 
  It means that in a trained neural net, multiple features can be leaned in one single convolutional layer.
  
  Recurrent neural networks (RNN) have shown great performance in analysing sequential data such as machine translation, time-series prediction, and time-series classification <cit.>. RNNs can capture long-term temporal dependencies which is quite useful for solving our problem. <cit.> For example, they might learn that “climb” state in a UAV auto-pilot usually follows “take off”. Therefore, while it is outputting “take off” it anticipates what the next state will probably be and as soon as its input features start shifting, it detects the onset of a state change. It will help the model to better predict the system's behavior and be quicker to detect state changes in a way that could hardly be achieved with classic methods.
  Therefore, in this paper, we combine the CNNs and RNNs to create what is known as a hybrid deep neural network <cit.> to use for both CPD and state classification problems, in our context.  
  
  
  
  
  
  § HYBRID NEURAL NETWORK FOR STATE INFERENCE
   
  In this section, we describe our proposed deep learning approach for the black-box state inference task, in details. 
  
  
  
   §.§ The Model Architecture
  
  
  
  The goal of this study is to infer the states of a running software system, over time. Given that our assumption is we don't have access to the source code (or part of it), we only leverage the values of inputs and outputs of the system, over time. As can be seen in figure <ref>, we capture all the inputs and outputs of the system as a time series and then process it in a DNN. The architecture of our proposed model is a hybrid DNN which is inspired by models proposed in the field of Human Activity Recognition (HAR). This task is quite similar to the subject of our paper in the sense that they both take in a multivariate time series-data (from sensor readings) and output the state of the system that generated those readings (see section <ref> for more details on HAR papers). This DNN is made of three parts in sequence: 1) Convolutional, 2) Recurrent, and 3) Fully connected layers. This architecture addresses the aforementioned traditional methods' challenges; each part serves a different purpose in this process, as follows.
  
  
  Convolutions, being more generalized than simple sliding windows, can discover patterns and features in the signals, both in temporal and in spatial (how signals affect each other) dimensions <cit.>. 
  The convolutional layers' flexibility allows them to learn some typical preprocessing operations. For example a moving average or a discrete derivative can be learned as simple convolutional filters. They also help the model to be more resilient to varying time delays between noticing a deviation in input signals and the reaction that will appear in the output signals. Applying convolutional layers in sequence has been shown to result in each layer learning more complex features than the previous layers <cit.>.
  The number of layers, filters, and the kernel size are hyper-parameters that should be selected based on the size of data and the complexity of the system being modeled.
  Using a sequence of convolutions with a) increasing number of filters and the same kernel size, b) same number of filters and increasing kernel size, and c) decreasing filters with increasing kernel sizes are all different approaches that have been used in the literature by well-known architectures such as VGG and U-net <cit.>. We will discuss more details of our CNN layers in Section <ref>.
  
  Convolutions are quite powerful in discovering local features. To capture long-term features, recurrent layers which learn sequences of data are leveraged. For example, in our case, they can learn that “accelerate” and “take off” states only happen in the start of the states sequence, and each “take off” state is usually followed by a “climb” state. The type of recurrent cell to use (LSTM, GRU, etc.), how many cells to unravel in the layer, and the number of layers are also hyper-parameters that need to be tuned depending on the size and complexity of system under study.
  
  Finally, one or more dense (fully connected) layers in the end are a common way of reducing the dimensions to match expected output dimensions. 
  If there are only two states, the last layer can have a sigmoid activation function and be of shape L (the length of the input), otherwise, to match the one-hot encoding of labels, an output of shape L× N_s with softmax activation along the second axis (N_s) is required (N_s being the number of possible states).
  
  In terms of loss function to optimize in the training process, a good choice is a dice overlap loss function, which is used in image semantic segmentation tasks as well. An important property of this loss function is not getting negatively affected by class imbalances <cit.>.
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Data Encoding
  
  
  The input/output values of the black-box system create a multivariate time-series (T_k), which can be defined as a set of n univariate time series (V_i) of the same length l_k. Each V_i corresponds to the recorded values for one of the inputs or outputs of the system:
  
      T_k = {V_1_k, V_2_k, …, V_n_k}
  
  
      |V_1_k|=|V_2_k|=…=|V_n_k|=l_k
  
  
  Note that, as figure <ref> shows, we take both inputs and outputs as part of the time-series data to be fed as input into our deep learning models. This is to make sure we can model state-based behavior of the system, where the current state depends not only on the inputs, but also on the last state(s) (captured as previous outputs) of the system. As an example, from our case study, if the outputs are not taken into account 
  
  a mid-flight “descend” state and the “approach” state right before landing
  are indistinguishable, using the sensor readings (inputs) alone. 
  
  Having such a time-series, the only remaining pieces from a training set are the labels. Unlike the input/output values (the features in the data set) the labels are not usually given. Our method to infer the labels is a supervised approach. Thus, we need the domain expert to manually label each individual time stamp with a state name/ID. In practice, what they would do is to identify the approximate time that a state change happens and assign the new state to one of the previous states labels or define a new label for this new state.
  Thus we encode the states information over time as a set of tuples in the form of (t_s, s) where t_s denotes the timestamp where the system entered state s. We show the set of all possible states with S (s ∈ S) and define N_s as the cardinality of this set. 
  
      CP_k    = { (t_s_1, s_1), (t_s_2, s_2), …, (t_s_l, s_l) } ,  s_i ∈ S 
      
          N_s     = |S|
  
  So in summary, the dataset consists of N pairs of the I/O values as features and their state information as labels {(X=T_k, y=CP_k)|1≤ k≤ N}. 
  
  
  
  
  
    §.§.§ Data Preprocessing
  
  
  Before being fed into the model ℱ (as defined below), the inputs and labels need some preprocessing. 
  
      ℱ(δ(T), m) ℝ^L× n×ℝ^L→ S^L.
  
  To run more efficiently, TensorFlow expects all the inputs to have the same length. To do that, the shorter T_ks should be zero-padded to length L = max{l_k}. The padding function δ does that.
  Therefore, eventually, the input to the model will be T_ks that are rearranged to form a tensor of shape n × L along with a padding mask (denoted with m). 
  The mask tells the model where the tail starts so the model can ignore all the zeros from there on. 
  
  
      Ô   = ⟨ô_i ∈ S ⟩^L_i=1 = ℱ([ δ(V_1)^⊺ δ(V_2)^⊺ … δ(V_n)^⊺],m) 
      
          m    = δ(1⃗_l)   i.e.  ⟨m_j ⟩^l_j=1 = 1 ,  ⟨m_j ⟩^L_j=l+1 = 0
  
  Here l denotes the length of the input before padding. It is equal to l_k for the kth training data (T_k).
  
  
  As defined in (<ref>), CP_ks are tuples of (t, s) which indicate the system have gone into state s at time t. To train the model, CP_k needs to be expanded into a vector of length L denoted by O where each element o_t holds the state at time t. To define it formally, the elements can be derived from CP_k using the following formula:
  
      O = ⟨∀ t ∈ℕ_L : s_i  | 
                 (    t_s_i, s_i) ∈ CP_k  
          t_s_i = max{t_s_j |  (t_s_j, s_j) ∈ CP_k  t_s_j≤ t}⟩
  
  For example: Suppose L=10 and CP = {(0, a), (3, b), (5, c), (8, a)} 
  
  then O = ⟨ a a a b b c c c a a ⟩.
  If there are more than two possible states (N_s > 2), O needs to be one-hot encoded, at this stage.
  
  
  
  
  
   §.§ The Model Implementation
   
  The first few layers of the model are convolutional layers. We have used 5 convolutional layers with 64 filters each and a growing kernel size.
  The intuition behind this design is that starting with a small kernel guides the training in a way that the first layers learn simpler more local features that fits in their window (kernel size).
  Kernel sizes started with 3 since it is a common number in the literature for kernel sizes, then we used multiples of 5 from 5 to 20. 
  The rationale behind choosing 5 is because the sampling frequency is 5, so each layer with a kernel size of 5n processes a whole n seconds worth of simulation data, in each step.
  Stopping at kernel size of 20 was a compromise between generalizability and model size. Generally, a larger model has more learning capacity, but it is also more prone to over-fitting. The current models are the smallest we could make the models (to avoid over-fitting), without compromising the performance.
  
  Same compromise was made in the second section of the model (Recurrent layers), the sweet spot for hyper-parameters here was to use two GRU layers with 128 cells each. Their output was fed into a fully connected layer with 128 neurons with a leaky ReLU (α=0.3) activation function <cit.> and finally to a dense layer with N_s=25 units with softmax activation.
  We used Adam optimizer <cit.> that could converge in 60-80 epochs, i.e. validation accuracy plateaued. The full architecture can be seen in figure <ref>.
  
  
  
  
  
  § EMPIRICAL EVALUATION
   
  
  In this section, we explain our empirical evaluation of the proposed approach through a case study.
  
  
  
   §.§ The Study Objectives
  
  The goals of this study is to evaluate our proposed method in terms of change point detection and state inference, in comparison to traditional techniques in this domain.  Therefore, our research questions are as follows:
  
  
  
    §.§.§ RQ 1) How does our proposed technique perform in detecting the state changes?
  
  The goal of this RQ is to see how close the predicted state-change times are to the real state-change times.  In other words, in RQ1, we do not predict the exact state labels and are only interested in predicting the change.
  To answer this question, we compare the performance of our proposed approach with several traditional baselines (see <ref>), in terms of modified precision, recall, and F1 scores that are introduced in section <ref>.
  
  
  
  
    §.§.§ RQ 2) How well does our proposed technique predict the internal state of the system?
  
  In RQ1, we are only interested in detecting the time a state-change happens (binary classification), but here in RQ2, we extend that and are also interested in predicting the label of the new state that the system is going into (multi-class classification).  
  
  Therefore, to answer this RQ, we change the labels from a Boolean (changed/not changed) to the actual collected labels. 
  
  
  Note that for both RQs, in our empirical study, to evaluate our approach, we use the source code to collect the exact time a state-change happens and the actual state labels (ground truth). However, in practice, labeling the training set is supposed to be done by the domain expert in a black-box manner. This is not an infeasible task or extra overhead. Monitoring the logs and identifying the current system state is in fact part of the developers/testers regular practice during inspection and debugging. All we provide here is a tool that given a partial labeling (only on the training set), automatically predict the state labels and the state-change times, for future flights.  Also note that even though we use the source code to label the training set, we still look at the test set as a black-box and don't leak any information.
  
  
  
    §.§.§ RQ 3) How much does the proposed model owe its performance to being a hybrid model?
  
  The proposed model architecture, inspired by the related work, combines the power of convolutional and recurrent layers. It has been shown in those contexts that using this combination is beneficial over using a fully-convolutional architecture or a recurrent architecture without any help from convolutions. To answer this question we trained two other models one without the convolutional part and one without the GRU layers. We compare these two with the proposed model.
  
  
  
   §.§ Evaluation Metrics
  
  
  
    §.§.§ RQ1 (CPD) Performance Metrics
   
  
  Given that in RQ1 there is an inherent class imbalance (there are far more points where a change has not happened compared to points with a state-change positive label), we avoid using accuracy and report both precision and recall. 
  However, the original precision/recall metrics require some modifications due to the difficulty of predicting the exact time stamp that a state-change happened. To handle this, similar to related work <cit.>, we use a tolerance margin τ. If a detected state-change (∈ĈP̂_k) is within ±τ of a true change (∈CP_k) , we call the prediction a True Positive, otherwise it is a False Positive. Similar adjustment to definition is applied for True Negative and False Negative. 
  Formally speaking, we define predicted change points for k-th sample as:
  
      ĈP̂_k = {(t, ô_t)  | ô_t ≠ô_t-1}
  
  Please note that in (<ref>), ô_t refers to t-th element of output vector Ô, as previously defined in (<ref>). Based on that the confusion matrix elements are calculated as:
  
      TP =   |{ (t̂, ŝ_t) ∈ĈP̂_k  | ∃  (t, s_t) ∈ CP_k  s.t.  |t - t̂| < τ}| 
      
      FP =   |{ (t̂, ŝ_t) ∈ĈP̂_k  | ∄  (t, s_t) ∈ CP_k  s.t.  |t - t̂| < τ}| 
      
      FN =   |{ (t, s_t) ∈ CP_k  | ∄  (t̂, ŝ_t) ∈ĈP̂_k  s.t.  |t - t̂| < τ}|
  
  With these in mind, we measure precision, recall, and their harmonic mean F1 Score with three values for τ: 1, 3, and 5 seconds. The smaller the tolerance is the stricter the definitions become and the lower the numbers are. 
  
  
  
    §.§.§ RQ2 (State detection) metrics
  
  
  In RQ2, we have a multi-class classification problem and thus multiple precisions/recalls will be calculated, one per class (state label). We then report the mean value across all classes. 
  
      P_s =   {ŝ_t ∈Ô_k  | ŝ_t = s}
      
      T_s =   {s_t ∈ O_k  |  s_t = s}
      
      TP_s =   {ŝ_t ∈ P_s  | ŝ_t = s_t ∈ O_k}
  
  
      Precision =1/N_s∑_s=1^N_s|TP_s|/|P_s|  ,   Recall = 1/N_s∑_s=1^N_s|TP_s|/|T_s|
  
  
  
  
    §.§.§ RQ3
  
  We used the same metrics as RQ1 and RQ2.
  
  
  
   §.§ Comparison Baselines
   
  
  
    §.§.§ RQ1 (CPD) baselines
   
  We used `ruptures' library developed by authors of a recent CPD survey study <cit.>. It provides a modular framework for applying several CPD algorithms to univariate and multivariate data. 
  As mentioned earlier two main elements of a CPD algorithm in their survey are the search method and the cost function.
  
  We used Pelt <cit.> as the most efficient exact search method. As examples of approximate search methods, we applied bottom-up segmentation and window-based methods using a default window size of 100 <cit.>.
  However, after trying to run Pelt algorithm, we realized that it takes prohibitively longer to run compared to the approximate methods without providing much better results, so we only use the bottom-up and the window-based segmentation methods, as our CPD baselines.
  
  For the cost function, we tried “Least Absolute Deviation”, “Least Squared Deviation”, “Gaussian Process Change”, “Kernelized Mean Change”, “Linear Model Change”, “Rank-based Cost Function”, and “Auto-regressive model change” as defined in the library. Their parameters were left as default.
  To optimize the number of change points a penalty value (linearly proportionate to the number of detected change points) is added to the cost function, which limits the number of detected change points, the higher the penalty the fewer reported change points. We tried three different ratios (100, 500, and 1000) for the penalty.
  
  
  
  
    §.§.§ RQ2 (Multi-class classification) baselines
  
  We used a sliding window of width w over the 10 time-series values and then flattened it to make a vector of size 10w as the features. For the labels, we used one-hot encoded state of the system.
  The window sizes were chosen as same as the sizes of convolutional layers' kernel sizes (3, 5, 10, 15, 20), to make the baselines better comparable with our method. 
  We used Scikit-learn's implementation of the classification algorithms: A ridge classifier (Logistic regression with L2 regularization) and three decision trees. The ridge classifier was configured to use the built-in cross validation to automatically chose the best regularization hyper-parameter α in the range of 10^-6 to 10^6. Each decision tree was regularized by setting “maximum number of features” and “maximum depth”. For “maximum number of features” we tried no limits, √(10w), and log_210w. To find best “maximum depth” we first tried having no upper bound and observed how deep the tree grows; then we tried multiple numbers less than the maximum, until a drop in performance was observed. 
  
  
  
  
    §.§.§ RQ3 Hybrid vs. Homogeneous baselines
  
  We compared two versions of the model, one fully convolutional and one fully recurrent, with the full hybrid model to see if combining RNNs and CNNs has an added value or the same results could be achieved using only one type of layers.
  
  
  
  
   §.§ Dataset and the Data Collection Process
  
  We ran 948 existing test cases from MicroPilot's test repository using a software simulator[It is developed by MicroPilot Inc and provides an accurate simulation of the aerodynamic forces on the aircraft, the physical environment irregularities (e.g. unexpected wind gusts), and noises in sensor readings] and collected the logged flight data, over time. The test cases are system-level tests. Each test case includes a flight scenario for various supported aircraft. A flight scenario goes through different phases in a flight such as “take off”, “climb”, “cruise”, “hitting way points”, and “landing”.
  We sampled input and output values (listed in Table <ref>) at 5 Hz rate, which is the rate that AutoPilot reads the sensor values and performs the calculations required to update its output values at.
  
  
  Above Ground Level
  Out of the 948 flight logs, we omitted 60 that were either too short or too long (shorter than 200 samples or longer than 20k samples). Figure <ref> shows the distribution of the remaining log lengths. The maximum length (L) was 18,000 samples.
  
  
  
  
  
  The dataset was randomly split into three chunks of 90%, 5%, and 5% for training, validation, and testing, where each sample corresponds to one test execution. Note that separate test and validation sets are needed to facilitate proper hyper-parameters tuning, without leaking information. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Experiment Execution Environment
   
  Training and evaluation of the deep learning model was done on a single node running Ubuntu 18.04 LTS (Linux 5.3.0) equipped with Intel Core i7-9700 CPU, 32 gigabytes of main memory, and 8 gigabytes of GPU memory on a NVIDIA GeForce RTX 2080 graphics card.
  The code was implemented using keras on TensorFlow 2.0.
  
  The baseline models could not fit on that machine, so two nodes on Compute Canada's Beluga cluster, one with 6 CPUs and 75GiB of memory and one with 16 CPUs and 64GiB of memory, were used to train and evaluate them.
  
  
  
   §.§ Results
   
  In this section, we present the results of the experiments and answer the two research questions. 
  
  
    §.§.§ RQ1 Results: CPD Performance
  
  
  
  Table <ref> shows the results of running CPD algorithms for various configurations (as described in <ref>). For each search method and cost function pair only one of the penalty values which resulted in the highest F1 scores for all τ values is reported. 
  
  The first observation from the results is that as values of τ increases the scores get better. This was expected, since larger values relax the constraints on which detected change points are considered as a true positive. Another observation is that the bottom-up segmentation consistently outperforms the window-based segmentation method. We can also see that the linear cost function beats all the other ones, in terms of precision. The Gaussian cost function achieves much higher recall values costing it a huge loss in precision. It means this cost function results in detecting numerous change points spread across the time axis, so there is a good chance of having at least one change point predicted close to each true change point (hence the high recall), but also there are a lot of false positives, which leads to a low precision. 
  
  
  
  Measuring the same metrics on how our model performs on the test data shows better scores, almost twice the F1 score of the best performing baseline (see Table <ref>). Please note that unlike machine learning algorithms (such as ours), CPD algorithms do not have a separate training and testing phases. This fact works in their favor (by using the entire dataset for prediction and not just the training set), but still our model outperforms them.
  
  
  In terms of execution cost, running all 42 different settings of CPD algorithms on the whole dataset took a bit over 12 hours in the cloud using 16 CPUs and 64GB of main memory. The deep learning model on the other hand takes about an hour to train (which only needs to be done once), on a smaller machine (see section <ref>). It made predictions on the whole dataset in less than a minute.
  
  So to answer RQ1, our method has shown (66.18/32.73)-1=102.20% improvement in F1 score with τ=1s, (78.06/41.52)-1=88.00% with τ=3s, and (85.42/44.46)-1=92.13% with τ=5s; almost doubling the score compared to the baselines. 
  
  
  Our model, which requires less memory compared to traditional CPD algorithms, improved their best performance by up to 102%, measured by F1 score, in less execution time.
  
  
  
  
    §.§.§ RQ2 Results: Multi-class Classification Performance
  
  To answer RQ2, we first compare different configurations of the baseline methods using the F1 score (harmonic mean of precision and recall) on the test data. The results are presented in Table <ref>.
  
  
  
  Comparing the baseline methods with our proposed method (the last row) in Table <ref> shows that our model outperforms all baselines. Comparing it with the model with the best F1-score shows a (86.29/73.21)-1=17.87% improvement in precision as well as a (95.04/82.16)-1=15.68% improvement in recall that means (90.45/77.42)-1=16.83% overall improvement in F1-score. 
  
  To have a feeling of how good our predictions are in practice, Figure <ref> shows the output of our model side by side with the ground truth. The horizontal axis shows sample ID (time) and the states are color coded. As it is seen, our algorithm performs better when the state changes are farther apart. Also there are some state changes that happen quite briefly which are not detected. That is not to a great surprise since it takes some time for state changes to be reflected in the outputs and those might not have got any chance.
  
  
  The classical models only see one window of the data at a time, convolutional layers on the other hand are more generalized and flexible since each filter in each layer is comparable to a sliding window. As we saw in Table <ref>, a larger window size means a higher performance. However, it gets significantly more difficult to train a model with large window sizes. In addition, convolutions can automatically learn preprocessing steps that could be beneficial such as a moving average. Each convolutional filter can learn a linear combination of its inputs. So when the convolutional layers are stacked on each other, with non-linear activation functions in between, the hypothesis space they can learn becomes quite large, probably much larger than most of the classical ML algorithms here. Also, they are still quite efficient (more efficient than baselines) due to parameter sharing and their high parallelizability.
  
  The fact that the performance improves as the window size increases indicates the positive effect of being able to see longer-term relations in detecting the system's state. Recurrent cells (such as GRU) can capture long-term dependencies (that do not necessarily fall into one window) and learn sequences. This is one of the major differences between an RNN model and others, such as decision trees, which do not have such a notion of a “long-term memory” as LSTM/GRU neural networks do. All a decision tree could see is the values in a sliding window.
  
  In terms of the training complexity (time and memory), our method is superior as well. That can largely be attributed to the use of deep learning. In baseline models, as the window size w grows the training and evaluation complexity grows, up to a point that they ran out of memory – consuming all the 47GB of main memory and swap area. This forced us to train them in the cloud. Meanwhile, as mentioned earlier, the deep learning model could be trained on a 8GB GPU in roughly an hour. (see section <ref> for the machines' specs). Also, the decision tree training was not parallelized using only one core of the CPU, while virtually all deep learning models can be heavily parallelized on a GPU/TPU. 
  
  
  Our model, which requires less than half as many CPUs and 70% as much memory compared to the best performing classical ML model, improved their best performance by up to 17%, measured by F1 score, in less execution time.
  
  
  
  
  
  
  
  
    §.§.§ RQ3 Results: Hybrid vs. Homogeneous model
  
  As the results in table <ref> suggest, using a hybrid architecture in this problem delivers more than sum of its parts, outperforming the fully convolutional and fully recurrent baselines. 
  We can also see how the RNN baseline got closer results to the full model, suggesting the important role it plays in capturing long-term relations in the data and inferring the system's internal state.
  
  You might also notice that the results in the last column differ a little (around 1% in absolute value) from their corresponding results in tables <ref> and <ref>. That is due to randomizations in splitting the data into training, testing, and validation sets.
  
  
  
  The hybrid architecture performs better than a comparable RNN model or fully convolutional model, however the recurrent section plays a more important role in the model's performance.
  
  
  
  
   §.§ Limitations and Threats to Validity
   
  One of the limitations of our approach is that it might miss an input-output invariant correlation. It can happen when the input remains constant or it changes too little to reveal its relation with certain outputs, therefore remaining unobserved. However this is a shared shortcoming of dynamic analysis approaches.
  
  We assume that during the data collection, sampling happens in regular intervals; our approach probably will have a hard time achieving high performances, working on unevenly spaced time-series data.
  
  
  
  In terms of construct validity, we are using standard metrics to evaluate the results. However, the use of tolerance margin should be taken with caution since it is a domain-dependant variable and can change the final results. To alleviate this threats, we have used multiple margins and reported all results. 
  In terms of internal validity threats, we reduced the threat by not implementing the CPD baselines by ourselves and rather reusing existing libraries. 
  In terms of conclusion validity threats, we have used many (888) real test cases from MicroPilot's test repository and provided a proper train-validation-test split for training, tuning, and evaluation. 
  Finally, in terms of external validity threats, our study suffers from being limited to only one case study. 
  However, the study is a large-scale real-world study with many test cases. 
  We plan to extend this work with more case studies from other domains, to increase its generalizability. 
  
  
   
  
  
  § RELATED WORK
   
  
  
  
   §.§ Time Series Change Point Detection
  
  Change point detection is a well-studied subject due to its wide range of applications <cit.>.
  Several statistical and algorithmic methods have been tried to tackle several variations of this problem <cit.>. 
  The models vary based on: whether the whole data is available at once (offline) or it is being generated on the go (online), whether there are statistical assumptions about the data distribution <cit.>, whether the number of change points is known <cit.>, or whether we are dealing with a univariate or a multivariate time series, etc. 
  
  Ives and Dakos utilized locally linear models and used statistical significance test to determine at which point the changes in model parameters are large enough to signal a change in the state <cit.>. Blythe et al., used subspace analysis to reduce data dimensionality to keep the most non-stationary dimensions. This process helps detecting change points more effectively <cit.>.
  Several techniques have used penalty functions to find models that best fit each segment of the signal <cit.>. 
  Desobry et al., and Hido et al., proposed methods to indirectly use classifiers such as SVM to detect change points <cit.>. We applied their approach on our data in early stages of the research but it could not perform as others.
  Lee et al., trained deep auto encoder networks that learns latent features in the data to detect change points <cit.>. Ebrahimzadeh et al., proposed what they call a pyramid recurrent neural network architecture, which is resilient to missing to detect patterns that are warped in time <cit.>.
  
  There are also a family of methods based on Bayesian models that focus on finding changes in parameters of underlying distributions of the data <cit.>. 
  
  Making assumptions about the data such as its distribution or the distribution of change points across the time and relying on basic statistical properties are the two major short comings of traditional CPD methods <cit.>, which our proposed approach has overcome.
  
  
  
  
   §.§ State Model Inference
  
  Roughly speaking, dynamic EFSM[Extended Finite State Machines, are special kind of state machines that have conditional expressions called “transition guards” on their transitions <cit.>. A state transition can only happen if the transition guard evaluates as true.] inference algorithms generally take a trace of “events” (along with perhaps some variable values) as their input <cit.> to infer a generalized finite state machine. They use the events to find the state transitions and the values for detecting invariants and generating the guard conditions on the transitions. 
  k Tails, Gk Tail, EDSM, and MINT are examples of these algorithms, each improving upon the previous one <cit.>.  
  
  Walkinshaw et al., proposed an algorithm and developed a tool for state model inference <cit.>. Their work is based on previous endeavors on state merging algorithms such as gk-tail and k-tails <cit.>. These methods require an execution trace of the program consisting of a list of “events” that occurred during program execution, such as function calls, system calls, transmitted network data, etc. Krka et al., performed an empirical study on 4 different categories of model inference algorithms to figure out what makes each group of methods more effective <cit.>. Beschastnikh et al., proposed a method to mine invariants from partially ordered logs from concurrent/distributed systems <cit.>. Invariants can be used to augment state models <cit.>. Groz et al., use machine learning to heuristically infer state machine models of a un-resettable black-box system <cit.>, however a significant difference between our method and theirs is that their method still relies on discrete events (such as HTTP request and responses) while our method does not assume that the input and outputs contain any kind of “events” happening at certain times. Our method aims to search for such events as change points in a continuous stream of data as time series. 
  
  
  
  
   §.§ Using Deep Learning on Time Series Data
   
  Human activity recognition (HAR) is a well researched task which is quite relevant to the problem of black-box model inference. In HAR, just like in our context, a multivariate time series data is created from various sensors on a human body. The goal is to figure our what was the activity that human was performing in different time intervals. The sensors can be body worn accelerometers, or more generic sensors such as the ones found in a smart watch or a smartphone. 
  Murad et al., <cit.> have shown deep RNNs outperform fully convolutional networks and deep belief networks in HAR task.
  Hybrid models are the combination of some deep architectures <cit.>, such as a CNN + RNN or a CNN + a fully connected net. Morales et al., have shown the former preforms better than the latter in HAR <cit.>. Yao et al., <cit.> introduced a CNN + RNN architecture that outperforms the state of the art both in classification and in regression tasks. Similar results have been shown in other works such as <cit.>, as well.
  
  Another related topic here is the time series classification. However, time series classification techniques often output only one label classifying entire data, thus not applicable in our context. What is more related to our problem is called “segmentation”, using the computer vision terminology (not be confused with time series segmentation, such as <cit.>). U-net is one of the promising auto-encoder architectures for image segmentation <cit.>. Perslev et al., developed a similar idea for time-series to capture long-term dependencies and called it U-time <cit.>. It is fully convolutional and does not use memory cells (recurrent cells). A fully convolutional model can perform very well, since convolutions operate locally and image segments are large chunks of pixels in the 2D space and capturing local features using neighbouring pixels is quite useful. However, it cannot necessarily be as powerful on a more limited 1D data of time-series with different characteristics from an image.  This study's design is optimized for the task of sleep phase detection, which does not have very clear boundaries between states and also the state changes are not very frequent. Therefore, the same method does not necessarily generalize to tasks such as ours, where we cannot make assumptions about frequency of state changes.
  
  
  
  
  
  
  
  § SUMMARY AND FUTURE WORK
    
  In this paper, we introduced a hybrid CNN-RNN model that can be used for both CPD and state classification problems in multivariate time series. The proposed approach can be used as a black-box state model inference for variety of use cases such as testing, debugging, and anomaly detection in control software systems, where there are several input signals that control output states. We have evaluated our approach on a case study of a UAV auto-pilot software from our industry partner with 888 test cases and showed significant improvement in both change point detection and state classification. In the future, we are planning to extend this research with more case studies from open source auto-pilots. In addition, better tuning of hyper-parameters will be explored. Finally, we plan to examine the use of transfer learning to reduce the labeling overhead.
  
  
  
  We would like to thank the anonymous reviewers for their constructive comments.
  We acknowledge the support of the NSERCNatural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number NSERCCRDPJ/515254-2017].
  
  
  ACM-Reference-Format
  
  
  