ScalOTA: Scalable Secure Over-the-Air Software Updates for Vehicles

The message abstractions and symbols used throughout the paper are summarized in the next table for the reader’s convenience.

Figure 1 depicts the architecture of ScalOTA. The architecture is composed of four main parts: the manufacturer’s Software Update Director (SUD), the supplier chain of Image Repositories, the EV Station Manager (ESM), and the vehicles.

The Software Update Director (SUD) is an entity that is owned by the OEM to control the updates of the entire fleet. For this, the SUD retains an inventory database of the entire fleet information and vehicle specifications, versions, and associated suppliers. The SUD also calculates version dependencies and conflicts to generate safe update lists. The SUD contains roles that represent entities inside the SUD with different responsibilities; when a role writes metadata it always signs it with its own key(s). The roles are: targets—stores the various updates’ information; snapshot—creates metadata describing stable software bundles; timestamp—responsible for applying timestamps to targets’ and snapshot’s metadata, which is used to know if there are new updates; and root—acts as a Certificate Authority (CA) for the other roles. Image Repository (IR). This is a database where all OEM-associated software is stored, including packages developed in-house and from N-Tier suppliers. The Update Distribution Broker (UDB) is a network of vehicle update stations (UStations), e.g., associated with EV charging stations, and operated by a new entity we call update operator. The UDB acts as a CA for its stations, such that the vehicles can attest the owner of each UStation. Each UStation collects identifiers about vehicle models in its corresponding zone, for which updates are downloaded and cached. The UStation pulls from the UE updates corresponding to the identifier, that by its turn subscribes to the corresponding updates provided by the manufacturer’s SUD, through the MQTT pub/sub protocol. The UE then redirect the update downloads to the designated UStation. The UE can optimize the cache of the software updates on zonal-basis. It can also predict update usage, i.e., if an update $\Delta$ becomes available for a vehicle type that is frequently seen in its UStations, then it can preemptively publish it. A Vehicle is composed of a primary and several secondary ECUs, for which software updates are continuously needed. The Supplier is the main software update producer. It stores updates in local or manufacturer-owned Image Repository (IR). As explained later, a direct supplier (called Tier 1) can securely delegate software to other third-party (Tier 2 or Tier 3) suppliers. Finally, the Time Server is a trusted source of time for all elements considered.

This section presents the ScalOTA protocol steps for update installation and publishing to the update stations.

This section presents the ScalOTA protocol steps followed by the vehicles to download software updates.

In this step, the vehicle attempts to check if there are any software updates to download and install. Nevertheless, the vehicle cannot do this with on its own because of the potential dependencies bundled by the OEM. This is common in automotive OTA updates, where the OEM director is in charge of deciding the updates to be installed for each vehicle.

To do this in ScalOTA, the primary ECU sends a periodic report $R$ about the current status $\gamma=\langle\mathsf{Status},R,\tau_{\gamma}\rangle_{\sigma}$ of the software versions installed on the vehicle to the OEM’s SUD. The sending frequency can be once per week, day, or even upon every vehicle ignition, but it must be defined for freshness reasons. The primary prepares $\gamma$ as follows: it adds to a list $R$ the timestamp meta-data $\tau_{e}$ corresponding to all the vehicle ECUs’ versions that are currently installed. If $R$ is the same as the previous sent Status message, the primary sends the hash digest of $R$ instead. The primary also prepares $\tau_{\gamma}=(t_{\gamma},v_{\gamma})$ by updating its timestamp $t_{\gamma}$ and using the last Status message’s version $v_{\gamma}$ it has. Finally, the primary signs $\gamma$ by adding its signature $primary$ to $\sigma$ and sends it to the SUD.

In the case where a secondary ECU does not trust the primary, which has the only communication interface to the outside world, the secondary has to sign the $\tau_{e}$ by itself, and relays it through the primary while preparing $\sigma$. This has the advantage that the primary cannot lie to the OEM about the last versions installed on the secondary. In addition, the secondary has to send $\tau_{e}$ at a fixed frequency, e.g., once per week, day, or even upon every vehicle ignition, so that it can raise an alert flag to the driver, when the primary delays or discards the OEM’s replies of the Status message.

When the SUD receives $\gamma=\langle\mathsf{Status},R,\tau_{\gamma}\rangle_{\sigma}$ from the primary ECU of vehicle $V$, it first validates its authenticity and hash integrity, which occurs similar manner as before. The exception is freshness validation: if $R$ has been previously seen by the SUD, freshness is ensured if $t^{last}_{\gamma}<t_{\gamma}$ and $v^{last}_{\gamma}\geq v_{\gamma}$; where $\tau_{\gamma}=(t_{\gamma},v_{\gamma})$, and $v^{last}_{\gamma}$ and $t^{last}_{\gamma}$ correspond to the last retained Status message’s meta-data at the OEM’s SUD. The validation of $v_{\gamma}$ is important since the vehicle should never have a newer version than the OEM. If $\gamma$ is invalid, the SUD will discard the message, and consequently, the response to the $Status$ message will be delayed, and the ECUs at the vehicle will raise an alert to the driver.

Now, the SUD is ready to prepare for the reply $\gamma^{\prime}=\langle\mathsf{Status},R^{\prime},\tau_{\gamma^{\prime}}\rangle_{\sigma}$. This is done by figuring out all the bundles’ meta-data $(\Delta_{1},\Delta_{2},..,\Delta_{k})$ in the Fleet Repository that are in the future of those reported in $R$. If none, i.e., $R$ has been seen before, $R^{\prime}$ is set to $R$ again. However, this time with a new timestamp $t_{\gamma}^{\prime}$ and incremented Status message’s version $v_{\gamma}^{\prime}=v_{\gamma}+1$ in $\tau_{\gamma^{\prime}}=(t_{\gamma}^{\prime},v_{\gamma}^{\prime})$, so that the ECUs can assert the freshness of Status message. (Recall that each update $\delta$ has another $\tau_{\delta}$ that is used to validate the freshness of the update.) Finally, the SUD’s timestamp role signature is added to $\sigma$, and $\gamma^{\prime}$ is sent back to the primary ECU.

In the case where secondary ECUs do not trust the primary, the SUD has to verify each ECU’s timestamp $\tau_{e}$ in $\gamma$, and then sign each bundle $\Delta$ destined to $e$. This allows the latter to verify the bundle instead of the primary ECU.

When the vehicle’s primary ECU receives the Status reply $\gamma^{\prime}=\langle\mathsf{Status},R^{\prime},\tau_{\gamma}^{\prime}\rangle_{\sigma}$ from the SUD, it validates its authenticity and hash integrity, as usual. Freshness validation is however done through asserting that $t^{last}_{\gamma}<t^{\prime}_{\gamma}$ and $v^{last}_{\gamma}\leq v^{\prime}_{\gamma}$, where $\tau_{\gamma}^{\prime}=(t^{\prime}_{\gamma},v^{\prime}_{\gamma})$, and $v^{last}_{\gamma}$ and $t^{last}_{\gamma}$ correspond to the last retained Status message’s meta-data at the primary. Note that its okay if the primary did not receive some $\gamma$ versions between $v^{last}_{\gamma}$ and $v^{\prime}_{\gamma}$, since any recent $\gamma$ version will include all the bundles with their dependencies (again other bundles). Thus, it is sufficient for the primary to download the last bundles, in $\gamma$, it does not have, and thus discard any (delayed) $\gamma^{\prime\prime}$ message whose $t^{\prime\prime}_{\gamma}<t^{last}_{\gamma}$.

Afterwards, if $\gamma^{\prime}$ is valid, the primary retains all the meta-data manifest bundles reported in $R^{\prime}$, in a pending state, until it connects to an update station to download them. However, if $v^{last}_{\gamma}=v^{\prime}_{\gamma}$, then $R^{\prime}$ has been seen before and, therefore, no new updates are available. At this stage, vehicles that do not wish to download the updates through the update stations of the UDB can still download them via typical wireless, e.g., cellular communication.

In the case where a secondary ECU $e$ does not trust the primary, the latter must send the relevant bundles of $e$, together with $\tau_{\gamma}^{\prime}$, to verify them by itself. If this failed, or got delayed to reach $e$, or even the primary has not received a valid $\gamma^{\prime}$ on time, any of these ECUs can raise an alert to the driver.

When the vehicle stops at an update station, e.g., while charging at an integrated EV station, operated by the update broker UDB, it tries to connect, preferably, via a fast wired interface (e.g., an Ethernet cable that is bundled with the EV electric cable or a Powerline cable [32]), or via other available communication media, like Wi-Fi. Then, the primary exchanges its public key, signed by its private key, with the update station to authenticate it—assuming that the vehicle already has a valid account with the UDB operator. If authentication succeeded, the primary sends all its pending meta-data bundles to the update station. Recall that each bundle $\Delta^{\prime}=\langle\mathsf{Bundle},D^{\prime},\tau^{\prime}_{\Delta^{\prime}}\rangle_{\sigma}$ may include many meta-data manifests like $\mu^{i}_{\delta_{i}}=\langle\mathsf{Manifest},l_{\delta_{i}},\theta_{\delta_{i}},\tau_{\delta_{i}}\rangle_{\sigma}$ for multiple updates $\delta_{i}\in D^{\prime}$, where the update integrity details are in $\theta_{\delta_{i}}=(\mathsf{Meta},h_{\delta_{i}},e_{\delta_{i}},s_{\delta_{i}},d_{\delta_{i}})$. The update station uses these details to identify the corresponding image $\delta_{i}$, and thus pushes it to the primary ECU if it is already cached. Otherwise, the update station have to download the update on the spot in the cases of cache miss or unknown vehicle model, as discussed in the following. Finally, the primary validates the hash digest of $\delta_{i}$ against the the manifest’s digest $h_{\delta_{i}}$, thus asserting its integrity.

Prior to pushing updates from the primary to secondary ECUs, two components are required. The first is an in-vehicle communication medium that supports the basic communication and security abstractions used in the protocol above. For simplicity, we consider an Automotive Ethernet [27] network between the primary and secondaries. Considering other networks is orthogonal to ScalOTA since we consider the communication channels as a black-box. The second component is a Flash Bootloader tool at the secondaries, which is used to handle the received updates and install them. The Flash Bootloader is assumed to have a running daemon that has a defined API to be able to communicate with other processes over the network, e.g., with the primary ECU. To avoid pedantic details, we assume that these tools are immutable (i.e., are never updated).

We differentiate between two cases for pushing the updates from the primary to a secondary ECU, considering whether the secondary trusts the primary or not.

Trusted Primary. Assuming the primary is trusted, it can handle the entire software download process as specified in Steps 6-9 above, on behalf of the secondary. The secondary only need to do partial verification: verify the key of the primary ECU, i.e., $primary\in\sigma$, and the update image against the received hash $h_{\delta_{i}}$ in the meta-data $\theta_{\delta_{i}}=(\mathsf{Meta},h_{\delta_{i}},e_{\delta_{i}},s_{\delta_{i}},d_{\delta_{i}})$ of the manifest $\mu^{i}_{\delta_{i}}$. It may also perform basic sanity checks, e.g., error correction or erasure code. If these are valid, the Flash Bootloader daemon installs the update locally and reboots the secondary ECU if needed.

Untrusted Primary. An untrusted primary may lead to integrity or availability issues (and confidentiality if considered). It could violate integrity by forging the software update images or manifests. This would require the secondary to do a full verification, which means verifying all the encapsulated messages $\Delta$, $\mu_{\delta}$ $\tau$, $\theta$, and $\sigma$ as the above in Steps 6-9. On the other hand, the primary may simply delay or drop the updates destined to the secondary. To address this, the secondary’s Flash daemon has to send the Status message following a pre-defined frequency, as discussd in Step 6 and 8, and then raise an alert if no valid responses are received on time. This ensures that the primary could neither delay or discard the received updates from the OEM beyond the pre-defined period (e.g., defined on safety basis), nor tampering with their content.

As described in the protocol in Step 9, the vehicle can start downloading the update images once it connects to an update station. However, given the storage capacity of the cache at update stations as well as the mobility patterns of similar vehicle models, an update images may or may not be available at the update station for immediate download. We, thus, consider three interesting cases: Cache Hit, Cache Miss, and Unknown Vehicle, discussed below.

Cache Hit. The update station has local caches for the required updates. This means that the UDB’s Update Engine has already pushed the updates to this station, as a result of a previous access that had occurred by a vehicle model requiring the same software. The primary can thus download the software images without any delays, i.e., via a wired connection.

Cache Miss. The update station does not have the update images requested by the vehicle. In this case, the vehicle’s software are assumed to be subscribed to the UDB’s Pub/Sub system, but it lost the images possibly because of the cache scheme. This can happen if any vehicle model that shares the same software had already passed by any update station operated by the UDB. The station can thus pull the updates from the UDB’s Update Engine. Although the network connecting the update station is assumed to be fast, e.g., using fiber optics, a cache miss will incur additional delays. Despite this, the download can be one order of magnitude faster than a cellular-based connection, as we show in Section VI.

Unknown Vehicle. The current vehicle’s model ($MID$) is unknown to the update station. In this case, the station sends a subscribe request to the UDB’s Update Engine. If the latter has the $MID$ subscription through another update station, it adds the current station to its list of destinations and sends to it the updates. On the other hand, if the Update Engine does not know about the $MID$ at all (i.e., this model has never been seen at any update station), the UDB subscribes to the OEM’s SUD and starts getting updates for that model. Therefore, the protocol is followed to make the updates of this car model supported at the UDB and at this very update station.

We have implemented ScalOTA in Python and C. The core footprint is 1700 LOC, excluding dependencies on external libraries, mainly TUF [34]. To evaluate ScalOTA, we used Emulab [11] that allowed us to use tens of real machines (8-cores with tens of GB of memory) without interference with other applications, while emulating network bandwidth and link delays as needed (via using extra delay machines). We ran our code on Ubuntu 20.04 VM/bare metal machines depending on the experiment. We set up three types of links with different characteristics for the three typical network use cases suggested in ScalOTA: cellular from the vehicles to the SUD or IR (5Mbps bandwidth, 30ms latency); cable between UStations and IRs (10Mbps bandwidth, 10ms latency), and direct Ethernet between the UStation and the vehicles (100Mbps bandwidth, 2ms latency). All measurements include computation times, such as verifying signatures.

ScalOTA is attractive to vehicle owners since it uses a direct connection to a UStation, i.e., fast and free, while currently users pay a costly cellular data plan whose speed and bandwidth are capped or limited depending on the region. In Figure 2 we show this ScalOTA’s advantages for the user by comparing the time taken to download 100MB of updates through cellular link and directly from the UStation. In this scenario, we consider all update requests to the UStation are hits. We can see that as we serve a larger percentage of updates from the UStations the time required for downloading the whole bundle decreases significantly, up to $\frac{1}{5}$ of the cellular network time. We discriminate the time used to fetch the manifests as these are always downloaded via the cellular network. This figure demonstrates the benefit of using dedicated links for the convenience of the user.

Figure 3 shows the bandwidth usage of downloading 100MB of updates over the different cache events considered in ScalOTA: hit, miss, and unknown (see Section V-E for details). Over the X-axis we present several scenarios, where a different percentage of the updates falls under (H)it, (M)iss, and (U)nknown events. We present a scenario where each event type is dominant, as well as more balanced scenarios. There are two takeaways from the figure: 1) the update distribution algorithm is paramount for the success of ScalOTA since we want to prioritize hits for maximum efficiency; 2) the download times between miss and unknown are very similar—this is due to the simplicity of establishing a subscription for a new model, which is the only difference between the processes. These results reinforce the effectiveness of ScalOTA, since in the worst case scenario—100% misses—the download speed is lower than using only the cellular network, while at the same time being free of charge.

In Figure 4, we show the impact the number of clients have on simultaneously downloading a 100Mb update bundle from the IR. The X-axis represents the percentage of the bundle that is served by UStations (the remainder is downloaded via the cellular network), while the various lines represent the number of clients simultaneously downloading the bundle. There is a clear degradation of service as the server gets overloaded with requests when there is little update coverage from the UStations. Using ScalOTA means drastically reducing the download times even during peak-usage events, since the load is distributed in the edge instead of centralized in the cloud. In fact, in a real-world scenario this result is expected to be even worse due to the network congestion and interference from multiple vehicles in close proximity degrading the link quality [4, 6].

We estimate the bandwidth cost theoretically since we faced some issues with Emulab while running hundreds of ScalOTA real instances within hundreds of VMs. The total update cost is usually paid by owners. It can be modeled as follows: $C_{T}=C_{up}+C_{bwdth}$, where $C_{up}$ is the software update service cost, often offered by the OEM, and $C_{bwdth}=r*(\Delta^{a}+\mu^{a})$ is the estimated bandwidth cost for software $a$ offered by a cellular operator, where $r$ is the telecommunication bandwidth rate. Notice that in state of the art solutions, a software update downloads $\Delta^{a}+\mu^{a}$ through the OEM’s SUD (that hosts the Image Repository in this case).

ScalOTA reduces the $C_{bwdth}$ part, which dominates the update service cost, as the vehicle only downloads $\mu^{a}$ through the SUD, and $\Delta^{a}$ via the update station. In his case, it is reasonable to assume the new update service to be equivalent to $C_{up}$, while the bandwidth cost from the update station is assumed to be free. Therefore the total bandwidth cost will be $C_{bwdth}=r*\mu^{a}$, and thus the relative bandwidth cost will be $\mu^{a}/(\Delta^{a}+\mu^{a})$. In our implementation of ScalOTA, the manifests occupy from a couple to less than a hundred kilobytes, thus confirming that $\Delta^{a}$ dominates the download cost, and therefore the savings obtained.