Method and system for generating a reverse binary patch for undoing a software update

• US 7,779,401 B2
• Filed: 06/26/2006
• Issued: 08/17/2010
• 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: Dahms, John F. A., Scian, Anthony F.
• Primary Examiner(s): Khatri; Anil
• Application Number:
  US11/426,331
• Publication Number:
  US 20070300205A1
• Time in Patent Office: 1,513 Days
• Field of Search: 717167-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 for 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 the steps of:

generating an index file at a server, 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;

transmitting the forward patch and the index file from the server to the electronic device;

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;

wherein said steps of generating the index file, applying the forward patch, and generating the reverse patch are performed on a sector-by-sector basis.

2. The method claimed in claim 1, further including a step of generating the forward patch.

3. The method claimed in claim 2, wherein the new binary image occupies a plurality of sectors, and wherein said steps of 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,

computing a binary difference algorithm to generate a 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 steps of selecting, computing, overwriting, and generating once for each of the plurality of sectors,

and wherein the forward patch comprises a plurality of delta files created from the computing steps, and wherein the index file comprises a plurality of sector-specific index files created from the generating steps.

4. The method claimed in claim 3, wherein the steps of 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 reverse index files, and

repeating the steps of 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.

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

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

7. The method claimed in claim 6, wherein said electronic device comprises a mobile wireless device, and wherein said communications networks include a wireless network.

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

9. A method for generating a reverse 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 method comprising the steps of:

generating an index file at a server, 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 the forward patch and the index file from the server to the electronic device;

further including a step of generating the forward patch;

wherein said steps of generating the index file, applying the forward patch, and generating the reverse patch are performed on a sector-by-sector basis.

10. The method claimed in claim 9, wherein the new binary image occupies a plurality of sectors, and wherein said steps of 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,

computing a binary difference algorithm to generate a 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 steps of selecting, computing, overwriting, and generating once for each of the plurality of sectors,

and wherein the forward patch comprises a plurality of delta files created from the computing steps, and wherein the index file comprises a plurality of sector-specific index files created from the generating steps.

11. The method claimed in claim 9, wherein said step of generating the index file includes performing an indexing operation, and wherein said indexing operation includes hashing or suffix sorting.

12. The method claimed in claim 9, wherein said step of transmitting includes packaging said forward patch and said reverse index file together as a deliverable, and transmitting said deliverable over one or more communications networks.

13. A method for 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 the steps of:

receiving the forward patch and an index file from a server, 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 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;

wherein said steps of generating the index file, applying the forward patch, and generating the reverse patch are performed on a sector-by-sector basis.

14. The method claimed in claim 13, 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 reverse index files, and wherein the steps of 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 reverse index files, wherein said sector-specific index file identifies regions of similarity between said old sector and said current image, and

repeating the steps of 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.

15. The method claimed in claim 13, wherein said step of 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.

16. The method claimed in claim 15, wherein said electronic device comprises a mobile wireless device, and wherein said communications network includes a wireless network.

17. The method claimed in claim 13, further including a step of storing said reverse patch in non-volatile memory on said electronic device.

18. 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;

wherein said indexing module is configured to generate said index file on a sector-by-sector basis, wherein said patch manager is configured to apply the forward patch on a sector-by-sector basis, and wherein said patch generation module is configured to generate the reverse patch on a sector-by-sector basis.

19. The system claimed in claim 18, wherein said server further includes a binary difference algorithm for generating said forward patch.

20. The system claimed in claim 19, 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 computing 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, computing, 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 computing, and wherein the index file comprises a plurality of sector-specific index files created by the component for generating.

21. The system claimed in claim 20, 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 reverse 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.

22. The system claimed in claim 18, wherein said indexing module for generating the index file includes an indexing operator, which includes hashing or suffix sorting.

23. The system claimed in claim 18, 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 reverse index file to the mobile wireless device.

24. The system claimed in claim 18, wherein said electronic device includes non-volatile memory for storing said reverse patch.

25. A server for generating a reverse 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;

further including a step of generating the forward patch;

wherein said steps of generating the index file, applying the forward patch, and generating the reverse patch are performed on a sector-by-sector basis.

26. The server claimed in claim 25, 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 computing 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, computing, 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 computing, and wherein the index file comprises a plurality of sector-specific index files created by the component for generating.

27. The server claimed in claim 25, wherein said indexing module includes a component for hashing or a component for suffix sorting.

28. The server claimed in claim 25, wherein said communications interface includes a component for packaging said forward patch and said reverse index file together as a deliverable, and transmitting said deliverable over one or more communications networks.

29. An electronic device 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 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;

wherein said patch manager is configured to operate on a sector-by-sector basis, and wherein said patch generation module is configured to operate on a sector-by-sector basis.

30. The electronic device claimed in claim 29, 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 reverse 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 reverse 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.

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

32. The electronic device claimed in claim 29, further including non-volatile memory for storing said reverse patch.

33. A computer program product comprising a computer readable medium having encoded thereon computer-executable instructions for configuring a processor to generate a reverse 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 an index file at a server, 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 from the server to the electronic device;

further including a step of generating the forward patch;

wherein said steps of generating the index file, applying the forward patch, and generating the reverse patch are performed on a sector-by-sector basis.

34. A 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 from a server, 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;

wherein said steps of generating the index file, applying the forward patch, and generating the reverse patch are performed on a sector-by-sector basis.