Memtag ABI Extension to ELF violates idempotency requirement

[EliaGeretto]

The "ELF for the Arm® 64-bit Architecture (AArch64)" states that:

5.7.19 Idempotency
All RELA type relocations are idempotent. They may be reapplied to the place and the result will be the same. This allows a static linker to preserve > full relocation information for an image by converting all REL type relocations into RELA type relocations.

(https://github.com/ARM-software/abi-aa/blob/main/aaelf64/aaelf64.rst#idempotency)

The extended R_AARCH64_RELATIVE, as defined in "Memtag ABI Extension to ELF", violates the idempotency principle because it uses the place P to store the tag offset. Once the relocation is performed the first time, that information is lost, so it cannot be reapplied:

ELF64 Code	Name	Base Operation	MemtagABI Extended Operation
1027	R_AARCH64_RELATIVE	Delta + A	LDG(Delta + A + *P) - *P

(https://github.com/ARM-software/abi-aa/blob/main/memtagabielf64/memtagabielf64.rst#relocation-operations)

The interest in preserving the idempotency principle comes from baremetal targets. The only way to deploy memory tagging on a self-relocating target is relocating once with zero tags to perform the initialization required for virtual memory, apply the tags, and then relocate again with randomized tags. If the idempotency is not preserved, it is necessary store a copy of the tag offsets somewhere else and then reuse them.

Unfortunately, at a first glance, it seems impossible to preserve backwards compatibility when the tag offset is not zero, unless the tag offset is stored "off band". It seems that one bit of information would be enough to tell the loader to "fetch the tag from the previous 16 bytes granule", if end pointers are the only concern. However, this single bit of information can only be stored using a new relocation type given that both the addend field and the place cannot be touched to preserve backwards compatibility and idempotency.

It is worth noting that the "PAuth ABI Extension to ELF" has a similar issue, since it uses the place P to store the signature schema. The main difference with Memtag relocations is that PAuth introduces new relocations types, which provide more flexibility. The proposed workaround there is to ask the platform to decide whether to sacrifice either half the addend or idempotency, by storing the schema in P. See #398. This proposed workaround, however, does not address directly the issue of a PAuth relocation that also requires a tag offset (points to one off the end of a tagged object). One of the bits in the PAuth schema could be used for this. This should probably be addressed in one, or both, the documents.

[EliaGeretto]

This issue was discussed in the LLVM Pointer Authentication meetup. I am tagging the people that were mentioned as co-authors of the "Memtag ABI Extension to ELF" or appeared recently in the git history, feel free to pull in anyone else who may be relevant for this discussion. @smithp35 @pcc @fmayer

[jrtc27]

As mentioned on Discord, is R_<CLS>_JUMP_SLOT not already a non-idempotent relocation, given it carries both "unrelocated address of PLT header" and "bound target", with the former being stored in memory even when using the RELA format (effectively, it's both an implicit REL format R_<CLS>_RELATIVE and a REL(A, if used,) format R_<CLS>_GLOB_DAT optionally bound lazily)? I believe that means if you want to re-process jump slots you cannot do lazy binding, even with the base aaelf64 spec? Maybe you're not doing lazy binding (or you're operating in a statically-linked context) so that problem doesn't concern you, but I think it's therefore incorrect to frame this as a "problem" (whether the ABI should accommodate this use case or require software to remember any state it needs is subjective) limited to the likes of PAuth and Memtag.

[EliaGeretto]

Maybe you're not doing lazy binding (or you're operating in a statically-linked context) so that problem doesn't concern you, but I think it's therefore incorrect to frame this as a "problem" (whether the ABI should accommodate this use case or require software to remember any state it needs is subjective) limited to the likes of PAuth and Memtag.

Yes, our usecase is related to baremetal targets, so there is no lazy binding involved. Still, considering R_<CLS>_JUMP_SLOT, we are talking about two slightly different things. I agree that applying that relocation twice is a bad idea with lazy binding, but that relocation is idempotent nonetheless because, if applied twice, the result written in the "place" is the same. The fact that the content of the "place" was modified in the meantime because the lazy resolution happened does not influence idempotency. Idempotency is compromised only by the fact that we have *P in the formula, which is not the case for R_<CLS>_JUMP_SLOT.

To clarify, in my opinion, lazy binding is similar to an empty global linked list head. After the relocations have happened, the empty list will point to itself. If you add elements, the pointers will be modified and, if you relocate again, that will leak nodes in the list. It is a bad idea, but it does not mean that the relocation is not idempotent. The software being relocated twice needs to be aware of it and not use, or empty, the global list before relocating the second time.

[jrtc27]

Maybe you're not doing lazy binding (or you're operating in a statically-linked context) so that problem doesn't concern you, but I think it's therefore incorrect to frame this as a "problem" (whether the ABI should accommodate this use case or require software to remember any state it needs is subjective) limited to the likes of PAuth and Memtag.

Yes, our usecase is related to baremetal targets, so there is no lazy binding involved. Still, considering R_<CLS>_JUMP_SLOT, we are talking about two slightly different things. I agree that applying that relocation twice is a bad idea with lazy binding, but that relocation is idempotent nonetheless because, if applied twice, the result written in the "place" is the same. The fact that the content of the "place" was modified in the meantime because the lazy resolution happened does not influence idempotency. Idempotency is compromised only by the fact that we have *P in the formula, which is not the case for R_<CLS>_JUMP_SLOT.

No, that’s my point, *P does feature in the formula when doing lazy binding. It doesn’t for the actual symbol binding but does when doing the initial relocation that adjusts the entries used for lazy binding to account for the load base.

[EliaGeretto]

Maybe you're not doing lazy binding (or you're operating in a statically-linked context) so that problem doesn't concern you, but I think it's therefore incorrect to frame this as a "problem" (whether the ABI should accommodate this use case or require software to remember any state it needs is subjective) limited to the likes of PAuth and Memtag.

Yes, our usecase is related to baremetal targets, so there is no lazy binding involved. Still, considering R_<CLS>_JUMP_SLOT, we are talking about two slightly different things. I agree that applying that relocation twice is a bad idea with lazy binding, but that relocation is idempotent nonetheless because, if applied twice, the result written in the "place" is the same. The fact that the content of the "place" was modified in the meantime because the lazy resolution happened does not influence idempotency. Idempotency is compromised only by the fact that we have *P in the formula, which is not the case for R_<CLS>_JUMP_SLOT.

No, that’s my point, *P does feature in the formula when doing lazy binding. It doesn’t for the actual symbol binding but does when doing the initial relocation that adjusts the entries used for lazy binding to account for the load base.

The only formula for R_<CLS>_JUMP_SLOT is S + A, according to the reference. The fact that the relocation operation is performed lazily does not compromise idempotency, because idempotency deals with the result of the formula, not with how the implementation actually executes the relocation. That relocation is "finished" only when the actual symbol address is resolved.

Also, I haven't tried implementing this, but you could probably just lazy bind the symbol twice:

• Start the relocation pointing to the PLT stub.
• On call, finish the relocation pointing to the actual symbol.
• Start the second relocation pointing to the PLT stub again.
• On call, finish the second relocation pointing to the actual symbol.

Anyway, R_<CLS>_JUMP_SLOT remains idempotent for me, even if it is true that lazy binding stretches the definition. Writing relocation metadata in *P cannot fit with the definition of idempotency though, so it's a different thing.

[jrtc27]

Also, I haven't tried implementing this, but you could probably just lazy bind the symbol twice:

• Start the relocation pointing to the PLT stub.
• On call, finish the relocation pointing to the actual symbol.
• Start the second relocation pointing to the PLT stub again.
• On call, finish the second relocation pointing to the actual symbol.

My point is this doesn't work. There's no way to do "Start the second relocation pointing to the PLT stub again.", because the information of where that PLT header is has been overwritten by the binding, and I don't see how you can reliably tell whether the second step has happened to know if you have that PLT header location available.

[jrtc27]

The only formula for R_<CLS>_JUMP_SLOT is S + A, according to the reference. The fact that the relocation operation is performed lazily does not compromise idempotency, because idempotency deals with the result of the formula, not with how the implementation actually executes the relocation. That relocation is "finished" only when the actual symbol address is resolved.

I disagree here. The spec also says:

• On platforms that support dynamic binding the relocations may be performed lazily on demand.
• The initial value stored in the place is the offset to the entry sequence stub for the dynamic linker. It must be adjusted during initial loading by the offset of the load address of the segment from its link address.

Just because the table only gives the one formula does not mean that this does not also exist, and so I think all you're arguing is "if you need it to be idempotent you have to ignore lazy binding", which was precisely the point I was trying to make. Lazy binding exists and the spec describes how to do it, yet it's not idempotent.

[EliaGeretto]

Also, I haven't tried implementing this, but you could probably just lazy bind the symbol twice:

• Start the relocation pointing to the PLT stub.
• On call, finish the relocation pointing to the actual symbol.
• Start the second relocation pointing to the PLT stub again.
• On call, finish the second relocation pointing to the actual symbol.

My point is this doesn't work. There's no way to do "Start the second relocation pointing to the PLT stub again.", because the information of where that PLT header is has been overwritten by the binding, and I don't see how you can reliably tell whether the second step has happened to know if you have that PLT header location available.

I did more research into that and yes, you are correct on lazy binding not being idempotent. It turns out glibc actually backs up the stub address, suggesting that information is not stored anywhere else. I am attaching the relevant code from glibc 2.43 at the end of this comment. My previous statement that you can always perform lazy binding twice is incorrect, sorry for that, I should have looked into it before.

Still, as far as I can see, you should be able to process the same relocation record twice by doing:

• Start the relocation, adjusting the offset to the stub.
• On call, finish the relocation pointing to the actual symbol.
• Perform the relocation without lazy binding.

My point being that, if you look at R_<CLS>_JUMP_SLOT in terms of its final relocation result, the information needed to compute that result, given by S + A, is still all there. So the final R_<CLS>_JUMP_SLOT binding is still idempotent in my opinion, even if the lazy-binding setup cannot be replayed.

I guess our disagreement stems from how we interpret the idempotency definition: I read it as referring to the final relocation computation, so only to *P = S + A in this case, which is idempotent; you read it as also covering the replayability of the lazy-binding setup state used before that final value is written.

In any case, putting *P in the relocation formula would break both interpretations, since then even the final relocation computation depends on the previous contents of the place.

static inline void
__attribute__ ((always_inline))
elf_machine_lazy_rel (struct link_map *map, struct r_scope_elem *scope[],
		      ElfW(Addr) l_addr,
		      const ElfW(Rela) *reloc,
		      int skip_ifunc)
{
  ElfW(Addr) *const reloc_addr = (void *) (l_addr + reloc->r_offset);
  const unsigned int r_type = ELFW (R_TYPE) (reloc->r_info);
  /* Check for unexpected PLT reloc type.  */
  if (__builtin_expect (r_type == AARCH64_R(JUMP_SLOT), 1))
    {
      if (__glibc_unlikely (map->l_info[DT_AARCH64 (VARIANT_PCS)] != NULL))
	{
	 /* ... */
	}

      if (map->l_mach.plt == 0)
	*reloc_addr += l_addr;
      else
	*reloc_addr = map->l_mach.plt;
    }
/* ... */
}

static inline int __attribute__ ((unused))
elf_machine_runtime_setup (struct link_map *l, struct r_scope_elem *scope[],
			   int lazy, int profile)
{
  if (l->l_info[DT_JMPREL] && lazy)
    {
      ElfW(Addr) *got;
      extern void _dl_runtime_resolve (ElfW(Word));
      extern void _dl_runtime_profile (ElfW(Word));

      got = (ElfW(Addr) *) D_PTR (l, l_info[DT_PLTGOT]);
      if (got[1])
	{
	  l->l_mach.plt = got[1] + l->l_addr;
	}
      got[1] = (ElfW(Addr)) l;

      /* ... */
    }

  return lazy;
}

[EliaGeretto]

At this point, I think we have probably explored the R_<CLS>_JUMP_SLOT comparison enough. I agree that lazy binding is not replayable in the strong sense, and that avoiding lazy binding is the practical workaround when relocation reprocessing is required.

What I am actually looking for here is an acknowledgment of the Memtag issue and, if an actual ABI-level fix is not practical, at least a sanctioned workaround for this case. In other words, what should consumers that need to reprocess Memtag relocations do?

[smithp35]

Some thoughts on where I've got too so far:

Without wishing to get drawn too deeply into the idempotency debate. I think RELA relocations can be idempotent in as far as calculations that can be expressed using S, P and A exclusively. The MemtagABI, the PauthABI and Morello ABI have a need for extra information that can't be comfortably encoded in S, P or A without additional compromises. For most open platforms which also need to support targets with REL format as well, storing that information in the contents of the place is a useful solution as it requires minimal modification on existing tools to support. The AArch64 ABI has not been written with a hard requirement that all RELA relocations are always idempotent, particularly in the extension area, where the aim there is largely to document the implementation rather than lead it.

There is at least one platform, where storing that additional information in the place doesn't work, or is at least highly inconvenient (could preserve information in the place in a buffer somewhere and restore it). As an aside I have been thinking if there is an alternative design that avoids relocations having been done twice that I'll put in a separate comment.

Some options for the general case:

• Reserve bits of the addend field to encode the additonal information at the expense of compromising the size of addends. This could be handled by a post-linker if the only dynamic relocations are affected.
• If the difference in calculation is fixed, i.e. if the additional information is fixed such as the suggestion to use a fixed offset for the R_AARCH64_RELATIVE memtag ABI then that can be encoded by a new relocation code.
• Store the extra information somewhere else entirely such as a new ELF section. These have a nasty habit of getting broken by third-party and hand-rolled ELF processing tools that aren't aware of them.
• Invent a new relocation format like SHT_AUTH_RELR for this specific case.

The observation we had from the 32-bit ABI was that tool ecosystems will implement what is written in the ABI when the benefit of interoperability outweighs the pain of implementing the ABI. With, so far, only a single use case I'd like to try and find a solution that minises the implementation pain.

What I've got to do next:

Reread the Memtag ABI to see if the combination of PAuthABI and MemtagABI needs to be revisited. The combination of the two extensions is currently theoretical, this is the first project to try and combine them. While we can't change the behaviour that the existing users of PAuthABI and users of Memtag ABI are using; I think the combination is open. For example, instead of using the R_AARCH64_AUTH_* relocations and changing their behaviour when Memtag is active, could explicit AUTH_TAG relocations be defined.

Draft a proposal in a PR.

I'll be away at a conference for most of next week, but will be thinking about this over the coming weeks.

[smithp35]

This is just some musings on how to avoid having to do the relocations twice for ASLR. Feel free to ignore.

The case I'm thinking about where relocations wouldn't need to be done twice is to partition the code and data into an initialisation stage and a post-initialisation stage. The initialisation stage is position dependent and exists only to setup hardware and do the ASLR step. Post ASLR the code and data from the initialisation stage and is never accessed again.

The simplest way to do that would be to make the initialisation stage and the post-initialisation stage separate ELF files, with the initialisation stage effectively a position dependent dynamic loader for the position independent rest of the program. The dynamic loader is only run once, and can in theory be unmapped afterwards.

I don't think that this can easily be done in a single ELF file, at least not without linker changes. Data relocations for the initialisation stage could be concentrated into a single contiguous address range, which would permit filtering out relocations for the post-initialisation data. The problem is the GOT as the linker does not give us any guarantees on the order of the GOT. There may be ways to work around this such as making sure there are no GOT accesses from the initialisation stage, which might be possible using hidden-visibility.

[EliaGeretto]

Reserve bits of the addend field to encode the additonal information at the expense of compromising the size of addends. This could be handled by a post-linker if the only dynamic relocations are affected.

Compromising the size of the addends is problematic for all R_*_RELATIVE relocations. Since A stores the link time value of pointers for those, the effect is capping the maximum value of pointers at link time. If the link time base is set to be low enough, this is not really a deal breaker if we have enough bits available. In concrete:

• PAuth needs 32 bits for the signature schema, only 32 bits pointers can be used at link time.
• Memtag needs only 1 bit, so the size is not a problem.

If the difference in calculation is fixed, i.e. if the additional information is fixed such as the suggestion to use a fixed offset for the R_AARCH64_RELATIVE memtag ABI then that can be encoded by a new relocation code.

The problem with Memtag is that backwards compatibility is stated as a requirement and putting that 1 bit in r_addend would violate it. At that point, we would need a new relocation code anyway, so we might as well add one for normal pointers and one for end pointers. For Memtag, I would prefer this option to stealing bits from r_addend.

@fmayer, @pcc, could you please clarify:

• Are end pointers the only use case for the tag offset? Is 1 bit of information (load tag from this or the previous granule) enough to cover all functionality?
• Is loosing backwards compatibility something that may work for you? This impacts only Memtag globals, which was an Android-only feature until a few months ago. In terms of implementation, do you only need this in LLVM and in the dynamic linker used in Android? Or is it supported somewhere else?

• Store the extra information somewhere else entirely such as a new ELF section. These have a nasty habit of getting broken by third-party and hand-rolled ELF processing tools that aren't aware of them.
• Invent a new relocation format like SHT_AUTH_RELR for this specific case.

From my perspective, the problem that needs to be addressed is that we have relocations that need space for metadata while preserving idempotency so, if we want to go for a "proper" solution at the expense of implementation/adoption effort, we should go for a SHT_RELM with a relocation format that stores: r_offset, r_info, r_addend, r_metadata. The content of r_metadata would be dependent on the relocation code in r_info. RELM relocations, like RELA relocations, would be idempotent. Obviously, Morello, PAuth, and Memtag would be the only users of RELM relocations. SHT_AUTH_RELR solves the problem by removing the idempotency requirement using RELR instead of RELA, but there would be no way to encode PAuth/Memtag relocations without information loss when the relocation is applied.

That said, if there is not enough support for this, a sanctioned workaround is enough for us. I just wanted to sketch how a "complete" solution looks like to me.

The combination of the two extensions is currently theoretical, this is the first project to try and combine them. While we can't change the behaviour that the existing users of PAuthABI and users of Memtag ABI are using; I think the combination is open. For example, instead of using the R_AARCH64_AUTH_* relocations and changing their behaviour when Memtag is active, could explicit AUTH_TAG relocations be defined.

Regarding this, the easy fix is stealing one of the reserved bits in the schema, like you proposed in the call. However, conceptually, adding a new relocation code does indeed make more sense because the relocation operation, the actual formula I mean, would be different. If we could add the new Memtag-only relocations together with those, it would be perfect.

[EliaGeretto]

The case I'm thinking about where relocations wouldn't need to be done twice is to partition the code and data into an initialisation stage and a post-initialisation stage. The initialisation stage is position dependent and exists only to setup hardware and do the ASLR step. Post ASLR the code and data from the initialisation stage and is never accessed again.

The simplest way to do that would be to make the initialisation stage and the post-initialisation stage separate ELF files, with the initialisation stage effectively a position dependent dynamic loader for the position independent rest of the program. The dynamic loader is only run once, and can in theory be unmapped afterwards.

I don't think that this can easily be done in a single ELF file, at least not without linker changes. Data relocations for the initialisation stage could be concentrated into a single contiguous address range, which would permit filtering out relocations for the post-initialisation data. The problem is the GOT as the linker does not give us any guarantees on the order of the GOT. There may be ways to work around this such as making sure there are no GOT accesses from the initialisation stage, which might be possible using hidden-visibility.

The Linux kernel does something similar, if I understand correctly. It initializes the MMU with identity mapped code that is not allowed to use relocated memory locations, then maps the kernel at a randomized address with KASLR, and only then performs the relocations, just before jumping to the KASLR-ed kernel. The kernel tags the symbols that are guaranteed not to use relocations with __pi_ and verifies that the pi/ object files do not contain any R_AARCH64_ABS64 in data sections. So it is indeed feasible.

The problem with this solution is that existing code may have not been designed with this separation in mind, making it infeasible to introduce it after. Relocating twice exploiting the idempotency principle becomes very attractive for this reason. The code needs to be aware that, if relocated locations are actually used, they need to be brought back to their original state before relocating again, e.g., a global empty list should be emptied before relocating again. As I have already mentioned, we already have code that relies on idempotency for its ASLR implementation so, if we want to use PAuth and Memtag, those relocations need to be idempotent as well.

[EliaGeretto]

@smithp35 in the last PAuth sync-up call you mentioned that here in the reference adding is fine, modifying is not. We could give the option to preserve idempotency, like you did with PAuth, by add a R_AARCH64_RELATIVE_MEMTAG_ENDPTR with formula LDG(Delta + A - 16) + 16. All the rest would remain the same. If one does not need idempotency, he can stick to R_AARCH64_RELATIVE with the tag offset written in *P. If instead he needs idempotency, R_AARCH64_RELATIVE is always assumed to have tag offset 0 without reading *P, R_AARCH64_RELATIVE_MEMTAG_ENDPTR would be used for end pointers instead. As you wrote for PAuth, a platform picks one and supports that. It would require a flag in the compiler and/or linker though. Would this work?