I. INTRODUCTION

As many societal and economical requirements are put on automobiles, such as the improvement of driving performance and comfort, and the enhancement of both passive and active safety, more and more information and communication technology (ICT) contents are brought into the automotive electronic systems in the forms of software, network, and etc^[1]. As a result, automotive electronic systems are evolved from a close system to an open automotive cyber-physical system (ACPS) comprising of 70 to 100 electronic control units (ECUs) interconnected by several networks^{[2, 3]}.The openness of ACPS brings many new exciting experiences to the automobile users, while at the same time it imposes severe challenges in cyber-security to auto industry^{[4, 5]}. In ^{[6, 7]}, the authors showed that ACPS could be attacked through various interfaces, including direct and indirect physical access, short-range and long-range wireless channels. Cyber-security problems produce numerous adverse impacts to the driver, varying from the discomfort caused by malfunction of air conditioner to endangering of driver and passenger's life. Despite of these potential cyber-security vulnerabilities, functions of different criticalities (like safety-critical, function-critical and non-critical functions) are integrated into the same ECU in ACPS because of the pressure from size, weight, and power (SWaP) properties^[2]. As a consequence, the cyber-security threat is daily increasing for ACPS.

Controller area network (CAN) is the most widely employed real-time communication technologies in ACPS^[8], However, it is designed without the consideration of cyber-security. And in itself there are several cyber-security vulnerabilities^[5], such as CAN is a CSMA/CD protocol and CAN messages are being broadcasted to all ECU nodes on the network, which means that attacker can easily eavesdrop on the network and read the content of the messages; CAN message do not contain any information to authenticate its sender, thus attacker can potentially masquerade other ECU and send the messages, and etc. Due to the above vulnerabilities, CAN becomes the ideal attacking object for cyber-security attackers in ACPS^{[9, 10, 11, 12, 13]}. Taking the wide application of CAN in auto industry into account, huge price needs to be paid if the existing CAN specification is modified to protect it against the cyber security attackers. Therefore, the feasible security mechanism should be designed to be compatible with the current CAN specification. In this paper, the MAC-based security enhancement mechanism is integrated into the signal packing problem (SPP) of CAN^{[14, 15, 16, 17, 18]}, but the bandwidth overhead brought together makes it a necessity to find the tradeoff among the cyber-security, real-time and bandwidth utilization, as CAN's bandwidth is limited to 1 Mbps, and CAN message's maximal payload is limited to 8 bytes.

After the above analysis, we can find that SPP is a typical multi-objective optimization problem. In this paper, we set the requirement in cyber-security and real-time as the key constraints, because only as far as the requirements on these two non-functional properties are met, system's safety can be guaranteed. We set bandwidth utilization as the final optimization objective due to the limitation of CAN's bandwidth. Through this research, a security-aware signal packing (SASP) algorithm is proposed for CAN, and the minimization about the bandwidth's overhead brought by security enhancement is pursued to improve the bandwidth utilization of CAN and consequently to lower the cost for ACPS.

II. RELATED WORK

A. Related Work About the SPP of CAN

SPP can be seen as a special case of the bin packing problem, which is known to be a NP-hard optimization problem. There are several works addressing the SPP with heuristics, and bandwidth utilization and message's schedulability are the general optimization objective. Sandstrom et al.^[14] propose a next-fit-decreasing based heuristic packing algorithm to optimize the bandwidth utilization. Polzlbauer et al.^[15] define a metric of bandwidth utilization, and based on it a packing algorithm is designed to optimize both bandwidth utilization and message's schedulability. And later, Polzlbauer et al.^[16] present another extensibility-aware packing algorithm, which is based on the simulated annealing and the bandwidth utilization is its optimization objective.

Some other research tries to combine the SPP with message scheduling, which are the two key design problems of CAN. Saket et al.^[17] propose a best-fit-decreasing based heuristic to optimize the bandwidth utilization with deadline constraint. Pop et al.^[18] use the offset to order the signals, and a heuristic algorithm is given to improve message's schedulability. Zheng et al.^[19] }$and Zhu et al.^[20] integrate the design of CAN and ECU into the same optimization framework, and their objectives are end-to-end WCRT (Worst-case response time) and extensibility, respectively. However, cyber-security is not considered in the above works, while our work tries to find the balance among cyber-security, real-time and bandwidth utilization for SPP.

B. Related Work About the Security Enhancement Mechanisms of CAN

MAC-based authentication is a widely used security enhancement mechanism for CAN. Nilsson et al.^[10] raise a message authentication method with the compound MAC, which supports the split and assembly of MAC and can protect CAN from injection attack and tempering attack. Groza et al.^[11] give a light broadcasting authentication mechanism for CAN, which supports the MAC sharing among different nodes and the separate transmitting of MAC and message. Van Herrewege et al.^[12] propose a MAC-based backward compatible broadcast authentication protocol for CAN+. Han et al.^[13] combine the MAC-based authentication with the anonymous ID based message filtering to defend the CAN against injection and modification attack. However, the above works focus only on the security enhancement mechanisms, while our work integrates the security consideration into the multi-objective design optimization problem of CAN.

Lin et al. add both the MAC and counter into the CAN message to protect it from masquerade attack and replay attack, and then they also integrate the security mechanism into the design process of CAN in ^[21]. This latest work integrates the SPP of CAN and task allocation together, and a grouping mechanism is used to decrease the bandwidth overhead brought by the security mechanism, its optimization objective is the end-to-end WCRT. The difference between Lin et al's work and our work is in two aspects:

1) Lin et al. assume the same security requirement for all signals, while our work takes the software integration trend of ECUs into account and considers the different levels of security requirements for signals included in functions of different criticalities.

2) We set the bandwidth utilization as the optimization objective and treat the real-time requirement only as a constraint. As for CAN, only if the deadline is not violated for message, system's safety can be guaranteed, no matter what is the specific WCRT of message. While its bandwidth is quite limited, thus the bandwidth utilization should be improved as much as possible.

After the above analysis, we can come to the conclusion about the shortcomings of the related works:

1) Security is not considered enough in the design of CAN system, and the tradeoff among the security, real-time and bandwidth utilization is still an open question;

2) Different levels of security requirement for mixed criticality functions included in the same ECU is out of their consideration, which will cause the over-design of ACPS.

Aiming at compensating for the above shortcomings, we first give a mixed security signal model to formally describe the properties and requirement in security and real-time for signals included in mixed criticality functions. Based on that, an optimal MILP formulation based SASP is proposed for SPP to find the tradeoff among security, real-time and bandwidth utilization, where the bandwidth utilization is improved and the requirements on security and real-time are both met.

III. SYSTEM MODEL AND ASSUMPTIONS

A. Signal Model and Message Model

As shown in Fig. 1, this is a typical CAN-based ACPS. ECU set is indicated as: $ECU =\{E_{1}, E_{2}, \ldots, E_{k}, {\ldots}, E_{N} \}$. There is a signal set in ECU $E_{k}$ and it is indicated as: $S_{k}=\{s_{k, 1}, s_{k, 2}, {\ldots}, s_{k, i}, {\ldots}, s_{k, L}\}$, where $L\in {\bf N}^{+}$ and $L$ represents the number of signals in $S_{k}$. As the signal packing is only used for signals belonging to the same ECU, we omit the subscript $k$ of signal's notation to keep the signal model clear and simple, thus ${s_i}$ is used to indicate the signal for the following part of this paper, and $s\_own(i$, $k)$ is used to indicate the relation between ${s_i}$ and $E_{k}$. Real-time properties of signal can be described with a 3-tuple, ${s_i}:\left\{ {s\_period(i), s\_size(i), s\_deadline(i)} \right\}$, which indicates the period, transmission time and deadline of ${s_i}$, respectively, and we assume that the deadline equals to the period for all signals and messages.

Signals in $S_{k}$ need to be packed into messages before they can be transmitted on CAN, and how many messages will be generated depends on the used packing algorithm. The obtained message set in $E_{k}$ is represented as ${M_k} = \left\{ {{m_{k,1}},{m_{k,2}}, \ldots ,{m_{k,i}}, \ldots ,{m_{k,L'}}} \right\}$ where $L'\in {\bf N}^{+}$ and $L'\le L$. As shown in Fig. 1, the signal set contained in $E_{1}$ is: ${S_1}{\rm{ = }}\left\{ {{s_{{\rm{1, 1}}}}{\rm{, }}{s_{{\rm{1, 2}}}}{\rm{, }}{s_{{\rm{1, 3}}}}} \right\}$, and the corresponding message set is: $M_{1}$ = {$m_{1, 1}, m_{1, 2}$}, where $m_{1, 1}$ = {$s_{1, 1}, s_{1, 2}$}, $m_{1, 2}$ = {$s_{1, 3}$}. For the same reason described before, we also omit the subscript $k$ of message's notation for the following part of this paper, and use ${m{\_}own}(j, k)$ to describe the belonging ECU of ${m_j}$. Real-time properties of ${m_j}$ can be described with a 3-tuple: {${m{\_}period}(j)$, ${m{\_}size}(j), {m{\_}deadline}(j)$}, which indicate the period, transmission time and deadline of ${m_j}$, respectively. If signals with different periods are packed into the same message, there will be oversampling for signals with relatively bigger period. As a consequence, we assume that only the signals with the same period can be packed into the same message, which is a common assumption in other works such as ^{[15, 16, 21, 22]}. Period, transmission time and deadline of ${m_j}$ can be calculated with the following equations:

\begin{equation} \label{eq1} m\_period(j)=s\_period(i), s_i \in m_j, \end{equation}

(1)

\begin{equation} \label{eq2} m\_size(j)=\sum\limits_{s_i \in m_j } {s\_size(i)}, \end{equation}

(2)

\begin{equation} \label{eq3} m\_deadline(j)=s\_deadline(i), s_i \in m_j. \end{equation}

(3)

We assume that signals are packed according to the standard format of CAN, thus $m\_size(j)$ can be calculated from (4)^[23]:

\begin{equation} \label{eq4} {\rm m\_size}(j)=(55+10\cdot PL_j )\cdot \tau _{bit}, \end{equation}

(4)

where $\textit{PL}_{j}$ indicates the payload of ${m_j}$, and $\tau _{bit} $ indicates the time for CAN to transmit 1 byte. We assume the bandwidth of CAN is 500 kbps. The payload of CAN message varies from 1 bit to 8 bytes, and besides it there are other segments in message such as the ID and CRC, which are the cause of the bandwidth overhead in message itself. According to (4), the bandwidth overhead for CAN message can vary from 41.35 % to 97.8 %.

B. Attacker Model and Security Mechanism

The masquerade attack is potentially one of the most popular attacking approach on CAN^{[5, 21, 22]}, thus we mainly try to defend the CAN from the masquerade attack in this paper, and the MAC-based authentication mechanism is employed^{[10, 11, 12, 13, 21, 22]}. According to this mechanism, there is a public key shared between any two communicating ECUs. The message sender uses the key and the content of the message to generate a MAC $\textit{MAC}_{s}$, and $\textit{MAC}_{s}$ is also packed into the message together with the signals. After the message's transmission, another MAC $\textit{MAC}_{r}$ will be generated in the receiver node according to the content of the received message and the shared key, and a comparison between the $\textit{MAC}_{s}$ and $\textit{MAC}_{r}$ is done to authenticate the identity of the message sender and make sure that the content of the message is not modified by any other attacker. When the signals inside the same message have the same receiving ECU, they can share the same MAC to reduce the bandwidth overhead. And when there are different receiving ECUs for the same message, several MACs need to be generated and added into the message.

The security mechnism adopted in this paper is MAC-based, if the attacker does not have any prior knowledge about the MAC, guess of the MAC is quite random, and the success probability of the masquerade attack is 2$^{-H}$, where $H$ indicates the length of MAC (in bits). On the contrary, if we know the security requirement of the functions, (5) can be used to calculate the value of $H$, where $P$ represents the security requirement put on message.

\begin{equation} \label{eq5} H=\log _2 \frac{1}{P}. \end{equation}

(5)

C. Mixed Security Signal Model

The pressure from the SWaP property will gradually transform the ACPS into a mixed-criticality system, where several functions with different criticalities are integrated into the same ECU^[2]. The functional safety standard ISO 26262^[24] is proposed to give formal and quantitative description about the safety requirement (such as the dependability, security and etc) for automobiles, where the functions are classified into four categories with different levels of safety requirement (or criticality). Therefore, different levels of security protection are needed for signals included in functions with different criticality. In this paper, we extend the basic signal model described in Section III-A and propose a mixed-security signal model to formally describe the security requirement on signals.

We divide the functions in ACPS into two categories: {Fun}$_{HI}$ and {Fun}$_{LO}$, which have the high and low level of security requirement, respectively. The mixed-security signal model used to describe the signals with mixed-level of security requirements is described as ${s_i}{\rm{: }}\left\{ {s\_period{\rm{(i)}}, s\_size{\rm{(i)}}, s\_deadline{\rm{(i)}}, s\_mac{\rm{(i)}}} \right\}$, and ${s{\_}mac}(i)$ indicates the length of MAC needed to obtain the required level of security for ${s_i}$. For signals belonging to the functions with higher level of security requirement, their ${s{\_}mac}(i)$ is larger that that of the signals belonging to the functions with lower level of security requirement. We assume that the security requirement of the functions is known as in ^{[21, 22]}, so ${s{\_}mac}(i)$ can be calculated with (5). As far as we know the required security levels put on functions, this mixed-security signal model can be easily extended to describe the signals with more levels of security requirements.

IV. MILP FORMULATION OF THE PROPOSED SASP

SPP can be seen as a special case of the Bin Packing problem^{[14, 15, 16]}, where signals are the objects needed to be packed into the bins (messages). The size of bin equals to that of the message with maximal payload, and the number of bins equals to that of the signals. The difference is that signals may have different sizes, periods and different levels of security requirement, the packing rules need to be extended to further include the requirements on security and real-time, and the objective is changed to minimize the space utilization of bins (the sum of the bandwidth utilization of all messages). MILP is a powerful method that is often used to solve the bin-packing problem, thus we also formulate the SPP problem into a MILP problem and solve it with the CPLEX tool developed by IBM.

In this section, we first give all the constraints needed to be met by SASP, and then the objective function is explained. Tables I and II show all the known variables and the unknown variables requiring to be solved. The value of binary variable is 1 if the condition is true and 0 otherwise.

A. Constraints

For all the following constraints, $i$ and $i'$ are the labels for signals, $j$ and $j'$ are the labels for messages, and $k$ and $k'$ are the labels for ECUs.

1) Constraint on mapping relation between signals and messages

\begin{align} &\label{eq6} \forall s_i \in S_k , k, \notag\\ &\sum\limits_j {assign(i, k, j)} =s\_own(i, k)\times m\_own(j, k), \end{align}

(6)

\begin{equation} \label{eq7} \forall s_i \in S_k , k, {\kern 1pt}j, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}assign(i, k, j)\le taken(k, j). \end{equation}

(7)

Equation (6) indicates the constraint that each signal is exactly packed into only one message, (7) indicates the condition that if signal ${s_i}$ is packed into ${m_j}$ of $E_{k}$, if that is the truth, then $taken$ ($k, j)=1$.

2) Constraint on size and period of messages

According to the security mechanism proposed in this paper, two different parts are contained in message's payload: signals and the attached MACs. Equation (8) calculates the payload for ${m_j}$, which equals to the sum size of the included signals. Equation (9) indicates the constraint that the maximal payload of message should not be overloaded. Equation (10) calculates the transmission time of ${m_j}$.

\begin{align} &\label{eq8} \forall m_j \in M_k , k, \notag\\ &m\_size(j)=\sum\limits_i assign(i, k, j)\notag\\ &\quad\times (m\_mac\_t(j)+s\_size(i)), \end{align}

(8)

\begin{align} &\label{eq9} \forall m_j \in M_k , k, \notag\\ &\sum\limits_i {assign(i, k, j)\times \frac{m\_mac\_t(j)+s\_size(i)}{8}} \le capacity, \end{align}

(9)

\begin{equation} \label{eq10} \forall m_j , {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}m\_t\_size(j)=\frac{55+10\times \frac{m\_size(j)}{8}}{speed}. \end{equation}

(10)

According to our assumption that only signals with equal periods can be packed into the same message, message's period equals to that of the included signals. Thus, (11) and (12) are used to define the constraints about the period of signal and message.

\begin{align} &\label{eq11} \forall s_i \in S_k , k, j, \notag\\ &assign(i, k, j)\times s\_period(i)\le m\_period(j), \end{align}

(11)

\begin{align} &\label{eq12} \forall s_i \in S_k , k, j, \notag\\ &assign(i, k, j)\times m\_period(j)\le s\_period(i). \end{align}

(12)

3) Constraint on security

We consider about the signals with different levels of security requirement, and there are two possible packing strategies for them. Strategy 1 does not allow signals with different levels of security requirement to be packed into the same message, thus all the signals inside the same message have the same level of security requirement, and the security requirement of the message equals to that of the included signals. While Strategy 2 allows signals with different levels of security requirement to be packed into the same message, so we need to give all the included signals the high level of security protection, or else signals with relatively lower security requirement will become the weakness of the message, and the attacker can take advantage of them to attack the message successfully with lesser efforts. Consequently, message's security requirement is equal to the relatively higher security requirement of the included signals. Equation (13) indicates the required level of security for message:

\begin{align} &\label{eq13} \forall m_j \in M_k , k, \notag\\ &m\_mac\_t(j)=\max (assign(i, k, j)\times s\_mac(i)). \end{align}

(13)

After the constraint on period defined in (11) and (12) that only signals with the same period can be packed into the same message, (14) is further used in strategy 1 to enforce the constraint that only signals with the same level of security requirement can be packed into the same message, where $sm(i, i')$ indicates if the security requirement on ${s_i}$ and $s_{i'}$ are the same or not. As Strategy 2 allows signals with different levels of security requirement to be packed together, no constraint needs to be defined for it.

\begin{align} &\label{eq14} \forall s_i, s_{i^\prime} \in S_k , k, j, \notag\\ &assign(i, k, j)+assign(i', k, j)+sm(i, i^\prime)\neq 2. \end{align}

(14)

According to Strategy 1, signals with different levels of security requirement need to be divided into different messages even if their periods are the same, but those signals can be packed together originally when security is not considered. As a consequence, more messages will be generated in Strategy 1 comparing with Strategy 2, and it brings extra bandwidth overhead originated from the bandwidth overhead in message itself. However, although Strategy 2 allows more signals to be packed together, the length of MAC corresponding with the signals with relatively lower level of security requirement needs to be increased so as to guarantee the security of the obtained message. Consequently, Strategy 2 also causes extra bandwidth overhead. As the comparison experiment showed in Section V, Strategy 2 is better than Strategy 1 in bandwidth utilization, thus strategy 2 is used in SASP.

After the above analysis, the sum of MAC that is needed to obtain the required level of security for all signals included in ${m_j}$ can be calculated according to (15):

\begin{align} &\label{eq15} \forall m_j \in M_k , k, \notag\\ &m\_mac(j)=\sum\limits_i {assign(i, k, j)\cdot m\_mac\_t(j)}. \end{align}

(15)

4) Constraint on response time of message and signal

For constraint on response time of message, we first give the feasible priority assignment, and then the analysis about the blocking time and WCRT^{[22, 23]}.

a) Priority assignment

As each CAN message has a unique priority, (16) and (17) are used to indicate the constraint on priority relation of any two messages. Equation (18) indicates the transitive property of the priority relation among messages. For example, if $hp(j, j')=1$ and $hp(j', j")=1$, then $hp(j, j")=1$.

\begin{equation} \label{eq16} \forall m_j , {\kern 1pt}{\kern 1pt}{\kern 1pt}hp(j, j)=0, \end{equation}

(16)

\begin{equation} \label{eq17} \forall m_j , m_{j'} , k, j\ne j', {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}hp(j, j')+hp(j', j)=1, \end{equation}

(17)

\begin{align} &\label{eq18} \forall m_j , m_{j'} , m_{j"} , k, j\ne j', j'\ne j", \notag\\ &hp(j, j')+hp(j', j")-1\leq hp(j, j"). \end{align}

(18)

b) Blocking time analysis

As CAN messages are scheduled non-preemptively, $block(j)$ is used to indicate the blocking delay caused by other messages with lower priority for ${m_j}$, and it can be calculated with

\begin{align} &\label{eq19} \forall m_j , m_{j'} , {\kern 1pt}k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}block(j)=\max (m\_t\_size(j), \notag\\ &hp(j', j)\times m\_t\_size(j')). \end{align}

(19)

c) Response time analysis for message

Equation (20) is used to analyze the WCRT for ${m_j}$, the first part indicates the experienced blocking time, the second part indicates the transmission time of ${m_j}$ itself, and the third part indicates the preemption delay caused by other messages with higher priority. Equation (21) describes the schedulability constraint on message's response time:

\begin{align} & \forall m_j , m_{j'} , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}m\_r(j)=block(j)+m\_t\_size(j) \notag\\ &\quad+\sum\limits_{j'} taken(k, j)\times hp(j', j)\notag\\ &\quad\times \left\lceil {\frac{m\_r(j)-m\_t\_size(j)}{m\_period(j')}} \right\rceil \times m\_t\_size(j'), \end{align}

(20)

\begin{align} & \forall m_j , m_{j'} , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}block(j)+m\_t\_size(j)\notag \\ &\quad+ \sum\limits_{j'} taken(k, j)\times hp(j', j)\notag\\ &\quad\times \left\lceil {\frac{m\_r(j)-m\_t\_size(j)}{m\_period(j')}} \right\rceil \notag\\ &\quad\times m\_t\_size(j') \le m\_period(j). \end{align}

(21)

d) Response time analysis for signal

As Strategy 2 is used for SPP, signal's WCRT equals to that of the belonging message, so (22)-(23) defines the WCRT for signals. $W$ is a big constant needed for linearization.

\begin{equation} \label{eq22} \forall s_i \in S_k , k, j, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}m\_r(j)-W\times (1-assign(i, k, j))\le s\_r(i), \end{equation}

(22)

\begin{equation} \label{eq23} \forall s_i \in S_k , k, j, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}s\_r(i)\le m\_r(j)+W\times (1-assign(i, k, j)). \end{equation}

(23)

B. Objective Function

We set bandwidth utilization as the optimization objective of SASP, and it is calculated by summing up the consumed bandwidth of the occupied messages as described in (24), where the consumed bandwidth of each message is obtained by dividing its size by its period.

\begin{align} &\label{eq24} Objective:\forall m_j \in M_k , k, \notag\\ &\sum\limits_j {taken(k, j)\times \frac{m\_size(j)}{m\_period(j)}}. \end{align}

(24)

C. Conversion to Linear Constraints

For the described MILP formulation above, (14), (20), (21) and (24) are needed to be linearized before they can be solved by CPLEX tool^[22]. Equation (14) is an inequality of summation of three binary variables, and it can be linearized and replaced with the following equations:

\begin{align} &\label{eq25} \forall s_i , s_{i^\prime} \in S_k , k, j, \notag\\ &assign(i, k, j)+assign(i^\prime, k, j)-sm(i, i^\prime)\le 1, \end{align}

(25)

\begin{align} &\label{eq26} \forall s_i , s_{i^\prime} \in S_k , k, j, \notag\\ &assign(i, k, j)-assign(i^\prime, k, j)+sm(i, i^\prime)\le 1, \end{align}

(26)

\begin{align} &\label{eq27} \forall s_i , s_{i^\prime} \in S_k , k, j, \notag\\ &-assign(i, k, j)+assign(i\prime, k, j)+sm(i, i\prime)\le 1. \end{align}

(27)

Equations (20) and (21) can be linearized similarly in three steps. First, the ceiling function $\left\lceil x \right\rceil $ can be replaced by a non-integer variable $y$, and another constraint: $0\le y-x\le $ 1 is added. Second, the multiplication of two binary variables $x$ and $y$ can be replaced by a binary variable $z$, and then one constraint is added as: $x\times y=z$. And then $x\times y=z$ can be replaced by equivalent constraints: $x+y-1\le z, z\le x$ and $z\le y$. Third, the multiplication of one binary variable $x$ and one non-integer variable $y$ can be replaced by a non-integer variable $z$, and one constraint $x\times y=z$ is added. Next, $x\times y=z$ can be replaced by equivalent constraints: $0\le z\le y$ and $y-W\times $ $(1-x) \le z\le W\times x$. For example, (20) can be linearized and replaced with (28), and six more constraints described by (29) through (34) are added:

\begin{align} &\label{eq28} \forall m_j \in M_k , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}m\_r(j)=block(j)+m\_t\_size(j)\notag\\ &\quad+\sum\limits_{j'} {Z(j, j', k)\times m\_t\_size(j')}, \end{align}

(28)

\begin{align} \label{eq29} \forall m_j , m_{j'} , {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}0\le X(j, j')-{\kern 1pt}\frac{m\_r(j)-m\_t\_size(j)}{m\_period(j')}\le 1, \end{align}

(29)

\begin{equation} \label{eq30} \forall m_j , m_{j'} , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}0\le {\kern 1pt}taken(k, j)+hp(j', j)-1\le Y(j, j', k), \end{equation}

(30)

\begin{equation} \label{eq31} \forall m_j , m_{j'} , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}Y(j, j', k)\le {\kern 1pt}taken(k, j), \end{equation}

(31)

\begin{equation} \label{eq32} \forall m_j , m_{j'} , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}Y(j, j', k)\le hp(j', j), \end{equation}

(32)

\begin{equation} \label{eq33} \forall m_j , m_{j'} , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}0\le Z(j, j', k)\le Y(j, j', k), \end{equation}

(33)

\begin{align} \label{eq34} &\forall m_j , m_{j'} , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}Y(j, j', k)-W\notag\\ &\quad\times (1-X(j, j'))\le Z(j, j', k)\le W\times X(j, j'). \end{align}

(34)

Equation (24) also includes a multiplication of binary variable and one non-integer variable, and it can be linearized with the same approach as described above. Equation (24) can be replaced with (35) and two more constraints described by (36) and (37) are added:

\begin{equation} \label{eq35} {\rm Objective}:\forall m_j , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}\sum\limits_j {Z(k, j)}, \end{equation}

(35)

\begin{equation} \label{eq36} \forall m_j , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}0\le Z(k, j)\le \frac{m\_size(j)}{m\_period(j)}, \end{equation}

(36)

\begin{align} &\label{eq37} \forall m_j , k, {\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}\frac{m\_size(j)}{m\_period(j)}-W\times (1-taken(k, j))\notag\\ &\quad \le Z(k, j)\le W\times taken(k, j). \end{align}

(37)

V. EXPERIMENTAL ANALYSIS

Two sets of experiments based on signal sets from different sources are done to verify the effectiveness of the SASP by comparing it with the SPP algorithm proposed in ^[22]. The first signal set is a standard CAN signal set from the SAE^[25], which represents the requirement from the industry. And the second one is generated by Netcarbench 3.4^[26], which is a popular simulation tool for CAN Network. According to the ISO 26262, there are four levels of security requirement in ACPS, which are $L_{1}-L_{4}$, respectively, and we assume that the corresponding length of MACs are 2/4/6/8 (in bit). The MILP formulation of SASP is implemented in ILOG CPLEX Optimization Studio 12.6 from IBM, and the configuration of the PC running the experiments is: Intel(R) Core(TM)2 2.13 GHZ and 2 GB RAM.

A. Introduction About the Two Employed Signal Sets

1) SAE signal set

The SAE standard signal set is corresponding to a CAN network composed with 7 ECU nodes and 53 signals, signal's size varies from 1 bit to 8 bits, and signal's period varies from 5 ms to 1 000 ms, please refer to ^[25] for more details about this signal set. When security is not considered, the number of the obtained messages is 17 and the bandwidth utilization is 17.94 %.

2) Simulated signal set

The simulated signal set generated by Netcarbench 3.4 is for powertrain subsystem of ACPS, which is composed with 14 ECUs and 100 signals. When security is not considered, the number of the obtained messages is 61 and the bandwidth utilization is 39.36 %.

B. Exploration About the Two Candidate Packing Strategies

We explained in Section IV that there are two candidate packing strategies for SPP (Strategy 2 allows signals with different levels of security requirement to be packed together, while Strategy 1 does not allow that), thus we compared them based on the above two signal sets and the obtained results are shown in Tables III and IV, respectively.

We can find from Tables III and IV that both the obtained number of messages and the bandwidth utilization are smaller for Strategy 2 as compared to Strategy 1. The reason is that compared with the bandwidth overhead brought by increasing the length of MAC to guarantee the security of message, the bandwidth overhead brought by dividing signals with same period into different messages is much bigger. As we analyzed in Section III-A, the bandwidth overhead in CAN message varies from 41.35 % to 97.8 %. Therefore, Strategy 2 is better and employed in SASP from now on.

C. Efficiency of SASP

To show its efficiency, SASP is used to pack the signal sets when the level of security requirement is set as $L_{1}-L_{4}$ for signals, respectively, and the result is shown in Table V and Table VI. We can see from these two tables that along with the increasing of the security requirement, the obtained number of messages and the bandwidth overhead also increase. But as SASP is based on the optimal MILP formulation, even when the level of security requirement reaches $L_{4}$, the bandwidth overhead is limited to 5.17 % and 8.22 % for the two signal sets, respectively.

D. Comparison Between SASP and the SPP Algorithm Used in ^[21]

We did experiments to verify the effectiveness of SASP by comparing it with the SPP algorithm employed in ^[21]. The SPP algorithm used in ^[21] is also based on MILP formulation, and we modified its objective function to realize the comparison. As it assumes that the same security requirement is put for all signals, the packing result is the same with that of SASP under the same assumption. Please refer to Tables V and VI for detailed packing result. Tables VII and VIII give the detailed packing result of SASP for the two used signal sets. The runtime of the experiments on SAE signal set and the simulated signal set are about 0.5 s and 4 min, respectively.

We can come to two conclusions from packing result of SASP shown in Tables VII and VIII: 1) horizontal trend, the bandwidth utilization decreases as the percentage of signals with relatively low level of security requirement increases; 2) vertical trend, the bandwidth utilization increases as the widening of the gap between the two levels of security requirement.

From the obtained packing results described in Table V through Table VIII, we can get the conclusion that SASP is more efficient in bandwidth utilization as compared to the packing algorithm used in ^[21], and Figs. 2 and 3 show the obtained optimization extent in reducing the bandwidth overhead of SASP for the two used signal sets. According to the comparison result, when different combinations of security requirements are explored, the optimization extent of SASP in bandwidth overhead's reduction varies from 10.99 % to 17.8 % and 12.13 % to 49.4 % for the used two signal sets, respectively. With the increasing of the percentage of signals with relatively low level of security requirement, the optimization extent increases; and with the widening of the gap between the two levels of security requirement, the optimization extent also increases.

Taking all the experimental results into account, and considering the facts about the integration of functions with several criticalities into the same ECU and the percentage of functions with high security requirement are relatively low, the usefulness of SASP is obvious for ACPS.

We use MAC-based mechanism to defend CAN from masquerade attack, but this mechanism brings bandwidth overhead in the meantime. Thus, we formulate a MILP-based optimization problem to realize the tradeoff among the security, real-time and bandwidth utilization for the SPP of CAN. First, we give a new mixed-security signal model to formally describe the properties and requirement in security and real-time at the same time. And then, a MILP-based security-aware signal packing algorithm SASP is proposed, which can realize the optimization of the bandwidth utilization while meeting the requirements in both security and real-time. SASP is also compatiable with the existing CAN specification, which makes it feasible for implementation in real applications. Two sets of experiments based on signal sets from both the industry and simulation tool are implemented to compare the SASP with the state-of-the-art algorithm, and the effectiveness and efficiency of the SASP is showed.