Code layout optimization for remote progressive code update for networked embedded systems

Many embedded systems need to have their firmware updated several times over the lifetime of the system after deployment. While those based on binary differencing suffer from unpredictable code shift, overwriting the entire firmware image may be too costly for those connected by slow, unreliable, or expensive data links. Firmware update over a network connection is an essential but expensive feature for many embedded systems due to the relatively high power consumption and limited bandwidth.;To address these problems, we propose RPFU (remote progressive firmware update), a new link-time technique that minimizes not only the size of patching scripts but also perturbation to the firmware memory, over the entire sequence of updates in the system's lifetime. We exploit high-level knowledge about the source program structure in laying out the binary image. Specifically, we show that by laying out code in increasing order of the Cyclomatic Complexity of the routines, the code will evolve with minimal Hamming distance between successive revisions as the code evolves. This code layout techniques have the benefits of minimizing bandwidth and power requirements for remote firmware update while also minimizing the wearing of the non-volatile program memory. Our techniques also consider both byte-writable and page-writable types of flash memory commonly found in modern microcontrollers.;Experimental results show our technique to reduce the energy consumption of firmware update by 30--42% over the state-of-the-art. Moreover, we also show that such code images run more efficiently on a demand code-paging system due to better locality.