Efficient Recovery of Software Updates Using Micro-Patches, 10-R6194

Background

Remote software over-the-air (OTA) updates for vehicles and other smart devices is a critical feature for today’s embedded systems. Unfortunately, updates are a high-value target for adversaries who seek to manipulate the vehicle’s software for their own purposes. Updates can also suffer from more mundane failures such as communication issues. When an update fails, the default solution is to resend the entire update, costing bandwidth, memory storage, and time. If the server and vehicle can communicate to identify which portions of the received update are usable, the update server only needs to retransmit those portions which are not usable, significantly reducing the data transmitted.

Approach

Through the research executed by Southwest Research Institute, instead of re-sending a failed update, an algorithm called double breakpoint search has been developed that enables the recovery of a failed update with significantly less overhead than re-sending. The algorithm allows the vehicle and server to identify the correctly transmitted segments and generate update micro-patches consisting of only the incorrect data.

Accomplishments

This solution can be applied to client projects that have a need for efficient transmission of updates or other files. Bandwidth constrained or communication denied environments would benefit from the efficiencies that were achieved. The solution has also demonstrated outstanding performance compared to algorithms used for generating patches for binaries located on the same device. Under assumptions about corruption types and their relative frequencies, this algorithm can remotely micro-patch a large binary with transmission cost equal to two-thirds the amount of corruption on average, plus a minimal communication overhead. This extraordinary performance was due to the nature of the modeled corruption. Insertion errors can be recognized and corrected with an incredibly efficient strategy, effectively reducing the communication cost by roughly the same number of bytes as the inserted corruption. Using this approach, update failures in bandwidth constrained scenarios can be recovered quickly and efficiently (see Fig 1).