Software systems are constantly changing. Patches to fix bugs and patches to add features are all too common. Every change risks breaking a previously working system. Hence administrators loathe change, and are willing to delay even critical security patches until after fully validating their correctness. Compared to off-line validation, on-line validation has clear advantages since it tests against real life workloads. Yet unfortunately it imposes restrictive overheads as it requires running the old and new versions side-by-side. Moreover, due to spurious differences (e.g. event timing, random number generation, and thread interleavings), it is difficult to compare the two for validation. To allow more effective on-line patch validation, we propose a new mechanism, called delta execution, that is based on the observation that most patches are small. ∆ execution merges the two side-by-side executions for most of the time and splits only when necessary, such as when they access different data or execute different code. This allows us to perform on-line validation not only with lower overhead but also with greatly reduced spurious differences, allowing us to effectively validate changes. We first validate the feasibility of our idea by studying the characteristics of 240 patches from 4 server programs; our examination shows that 77% of the changes should not be expected to cause large changes and are thereby feasible for ∆ execution. We then implemented ∆ execution using dynamic instrumentation. Using real world patches from 7 server applications and 3 other programs, we compared our implementation of ∆ execution against a traditional sideby-side on-line validation. ∆ execution outperformed traditional validation by up to 128%; further, for 3 of the changes, spurious differences caused the traditional validation to fail completely while ∆ execution succeeded. This demonstrates that ∆ execution can allow administrators to use on-line valPermission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
This work represents a new application of delta execution REF , which was originally devised for efficient on-line patch validation.
Efficient online validation with delta execution
ASPLOS
Computer Science