在Linux系统中，ELF（Executable and Linkable Format）文件是一种广泛使用的二进制文件格式，用于可执行文件、目标代码、共享库等。ELF文件中的动态链接信息通过动态节（dynamic section）来管理，其中包含了多种类型的表，用于加速符号解析过程。本文将深入探讨两种哈希表：DT_HASH 和 DT_GNU_HASH，以及它们的实现和对比【本文采用案例：android的动态链接库】。
⊙一、背景知识
⊙二、DT_HASH
⊙三、DT_GUN_HASH
一、背景知识
ELF文件和动态链接
ELF文件包含多个节（section），每个节包含特定类型的数据，比如代码、数据、符号表等。在程序运行时，动态链接器（dynamic linker）负责解析符号地址，即找到函数和变量的实际存储位置。为了加速这个过程，ELF文件使用了哈希表。
符号查找的挑战
在动态链接过程中，符号查找是一个关键步骤。传统的线性查找方法效率低下，对于大型应用程序来说，这种方法的性能瓶颈尤为明显。为了解决这一问题，ELF文件引入了哈希表，以提高符号查找的效率。
二、DT_HASH
这个好像当时大学数据结构课的hash表，没有那么复杂。
DT_HASH 是较早的一种哈希表实现，用于加速动态链接过程中的符号查找。我们来详细看看它的结构和工作原理。
2.1 结构
DT_HASH 包含以下几部分：
nbucket（桶数组大小）：一个无符号整数，表示桶数组的大小。
nchain（链表数组大小）：一个无符号整数，表示链表数组的大小。
bucket（桶数组）：大小为 nbucket 的数组，每个元素都是一个无符号整数，指向符号表中的某个位置。
chain（链表数组）：大小为 nchain 的数组，每个元素都是一个无符号整数，用于解决哈希冲突
下面是android linker，对于DT_HASH中数据的填充赋值：
为了更方便的理解DT_HASH如何通过通过hash来找到函数地址。
这个表应该注意，symtab和chain表都是一一对应的。
这里举两个例子：
-
freelocal：
//计算哈希值hash = elf_hash("freelocal") = 0x0bc334fc//桶索引计算，查找桶数组chain starts at bucket[0x0bc334fc % 4] = bucket[0] = 2//遍历链表数组symbols[2] (= "freelocal") == "freelocal"? yep => found at index 2
这里通过一次查找桶数组寻找到了symtab。
2.getspen
//计算hash值hash = elf_hash("getspen") = 0x0dcba6de//桶索引计算，查找桶数组chain starts at bucket[0x0dcba6de % 4] = bucket[2] = 1//遍历链表数组symbols[1] (= "isnan") == "getspen"? nope => chain continues at 5symbols[5] (= "endrpcen") == "getspen"? nope => chain continues at 7symbols[7] (= "setrlimi") == "getspen"? nope => chain continues at 9symbols[9] (= "getspen") == "getspen"? yep => found at index 9
这里详细描述下对于getspen:
首先计算hash值；
根据hash值计算出来桶索引位2，桶所存储的index为1。
先去符号表里面1的位置发现symbol的name位isnan，不是getspen，那么去index1的chain表中看到的是5，那么接着去index5的symbol去寻找，然后按照这个寻找模式，就找到了再symbol9的位置找到了。
3.foobar:
hash = elf_hash("foobar") = 0x06d65882chain starts at bucket[0x06d65882 % 4] = bucket[2] = 1symbols[ 1] (= "isnan") == "foobar"? nope => chain continues at 5symbols[ 5] (= "endrpcen") == "foobar"? nope => chain continues at 7symbols[ 7] (= "isinf") == "foobar"? nope => chain continues at 9symbols[ 9] (= "getspen") == "foobar"? nope => chain continues at 10symbols[10] (= "umoun") == "foobar"? nope => chain continues at 13symbols[13] (= "getttyen") == "foobar"? nope => chain continues at 14symbols[14] (= "uselib") == "foobar"? nope => chain continues at 0symbols[ 0] is STN_UNDEF => not found
到这里DT_HASH就结束了，在早期的hash表中，DT_HASH,是被采用的，但是现在新版的NDK编译so库，一般都是DT_GNU_HASH。
优点：
结构简单，易于实现。
对于小型符号表，查找效率较高。
缺点：
哈希冲突处理机制较简单，当符号表较大时，链表长度增加，查找效率下降。
没有利用更多的优化技术，如布隆过滤器。
三、DT_GNU_HASH
DT_GNU_HASH 是GNU扩展的一种哈希表实现，它在结构和查找算法上都有一些改进，从而在某些情况下比 DT_HASH 更高效。
DT_GNU_HASH 的结构如下：nbucket（桶数组大小）：一个无符号整数，表示桶数组的大小。symndx（符号表起始索引）：一个无符号整数，表示符号表的起始索引。maskwords：一个无符号整数，表示布隆过滤器的大小。shift：一个无符号整数，用于哈希计算。bloom_filter（布隆过滤器）：用于快速排除不存在的符号。bucket（桶数组）：大小为 nbucket 的数组，每个元素都是一个无符号整数，指向符号表中的某个位置。chain（链表数组）：用于解决哈希冲突。
为了理解：
1.gnu_bucket里面装的是symbol和chain的index。
2.和上面的dt_hash一样，在dt_gnu_hash中，symbol和chain表是平行的。
3.gnu_bloom_filter，是实现的布隆过滤器：在这里你需要知道，他会根据你传入的字符串，例如strlen，然后算出hash，就可以判断出是否在hash表存在，时间复杂度比较低。
4.查找过程
4.1首先gnu_bucket_[hash % gnu_nbucket_]; 这个也就上图步骤1的index，然后根据这个index去符号表中去对比符号表的name是否和他一致，如果不一致，在chain中继续往下(这里注意在chain中往下寻找的结束条件，是最低位位0)
bool gnu_lookup(char * name) {uint32_t hash = gnu_hash(name);uint32_t h2 = hash >> gnu_shift2_;uint32_t bloom_mask_bits = sizeof(ElfW(Addr))*8;uint32_t word_num = (hash / bloom_mask_bits) & gnu_maskwords_;ElfW(Addr) bloom_word = gnu_bloom_filter_[word_num];// test against bloom filterif ((1 & (bloom_word >> (hash % bloom_mask_bits)) & (bloom_word >> (h2 % bloom_mask_bits))) == 0) {printf("not found sym %sn",name);return true;}// bloom test says "probably yes"...uint32_t n = gnu_bucket_[hash % gnu_nbucket_];if (n == 0) {printf("NOT FOUND %sn",name);return true;}do {ElfW(Sym)* s = symtab_ + n;// const ElfW(Versym)* verdef = get_versym(n);// // skip hidden versions when verneed == kVersymNotNeeded (0)// if (verneed == kVersymNotNeeded && is_versym_hidden(verdef)) {// continue;// }if (((gnu_chain_[n] ^ hash) >> 1) == 0 &&strcmp((char *)strtab_ +symtab_[n].st_name, name) == 0 ) {printf("hash~find%",name);return true;}} while ((gnu_chain_[n++] & 1) == 0);}
其过程已经用代码实现。
通过这一原理我们可以根据bucket的长度遍历bucket，从而能得到所有的hash表及其地址。
//是一个数量，-1未bucket的个数 182-1gnu_nbucket_ = reinterpret_cast<uint32_t *>(load_bias_ + d->d_un.d_ptr)[0];// skip symndxgnu_maskwords_ = reinterpret_cast<uint32_t *>(load_bias_ + d->d_un.d_ptr)[2];//256gnu_shift2_ = reinterpret_cast<uint32_t *>(load_bias_ + d->d_un.d_ptr)[3];gnu_bloom_filter_ = reinterpret_cast<ElfW(Addr) *>(load_bias_ + d->d_un.d_ptr + 16);//hex桶gnu_bucket_ = reinterpret_cast<uint32_t *>(gnu_bloom_filter_ + gnu_maskwords_);// amend chain for symndx = header[1]gnu_chain_ = gnu_bucket_ + gnu_nbucket_ -reinterpret_cast<uint32_t *>(load_bias_ + d->d_un.d_ptr)[1];--gnu_maskwords_;//打印hash表for(int i=0;i<gnu_nbucket_;i++){size_t n = gnu_bucket_[i];if(n){printf("hash_addr:%08x,name: %sn",symtab_[n].st_value,(char *)strtab_ +symtab_[n].st_name);}while((gnu_chain_[n] &1)==0){n++;printf("hash_addr:%08x,name: %sn",symtab_[n].st_value,(char *)strtab_ +symtab_[n].st_name);}}
还可以根据字符串的hash找到函数偏移
优点：布隆过滤器：能够快速排除不存在的符号，减少不必要的查找，提高查找效率。优化的哈希函数：减少了哈希冲突的概率，提高了查找效率。更紧凑的链表结构：通过更高效的链表遍历，减少了查找时间。缺点：结构复杂度较高，实现和理解相对较难。由于布隆过滤器的存在，存在一定的误判率（即布隆过滤器可能错误地认为一个不存在的符号存在）。
更好的逆向和爬虫学习可以关注我朋友～：
我是BestToYou,分享工作或日常学习中关于Android、iOS逆向及安全防护的一些思路和一些自己闲暇时刻调试的一些程序,文中若有错误或者不足的地方,恳请大家联系我批评指正。
扫码加我为好友
原文始发于微信公众号（二进制科学）：深入理解ELF文件中的哈希表：DT_HASH与DT_GNU_HASH
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论