Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / zucchini / 725a8734514bb88b5acd976040e6710e26b2e3b5
commit725a8734514bb88b5acd976040e6710e26b2e3b5[log] [tgz]
authorEtienne Pierre-doray <etiennep@chromium.org>Mon Sep 10 16:19:33 2018 +0000
committerCopybara-Service <copybara-worker@google.com>Sun Jul 25 20:36:14 2021 -0700
tree15293dbea03b652c5873d1aaebbc2efaf67c88c3
parent74d44edc92e96d45c2f1d488e42171bb3c55570c [diff]
[Zucchini]: Fix OffsetMapper implicit conversion.

Fix compile error with -Wshorten-64-to-32. Image size is new stored as an
offset_t to avoid implicit conversion.

Bug: 881008
Change-Id: I82b12ce17d8368f05d6a5537fd1734ee32b37dbe
Reviewed-on: https://chromium-review.googlesource.com/1213549
Reviewed-by: Samuel Huang <huangs@chromium.org>
Commit-Queue: Etienne Pierre-Doray <etiennep@chromium.org>
Cr-Commit-Position: refs/heads/master@{#589938}
NOKEYCHECK=True
GitOrigin-RevId: 5946dbfa3f684d8f4960bb413b5e8322ebddcee3
5 files changed
tree: 15293dbea03b652c5873d1aaebbc2efaf67c88c3
  1. fuzzers/
  2. testdata/
  3. abs32_utils.cc
  4. abs32_utils.h
  5. abs32_utils_unittest.cc
  6. address_translator.cc
  7. address_translator.h
  8. address_translator_unittest.cc
  9. algorithm.h
  10. algorithm_unittest.cc
  11. binary_data_histogram.cc
  12. binary_data_histogram.h
  13. binary_data_histogram_unittest.cc
  14. buffer_sink.cc
  15. buffer_sink.h
  16. buffer_sink_unittest.cc
  17. buffer_source.cc
  18. buffer_source.h
  19. buffer_source_unittest.cc
  20. buffer_view.h
  21. buffer_view_unittest.cc
  22. BUILD.gn
  23. crc32.cc
  24. crc32.h
  25. crc32_unittest.cc
  26. disassembler.cc
  27. disassembler.h
  28. disassembler_dex.cc
  29. disassembler_dex.h
  30. disassembler_dex_unittest.cc
  31. disassembler_elf.cc
  32. disassembler_elf.h
  33. disassembler_elf_unittest.cc
  34. disassembler_no_op.cc
  35. disassembler_no_op.h
  36. disassembler_win32.cc
  37. disassembler_win32.h
  38. disassembler_ztf.cc
  39. disassembler_ztf.h
  40. disassembler_ztf_unittest.cc
  41. element_detection.cc
  42. element_detection.h
  43. element_detection_unittest.cc
  44. encoded_view.cc
  45. encoded_view.h
  46. encoded_view_unittest.cc
  47. ensemble_matcher.cc
  48. ensemble_matcher.h
  49. equivalence_map.cc
  50. equivalence_map.h
  51. equivalence_map_unittest.cc
  52. heuristic_ensemble_matcher.cc
  53. heuristic_ensemble_matcher.h
  54. image_index.cc
  55. image_index.h
  56. image_index_unittest.cc
  57. image_utils.h
  58. image_utils_unittest.cc
  59. imposed_ensemble_matcher.cc
  60. imposed_ensemble_matcher.h
  61. imposed_ensemble_matcher_unittest.cc
  62. integration_test.cc
  63. io_utils.cc
  64. io_utils.h
  65. io_utils_unittest.cc
  66. main_utils.cc
  67. main_utils.h
  68. mapped_file.cc
  69. mapped_file.h
  70. mapped_file_unittest.cc
  71. OWNERS
  72. patch_read_write_unittest.cc
  73. patch_reader.cc
  74. patch_reader.h
  75. patch_utils.h
  76. patch_utils_unittest.cc
  77. patch_writer.cc
  78. patch_writer.h
  79. README.md
  80. reference_bytes_mixer.cc
  81. reference_bytes_mixer.h
  82. reference_set.cc
  83. reference_set.h
  84. reference_set_unittest.cc
  85. rel32_finder.cc
  86. rel32_finder.h
  87. rel32_finder_unittest.cc
  88. rel32_utils.cc
  89. rel32_utils.h
  90. rel32_utils_unittest.cc
  91. reloc_elf.cc
  92. reloc_elf.h
  93. reloc_elf_unittest.cc
  94. reloc_win32.cc
  95. reloc_win32.h
  96. reloc_win32_unittest.cc
  97. suffix_array.h
  98. suffix_array_unittest.cc
  99. target_pool.cc
  100. target_pool.h
  101. target_pool_unittest.cc
  102. targets_affinity.cc
  103. targets_affinity.h
  104. targets_affinity_unittest.cc
  105. test_disassembler.cc
  106. test_disassembler.h
  107. test_reference_reader.cc
  108. test_reference_reader.h
  109. test_utils.cc
  110. test_utils.h
  111. type_dex.h
  112. type_elf.h
  113. type_win_pe.h
  114. type_ztf.h
  115. typed_value.h
  116. typed_value_unittest.cc
  117. zucchini.h
  118. zucchini_apply.cc
  119. zucchini_apply.h
  120. zucchini_apply_unittest.cc
  121. zucchini_commands.cc
  122. zucchini_commands.h
  123. zucchini_exe_version.rc.version
  124. zucchini_gen.cc
  125. zucchini_gen.h
  126. zucchini_gen_unittest.cc
  127. zucchini_integration.cc
  128. zucchini_integration.h
  129. zucchini_main.cc
  130. zucchini_tools.cc
  131. zucchini_tools.h
README.md

Basic Definitions for Patching

Binary: Executable image and data. Binaries may persist in an archive (e.g., chrome.7z), and need to be periodically updated. Formats for binaries include {PE files EXE / DLL, ELF, DEX}. Architectures binaries include {x86, x64, ARM, AArch64, Dalvik}. A binary is also referred to as an executable or an image file.

Patching: Sending a "new" file to clients who have an "old" file by computing and transmitting a "patch" that can be used to transform "old" into "new". Patches are compressed for transmission. A key performance metric is patch size, which refers to the size of compressed patch file. For our experiments we use 7z.

Patch generation: Computation of a "patch" from "old" and "new". This can be expensive (e.g., ~15-20 min for Chrome, using 1 GB of RAM), but since patch generation is a run-once step on the server-side when releasing "new" binaries, the expense is not too critical.

Patch application: Transformation from "old" binaries to "new", using a (downloaded) "patch". This is executed on client side on updates, so resource constraints (e.g., time, RAM, disk space) is more stringent. Also, fault- tolerance is important. This is usually achieved by an update system by having a fallback method of directly downloading "new" in case of patching failure.

Offset: Position relative to the start of a file.

Local offset: An offset relative to the start of a region of a file.

Element: A region in a file with associated executable type, represented by the tuple (exe_type, offset, length). Every Element in new file is associated with an Element in old file and patched independently.

Reference: A directed connection between two offsets in a binary. For example, consider jump instructions in x86:

00401000: E9 3D 00 00 00     jmp         00401042

Here, the 4 bytes [3D 00 00 00] starting at address 00401001 point to address 00401042 in memory. This forms a reference from offset(00401001) (length 4) to offset(00401042), where offset(addr) indicates the disk offset corresponding to addr. A reference has a location, length (implicitly determined by reference type), body, and target.

Location: The starting offset of bytes that store a reference. In the preceding example, offset(00401001) is a location. Each location is the beginning of a reference body.

Body: The span of bytes that encodes reference data, i.e., [location, location + length) = [location, location + 1, ..., location + length - 1]. In the preceding example, length = 4, so the reference body is [00401001, 00401001 + 4) = [00401001, 00401002, 00401003, 00401004]. All reference bodies in an image must not overlap, and often regions boundaries are required to not straddle a reference body.

Target: The offset that's the destination of a reference. In the preceding example, offset(00401042) is the target. Different references can share common targets. For example, in

00401000: E9 3D 00 00 00     jmp         00401042
00401005: EB 3B              jmp         00401042

we have two references with different locations and bodies, but same target of 00401042.

Because the bytes that encode a reference depend on its target, and potentially on its location, they are more likely to get modified from an old version of a binary to a newer version. This is why "naive" patching does not do well on binaries.

Target Key: An alternative representation of a Target for a fixed pool, as its index in the sorted list of Target offsets. Keys are useful since:

  • Their numerical index are smaller than offsets, allowing more efficient storage of target correction data in patch.
  • They simplify association from Targets to Labels.

Disassembler: Architecture specific data and operations, used to extract and correct references in a binary.

Type of reference: The type of a reference determines the binary representation used to encode its target. This affects how references are parsed and written by a disassembler. There can be many types of references in the same binary.

A reference is represented by the tuple (disassembler, location, target, type). This tuple contains sufficient information to write the reference in a binary.

Pool of targets: Collection of targets that is assumed to have some semantic relationship. Each reference type belong to exactly one reference pool. Targets for references in the same pool are shared.

For example, the following describes two pools defined for Dalvik Executable format (DEX). Both pools spawn multiple types of references.

  1. Index in string table.
  • From bytecode to string index using 16 bits.
  • From bytecode to string index using 32 bits.
  • From field item to string index using 32 bits.
  1. Address in code.
  • Relative 16 bits pointer.
  • Relative 32 bits pointer.

Boundaries between different pools can be ambiguous. Having all targets belong to the same pool can reduce redundancy, but will use more memory and might cause larger corrections to happen, so this is a trade-off that can be resolved with benchmarks.

Abs32 references: References whose targets are adjusted by the OS during program load. In an image, a relocation table typically provides locations of abs32 references. At each abs32 location, the stored bytes then encode semantic information about the target (e.g., as RVA).

Rel32 references: References embedded within machine code, in which targets are encoded as some delta relative to the reference's location. Typical examples of rel32 references are branching instructions and instruction pointer-relative memory access.

Equivalence: A (src_offset, dst_offset, length) tuple describing a region of "old" binary, at an offset of |src_offset|, that is similar to a region of "new" binary, at an offset of |dst_offset|.

Raw delta unit: Describes a raw modification to apply on the new image, as a pair (copy_offset, diff), where copy_offset describes the position in new file as an offset in the data that was copied from the old file, and diff is the bytewise difference to apply.

Associated Targets: A target in "old" binary is associated with a target in "new" binary if both targets:

  1. are part of similar regions from the same equivalence, and
  2. have the same local offset (relative to respective start regions), and
  3. are not part of any larger region from a different equivalence. Not all targets are necessarily associated with another target.

Target Affinity: Level of confidence in the association between two targets. The affinity between targets that are potentially associated is measured based on surrounding content, as well as reference type.

Label: An integer assigned for each Target in "old" and "new" binary as part of generating a patch, and used to alias targets when searching for similar regions that will form equivalences. Labels are assigned such that associated targets in old and new binaries share the same Label. Unmatched Targets have a Label of 0. For example, given

  • "Old" targets = [0x1111, 0x3333, 0x5555, 0x7777],
  • "New" targets = [0x2222, 0x4444, 0x6666, 0x8888], to represent matchings 0x1111 <=> 0x6666, 0x3333 <=> 0x2222, we'd assign
  • Label 1 to 0x1111 (in "old") and 0x6666 (in "new"),
  • Label 2 to 0x3333 (in "old") and 0x2222 (in "new"). Represented as arrays indexed over Target Keys, we'd have:
  • "Old" labels = [1, 2, 0 ,0],
  • "New" labels = [2, 0, 1, 0].

Encoded Image: The result of projecting the content of an image to scalar values that describe content on a higher level of abstraction, masking away undesirable noise in raw content. Notably, the projection encodes references based on their associated label.

Interfaces

zucchini_lib: Core Zucchini library that operate on buffers to generate and apply patches.

zucchini_io: Wrapper on zucchini_lib that handles file I/O, using memory-mapped I/O to interface with zucchini_lib.

zucchini: Stand-alone executable that parses command-line arguments, and passes the results to zucchini_io. Also implements various helper flows.

Zucchini Ensemble Patch Format

Types

int8: 8-bit unsigned int.

uint32: 32-bit unsigned int, little-endian.

int32: 32-bit signed int, little-endian.

Varints: This is a generic variable-length encoding for integer quantities that strips away leading (most-significant) null bytes. The Varints format is borrowed from protocol-buffers, see documentation for more info.

varuint32: A uint32 encoded using Varints format.

varint32: A int32 encoded using Varints format.

File Layout

NameFormatDescription
headerPatchHeaderThe header.
elements_countuint32Number of patch units.
elementsPatchElement[elements_count]List of all patch elements.

Position of elements in new file is ascending.

Structures

PatchHeader

NameFormatDescription
magicuint32 = kMagicMagic value.
old_sizeuint32Size of old file in bytes.
old_crcuint32CRC32 of old file.
new_sizeuint32Size of new file in bytes.
new_crcuint32CRC32 of new file.

kMagic == 'Z' | ('u' << 8) | ('c' << 16)

PatchElement Contains all the information required to produce a single element in new file.

NameFormatDescription
headerPatchElementHeaderThe header.
equivalencesEquivalenceListList of equivalences.
raw_deltasRawDeltaListList of raw deltas.
reference_deltasReferenceDeltaListList of reference deltas.
pool_countuint32Number of pools.
extra_targetsExtraTargetList[pool_count]Lists of extra targets.

PatchElementHeader Describes a correspondence between an element in old and in new files. Some redundancy arise from storing |new_offset|, but it is necessary to make PatchElement self contained.

NameFormatDescription
old_offsetuint32Starting offset of the element in old file.
old_lengthuint32Length of the element in old file.
new_offsetuint32Starting offset of the element in new file.
new_lengthuint32Length of the element in new file.
exe_typeuint32Executable type for this unit, see enum ExecutableType.

EquivalenceList Encodes a list of equivalences, where dst offsets (in new image) are ascending.

NameFormatDescription
src_skipBufferSrc offset for each equivalence, delta encoded.
dst_skipBufferDst offset for each equivalence, delta encoded.
copy_countBufferLength for each equivalence.

RawDeltaList Encodes a list of raw delta units, with ascending copy offsets.

NameFormatDescription
raw_delta_skipBufferCopy offset for each delta unit, delta encoded and biased by -1.
raw_delta_diffBufferBytewise difference for each delta unit.

ReferenceDeltaList Encodes a list of reference deltas, in the order they appear in the new image file. A reference delta is a signed integer representing a jump through a list of targets.

NameFormatDescription
reference_deltaBufferVector of reference deltas.

ExtraTargetList Encodes a list of additional targets in the new image file, in ascending order.

NameFormatDescription
pool_taguint8_tUnique identifier for this pool of targets.
extra_targetsBufferAdditional targets, delta encoded and biased by -1.

Buffer A generic vector of data.

NameFormatDescription
sizeuint32Size of content in bytes.
contentT[]List of integers.