Page MenuHomeFreeBSD

rtld: fix SysV hash function overflow
ClosedPublic

Authored by emaste on Apr 12 2023, 2:10 PM.
Tags
None
Referenced Files
Unknown Object (File)
Fri, Mar 22, 9:29 PM
Unknown Object (File)
Fri, Mar 22, 9:29 PM
Unknown Object (File)
Fri, Mar 22, 9:28 PM
Unknown Object (File)
Fri, Mar 22, 9:28 PM
Unknown Object (File)
Fri, Mar 22, 9:28 PM
Unknown Object (File)
Mon, Mar 4, 5:37 AM
Unknown Object (File)
Feb 15 2024, 10:21 AM
Unknown Object (File)
Jan 5 2024, 11:11 AM
Subscribers

Details

Summary
Quoting from https://maskray.me/blog/2023-04-12-elf-hash-function:

The System V Application Binary Interface (generic ABI) specifies the
ELF object file format. When producing an output executable or shared
object needing a dynamic symbol table (.dynsym), a linker generates a
.hash section with type SHT_HASH to hold a symbol hash table. A DT_HASH
tag is produced to hold the address of .hash.

The function is supposed to return a value no larger than 0x0fffffff.
Unfortunately, there is a bug. When unsigned long consists of more than
32 bits, the return value may be larger than UINT32_MAX. For instance,
elf_hash((const unsigned char *)"\xff\x0f\x0f\x0f\x0f\x0f\x12") returns
0x100000002, which is clearly unintended, as the function should behave
the same way regardless of whether long represents a 32-bit integer or
a 64-bit integer.

Sponsored by:   The FreeBSD Foundation

Diff Detail

Lint
Lint Skipped
Unit
Tests Skipped

Event Timeline

emaste created this revision.

I read that thread. Wouldn't it be better/cleaner to change types to uint32_t, or even Elf32_Word?

sys/kern/link_elf.c
1480–1481

g is unused now?

Use 0x0fffffff to make it more obvious that this is 28 bits not 32.

Still do not want to use Elf32Word?

BTW, what about re-indenting the function as the preparatory commit? You change more lines than keep intact.

sys/kern/link_elf.c
1473

The last sentence from the comment is worth keeping as well, IMO.

1480–1481

I mean, the h var type should be changed as well.

  • More kib feedback
  • Reindent first (this diff is against the reindent, which will be committed independently first)
  • edit libexec/rtld-elf/rtld.c instead of sys/kern/link_elf.c

Presumably we should make the same change in rtld.c and link_elf.c

libexec/rtld-elf/rtld.c
1805
sys/kern/link_elf.c
1479
1480

Include both rtld and kernel.
I'd expect this to be three separate commits:

  • reindent rtld
  • rtld
  • kernel
libexec/rtld-elf/rtld.c
1805

will include with the reindent commit

This revision is now accepted and ready to land.Apr 12 2023, 3:45 PM

LGTM. I made a post last night and did plan to make this FreeBSD change for my exercise, but you beat it to me :)

elf_hash((const unsigned char *)"ZZZZZW9p")) == 100000000. This is an all-ascii-alphanumeric identifier.
For extra fun, you may try ld -shared --hash-style=sysv and ensure 100000000 % nbucket != 0 (lld sets nbucket to the number of dynamic symbols) and see whether the dynamic symbol cannot be bound without this patch:)

For extra fun, you may try ld -shared --hash-style=sysv and ensure 100000000 % nbucket != 0 (lld sets nbucket to the number of dynamic symbols) and see whether the dynamic symbol cannot be bound without this patch:)

Indeed, I made a test object with two functions

void ZZZZZW9p(void) { }
void fn(void) { }

which gives 3 dynamic symbols.

SysV hash section:

Hex dump of section '.hash':
  0x00000210 03000000 03000000 01000000 00000000 ................
  0x00000220 02000000 00000000 00000000 00000000 ................

When linked with --hash-style=sysv, dlsym(dl, "ZZZZZW9p") returns null (i.e., fails). When linked wtih --hash-style=gnu it works. With this patch (D39517) applied to rtld it works for both hash styles.

For extra fun, you may try ld -shared --hash-style=sysv and ensure 100000000 % nbucket != 0 (lld sets nbucket to the number of dynamic symbols) and see whether the dynamic symbol cannot be bound without this patch:)

Indeed, I made a test object with two functions

void ZZZZZW9p(void) { }
void fn(void) { }

which gives 3 dynamic symbols.

SysV hash section:

Hex dump of section '.hash':
  0x00000210 03000000 03000000 01000000 00000000 ................
  0x00000220 02000000 00000000 00000000 00000000 ................

When linked with --hash-style=sysv, dlsym(dl, "ZZZZZW9p") returns null (i.e., fails). When linked wtih --hash-style=gnu it works. With this patch (D39517) applied to rtld it works for both hash styles.

Did you tried linking the dso with ld.bfd?

it looks like bfd sets nbuckets=1 for my test object so isn't useful to create the problem.

Hex dump of section '.hash':
  0x00000120 01000000 03000000 02000000 00000000 ................
  0x00000130 00000000 01000000                   ........

but bfd added & 0xffffffff decades ago as mentioned in the blog - https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=32dfa85d9015feea4a06d423fe58f6eaf841456e