# Security-Aware Scheduling for FlexRay-Based Real-Time Automotive Systems

Authors: R. Zhao; G. H. Qin; H. P. Chen; J. Qin; J. Yan
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

FlexRay is a hybrid communication protocol tailored to the requirements of safety-critical distributed real-time automotive systems, providing support for the transmission of time-critical periodic frames in a static segment and event-triggered frames in a dynamic segment. With the development of intelligence and networking of vehicles, such systems are becoming increasingly connected to external environments; thus, security has become a pressing issue in system design. However, FlexRay-based architecture does not have direct support for secure communication. When deploying the security mechanisms on these architectures, a primary challenge is to guarantee the schedulability of systems, given the tight resource constraints and strict timing constraints. In this paper, we apply an authentication mechanism based on the delayed exposure of one-way key chains to protect the authenticity of messages on FlexRay and make a slight modification to reduce the authentication delay. On that basis, we propose a mixed integer linear programming formulation for solving the scheduling problem of FlexRay-based real-time automotive systems subject to both authentication mechanism constraints and other traditional design constraints. Experimental results demonstrate the effectiveness and efficiency of the proposed method in system design and indicate the necessity of collaborative design between security and other functionalities.


---

## Body

## 1. Introduction

In recent years the number of electronics-based and software-based functionalities is constantly increasing in modern vehicles. X-by-wire systems are replacing the typical hydraulic and mechanic systems to improve the control efficient and handling stability of vehicles. Active safety systems such as lane departure warning, adaptive cruise control, collision prevention assist, electronic stability program, or blind spot detection make vehicles safer and more comfortable. These new function applications are often implemented on a distributed architecture with high demands on the in-vehicle network in terms of bandwidth and deterministic behavior [1]. To overcome the deficiencies of the predominant event-triggered control area network (CAN) [2] for in-vehicle communication, the time-triggered (TT) architecture based on FlexRay [3] is becoming increasingly more common for implementation of such safety-critical automotive systems [4–6].FlexRay is a hybrid in-vehicle communication standard with fully deterministic and high bandwidth (10 Mbps). In FlexRay, time is divided into communication cycles, and each cycle contains both a Static Segment (ST) with time-triggered (TDMA) communication and a Dynamic (DYN) Segment with event-triggered communication. The ST segment enables the transmission of time-critical frames in a predefined position of the cycle. The DYN segment is used to transfer less critical frames such as diagnosis and maintenance data. FlexRay includes a dual channel bus specification and strong error-detection mechanisms for increased reliability. These capabilities make it a powerful network solution in automotive domain.With the development of intelligence and networking of vehicles, automotive systems are becoming increasingly connected to the physical environment, mobile devices, surrounding infrastructures, and other systems. A wide range of communication interfaces increases the risks of systems being compromised by attackers. In [7–11], the researchers demonstrated that modern automotive systems are vulnerable to attacks through various interfaces such as OBD-II, Bluetooth, Wi-Fi, DSRC, GPS, and 3G/4G. Once one Electronic Control Unit (ECU) of the system is compromised by malicious attackers through any interface, they can gain access to other safety-critical ECUs via internal network and inject malicious messages, thereby inducing system failures. It is therefore important to guarantee the authenticity of the communication data of automotive systems. However, despite the various advantages of FlexRay-based architecture, it does not directly provide multicast source authentication to protect data authenticity.Integrating authentication mechanisms into FlexRay-based real-time automotive systems is not an easy task. Such systems usually have tight resource constraints, such as limited computing and bandwidth resources, strict timing constraints, and high-performance requirements with respect to latency and extensibility. This makes it virtually impossible to add authentication mechanism after the scheduling design stage without violating the system constraints or degrading the system performances. Therefore it is essential to address security together with other constraints and objectives from the beginning of scheduling design process.This involves two issues: The first is to deploy an appropriate multicast authentication mechanism considering the resource constraints and timing constraints of the systems; the second is to develop an optimal security-aware design of system scheduling subject to both authentication mechanism constraints and all other traditional design constraints, which are often in conflict and require careful trade-offs.A number of studies on multicast authentication mechanisms have been reported in literature [12–22]. Digital signatures based on public key cryptography provide an elegant method for signing multicast data, but they are not the solution in our context because of the high computational overhead. Although the computational overhead could be alleviated by dedicated circuits, such as FPGAs or ASICs, this will add component costs, an issue that is typically avoided by manufacturers. Schemes using one-time signatures [12, 14, 15] are much more computationally efficient than traditional public key signatures. However, one-time signatures can incur kilobytes of authentication data per message, which makes them impractical for automotive systems with the requirement of real-time and efficient data transmission.In contrast, symmetric cryptography is more suitable for the constrained environments. Simply applying the point-to-point authentication mechanisms, such as appending a message authentication code (MAC) to each message or every other message computed by a secret key shared across all nodes, cannot provide adequate multicast authentication. The problem is that any node which holds the secret key can forge message and impersonate the sender. Several schemes [16, 17] have been based on the concept that a sender shares a unique symmetric key with each receiver to prevent this attack. For each message, the sender generates and sends one MAC for each distinct receiver. However, even for a small number of receivers, the computational and bandwidth overhead makes this approach infeasible for automotive systems with tight resource constraints and strict timing constraints. TESLA [18] provides multicast authentication based on delayed disclosure of keys by using only symmetric cryptography. The core idea of TESLA is that the sender appends to each message a MAC computed by using a key known only to itself and discloses this key after a short time interval. Each receiver buffers the received frame and then verifies the authenticity after it receives the correct key. TESLA was extended and applied in resource constrained wireless sensor networks by several authors [13, 19–22], because it provides an appropriate trade-off between security level and resource overheads.In this work, we choose the TESLA mechanism to perform multicast authentication on FlexRay bus and make a modification to the original TESLA so that it is more appropriate for our application setting.Moreover, the design synthesis of the FlexRay static communication schedule has also been well studied in the past [1, 23–29]. Schmidtet al. [23] addressed the scheduling problem of periodic signals in the FlexRay ST segment. In their study, signals are first packed into message frames while maximizing the utilization; the obtained messages are then scheduled in the FlexRay ST segment while using a minimum number of slots. Kanget al.[24] proposed a frame-packing algorithm that allows the packing of signals with different periods into a frame. Schmidtet al. [25] proposed an ILP-based method to assign ST slots for the signals. Grenieret al. [26] proposed a heuristic to construct the schedule on the ST segment of FlexRay systems. Some studies have further considered using the slot multiplexing mechanism on signal scheduling of FlexRay, which is specifically dedicated for scalable efficient bandwidth exploitation. Lukasiewyczet al. [27] applied single slot multiplexing to the scheduling of the ST segment with the objective of increasing the utilization of the FlexRay bus. Zhaoet al. [28] proposed a fast heuristic as well as an efficient integer linear programming (MILP) approach to optimize the scheduling of the FlexRay ST segment. They [29] also proposed a rectangle bin packing optimization approach to schedule communication signals with timing constraints into the FlexRay static segment at minimum bandwidth cost. Sagstetteret al. [1] proposed single-stage and multistage ILP approaches to schedule the FlexRay ST segment. All of the above works only focus on the communication schedule and did not attempt to schedule at the system-level. The isolated signal scheduling may seriously limit the feasibility and performance of automotive applications, which consist of both signals and tasks.A handful of studies have studied the scheduling on both signals and tasks for FlexRay-based real-time automotive systems. Zenget al. [30] applied MILP optimization framework to solve the scheduling problem for time-triggered systems communicating over the FlexRay ST segment. Huet al. [31] proposed a holistic scheduling algorithm for FlexRay-based time-triggered systems. Lukasiewyczet al. [32] presented a modular framework based on ILP to perform schedule synthesis for FlexRay-based time-triggered automotive systems. Royet al. [33] proposed a multiobjective cooptimization approach that synthesizes both the controllers and the task and communication schedules of FlexRay ST segment. However, none of the above-mentioned works considered the pressing concerns of security for automotive systems, i.e., the interference of security operations on system applications.Furthermore, several approaches have been proposed for the codesign of security and other traditional functions of embedded systems. Jianget al. [34] presented a constraint logic programming-based approach to efficiently implement cryptographic algorithms on the distributed real-time embedded systems. The objective of their approach is to determine the minimal hardware overhead and the mapping for encryption and decryption tasks of the system such that the confidentiality requirements for messages were fulfilled and the time constraints were satisfied. For authenticity, Wasiceket al. [35] presented an implementation of the TESLA mechanism in a Time-Triggered system but did not consider system-level design issues. Linet al. [36] applied MACs generated by a group session key to protect against masquerade and replay attacks on CANs, and they proposed an integrated MILP formulation to explore the mapping from the functional model to the CAN-based architecture platform. They [37] later proposed optimization algorithms for mapping from a functional model to a TDMA-based architecture platform, while both works focused on network scheduling issues but did not consider the CPU overheads of authentication operations as well as their interference on application tasks scheduling. Guet al. [38] proposed a security-aware optimization approach of FlexRay-based distributed systems, interested in minimizing the total used number of hardware units subject to schedulability. However their approach ignored the key authentication operations of the applied TESLA mechanism and therefore cannot provide adequate security.In this work, we analyze and model all the additional operations induced by TESLA authentication mechanism and then provide an MILP formulation for solving the scheduling optimization problem of FlexRay-based real-time automotive systems while meeting the requirements of both information security and functional safety.To this end, our major contributions are as follows.(i)
First, we apply the TESLA authentication mechanism to protect against forgery and replay attacks on FlexRay bus. It provides an appropriate trade-off between security level and resource overhead, compared with other multicast authentication approaches. Moreover, we make a slight modification to the original TESLA in order to improve on the authentication delay.(ii)
Furthermore, we propose an MILP formulation that efficiently solves the optimal scheduling problem of FlexRay-based real-time automotive systems with authentication mechanism constraints. The proposed approach considers end-to-end delays and the precedence constraints induced by information passing between all automotive control and authentication mechanism-related tasks and signals. The scheduling design includes (a) the packing of automotive control and authentication mechanism-related signals to FlexRay frames, (b) the scheduling of frames on FlexRay bus (i.e., slot assignment), and (c) the scheduling of automotive control and authentication mechanism-related tasks on respective ECU. The optimization objective is to maximize the laxity (difference between deadlines and response times) on time-sensitive function paths, therefore improving timing performance, or to minimize the number of used slots, therefore improving extensibility.The remainder of the paper is organized as follows. Section2 introduces the system model and application model. Section 3 presents the security mechanism and security model. Section 4 describes the security-aware optimization scheduling problem whose solution is tackled using MILP-based method. Section 5 shows experimental results, and Section 6 concludes the paper.


## 2. System Model and Application Model

### 2.1. System Model

The target platform is a typical distributed time-triggered automotive system: a cluster of ECUs that are connected via the FlexRay bus, as presented in Figure1(a). The ECU eg∈E runs the TT real-time operating system in which tasks are executed according to a schedule table that defines their start times. In addition, the network uses the ST segment arbitration model provided by the FlexRay protocol. Tasks are triggered based on a local clock in each ECU. The synchronization of local clocks throughout the system is provided by the FlexRay communication protocol.Figure 1
System model example.
(a) (b) (c)In FlexRay, the communication takes place in a recurring cycle, as depicted in Figure2. Each communication cycle involves the ST segment, DYN segment, symbol window, and network idle time. The static segment applies the TDMA scheme and is composed of several equally sized slots. During any slot in any communication cycle, the sole ECU Tmf which holds the frame fm∈F with the frame identifier equal to the current value of the slot counter, cycle number equal to the current value of the cycle counter is allowed to send counter and the corresponding frame on the bus. Clock synchronization, embedded in the standard, ensures deterministic communication at no additional cost.Figure 2
Basic structure of FlexRay communication cycles with a detailed illustration of the static segment.To support the efficient use of the ST, FlexRay provides a proprietary slot multiplexing mechanism that allows the alteration of frame contents being sent to this slot from cycle to cycle. The repetitionREmf of a frame fm with the slot multiplexing mechanism should be expressed as a multiple of the communication cycle, with the constraints that REmf∈{1,2,4,8,16,32,64} for version 2.1 of FlexRay and REmf∈{1,2,4,5,8,10,16,20,32,40,50,64} for version 3.0 of FlexRay. The lengths of ST slot Lslot, ST segment LST, and the communication cycle Lcycle are usually designed by the automotive Original Equipment Manufacturer (OEM), taking into account the composition of subsystems, reuse of components, and future design extensibility. In this work, because of standardization, we assume these design parameters as given inputs to our schedule synthesis.


### 2.2. Application Model

We model an applicationλr∈Λapp to be processed in the system as a directed, acyclic graph Grapp, where the vertices represent the tasks and the edges represent the signals communicated between tasks.A taskτi∈Γapp is characterized by the tuple (Eiτ,Liτ,Piτ,Diτ), where Eiτ denotes the ECU resource it needs to execute, Liτ is its execution time, Piτ is its period, and Diτ is its deadline. An edge linking two tasks τi and τi′ denotes a signal σj, produced by τi that is available to τi′. Each task reads its input at its start time and writes its results at the end of execution. A signal σj∈Sapp is characterized by the tuple (Tjσ,Rjσ,Ljσ,Pjσ,Djσ), where Tjσ and Rjσ denote the ECU resources required for sending and receiving it, Ljσ is its bit width, Pjσ is its period, and Djσ is its deadline.For example, in the applicationλ1 of Figure 1(b), task τ3 generates a multicast signal, and tasks τ5 and τ7 are the receivers of this signal. In our model, each branch of a multicast signal is represented as a separate signal because the branches have different receivers. Specifically, we define a set of signals Sg,h containing all of the branches of theh-th multicast signal of each ECU eg, such as signals σ9 and σ10 that are assumed to be the two branches of the first multicast signal of ECU e2; thus we have σ9,σ10∈S2,1.A function pathρε∈FPapp from τi to τi′ is a sequence τi,…,τi′ of tasks such that there is a link between any two consecutive tasks. For instance, in application λ1, there is a function path between tasks τ1 and τ5. The latency of function path is defined as the time interval between the start of an instance of τi and the completion of the instance of τi′ that produces a result that is dependent on the output of τi. The deadline Dερ of function path is set by system designers as an application requirement.


## 2.1. System Model

The target platform is a typical distributed time-triggered automotive system: a cluster of ECUs that are connected via the FlexRay bus, as presented in Figure1(a). The ECU eg∈E runs the TT real-time operating system in which tasks are executed according to a schedule table that defines their start times. In addition, the network uses the ST segment arbitration model provided by the FlexRay protocol. Tasks are triggered based on a local clock in each ECU. The synchronization of local clocks throughout the system is provided by the FlexRay communication protocol.Figure 1
System model example.
(a) (b) (c)In FlexRay, the communication takes place in a recurring cycle, as depicted in Figure2. Each communication cycle involves the ST segment, DYN segment, symbol window, and network idle time. The static segment applies the TDMA scheme and is composed of several equally sized slots. During any slot in any communication cycle, the sole ECU Tmf which holds the frame fm∈F with the frame identifier equal to the current value of the slot counter, cycle number equal to the current value of the cycle counter is allowed to send counter and the corresponding frame on the bus. Clock synchronization, embedded in the standard, ensures deterministic communication at no additional cost.Figure 2
Basic structure of FlexRay communication cycles with a detailed illustration of the static segment.To support the efficient use of the ST, FlexRay provides a proprietary slot multiplexing mechanism that allows the alteration of frame contents being sent to this slot from cycle to cycle. The repetitionREmf of a frame fm with the slot multiplexing mechanism should be expressed as a multiple of the communication cycle, with the constraints that REmf∈{1,2,4,8,16,32,64} for version 2.1 of FlexRay and REmf∈{1,2,4,5,8,10,16,20,32,40,50,64} for version 3.0 of FlexRay. The lengths of ST slot Lslot, ST segment LST, and the communication cycle Lcycle are usually designed by the automotive Original Equipment Manufacturer (OEM), taking into account the composition of subsystems, reuse of components, and future design extensibility. In this work, because of standardization, we assume these design parameters as given inputs to our schedule synthesis.


## 2.2. Application Model

We model an applicationλr∈Λapp to be processed in the system as a directed, acyclic graph Grapp, where the vertices represent the tasks and the edges represent the signals communicated between tasks.A taskτi∈Γapp is characterized by the tuple (Eiτ,Liτ,Piτ,Diτ), where Eiτ denotes the ECU resource it needs to execute, Liτ is its execution time, Piτ is its period, and Diτ is its deadline. An edge linking two tasks τi and τi′ denotes a signal σj, produced by τi that is available to τi′. Each task reads its input at its start time and writes its results at the end of execution. A signal σj∈Sapp is characterized by the tuple (Tjσ,Rjσ,Ljσ,Pjσ,Djσ), where Tjσ and Rjσ denote the ECU resources required for sending and receiving it, Ljσ is its bit width, Pjσ is its period, and Djσ is its deadline.For example, in the applicationλ1 of Figure 1(b), task τ3 generates a multicast signal, and tasks τ5 and τ7 are the receivers of this signal. In our model, each branch of a multicast signal is represented as a separate signal because the branches have different receivers. Specifically, we define a set of signals Sg,h containing all of the branches of theh-th multicast signal of each ECU eg, such as signals σ9 and σ10 that are assumed to be the two branches of the first multicast signal of ECU e2; thus we have σ9,σ10∈S2,1.A function pathρε∈FPapp from τi to τi′ is a sequence τi,…,τi′ of tasks such that there is a link between any two consecutive tasks. For instance, in application λ1, there is a function path between tasks τ1 and τ5. The latency of function path is defined as the time interval between the start of an instance of τi and the completion of the instance of τi′ that produces a result that is dependent on the output of τi. The deadline Dερ of function path is set by system designers as an application requirement.


## 3. Security Mechanism and Security Model

### 3.1. Security Mechanism

#### 3.1.1. Attack Model

We assume that an attacker can gain access to such system through a gateway linked with an external network, physical access to FlexRay channel, malicious insider code, or tampering with ECUs. We consider an active attacker model where an attacker can masquerade as other ECUs to inject forged messages and can also replay messages [17]. We assume that the attacker knows about the network schedule (e.g., by applying technical skill to reverse engineer the appropriate systems and protocols or purchasing such information from a third-party) and consequently has the ability to insert well-formed frames into FlexRay bus.


#### 3.1.2. Overview of the TESLA Mechanism

We apply TESLA authentication mechanism to protect the authenticity of messages on FlexRay bus. The main idea behind TESLA is to use time with the one-way key chain for asymmetry to enjoy the benefit of computational efficiency while having the asymmetric security property. TESLA requires loose time synchronization between the sender and the receivers. In this work, TESLA is initiated after the clock synchronization process of FlexRay is completed, so that it uses the synchronized time provided by FlexRay.In TESLA, time is divided into several intervals with uniform durationPint. Before protocol execution, the sender generates a one-way key chain of self-authenticating values using a hash functionH as K0,K1,…,Knint, where Kφ=H(Kφ+1), and assigns the keys sequentially to the time intervals, as depicted in Figure 3. The chain is used in reverse order starting with K1. To bootstrap TESLA, the sender uses asymmetric cryptography to distribute the initial key to every receiver in the network authoritatively.Figure 3
TESLA protocol example.When a sender sends a message inφ-th time interval, it appends a MAC to the message computed using a hash function and the key Kφ corresponding to the current time interval. The key remains secret ford intervals, so, along with the message, the sender also sends the key Kφ-d that it can disclose.When a receiver receives a message inφ-th time interval, it first checks the MAC is still secret by determining that the sender could not have yet reached the time interval for disclosing it. If the MAC key is still secret, then the receiver buffers the packet and verifies the authenticity after it gets the correct key Kφ. The legitimacy of key Kφ can be determined by verifying previously released keys Kφ-1 that Kφ-1=HKφ.


#### 3.1.3. Modification to the TESLA Mechanism

There are two following major barriers when using TESLA in FlexRay-based real-time automotive systems:(i) To ensure the key to be disclosed in an interval can arrive at its receivers on time, TESLA protocol specifies that the key must be appended to each message frame in that interval. This thus causes the waste of bandwidth and computing resources, as well as the increase of the authentication delay which is the most critical part in real-time automotive systems in general.(ii) In addition, the full-size MAC in TESLA makes FlexRay network communication inefficient; i.e., TESLA has an overhead of 32 bytes per packet.In this section, we make some modifications to the original TESLA, so that it provides better trade-off between security level and resource overhead.Modification 1: We specify that each key Kφ is released only once in its next interval and is transmitted through the ST segment to ensure its time determinism.Modification 2: We truncate the MAC size within the application frame, as long as the desired level of security is ensured, e.g., ISO 26262 standard. The standard constrains the permissible probability ϕ of automotive system failure in a time unit Punit. Following this, we assume that the maximum probability of a system failure due to any malicious data in a time unit, Punit, is constrained by ϕ. We define 1-ϕ as the security goal of each signal, which represents the quantified performance level with respect to forgery attacks. Without secret key, the generated MAC can be assumed to be random [17]. The probability of successfully forging a valid MAC with the size of LMAC bits is 2-LMAC. Assuming the period of the signal with the maximum security goal is Pmaxσ, the MAC size LMAC is truncated to the minimum value satisfying the following constraint:(1)1-2-LMACPunit/Pmaxσ>1-ϕThis constraint ensures that the global security probability of all instances of the signal during the time unitPunit is greater than its security goal 1-ϕ.


### 3.2. Security Model

After applying the modified TESLA authentication mechanism to the system, extra information, i.e., keys, needs to be sent and extra operations (including MAC generation, MAC verification, key generation, and key verification tasks) need to be executed.The MAC generation and verification tasks of each message framefm are executed on its sender and receivers. Moreover, the authentication-related operations of each key are considered as a time-triggered application. Similar to the automotive control applications, we model a key authentication application λr∈Λsec as a directed, acyclic graph Grsec, which includes the key release task τgrel generated by the sender eg, key verification tasks τg,g′ver generated by the receivers eg, and key signals σg,g′key produced by τgrel that is available to τg,g′ver. Figure 4 illustrates the additional operations after applying the authentication mechanism to the example system in Figure 1.Figure 4
Security model example.
(a) (b)For simplicity, the key authentication-related tasks or signals are also identified and denoted by a single index, as inτi or σj. A key verification task τi∈Γsec is characterized by the tuple Eiτ,Viτ,Liτ,Piτ, where Eiτ and Viτ are the ECUs it needs to execute and verify, Liτ is its time cost indicating the execution time of the one-way hash function H on the ECU Eiτ which can be simply measured, and Piτ is its period (i.e., the interval duration Pint of key release). The choice of interval duration is dictated by the special timing requirements of the automotive systems, which will be described in the next subsection. A key signal σj∈Ssec is characterized by the tuple (Tjσ,Rjσ,Ljσ,Pjσ), where Tjσ and Rjσ are the ECU resources required for sending and receiving it, Ljσ is its bit width, and Pjσ is its period. Specially, the design of system scheduling does not need to consider the key release tasks since the keys are generated during the initialization stage thus taking no time.


### 3.3. Choice of Interval Duration of Key Release

Following the authentication mechanism, the smaller the interval duration is, the more frequently the key authentication applications execute and thus the more processing and communication resources are consumed. But the larger the interval duration is, the longer the response times of the signals take, and thus the greater the likelihood that the signals and function paths will miss their deadlines. Therefore, to efficiently apply the authentication mechanism to the automotive systems, we choose the largest interval duration under the premise of satisfying the timing constraints of the systems.For a function pathρε∈FPapp, we let Lερ denote the number of tasks that need to receive signals arriving from network, also referred to as the signal level. We consider that the interval duration Pint is the maximum value satisfying the following constraints:(2a)∀ρε∈FPapp,Pint∙Lερ≤Dερ(2b)Pint≤minσj∈Sapp⁡Djσ(2c)Pintmod⁡gcdσj∈Sapp⁡Pjσ=0,orPint=n∙gcdσj∈Sapp⁡Pjσ,n∈Z∗Relations (2a) and (2b) provide the time limits; i.e., the product of interval duration Pint and signal level Lερ cannot exceed the deadline Dερ for a function path ρε∈FPapp. That is because the task that needs receive signals can complete authentication only in the next interval after the signals are transmitted, and thus normally, the whole process of a path ρε must have a duration of Lερ intervals. In addition, the interval duration Pint cannot exceed the minimum value of the deadlines Djσ of signals σj∈Sapp, to ensure that each signal can be authenticated by the receiver before its deadline. Relation (2c) is bound to the alignment of the key signals and automotive control signals schedules; i.e., the interval duration Pint should be an integer multiple or factor of the greatest common divisor (gcd) of the periods of all the signals.


## 3.1. Security Mechanism

### 3.1.1. Attack Model

We assume that an attacker can gain access to such system through a gateway linked with an external network, physical access to FlexRay channel, malicious insider code, or tampering with ECUs. We consider an active attacker model where an attacker can masquerade as other ECUs to inject forged messages and can also replay messages [17]. We assume that the attacker knows about the network schedule (e.g., by applying technical skill to reverse engineer the appropriate systems and protocols or purchasing such information from a third-party) and consequently has the ability to insert well-formed frames into FlexRay bus.


### 3.1.2. Overview of the TESLA Mechanism

We apply TESLA authentication mechanism to protect the authenticity of messages on FlexRay bus. The main idea behind TESLA is to use time with the one-way key chain for asymmetry to enjoy the benefit of computational efficiency while having the asymmetric security property. TESLA requires loose time synchronization between the sender and the receivers. In this work, TESLA is initiated after the clock synchronization process of FlexRay is completed, so that it uses the synchronized time provided by FlexRay.In TESLA, time is divided into several intervals with uniform durationPint. Before protocol execution, the sender generates a one-way key chain of self-authenticating values using a hash functionH as K0,K1,…,Knint, where Kφ=H(Kφ+1), and assigns the keys sequentially to the time intervals, as depicted in Figure 3. The chain is used in reverse order starting with K1. To bootstrap TESLA, the sender uses asymmetric cryptography to distribute the initial key to every receiver in the network authoritatively.Figure 3
TESLA protocol example.When a sender sends a message inφ-th time interval, it appends a MAC to the message computed using a hash function and the key Kφ corresponding to the current time interval. The key remains secret ford intervals, so, along with the message, the sender also sends the key Kφ-d that it can disclose.When a receiver receives a message inφ-th time interval, it first checks the MAC is still secret by determining that the sender could not have yet reached the time interval for disclosing it. If the MAC key is still secret, then the receiver buffers the packet and verifies the authenticity after it gets the correct key Kφ. The legitimacy of key Kφ can be determined by verifying previously released keys Kφ-1 that Kφ-1=HKφ.


### 3.1.3. Modification to the TESLA Mechanism

There are two following major barriers when using TESLA in FlexRay-based real-time automotive systems:(i) To ensure the key to be disclosed in an interval can arrive at its receivers on time, TESLA protocol specifies that the key must be appended to each message frame in that interval. This thus causes the waste of bandwidth and computing resources, as well as the increase of the authentication delay which is the most critical part in real-time automotive systems in general.(ii) In addition, the full-size MAC in TESLA makes FlexRay network communication inefficient; i.e., TESLA has an overhead of 32 bytes per packet.In this section, we make some modifications to the original TESLA, so that it provides better trade-off between security level and resource overhead.Modification 1: We specify that each key Kφ is released only once in its next interval and is transmitted through the ST segment to ensure its time determinism.Modification 2: We truncate the MAC size within the application frame, as long as the desired level of security is ensured, e.g., ISO 26262 standard. The standard constrains the permissible probability ϕ of automotive system failure in a time unit Punit. Following this, we assume that the maximum probability of a system failure due to any malicious data in a time unit, Punit, is constrained by ϕ. We define 1-ϕ as the security goal of each signal, which represents the quantified performance level with respect to forgery attacks. Without secret key, the generated MAC can be assumed to be random [17]. The probability of successfully forging a valid MAC with the size of LMAC bits is 2-LMAC. Assuming the period of the signal with the maximum security goal is Pmaxσ, the MAC size LMAC is truncated to the minimum value satisfying the following constraint:(1)1-2-LMACPunit/Pmaxσ>1-ϕThis constraint ensures that the global security probability of all instances of the signal during the time unitPunit is greater than its security goal 1-ϕ.


## 3.1.1. Attack Model

We assume that an attacker can gain access to such system through a gateway linked with an external network, physical access to FlexRay channel, malicious insider code, or tampering with ECUs. We consider an active attacker model where an attacker can masquerade as other ECUs to inject forged messages and can also replay messages [17]. We assume that the attacker knows about the network schedule (e.g., by applying technical skill to reverse engineer the appropriate systems and protocols or purchasing such information from a third-party) and consequently has the ability to insert well-formed frames into FlexRay bus.


## 3.1.2. Overview of the TESLA Mechanism

We apply TESLA authentication mechanism to protect the authenticity of messages on FlexRay bus. The main idea behind TESLA is to use time with the one-way key chain for asymmetry to enjoy the benefit of computational efficiency while having the asymmetric security property. TESLA requires loose time synchronization between the sender and the receivers. In this work, TESLA is initiated after the clock synchronization process of FlexRay is completed, so that it uses the synchronized time provided by FlexRay.In TESLA, time is divided into several intervals with uniform durationPint. Before protocol execution, the sender generates a one-way key chain of self-authenticating values using a hash functionH as K0,K1,…,Knint, where Kφ=H(Kφ+1), and assigns the keys sequentially to the time intervals, as depicted in Figure 3. The chain is used in reverse order starting with K1. To bootstrap TESLA, the sender uses asymmetric cryptography to distribute the initial key to every receiver in the network authoritatively.Figure 3
TESLA protocol example.When a sender sends a message inφ-th time interval, it appends a MAC to the message computed using a hash function and the key Kφ corresponding to the current time interval. The key remains secret ford intervals, so, along with the message, the sender also sends the key Kφ-d that it can disclose.When a receiver receives a message inφ-th time interval, it first checks the MAC is still secret by determining that the sender could not have yet reached the time interval for disclosing it. If the MAC key is still secret, then the receiver buffers the packet and verifies the authenticity after it gets the correct key Kφ. The legitimacy of key Kφ can be determined by verifying previously released keys Kφ-1 that Kφ-1=HKφ.


## 3.1.3. Modification to the TESLA Mechanism

There are two following major barriers when using TESLA in FlexRay-based real-time automotive systems:(i) To ensure the key to be disclosed in an interval can arrive at its receivers on time, TESLA protocol specifies that the key must be appended to each message frame in that interval. This thus causes the waste of bandwidth and computing resources, as well as the increase of the authentication delay which is the most critical part in real-time automotive systems in general.(ii) In addition, the full-size MAC in TESLA makes FlexRay network communication inefficient; i.e., TESLA has an overhead of 32 bytes per packet.In this section, we make some modifications to the original TESLA, so that it provides better trade-off between security level and resource overhead.Modification 1: We specify that each key Kφ is released only once in its next interval and is transmitted through the ST segment to ensure its time determinism.Modification 2: We truncate the MAC size within the application frame, as long as the desired level of security is ensured, e.g., ISO 26262 standard. The standard constrains the permissible probability ϕ of automotive system failure in a time unit Punit. Following this, we assume that the maximum probability of a system failure due to any malicious data in a time unit, Punit, is constrained by ϕ. We define 1-ϕ as the security goal of each signal, which represents the quantified performance level with respect to forgery attacks. Without secret key, the generated MAC can be assumed to be random [17]. The probability of successfully forging a valid MAC with the size of LMAC bits is 2-LMAC. Assuming the period of the signal with the maximum security goal is Pmaxσ, the MAC size LMAC is truncated to the minimum value satisfying the following constraint:(1)1-2-LMACPunit/Pmaxσ>1-ϕThis constraint ensures that the global security probability of all instances of the signal during the time unitPunit is greater than its security goal 1-ϕ.


## 3.2. Security Model

After applying the modified TESLA authentication mechanism to the system, extra information, i.e., keys, needs to be sent and extra operations (including MAC generation, MAC verification, key generation, and key verification tasks) need to be executed.The MAC generation and verification tasks of each message framefm are executed on its sender and receivers. Moreover, the authentication-related operations of each key are considered as a time-triggered application. Similar to the automotive control applications, we model a key authentication application λr∈Λsec as a directed, acyclic graph Grsec, which includes the key release task τgrel generated by the sender eg, key verification tasks τg,g′ver generated by the receivers eg, and key signals σg,g′key produced by τgrel that is available to τg,g′ver. Figure 4 illustrates the additional operations after applying the authentication mechanism to the example system in Figure 1.Figure 4
Security model example.
(a) (b)For simplicity, the key authentication-related tasks or signals are also identified and denoted by a single index, as inτi or σj. A key verification task τi∈Γsec is characterized by the tuple Eiτ,Viτ,Liτ,Piτ, where Eiτ and Viτ are the ECUs it needs to execute and verify, Liτ is its time cost indicating the execution time of the one-way hash function H on the ECU Eiτ which can be simply measured, and Piτ is its period (i.e., the interval duration Pint of key release). The choice of interval duration is dictated by the special timing requirements of the automotive systems, which will be described in the next subsection. A key signal σj∈Ssec is characterized by the tuple (Tjσ,Rjσ,Ljσ,Pjσ), where Tjσ and Rjσ are the ECU resources required for sending and receiving it, Ljσ is its bit width, and Pjσ is its period. Specially, the design of system scheduling does not need to consider the key release tasks since the keys are generated during the initialization stage thus taking no time.


## 3.3. Choice of Interval Duration of Key Release

Following the authentication mechanism, the smaller the interval duration is, the more frequently the key authentication applications execute and thus the more processing and communication resources are consumed. But the larger the interval duration is, the longer the response times of the signals take, and thus the greater the likelihood that the signals and function paths will miss their deadlines. Therefore, to efficiently apply the authentication mechanism to the automotive systems, we choose the largest interval duration under the premise of satisfying the timing constraints of the systems.For a function pathρε∈FPapp, we let Lερ denote the number of tasks that need to receive signals arriving from network, also referred to as the signal level. We consider that the interval duration Pint is the maximum value satisfying the following constraints:(2a)∀ρε∈FPapp,Pint∙Lερ≤Dερ(2b)Pint≤minσj∈Sapp⁡Djσ(2c)Pintmod⁡gcdσj∈Sapp⁡Pjσ=0,orPint=n∙gcdσj∈Sapp⁡Pjσ,n∈Z∗Relations (2a) and (2b) provide the time limits; i.e., the product of interval duration Pint and signal level Lερ cannot exceed the deadline Dερ for a function path ρε∈FPapp. That is because the task that needs receive signals can complete authentication only in the next interval after the signals are transmitted, and thus normally, the whole process of a path ρε must have a duration of Lερ intervals. In addition, the interval duration Pint cannot exceed the minimum value of the deadlines Djσ of signals σj∈Sapp, to ensure that each signal can be authenticated by the receiver before its deadline. Relation (2c) is bound to the alignment of the key signals and automotive control signals schedules; i.e., the interval duration Pint should be an integer multiple or factor of the greatest common divisor (gcd) of the periods of all the signals.


## 4. Security-Aware Scheduling

### 4.1. Problem Statement

The security-aware scheduling problem we are addressing in this paper can be formulated as follows. Given the system model, application model, and the security model generated by the authentication mechanism, we decide on the (a) packing of automotive control and authentication mechanism-related signals to messages, (b) scheduling of messages on FlexRay ST segment, and (c) scheduling of automotive control and authentication mechanism-related tasks on respective ECU, such that(i)
the deadline constraints and the precedence constraints caused by information passing between all tasks and signals are satisfied(ii)
the constraints related to FlexRay Protocol are satisfied(iii)
the objective function with respect to timing performance or extensibility is optimized


### 4.2. Motivational Examples

Let us illustrate the integrated scheduling problem using the setup from Figure1, where two automotive control applications are executed on the system consisting of four ECUs. The corresponding security applications are depicted in Figure 4. For simplicity, in this example we assume that the execution times of the hash function on all ECUs are 0.2 ms. The lengths of the communication cycle, ST segment, ST slot, and frame payload are 5 ms, 3.264 ms, 0.032 ms, and 16 bytes, respectively. There are 120 slots in the FlexRay ST segment. We assume that there are two time-sensitive paths, one from τ1 to τ5 with a deadline of 7.5 ms and the other from τ2 to τ8 with a deadline of 5 ms. According to (2a)-(2c), the interval duration Pint of key release is 2.5 ms.A straightforward solution to the security-aware scheduling problem is to (a) pack the signals generated by the same task into a frame and (b) schedule the key authentication-related tasks and frames first and then other tasks and frames using As-Soon-As-Possible (ASAP) scheduling (that is because an automotive control-related frame can be verified by its receiver only after the verification task for its MAC key is completed). For the example in Figure1, this solution is depicted by the Gantt chart in Figure 5(a). For simplicity, key signals σ1,2key,σ1,3key,σ1,4key,σ2,3key,σ2,4key are denoted by σ11-σ15, and key verification tasks τ1,2ver,τ1,3ver,τ1,4ver,τ2,3ver,τ2,4ver are denoted by τ9-τ13. In this solution, the automotive control signals σ1,σ2 are packed into frame f1,σ9,σ10 into f2 and σ3-σ8 into f3, and the key signals σ11-σ13 are packed into f4,σ14,σ15 into f5. In this case, the value of the laxity of time-sensitive function paths is 0.91 ms (the path from τ1 to τ5 misses its deadline) and the numbers of the used slot identifiers and slots are 7 and 12, respectively.Figure 5
Motivational examples.Figure5(b) illustrates an optimal solution with respect to timing performance. This solution increases the laxity of paths to 3.936 ms and satisfies the deadline constraints of both paths. On the other hand, Figure 5(c) illustrates an optimal solution with respect to extensibility, which reduces the number of the used slot identifiers and slots to 4 and 8, respectively, by packing signals to frames while satisfying the deadline constraints.


### 4.3. MILP-Based Optimization Scheduling Approach

We use an MILP formulation to find an optimal solution to the security-aware scheduling problem with respect to timing performance- or extensibility-related cost functions. In an MILP framework, the system is represented with constant parameters, decision variables, and constraints based on the parameters and variables. The objective function, defined over the same sets of parameters and variables, characterizes the optimal solution. MILPs can be solved very efficiently by various solvers. In this work, we employ the LINGO solver.


#### 4.3.1. Definitions

The notations of the elements and constant parameters were described in the previous definition of system model and security model. We assume these parameters are given as design inputs. The notations of the decision variables in the MILP formulation are listed in Table1.Table 1
The notations of binary variables and real variables.
Symbol Variable Type Implication x j , m binary variablea signalσj is packed into frame fm y j , m binary variable signalσj adds its length to frame fm z m , k , w binary variable framefm is packed into the k-th slot of the w-th cycle v g , k , w binary variable thek-th slot of the w-th cycle is owned by ECUeg v g , k binary variable thek-th slot is owned by ECU eg r m , g f binary variable ECUeg is the receiver of frame fm μ m , g f binary variable ECUeg executes authentication-related operations of frame fm θ m f binary variable framefm is not empty π m f binary variable framefm includes automotive control-related signals ϑ i , i ′ α , β binary variable theα-th instance of task τi starts earlier than the β-th instance of task τi′ δ g , m , m ′ α , β binary variable theα-th instance of frame fm starts earlier than the β-th instance of frame fm′ on ECU eg η g , i , m α , β binary variable theα-th instance of task τi starts earlier than the β-th instance of frame fm on ECU eg o i τ real variable the start time of taskτi o j σ real variable the start time of signalσj c j σ real variable the finish time of signalσj o m , g f real variable the start time of framefm on ECU eg o m , n f real variable the start time of framefm on FlexRay bus l m f real variable the length of framefm φ m f real variable the time interval in which the MAC key of framefm is released


#### 4.3.2. Constraints

In this section, we present the various constraints on frame packing, frame scheduling, task scheduling, data dependency, and end-to-end latency.(a) Frame Packing (3a) ∀ g , σ j ∈ S g , ∑ f m ∈ F g x j , m = 1 (3b) ∀ g , σ j ∈ S g , ∑ f m ∉ F g x j , m = 0 (3c) ∀ j , m , x j , m · R E m f ≤ P j σ (3d) ∀ m , ∀ σ j , σ j ′ ∈ S g , h , x j , m = x j ′ , m (3e) ∀ m , ∀ σ j ∈ S g , h , x j , m = ∑ σ j ′ ∈ S g , h y j ′ , mEquations (3a) and (3b) guarantee that the signal σj is packed into exactly one frame with the same type from the same ECU, where Sg and Fg denote the sets of the signals and frames from ECU eg, respectively. Constraint (3c) guarantees that the period of a signal is greater than or equal to the repetition of the frame into which the signal is packed. Equation (3d) ensures that each branch of a multicast signal is packed into the same frame. Equation (3e) ensures that exactly one branch of a multicast signal adds its length to the frame.(4a)∀m,j,xj,m≤μm,Sjσf(4b)∀m,j,xj,m≤μm,Rjσf(4c)∀m,g,μm,gf≤∑σj∈σj∈S∣Rjσ=egorSjσ=egxj,m(4d)∀m,∀σj∈Sapp,xj,m≤πmf(4e)∀m,πmf≤∑σj∈Sappxj,m(4f)∀m,θmf≤∑σj∈Sxj,m(4g)∀m,θmf≥∑σj∈Sxj,mMConstraints (4a)-(4c) guarantee that an ECU eg executes authentication-related operations on the frame fm only if there exists a signal σj packed into fm and eg is the sender or receiver of the signal. Constraints (4d) and (4e) ensure that a frame belongs to the application type only if there exists an automotive application-related signal packed into it. Constraints (4f)-(4g) ensure that a frame is not empty only if there exists a signal packed into it, where M is a large constant for linearization in this paper. (5a)∀m,lmf=∑σj∈Syj,m∙Ljσ+πmf∙LMAC(5b)∀m,lmf≤LframeEquation (5a) calculates the total length of the frame, including the data payload and the MAC length (that is only contained in the automotive control frame). Constraint (5b) ensures that the frame length does not exceed the limit Lframe allowed by FlexRay.(b) Frame Scheduling(i) Slot Assignment (6a) ∀ m , ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k ≤ 1 + M ∙ 1 - θ m f (6b) ∀ m , 1 - M ∙ 1 - θ m f ≤ ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k (6c) ∀ m , ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k ≤ M ∙ θ m f (6d) ∀ m , w , ∀ k ∈ 0 , … , R E m f - 1 , n r e p ∈ 0 , … , H R E m f ∙ L c y c l e - 1 z m , w , k = z m , w + n r e p ∙ R E m f , kConstraints (6a)-(6c) ensure that each nonempty frame is scheduled in exactly one slot at a specific base cycle. Constraint (6d) ensures that each frame fm multiplexes the assigned slot with repetition of REmf cycles.(ii) Slot Ownership (FlexRay 2.1) (7a) ∀ m , w , k , z m , w , k ≤ v T m f , k (7b) ∀ k , ∑ e g ∈ E v g , k ≤ 1 (7c) ∀ g , w , k , v g , k ≤ ∑ f m ∈ F z m , w , kFlexRay 2.1 has its requirement for the slot ownership. If a slot is owned by one ECU, then the ownership applies to every cycle. Constraint (7a) states that if a frame is mapped to a specific cycle and slot, then its source ECU must own the slot. Constraint (7b) ensures that every slot can be assigned to a most one ECU, and (7c) sets the slot ownership to null.(iii) Slot Ownership (FlexRay 3.0) (8a) ∀ m , w , k , z m , w , k ≤ v T m f , w , k (8b) ∀ w , k , ∑ e g ∈ E v g , w , k ≤ 1 (8c) ∀ g , w , k , v g , w , k ≤ ∑ f m ∈ F z m , w , kIn comparison to version 2.1 of the FlexRay protocol, FlexRay 3.0 standard introduces several changes on slot ownership, and it allows a slot to be shared among different ECUs in the form of cycle multiplexing for improving the utilization of the bus. Constraint (8a) ensures that if a frame is mapped to a specific cycle and slot, then the slot is assigned to its source ECU at this cycle. Constraint (8b) ensures that a slot at a specific cycle can be assigned to a most one ECU, and (8c) states that if there are no frames to be assigned to one slot of one cycle, then the ownership of the slot at this cycle is null.(iv) Timing-Related (9a) ∀ m , k , ∀ w ∈ 0 , … , R E m f , o m , n f ≤ w ∙ L c y c l e + k - 1 ∙ L s l o t + M ∙ 1 - z m , w , k (9b) ∀ m , k , ∀ w ∈ 0 , … , R E m f , w ∙ L c y c l e + k - 1 ∙ L s l o t - M ∙ 1 - z m , w , k ≤ o m , n f (9c) ∀ m , o m , n f ≤ M ∙ θ m f (9d) ∀ m , o m , T m f f + L T m f e ≤ o m , n f + M ∙ 1 - π m f (9e) ∀ m , g , o m , g f ≤ o m , n f + L s l o t + M ∙ 1 - r m , g f + M ∙ 1 - π m f (9f) ∀ m , g , o m , g f ≤ M ∙ μ m , g fConstraints (9a) and (9b) ensure that if a nonfull frame fm is packed into the k-th slot of the w-th cycle, its start time on FlexRay bus is equal to the start time of the slot. Constraints (9c) ensure that the start time and finish time of an empty frame on FlexRay bus are equal to zero. Constraint (9d) states that an automotive control frame fm must be signed by its sender before being sent out, where LTmfe denotes the execution time of the selected MAC computation function on its sender Tmf. And (9e) ensures that the frame fm must be verified after the reception of itself. Constraint (9f) ensures that the start time of a frame on its unused ECU (i.e., neither its sender nor its receiver) is equal to zero.(10a)∀j,m,ojσ-M∙1-xj,m≤om,Tjσf(10b)∀j,m,om,Tjσf≤ojσ+M∙1-xj,m(10c)∀σj∈Sapp,∀m,cjσ-M∙1-xj,m≤om,Rjσf+LRjσe(10d)∀σj∈Sapp,∀m,om,Rjσf+LRjσe≤cjσ+M∙1-xj,m(10e)∀σj∈Ssec,∀m,cjσ-M∙1-xj,m≤om,nf+Lslot(10f)∀σj∈Ssec,∀m,om,nf+Lslot≤cjσ+M∙1-xj,m(10g)∀σj∈Sapp,cjσ≤DjσConstraints (10a) and (10b) guarantee that the start time ojσ of a signal σj equals the start time om,Tjσf of the frame fm into which the signal is packed on its sender Tjσ. Similarly, (10c) and (10d) guarantee that the finish time cjσ of an automotive control signal σj∈Sapp equals the finish time om,Rjσf+LRjσe of the frame fm into which the signal is packed on its receiver. Given that the key signal σj∈Ssec is not required to have a MAC verification processing, (10e) and (10f) guarantee that its finish time cjσ equals the finish time om,nf+Lslot of the frame fm into which it is packed on the FlexRay bus. And (10g) specifies that the finish time of each automotive control signal is within its deadline.(11)∀g,∀fm,fm′,m≠m′,α∈0,…,lcm⁡REmf,REm′fREmf-1,β∈0,…,lcm⁡REmf,REm′fREm′f-1(12a)α∙REmf+om,gf+Lge≤β∙REm′f+om′,gf+M∙1-δg,m,m′α,β+M∙1-μm,gf+M∙1-μm′,gf(12b)β∙REm′f+om′,gf+Lge≤α∙REmf+om,gf+M∙δg,m,m′α,β+M∙1-μm,gf+M∙1-μm′,gfIn the final of this part, constraints (12a) and (12b) ensure that the authentication-related operations of two frames do not overlap on any ECU. The variable δg,m,m′α,β is used for switching; i.e., one of (12a) or (12b) is trivially satisfied depending on δg,m,m′α,β.(c) Task Scheduling (13a) ∀ τ i ∈ Γ a p p , o i τ + L i τ ≤ D i τ (14) ∀ g , ∀ τ i , τ i ′ ∈ Γ g , i ≠ i ′ , α ∈ 0 , … , lcm ⁡ P i τ , P i ′ τ P i τ - 1 , β ∈ 0 , … , lcm ⁡ P i τ , P i ′ τ P i ′ τ - 1 (14b) α ∙ P i τ + o i τ + L i τ ≤ β ∙ T i ′ τ + o i ′ τ + M ∙ 1 - ϑ i , i ′ α , β (14c) β ∙ T i ′ τ + o i ′ τ + L i ′ τ ≤ α ∙ P i τ + o i τ + M ∙ ϑ i , i ′ α , βConstraint (13a) determines that the finish time of a task τi, i.e., the sum of its start time oiτ and execution time Liτ, is within its deadline. Constraints (14b) and (14c) ensure that two tasks do not overlap on any ECU, where the variable ϑi,i′α,β is used for switching.(d) Data Dependency (15a) ∀ λ r ∈ Λ s e c U Λ a p p , σ j , τ i ∈ G r a p p , c j σ ≤ o i τ (15b) ∀ λ r ∈ Λ a p p , τ i , σ j ∈ G r a p p , o i τ + L i τ ≤ o j σConstraints (15a) and (15b) guarantee that the predecessor must complete its execution before all its successors start in an automotive control or key authentication application.(16a)∀m,φmf=om,TmffPint(16b)∀m,om,nf+LslotPint≤φmf(16c)∀g,∀τi∈Γgsec∣Viτ=Tmf,om,gf≥oiτ+Liτ+φmf∙Pint+M∙1-rm,gf+M∙1-πmfAccording to the authentication mechanism, an automotive control frame is accepted and stored awaiting to be authenticated by its receiver only when the key used to generate its MAC remains secret; i.e., the sender has not reached the time interval for releasing this key. Since the key is defined to be released in its corresponding next time interval, the transmission of each frame must be completed before the start of the next interval. Therefore, for a framefm, (16a) first computes the number of the time interval φmf in which its MAC key is released. And then, (16b) guarantees that the start time of a frame on its sender and its finish time on the FlexRay bus belong to the same time interval.Besides, an automotive control frame will be available to its receiver after the verification task for its MAC key is completed. Therefore, (16c) guarantees that the start time of an automotive control frame on its receiver must be later than the finish time of the verification task for its MAC key, where Γgsec denotes the set of the key verification tasks executed on ECU eg.(17)∀g,m,∀τi∈Γg,α∈0,…,lcm⁡Piτ,REmfPiτ-1,β∈0,…,lcm⁡Piτ,REmfREmf-1(18a)α∙Piτ+oiτ+Liτ≤β∙REmf+om,gf+M∙1-ηg,i,mα,β+M∙1-μm,gf+M∙1-θmf(18b)β∙REmf+om,gf+Lge≤α∙Piτ+oiτ+M∙ηg,i,mα,β+M∙1-μm,gf+M∙1-θmfConstraints (18a) and (18b) ensure that the authentication-related operations of the frames and the other tasks do not overlap on any ECU resource, where the variable ηg,i,mα,β is used for switching.(e) End-to-End Latency (19) ∀ ρ ε ∈ F P a p p , c D e s ε ρ τ - o S r c ε ρ τ ≤ D ε ρConstraint (19) ensures that the end-to-end delay must be less than the deadline for each function path, where Desερ and Srcερ are the source and sink object of the function path ρε∈FPapp, respectively.


#### 4.3.3. Objective Functions

Subject to the above constraints, we can seek optimality with respect to different cost functions. A quite important objective, related to timing performance, is to maximize the laxity (difference between deadlines and response times) among all latency-sensitive function paths:(20)Maximize∑ρε∈FPappDερ+oSrcερτ-cDesερτWe can alternatively minimize the consumption of network bandwidth, therefore improving extensibility. For FlexRay 2.1, an important objective related to extensibility is to minimize the number of the used slot identifiers:(21a)Minimize∑eg∈E∑kvg,kFor FlexRay 3.0, the objective is to minimize the number of the used slots:(21b)Minimize∑eg∈E∑w∑kvg,w,k


## 4.1. Problem Statement

The security-aware scheduling problem we are addressing in this paper can be formulated as follows. Given the system model, application model, and the security model generated by the authentication mechanism, we decide on the (a) packing of automotive control and authentication mechanism-related signals to messages, (b) scheduling of messages on FlexRay ST segment, and (c) scheduling of automotive control and authentication mechanism-related tasks on respective ECU, such that(i)
the deadline constraints and the precedence constraints caused by information passing between all tasks and signals are satisfied(ii)
the constraints related to FlexRay Protocol are satisfied(iii)
the objective function with respect to timing performance or extensibility is optimized


## 4.2. Motivational Examples

Let us illustrate the integrated scheduling problem using the setup from Figure1, where two automotive control applications are executed on the system consisting of four ECUs. The corresponding security applications are depicted in Figure 4. For simplicity, in this example we assume that the execution times of the hash function on all ECUs are 0.2 ms. The lengths of the communication cycle, ST segment, ST slot, and frame payload are 5 ms, 3.264 ms, 0.032 ms, and 16 bytes, respectively. There are 120 slots in the FlexRay ST segment. We assume that there are two time-sensitive paths, one from τ1 to τ5 with a deadline of 7.5 ms and the other from τ2 to τ8 with a deadline of 5 ms. According to (2a)-(2c), the interval duration Pint of key release is 2.5 ms.A straightforward solution to the security-aware scheduling problem is to (a) pack the signals generated by the same task into a frame and (b) schedule the key authentication-related tasks and frames first and then other tasks and frames using As-Soon-As-Possible (ASAP) scheduling (that is because an automotive control-related frame can be verified by its receiver only after the verification task for its MAC key is completed). For the example in Figure1, this solution is depicted by the Gantt chart in Figure 5(a). For simplicity, key signals σ1,2key,σ1,3key,σ1,4key,σ2,3key,σ2,4key are denoted by σ11-σ15, and key verification tasks τ1,2ver,τ1,3ver,τ1,4ver,τ2,3ver,τ2,4ver are denoted by τ9-τ13. In this solution, the automotive control signals σ1,σ2 are packed into frame f1,σ9,σ10 into f2 and σ3-σ8 into f3, and the key signals σ11-σ13 are packed into f4,σ14,σ15 into f5. In this case, the value of the laxity of time-sensitive function paths is 0.91 ms (the path from τ1 to τ5 misses its deadline) and the numbers of the used slot identifiers and slots are 7 and 12, respectively.Figure 5
Motivational examples.Figure5(b) illustrates an optimal solution with respect to timing performance. This solution increases the laxity of paths to 3.936 ms and satisfies the deadline constraints of both paths. On the other hand, Figure 5(c) illustrates an optimal solution with respect to extensibility, which reduces the number of the used slot identifiers and slots to 4 and 8, respectively, by packing signals to frames while satisfying the deadline constraints.


## 4.3. MILP-Based Optimization Scheduling Approach

We use an MILP formulation to find an optimal solution to the security-aware scheduling problem with respect to timing performance- or extensibility-related cost functions. In an MILP framework, the system is represented with constant parameters, decision variables, and constraints based on the parameters and variables. The objective function, defined over the same sets of parameters and variables, characterizes the optimal solution. MILPs can be solved very efficiently by various solvers. In this work, we employ the LINGO solver.


### 4.3.1. Definitions

The notations of the elements and constant parameters were described in the previous definition of system model and security model. We assume these parameters are given as design inputs. The notations of the decision variables in the MILP formulation are listed in Table1.Table 1
The notations of binary variables and real variables.
Symbol Variable Type Implication x j , m binary variablea signalσj is packed into frame fm y j , m binary variable signalσj adds its length to frame fm z m , k , w binary variable framefm is packed into the k-th slot of the w-th cycle v g , k , w binary variable thek-th slot of the w-th cycle is owned by ECUeg v g , k binary variable thek-th slot is owned by ECU eg r m , g f binary variable ECUeg is the receiver of frame fm μ m , g f binary variable ECUeg executes authentication-related operations of frame fm θ m f binary variable framefm is not empty π m f binary variable framefm includes automotive control-related signals ϑ i , i ′ α , β binary variable theα-th instance of task τi starts earlier than the β-th instance of task τi′ δ g , m , m ′ α , β binary variable theα-th instance of frame fm starts earlier than the β-th instance of frame fm′ on ECU eg η g , i , m α , β binary variable theα-th instance of task τi starts earlier than the β-th instance of frame fm on ECU eg o i τ real variable the start time of taskτi o j σ real variable the start time of signalσj c j σ real variable the finish time of signalσj o m , g f real variable the start time of framefm on ECU eg o m , n f real variable the start time of framefm on FlexRay bus l m f real variable the length of framefm φ m f real variable the time interval in which the MAC key of framefm is released


### 4.3.2. Constraints

In this section, we present the various constraints on frame packing, frame scheduling, task scheduling, data dependency, and end-to-end latency.(a) Frame Packing (3a) ∀ g , σ j ∈ S g , ∑ f m ∈ F g x j , m = 1 (3b) ∀ g , σ j ∈ S g , ∑ f m ∉ F g x j , m = 0 (3c) ∀ j , m , x j , m · R E m f ≤ P j σ (3d) ∀ m , ∀ σ j , σ j ′ ∈ S g , h , x j , m = x j ′ , m (3e) ∀ m , ∀ σ j ∈ S g , h , x j , m = ∑ σ j ′ ∈ S g , h y j ′ , mEquations (3a) and (3b) guarantee that the signal σj is packed into exactly one frame with the same type from the same ECU, where Sg and Fg denote the sets of the signals and frames from ECU eg, respectively. Constraint (3c) guarantees that the period of a signal is greater than or equal to the repetition of the frame into which the signal is packed. Equation (3d) ensures that each branch of a multicast signal is packed into the same frame. Equation (3e) ensures that exactly one branch of a multicast signal adds its length to the frame.(4a)∀m,j,xj,m≤μm,Sjσf(4b)∀m,j,xj,m≤μm,Rjσf(4c)∀m,g,μm,gf≤∑σj∈σj∈S∣Rjσ=egorSjσ=egxj,m(4d)∀m,∀σj∈Sapp,xj,m≤πmf(4e)∀m,πmf≤∑σj∈Sappxj,m(4f)∀m,θmf≤∑σj∈Sxj,m(4g)∀m,θmf≥∑σj∈Sxj,mMConstraints (4a)-(4c) guarantee that an ECU eg executes authentication-related operations on the frame fm only if there exists a signal σj packed into fm and eg is the sender or receiver of the signal. Constraints (4d) and (4e) ensure that a frame belongs to the application type only if there exists an automotive application-related signal packed into it. Constraints (4f)-(4g) ensure that a frame is not empty only if there exists a signal packed into it, where M is a large constant for linearization in this paper. (5a)∀m,lmf=∑σj∈Syj,m∙Ljσ+πmf∙LMAC(5b)∀m,lmf≤LframeEquation (5a) calculates the total length of the frame, including the data payload and the MAC length (that is only contained in the automotive control frame). Constraint (5b) ensures that the frame length does not exceed the limit Lframe allowed by FlexRay.(b) Frame Scheduling(i) Slot Assignment (6a) ∀ m , ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k ≤ 1 + M ∙ 1 - θ m f (6b) ∀ m , 1 - M ∙ 1 - θ m f ≤ ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k (6c) ∀ m , ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k ≤ M ∙ θ m f (6d) ∀ m , w , ∀ k ∈ 0 , … , R E m f - 1 , n r e p ∈ 0 , … , H R E m f ∙ L c y c l e - 1 z m , w , k = z m , w + n r e p ∙ R E m f , kConstraints (6a)-(6c) ensure that each nonempty frame is scheduled in exactly one slot at a specific base cycle. Constraint (6d) ensures that each frame fm multiplexes the assigned slot with repetition of REmf cycles.(ii) Slot Ownership (FlexRay 2.1) (7a) ∀ m , w , k , z m , w , k ≤ v T m f , k (7b) ∀ k , ∑ e g ∈ E v g , k ≤ 1 (7c) ∀ g , w , k , v g , k ≤ ∑ f m ∈ F z m , w , kFlexRay 2.1 has its requirement for the slot ownership. If a slot is owned by one ECU, then the ownership applies to every cycle. Constraint (7a) states that if a frame is mapped to a specific cycle and slot, then its source ECU must own the slot. Constraint (7b) ensures that every slot can be assigned to a most one ECU, and (7c) sets the slot ownership to null.(iii) Slot Ownership (FlexRay 3.0) (8a) ∀ m , w , k , z m , w , k ≤ v T m f , w , k (8b) ∀ w , k , ∑ e g ∈ E v g , w , k ≤ 1 (8c) ∀ g , w , k , v g , w , k ≤ ∑ f m ∈ F z m , w , kIn comparison to version 2.1 of the FlexRay protocol, FlexRay 3.0 standard introduces several changes on slot ownership, and it allows a slot to be shared among different ECUs in the form of cycle multiplexing for improving the utilization of the bus. Constraint (8a) ensures that if a frame is mapped to a specific cycle and slot, then the slot is assigned to its source ECU at this cycle. Constraint (8b) ensures that a slot at a specific cycle can be assigned to a most one ECU, and (8c) states that if there are no frames to be assigned to one slot of one cycle, then the ownership of the slot at this cycle is null.(iv) Timing-Related (9a) ∀ m , k , ∀ w ∈ 0 , … , R E m f , o m , n f ≤ w ∙ L c y c l e + k - 1 ∙ L s l o t + M ∙ 1 - z m , w , k (9b) ∀ m , k , ∀ w ∈ 0 , … , R E m f , w ∙ L c y c l e + k - 1 ∙ L s l o t - M ∙ 1 - z m , w , k ≤ o m , n f (9c) ∀ m , o m , n f ≤ M ∙ θ m f (9d) ∀ m , o m , T m f f + L T m f e ≤ o m , n f + M ∙ 1 - π m f (9e) ∀ m , g , o m , g f ≤ o m , n f + L s l o t + M ∙ 1 - r m , g f + M ∙ 1 - π m f (9f) ∀ m , g , o m , g f ≤ M ∙ μ m , g fConstraints (9a) and (9b) ensure that if a nonfull frame fm is packed into the k-th slot of the w-th cycle, its start time on FlexRay bus is equal to the start time of the slot. Constraints (9c) ensure that the start time and finish time of an empty frame on FlexRay bus are equal to zero. Constraint (9d) states that an automotive control frame fm must be signed by its sender before being sent out, where LTmfe denotes the execution time of the selected MAC computation function on its sender Tmf. And (9e) ensures that the frame fm must be verified after the reception of itself. Constraint (9f) ensures that the start time of a frame on its unused ECU (i.e., neither its sender nor its receiver) is equal to zero.(10a)∀j,m,ojσ-M∙1-xj,m≤om,Tjσf(10b)∀j,m,om,Tjσf≤ojσ+M∙1-xj,m(10c)∀σj∈Sapp,∀m,cjσ-M∙1-xj,m≤om,Rjσf+LRjσe(10d)∀σj∈Sapp,∀m,om,Rjσf+LRjσe≤cjσ+M∙1-xj,m(10e)∀σj∈Ssec,∀m,cjσ-M∙1-xj,m≤om,nf+Lslot(10f)∀σj∈Ssec,∀m,om,nf+Lslot≤cjσ+M∙1-xj,m(10g)∀σj∈Sapp,cjσ≤DjσConstraints (10a) and (10b) guarantee that the start time ojσ of a signal σj equals the start time om,Tjσf of the frame fm into which the signal is packed on its sender Tjσ. Similarly, (10c) and (10d) guarantee that the finish time cjσ of an automotive control signal σj∈Sapp equals the finish time om,Rjσf+LRjσe of the frame fm into which the signal is packed on its receiver. Given that the key signal σj∈Ssec is not required to have a MAC verification processing, (10e) and (10f) guarantee that its finish time cjσ equals the finish time om,nf+Lslot of the frame fm into which it is packed on the FlexRay bus. And (10g) specifies that the finish time of each automotive control signal is within its deadline.(11)∀g,∀fm,fm′,m≠m′,α∈0,…,lcm⁡REmf,REm′fREmf-1,β∈0,…,lcm⁡REmf,REm′fREm′f-1(12a)α∙REmf+om,gf+Lge≤β∙REm′f+om′,gf+M∙1-δg,m,m′α,β+M∙1-μm,gf+M∙1-μm′,gf(12b)β∙REm′f+om′,gf+Lge≤α∙REmf+om,gf+M∙δg,m,m′α,β+M∙1-μm,gf+M∙1-μm′,gfIn the final of this part, constraints (12a) and (12b) ensure that the authentication-related operations of two frames do not overlap on any ECU. The variable δg,m,m′α,β is used for switching; i.e., one of (12a) or (12b) is trivially satisfied depending on δg,m,m′α,β.(c) Task Scheduling (13a) ∀ τ i ∈ Γ a p p , o i τ + L i τ ≤ D i τ (14) ∀ g , ∀ τ i , τ i ′ ∈ Γ g , i ≠ i ′ , α ∈ 0 , … , lcm ⁡ P i τ , P i ′ τ P i τ - 1 , β ∈ 0 , … , lcm ⁡ P i τ , P i ′ τ P i ′ τ - 1 (14b) α ∙ P i τ + o i τ + L i τ ≤ β ∙ T i ′ τ + o i ′ τ + M ∙ 1 - ϑ i , i ′ α , β (14c) β ∙ T i ′ τ + o i ′ τ + L i ′ τ ≤ α ∙ P i τ + o i τ + M ∙ ϑ i , i ′ α , βConstraint (13a) determines that the finish time of a task τi, i.e., the sum of its start time oiτ and execution time Liτ, is within its deadline. Constraints (14b) and (14c) ensure that two tasks do not overlap on any ECU, where the variable ϑi,i′α,β is used for switching.(d) Data Dependency (15a) ∀ λ r ∈ Λ s e c U Λ a p p , σ j , τ i ∈ G r a p p , c j σ ≤ o i τ (15b) ∀ λ r ∈ Λ a p p , τ i , σ j ∈ G r a p p , o i τ + L i τ ≤ o j σConstraints (15a) and (15b) guarantee that the predecessor must complete its execution before all its successors start in an automotive control or key authentication application.(16a)∀m,φmf=om,TmffPint(16b)∀m,om,nf+LslotPint≤φmf(16c)∀g,∀τi∈Γgsec∣Viτ=Tmf,om,gf≥oiτ+Liτ+φmf∙Pint+M∙1-rm,gf+M∙1-πmfAccording to the authentication mechanism, an automotive control frame is accepted and stored awaiting to be authenticated by its receiver only when the key used to generate its MAC remains secret; i.e., the sender has not reached the time interval for releasing this key. Since the key is defined to be released in its corresponding next time interval, the transmission of each frame must be completed before the start of the next interval. Therefore, for a framefm, (16a) first computes the number of the time interval φmf in which its MAC key is released. And then, (16b) guarantees that the start time of a frame on its sender and its finish time on the FlexRay bus belong to the same time interval.Besides, an automotive control frame will be available to its receiver after the verification task for its MAC key is completed. Therefore, (16c) guarantees that the start time of an automotive control frame on its receiver must be later than the finish time of the verification task for its MAC key, where Γgsec denotes the set of the key verification tasks executed on ECU eg.(17)∀g,m,∀τi∈Γg,α∈0,…,lcm⁡Piτ,REmfPiτ-1,β∈0,…,lcm⁡Piτ,REmfREmf-1(18a)α∙Piτ+oiτ+Liτ≤β∙REmf+om,gf+M∙1-ηg,i,mα,β+M∙1-μm,gf+M∙1-θmf(18b)β∙REmf+om,gf+Lge≤α∙Piτ+oiτ+M∙ηg,i,mα,β+M∙1-μm,gf+M∙1-θmfConstraints (18a) and (18b) ensure that the authentication-related operations of the frames and the other tasks do not overlap on any ECU resource, where the variable ηg,i,mα,β is used for switching.(e) End-to-End Latency (19) ∀ ρ ε ∈ F P a p p , c D e s ε ρ τ - o S r c ε ρ τ ≤ D ε ρConstraint (19) ensures that the end-to-end delay must be less than the deadline for each function path, where Desερ and Srcερ are the source and sink object of the function path ρε∈FPapp, respectively.


### 4.3.3. Objective Functions

Subject to the above constraints, we can seek optimality with respect to different cost functions. A quite important objective, related to timing performance, is to maximize the laxity (difference between deadlines and response times) among all latency-sensitive function paths:(20)Maximize∑ρε∈FPappDερ+oSrcερτ-cDesερτWe can alternatively minimize the consumption of network bandwidth, therefore improving extensibility. For FlexRay 2.1, an important objective related to extensibility is to minimize the number of the used slot identifiers:(21a)Minimize∑eg∈E∑kvg,kFor FlexRay 3.0, the objective is to minimize the number of the used slots:(21b)Minimize∑eg∈E∑w∑kvg,w,k


## 4.3.1. Definitions

The notations of the elements and constant parameters were described in the previous definition of system model and security model. We assume these parameters are given as design inputs. The notations of the decision variables in the MILP formulation are listed in Table1.Table 1
The notations of binary variables and real variables.
Symbol Variable Type Implication x j , m binary variablea signalσj is packed into frame fm y j , m binary variable signalσj adds its length to frame fm z m , k , w binary variable framefm is packed into the k-th slot of the w-th cycle v g , k , w binary variable thek-th slot of the w-th cycle is owned by ECUeg v g , k binary variable thek-th slot is owned by ECU eg r m , g f binary variable ECUeg is the receiver of frame fm μ m , g f binary variable ECUeg executes authentication-related operations of frame fm θ m f binary variable framefm is not empty π m f binary variable framefm includes automotive control-related signals ϑ i , i ′ α , β binary variable theα-th instance of task τi starts earlier than the β-th instance of task τi′ δ g , m , m ′ α , β binary variable theα-th instance of frame fm starts earlier than the β-th instance of frame fm′ on ECU eg η g , i , m α , β binary variable theα-th instance of task τi starts earlier than the β-th instance of frame fm on ECU eg o i τ real variable the start time of taskτi o j σ real variable the start time of signalσj c j σ real variable the finish time of signalσj o m , g f real variable the start time of framefm on ECU eg o m , n f real variable the start time of framefm on FlexRay bus l m f real variable the length of framefm φ m f real variable the time interval in which the MAC key of framefm is released


## 4.3.2. Constraints

In this section, we present the various constraints on frame packing, frame scheduling, task scheduling, data dependency, and end-to-end latency.(a) Frame Packing (3a) ∀ g , σ j ∈ S g , ∑ f m ∈ F g x j , m = 1 (3b) ∀ g , σ j ∈ S g , ∑ f m ∉ F g x j , m = 0 (3c) ∀ j , m , x j , m · R E m f ≤ P j σ (3d) ∀ m , ∀ σ j , σ j ′ ∈ S g , h , x j , m = x j ′ , m (3e) ∀ m , ∀ σ j ∈ S g , h , x j , m = ∑ σ j ′ ∈ S g , h y j ′ , mEquations (3a) and (3b) guarantee that the signal σj is packed into exactly one frame with the same type from the same ECU, where Sg and Fg denote the sets of the signals and frames from ECU eg, respectively. Constraint (3c) guarantees that the period of a signal is greater than or equal to the repetition of the frame into which the signal is packed. Equation (3d) ensures that each branch of a multicast signal is packed into the same frame. Equation (3e) ensures that exactly one branch of a multicast signal adds its length to the frame.(4a)∀m,j,xj,m≤μm,Sjσf(4b)∀m,j,xj,m≤μm,Rjσf(4c)∀m,g,μm,gf≤∑σj∈σj∈S∣Rjσ=egorSjσ=egxj,m(4d)∀m,∀σj∈Sapp,xj,m≤πmf(4e)∀m,πmf≤∑σj∈Sappxj,m(4f)∀m,θmf≤∑σj∈Sxj,m(4g)∀m,θmf≥∑σj∈Sxj,mMConstraints (4a)-(4c) guarantee that an ECU eg executes authentication-related operations on the frame fm only if there exists a signal σj packed into fm and eg is the sender or receiver of the signal. Constraints (4d) and (4e) ensure that a frame belongs to the application type only if there exists an automotive application-related signal packed into it. Constraints (4f)-(4g) ensure that a frame is not empty only if there exists a signal packed into it, where M is a large constant for linearization in this paper. (5a)∀m,lmf=∑σj∈Syj,m∙Ljσ+πmf∙LMAC(5b)∀m,lmf≤LframeEquation (5a) calculates the total length of the frame, including the data payload and the MAC length (that is only contained in the automotive control frame). Constraint (5b) ensures that the frame length does not exceed the limit Lframe allowed by FlexRay.(b) Frame Scheduling(i) Slot Assignment (6a) ∀ m , ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k ≤ 1 + M ∙ 1 - θ m f (6b) ∀ m , 1 - M ∙ 1 - θ m f ≤ ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k (6c) ∀ m , ∑ w ∈ 0 , … , R E m f - 1 ∑ k ∈ 1 , … , n s l o t z m , w , k ≤ M ∙ θ m f (6d) ∀ m , w , ∀ k ∈ 0 , … , R E m f - 1 , n r e p ∈ 0 , … , H R E m f ∙ L c y c l e - 1 z m , w , k = z m , w + n r e p ∙ R E m f , kConstraints (6a)-(6c) ensure that each nonempty frame is scheduled in exactly one slot at a specific base cycle. Constraint (6d) ensures that each frame fm multiplexes the assigned slot with repetition of REmf cycles.(ii) Slot Ownership (FlexRay 2.1) (7a) ∀ m , w , k , z m , w , k ≤ v T m f , k (7b) ∀ k , ∑ e g ∈ E v g , k ≤ 1 (7c) ∀ g , w , k , v g , k ≤ ∑ f m ∈ F z m , w , kFlexRay 2.1 has its requirement for the slot ownership. If a slot is owned by one ECU, then the ownership applies to every cycle. Constraint (7a) states that if a frame is mapped to a specific cycle and slot, then its source ECU must own the slot. Constraint (7b) ensures that every slot can be assigned to a most one ECU, and (7c) sets the slot ownership to null.(iii) Slot Ownership (FlexRay 3.0) (8a) ∀ m , w , k , z m , w , k ≤ v T m f , w , k (8b) ∀ w , k , ∑ e g ∈ E v g , w , k ≤ 1 (8c) ∀ g , w , k , v g , w , k ≤ ∑ f m ∈ F z m , w , kIn comparison to version 2.1 of the FlexRay protocol, FlexRay 3.0 standard introduces several changes on slot ownership, and it allows a slot to be shared among different ECUs in the form of cycle multiplexing for improving the utilization of the bus. Constraint (8a) ensures that if a frame is mapped to a specific cycle and slot, then the slot is assigned to its source ECU at this cycle. Constraint (8b) ensures that a slot at a specific cycle can be assigned to a most one ECU, and (8c) states that if there are no frames to be assigned to one slot of one cycle, then the ownership of the slot at this cycle is null.(iv) Timing-Related (9a) ∀ m , k , ∀ w ∈ 0 , … , R E m f , o m , n f ≤ w ∙ L c y c l e + k - 1 ∙ L s l o t + M ∙ 1 - z m , w , k (9b) ∀ m , k , ∀ w ∈ 0 , … , R E m f , w ∙ L c y c l e + k - 1 ∙ L s l o t - M ∙ 1 - z m , w , k ≤ o m , n f (9c) ∀ m , o m , n f ≤ M ∙ θ m f (9d) ∀ m , o m , T m f f + L T m f e ≤ o m , n f + M ∙ 1 - π m f (9e) ∀ m , g , o m , g f ≤ o m , n f + L s l o t + M ∙ 1 - r m , g f + M ∙ 1 - π m f (9f) ∀ m , g , o m , g f ≤ M ∙ μ m , g fConstraints (9a) and (9b) ensure that if a nonfull frame fm is packed into the k-th slot of the w-th cycle, its start time on FlexRay bus is equal to the start time of the slot. Constraints (9c) ensure that the start time and finish time of an empty frame on FlexRay bus are equal to zero. Constraint (9d) states that an automotive control frame fm must be signed by its sender before being sent out, where LTmfe denotes the execution time of the selected MAC computation function on its sender Tmf. And (9e) ensures that the frame fm must be verified after the reception of itself. Constraint (9f) ensures that the start time of a frame on its unused ECU (i.e., neither its sender nor its receiver) is equal to zero.(10a)∀j,m,ojσ-M∙1-xj,m≤om,Tjσf(10b)∀j,m,om,Tjσf≤ojσ+M∙1-xj,m(10c)∀σj∈Sapp,∀m,cjσ-M∙1-xj,m≤om,Rjσf+LRjσe(10d)∀σj∈Sapp,∀m,om,Rjσf+LRjσe≤cjσ+M∙1-xj,m(10e)∀σj∈Ssec,∀m,cjσ-M∙1-xj,m≤om,nf+Lslot(10f)∀σj∈Ssec,∀m,om,nf+Lslot≤cjσ+M∙1-xj,m(10g)∀σj∈Sapp,cjσ≤DjσConstraints (10a) and (10b) guarantee that the start time ojσ of a signal σj equals the start time om,Tjσf of the frame fm into which the signal is packed on its sender Tjσ. Similarly, (10c) and (10d) guarantee that the finish time cjσ of an automotive control signal σj∈Sapp equals the finish time om,Rjσf+LRjσe of the frame fm into which the signal is packed on its receiver. Given that the key signal σj∈Ssec is not required to have a MAC verification processing, (10e) and (10f) guarantee that its finish time cjσ equals the finish time om,nf+Lslot of the frame fm into which it is packed on the FlexRay bus. And (10g) specifies that the finish time of each automotive control signal is within its deadline.(11)∀g,∀fm,fm′,m≠m′,α∈0,…,lcm⁡REmf,REm′fREmf-1,β∈0,…,lcm⁡REmf,REm′fREm′f-1(12a)α∙REmf+om,gf+Lge≤β∙REm′f+om′,gf+M∙1-δg,m,m′α,β+M∙1-μm,gf+M∙1-μm′,gf(12b)β∙REm′f+om′,gf+Lge≤α∙REmf+om,gf+M∙δg,m,m′α,β+M∙1-μm,gf+M∙1-μm′,gfIn the final of this part, constraints (12a) and (12b) ensure that the authentication-related operations of two frames do not overlap on any ECU. The variable δg,m,m′α,β is used for switching; i.e., one of (12a) or (12b) is trivially satisfied depending on δg,m,m′α,β.(c) Task Scheduling (13a) ∀ τ i ∈ Γ a p p , o i τ + L i τ ≤ D i τ (14) ∀ g , ∀ τ i , τ i ′ ∈ Γ g , i ≠ i ′ , α ∈ 0 , … , lcm ⁡ P i τ , P i ′ τ P i τ - 1 , β ∈ 0 , … , lcm ⁡ P i τ , P i ′ τ P i ′ τ - 1 (14b) α ∙ P i τ + o i τ + L i τ ≤ β ∙ T i ′ τ + o i ′ τ + M ∙ 1 - ϑ i , i ′ α , β (14c) β ∙ T i ′ τ + o i ′ τ + L i ′ τ ≤ α ∙ P i τ + o i τ + M ∙ ϑ i , i ′ α , βConstraint (13a) determines that the finish time of a task τi, i.e., the sum of its start time oiτ and execution time Liτ, is within its deadline. Constraints (14b) and (14c) ensure that two tasks do not overlap on any ECU, where the variable ϑi,i′α,β is used for switching.(d) Data Dependency (15a) ∀ λ r ∈ Λ s e c U Λ a p p , σ j , τ i ∈ G r a p p , c j σ ≤ o i τ (15b) ∀ λ r ∈ Λ a p p , τ i , σ j ∈ G r a p p , o i τ + L i τ ≤ o j σConstraints (15a) and (15b) guarantee that the predecessor must complete its execution before all its successors start in an automotive control or key authentication application.(16a)∀m,φmf=om,TmffPint(16b)∀m,om,nf+LslotPint≤φmf(16c)∀g,∀τi∈Γgsec∣Viτ=Tmf,om,gf≥oiτ+Liτ+φmf∙Pint+M∙1-rm,gf+M∙1-πmfAccording to the authentication mechanism, an automotive control frame is accepted and stored awaiting to be authenticated by its receiver only when the key used to generate its MAC remains secret; i.e., the sender has not reached the time interval for releasing this key. Since the key is defined to be released in its corresponding next time interval, the transmission of each frame must be completed before the start of the next interval. Therefore, for a framefm, (16a) first computes the number of the time interval φmf in which its MAC key is released. And then, (16b) guarantees that the start time of a frame on its sender and its finish time on the FlexRay bus belong to the same time interval.Besides, an automotive control frame will be available to its receiver after the verification task for its MAC key is completed. Therefore, (16c) guarantees that the start time of an automotive control frame on its receiver must be later than the finish time of the verification task for its MAC key, where Γgsec denotes the set of the key verification tasks executed on ECU eg.(17)∀g,m,∀τi∈Γg,α∈0,…,lcm⁡Piτ,REmfPiτ-1,β∈0,…,lcm⁡Piτ,REmfREmf-1(18a)α∙Piτ+oiτ+Liτ≤β∙REmf+om,gf+M∙1-ηg,i,mα,β+M∙1-μm,gf+M∙1-θmf(18b)β∙REmf+om,gf+Lge≤α∙Piτ+oiτ+M∙ηg,i,mα,β+M∙1-μm,gf+M∙1-θmfConstraints (18a) and (18b) ensure that the authentication-related operations of the frames and the other tasks do not overlap on any ECU resource, where the variable ηg,i,mα,β is used for switching.(e) End-to-End Latency (19) ∀ ρ ε ∈ F P a p p , c D e s ε ρ τ - o S r c ε ρ τ ≤ D ε ρConstraint (19) ensures that the end-to-end delay must be less than the deadline for each function path, where Desερ and Srcερ are the source and sink object of the function path ρε∈FPapp, respectively.


## 4.3.3. Objective Functions

Subject to the above constraints, we can seek optimality with respect to different cost functions. A quite important objective, related to timing performance, is to maximize the laxity (difference between deadlines and response times) among all latency-sensitive function paths:(20)Maximize∑ρε∈FPappDερ+oSrcερτ-cDesερτWe can alternatively minimize the consumption of network bandwidth, therefore improving extensibility. For FlexRay 2.1, an important objective related to extensibility is to minimize the number of the used slot identifiers:(21a)Minimize∑eg∈E∑kvg,kFor FlexRay 3.0, the objective is to minimize the number of the used slots:(21b)Minimize∑eg∈E∑w∑kvg,w,k


## 5. Experimental Results and Discussion

In order to assess the effectiveness and efficiency of the proposed MILP-based security-aware scheduling approach (hereafter referred to as MILP-S), we conducted extensive experiments by scheduling a number of real-time automotive applications on the FlexRay-based system architecture. The MILP is solved using LINGO 11.0 on a machine with a 2.8 GHz processor and 8 GB memory. The MACs are computed using hash function HMAC-MD5. We measure the execution times of HMAC-MD5 on Infineon TriCore, a representative automotive 32-bit microcontroller. A MAC generation/verification operation takes 11μs.In all experiments, the cost functions with respect to latency or extensibility are used as the criterions of performance evaluation. To assess the impact of the additional authentication mechanism on the system performances after using the proposed MILP-S, we compare the results of MILP-S and two non-security-aware scheduling optimization approaches, MILP-NS and ASAP-NS. The MILP-NS is based on the same MILP formulation, but it does not consider the authentication mechanism-related operations. The ASAP-NS is to (a) pack the signals generated by the same task into a frame and (b) schedule the tasks and frames using As-Soon-As-Possible (ASAP) scheduling. Such a solution would be chosen by a good designer without the help of the dedicated optimization tool. It should be noted that, since ASAP-based security-aware scheduling approach cannot obtain the feasible scheduling solutions (i.e., satisfying all the design constraints) in all experiments, this section does not present the results of this approach.


### 5.1. Case Study: An Automotive X-by-Wire System

The system consists of 8 ECUs interconnected by the FlexRay bus. There are 25 tasks and 55 signals in the X-by-Wire applications. Tables2 and 3 show the periods, the worst-case execution time of tasks (in microseconds), and the sizes of signals (in bits). The lengths of the communication cycle, ST slot, and frame payload are 1 ms, 0.035 ms, and 16 bytes, respectively. There are 22 slots in the FlexRay ST segment. The maximum security goal of all signals is 1-10−8 per hour, which corresponds to the most stringent safety level of ISO 26262, i.e., Automotive Safety Integrity Level D. The MAC size is truncated to 48 bits according to constraint (1).Table 2
Tasks of the x-by-wire system.
Task ECU Period Execution time Task ECU Period Execution time τ 1 e 7 8000 350 τ 14 e 7 8000 360 τ 2 e 8 8000 330 τ 19 e 6 8000 770 τ 3 e 3 8000 200 τ 20 e 6 8000 770 τ 4 e 4 8000 190 τ 21 e 7 8000 305 τ 5 e 6 8000 200 τ 22 e 8 8000 500 τ 6 / τ 7 / τ 8 / τ 9 e 3 / e 4 / e 5 / e 6 8000 860 τ 23 e 8 8000 455 τ 10 / τ 11 / τ 12 / τ 13 e 3 / e 4 / e 5 / e 6 2000 40 τ 24 e 1 2000 780 τ 15 / τ 16 / τ 17 / τ 18 e 3 / e 4 / e 5 / e 6 8000 780 τ 25 e 2 8000 890Table 3
Signals of the x-by-wire system.
Signal Send Receive Size Signal Send Receive Size σ 1 - σ 4 τ 1 τ 6/τ7/τ8/τ9 32 σ 25 τ 8 τ 20 8 σ 5 - σ 8 τ 2 τ 6/τ7/τ8/τ9 32 σ 26 - σ 28 τ 9 τ 19 8 σ 9 - σ 10 τ 3 τ 7/τ8/τ9 32 σ 29 - σ 33 τ 15 τ 21 4 σ 11 - σ 12 τ 4 τ 6/τ8/τ9 32 σ 34 - σ 27 τ 16 τ 21 4 σ 13 - σ 16 τ 5 τ 6/τ7/τ8 32 σ 38 - σ 41 τ 17 τ 21 4 σ 17 - σ 18 τ 10 τ 11/τ12/τ13 4 σ 42 - σ 45 τ 18 τ 21 4 σ 19 - σ 20 τ 14 τ 15/τ16/τ17/τ18 8 σ 46 - σ 49 τ 21 τ 22/τ23 4 σ 21 - σ 22 τ 6 τ 19/τ20 4 σ 50 - σ 52 τ 24 τ 21 32 σ 23 - σ 24 τ 7 τ 19/τ20 8 σ 53 - σ 55 τ 25 τ 21 32Table4 depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to latency and extensibility laxity metric functions. It is shown that MILP-S can guarantee the schedulability of system with authentication mechanism overheads and constraints whether the slot multiplexing mechanism of FlexRay 2.1 or FlexRay 3.0 is applied. Specifically, when the extensibility is taken as optimization objective and FlexRay 3.0 is applied, the number of slots used by MILP-S is greater than that of the non-security-aware scheduling optimization approaches MILP-NS and ASAP-NS. This is because each sender needs to transmit the released key in each time interval after using the TESLA authentication mechanism and consumes more slots. Even so, for safety-critical automotive systems, a small portion of their bandwidth resources is still worth achieving security. When the extensibility is taken as optimization objective and FlexRay 2.1 is applied, the number of the slot identifiers used by MILP-S is the same as that of MILP-NS and even less than that of ASAP-NS. These demonstrate that, although the introduction of authentication function requires more slots to transmit the keys, these slots share the slot identifiers as far as possible by using the proposed MILP-S, thereby not degrading the extensibility of systems in this scenario.Table 4
Experimental results of the x-by-wire system.
Approach Extensibility Time performance FlexRay 2.1 FlexRay 3.0 FlexRay 2.1 FlexRay 3.0 MILP-S 8 64 73.65 74.28 ASAP-NS 18 21 85.63 85.63 MILP-NS 8 15 99.02 99.02On the other hand, when the timing performance is taken as optimization objective, the laxity of all time-sensitive function paths obtained by MILP-S is slightly lower than that of the non-security-aware scheduling optimization approaches MILP-NS and especially ASAP-NS, whether the slot multiplexing mechanism of FlexRay 2.1 or FlexRay 3.0 is applied. These demonstrate that the introduction of authentication function hardly affects the timing performance of systems after using the proposed MILP-S.


### 5.2. Scalability Analysis

To assess the scalability of the proposed approach, we evaluate the performance of the proposed scheduling approach on systems with different numbers of time-sensitive function paths. We generated a set of synthetic applications based on realistic automotive system cases. Specifically, the periods of tasks and signals are varied among the range [5, 10, and 20 ms]. The lengths of the communication cycle, ST slot, and frame payload are 2.5 ms, 0.032 ms, and 16 bytes, respectively. There are 45 slots in the FlexRay ST segment. The number of ECUs is 8. The average ratio of deadline to period of each time-sensitive function path is 0.7. The maximum security goal of all signals is 1-10−7 per hour, which corresponds to the Automotive Safety Level C of ISO 26262 standard. The MAC size should be no less than 43 bits according to constraint (1). In these experiments, it is set to 6 bytes for alignment.In the figures of results, the horizontal axis marks the number of paths, which denotes the scale of the experiments, as the numbers of tasks and signals simultaneously grow. The number of time-sensitive function paths is varied among the range[10,15,20,25]. When the number of paths is 25, the numbers of automotive applications, tasks, and signals are 12, 54, and 150, respectively. The average cost of a task is 0.55 ms.Figure6(a) depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to extensibility metric function on systems applying FlexRay 2.1. It is shown that the number of the slot identifiers obtained by MILP-S is average 15% more than that of MILP-NS and 35% less than that of ASAP-NS. These demonstrate that the introduction of authentication function has not led to huge increases in slot identifiers consumption by using the proposed MILP-S.Figure 6
Comparison results of MILP-S, MILP-NS, and ASAP-NS for different optimization metrics versus number of paths. (a) Number of the slot identifiers. (b) Number of the slots. (c) Laxity.
(a) (b) (c)Similarly, Figure6(b) depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to extensibility metric function on systems applying FlexRay 3.0. It is shown that MILP-S used the largest number of slots. In addition, as the number of paths increases, the differences in slot consumption between the security-aware MILP-S and non-security-aware MILP-NS and ASAP-NS decrease slightly. This is because, when the number of function paths grows and the number of ECUs remains constant, each ECU produces more signals, thus providing more possibility of optimization of frame packing and scheduling.On the other hand, Figure6(c) depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to latency metric function on systems with different numbers of time-sensitive function paths. Since the MILP-NS and ASAP-NS returned the same laxities when FlexRay 2.1 and FlexRay 3.0 are applied in the systems, and for the MILP-S, the laxity differences between applying FlexRay 2.1 and FlexRay 3.0 were all slight (within 1 ms), and both results are represented as a graph. First, it is shown that MILP-S can still guarantee the schedulability of systems with authentication mechanism overheads and constraints in all cases. Second, the laxity of all function paths obtained by MILP-S is average 22% lower than that of MILP-NS and only 16% lower than that of ASAP-NS. These demonstrate that authentication function hardly affects the timing performance of systems by using the proposed MILP-S.At the end of this part, Figure7 shows the runtime of the MILP solver for each experiment. It is shown that, for both optimization metrics and both versions of FlexRay protocols, the solver is able to find the optimal solution within the time limit when the number of paths is less than 25 and returns a feasible solution when the number of paths is 25. A straightforward application of the proposed MILP approach to systems with hundreds of signals could provide only a feasible solution or not feasible, instead of the optimum. In this case, it is still possible to use the approach incrementally, by dividing the applications into several subsets, as in [34]. The application subsets could be scheduled iteratively starting from the most critical components and moving to less critical ones. This would require solving several consecutive MILP problems. Although this method cannot guarantee optimality, it should provide a good tradeoff between optimality and runtime.Figure 7
Runtime of the MILP solver for different optimization metrics versus number of paths. (a) Extensibility. (b) Latency.
(a) (b)


## 5.1. Case Study: An Automotive X-by-Wire System

The system consists of 8 ECUs interconnected by the FlexRay bus. There are 25 tasks and 55 signals in the X-by-Wire applications. Tables2 and 3 show the periods, the worst-case execution time of tasks (in microseconds), and the sizes of signals (in bits). The lengths of the communication cycle, ST slot, and frame payload are 1 ms, 0.035 ms, and 16 bytes, respectively. There are 22 slots in the FlexRay ST segment. The maximum security goal of all signals is 1-10−8 per hour, which corresponds to the most stringent safety level of ISO 26262, i.e., Automotive Safety Integrity Level D. The MAC size is truncated to 48 bits according to constraint (1).Table 2
Tasks of the x-by-wire system.
Task ECU Period Execution time Task ECU Period Execution time τ 1 e 7 8000 350 τ 14 e 7 8000 360 τ 2 e 8 8000 330 τ 19 e 6 8000 770 τ 3 e 3 8000 200 τ 20 e 6 8000 770 τ 4 e 4 8000 190 τ 21 e 7 8000 305 τ 5 e 6 8000 200 τ 22 e 8 8000 500 τ 6 / τ 7 / τ 8 / τ 9 e 3 / e 4 / e 5 / e 6 8000 860 τ 23 e 8 8000 455 τ 10 / τ 11 / τ 12 / τ 13 e 3 / e 4 / e 5 / e 6 2000 40 τ 24 e 1 2000 780 τ 15 / τ 16 / τ 17 / τ 18 e 3 / e 4 / e 5 / e 6 8000 780 τ 25 e 2 8000 890Table 3
Signals of the x-by-wire system.
Signal Send Receive Size Signal Send Receive Size σ 1 - σ 4 τ 1 τ 6/τ7/τ8/τ9 32 σ 25 τ 8 τ 20 8 σ 5 - σ 8 τ 2 τ 6/τ7/τ8/τ9 32 σ 26 - σ 28 τ 9 τ 19 8 σ 9 - σ 10 τ 3 τ 7/τ8/τ9 32 σ 29 - σ 33 τ 15 τ 21 4 σ 11 - σ 12 τ 4 τ 6/τ8/τ9 32 σ 34 - σ 27 τ 16 τ 21 4 σ 13 - σ 16 τ 5 τ 6/τ7/τ8 32 σ 38 - σ 41 τ 17 τ 21 4 σ 17 - σ 18 τ 10 τ 11/τ12/τ13 4 σ 42 - σ 45 τ 18 τ 21 4 σ 19 - σ 20 τ 14 τ 15/τ16/τ17/τ18 8 σ 46 - σ 49 τ 21 τ 22/τ23 4 σ 21 - σ 22 τ 6 τ 19/τ20 4 σ 50 - σ 52 τ 24 τ 21 32 σ 23 - σ 24 τ 7 τ 19/τ20 8 σ 53 - σ 55 τ 25 τ 21 32Table4 depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to latency and extensibility laxity metric functions. It is shown that MILP-S can guarantee the schedulability of system with authentication mechanism overheads and constraints whether the slot multiplexing mechanism of FlexRay 2.1 or FlexRay 3.0 is applied. Specifically, when the extensibility is taken as optimization objective and FlexRay 3.0 is applied, the number of slots used by MILP-S is greater than that of the non-security-aware scheduling optimization approaches MILP-NS and ASAP-NS. This is because each sender needs to transmit the released key in each time interval after using the TESLA authentication mechanism and consumes more slots. Even so, for safety-critical automotive systems, a small portion of their bandwidth resources is still worth achieving security. When the extensibility is taken as optimization objective and FlexRay 2.1 is applied, the number of the slot identifiers used by MILP-S is the same as that of MILP-NS and even less than that of ASAP-NS. These demonstrate that, although the introduction of authentication function requires more slots to transmit the keys, these slots share the slot identifiers as far as possible by using the proposed MILP-S, thereby not degrading the extensibility of systems in this scenario.Table 4
Experimental results of the x-by-wire system.
Approach Extensibility Time performance FlexRay 2.1 FlexRay 3.0 FlexRay 2.1 FlexRay 3.0 MILP-S 8 64 73.65 74.28 ASAP-NS 18 21 85.63 85.63 MILP-NS 8 15 99.02 99.02On the other hand, when the timing performance is taken as optimization objective, the laxity of all time-sensitive function paths obtained by MILP-S is slightly lower than that of the non-security-aware scheduling optimization approaches MILP-NS and especially ASAP-NS, whether the slot multiplexing mechanism of FlexRay 2.1 or FlexRay 3.0 is applied. These demonstrate that the introduction of authentication function hardly affects the timing performance of systems after using the proposed MILP-S.


## 5.2. Scalability Analysis

To assess the scalability of the proposed approach, we evaluate the performance of the proposed scheduling approach on systems with different numbers of time-sensitive function paths. We generated a set of synthetic applications based on realistic automotive system cases. Specifically, the periods of tasks and signals are varied among the range [5, 10, and 20 ms]. The lengths of the communication cycle, ST slot, and frame payload are 2.5 ms, 0.032 ms, and 16 bytes, respectively. There are 45 slots in the FlexRay ST segment. The number of ECUs is 8. The average ratio of deadline to period of each time-sensitive function path is 0.7. The maximum security goal of all signals is 1-10−7 per hour, which corresponds to the Automotive Safety Level C of ISO 26262 standard. The MAC size should be no less than 43 bits according to constraint (1). In these experiments, it is set to 6 bytes for alignment.In the figures of results, the horizontal axis marks the number of paths, which denotes the scale of the experiments, as the numbers of tasks and signals simultaneously grow. The number of time-sensitive function paths is varied among the range[10,15,20,25]. When the number of paths is 25, the numbers of automotive applications, tasks, and signals are 12, 54, and 150, respectively. The average cost of a task is 0.55 ms.Figure6(a) depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to extensibility metric function on systems applying FlexRay 2.1. It is shown that the number of the slot identifiers obtained by MILP-S is average 15% more than that of MILP-NS and 35% less than that of ASAP-NS. These demonstrate that the introduction of authentication function has not led to huge increases in slot identifiers consumption by using the proposed MILP-S.Figure 6
Comparison results of MILP-S, MILP-NS, and ASAP-NS for different optimization metrics versus number of paths. (a) Number of the slot identifiers. (b) Number of the slots. (c) Laxity.
(a) (b) (c)Similarly, Figure6(b) depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to extensibility metric function on systems applying FlexRay 3.0. It is shown that MILP-S used the largest number of slots. In addition, as the number of paths increases, the differences in slot consumption between the security-aware MILP-S and non-security-aware MILP-NS and ASAP-NS decrease slightly. This is because, when the number of function paths grows and the number of ECUs remains constant, each ECU produces more signals, thus providing more possibility of optimization of frame packing and scheduling.On the other hand, Figure6(c) depicts the comparison results of MILP-S, MILP-NS, and ASAP-NS with respect to latency metric function on systems with different numbers of time-sensitive function paths. Since the MILP-NS and ASAP-NS returned the same laxities when FlexRay 2.1 and FlexRay 3.0 are applied in the systems, and for the MILP-S, the laxity differences between applying FlexRay 2.1 and FlexRay 3.0 were all slight (within 1 ms), and both results are represented as a graph. First, it is shown that MILP-S can still guarantee the schedulability of systems with authentication mechanism overheads and constraints in all cases. Second, the laxity of all function paths obtained by MILP-S is average 22% lower than that of MILP-NS and only 16% lower than that of ASAP-NS. These demonstrate that authentication function hardly affects the timing performance of systems by using the proposed MILP-S.At the end of this part, Figure7 shows the runtime of the MILP solver for each experiment. It is shown that, for both optimization metrics and both versions of FlexRay protocols, the solver is able to find the optimal solution within the time limit when the number of paths is less than 25 and returns a feasible solution when the number of paths is 25. A straightforward application of the proposed MILP approach to systems with hundreds of signals could provide only a feasible solution or not feasible, instead of the optimum. In this case, it is still possible to use the approach incrementally, by dividing the applications into several subsets, as in [34]. The application subsets could be scheduled iteratively starting from the most critical components and moving to less critical ones. This would require solving several consecutive MILP problems. Although this method cannot guarantee optimality, it should provide a good tradeoff between optimality and runtime.Figure 7
Runtime of the MILP solver for different optimization metrics versus number of paths. (a) Extensibility. (b) Latency.
(a) (b)


## 6. Conclusions

In this paper, we have proposed an approach to address both the information security and functional safety in the scheduling design of FlexRay-based automotive systems. An authentication mechanism based on delayed exposure of one-way key chains is applied on TTEthernet to protect against forgery and replay attacks. The authentication mechanism provides an appropriate trade-off between security level and resource overhead. Furthermore, an MILP formulation is proposed for solving the scheduling optimization problem of FlexRay-based real-time automotive systems subject to both authentication mechanism constraints and other traditional design constraints. The objective of MILP approach is to maximize the laxity on function paths (therefore improving timing performance) or to minimize the number of used slots or slot identifiers (therefore improving extensibility). The experiment results show that the proposed MILP approach can still guarantee the schedulability of systems with authentication mechanism overheads and constraints and achieve good performance with timing and extensibility.



---

*Source: 4130756-2019-06-13.xml*