Security-Aware Scheduling for TTEthernet-Based Real-Time Automotive Systems

TTEthernet is a deterministic, congestion-free, and high-bandwidth communication protocol based on the Ethernet standard that provides a powerful network solution for developing safety-critical distributed real-time automotive systems. 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, TTEthernet-based architecture does not have direct support for secure communication. When deploying the security mechanisms on these architectures, a major 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 TTEthernet 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 the TTEthernet-based real-time automotive systems subject to both authentication mechanism constraints and other traditional design constraints. The extensive experiments are conducted to demonstrate the effectiveness and efficiency of the proposed method.

SECTION I. Introduction

TTEthernet [1] is a highly available networking technology that implements time-triggered communication mechanisms over Ethernet standard to satisfy the requirements of fully deterministic, high-speed and low-cost communication. It can guarantee constant latency for multi-hop network communication routes relying on fault-tolerant synchronization services. In addition to time-triggered (TT) traffic, TTEthernet supports rate-constrained traffic (compatible with ARINC 664P7 [2]) and standard Ethernet [3] traffic to provide flexibility. These capabilities make TTEthernet a powerful network solution for developing real-time safety-critical automotive systems [4]–​[6].

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. For example, researchers have demonstrated that modern automotive systems are vulnerable to attacks through various interfaces such as OBD-II, Bluetooth, Wi-Fi, DSRC, GPS and 3G/4G [7]–​[10]. Once one Electronic Control Units (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 TTEthernet-based architecture, it does not directly provide multicast source authentication to protect data authenticity.

Integrating authentication mechanisms into TTEthernet-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.

Given these issues, our major contributions are as follows.

1. First, we apply the TESLA [11] authentication mechanism based on delayed exposure of keys to protect against forgery and replay attacks on TTEthernet. It provides an appropriate trade-off between security level and resource overhead, compared with other multicast authentication approaches. Moreover, we make a modification to the original TESLA in order to improve on the authentication delay.

2. Furthermore, we propose a mixed integer linear programming (MILP) formulation that efficiently solves the optimal scheduling problem of TTEthernet-based real-time automotive systems with authentication mechanism constraints. The scheduling design includes (a) the packing of automotive control and authentication mechanism-related signals to TTEthernet frames, (b) the scheduling of frames on TTEthernet, 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 bandwidth consumption, therefore improving extensibility. To the best of our knowledge, this is the first work to integrate security constraints and other traditional constraints in the scheduling design of TTEthernet-based automotive systems.

The remainder of the paper is organized as follows. Section II overviews some related work. Section III introduces the system model. Section IV presents the security mechanism and security model. Section V formally states the security-aware optimization scheduling problem whose solution is tackled using MILP-based method. Section VI presents experimental results, with conclusions following in Section VII.

SECTION II. Related Work

A. Multicast Authentication

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]–​[15] are much more computationally efficient than traditional public key signatures. However, one-time signatures can incur kilobytes of authentication data per message, that 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 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 [11], [18]–​[21], 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 TTEthernet, and make a modification to the original TESLA so that it is more appropriate for our application setting.

B. Scheduling

Steiner [22] proposed a scheduling method based satisfiability modulo theory (SMT) for the TTEthernet TT traffic. They defined a set of scheduling constraints and used the SMT solver to find a solution that satisfies all constraints. Steiner [23] proposed to introduce periodic slots into static schedules to help reduce the RC delays. Suethanuwong [24] proposed a scheduling approach to compute the periods and offsets of TT frames. Tǎmaş-Selicean et al. [25] proposed a Tabu-search-based metaheuristic for TT schedule optimization. They [26] also suggested a Tabu-search-based metaheuristic to optimize TTEthernet networks, where in addition to optimal TT schedules, the proposed method provides optimal bandwidth allocation of RC frames. Dvořák [27] developed a three-stage algorithm to create the communication schedules for TT traffic. These works only focused 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.

The system-level scheduling on both signals and tasks has also been studied for TTEthernet-based real-time systems. Zhang et al. [28] applied mixed-integer programming (MIP) to solve the scheduling problem for Ethernet-based TT systems. Craciunas and Oliver [29] formulated the scheduling problem of TTEthernet-based distributed systems using first-order logical constraints and applied SMT and MIP solvers to solve it, respectively. Abuteir and Obermaisser [30] proposed a scheduling algorithm based on neighborhood search for multi-cluster TTEthernet systems. However, none of the above-mentioned works considered the interference of security operations on system applications. In this work, we provide an MILP formulation for solving the scheduling optimization problem of TTEthernet-based real-time automotive systems while meeting the requirements of both information security and functional safety.

SECTION III. System

A. Hardware Architecture

A TTEthernet-based architecture consists of a set of ECUs (usually called end systems, ESes) interconnected by physical links and network switches (NSes). The physical links are fully duplex and the networks can be multi-hop. Each ES is composed of a processing element (PE) containing a CPU, RAM and I/O resources, and a network interface card (NIC). An example of the TTEthernet architecture is presented in Fig. 1(a).

FIGURE 1.

System model example, where signals $\sigma _{1},\sigma _{2}$ are packed into frame ${\,f}_{1},\sigma _{8},\sigma _{9}$ into $f_{2}$ , $\sigma _{3}, ~\sigma _{4}$ into $f_{3}$ , and $\sigma _{5},\sigma _{6},\sigma _{7}$ into $f_{4}$ .

We denote $\mathcal {N}$ the set of communication nodes (ESes and NSes) in a TTEthernet-based architecture, and $\mathcal {L}\subseteq \mathcal {N}\times \mathcal {N}$ the set of directional communication links between nodes, i.e., ${\mathrm {[n}}_{\mathrm {a}}\mathrm {n}_{\mathrm {b}}\mathrm {]\in L} {\mathrm {[n}}_{\mathrm {a}},\mathrm {n}_{\mathrm {b}}\mathrm {]\in L}$ is an ordered tuple representing a communication link from node $n_{a}\in \mathcal {N}$ to $n_{b}\in \mathcal {N}$ . Since the scheduling problem addressed in this paper is performed at the system-level, we also consider PEs of the ESes for running tasks in addition to the network link resources. We model the PE of each ES as a directional self-link ${[n}_{a},n_{a}]\in \mathcal {L}$ , which we call PE link resource, connecting an ES $n_{a}\in \mathcal {N}$ with itself. For simplicity, the network or PE link resource will also be identified and denoted by a single index, as in $l_{g}$ .

B. Software Architecture

In our model, ESes are assumed to run 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 TT traffic arbitration model provided by the TTEthernet protocol. In TTEthernet, the transmission of a frame $f_{m}\in$ { from its sender $T_{m}^{\,f}$ to multiple receivers typically requires several transfers. The route of a frame is defined via the concept of virtual link, which is a logical data-flow path from one sender ES to one or more receiver ESes. For example, in Fig. 1(a), the virtual link of frame $f_{1}$ connects ES $n_{1}$ to $n_{4}$ and $n_{5}$ , which can be denoted as $\mathrm {[[}n_{1},n_{3}\mathrm {],}~[{n_{3},n_{4}\mathrm {], [}n}_{3},n_{5}\mathrm {]]}$ or $[l_{3},l_{5},l_{6}]$ . TT communication is done according to communication schedules determined offline and stored in the ESes and NSes. Each ES or NS will protect the network as it will only transmit frames as specified sending times in the schedule table. The start time of a TT frame $f_{m}$ on each link resource it uses is specified by its period $P_{m}^{\,f}$ and an offset within the period.

C. Application Model

We model an application $\lambda _{r}\in \Lambda ^{app}$ to be processed in the system as a directed, acyclic graph $\mathrm { }G_{r}^{app}$ , where the vertices represent the tasks, and the edges represent the signals communicated between tasks.

A task $\tau _{i}\in \Gamma ^{app}$ is characterized by the tuple $(E_{i}^{\tau },C_{i}^{\tau }, P_{i}^{\tau },D_{i}^{\tau })$ , where $E_{i}^{\tau }$ denotes the PE link resource it needs to execute, $C_{i}^{\tau }$ is its execution time, $P_{i}^{\tau }$ is its period and $D_{i}^{\tau }$ is its deadline. An edge linking two tasks $\tau _{i}$ and $\tau _{i^{'}}$ denotes a signal $\sigma _{j}$ , produced by $\tau _{i}$ that is available to $\tau _{i^{'}}$ . Each task reads its input at its start time and writes its results at the end of execution. A signal $\sigma _{j}\in \mathcal {S}^{app}$ is characterized by the tuple $({T_{j}^{\sigma },R_{j}^{\sigma },W}_{j}^{\sigma },P_{j}^{\sigma },D_{j}^{\sigma })$ , where $T_{j}^{\sigma }$ and $R_{j}^{\sigma }$ denotes the PE link resources required for sending and receiving it, $W_{j}^{\sigma }$ is its bit width, $P_{j}^{\sigma }$ is its period and ${D}_{j}^{\sigma }$ is its deadline. In addition, its resource path (the ordered sequence of the used resources) is modeled by two sets $\mathcal {U}$ and ${Q}$ derived from the base signal set and link resource set, where $(\sigma _{j},l_{g})\in \mathcal {U}$ denotes that the signal $\sigma _{j}$ uses the resource $l_{g}$ , and $\left ({\sigma _{j},l_{g},l_{g^{'}} }\right)\in Q$ denotes that the signal $\sigma _{j}$ uses the resource $l_{g}$ and $l_{g^{'}}$ in order.

For example, in the application $\lambda _{2}$ of Fig. 1(b), task $\tau _{6}$ generates a multicast signal, tasks $\tau _{7}$ and $\tau _{8}$ 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 resource paths. Specifically, we define a set of signals $\mathcal {S}_{g,h}$ containing all of the branches of the $h$ -th multicast signal of each PE link resource $l_{g}$ , such as signals $\sigma _{8}$ and $\sigma _{9}$ are assumed to be the two branches of the second multicast signal of resource $l_{1}({[n}_{1},n_{1}])$ , their respective resource paths are listed in Fig. 1(c); thus, we have $\sigma _{8},\sigma _{9}\in \mathcal {S}_{1,2}$ .

A function path $\rho _{\varepsilon }{\in \mathcal {FP}}^{app}$ from $\tau _{i}$ to $\tau _{i^{'}}$ is a sequence $\left [{ \tau _{i}{,\ldots,\tau }_{i^{'}} }\right]$ of tasks such that there is a link between any two consecutive tasks. For instance, in application $\lambda _{1}$ , there is a function path between tasks $\tau _{1}$ and $\tau _{5}$ .The latency of function path is defined as the time interval between the start of an instance of $\tau _{i}$ and the completion of the instance of $\tau _{i^{'}}$ that produces a result that is dependent on the output of $\tau _{i}$ . The deadline ${D}_{\varepsilon }^{\rho }$ of function path is set by system designers as an application requirement.

SECTION IV. Security Mechanism and Security Model

A. Security Mechanism

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 TTEthernet switches, malicious insider code, or tampering with ESes. We consider an active attacker model where an attacker can masquerade as other ESes to inject forged messages and can also replay messages. Attackers accessing the TTEthernet through corrupted nodes will have access to the key material in those ESes. An attacker must not be able to masquerade as any ES they do not already control to perform a successful attack [17].

Additionally, 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 inject a well-formed frame in another node’s time slot. And an attack can only take one forgery or replay attempt per valid time slot, since transmitters are only permitted to send a frame per assigned time slot in TTEthernet.

2) Overview of the TESLA Mechanism

In this work, we apply TESLA authentication mechanism to protect the authenticity of messages on TTEthernet. The main ideas 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.

In TESLA, time is divided into several intervals with uniform duration $P_{int}$ . Before protocol execution, the sender generates a one-way key chain of self-authenticating values (easy to compute but difficult to invert) using a one-way hash function $H$ as $K_{0},K_{1},\ldots,K_{n}$ , where $K_{\varphi }=H(K_{\varphi +1})$ , and assigns the keys sequentially to the time intervals, as depicted in Fig. 2. The chain is used in reverse order starting with $K_{1}$ . To bootstrap TESLA, the sender uses asymmetric cryptography to distribute the initial key $K_{0}$ to every receiver in the network authoritatively.

FIGURE 2.

TESLA protocol example.

When a sender sends a message in $\varphi$ -th time interval, it appends a MAC to the message computed using a hash function and the key $K_{\varphi }$ corresponding to the current time interval. The key remains secret for $d$ intervals, so along with the message, the sender also sends the key $K_{\varphi -d}$ that it can disclose.

When a receiver receives a message in $\varphi$ -th time interval, it cannot yet verify the authenticity of the message. Instead, it puts the message into a buffer, and verifies the authenticity after it gets the correct key $K_{\varphi }$ . The legitimacy of key $K_{\varphi }$ can be determined by verifying previously released key $K_{\varphi -1}$ that $K_{\varphi -1}=H({K}_{\varphi })$ .

3) Modification to the TESLA Mechanism

To ensure the key to be disclosed in an interval can arrive at its receivers on time, TESLA protocol specify that the key must be appended to each message frame in that interval. The repeated transmission and verification of the same key will cause 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.

For this, we make a modification to the original TESLA combining with our application setting. Given the TTEthernet TT traffic provides highly deterministic communication, we specify that each key $K_{\varphi }$ is released only once in its next interval and is transmitted through the TT traffic to ensure its time determinism.

B. Security Model

After applying the modified TESLA authentication mechanism to the system, extra information, i.e. keys, need 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 frame $f_{m}$ are executed on the PEs $l_{g}$ of 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 $\lambda _{r}\in \Lambda ^{sec}$ as a directed, acyclic graph $\mathcal {G}_{r}^{sec}$ , which includes the key release task $\tau _{g}^{rel}$ generated by the sender $l_{g}$ , key verification tasks $\tau _{g,g^{'}}^{ver}$ generated by the receivers $l_{g^{'}}$ and key signals $\sigma _{g,g^{'}}^{key}$ produced by $\tau _{g,g^{'}}^{rel}$ that is available to $\tau _{g,g^{'}}^{ver}$ . Fig. 3 illustrates the additional operations after applying the authentication mechanism to the example system in Fig. 1.

FIGURE 3.

Security model example.

For simplicity, the key authentication-related tasks or signals are also identified and denoted by a single index, as in $\tau _{i}$ or $\sigma _{j}$ . A key verification task $\tau _{i}\in \Gamma ^{sec}$ is characterized by the tuple $(E_{i}^{\tau },V_{i}^{\tau },{C_{i}^{\tau },P}_{i}^{\tau })$ where $E_{i}^{\tau }$ and $V_{i}^{\tau }$ are the PE link resources it needs to execute and verify, $C_{i}^{\tau }$ is its time cost indicating the execution time of the one-way hash function $H$ on the PE $E_{i}^{\tau }$ which can be simply measured, and $P_{i}^{\tau }$ is its period (i.e., the interval duration $P_{int}$ 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 $\sigma _{j}\in \mathcal {S}^{sec}$ is characterized by the tuple $(T_{j}^{\sigma },R_{j}^{\sigma }, N_{j}^{\sigma },W_{j}^{\sigma },P_{j}^{\sigma })$ ,where $T_{j}^{\sigma }$ and $R_{j}^{\sigma }$ are the PE link resources required for sending and receiving it, $N_{j}^{\sigma }$ is the last network link resource required for transmitting it, $W_{j}^{\sigma }$ is its bit width and $P_{j}^{\sigma }$ is its period. Similar to the automotive control signals, its resource path is also modeled by two sets $\mathcal {U}$ and ${Q}$ derived from the base key signal set and link resource set are defined. 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.

C. Choice of Interval Duration of Key Release

Following the authentication mechanism, the smaller the interval duration, the more frequently key authentication applications execute and thus the more processing and communication resources are consumed. But the larger the interval duration, 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 $\rho _{\varepsilon }\in \mathcal {FP}^{app}$ , we let $C_{\varepsilon }^{\rho }$ 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 $P_{int}$ is the maximum value that satisfying the following constraints:

$$\begin{align*}&\forall {\rho _{\varepsilon }\in \mathcal {FP}}^{app},\quad P_{int}\cdot C_{\varepsilon }^{\rho }\le D_{\varepsilon }^{\rho }\tag{1}\\&P_{int}\le {min}_{\sigma _{j}\in \mathcal {S}^{app}}D_{j}^{\sigma }\tag{2}\\&{\begin{array}{cccccccccccccccccccc} P_{int} mod {gcd}_{\sigma _{j}\in \mathcal {S}^{app}}P_{j}^{\sigma }=0, \\ {P}_{int} =n\cdot {gcd}_{\sigma _{j}\in \mathcal {S}^{app}}P_{j}^{\sigma },\quad n\in Z^{\ast }\\ \end{array}} or\tag{3}\end{align*}$$

Relations (1) and (2) provide the time limits, i.e. the product of interval duration $P_{int}$ and signal level $C_{\varepsilon }^{\rho }$ cannot exceed the deadline $D_{\varepsilon }^{\rho }$ for a function path ${\rho }_{\varepsilon }\in \mathcal {FP}^{app}$ . 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 $\rho _{\varepsilon }$ must have a duration of $C_{\varepsilon }^{\rho }$ intervals. In addition, the interval duration $P_{int}$ cannot exceed the minimum value of the deadlines $D_{j}^{\sigma }$ of signal $\sigma _{j}\in \mathcal {S}^{app}$ to ensure that each signal can be authenticated by the receiver before its deadline. Relation (3) is bound to the alignment of the key signals and automotive control signals schedules, i.e. the interval duration $P_{int}$ should be an integer multiple or factor of the greatest common divisor (gcd) of the periods of all the signals.

SECTION V. Security-Aware Scheduling

A. Problem Statement

The security-aware scheduling problem we are addressing in this paper can be formulated as follows. Given the system model and the security model generated by the authentication mechanism, we decide on the (1) packing of automotive control and authentication mechanism-related signals to TTEthernet frames, (2) scheduling of frames on TTEthernet, and (3) scheduling of automotive control and authentication mechanism- related tasks on respective PE, such that:

• the deadline constraints and the precedence constraints caused by information passing between all tasks and signals are satisfied,

• the payload size and the usage sequence of the link resources constraints on frames are satisfied,

• the objective function with respect to extensibility or timing performance is optimized.

B. Motivational Examples

Let us illustrate the integrated scheduling problem using the setup from Fig. 1, where two automotive control applications are executed on the system consisting of four ESes and one NS. The corresponding security applications are depicted in Fig. 3. For simplicity, in this example we assume that the execution times of the hash function on all PEs are 0.1 ms. Although the standard TTEthernet speed is 100 Mbps or higher, in order to describe the data transmission process clearly, we consider that the link speed is only 10 Mbps. We assume that there are two time-sensitive paths, one form $\tau _{1}$ to $\tau _{5}$ with a deadline of 5 ms and the other from $\tau _{2}$ to $\tau _{8}$ with a deadline of 2.5 ms. According to (1)–(3), the interval duration $P_{int}$ of key release is 1.25 ms.

A Straightforward solution to the security-aware scheduling problem is to (1) pack the signals generated by the same task into a frame, and (2) 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 Fig. 1, this solution is depicted by the Gantt chart in Fig. 4(a), where automotive control signals $\sigma _{1},\sigma _{2}$ are packed into frame $f_{\mathrm {1,}} \sigma _{8},\sigma _{9}$ into $f_{\mathrm {2,}} \sigma _{3},\sigma _{4}$ into ${\,f}_{3}$ , and $\sigma _{5}{,\sigma }_{6}$ , $\sigma _{7}$ into ${\,f}_{4}$ , key signal $\sigma _{1,7}^{key},\sigma _{1,8}^{key}\mathrm {\sigma }_{{\mathrm {g,g}}^{\mathrm {'}}}^{\mathrm {k}}$ ,are packed into $f_{5,} \mathrm {\sigma }_{{\mathrm {g,g}}^{\mathrm {'}}}^{\mathrm {k}}\mathrm {\sigma }_{2,8}^{\mathrm {key}}$ into ${\,f}_{6,} \sigma _{7,8}^{key}$ into ${\,f}_{7,}$ and key verification tasks $\tau _{1,7}^{ver}, \tau _{1,8}^{ver},\tau _{2,7}^{ver},\tau _{2,8}^{ver}$ are simply denoted by $\tau _{9}-\tau _{12}$ . In this case, the value of the laxity of time-sensitive function paths is −0.2288 ms (the path from $\tau _{2}$ to $\tau _{8}$ misses its deadline) and the sum of the bandwidth consumption rates of all communication links is 0.64928.

FIGURE 4.

Motivational examples.

Fig. 4(b) illustrates an optimal solution with respect to timing performance. This solution increases the laxity of paths to 3.1024 ms and satisfies the deadline constraints of both paths. On the other hand, Fig. 4(c) illustrates an optimal solution with respect to extensibility, which reduces the bandwidth consumption to 0.61664 by packing signals to frames while satisfying the deadline constraints.

C. 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.

1) Definitions

The notations of the elements and constant parameters were described in the previous definition of system model and security model. Besides, two new binary parameters $Z_{m}^{\,f}$ an $Z_{j}^{\sigma }$ are used to denote the type of signals ${\sigma }_{j}$ and frame $f_{m}$ (i.e., 1 for automotive control-related signals and frames and 0 for authentication mechanism-related signals and frames). We assume these parameters are given as design inputs. The notations of the decision variables in the MILP formulation are listed in Table 1.

TABLE 1 The Notations of Binary Variables and Real Variables

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

$$\begin{align*}&\forall g,\sigma _{j}\in \mathcal {S}_{g},\quad \sum \nolimits _{f_{m}\in \left \{{\mathcal F_{g}\thinspace \vert \thinspace {Z_{g}^{\,f}=Z_{j}^{\sigma }}}\right \}} x_{j,m} =1\tag{4}\\&\forall g,\sigma _{j}\in \mathcal S_{g},\quad \sum \nolimits _{f_{m}\in \left \{{\mathcal F_{g}\thinspace \vert \thinspace {Z_{g}^{\,f}\ne Z_{j}^{\sigma }}}\right \}} x_{j,m} =0\tag{5}\\&\mathrm {\forall }j, m,\quad {x}_{j,m}\cdot P_{m}^{\,f}\le P_{j}^{\sigma }\tag{6}\end{align*}$$

Equations (4) and (5) guarantee that the signal $\sigma _{j}$ is packed into exactly one frame with the same type from the same PE link resource, where $\mathcal S_{g}$ and $\mathcal F_{g}$ denote the sets of the signals and frames from PE resource $\mathrm { }l_{g}$ , respectively. Constraint (6) guarantees that the period of a signal is greater than or equal to the period of the frame in which the signal is packed into.

$$\begin{align*}&\forall m, \forall \sigma _{j},\sigma _{j^{'}}\in \mathcal S_{g,h},\quad {x}_{j,m}= x_{j^{'},m}\tag{7}\\&\forall m, \forall \sigma _{j}\in \mathcal S_{g,h},\quad x_{j,m}= \sum \nolimits _{\sigma _{j^{'}}\in S_{g,h}} y_{j^{'},m}\tag{8}\end{align*}$$

Equation (7) ensures that each branch of a multicast signal is packed into the same frame. Equation (8) ensures that exactly one branch of a multicast signal adds its length to the frame.

$$\begin{align*}&\forall \left ({\sigma _{j},l_{g} }\right)\in \mathcal U, \forall m,\quad {x}_{j,m}\le \mu _{m,g}^{\,f}\tag{9}\\&\forall m,g, \quad {\mu }_{m,g}^{\,f}\le \sum \nolimits _{(\sigma _{j},l_{g})\in U} {x_{j,m}} \tag{10}\\&\forall \left ({\sigma _{j},l_{g},l_{g^{'}} }\right)\in Q,\forall m,\quad {x}_{j,m}\le q_{m,g,g^{'}}^{\,f}\tag{11}\\&\forall m,g, g^{'},\quad q_{m,g,g^{'}}^{\,f}\le \sum \nolimits _{\left ({\sigma _{j},l_{g},l_{g^{'}} }\right)\in Q} {x}_{j,m}\tag{12}\\&\forall m,j,\quad x_{j,m}\le r_{m,R_{j}^{\sigma }}^{\,f}\tag{13}\\&\forall m,\forall l_{g}\in \mathcal L^{PE},\quad r_{m,g}^{\,f}\le \sum \nolimits _{\sigma _{j}\in \left \{{\mathcal S\thinspace \vert \thinspace {R_{j}^{\sigma }=l_{g}}}\right \}} {x}_{j,m}\tag{14}\end{align*}$$

Constraints (9) and (10) guarantee that a frame $f_{m}$ uses the resource $l_{g}$ only if there exists a signal $\sigma _{j}$ packed into $f_{m}$ and the signal uses resource $l_{g}$ . Similarly, (11) and (12) guarantee that a frame $f_{m}$ uses the resources $l_{g}$ and $l_{g^{'}}$ in order only if there exists a signal $\sigma _{j}$ such that $\sigma _{j}$ uses the two resources in order and is packed into $f_{m}$ . And (13) and (14) guarantee that the PE link resource $l_{g}$ is the receiver of the frame $f_{m}$ only if there exists a signal $\sigma _{j}\mathrm { }$ packed into $f_{m}$ and the receiver of the signal is $l_{g}$ , where $L^{PE}\subset L$ denotes the set of PE link resources and $\mathcal S=\mathcal S^{app}\bigcup \mathcal S^{sec}$ denotes the set of all signals.

$$\begin{align*} \forall m, {w}_{m}^{\,f}=&OH+ \sum \nolimits _{\sigma _{j}\in \mathcal S} y_{j,m} \cdot W_{j}^{\sigma }+Z_{m}^{\,f}\cdot W^{MAC}\quad \tag{15}\\ \forall m, w_{m}^{\,f}\le&W_{max}^{\,f}\tag{16}\end{align*}$$

Equation (15) calculates the total length of the frame, including the frame overhead $OH$ , the data payload, and the MAC length (that is only contained in the automotive control frame). Constraint (16) ensures that the frame length does not exceed the limit $W_{max}^{\,f}$ allowed by TTEthernet.

(b) Frame scheduling

$$\begin{equation*} \forall m,g, {o}_{m,g}^{\,f}{+c}_{m,g}^{\,f}{+a}_{m,g}^{\,f}\le M\cdot \mu _{m,g}^{\,f}\tag{17}\end{equation*}$$

Constraint (17) ensures that the start time $\mathrm {o}_{\mathrm {m,g}}^{\mathrm {\,f}}$ , execution time $\mathrm { }c_{m,g}^{\,f}$ , and finish time $a_{m,g}^{\,f}$ of a frame $f_{m}$ on its unused link resource $l_{g}$ are equal to zero, where $M$ is a large constant for linearization in this paper.

$$\begin{align*}&\forall m,\forall l_{g}\in \mathcal L^{net},\quad c_{m,g}^{\,f}\le w_{m}^{\,f} / V_{g}^{l}+M\cdot ({1-\mu }_{m,g}^{\,f})\tag{18}\\&\forall m,\forall l_{g}\in \mathcal L^{net},\quad w_{m}^{\,f} / V_{g}^{l}-M\cdot \left ({{1-\mu }_{m,g}^{\,f} }\right) \!\le \! c_{m,g }^{\,f}\qquad \tag{19}\\&\forall m,\forall l_{g}\in \mathcal L^{PE},\quad {c}_{m,g}^{\,f}=\mu _{m,g}^{\,f}{\cdot Z_{m}^{\,f}\cdot C}_{g}^{l}\tag{20}\end{align*}$$

Constraints (18) and (19) state that the execution time $c_{m,g}^{\,f}$ of a frame $f_{m}$ on its used network link resource $l_{g}$ equals to the quotient of its length $w_{m}^{\,f}$ and the configured link speed $V_{g}^{l}$ , where $\mathcal L^{net}\subset \mathcal L$ denotes the set of network link resources.

As mentioned above, the MAC generation and verification operations of each frame are considered the executions on the PEs of its sender and receivers. Thus (20) states that the execution time $c_{m,g}^{\,f}$ of an automotive control frame $f_{m}$ on its used PE link resource $l_{g}$ (i.e., its sender or one of its receivers) equals to the execution time $C_{g}^{l}$ of the selected MAC computation function on $l_{g}$ . In addition, since the use of key signals is not required to have the MAC generation and verification processes, the execution time $c_{m,g}^{\,f}$ of a frame ${\,f}_{m}$ that contains only key signals on its used PE $l_{g}$ is equal to zero.

$$\begin{align*}&\forall m,g,\quad {a}_{m,g}^{\,f}=o_{m,g}^{\,f}+c_{m,g}^{\,f}\tag{21}\\&\forall m,g,g^{'},\quad {a}_{m,g}^{\,f}-M\cdot (1-q_{m,g,g^{'}}^{\,f})\le o_{m,g^{'}}^{\,f}\tag{22}\end{align*}$$

Constraint (21) determines that the finish time $a_{m,g}^{\,f}$ of a frame $f_{m}$ on the resource $l_{g}$ equals to the sum of the start time $o_{m,g}^{\,f}$ and execution time $c_{m,g}^{\,f}\mathrm { }$ on this resource. Constraint (22) ensures that if a frame $f_{m}$ uses the resources $l_{g}$ and $\mathrm { }l_{g^{'}}$ in order, its finish time ${a}_{m,g}^{\,f}$ on the resource $l_{g}$ is before than its start time $o_{m,g^{'}}^{\,f}$ on $l_{g^{'}}$ .

$$\begin{align*}&\forall g, \forall f_{m},f_{m^{'}}, m\!\ne \! m^{'}, \alpha \!\in \! \left \{{\!0,\ldots,lcm\left ({P_{m}^{\,f},P_{m^{'}}^{\,f} }\right) / {P_{m}^{\,f}-1} \!}\right \}, \\&\beta \!\in \! \{0,\ldots,lcm{(P_{m}^{\,f},P_{m^{'}}^{\,f})} \mathord {\left /{ {\vphantom {{(P_{m}^{\,f},P_{m^{'}}^{\,f})} {P_{m^{'}}^{\,f}-1}}} }\right. } {P_{m^{'}}^{\,f}-1} \\&\alpha \cdot P_{m}^{\,f}+a_{m,g}^{\,f}\le \beta \cdot P_{m^{'}}^{\,f}+o_{m^{'},g}^{\,f}+M\cdot \left ({1-\delta _{g,m,m^{'}}^{\alpha,\beta } }\right) \\&+\,M\cdot \left ({1-\mu _{m,g}^{\,f} }\right)+M\cdot \left ({1-\mu _{m^{'},g}^{\,f} }\right)\tag{23}\\&\beta \cdot P_{m^{'}}^{\,f}+a_{m^{'},g}^{\,f}\le \alpha \cdot P_{m}^{\,f}+o_{m,g}^{\,f}+M\cdot \delta _{g,m,m^{'}}^{\alpha,\beta } \\&+\,M\cdot \left ({1-\mu _{m,g}^{\,f} }\right)+M\cdot \left ({1-\mu _{m^{'},g}^{\,f} }\right)\tag{24}\end{align*}$$

Constraints (23) and (24) ensure that two frames never preempt each other on any resource. The variable $\delta _{g,m,m^{' }}^{\alpha,\beta }$ is used for switching, i.e., one of (23) or (24) is trivially satisfied depending on $\delta _{g,m,m^{'}}^{\alpha,\beta }$ .

$$\begin{align*}&\forall j,m,\quad o_{j}^{\sigma }-M\cdot (1-x_{j,m})\le o_{m,T_{j}^{\sigma }}^{\,f}\tag{25}\\&\forall j,m,\quad o_{m,T_{j}^{\sigma }}^{\,f}\le o_{j}^{\sigma }+M\cdot (1-x_{j,m})\tag{26}\\&\forall m,\forall \sigma _{j}\in \mathcal S^{app},\quad a_{j}^{\sigma }-M\cdot \left ({1-x_{j,m} }\right)\le a_{m,R_{j}^{\sigma }}^{\,f}\quad \tag{27}\\&\forall m,\forall \sigma _{j}\in \mathcal S^{app},\quad a_{m,R_{j}^{\sigma }}^{\,f}\le a_{j}^{\sigma }+M\cdot \left ({1-x_{j,m} }\right)\quad \tag{28}\\&\forall m,\forall \sigma _{j}\in \mathcal S^{sec},\quad a_{j}^{\sigma }-M\cdot \left ({1-x_{j,m} }\right)\le a_{m,N_{j}^{\sigma }}^{\,f}\quad \tag{29}\\&\forall m,\forall \sigma _{j}\in \mathcal S^{sec},\quad {a}_{m,N_{j}^{\sigma }}^{\,f}\le a_{j}^{\sigma }+M\cdot (1-x_{j,m})\tag{30}\\&\forall \sigma _{j}\in \mathcal S^{app},\quad {a}_{j}^{\sigma }\le D_{j}^{\sigma }\tag{31}\end{align*}$$

Constraints (25) and (26) guarantee that the start time $o_{j}^{\sigma }$ of a signal $\sigma _{j}$ equals to the start time $o_{m,T_{j}^{\sigma }}^{\,f}$ of the frame $f_{m}$ in which the signal is packed into on its sender $T_{j}^{\sigma }$ . Similarly, (27) and (28) guarantee that the finish time $a_{j}^{\sigma }$ of an automotive control signal $\sigma _{j}\in \mathcal S^{app}$ equals to the finish time $a_{m,R_{j}^{\sigma }}^{\,f}$ of the frame $f_{m}$ in which the signal is packed into on its receiver. Given that the key signal $\sigma _{j}\in \mathcal S^{sec}$ is not required to have a MAC verification processing, (29) and (30) guarantee that its finish time $a_{j}^{\sigma }$ equals to the finish time $a_{m,N_{j}^{\sigma }}^{\,f}$ of the frame $f_{m}$ in which it is packed into on the last network link resource $N_{j}^{\sigma }$ that transmits it. And in the final of this part, (31) specify that the finish time of each automotive control signal is within its deadline.

(c) Tasks Scheduling

$$\begin{align*}&\forall \tau _{i}\in \Gamma ^{app},\quad o_{i}^{\tau }+C_{i}^{\tau }\le D_{i}^{\tau }\tag{32}\\&\forall g, \forall \tau _{i},\tau _{i^{'}}{\in \Gamma }_{g}, i\!\ne \! i^{'}, \alpha \!\in \! \left \{{\!0,\ldots,lcm\left ({P_{i}^{\tau },P_{i^{'}}^{\tau } }\right) / {P_{i}^{\tau }\!-\!1} \!}\right \}, \\&\beta \in \{0,\ldots,lcm{(P_{i}^{\tau },P_{i^{'}}^{\tau })} / {P_{i^{'}}^{\tau }-1}\} \\&\alpha \cdot P_{i}^{\tau }+o_{i}^{\tau }+C_{i}^{\tau }\le \beta \cdot P_{i^{'}}^{\tau }+o_{i^{'}}^{\tau }+M\cdot \left ({1-\theta _{i,i^{'}}^{\alpha,\beta } }\right)\tag{33}\\&\beta \cdot P_{i^{'}}^{\tau }+o_{i^{'}}^{\tau }+C_{i^{'}}^{\tau }\le \alpha \cdot P_{i}^{\tau }+o_{i}^{\tau }+M\cdot \theta _{i,i^{'}}^{\alpha,\beta }\tag{34}\end{align*}$$

Constraint (32) determines that the finish time of a task $\tau _{i}$ , i.e., the sum of its start time $o_{i}^{\tau }$ and execution time $C_{i}^{\tau }$ is within its deadline. Constraints (33) and (34) ensure that two tasks never preempt each other on any PE resource, where the variable $\theta _{i,i^{'}}^{\alpha,\beta }$ is used for switching.

(d) Data dependency

$$\begin{align*}&{\forall \lambda _{r}\in \Lambda ^{sec}U \Lambda ^{app},\quad \left ({\sigma _{j},\tau _{i} }\right)\in G}_{r}^{app},\quad a_{j}^{\sigma }\le o_{i }^{\tau }\quad \tag{35}\\&{\forall \lambda _{r}\in \Lambda ^{app},\quad \left ({{\tau _{i},\sigma }_{j} }\right)\in G}_{r}^{app},\quad a_{i}^{\tau }\le o_{j}^{\sigma }\tag{36}\end{align*}$$

Constraints (35) and (36) guarantee that the predecessor must complete its execution before all its successors start in an automotive control or key authentication application.

$$\begin{align*} \forall m,\quad \varphi _{m}^{\,f}=&\left \lceil{ \frac {o_{m,T_{m}^{\,f}}^{\,f}}{P_{int}} }\right \rceil \tag{37}\\ \forall m,\forall l_{g}\in L^{net},\quad \left \lceil{ \frac {a_{m,g}^{\,f}}{P_{int}} }\right \rceil\le&\varphi _{m}^{\,f}\tag{38}\end{align*}$$

According to the authentication mechanism, an automotive control frame is accepted and stored awaiting to be authenticcated 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 frame $f_{m}$ , (37) first computes the number of the time interval $\varphi _{m}^{\,f}$ in which its MAC key is released. And then, (38) guarantees that the start time of a frame on its sender and the finish time of the frame on any one of the used network link resource belong to the same time interval.

$$\begin{align*}&\forall g,f_{m}\in \left \{{\mathcal F_{g}\thinspace \vert \thinspace {Z_{g}^{\,f}=1}}\right \},\forall \tau _{i}\in \left \{{\Gamma _{g}^{sec}\thinspace \vert \thinspace {V_{i}^{\tau }=T_{m}^{\,f}}}\right \}, \\&\mathop {\,f}\limits _{o m, g}\ge a_{i}^{\tau }+ \varphi _{m}^{\,f}\cdot P_{int}-M\cdot \left ({1-r_{m,g}^{\,f} }\right)\tag{39}\end{align*}$$

Besides, an automotive control frame will be available to its receiver after the verification task for its MAC key is completed. Therefore, (39) guarantee that the start time of the verification operation of a frame $f_{m}\in \left \{{F_{g}\thinspace \vert \thinspace {Z_{m}^{\,f}=1}}\right \}$ on its receiver must later than the finish time of the verification task for its MAC key, where $\Gamma _{g}^{sec}$ denotes the set of the key verification tasks executed on PE $l_{g}$ .

$$\begin{align*}&{\forall l}_{g}\in \mathcal L^{PE}, f_{m}\in \left \{{F_{g}\thinspace \vert \thinspace {Z_{m}^{\,f}=1}}\right \},\quad \forall {\tau _{i}\in \Gamma }_{g}, \\&\alpha \!\in \! \left\{{0,\ldots,\frac {lcm\left ({P_{i}^{\tau },P_{m}^{\,f} }\right)}{P_{i}^{\tau }}-1,}\right\}, \\&\beta \left\{{\!\in \! 0,\ldots,\frac {lcm\left ({\! P_{i}^{\tau },P_{m}^{\,f} \!}\right)}{P_{m}^{\,f}}\!-\!1}\right\} \\&\alpha \cdot P_{i}^{\tau }+o_{i}^{\tau }+C_{i}^{\tau }\le \beta \cdot P_{m}^{\,f}+o_{m,g}^{\,f}+M\cdot \left ({1-\eta _{g,i,m}^{\alpha,\beta } }\right) \\&+\,M\cdot \left ({1-\mu _{m,g}^{\,f} }\right)\tag{40}\\&\beta \cdot P_{m}^{\,f}+o_{m,g}^{\,f}+c_{m,g}^{\,f}\le \alpha \cdot P_{i}^{\tau }+o_{i}^{\tau }+M\cdot \eta _{g,i,m}^{\alpha,\beta } \\&+\,M\cdot \left ({1-\mu _{m,g}^{\,f} }\right)\tag{41}\end{align*}$$

Constraints (40) and (41) ensure that the frame verification tasks and other tasks never preempt each other on any PE resource during execution, where the variable $\eta _{g,i,m}^{\alpha,\beta }$ is used for switching.

(e) End-to-end latency

$$\begin{equation*} \forall \rho _{\varepsilon }\in \mathcal {FP}^{app}, a_{Des_{\varepsilon }^{\rho }}^{\tau }-o_{Src_{\varepsilon }^{\rho }}^{\tau }\le D_{\varepsilon }^{\rho }\tag{42}\end{equation*}$$

Constraint (42) ensure that the end-to-end delay must less than the deadline for each function path, where ${Des}_{\varepsilon }^{\rho }$ and ${Src}_{\varepsilon }^{\rho }$ are the source and sink object of the function path ${\rho _{\varepsilon }\in \mathcal {FP}}^{app}$ , respectively.

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:

$$\begin{equation*} \mathrm {Maximize} \sum \nolimits _{\forall {\rho _{\varepsilon }\in \mathcal {FP}}^{app}} {D_{\varepsilon }^{\rho }+o_{Src_{\varepsilon }^{\rho }}^{\tau }-a_{Des_{\varepsilon }^{\rho }}^{\tau }}\tag{43}\end{equation*}$$

We can alternatively minimize the consumption of network bandwidth, therefore improving extensibility:

$$\begin{equation*} \mathrm {Minimize}\sum \nolimits _{\forall \mathrm {\,f}_{\mathrm {m\in }}\mathrm {\,f}} \sum \nolimits _{\mathrm {l}_{\mathrm {g}}\mathrm {\in }\mathrm {L}^{\mathrm {net}}} \mathrm {c}_{\mathrm {m,g}}^{\mathrm {\,f}} / \mathrm {P}_{\mathrm {m}}^{\mathrm {\,f}}\tag{44}\end{equation*}$$

SECTION VI. 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 TTEthernet-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 consider the Infineon TriCore, a widely used automotive 32-bit microcontroller, as a representative platform. A MAC generation/verification operation takes $11~\mu$ s on Tricore at 180 MHz [31].

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 (1) pack the signals generated by the same task into a frame, and (2) 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.

A. Types of Graphics Case Study: An Advanced Control System

We consider a case study from the literature [32], a set of advanced automotive control applications including adaptive cruise control (ACC), electric power steering (EPS), and traction control (TC). There are 24 tasks and 18 signals, 3 of which are multicast signals.

Tables 2 and 3 show the periods and the worst-case execution time of tasks (in microseconds) and the sizes of Signals (in bits). The hardware platform consists of 6 ESes connected via a switched Ethernet network. The speeds of the communication links are 100 Mbps.

TABLE 2 Tasks of the Advanced Automotive Control System

TABLE 3 Signals of the Advanced Automotive Control System

Table 4 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 authentica-tion mechanism overheads and constraints.

TABLE 4 Results of the Advanced Automotive Control System

Specifically, 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. These demonstrate that the introduction of authentication function hardly affects the timing performance of systems after using the proposed MILP-S. On the other hand, when the extensibility is taken as optimization objective, the bandwidth used by MILP-S is greater than that of the non-security-aware scheduling optimization approaches MILP-NS and ASAP-NS. This is because that each sender needs to transmit the released key in each time interval after using the TESLA authentication mechanism, and consumes more bandwidth. Even so, for safety-critical automotive systems, a small portion of their bandwidth resources is still worth achieving security.

B. Scalability Analysis

1) System Configurations

To assess the scalability of the proposed approach, we generated a set of synthetic applications and network topologies based on realistic automotive system cases. Specifically, the period of tasks and signals are varied among the range [5, 10, and 20 ms]. The average ratio of deadline to period of each time-sensitive function path is 0.7. The speeds of the communication links are set to 100 Mbps. Two broad classes of experiments are conducted as follows.

1. First, we evaluate the performance of the proposed scheduling approach on different system scales. In the figures of results, the horizontal axis marks the number of PEs, which denotes the scale of the experiments, as the number of PEs and the number of tasks and signals simultaneously grow. The number of PEs on the horizontal axis is varied among the range [4], [8], [16], considering that a typical distributed automotive system such as infotainment or chassis is composed of less than 15 PEs. When the number of PEs is 16, the number of automotive applications, time-sensitive function paths, tasks and signals are 18, 36, 65 and 190, respectively. The average cost of a task is 2 ms and the average size of a signal is 32 bytes.

2. Second, we evaluate the performance of the proposed scheduling approach on systems with different numbers of time-sensitive function paths. We increase the number of time-sensitive function paths while keeping the same hardware architecture. Specifically, the number of time-sensitive function paths is varied among the range [5], [10], [11], [24]. The number of PEs is 8. The average cost of a task is 0.42 ms and the average size of a signal is 39 bytes.

2) Results and Disscussion

a: Increased Scales of System

Fig. 5 depicts the comparison results of MILP-S, MILP-NS and ASAP-NS with respect to laxity metric function on different system scales. It is shown that MILP-S can guarantee the schedulability of systems with authentication mechanism overheads and constraints in all experiments. In addition, the laxity of all time-sensitive function paths obtained by MILP-S is average 15% lower than that of MILP-NS, and only 9% lower than that of ASAP-NS. These demonstrate that the introduction of authentication function hardly affects the timing performance of systems after using the proposed MILP-S.

FIGURE 5.

Laxities of the scheduling approaches versus number of PEs.

Fig. 6 depicts the comparison results of MILP-S, MILP-NS and ASAP-NS with respect to extensibility metric function on different system scales. The SD is the total fraction of the network bandwidth that is required by all signals. It can be calculated by $SD= \sum \nolimits _{\sigma _{j}\in \mathcal {S}^{app}} \sum \nolimits _{l_{g}\in \{L^{net}\vert \left ({\sigma _{j},l_{g} }\right)\in \mathcal {U}\}} W_{j}^{\sigma } / {(V_{g}^{l}\cdot P_{j}^{\sigma })}$ . First, it is shown that MILP-S returns the biggest bandwidth consumption that is approximately 3.4 times SD; and the bandwidth consumptions of ASAP-NS and MILP-NS are 1.9 times and 1.6 times SD, respectively. Moreover, as the number of PEs increases, the differences in bandwidth consumption between the security-aware MILP-S and non-security-aware MILP-NS and ASAP-NS grow slightly. This is because as the number of PEs increases, the authentication function requires more bandwidth resource to transmit the keys they release.

FIGURE 6.

Bandwidth consumption ratios of the scheduling approaches versus number of PEs.

Furthermore, Fig. 7 shows the runtime of the MILP solver for each of these experiments. In our experiments, we set a 3600 s time limit. For both optimization metrics, the solver is able to find the optimal solution within the time limit when the number of PEs is less than 16; and return a feasible solution when the number of PEs is 16.

FIGURE 7.

Runtime of the MILP solver versus number of PEs.

b: Increased Number of Function Paths

Fig. 8 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. First, it is shown that MILP-S can still guarantee the schedulability of systems with authentication mechanism overheads and constraints. Second, the laxity of all function paths obtained by MILP-S is average 17% lower than that of MILP-NS, and only 12% lower than that of ASAP-NS.

FIGURE 8.

Laxities of the scheduling approaches versus number of paths.

Similarly, Fig. 9 depicts the comparison results of MILP-S, MILP-NS and ASAP-NS with respect to extensibility metric function on systems with different numbers of time-sensitive function paths. It is shown that MILP-S returns the biggest bandwidth consumption that is approximately 3.3 times the SD. And the bandwidth consumptions of ASAP-NS and MILP-NS are 1.8 times and 1.3 times SD, respectively. In addition, as the number of paths increases, the differences in bandwidth consumption between the security-aware MILP-S and non-security- aware MILP-NS and ASAP-NS decrease. This is because when the number of function paths grows and the number of PEs remains constant, each PE produces more signals, thus providing more possibility of optimization of frame packing.

FIGURE 9.

Bandwidth consumption ratios of the scheduling approaches versus on number of paths.

Fig. 10 shows the runtime of the MILP solver for each experiment. For both optimization metrics, the solver can find the optimal solution within the time limit in all cases. These demonstrate the effectiveness and efficiency of the proposed approach.

FIGURE 10.

Runtime of the MILP solver versus number of paths.

SECTION VII. Conclusion

In this paper, we have proposed an approach to address both the information security and functional safety in the scheduling design of TTEthernet-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 optimiza-tion problem of TTEthernet-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 bandwidth consumption (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. In future work, we plan to implement encryption mechanism on TTEthernet for protecting the data confidentiality. Meanwhile, we will extend our optimization framework to include all cryptographic operations of the encryption mechanism.

Appendix

The list of symbols and constant parameters in the MILP formulation are summarized in Tables 5 and 6 respectively.

TABLE 5 The Notations of Elements and Sets

TABLE 6 The Notations of Constant Parameters