It's a good thing you spotted this, thanks! I wonder how this translates in patch when/if it happens. Do we filter out invalid offsets? Or perhaps we implicitly treat these as negative numbers (thanks to overflows) during label ajustement.
In my opinion, simplest and most logical alternative is to clip projected offsets to a valid range [0, new_image.size()) in OffsetMapper::ForwardProject(). That might change generated patch for inputs that trigger this weird behavior, so it's worthwhile to investigate to see if this behavior causes issues. I'll get back on this issue as soon as possible!

No rush at this for now! It also would be nice to be able to repro the bug and verify it exists, before implementing a fix. To this end, ckitagawa@ is working on  bug 834904  to improve testing.

With the ZTF in place (thanks to ckitagawa@), I have an example to repro this:

*** Old file ***
ZTxt-----------
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
ZTxt+++++++++++
AAAAAAAAAAAAAAA
AAA(03,01)AAAAA
AAA(09,15)AAAAA
AAAAAAAAAAAAAAA
BBBBBBBBBBBBBBB
BBBBBBBBBBBBBBB
txTZ
================


*** New file ***
ZTxt+++++++++++
AAAAAAAAAAAAAAA
AAA(02,01)AAAAA
AAA(05,15)AAAAA
AAAAAAAAAAAAAAA
txTZ
================

Note that each must end with a "txtZ" followed by new line.

The good new is that patching generation / application still works. However, from dumping, we see that OffsetMapper::ForwardProject() does produce offsets that are outside "new" image bound (for this example, 0xFFFFFFF0 and 0x0000005E). However, TargetPool::KeyForNearestOffset() maps the invalid offset to a valid key, so no damage is done (except for patch size degradation).

While implementing to fix this, another benign problem is revealed.

Zucchini contains "dangling targets", which are targets that point *outside* the end of files. These represent addresses that have no offset in the file, e.g., .bss data.

During reference induction (Zucchini-gen or Zucchini-apply),  OffsetMapper::ForwardProject() is applied to "old" targets to create estimated "new" target (not *location*, as mistakenly stated in original comment). These actually "extended" forward projection, where a nearest "old" equivalence block is found, and the its displacement is used to compute the estimate.

Turns out that OffsetMapper::ForwardProject() is also applied to dangling targets. The algorithm would find the equivalence unit with maximal "old" block, and apply its displacement to create an estimated "new" target, which is then mapped to nearest actual "new" target (possibly dangling), then converted to target key, which is then used to compute / apply reference correction.

If we simply clamp the output of OffsetMapper::ForwardProject() (to "new" size - 1), then dangling "old" targets would produce estimated "new" targets that's lower than they should. This depresses resulting target key, and increases the magnitude of value stored for reference correction, i.e., make patch bigger!

However, the current behavior also makes dangling patching highly sensitive to the equivalence unit with maximal "old" block, which can be arbitrary.

A solution (in addition to clamping) is to have OffsetMapper::ForwardProject() (which should be renamed) detect dangling targets, and simply map them by adding delta file length, i.e.:
  est. "new" dangling target = "old" dangling target - "old" size + "new" size.

As clarification, "dangling RVAs" refer to .bss RVAs, "fake offsets" are offsets that point outside of image, and "dangling targets" are targets that are "fake offsets" (since "fake target" sound off).

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/ad7a5c086f00de62997714b84d6d6b5817ccc9d8

commit ad7a5c086f00de62997714b84d6d6b5817ccc9d8
Author: Samuel Huang <huangs@chromium.org>
Date: Tue Jun 26 14:47:02 2018

[Zucchini] Fix underflow / overflow for extended forward-projection.

Forward-projection is how Zucchini uses the equivalence map to create
estimated "new" targets from "old" targets. Extended forward-projection
is defined to transform non-covered offsets: Given an offset, it finds
the equivalence unit with nearest "old" block, then applies the
"old"-to-"new" displacement to the offset. However, this makes it
possible to map an "old" offset to an offset outside "new" image.

Another issue is that Zucchini uses "dangling targets" that use "fake
offsets" outside the image file to represent .bss data. These targets
also undergo forward-projection, and should be properly handled.

This CL fixes the existing behavior, where underflow / overflow go
unchecked (although these values are rendered benign downstream, since
the nearest actual "new" target is found). The updated extended
forward-projection specifies:
- For "old" targets with real offsets: Take nearest equivalence unit,
  clamp output to be inside [0, "new" image size).
- For "old" dangling targets with fake offsets: Use difference in
  file size as displacement.

The main impact w.r.t. patch is to reduce possible variance in patch
sizes -- dangling targets are now handled better. Extensive unit tests
are also added.

Bug:  832572 
Change-Id: I41fea175e4c13585d14a97a712a191afc2fcc6d6
Reviewed-on: https://chromium-review.googlesource.com/1111467
Reviewed-by: Samuel Huang <huangs@chromium.org>
Reviewed-by: Greg Thompson <grt@chromium.org>
Commit-Queue: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#570401}
[modify] https://crrev.com/ad7a5c086f00de62997714b84d6d6b5817ccc9d8/components/zucchini/equivalence_map.cc
[modify] https://crrev.com/ad7a5c086f00de62997714b84d6d6b5817ccc9d8/components/zucchini/equivalence_map.h
[modify] https://crrev.com/ad7a5c086f00de62997714b84d6d6b5817ccc9d8/components/zucchini/equivalence_map_unittest.cc
[modify] https://crrev.com/ad7a5c086f00de62997714b84d6d6b5817ccc9d8/components/zucchini/zucchini_apply.cc
[modify] https://crrev.com/ad7a5c086f00de62997714b84d6d6b5817ccc9d8/components/zucchini/zucchini_gen.cc
[modify] https://crrev.com/ad7a5c086f00de62997714b84d6d6b5817ccc9d8/components/zucchini/zucchini_gen_unittest.cc