This paper addresses the problem of evaluating the communication behavior of cyber physical systems. An important problem for the validation of the interaction in the distributed system is missing, wrong or incomplete specification. In this paper, the application of a new approach for assessing the communication behavior based on reference traces is presented and evaluated. The benefit of the approach is that it works automatically, with low additional effort and without using any specification. This paper provides a use case in conjunction with a feasibility study to investigate the applicability of a selflearning anomaly detection methodology. The data of the feasibility study are created by applying the described anomaly detection within a real vehicle network.
This paper focuses on test and validation of the communication behavior in cyber physical systems (CPS). On such systems with highly distributed functionality like it can be found in modern car’s electronics, the communication behavior is an important aspect on system validation. At field operational test it is important to analyze the network traffic in a fully assembled car. Even if all single electronic control units are tested exhaustively, a significant portion of remaining bugs resulting in errors or malfunction is lately found at real driving or field operational test.
The most important problem of ensuring the correct interaction of functions in CPS
at system-level is missing, wrong or incomplete specification (compare [
Because network traffic represents the internal behavior of a distributed system, its
analysis can help to detect possible bugs earlier and faster. But especially on system
level test it is not easy to rate about the correctness of communication at the network.
In [
The paper is structured as follows. In chapter 2 the use case for the proposed methodology and its integration in the test process explained. Chapter 3 provides the previous work and basically describes the new self-learning methodology. In chapter 4 the quality measurements for proofing the feasibility are defined and calculated. The paper closes with chapter 5 conclusion and future work. 2
The new approach presented in this paper shall help to find bugs in field operational tests faster. For this reason an important aspect of the proposed solution is the integration in the established testing and validation process for the car’s electronic infrastructure. To get an overview about the testing process of this distributed but even closed system in the following the basic testing steps for such a distributed system are described.
As in every software development cycle the first test stage are unit tests and basically the second stage are integration tests. On integration tests, the different applications belonging to an electronic control unit (ECU) are integrated and the basic functionality required from this ECU is tested. The next test level in testing can be characterized as system validation, often it is called system test. This is a test on system level, where the interaction of different ECUs is tested.
Because of the strong interaction of the embedded applications of a car with its
environment, field operational tests are commonly finalizes the validation. For
software realized functions this kind of test became important at least with the
introduction of advanced driver assistant systems which need to be evaluated in real
driving tests (compare [
Since the distributed network of ECUs inside the car is a closed system, in most cases it is not possible to control the endurance test on network level. In case of field operational test, mostly normal driving tasks are executed by the test drivers. At this testing level the test driver is only able to detect software bugs that lead to a noticeable malfunction of the car and its components to the driver. Because this is a very limited perspective to the executed software system, in most cases the network traffic from inside the car is recorded at test drives. The recorded network traffic provides information about the internal behavior of the cars electronic infrastructure at test drives. These traces are beside the voting of the test driver, the only source of information for validating the behavior of the cars electronic.
Only when these test drives are executed without a detected malfunction over a dedicated distance of kilometers the electronic system of the tested car passed the final acceptance test. There are still a lot of remaining bugs that are lately found within these tests with fully assembled car. It did not surprise that there could be easily summate a few million kilometers until all remaining bugs are found, fixed and a test period can be successful completed.
There are two ways to shorten this expensive and time consuming procedure to get a fault free tests drive period within the endurance test. The first one is to reduce the number of remaining bugs that can cause malfunction at test drives. This require better testing methodologies at earlier development phases. Or secondly try to identify possible bugs faster and more efficient within the test drives.
The first one is questionless methodically the clean way. But one of the basic
problems in praxis is missing, wrong or incomplete specification of system
requirements. This problem becomes commonly relevant with a high number of
interacting functions like it can be found highly distributed functionality. To solve this
problems there are many research in progress (e.g. [
This paper provides a new solution for the second way, the faster identification of potential bugs within test drives. This solution basically tries to identify changes in the system behavior by comparing it with a reference trace. Thereby the probability that this new behavior which is not represented within the reference trace is caused by a bug seems to be high. For this reason a self-learning methodology for an automatic evaluation of the recorded network traffic from field operational tests is presented and evaluated in this paper. 3
This chapter provides an overview of the author’s previous work that motivates this new approach and provides the foundation and experiments for the proposed selflearning method.
In [
Therefore the goal is the construction of a method that allows a qualitative comparison between communication that is presented within a reference trace and newly recorded traces. The essential outcome of the proposed procedure is the awareness, that the newly recorded network trace represents a new system behavior, which was not represented within the reference trace. If such a behavior is recognized, the method outputs a trigger or some equivalent information to the tester. At this point two potential expectations about the tested network behavior can be made: 1) A newly implemented or just jet not observed behavior was found, or 2) A bug in in communication behavior is detected. Just at this point a system expert has to decide if the proposed method detects case 1) or 2). Surely it is not possible to detect bugs, which are already within the reference trace included, but if no other tests detect these bugs and these bugs did not lead to malfunction, it is not sure if it is a bug or just unspecified behavior.
In conjunction to this idea, starting with [
Because of the unsatisfactory false alarm rate and the high performance utilization
of the neural networks, other learning algorithms were looked for. The Angluin L*
algorithm which is able to generate finite state automata (compare [
A solution for this problem was provided in [
The identification of independent execution graphs within the network trace was
undertaken in [
If the reference trace represents the normal behavior of a system the inferred
automata should accept this normal behavior. If a newly recoded trace holds even a
normal behavior of the system, the automata should accept this trace. If this trace
holds another behavior it should be rejected by the automata. If the inferred automata
do not accept a newly recorded trace, this trace potentially holds a behavior that is out
of the norm. This can be called an out of norm (OoN) behavior (comp. [
Even though it is now possible to extract acceptance automata that describe the behavior of the reference trace satisfactory, the usage of these automata for evaluating other traces is still not proofed. For applying this methodology to the introduced use case of finding bugs within network traces from field operational test, it is necessary to proof the quality of the inferred automata in conjunction to that use case. That means, that a more detailed analysis of the expectable rate of false alarms and the percentage of bugs that are detectable needs to be done.
In the following the basic characteristics for determining the quality and usability of the OoN-detection are explained, defined and estimated. With the usage of real CAN-traces the feasibility of the proposed OoN-detection in an automotive test scenario is examined. 4.1
The first criterion for a test mechanism is the test coverage. In the case of the proposed self-learning approach the definition of coverage needs to be adopted to the visible system behavior. The visible system behavior in this case is completely included within the reference trace. The coverage needs to be calculated in relation to the reference trace. A trace basically consists of a set of events . A sequence of events is defined by . In case of a network trace a sequence defines the complete recorded amount of events in the given period, which can be easily more than 106 events.
In [
The essential criterion for classification is the rating if the classified belongs to a specific class of object or not. In case of the OoN-detection the trace needs to be classified in the two decision classes: (1) the trace has the same behavior as the reference trace (2) the trace has a different behavior as the reference trace. To rate if the decision of the OoN-detector is correct there are for different results possible: 1. True positive (tp) :The trace was classified to has the same behavior as the reference trace and this was correct 2. False positive ( ):The trace was classified to has the same behavior as the reference trace, but this was not correct 3. True negative ( ):The trace was classified to has a different behavior as the reference trace and this was correct 4. False negative ( ):The trace was classified to has a different behavior as the reference trace, but this was not correct false alarm rate rate of detectable anomalies
With this attributes the two important relational criteria, the false alarm rate and the rate of detectable anomalies , can be calculated. (3) (4)
The rate of detectable anomalies determines the percentage the method find real OoN deviations in a trace. The optimal way to calculate this rate would be to have traces that holds known bugs, that can be presented to the OoN-detection. But for this kind of bug detection no public data sets are available.
A practicable method for estimating the rate of detectable anomalies is the instrumentation of a trace which has no bugs inside and is completely accepted by the inferred automata. In the proposed use case this needs to be the reference trace that was used to learn the acceptance automata. For estimating the rate of detectable anomalies the reference trace was instrumented in three different ways: (1) a randomly selected event is deleted from the trace (2) a randomly selected event is duplicated and (3) a randomly selected event is replaced by another randomly selected event.
The estimation of the false alarm rate turns out to be more complicated. Since the reference trace describes not all possible behavior, the OoN-detection will find necessarily new behavior within the test traces. But without a deeper knowledge of the system, it is not possible to decide if the OoN-detection did in fact identify new behavior or not.
Because a false alarm is not directly identifiable it would be helpful to have a look at the causes of false alarms. If it is clear what circumstances can cause a false alarm, it should be possible to estimate the count of false alarm otherwise.
The inferred acceptance automata of the OoN-detection mechanism are not based on probabilistic decisions like neural networks or Markov chains. Therefore it can be shown that the inferred acceptance automata do always evaluate the reference trace correct and in the same way. But these acceptance automata can be overfitted that they only accept the behavior of the reference trace. An overfitting in that case means that an acceptance automaton evaluates events that are not correlated to each other. Only if the events are correlated, they can have a dedicated behavior that is reproducible and can therefore declared as normal. If an inferred acceptance automaton is overfitted it accepts only the reference trace but no other traces. It can be pointed out that the most significant part of false alarms will be caused by overfitted automata. Therefore the ascertainment of the number of overfitted automata will give a first impression of the false alarm rate.
It is a strong indication of overfitting, if an inferred acceptance automaton rejects all the tested traces except the reference trace. To estimate the false alarm rate, one test trace is evaluated by the inferred acceptance automata. All automata that reject this trace are taken in the next step to evaluate the other test traces. If an automata reject all test traces it is very likely overfitted. 5
Results of feasibility study The best way to examine the feasibly of the described OoN-detection mechanism would be the evaluation with real network data that have known anomalies. But for the proposed use case, for the evaluation of network data from a cars network, there are no such data sets available.
The evaluation results presented in this chapter are generated by using real network data that are taken from a powertrain CAN of a car in series production. Because of the usage of a proven in use product, it is expected that these network data do not have any faults or anomalies.
The starting point for the evaluation is the reference trace that was used in [
For the quality measurement four test traces on the same car at different driving scenarios are recorded. The recording time of these traces is in the range of 14.60 min to 2.85 min and has in total approximately 26 min (see Table 1).
For estimating the false alarm rate Trace 1 is evaluated by the 2,848 acceptance automata. This trace is rejected by 1,943 automata as shown in the first column of Fig. 1. When these automata are checked for overfitting with trace 2 a number approximately seems to be overfitted because they reject trace 1 and 2. If these overfitted automata are excluded 181 remaining automata generate an OoN-trigger. If these remaining automata are additionally checked with trace 3 and 4 a number of 114 automata are left that seems to be not overfitted. That means with the additionally plausibility check with only 2 trace a remaining false alarm rate of can be achieved (compare Fig. 1).
2000 a 1800 t jce 1600 re 1400 t a 1200 h ta 1000 ta ce 800 tom tra 600 au 400 fo 200 reb 0 m u n 1943 90% 181 40%
114 number of automata that automata that automata that reject trace 1 and reject trace 1 and reject trace 1 not trace 2 not trace 2,3,4
The experiments for estimating the rate of detectable anomalies are executed by instrumenting the reference trace. The results are shown in Table 2. In the experiment approximately 0.1 % of the trace was modified, that leads to about 2.500 injected anomalies.
The 2.848 initial inferred automata cover approximately 80 % of the trace (see Fig. 2 with ). When the overfitted automata are excluded a number of 770 acceptance automata are usable for OoN-detection. These do have still a coverage of approximately 45 % (compare Fig. 2 right column).
After the overfitting analysis a number of 770 automata are usable for OoNdetection. If the OoN-detection mechanism is applied to these automata for the given reference traces 621 of these automata do accept all four test traces. A number of 149 automata rejects at least one test traces. In Fig. 3 the resulting coverage of the detected normal behavior and the detected not normal behavior is shown.
100% d taan taa 80%
m taom tauo au le 60%
b d a e s r r u e f ifn eo 40% feo tgan g a rvaeo rcep 20% C
0% 100% N oO 80% d n a r ivo 60% a eh re b g la irg 40% rm T o n feo 20% g a r e vCo 0% trace coverage event coverage usable automata (%) 45% 26%
35% 14%
11% non overfitted automata normal behavior 19% 9%
3% positive OoN
Trigger trace coverage event coverage usable automata (%)
The results provide a first impression of the applicability of the proposed
selflearning OoN-detection. The evaluation based on real CAN-communication is a first
step for approving the proposed OoN-detection. The most critical point is of course
the false alarm rate. Although the estimation of this rate tends to be difficult task, the
results provide an evidence that the false alarm rate tends to be in the range of 40 %.
In comparison to automatic test methods like code checker this seems to be acceptable
(comp. [
This paper explains and evaluates an application use case for an self-learning OoNdetection that was established in prior work. Since the proposed OoN-detection is a new approach in the area of system validation, this paper provides a basic quality measurement for this automatic self-learning approach.
It could be shown that the proposed self-learning OoN-detection is potentially usable to detect anomalies in the communication behavior in comparison to a reference trace. Essentially for the critical false alarm rate the usage in a testing environment with approximately 40 % seems to be acceptable.
The provided evaluation results are recorded from a car in series production that has potentially no bugs inside. For this reason a further investigation within a real testing environment needs to done to learn more about the expected outcome and usability of the proposed self-learning OoN-detection for CPS. 7