Method and system for generating a reverse binary patch

• US 8,365,160 B2
• Filed: 08/16/2010
• Issued: 01/29/2013
• Est. Priority Date: 06/26/2006
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Research In Motion Limited (Blackberry Limited)
• Inventors: Scian, Anthony F., Dahms, John F. A.
• Primary Examiner(s): Khatri, Anil
• Application Number:
  US12/856,899
• Publication Number:
  US 20100306756A1
• Time in Patent Office: 897 Days
• Field of Search: 717168-174, 709203-204
• US Class Current: 717/168
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

A reverse patch for undoing a forward patch for obtaining a new binary image from an old binary image is generated in two parts. First a reverse index file is generated when the forward patch is created at a host or server. The reverse index file identifies regions of similarity between the old binary image and the new binary image. The reverse index file is transmitted with the forward patch to an electronic device. Second, while applying the forward patch to obtain the new binary image from the old binary image, the electronic device generates the reverse patch based upon the new binary image, the old binary image, and the reverse index file. The forward patch and reverse patch may both be incremental patches. Incremental patches are generated and applied on a sector-by-sector basis.

Claims

1. A method of generating an index file for use in reversing a forward patch on an electronic device, wherein the forward patch generates a new binary image from an old binary image, the method comprising:

generating, at a processor, the index file, the index file identifying regions of similarity between the old binary image and the new binary image for use in obtaining at least a portion of the old binary image from the new binary image; and

transmitting, from a communications interface, the forward patch and the index file to the electronic device.

2. The method of claim 1, further comprising:

applying the forward patch to the old binary image to create the new binary image at the electronic device; and

generating the reverse patch from the new binary image, the old binary image, and the index file at the electronic device.

3. The method of claim 2, further comprising generating the forward patch.

4. The method of claim 3, wherein the new binary image occupies a plurality of sectors, and wherein generating the forward patch and generating the index file include:

setting a current image as the old binary image,

selecting one of the plurality of sectors from the new binary image,

determining binary difference algorithm to generate delta file for obtaining said one of the plurality of sectors from the current image,

overwriting an old sector within the current image with said one of the plurality of sectors, while retaining a copy of the old sector,

generating a sector-specific index file, wherein the sector-specific index file identifies regions of similarity between said old sector and said current image, and

repeating the selecting, determining, overwriting, and generating once for each of the plurality of sectors,

wherein the forward patch thereby comprises a plurality of delta files, and

wherein the index file comprises a plurality of sector-specific index files.

5. The method of claim 4, wherein applying the forward patch and generating the reverse patch include:

setting a current image as the old binary image,

selecting one of the plurality of sectors from the new binary image,

applying one of said plurality of delta files to the current image to generate said one of the plurality of sectors,

overwriting an old sector within the current image with said one of the plurality of sectors while retaining a copy of the old sector,

generating a sector-specific reverse patch from the current image, the old sector, and one of the sector-specific index files, and

repeating the selecting, applying, overwriting, and generating once for each of the plurality of sectors,

and wherein the reverse patch comprises a plurality of said sector-specific reverse patches.

6. The method of claim 1, wherein said generating the index file includes performing an indexing operation, and wherein said indexing operation includes hashing or suffix sorting.

7. The method of claim 1, wherein said transmitting includes packaging said forward patch and said index file together as a deliverable, and transmitting said deliverable over one or more communications networks.

8. The method of claim 7, wherein said electronic device comprises a mobile wireless device, and wherein said communications networks include a wireless network.

9. The method of claim 1, further including storing said reverse patch in non-volatile memory on said device.

10. A method of generating a reverse patch for reversing a forward patch on an electronic device, wherein the forward patch generates a new binary image from an old binary image, the method comprising:

receiving, using a communications subsystem, the forward patch and an index file, the index file identifying regions of similarity between the old binary image and the new binary image for use in obtaining at least a portion of the old binary image from the new binary image;

applying, at a processor executing a patch manager, the forward patch to the old binary image to create the new binary image at the electronic device; and

generating, at said processor executing a patch generation module, the reverse patch from the new binary image, the old binary image, and the index file at the electronic device.

11. The method of claim 10, wherein the new binary image occupies a plurality of sectors, wherein the forward patch comprises a plurality of sector-specific delta files each for obtaining one of said plurality of sectors, wherein the index file comprises a plurality of sector-specific index files, and wherein applying the forward patch and generating the reverse patch include:

setting a current image as the old binary image,

selecting one of the plurality of sectors from the new binary image,

applying one of said plurality of sector-specific delta files to the current image to generate said one of the plurality of sectors,

overwriting an old sector within the current image with said one of the plurality of sectors while retaining a copy of the old sector,

generating a sector-specific reverse patch from the current image, the old sector, and one of the sector-specific index files, wherein said sector-specific index file identifies regions of similarity between said old sector and said current image, and

repeating the selecting, applying, overwriting, and generating once for each of the plurality of sectors,

and wherein the reverse patch comprises a plurality of said sector-specific reverse patches.

12. The method of claim 10, wherein said receiving includes receiving the forward patch and the index file over a communications network and storing the forward patch and the index file in memory on the electronic device.

13. The method of claim 12, wherein said electronic device comprises a mobile wireless device, and wherein said communications network includes a wireless network.

14. The method of claim 12, further comprising storing said reverse patch in non-volatile memory on said electronic device.

15. A system for generating a reverse patch for reversing a forward patch, wherein the forward patch generates a new binary image from an old binary image, the system comprising:

a server having a processor and memory for storing the new binary image and the old binary image, and for storing the forward patch, and having a indexing module executable by the processor for generating an index file, the index file identifying regions of similarity between the old binary image and the new binary image for use in obtaining at least a portion of the old binary image from the new binary image, the server including a communications interface for transmitting the forward patch and the index file from the server to the electronic device; and

an electronic device having a device processor and device memory for storing the forward patch and the index file received from the server via one or more communications networks, the electronic device including a patch manager for applying the forward patch to the old binary image to create the new binary image, and including a patch generation module for generating the reverse patch from the new binary image, the old binary image, and the index file.

16. The system of claim 15, wherein said server further includes a binary difference algorithm for generating said forward patch.

17. The system of claim 16, wherein the new binary image occupies a plurality of sectors, and wherein said binary difference algorithm and said indexing module include:

a component for setting a current image as the old binary image,

a component for selecting one of the plurality of sectors from the new binary image,

a component for determining a binary difference algorithm to generate a delta file for obtaining said one of the plurality of sectors from the current image,

a component for overwriting an old sector within the current image with said one of the plurality of sectors, while retaining a copy of the old sector, and

a component generating a sector-specific index file, wherein the sector-specific index file identifies regions of similarity between said old sector and said current image,

and wherein said components for selecting, determining, overwriting, and generating are configured to operate once for each of the plurality of sectors, and wherein the forward patch comprises a plurality of delta files created by the component for determining, and wherein the index file comprises a plurality of sector-specific index files created by the component for generating.

18. The system of claim 17, wherein said patch manager and said patch generation module include:

a component for setting a current image as the old binary image,

a component for selecting one of the plurality of sectors from the new binary image,

a component for applying one of said plurality of delta files to the current image to generate said one of the plurality of sectors,

a component for overwriting an old sector within the current image with said one of the plurality of sectors while retaining a copy of the old sector, and

a component for generating a sector-specific reverse patch from the current image, the old sector, and one of the sector-specific index files,

and wherein said components for selecting, applying, overwriting, and generating are configured to operate once for each of the plurality of sectors, and wherein the reverse patch comprises a plurality of said sector-specific reverse patches.

19. The system of claim 15, wherein said indexing module for generating the index file includes an indexing operator, which includes hashing or suffix sorting.

20. The system of claim 15, wherein said electronic device comprises a mobile wireless device, and further including a wireless network over which said server transmits the forward patch and the index file to the mobile wireless device.

21. The system of claim 15, wherein said electronic device includes non-volatile memory for storing said reverse patch.

22. A server configured to generate an index file for use in generating a reverse patch for reversing a forward patch on an electronic device, wherein the forward patch generates a new binary image from an old binary image, the server comprising:

a processor;

memory for storing the new binary image and the old binary image, and for storing the forward patch;

a indexing module executable by the processor for generating an index file, the index file identifying regions of similarity between the old binary image and the new binary image for use in obtaining at least a portion of the old binary image from the new binary image; and

a communications interface for transmitting the forward patch and the index file from the server to the electronic device.

23. The server of claim 22, further including a binary difference algorithm for generating the forward patch.

24. The server of claim 23, wherein the new binary image occupies a plurality of sectors, and said binary difference algorithm and said indexing module include:

a component for setting a current image as the old binary image,

a component for selecting one of the plurality of sectors from the new binary image,

a component for determining a binary difference algorithm to generate a delta file for obtaining said one of the plurality of sectors from the current image,

a component for overwriting an old sector within the current image with said one of the plurality of sectors, while retaining a copy of the old sector, and

a component for generating a sector-specific index file, wherein the sector-specific index file identifies regions of similarity between said old sector and said current image,

and wherein said components for selecting, determining, overwriting, and generating are configured to operate once for each of the plurality of sectors, and wherein the forward patch comprises a plurality of delta files created by the component for determining, and wherein the index file comprises a plurality of sector-specific index files created by the component for generating.

25. The server of claim 22, wherein said indexing module includes a component for hashing or a component for suffix sorting.

26. The server of claim 22, wherein said communications interface includes a component for packaging said forward patch and said index file together as a deliverable, and transmitting said deliverable over one or more communications networks.

27. An electronic device configured to generate a reverse patch for reversing a forward patch, wherein the forward patch generates a new binary image from an old binary image, the electronic device comprising:

a device processor;

a communications subsystem for receiving the forward patch and the index file from a server via one or more communications networks;

device memory for storing the forward patch and the index file;

a patch manager for applying the forward patch to the old binary image to create the new binary image;

a patch generation module for generating the reverse patch from the new binary image, the old binary image, and the index file.

28. The electronic device of claim 27, wherein the new binary image occupies a plurality of sectors, the forward patch comprises a plurality of sector-specific delta files each for obtaining one of said plurality of sectors, the index file comprises a plurality of sector-specific index files, and wherein the patch manager and the patch generation module include:

a component for setting a current image as the old binary image,

a component for selecting one of the plurality of sectors from the new binary image,

a component for applying one of said plurality of sector-specific delta files to the current image to generate said one of the plurality of sectors,

a component for overwriting an old sector within the current image with said one of the plurality of sectors while retaining a copy of the old sector, and

a component for generating a sector-specific reverse patch from the current image, the old sector, and one of the sector-specific index files, wherein said sector-specific index file identifies regions of similarity between said old sector and said current image,

and wherein said components for selecting, applying, overwriting, and generating are configured to operate once for each of the plurality of sectors, and wherein the reverse patch comprises a plurality of said sector-specific reverse patches.

29. The electronic device of claim 28, wherein said electronic device comprises a mobile wireless device, and wherein said one or more communications networks include a wireless network.

30. The electronic device of claim 27, further including non-volatile memory for storing said reverse patch.

31. A non-transitory computer program product comprising a computer readable medium having encoded thereon computer-executable instructions for configuring a processor to generate an index file for use in generating a reverse patch for reversing a forward patch on an electronic device, wherein the forward patch generates a new binary image from an old binary image, the computer executable instructions comprising:

instructions for generating the index file, the index file identifying regions of similarity between the old binary image and the new binary image for use in obtaining at least a portion of the old binary image from the new binary image; and

instructions for transmitting the forward patch and the index file to the electronic device.

32. A non-transitory computer program product comprising a computer readable medium having encoded thereon computer-executable instructions for configuring a processor to generate a reverse patch for reversing a forward patch on an electronic device, wherein the forward patch generates a new binary image from an old binary image, the computer executable instructions comprising:

instructions for receiving the forward patch and an index file, the index file identifying regions of similarity between the old binary image and the new binary image for use in obtaining at least a portion of the old binary image from the new binary image;

instructions for applying the forward patch to the old binary image to create the new binary image at the electronic device; and

instructions for generating the reverse patch from the new binary image, the old binary image, and the index file at the electronic device.