hazel'blog

字符串-反转字符串II

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += (2 * k)){
            if(i + k <= s.size()){
                reverse(s, i, i + k - 1);
                continue;
            }
            reverse(s, i, s.size() - 1);

        }
       
        return s;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        def reverse_substr(text):
            left, right = 0, len(text) - 1
            while left < right:
                text[left], text[right] = text[right], text[left]
                left += 1
                right -= 1
            return text
        
        res = list(s)

        for cur in range(0, len(s), 2*k):
            res[cur : cur + k] = reverse_substr(res[cur : cur + k]) 
        return ''.join(res)

字符串-反转字符串

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    void reverseString(vector<char>& s) {
        int fast = s.size() - 1;
        int slow = 0;
        while(fast > slow){    //fast != slow会出错,当字符串是偶数的时候会出事，fast与slow永远不会相等
            char tmp = s[slow];
            s[slow] = s[fast];
            s[fast] = tmp;
            fast--;
            slow++;
        }
    }
};

//可以直接用swap
class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        
        # 该方法已经不需要判断奇偶数，经测试后时间空间复杂度比用 for i in range(right//2)更低
        # 推荐该写法，更加通俗易懂
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

哈希表-四数之和

题目链接

这道题采用双指针的方法，首先顺序依次是i，j，left，right。和三数之和是一样的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++){

            if(i > 0 && nums[i] == nums[i - 1])continue;

            for(int j = i + 1; j < nums.size(); j++){

                if(j > i + 1 && nums[j] == nums[j - 1])continue;

                int left = j + 1;
                int right = nums.size() - 1;

                while(left < right){
                   // if(nums[i] + nums[j] + nums[left] + nums[right] > target)right--;//会溢出
                    if(nums[i] + nums[j] > target - (nums[left] + nums[right]))
                        right--;
        

                    else if(nums[i] + nums[j] < target - (nums[left] + nums[right]))
                        left++;

                    else{
                        result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                        while(left < right && nums[right] == nums[right - 1]) right--;
                        while(left < right && nums[left] == nums[left + 1]) left++;

                        right--;
                        left++;
                    }
                    

                }
            }

        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n):
        if i > 0 and nums[i] == nums[i - 1]: continue
        for k in range(i+1, n):
            if k > i + 1 and nums[k] == nums[k-1]: continue
            p = k + 1
            q = n - 1

            while p < q:
                if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                else:
                    res.append([nums[i], nums[k], nums[p], nums[q]])
                    while p < q and nums[p] == nums[p + 1]: p += 1
                    while p < q and nums[q] == nums[q - 1]: q -= 1
                    p += 1
                    q -= 1
    return res

摘要

​ 该文研究了恶意软件的规避行为。论文收集了92种恶意软件用来检测和以及阻止检测的规避技术，并做了系统化，提供了一种根据这些技术的语义和特征进行分类的分类方法。实现了一个对x86二进制文件进行逃避分析的框架，分析了2010年至2019年期间的45,375个恶意软件样本，并采取将这种分析与合法的主流windoiws程序进行比较的方法，来研究规避行为的内在特征。还研究了恶意软件家族与所采用的规避技术之间的相关性。并且论文确定了特定于恶意代码的技术，而不是恶意代码与合法软件都会使用的技术。

​ 论文实验结果体现了规避技术的使用以及随着时间的演变，发现规避行为十年间，在数量上仅仅增加了12%，但是在技术上已经有显著的提高。最后论文研究了如何应对新型规避技术的部署。

规避技术分类法

​ 该文根据在操作系统上执行的动作的语义来进行分类。基于先前提出的系统化，该文还开发了由16个语义等价组组成的分类法。有内存指纹、异常处理、CPU指纹、表描述符、陷阱、时间、暂缓、人类交互、注册表、系统环境、WMI、进程环境、文件系统、枚举进程、枚举服务、枚举驱动。 通过静态分析每个二进制程序，计算了实现92个规避技术所需的基本块、指令和函数调用的数量。

分析框架

​ 可以实现四个级别的检测：指令（监控每个执行指令）、API hook（hook一些感兴趣的Windows API）、系统调用（hook感兴趣的系统调用）、内存访问（监视对特定内存区域的访问）。系统会在逃避前后进行hook,这两个hook都会采用日志记录规避行为。

​ 系统根据级别分为了四个模块，并且还增加了一个库追踪器模块，用来记录规避技术和相关库的调用堆栈。

规避行为分析

​ 该部分根据五个问题展开

1.恶意软件最常见的规避技术是什么？

​ 时间和暂缓技术是使用最多的，搜索特定的驱动程序很少被用到，并且实验数据并未观察到对WMI的使用。恶意软件家族也会寻找关键字，其中“vbox”、“sandbox”和“虚拟virtualbox”是最常用的关键字。

2.恶意软件家族和采用的规避行为技术之间有什么联系吗？

​ 事实上，恶意软件样本通常是由工具构建的。恶意软件的作者通常开发可以很容易地用来生成新的样本的工具。该文建立了一个随机森林分类器；分类器的输入是一个布尔变量数组，表示样本中每种技术的使用情况；分类器的输出是族标签。我们为123个家族（所有至少有50个样本的家族）建立了123个分类器。每个分类器的输出采用分层抽样进行3倍交叉验证训练。对于每个分类器，计算了f1-score，这是一个评估分类器性能的指标，并考虑了所有的混淆矩阵。

3.在过去的10年里，每个家庭和每个类别所采用的规避技术的数量是否发生了变化？

​ 该部分研究了每种技术的使用周期，规避技术的使用量，单个样本所使用的规避技术的最大数量，恶意样本规避的四大目标占比。

4.采用恶意软件规避技术如何影响安全社区，反之亦然？

​ 如果该技术已经被广泛采用/已知，在报告发布后，我们注意到在随后的几年中它们的使用有轻微和暂时的下降。相反，如果该技术几乎很少被使用或者被知道，在报告发布后的接下来的几年里，它的采用迅速增加。一旦一种技术被广泛使用，相关报告的数量就会显著增加。

5.合法的软件是否也采用了规避技术？

​ 合法的程序也会采用规避技术，但是并不是很常见。特别是，只有少数技术被普遍采用，这表明这种技术并不主要用于真正的规避目的。

​ 基于良性软件分析，对每个技术进行了分类：

​ 被恶意软件使用的规避技术。这是在良性软件样本中从未观察到的逃避行为，或者手动验证了它在良性软件样本中被用作一种逃避机制。

​ 被用于良性软件的规避技术。这是在超过1%的良性软件样本中观察到的规避行为，或者手动验证没有被用作逃避行为。

​ 堆溢出是指程序向某个堆块中写入的字节数超过了堆块本身可使用的字节数，因而导致了数据溢出，并覆盖到物理相邻的高地址的下一个堆块。但是其与栈溢出所不同的是，堆上并不存在返回地址等可以让攻击者直接控制执行流程的数据，因此我们一般无法直接通过堆溢出来控制 EIP 。

Linux内存布局

先提一下windows的内存布局

linux 64位下内存布局如下，这种内存布局方式沿用的32位模式下内存的经典布局，但是栈和mmap的映射区域不再是从一个固定的地方开始，每次启动时的值都不一样。这样一来，使得使用缓冲区溢出攻击变得更加困难。（32位中，程序能够访问的最后地址是0xbfffffff(3G)的位置，3G以上的位置是给内核使用的，应用程序不能直接访问。）

heap操作的相关函数

​ brk()是系统调用、sbrk()是库函数。c语言的动态内存分配基本函数是malloc()，在linux上的实现是：malloc()函数调用库函数sbrk()，sbrk()的实质是调用brk()函数。brk()是一个简单的系统调用，只是简单的改变mm_struct结构体的成员变量brk的值。

Mmap映射区域操作的相关函数

​ malloc 会使用mmap来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存，并且这块内存仅被调用进程所使用。mmap()函数将一个文件或者其他对象映射进内存。文件被映射到多个页上，如果文件大小不是所有页大小之和，最后一个页不被使用的空间将会清零。munmap()执行相反的操作，删除特定地址区域的对象映射。

1

void * mmap(void * start,size_t length,int prot,int flags,int fd,off_t offset)

​ start — 映射区的开始地址。

​ length — 映射区的长度。

​ prot — 期望的内存保护标志。

​ flags — 指定映射对象的类型，映射选项和映射页是否可以共享。

​ fd — 有效的文件描述符。

​ offset — 被映射对象内容的起点。

​ mmap()系统调用使得进程之间通过映射同一个普通文件实现共享内存。但是并不是完全为了用于共享内存而设计的。它本身提供了不同于一般对普通文件的访问方式，进程可以像读写内存一样对普通文件的操作。

​ 普通文件被映射到进程地址空间后，进程可以像访问普通内存一样对文件进行访问，不必再调用read()，write()等操作。mmap并不分配空间, 只是将文件映射到调用进程的地址空间里（但是会占掉你的 virutal memory）, 然后你就可以用memcpy等操作写文件, 而不用write()了。写完后，内存中的内容并不会立即更新到文件中，而是有一段时间的延迟，你可以调用msync()来显式同步一下, 这样你所写的内容就能立即保存到文件里了。不过通过mmap来写文件这种方式没办法增加文件的长度, 因为要映射的长度在调用mmap()的时候就决定了。

堆基础知识

​ 先补充一下堆的基础知识，如下图。堆的结构是由“堆表”以及“堆块”构成这，其中“堆表”主要作用是用来索引堆块的位置。其中，堆表主要是有两种：空闲双向链表（Freelist）,快速单向链表（Lookaside）（注意：堆表仅仅是用来索引空闲态的堆块，即未被使用的堆块）“堆块”就是用来提供程序员申请堆空间的。

​ 未使用下的堆块与使用状态下的堆块差别在于，堆首部分添加了8字节的指针对，该指针就是用来链路堆表当中的。

​ 堆表中需要关注的是空表索引区，由128项指针数组组成，这对指针用来将空闲堆组织成双向链表。根据堆块大小的不同，存放的指针数组也不同。每项链接的堆块大小均比其前一项链接的堆块增大8字节。值得注意的是free[0]链接的是大于等于1024字节的堆块。

​ 下图是空闲双向链表，当释放相邻内存堆块后会发生合并现象，该点区别于快速单向链表，快速单向链表每项只有四个节点

​ linux早期的堆分配，为了安全性，一个线程使用堆时，会进行加锁。然而，与此同时，加锁会导致其它线程无法使用堆，降低了内存分配和回收的高效性。同时，如果在多线程使用时，没能正确控制，也可能影响内存分配和回收的正确性。后来在此基础上进行改进使其可以支持多线程，这个堆分配器就是 ptmalloc 。目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器：ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

​ 需要注意的是，在内存分配与使用的过程中，Linux 有这样的一个基本内存管理思想--内存延迟分配，只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存，但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，系统才会真正分配物理页面给用户使用。

内存分配与回收

先说上面面三个概念，三者概念的解释如下：

• arena：通过sbrk或mmap系统调用为线程分配的堆区，按线程的类型可以分为2类：
  • main arena：主线程建立的arena；
  • thread arena：子线程建立的arena；
• chunk：逻辑上划分的一小块内存，根据作用不同分为4类：
  • Allocated chunk：即分配给用户且未释放的内存块；
  • Free chunk：即用户已经释放的内存块；
  • Top chunk：顶块, 位于所有块之后, 保存着未分配的所有内存；
  • Last Remainder chunk
• bin：一个用以保存Free chunk链表的表头信息的指针数组，按所悬挂链表的类型可以分为4类:
  • Fast bin：chunk 的指针数组 , 每个元素是一 条单向链表的头部 , 且同一条链表中块的大小相同，主要保存大小 32 至 128 字节的块；
  • Unsorted bin：与 Small Bins 和 Large Bins 类似是双向循环链表 , 只有一个 bin, 其中保存的块大小不定，用于收集刚刚被 free 或从大的块中分裂剩下的块；
  • Small bin：chunk 的指针数组 , 每个元素是一条双向循环链表的头部 , 且同一条链表中块的大小相同，主要保存大小 32 至 1024 字节的块；
  • Large bin：每个元素是一条双向循环链表的头部 , 但同一条链表中块的大小不一定相同 , 按照从大到小的顺序排列 , 每个 bin 保存一定大小范围的块。主要保存大小 1024 字节以上的块。

在这里读者仅需明白arena的等级大于bin的等级大于(free)chunk的等级即可，即A>B>C。

main arena中的内存申请

与 thread 不同的是，main_arena 并不在申请的 heap 中，而是一个全局变量，在 libc.so 的数据段。

thread arena中的申请

chunk

在程序的执行过程中，我们称由 malloc 申请的内存为 chunk 。这块内存在 ptmalloc 内部用 malloc_chunk 结构体来表示。当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。

1
2
3
4
5
6
7
8
9
10
11
12

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

用户最小申请的内存大小必须是 2 * SIZE_SZ 的最小整数倍。32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。

​ 上图是在使用中的chunk 。

​ <1>chunk指针指向chunk开始的地址；mem指针指向用户内存块开始的地址。

​ <2> p=0时，表示前一个chunk为空闲，prev_size才有效。

​ <3> p=1时，表示前一个chunk正在使用，prev_size无效。 p主要用于内存块的合并操作。

​ <4> ptmalloc分配的第一个块总是将p设为1,以防止程序引用到不存在的区域。

​ <5> M=1 为mmap映射区域分配；M=0为heap区域分配。

​ <6> A=1 为非主分区分配；A=0 为主分区分配。

上图是一个空闲的chunk

<1> 空闲的chunk会被放置到空闲的链表bins上。当用户申请内存malloc的时候，会先去查找空闲链表bins上是否有合适的内存。

​ <2> fp和bp分别指向前一个和后一个空闲链表上的chunk

​ <3>fp_nextsize和bp_nextsize分别指向前一个空闲chunk和后一个空闲chunk的大小，主要用于在空闲链表上快速查找合适大小的chunk。

​ <4>fp、bp、fp_nextsize、bp_nextsize的值都会存在原本的用户区域，这样就不需要专门为每个chunk准备单独的内存存储指针了。

​ 当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用。这就是 chunk 中的空间复用。

空闲chunk容器

bin

​ 用户释放掉的内存并不是马上就归还给操作系统，ptmalloc会统一管理heap和mmap映射区中的空闲的chunk，当用户进行下一次请求分配时，ptmalloc会试图从空闲的内存中挑选一块给用户，这样可以避免频繁的系统调用，降低了内存分配的开销。ptmalloc将大小相似的chunk用双向循环链表连接起来，这样的一个链表称为bin。ptmalloc中一共维护了128个bin，并使用一个数组来存储这些bin（数组实际存储的是指针）。

​ 并不是所有的 chunk 被释放后就 立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的的 chunk 先放到一个叫做 fast bins 的容器内。

分配算法概述

主分配区分配顺序依次为：

fast bins –> small bins –> 合并fast bins并把chunk加入unsorted bins，找unsorted bins

–> 把unsorted bins加入到large bins，找large bins –> top chunk –> 增加heap大小或mmap分配

回收算法概述

free()函数接受一个指向分配区域的指针作为参数，释放指针指向需要释放的chunk。

（1）free()函数首先需要获取分配区的锁来保证线程安全。

（2）判断传入的指针是否为0，如果为0，则什么都不做，直接return。否则转下一步。

（3）判断所需释放的chunk是否为mmaped chunk，如果是，则调用munmap()释放解除空间映射，该空间不再有效。

（4）判断chunk的大小和所处的位置，若chunk_size<= max_fast，并且chunk并不处于heap的顶部，也就是说不与top chunk相邻，则转到下一步，否则转到第6步。

（5）将chunk放到fast bins中，chunk放入到fast bins中时，并不修改该chunk使用状态位P,也不与相邻的chunk进行合并。只是放进去。这一步做完之后释放就结束了，程序从free()函数中返回。

（6）判断前一个chunk是否正在使用中，如果前一个块也是空闲块，则合并。并转下一步。

（7）判断当前释放的chunk的下一个块是否为top chunk，如果是，则转第9步，否则转下一步。

（8）判断下一个chunk是否处于使用中，如果下一个chunk也是空闲的，则合并，并将合并后的chunk放到unsorted bin中。注意，这里在合并过程中，要更新chunk的大小，以反映合并后的chunk的大小。并转到第10步。

（9）如果执行到这一步，说明释放了一个与top chunk相邻的chunk。则无论它有多大，都将它和top chunk合并，并更新top chunk的大小等信息。转下一步。

（10）判断合并后的chunk的大小是否会大于max_fast（默认是64kb），如果是的话，则会触发进行fast bins的合并操作，fast bins中的chunk将被遍历，并与相邻的chunk进行合并，合并后的chunk会被放到unsorted bin中。fast bins将变为空，操作完成后进入到下一步。

（11）判断 top chunk的大小是否大于mmap收缩阀值（默认是128kb），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统。但是最先分配的128KB空间是不会归还给操作系统的，ptmalloc会一直管理这部分内存，用来响应用户的分配请求。如果是非主分配区，会进行sub_heap收缩，将top chunk的一部分返回给操作系统，如果 top chunk是整个sub_heap，会将整个sub_heap归还给操作系统。做完这一步后，释放结束，从free()函数退出。

对于Ubuntu 16.04而言，较小的chunk被free掉后，只是被放入fast bins中，其余什么也不做（见上述第5步）；对于Ubuntu 18.04而言，较小的chunk被free掉后，会被放入tcache bins中，

​

但无论是被放入fast bins还是tcache bins中，chunk的标志位都不会发生变化：

利用该特性，可以在free掉某个内存块后，重新申请处于fast bins或tcache bins中的内存块，并对其进行读写操作，从而达到漏洞利用的目的。

堆溢出利用

堆溢出是一种特定的缓冲区溢出（还有栈溢出， bss 段溢出等）。但是其与栈溢出所不同的是，堆上并不存在返回地址等可以让攻击者直接控制执行流程的数据，因此我们一般无法直接通过堆溢出来控制 EIP 。一般来说，我们利用堆溢出的策略是

1. 覆盖与其物理相邻的下一个 chunk的内容。
   • prev_size
   • size，主要有三个比特位，以及该堆块真正的大小。
     • NON_MAIN_ARENA
     • IS_MAPPED
     • PREV_INUSE
     • the True chunk size
   • chunk content，从而改变程序固有的执行流。
2. 利用堆中的机制（如 unlink 等 ）来实现任意地址写入（ Write-Anything-Anywhere）或控制堆块中的内容等效果，从而来控制程序的执行流。

寻找堆分配函数

​ 通常来说堆是通过调用 glibc 函数 malloc 进行分配的，在某些情况下会使用 calloc 分配。calloc 与 malloc 的区别是 calloc 在分配后会自动进行清空，这对于某些信息泄露漏洞的利用来说是致命的。

1
2
3
4

calloc(0x20);
//等同于
ptr=malloc(0x20);
memset(ptr,0,0x20);

​ 此外还有一种是realloc函数，该函数兼并malloc和free两个函数功能。

• 当 realloc(ptr,size) 的 size 不等于 ptr 的 size 时
  • 如果申请 size > 原来 size
    • 如果 chunk 与 top chunk 相邻，直接扩展这个 chunk 到新 size 大小
    • 如果 chunk 与 top chunk 不相邻，相当于 free(ptr),malloc(new_size)
  • 如果申请 size < 原来 size
    • 如果相差不足以容得下一个最小 chunk(64 位下 32 个字节，32 位下 16 个字节)，则保持不变
    • 如果相差可以容得下一个最小 chunk，则切割原 chunk 为两部分，free 掉后一部分
• 当 realloc(ptr,size) 的 size 等于 0 时，相当于 free(ptr)
• 当 realloc(ptr,size) 的 size 等于 ptr 的 size，不进行任何操作

寻找危险函数

常见的危险函数如下

• 输入
  • gets，直接读取一行，忽略 '\x00'
  • scanf
  • vscanf
• 输出
  • sprintf
• 字符串
  • strcpy，字符串复制，遇到 '\x00' 停止
  • strcat，字符串拼接，遇到 '\x00' 停止
  • bcopy

确定填充长度

这一部分主要是计算我们开始写入的地址与我们所要覆盖的地址之间的距离。 一个常见的误区是 malloc 的参数等于实际分配堆块的大小，但是事实上 ptmalloc 分配出来的大小是对齐的。这个长度一般是字长的 2 倍，比如 32 位系统是 8 个字节，64 位系统是 16 个字节。但是对于不大于 2 倍字长的请求，malloc 会直接返回 2 倍字长的块也就是最小 chunk，比如 64 位系统执行malloc(0)会返回用户区域为 16 字节的块。

还有一点是之前所说的用户申请的内存大小会被修改，其有可能会使用与其物理相邻的下一个 chunk 的 prev_size 字段储存内容。

实际上 ptmalloc 分配内存是以双字为基本单位，以 64 位系统为例，分配出来的空间是 16 的整数倍，即用户申请的 chunk 都是 16 字节对齐的。

例如在 64 位程序中：

1

malloc(8)

申请到的堆块总大小为 16 + 8 + 8 + 1 = 0x21

1.第一个 16 字节是系统最小分配的内存，也就是说你如果想要申请的内存小于系统最小分配的内存的话，就会按照最小的内存来分配。

• 在 64 位系统中这个值是 16 个字节，在 32 位系统中是 8 个字节
• 例如，如果代码中是 malloc(0) 的话，堆管理器也会分配最小内存空间给你

2.第二个 8 字节是 pre size 字段的大小（32 位的为 4 字节）
3.第三个 8 字节为 size 字段的大小（32 位的为 4 字节）
4.最后一个 1 字节是 PREV_INUSE 的值，只有 0 或 1两个值

栈溢出攻击基础知识

​ 栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数，因而导致与其相邻的栈中的变量的值被改变。关于栈溢出攻击，可以看一下下面的图。

​ 缓冲区可以理解为一段可读写的内存区域。代码段存放的是程序的机器码和只读数据。数据段存储的是静态数据和用户的全局变量。堆存储程序运行时分配的变量，大小不固定，由内存地址低向高增长。栈存放函数调用时的临时信息结构，由内存地址高向低增长。入栈（PUSH）时，栈顶变小。出栈（POP）时，栈顶变大。

​ 除了代码段和数据区域，其他的内存区域都能作为缓冲区，因此缓冲区溢出的位置可能在数据段、也可能在堆栈段。

linux安全机制

• canary(GS)：在栈靠近栈底某个位置设置初值，当函数结束时会检查这个栈上的值是否和存进去的值一致，防止栈溢出的一种保护
• relro：主要用来保护重定位表段对应数据区域，默认可写。分为两种，Partial RELRO：got表不可写，got.plt可写。Full RELRO：got表，got.plt不可写
• PIE(ALSR)：程序开启了PIE保护的话，在每次加载程序时都改变加载的基地址，不会影响指令间的相对地址
• NX(DEP)：数据执行保护，指不允许数据页(默认的堆页、各种堆栈页以及内存池页)执行代码

基本ROP

​ 直接向栈或者堆上直接注入代码的方式已经难以发挥效果，提出的主要的绕过保护的方法就是ROP（面向返回的编程），主要思想是在栈缓冲区溢出的基础上，利用程序中已有的小片段 (gadgets) 来改变某些寄存器或者变量的值，从而控制程序的执行流程。所谓 gadgets 就是以 ret 结尾的指令序列，通过这些指令序列，我们可以修改某些地址的内容，方便控制程序的执行流程。

利用条件如下：

        * 程序存在溢出，并且可以控制返回地址。
        * 可以找到满足条件的gadgets以及其地址。

• 序源码自带系统命令函数 -简单溢出
• 可以找到system函数的plt的绝对地址 -ret2text
• 利用输入函数，将shellcode写入到程序中 -ret2shellcode
• 利用ROPGadget配合int 0x80调用execve -ret2Syscall
• 利用Libc获取system函数的相对位置. -ret2Libc

ret2text

ret2text 即控制程序执行程序本身已有的的代码 (.text)。我们控制执行程序已有的代码的时候也可以控制程序执行好几段不相邻的程序已有的代码 (也就是 gadgets)。

1.先查看一下该elf文件，可以看到是32位elf文件见，并且是动态连接的。

查看一下程序的保护机制，可以看到是32位的程序且仅仅开启了栈不可执行保护NX

IDA分析

IDA看一下，可以看到主函数使用了gets函数，显然这个是可以利用的栈溢出漏洞。

查看字符串，双击进去看到是secure函数调用，这也就是gadgets，即反弹shell地址：0x0804863A

构造payload

​ 构造之前，需要计算能够控制得内存起始地址距离main()函数返回地址得字节数。在gets函数那个图中的call前面两行，说明了参数的地址是esp+0x1c，通过动态调试，我们也可以发现这一点。

​ 在0x080486AE处下断点调试

​ ESP为ffffd130，其中存放的内容为ffffd14c，即输入的内容s的地址为ESP+1c= ffffd14c，而EBP为ffffd1b8，则s到EBP的偏移为|ffffd1b8- ffffd14c|=6c，所以s相对与返回地址的偏移为0x6c+4=0x70。

payload

​ 我们的目标就是控制这个ret，由前面分析知，可以利用.text代码段区域中的system(“/bin/sh”)代码，该代码段即为可被ROP利用的Gadget，地址为0x0804863a，将其覆盖到函数返回地址处，前面再padding 70h个字节码即可。（图中应该是sendline，懒得重新截图了）

成功getshell：

ret2shellcode

​ ret2shellcode也就是控制程序执行shellcode(修改函数返回地址，让其指向溢出数据中的一段指令)。要想执行 shellcode，需要shellcode所在的区域具有可执行权限。该方法关键点：

• 溢出点附近有可执行权限，以便让填充的shellcode能够被执行；
• 有类似于jmp esp这样的gadget，使得程序能够跳转到shellcode中。

​ 前提条件：该技术的前提是需要操作系统关闭内存布局随机化以及需要程序调用栈有可执行权限。

静态分析

​ 可以看到是动态链接的32位程序，没有开启任何保护，并且具有可读、可写、可执行段。

​ IDA打开查看，依然是基本的栈溢出漏洞，不过这次将对应字符串复制到了buf2处

​ buf2处于bss段（这次查看字符串，并没有之前所利用的system(“/bin/sh”)了）

​ 先输入命令b main和r，然后输入vmmap查看映射状况，可以看到第三行，buf2所在的bss段具有可读可写可执行权限

调试分析

​ 可以和ret2text一样利用gdb下断点来计算偏移地址，也可以用GDB pattern字符串计算偏移量，先用pattern_create创建计算溢出偏移量的字符串，在输入的时候输入就可以了。（EIP指向CPU即将要执行的指令，SIGSEGV是当一个进程执行了一个无效的内存引用，或发生段错误时发送给它的信号）

​ pattern_offset计算出偏移量。也就是0x70

payload

​ asm()接收一个字符串作为参数，得到汇编码的机器代码。shellcraft模块是shellcode的模块，包含一些生成shellcode的函数。其中的子模块声明架构，比如shellcraft.arm 是ARM架构的，shellcraft.amd64是AMD64架构，shellcraft.i386是Intel 80386架构的，以及有一个shellcraft.common是所有架构通用的。

​ 而这里的shellcraft.sh()则是执行/bin/sh的shellcode了。shellcode.ljust()这段代码就是要讲shellcode不足112长度的地方用a来填充。注意红框部分，圈起来的地方需要b'A'，不然会报错。

ret2syscall

​ ret2syscall即控制程序执行系统调用，获取shell。需要满足两个条件：

    程序中有分别用于控制eax，ebx，ecx，edx的gadgets；
    程序中有int 0x80指令，用于触发系统调用。

​ 一般利用如下系统调用来获取shell：

1

execve("/bin/sh",NULL,NULL)

​ 当遇到32位程序时，需要使得：

• 系统调用号，即 eax 应该为 0xb（0xb 为 execve 对应的系统调用号）
• 第一个参数，即 ebx 应该指向 /bin/sh 的地址，其实执行 sh 的地址也可以。
• 第二个参数，即 ecx 应该为 0
• 第三个参数，即 edx 应该为 0

Linux系统调用的实现

Linux 的系统调用通过 int 80h 实现，用系统调用号来区分入口函数。在 Linux 中，0x80中断处理程序是内核，用于其他程序对内核进行系统调用。操作系统实现系统调用的基本过程是：

• 应用程序调用库函数（API）；
• API 将系统调用号存入 EAX，然后通过中断调用使系统进入内核态；
• 内核中的中断处理函数根据系统调用号，调用对应的内核函数（系统调用）；
• 系统调用完成相应功能，将返回值存入 EAX，返回到中断处理函数；
• 中断处理函数返回到 API 中；
• API 将 EAX 返回给应用程序。

应用程序的调用过程是：

• 把系统调用的编号存入 EAX；
• 把函数参数存入其它通用寄存器；
• 触发 0x80 号中断（int 0x80）。

静态分析

​ 发现文件是32位的静态链接文件，并且只打开了NX保护

​ IDA打开看到，gets函数存在栈溢出风险，

​ 如何控制寄存器的值呢？这里就需要使用 gadgets。比如说，现在栈顶是 10，那么如果此时执行了 pop eax，那么现在 eax 的值就为 10。但是我们并不能期待有一段连续的代码可以同时控制对应的寄存器，所以我们需要一段一段控制，这也是我们在 gadgets 最后使用 ret 来再次控制程序执行流程的原因。具体寻找 gadgets 的方法，我们可以使用 ropgadgets 这个工具。

​ 寻找pop eax~edx+ret寄存器的指令，记下符合条件的地址分别为0x080bb196和0x0806eb90：

​ 类似于之前的做法，我们可以获得 v4 相对于 ebp 的偏移为 108。所以我们需要覆盖的返回地址相对于 v4 的偏移为 112。此次，由于我们不能直接利用程序中的某一段代码或者自己填写代码来获得 shell，所以我们利用程序中的 gadgets 来获得 shell，而对应的 shell 获取则是利用系统调用。

​ 我们还需要获得 /bin/sh 字符串对应的地址，还有 int 0x80 的地址。

payload

payload构造如下，要在将返回地址指向int 0x80,在返回之前要将四个寄存器赋值完成，所以最终payload构成是

1

payload = padding+pop_eax+”0xb”+pop_edx_ecx_ebx+0+0+”/bin/sh”+int 0x80

ret2libc

​ libc是Standard C library的简称，它是符合ANSI C标准的一个函数库。libc库提供C语言中所使用的宏，类型定义，字符串操作函数，数学计算函数以及输入输出函数等。简而言之，每个使用了标准库函数的Linux程序，都会加载libc，以便能够真正调用这些库函数。在Ubuntu中，libc的实现是libc.so.6（32位）或libc-2.xx.so（64位），不同的Ubuntu系统，xx是不一样的，例如Ubuntu 16.04的64位libc实现是libc-2.23.so。

​ 这种攻击方式主要是针对 动态链接(Dynamic linking) 编译的程序，因为正常情况下是无法在程序中找到像 system() 、execve() 这种系统级函数(如果程序中直接包含了这种函数就可以直接控制返回地址指向他们，而不用通过这种麻烦的方式,，比如ret2text)。因为程序是动态链接生成的，所以在程序运行时会调用 libc.so (程序被装载时，动态链接器会将程序所有所需的动态链接库加载至进程空间，libc.so 就是其中最基本的一个)，libc.so 是 linux 下 C 语言库中的运行库glibc 的动态链接版，并且 libc.so 中包含了大量的可以利用的函数，包括 system() 、execve() 等系统级函数，我们可以通过找到这些函数在内存中的地址覆盖掉返回地址来获得当前进程的控制权。

​ 就像Windows里面对DLL的调用一样，如果一个Linux程序想要隐式调用libc库函数，就需要在程序的“导入表”中填写该函数的相关信息，包括函数名。当然，Linux是没有“导入表”这个概念的，取而代之的是.plt表和.got表，对比Windows，它们就像INT表和IAT表。前者是编译后就已经写好的，里面并不包含真正的目标函数地址；后者是在运行时确定的，包含真正的目标函数地址。

​ 为什么要多用一个PLT表？原因是为了程序的运行效率，GOT表的初始值都指向PLT对应的某个片段中，而对应的PLT片段中包含能够解析函数地址的函数。（提高效率的原因就在这里）

​ 外部函数的内存地址存储在 GOT 而非 PLT 表内，PLT 存储的入口点又指向 GOT 的对应条目，那么程序为什么选择 PLT 而非 GOT 作为调用的入口点呢？GOT 表的初始值都指向 PLT 表对应条目中的某个片段，这个片段的作用是调用一个函数地址解析函数。当程序需要调用某个外部函数时，首先到 PLT 表内寻找对应的入口点，跳转到 GOT 表中。如果这是第一次调用这个函数，程序会通过 GOT 表再次跳转回 PLT 表，运行地址解析程序来确定函数的确切地址，并用其覆盖掉 GOT 表的初始值，之后再执行函数调用。当再次调用这个函数时，程序仍然首先通过 PLT 表跳转到 GOT 表，此时 GOT 表已经存有获取函数的内存地址，所以会直接跳转到函数所在地址执行函数。整个过程如下面两张图所示。

​

再次调用的时候如下：

​ ret2libc，即控制执行 libc 中的函数，通常是返回至某个函数的 plt 处或者函数的具体位置 (即函数对应的 got 表项的内容)。一般情况下，我们会选择执行 system(“/bin/sh”)，故而此时我们需要知道 system 函数的地址。

1
2
3
4
5
6
7
8
9
10

1、泄露一个ret2libc函数的位置
2、获取libc的版本
3、根据偏移获取shell和sh的位置
4、执行程序获取shell

libc版本
1、https://libc.blukat.me。  2. LibcSearcher

1、求libc基地址（函数动态地址-函数偏移量）
2、求其他函数地址（基地址+函数偏移量）

静态分析

​ 首先看一下程序基本情况，发现是动态链接的并且只开启了NX保护

​ IDA查看

​ 可知“/bin/sh”字符串所在地址为0x08048720。

​ 因为要从libc中寻找利用函数，则可以在ida直接查看plt中是否有system()函数，发现是存在有的且地址为0x08048460,其内容只是一条jmp指令，跳转到.got表的地址中去。

​ 而.got表又是程序运行起来之后动态填充的，因此，我们在进行pwn时，只需返回到.plt表中的对应函数地址处，就能够让系统“帮忙”调用目标函数了。

​ 至于用户输入的变量v4距函数返回地址的偏移地址的计算如之前所示，结果是一样的为0x70。

payload

​ 这里我们需要注意函数调用栈的结构，如果是正常调用 system 函数，我们调用的时候会有一个对应的返回地址，这里以’bbbb’ 作为虚假的地址，其后参数对应的参数内容。

只有system(),无‘bin/sh’

​ 此次需要我们自己来读取字符串，所以我们需要两个 gadgets，第一个控制程序读取字符串，第二个控制程序执行 system(“/bin/sh”)。

​ 可以在plt中看到有gets()函数，即可以将该gets()函数地址用来踩掉原本程序函数的返回地址，然后通过输入的方式将“/bin/sh”输入进去。换句话说，整个过程分成了两部分，第一部分是将“/bin/sh”读入到内存中；第二部分是执行system()获取shell。

​ 可知get()函数地址为08048460。查看gets()函数，其需要一个可读可写的指针参数，且会返回值

​ 寻找一块可读可写的buffer区，通常会寻找.bss段，使用IDA查看可看到存在buf2[100]数组，并且调用命令vmmap可以看到该.bss段可读可写。

​ 因为在gets()函数完成后需要调用system()函数需要保持堆栈平衡，所以在调用完gets()函数后提升堆栈，这就需要add esp, 4这样的指令但是程序中并没有这样的指令。更换思路，通过使用pop xxx指令也可以完成同样的功能，在程序中找到了pop ebx，ret指令。通过ROPgadget工具查看，发现存在一条符合条件的指令，地址为0x0804841d

payload构造如下

无system(),无‘bin/sh’

​ 通常情况下，并没有这么好的条件让我们能够直接调用system。我们需要想办法通过已知函数地址，去推测system函数的地址。

​ 由于一个ELF文件在生成完成后，它的不同函数之间的偏移地址是不会改变的，或者说，每一个函数与文件起始地址之间的偏移是不会改变的。所以我们可以通过泄露libc中某个被调用过的函数的地址来获取libc版本，获取libc中各个偏移地址值，然后通过某个函数的真实地址计算出system()和/bin/bash的真实地址。

​ 对于system()函数，其属于libc，在libc.so动态链接库中的函数之间相对偏移是固定的。我们由泄露的某个函数的GOT表地址可以计算出偏移地址（A真实地址-A的偏移地址 = B真实地址-B的偏移地址 = 基地址），从而可以得到system()函数的真实地址（当然也可以直接调用pwntools的libc.address得到libc的真实地址，然后再直接查找即可找到真实的system()函数地址）。

利用过程

​ 红色箭头为第一次溢出调用，通过gets()栈溢出至函数返回地址处将其覆盖为puts的plt地址，将puts的GOT表地址泄露输出出来，再返回到_start()函数重新执行程序；蓝色箭头为程序第二次执行时的溢出调用，重新通过gets()输入内容栈溢出至函数返回地址处，覆盖该地址为libc中找到的system()地址（libc地址由泄露的puts函数地址计算得出），从而getshell：

• 将puts()的plt地址覆盖到函数返回地址处，通过puts()泄露某个已执行过的函数的GOT地址，并且返回地址设置为_start()或main()，以便于重新执行一遍程序
• 通过recv(4)接收puts()输出泄露的某个已执行过的函数的GOT地址，再以此来计算libc中地址与真实地址的偏移量；或者通过泄露的某个已执行过的函数的GOT地址，直接使用pwntools的libc.address=func_got-libc.symbols[‘func’]的形式直接获取libc的真实地址，从而直接通过system_addr=libc.symbols[‘system’]的方式直接获取该函数真实地址
• 程序再次执行时填充padding，在函数返回地址处覆盖为libc中system()函数的真实地址，其中参数为libc中”/bin/sh”字符串的真实地址。

​ 上面提到的泄漏方式，则是读取got表中的值。而反推libc版本的工作，已经有大佬通过编写LibcSearcher帮忙完成了。

​ 整个利用过程总体而言分为三步：

​ （1） 第一次ROP，打印出某个已知函数got表的值；

​ （2） 读取打印的这个值，并解析成地址，然后利用这个地址通过LibcSearcher去反推libc版本，进而利用已知偏移获取到libc基址；

​ （3） 解析ELF文件，获取目标函数（包括system）的偏移，加上基址就是目标函数实际地址，将获取到的地址填入溢出点完成exploit。

payload

​ 在第一次栈溢出puts()的plt地址覆盖函数返回地址时，puts()的返回地址可以设置为_start()或main()函数地址。

_start()和main()的区别

​ 简单地说，main()函数是用户代码的入口，是对用户而言的；而_start()函数是系统代码的入口，是程序真正的入口.我们可以看下本题的_start()函数内容，其包含main()和__libc_start_main()函数的调用，也就是说，它才是程序真正的入口：

返回地址为_start()函数

这里的示例只展示了两个可利用的函数puts()和__libc_start_main()。

泄露puts()函数地址

泄露__libc_start_main 地址

• 泄露 __libc_start_main 地址（这个地址就是libc文件的基址）
• 获取 libc 版本
• 获取 system 地址与 /bin/sh 的地址
• 再次执行源程序
• 触发栈溢出执行 system(‘/bin/sh’)

注意返回地址为start()

看了别人的博客发现，当将先将_start()换成main()，payload2的B字符的偏移量不变，运行脚本会报错，添加GDB调试交互发现溢出多了8个B

tips

为了更好理解，在网上找到了这个图，栈溢出利用的时候按照1234的顺序来写payload，先构造main()函数，造成溢出，然后构造puts()函数。

参考链接：栈溢出之ret系列、CTF-Wiki

哈希表-三数之和

题目链接

这道题采用双指针的方法，首先顺序依次是i，left，right。按照每个i下标处的值一次寻找排序后数组中满足条件的left和right下标位置的值（注意去重）。第一个i处理完成后，i递增，如果此时发现由重复的数也需要去重，这样可以寻找出所有满足条件的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > 0) return result;
            if(i > 0 && nums[i] == nums[i - 1])continue;
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
                else if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                    while(left < right && nums[left] == nums[left-1]) left++;
                } 
                else{
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    while(left < right && nums[right] == nums[right - 1]) right--;
                    while(left < right && nums[left] == nums[left+1]) left++;
                    right--;
                    left++;
                }
            }     
            
        }
        
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = list()
        nums.sort()
        for i in range(n):
            left = i + 1
            right = n - 1
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total > 0:
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]: right -= 1
                elif total < 0:
                    left += 1
                    while left < right and nums[left] == nums[left - 1]: left += 1
                else:
                    ans.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    left += 1
                    right -= 1 
        return ans

哈希表-赎金信

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for(int i = 0; i < magazine.length(); i++){
            record[magazine[i]-'a']++;
        }
        for(int j = 0; j < ransomNote.length(); j++){
            record[ransomNote[j]-'a']--;
            if(record[ransomNote[j]-'a'] < 0)
                return false;
        }
        return true;
    }
};

IRP介绍

​ IRP的全名是I/O Request Package，即输入输出请求包，它是Windows内核中的一种非常重要的数据结构。上层应用程序与底层驱动程序通信时，应用程序会发出I/O请求，操作系统将相应的I/O请求转换成相应的IRP，不同的IRP会根据类型被分派到不同的派遣函数中进行处理。

​ IRP有两个基本的属性，即MajorFunction和MinorFunction，分别记录IRP的主类型和子类型。操作系统根据MajorFunction决定将IRP分发到哪个派遣函数，然后派遣函数根据MinorFunction进行细分处理。没有设置派遣函数的IRP，默认与IopInvalidDeviceRequest函数关联。

​ 首先一个IRP在被分配时，调用者必须指定要分配多少个IO_STACK_LOCATION，这些结构直接在内存中伴随着IRP，其数量是设备堆栈中设备对象的数量。驱动程序会创建一个个设备对象，并将这些设备对象叠成一个垂直结构，叫做设备栈。IRP会被操作系统发送到设备栈顶层，如果顶层的设备对象的派遣函数结束了IRP的请求，那么这次I/O请求结束，如果没有，那么操作系统将IRP转发到设备栈的下一层设备处理，直到找到能够结束这个IRP请求的派遣函数的设备。

​ 因此，一个IRP请求可能被转发多次，为了记录IRP在每层设备中做的操作，IRP会有个IO_STACK_LOCATION数组（数组中的每个堆栈单元都对应一个将处理该IRP的驱动程序，另外还有一个堆栈单元供IRP的创建者使用。堆栈单元中包含该IRP的类型代码和参数信息以及完成函数的地址），数组的元素个数应该大于IRP穿过的设备数目， 当一个驱动程序接收到一个IRP时，将会获得一个指向IRP结构的指针，对于本层设备对应的IO_STACK_LOCATION,可以通过IoGetCurrentIrpStackLocation函数得到。

WDM与NT驱动程序

​ NT命名设备对象的名称形式为\Device\DeviceName, WDM驱动并不直接命名设备对象，系统规定了一个统一的命名方案，以确保设备名称不会在驱动程序之间发生冲突。WDM驱动程序命名方案：

• 设备的 PDO 被命名。总线驱动程序为其枚举的设备请求命名 PDO。总线驱动程序在创建设备对象时指定 FILE_AUTOGENERATED_DEVICE_NAME 设备特性。
• FDO 和FiDO 未命名。创建设备对象时，函数和过滤器驱动程序不请求名称。

共有三种 WDM 设备对象：

1. 物理设备对象 (PDO) – 表示总线上的设备到总线驱动程序，该设备对象表示在该总线上的该插槽中有某个设备。
2. 功能设备对象 (FDO) – 代表功能驱动程序的设备，通常由硬件的供应商提供。
3. 过滤设备对象（FiDO）——代表过滤器驱动程序的设备。

​ 驱动程序通过创建设备对象 (IoCreateDevice）并将其附加到设备堆栈 （IoAttachDeviceToDeviceStack ）将自己添加到处理设备 I/O 的驱动程序堆栈中。IoAttachDeviceToDeviceStack确定设备堆栈的当前顶部并将新设备对象附加到设备堆栈的顶部。

设备节点和设备堆栈

​ 大多数发送到设备驱动程序的请求都打包在IRP中。通常，当向设备发送 I/O 请求时，多个驱动程序会帮助处理该请求。这些驱动程序中的每一个都与一个设备对象相关联，并且这些设备对象被安排在一个堆栈中。设备对象及其相关驱动程序的序列称为设备堆栈。每个设备由一个设备节点表示，每个设备节点都有一个设备栈。

​ 即插即用管理器将一个设备节点与每个新创建的 PDO 相关联，并查看注册表以确定哪些驱动程序需要成为该节点的设备堆栈的一部分。设备堆栈必须有一个（并且只有一个）功能驱动程序，并且可以选择有一个或多个过滤器驱动程序。

​ 功能驱动程序是设备栈的主要驱动程序，负责处理读取、写入和设备控制请求。过滤器驱动程序在处理读取、写入和设备控制请求时起到辅助作用。在加载每个函数和过滤器驱动程序时，它会创建一个设备对象并将自己附加到设备堆栈。由功能驱动程序创建的设备对象称为功能设备对象（FDO），过滤驱动创建的设备对象称为过滤设备对象（Filter DO）。

​ PDO 始终是设备堆栈中的底部设备对象。这是由设备堆栈的构造方式造成的。首先创建 PDO，当附加设备对象附加到堆栈时，它们将附加到现有堆栈的顶部。

​ 在某些情况下，设备除了其内核模式设备堆栈外，还具有用户模式设备堆栈。用户模式驱动程序通常基于用户模式驱动程序框架 (UMDF)，它是Windows 驱动程序框架提供的驱动程序模型之一。在 UMDF 中，驱动程序是用户模式的 DLL，设备对象是实现 IWDFDevice 接口的 COM 对象。UMDF 设备堆栈中的设备对象称为WDF 设备对象(WDF DO)。

IO_STACK_LOCATION结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

typedef struct _IO_STACK_LOCATION {
    UCHAR  MajorFunction;
    UCHAR  MinorFunction;
    UCHAR  Flags;
    UCHAR  Control;
    union {
            struct {
                PIO_SECURITY_CONTEXT SecurityContext;
                ULONG Options;
                USHORT POINTER_ALIGNMENT FileAttributes;
                USHORT ShareAccess;
                ULONG POINTER_ALIGNMENT EaLength;
            } Create;
            struct {
                ULONG Length;
                ULONG POINTER_ALIGNMENT Key;
                LARGE_INTEGER ByteOffset;
            } Read;
            struct {
                ULONG Length;
                ULONG POINTER_ALIGNMENT Key;
                LARGE_INTEGER ByteOffset;
            } Write;
            ... ...
        } Parameters;
    PDEVICE_OBJECT  DeviceObject;
    PFILE_OBJECT  FileObject;
    PIO_COMPLETION_ROUTINE CompletionRoutine;
    PVOID Context;
} IO_STACK_LOCATION, *PIO_STACK_LOCATION;

kd> dt nt!_IO_STACK_LOCATION
   +0x000 MajorFunction    : UChar
   +0x001 MinorFunction    : UChar
   +0x002 Flags            : UChar
   +0x003 Control          : UChar
   +0x004 Parameters       : <unnamed-tag>
   +0x014 DeviceObject     : Ptr32 _DEVICE_OBJECT
   +0x018 FileObject       : Ptr32 _FILE_OBJECT
   +0x01c CompletionRoutine : Ptr32     long 
   +0x020 Context          : Ptr32 Void

这个结构的主要成员意义为：

• MajorFunction(UCHAR) ： 是该IRP的主功能码。这个代码应该为类似IRP_MJ_READ一样的值，并与驱动程序对象中MajorFunction表的某个派遣函数指针相对应。如果该代码存在于某个特殊驱动程序的I/O堆栈单元中，它有可能一开始是，例如IRP_MJ_READ，而后被驱动程序转换成其它代码，并沿着驱动程序堆栈发送到低层驱动程序。
• MinorFunction(UCHAR) ： 是该IRP的副功能码。它进一步指出该IRP属于哪个主功能类。例如，IRP_MJ_PNP请求就有约一打的副功能码，如IRP_MN_START_DEVICE、IRP_MN_REMOVE_DEVICE。
• Parameters(union) ： 是几个子结构的联合，每个请求类型都有自己专用的参数，而每个子结构就是一种参数。这些子结构包括**Create(IRP_MJ_CREATE请求)、Read(IRP_MJ_READ请求)、StartDevice(IRP_MJ_PNP的IRP_MN_START_DEVICE子类型)**，等等。
• DeviceObject(PDEVICE_OBJECT) ：是与该堆栈单元对应的设备对象的地址。该域由IoCallDriver函数负责填写。
• FileObject(PFILE_OBJECT) ： 是内核文件对象的地址，IRP的目标就是这个文件对象。驱动程序通常在处理清除请求(IRP_MJ_CLEANUP)时使用FileObject指针，以区分队列中与该文件对象无关的IRP。
• CompletionRoutine(PIO_COMPLETION_ROUTINE) ： 是一个I/O完成例程的地址，该地址是由与这个堆栈单元对应的驱动程序的更上一层驱动程序设置的。绝对不要直接设置这个域，应该调用IoSetCompletionRoutine函数，该函数知道如何参考下一层驱动程序的堆栈单元。设备堆栈的最低一级驱动程序并不需要完成例程，因为它们必须直接完成请求。然而，请求的发起者有时确实需要一个完成例程，但通常没有自己的堆栈单元。这就是为什么每一级驱动程序都使用下一级驱动程序的堆栈单元保存自己完成例程指针的原因。
• Context(PVOID) ： 是一个任意的与上下文相关的值，将作为参数传递给完成例程。

IRP操作流程

​ 通常大多数IRP是由I/O管理器创建的，该管理器初始化IRP结构和第一个I/O堆栈位置，然后它将IRP的指针传递到最上层。驱动程序在其适当的调度例程中接收到IRP。例如，如果这是一个ReadIRP，那么该驱动程序将从其驱动程序对象中调用其其主函数数组的IRP_MJ_READ索引。此时，驱动程序在处理IRP时可以有几个选项：

​ 1.将请求向下传递。如果这个驱动设备并不是设备节点的最后一个设备，当对该请求不感兴趣时，可以将其向下传递。这是由接收到不感兴趣的请求的过滤器驱动完成的，为了不损害设备的功能，驱动将该请求向下传递。需要调用IoCallDriver，IoCallDriver会调用IoGetNextIrpStackLocation下移设备栈的指针，因此我们需要对设备栈做如下之一的操作：

1
2
3
4
5
6
7
8
9
10
11
12

#define IoCopyCurrentIrpStackLocationToNext( Irp ) { \
    PIO_STACK_LOCATION irpSp; \
    PIO_STACK_LOCATION nextIrpSp; \
    irpSp = IoGetCurrentIrpStackLocation( (Irp) ); \
    nextIrpSp = IoGetNextIrpStackLocation( (Irp) ); \
    RtlCopyMemory( nextIrpSp, irpSp, FIELD_OFFSET(IO_STACK_LOCATION, CompletionRoutine)); \
    nextIrpSp->Control = 0; }

#define IoSkipCurrentIrpStackLocation( Irp ) \
    (Irp)->CurrentLocation++; \
    (Irp)->Tail.Overlay.CurrentStackLocation++;

​ IoCopyCurrentIrpStackLocationToNext 拷贝IO_STACK_LOCATION 成员到下一层。由于初始化的时候只初始化了第一个I/O堆栈位置，所以每个驱动需要初始化下一个驱动。

​ IoSkipCurrentIrpStackLocation 上移一层，下次使用的时候仍旧使用当前的IO_STACK_LOCATION。

​ 2.完全处理这个请求。接收到这个请求的设备可以调用IoCompleterequest处理这个请求，这样更低层的设备不会看到这个请求。

​ 3.结合1和2，驱动程序可以检查IRP，做一些事情（比如记录请求），然后传递它。或者它可以对下一个I/O堆栈位置进行一些更改，然后传递请求。

​ 4.传递请求并在请求完成时由底层设备通知。任何一层（除了最低的一层）都可以通过在传递请求之前调用IoSetCompletionRoutine来设置I/O完成例程。当其中一个较低的层完成请求时，将会调用驱动程序的完成例程。

​ 5.开始一些异步IRP处理。驱动程序可能想要处理该请求，但如果请求很长（典型的硬件驱动程序，但也可能是软件驱动程序），驱动可能通过调用IoMarkIrpPending标记IRP为挂起，并从它的调度例程返回一个STATUS_PENDING。最终，它将不得不完成IRP。

​ 一旦一些层调用IoCompleteRequest，该IRP就会向反方向回到IRP的发起者（通常是在管理器），如果完成例程已经注册，它们将按注册的相反顺序被调用，即从下到上。

IRP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

typedef struct _IRP {
	PMDL              MdlAddress;
	ULONG             Flags;
	union {
		struct _IRP*   MasterIrp;
		PVOID          SystemBuffer;
	} AssociatedIrp;
	IO_STATUS_BLOCK   IoStatus;
	KPROCESSOR_MODE   RequestorMode;
	BOOLEAN           PendingReturned;
	BOOLEAN           Cancel;
	KIRQL             CancelIrql;
	PDRIVER_CANCEL    CancelRoutine;
	PVOID             UserBuffer;
	union {
		struct {
			union {
				KDEVICE_QUEUE_ENTRY DeviceQueueEntry;
				struct {
					PVOID    DriverContext[4];
				};
			};
			PETHREAD     Thread;
			LIST_ENTRY   ListEntry;
		} Overlay;
	} Tail;
} IRP, *PIRP;

kd> dt nt!_IRP
   +0x000 Type             : Int2B
   +0x002 Size             : Uint2B
   +0x004 MdlAddress       : Ptr32 _MDL
   +0x008 Flags            : Uint4B
   +0x00c AssociatedIrp    : <unnamed-tag>
   +0x010 ThreadListEntry  : _LIST_ENTRY
   +0x018 IoStatus         : _IO_STATUS_BLOCK
   +0x020 RequestorMode    : Char
   +0x021 PendingReturned  : UChar
   +0x022 StackCount       : Char
   +0x023 CurrentLocation  : Char
   +0x024 Cancel           : UChar
   +0x025 CancelIrql       : UChar
   +0x026 ApcEnvironment   : Char
   +0x027 AllocationFlags  : UChar
   +0x028 UserIosb         : Ptr32 _IO_STATUS_BLOCK
   +0x02c UserEvent        : Ptr32 _KEVENT
   +0x030 Overlay          : <unnamed-tag>
   +0x038 CancelRoutine    : Ptr32     void 
   +0x03c UserBuffer       : Ptr32 Void
   +0x040 Tail             : <unnamed-tag>

• MdlAddress : 是一个MDL的指针，当内核层和用户层采用共享内存的结构传递数据的时候，这个MDL就代表共享的内存信息（共享物理内存，通过MDL映射）。这个成员生效的标记为：DO_DIRECT_IO, METHOD_IN_DIRECT 或者METHOD_OUT_DIRECT.
• AssociatedIrp : 这个成员是个联合体，其中存在一个SystemBuffer程序；当内核层使用用户层的数据的时候是通过拷贝数据的方式来实现的话，那么拷贝后的数据就放在了AssociatedIrp.SystemBuffer中了。这个成员生效的标记是DO_BUFFERED_IO或者METHOD_BUFFERED。
• IoStatus ： 返回的状态信息。
• RequestorMode : UserMode或KernelMode，指定原始I/O请求的来源。驱动程序有时需要查看这个值来决定是否要信任某些参数。
• **PendingReturned **: Pending 状态，如果为TRUE，则表明处理该IRP的最低级派遣函数返回了STATUS_PENDING。
• StackCount : 设备栈的数目。
• CurrentLocation : 当前处于哪个设备栈的索引。
• Cancel : IRP是否被取消，如果为TRUE，则表明IoCancelIrp已被调用(该函数用于取消这个请求)。如果为FALSE，则表明没有调用IoCancelIrp函数。
• **CancelIrql(KIRQL) **: 是一个IRQL值，表明那个专用的取消自旋锁是在这个IRQL上获取的.
• **CancelRoutine(PDRIVER_CANCEL) **: 是驱动程序取消例程的地址。你应该使用IoSetCancelRoutine函数设置这个域而不是直接修改该域(因为可以原子修改）。
• UserBuffer(PVOID) : 用户层参数的直接地址，设置标记METHOD_NEITHER时候有效。
• **Tail.Overlay **是Tail联合中的一种联合结构，如下：
  

访问用户缓冲区

驱动程序创建设备对象的时候，需要考虑该设备以何种方式读写。读写主要有缓冲区方式读写、直接方式读写、其他方式读写。一些派遣函数，比如IRP_MJ_READ，IRP_MJ_WRITE，IRP_MJ_DEVICE_CONTROL接受客户端提供的缓冲区——在大多数情况下来自用户模式。通常，派遣函数是在IRQL0和请求线程上下文中调用，这意味着用户模式提供的缓冲区指针非常容易访问：IRQL是0，所以页面错误通常会被处理，线程是请求者，因此指针在这个进程上下文中是有效的。

以WriteFile为例，WriteFile要求用户提供一段缓冲区，并且说明缓冲区大小，然后将这段内存数据传入到驱动程序中，这段缓冲区内存是用户模式的内存地址，驱动程序如果直接引用这段内存很危险。因为操作系统是多任务的，他可能随时切换到别的进程。

缓冲区方式读写

针对解决上述问题，缓冲区方式读写这种方法中，操作系统将应用程序提供的缓冲区的数据复制到内核模式下的地址中。IRP的派遣函数操作的是内核模式下的缓冲区而不是用户模式下的。这样的方法的缺点是，影响了运行效率，在少量内存操作时，可以采用这种方法。

1.I/O管理器会从非分页池中分配一个与用户模式下的缓冲区相同大小的缓冲区。并且Read/WriteFile创建的IRP的AssociatedIrp->SystemBuffer子域会记录这段内存地址。（可以通过IO_STACK_LOCATION中的Parameters.Read(or Write).Length知道请求了多少字节。）

2.I/O管理器会进行用户模式地址和内核模式地址的数据复制。

3.一旦驱动程序完成了IRP，I/O管理器（对于ReadFile请求）将系统缓冲区复制回用户的缓冲区(复制的大小由IoStatus.Information(记录了实际操作了多少字节)决定)

4.最后，I/O管理器释放内核缓冲区。

特点：使用简单，只需在设备对象中指定标志，其他所有事情都由I/O管理器处理。总是有一个副本，所以它最好用于小的缓冲区（通常最多一页）。大型缓冲区的复制成本可能会很高。在这种情况下，应该使用直接I/O来代替。

直接方式读写

与前一种方式不同，该方式读写设备时，操作系统会将用户模式下的缓冲区锁住。然后操作系统将这段缓冲区在内核模式地址再映射一遍。这样，用户模式和内核模式的缓冲区指向的是同一区域的物理内存。无论操作系统如何切换进程，内核模式地址都保持不变。

锁定后，操作系统用内存描述符表（MDL）记录这段内存,该数据结构描述了缓冲区是如何映射到RAM的，该数据结构存储在IRP的pIrp->MdlAddress。

从上图可知，这段虚拟内存首地址应该是mdl->StartVa+mdl->ByteOffset。

实现中主要用到MmGetSystemAddressForMdlSafe函数（该函数第二个参数是指定优先级），得到MDL在内核模式下的映射，返回值是内核地址。

如果返回NULL，这意味着系统超出系统页表或系统页表很低（取决于上面的优先级参数）。这种情况可能出现在内存很少的情况下，如果出现这种情况，那么IRP的完成状态应该是STATUS_INSUFFICIENT_RESOURCES。

其他方式读写

派遣函数直接读写应用程序提供的额缓冲区地址，只有把驱动程序和应用程序运行在相同线程上下文的情况下，才能使用这种方式。

缓冲区内存地址，可以在派遣函数中通过IRP的pIrp->UsersBuffer得到。因为ReadFile可能把空指针地址或者非法地址传递给驱动程序，所以驱动程序在使用用户模式地址前，需要探测这段内存是否可读或者可写（使用ProbeForWrite函数和try块）

IO设备控制操作

除了前面说的ReadFile，WriteFile之外，还可以通过另外一种方式操作设备。DeviceIoControl内部会使操作系统创建一个IRP_MJ_DEVICE_CONTROL类型的IRP，然后操作系统会将这个IRP转发到派遣函数。

DeviceIoControl与驱动交互

1
2
3
4
5
6
7
8
9

BOOL DeviceIoControl(
    HANDLE hDevice, // handle to device or file
    DWORD dwIoControlCode, // IOCTL code (控制码)
    PVOID lpInBuffer, // input buffer
    DWORD nInBufferSize, // size of input buffer
    PVOID lpOutBuffer, // output buffer
    DWORD nOutBufferSize, // size of output buffer
    PDWORD lpdwBytesReturned, // # of bytes actually returned
    LPOVERLAPPED lpOverlapped);

（IOCTL）控制码主要由四个参数构成，由CTL_CODE宏提供

1
2

#define CTL_CODE( DeviceType, Function, Method, Access ) ( \
((DeviceType) << 16) | ((Access) << 14) | ((Function) << 2) | (Method))

第三个参数比较关键，指的是操作模式（METHOD_BUFFERED、METHOD_IN_DIRECT、METHOD_OUT_DIRECT、METHOD_NEITHER）,这几种操作模式与前面提到的缓冲区、直接和其他访问方式类似，对于METHOD_IN/OUT_DIRECT的区别是，当以只读权限打开设备的时候，前者会成功，后者会失败。如果以读写权限打开设备，两者都成功。

参考链接：windows驱动之IRP结构、微软官方文档

哈希表-两数之和

题目链接

这道题用C++的unordered_map,首先不需要有顺序，以及键值不需要相同，从第一个元素开始不断比较以及往myMap里面插数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int,int> myMap;
        for(int i = 0; i < nums.size(); i++){
            auto pt = myMap.find(target - nums[i]);
            if(pt != myMap.end())
              return {pt->second, i};  
            myMap.insert(pair<int, int>(nums[i], i));
        }
    return {};
    }

};