Cache与内存的映射

1. 理解Cache Line

在大家印象中Cache Line就是一个数据块,能有什么理解难度呢?不妨再反问一下自己:真的是这样吗?

上篇文章中就说到Cache本身的容量远远小于内存容量,CPU为了能正确定位数据所在的CacheLine还需要做很多工作。简单来说可以将Cache Line理解成一个带标签的存储槽,下面以一个直观的例子来说明:

小A同学坐在座位上,如果老师想检查小A的作业的话就需要先定位到小A所在的座位号,然后再从小A的座位上拿到小A作业本。在这个例子中,小A的作业本就对应Cache Line中的数据,老师就是CPU Core,小A其实对应着内存地址(TAG),小A的座位就是Cache Line本身,而座位号就是Cache Line在Cache中的位置(索引,Index),教室里所有的座位就可以理解为整个Cache,而学校里所有的学生则是全部的系统内存。 Cache Flags

上图就是Cache的内部组织,除了TAG和数据外,还有两个标志位,V表示此CacheLine中的数据是否是有效的,即座位上有没有学生,D表示CacheLine中的数据有没有被修改过,修改过的数据是不能直接清除的,需要写回到主存(内存)。

2. Cache与内存的映射

映射方式有3种:

  1. 直接映射 (Direct Mapping)
  2. 组相联 (K-Way Set Associative Mapping)
  3. 全相联 (Full Associative Mapping)

2.1 全相联

继续以学生和座位为例,正常情况下我们并不限定位置,大家随便坐,先到先得。老师如果想检查一个同学的作业的话,也可以一个一个来找,即线性搜索,当然此举必然花费老师很多时间。另外一点需要强调,学生并不是老老实实坐在座位上的,不断会有学生进来或离开,也会有同学出去后又进来但前后的坐位并不相同的情况,这样的话“线性搜索”将不再可能。

想像最常见的一个场景,老师并不会主动来找,而是直接喊这个同学的学号(名字可能会有重名,但学号不会),所有的学生在听到名字后同时判断老师叫的是不是自己,只有被叫到的同学才会应答。在听到老师的请求后所有的学生同时并行判断的动作,对应于CPU及硬件实现就是一个并行的比较电路,而比较的内容则是座位上的同学和老师叫的学号,分别对应着TAG和内存地址。

这个例子中的随机编排座位的方式就是全相联映射。全相联映射方式的定位操作是最高效的,但是硬件成本亦最高,毕竟要实现复杂的并行比较电路,只有容量较小且对性能至关重要的缓存才会使用,如CPU的内存管理单元 (MMU, Mmemory Management Unit) 的TLB缓存 (Translation Lookaside Buffer),TLB中存放的是虚拟地址与物理地址的1:1的转换关系。

2.2 直接映射

假设上面例子中的教室只有20个座位,编号为0-19,全校共有400名学生,学号分别为0-399。直接映射方式的求是座位不能随便选择,而是通过学号和所有座位数的余数决定,即学号为0、20、40、60...的同学只能坐在0号座位上,同样学号为1、21、41、61...的同学只能争1号座位,后来的同学会将正坐在位置上的同学挤出去,如果1号和21号同学都要来教室的话就会发生两人不断被挤出去的情况,这就是Cache的颠簸效应(Cache Thrashing)。

2.3 组相联

为了解决直接映射的颠簸效应,遂引入了组相联映射。假设学校共有5个系,每个系均有80名学生,那我们可以这样安排座位,一系的学生只能选择0/5/10/15这4个座,二系则是1/6/11/16,依次类推,如下图所示:每个系有4个座位,这4个座位是没有顺序的,即本系的学生随意坐,但全系的80名学生将争抢这4个座位,这种分为5组的映射方式就是4路组相连映射,4路的意思是每组中有4个座位,即4个CacheLine。现实中CPU Cache无论是组数还是相联度(路)均是2的幂指数,不会出现本例中奇数5的情形。 Cache Groups 直接映射方式其实是组相联映射的一种特例,亦称作是单路组相联。

2.4 特别说明

更详细的阐述可参考链接1 [蜗窝科技: 浅谈Cache Memory],作者smcdef通过举例来说明三种方式的实现细节,作图精美,本文不再做过多说明。

3. Cache的分类及访问流程

目前主流的CPU,如Intel及AMD的桌面或服务器平台的CPU都是支持分页的,即物理内存的管理是以页划分和管理的。X86平台的页大小通常是4K,即4096字节。CPU层所操作的内存地址称作是虚拟地址(逻辑地址),并不是物理的内存地址,从虚拟地址至物理地址的翻译由硬件MMU来执行。Cache与MMU的位置关系直接决定了Cache的分类:如果Cache相对MMU离CORE的距离更近,则此类Cache被称作为逻辑Cache;相反则称作是物理Cache。下图是L1、L2及LLC与MMU的关系,L1是集成在CORE内部的,所以可以得出L1是逻辑Cache,而L2和LLC则是物理Cache。

Memory Paging & Addressing

如果再加上TAG的取值,取物理地址或虚拟地址,又可以组合成4种情况:

3.1. PIPT (Physically Indexed Virtually Tagged)

下图是2路组相联的PIPT的示例,CacheLine大小为64字节,即6个比特,组索引(SET)由S个比特来编址,剩余的部分即为标签项(TAG),CPU通过组索引来定位此地址所在Cache组,然后通过两组比较电路进行TAG值的并发比较,然后即可确定Cache所在位置,当然也有可能出现没有命中的情况。 Cache PIPT} L2及LLC,以及早期的CPU的L1均是使用PIPT的方式,这是因为内存的物理地址是唯一的,这就大大简单化PIPT的实现逻辑。

3.2. VIVT (Virtually Indexed Virtually Tagged)

VIVT的Index和Tag均使用虚拟地址,全程不需要MMU的参与,是性能最好的定位方式,但是由于虚拟地址的特性会导致歧义和别名的问题,最终决定了VIVT方式的不可行:

歧义 (Ambiguity,亦称Homonyms问题):不同的进程拥有相同的虚拟地址空间,虚拟化平台上不同的虚拟机亦是同样的情况。从而会导致相同的虚拟地址(不同进程或不同虚拟机)所对应的物理页面不同的,VIVT的方式将不能正确区分。

别名 (Alias):是指同一个物理页映射至不同的虚拟地址,即同一个物理地址将有多个虚拟地址的别名。多个别名的情况下VIVT将会映射至不同的CacheLine,将不能保证数据的一致性。

3.3. VIPT (Virtually Indexed Physically Tagged)

CPU层的指令所操作的均是虚拟地址,使用虚拟地址作为索引来直接进行Cache的定位不必经过MMU的转换。此时Cache Set的定位和MMU的转换过程是并发的,定位到指定Cache Set之后再进行两个Cache Line的Tag的对比,此时两个Tag的比对也是并行处理的。 Cache VIPT}

3.4. PIVT (Physically Indexed Virtually Tagged)

PIVT方式相比PIPT和VIPT来说没有任何优势,性能上必须等MMU转换完成之后,而且在数据一致性上无法处理好别名问题。

4. L1 Cache (VIPT)的别名问题

在Cache与内存的映射关系上,考虑到成本及性能,多采用组相联方式;在CacheLine的定位和访问方式上,L1 Cache多是VIPT,而L2及LLC是PIPT。以Intel Pentinum G5500T为例:L1是8路组相联,大小为32K; L2是4路组相联,大小为256K;LLC即L3则是16路组相联,大小为4M。

L1采用的是VIPT映射方式,虽然VIPT方式通过物理地址TAG解决了歧义的问题,但别名的问题依然存在,是怎样解决的呢?

实际上L1 Cache的每个Cache Set的数量正好限定在 (PAGE_SIZE/CACHE_LINE) 之内的,以G5500T为例,32K/(8*64) = 4K/64 = 64。虚拟地址最低6位为CacheLine中的偏移;位6-11共6位是组索引,6+6正好是12,即一个4K PAGE的大小,从而可推论出不管虚拟地址是多少,任意内存页面的固定偏移总是映射到相同的Cache Set中,而TAG的选择正是物理地址中的是12-47,可以理解为PFN,即每一个物理页面的唯一帧号,所以同一物理页的不同的虚拟地址最终将定位到同一个Cache Set中的同一个Cache Line上。

L1是8路组相联的,也就是说一个Cache Set中容纳了8个Cache Line,由上面的结论可得出:这8个Cache Line将分别来自于不同的物理页。最后大家不妨想一个问题,如果要将L1 Cache从32K增加到64K的话,怎样构造L1的相联度及Cache Set组数才是合理的?有多少种组合?

5. 参考连接

Cache为什么能提升性能

1. Cache的容量设计

上篇文章中介绍到CPU Cache是分级的,L1 Cache是集成在Core内部的,L2则是紧贴着Core,而L3是多个Core共享的。离Core(流水线)越近的分级速度越快,但容量也更小,并且造价愈贵。Cache的实现采用了高速的SRAM电路 (静态随机存取存储器: Static Random-Access Memory),SRAM相对DRAM (动态随机存取存储器: Dynamic Random Access Memory)要复杂和庞大的多,即使不考虑成本能做到无限增大,但因为电路复杂度的提升其性能即访问速度必然会下降,另外也会使得CPU的面积急速膨胀。最终,CPU的每一级Cache的容量都是在设计之初考虑各方面因素折中后的结果(trade-off)。下图是AMD Zen的CCX的die shot[来源:1. Zen - Microarchitectures - AMD],从图中我们就能看中L2及L3 Cache占据了很大一部分的面积: AMD ZEN die shot

一般而言L1 Cache约几十K,L2则是几百K,L3是几M或几十、几百M,但相比较内存动不动几十G的大小来说还是小了太多,根本不在一个数量级上。那么问题来了:Cache容量比内存小了太多,为什么根本不在一个数据量级的Cache能够大副度提升系统性能?

2. 局部性原理 (Principle of Locality)

简言之,程序倾向于访问(或执行)刚刚访问过的数据(执行过的指令)或与之相临近的数据(指令)

2.1 时间局部性 (Temporal locality):

刚刚被访问的地址(数据)在未来有很大的可能性被再次访问,即用过的数据可能会再次被用到

2.2 空间局部性 (Spatial locality):

刚刚被访问的地址的临近位置在未来有很大的可能被访问,以数组D[]为例,当前访问的是D[i],那么D[i+1]有很大的可能将被访问

2.3 算法局部性:

程序代码也遵守2/8法则,即帕累托法则(Pareto principle,亦称关键少数法则),80%的时间都是在执行20%的代码

正是因为局部性原理,少量的Cache大大减少了数据的访问延迟,从而提升了整体性能。

3. Cache的放大效应

先来考虑一个问题:Cache命中率(Cache Hit) 99%与98%的差别会有多大?从数值上来看二者本身仅相差1%,性能上最终能有多大差别呢?

假设命中L1的延时为4 cycles,不命中的话需要从内存中读取数据的延时为150 cycles,那么: 99%命中率的情况: 0.99 4 + 0.01 150 = 5.46 98%命中率的情况: 0.98 4 + 0.02 150 = 6.92

后者比前者的延时多了(6.92 - 5.46) / 5.46 = 26.7% 之多。换成95%的命中率的话,延时将高达99%命中率时的一倍之多。由此看来,不命中(Cache Miss)所带的性能惩罚巨大,这也预示了未来Cache发展的趋势,即容量将越来越大,拥有GB级Cache容量的CPU将指日可待,另外增加L4分级也将是不可避免的,有兴趣的读者可进一步参阅 [2. The Next Platform: Cache Is King]。

4. Cache Miss的原因

前面说了Cache Miss的惩罚,下面说一下会导致Cache Miss的因素,可以简单归纳为3C:

  1. Cold (Compulsory) Miss: 第一次访问数据时,数据根本不在Cache中
  2. Conflict Miss: 因冲突导致Cache Line被驱逐出Cache,上一篇文章中提到了相关的方法,如Evict(驱逐)、Prime(装填)等,当然冲突所导致的Cache Miss只针对组相联的Cache结构(直接映射可以认为是单路组相联),而全相联的Cache结构是没有Conflict Miss的,后续还会针对此课题做详细的介绍
  3. Capacity Miss: Cache的容量毕竟有限,如果程序确实需要密集访问大量内存时,Cache必然是不够的

在指定的CPU硬件上如果想提升Cache Hit的话就要从这几个因素上着手,如通过硬件预取以减少Cold Miss,通过程序算法改进及结构重组可减少2和3所带来的Cache Miss的发生概率,本文先点到为止,后面将进行详细拆解。

5. 参考资料

  1. wikichip: Zen - Microarchitectures - AMD
  2. The Next Platform: Cache Is King

CPU Cache测量方法

通过上一篇文章《通过TSC观察CPU》知道了可以通过TSC来测量CPU的内部行为,本文将介绍CPU Cache的结构及几种常用的测量手法:

Cache的分级结构

Memory & Cache的分级结构

  • Cache 是分级的:一般分为3级,较老的CPU如Core 2 Duo只有2级。L1是集成是core内部的,指令与数据Cache是分离的,好L1C和L1D;L2是紧贴core的;L3是多核共享的,每个core有自己的Slice,通过Ring Bus或Mesh结构互联互访
  • Cache以Cache Line为访问单位,即Cache及内存的访问是以块为单位的,而不是字节单位。较新的X86 CPU的Cache Line一般是64字节。上一篇文章通过TSC观察CPU曾注意到一个有趣的测量结果:X86程序访问一个1字节与访问2个、4个及8个字节的延进均为31个指令周期,并不是线性增长的,就是这个原因
  • 层级包含与否由CPU实现决定:L2一般都是包含L1的全部内容的,L3可以是Non-inclusive,也可以是Exclusive。Intel的CPU一般是包含的,但AMD的Zen系列CPU的L3就是定义为L1/L2的Victim Cache,Victim是指从L1及L2中移除的Cache项
  • Cache自身的构造采用“组相联”方式

Cache不同分级的性能

Memory & Cache性能数据

在上图中看到Cache是分级的,用不同级的访问速度有很大不同,故我们可以通过制造冲突或直接Flush Cache的方式将数据从Cache中清除,从而通过前后内存访问的时间差来进行判定。

测量方法

制造冲突以清除Cache的常用手段有以下几种【参阅 1:Cache side channel attacks: CPU Design as a security problem by Anders Fog]】:

  1. Evict (驱逐) + Time (测量) : 通过制造冲突以达成被测量目标数据从cache中清除的目的
  2. Prime (装填) + Probe (探测) :与1)方法一样,只是作用对象是反的
  3. Flush (冲刷) + Reload (加载) ) :最主动和最快的办法,直接利用clflush指令刷新,然后再读取内存,此时会发生Cache Miss事件。
  4. Flush (冲刷) + Flush (冲刷) ) :与3)类似,但测量的是clflush指令针对数据在不在cache中的执行周期的不同 在条件许可的情况下,尽量采用第3种,即最快的办法。

实例:Flush + Reload

Flush即clflush指令,Visual C++中定义如下:

        extern void _mm_clflush(void const*_P);

测量代码:

        /* flush */
        _mm_clflush(&data[0]);

        /* measure cache miss latency */
        ts = rdtscp(&ui);
        m |= data[0];
        te = rdtscp(&ui);

实战:Cache Line的测量

原理: Cache性能测量方法

结论: Cache性能结果

从图中我们可以看到64字节是一个明显的分界点。

硬件预取: Hardware Prefetcher

如果你在自己的电脑上进行测试,你看到的可能不是上图所示的样子,很大的可能如下图所示,明显的分界点不是64字节而是128字节: Cache性能结果

这是因为硬件预取即HWPrefetcher的缘故,并且硬件预取默都是开启的。硬件预取功能会在每次Cache Miss的情况下多读一个Cache Line,可以理解为每次读取两个Cache Line即64 * 2 = 128字节,但数据并不是同时到达的,第二个Cache Line的数据的到达周期会晚些,这也是为什么在128这个点上的延时会比64高。 CPU Cache Prefetcher

如何关闭硬件预取:

  1. 通过BIOS设置: 通过BIOS选项来关闭hwprefetcher,对所有的CPU生效
  2. 通过内核调试器windbg直接关闭:通过直接改写msr寄存器关闭当前核的硬件预取功能:
    0: kd> rdmsr 0x1a4
    msr[1a4] = 00000000`00000000
    0: kd> wrmsr 0x1a4 0x0f
    0: kd> ~1
    1: kd> rdmsr 0x1a4
    msr[1a4] = 00000000`00000000
    1: kd> wrmsr 0x1a4 0x0f
    1: kd> rdmsr 0x1a4
    msr[1a4] = 00000000`0000000f
    1: kd> ~0

实战:Cache不同分级的访问延时测量

如果我们以更大的的stride进行同样的测试则可以测量出Cache每一级的大小,即L1D,L2,LLC和内存访问的延时。下图中我们分别以1K、2K,直至64M的stride测量出来结果: Cache性能结果 可以看到整个曲线有4个平台,分别表示L1D、L2、LLC和内存。L1D的大小为32K,L2为256K,这部分和CPUZ的输出是一致的。 但第三个平台包含了512K、1M及2M,从4M开始延进有明显的跃升,从8M之后基本稳定在高位。这里就涉及到了LLC组织的不同:L1D及L2 Cache都是与物理核(Core)绑定的,而LLC是绑定CPU的,即2核的CPU的两个核心会共享同一个LLC,整个LLC是平均分配给每个核的,然后每个核心的LLC通过Ring Bus互联,即每个核又可以访问所有的LLC。这里在4M的stride发生波动的原因有两个:

  1. 当前运行测量程序的CPU核心用尽自己的LLC后会通过Ring Bus竞争访问另一个核心的LLC
  2. 测量程序运行时整个操作系统也在运行,所以整个系统均会竞争使用LLC,必然会带来挤出效应,从而增大了延时

参考资料

  1. CSCA: Cache side channel attacks: CPU Design as a security problem by Anders Fogh
  2. HWPF: Disclosure of Hardware Prefetcher Control on Some Intel® Processors
  3. SourceCode: CacheLatency Github Repo

通过TSC观察CPU

自Pentium开始x86 CPU均引入TSC了,可提供指令级执行时间度量的64位时间戳计数寄存器,随着CPU时钟自动增加。

CPU指令:

rdtsc: Real Time-Stamp Counter rdtscp: Real Time-Stamp Counter and Processor ID

调用:

Microsoft Visual C++:

unsigned __int64 __rdtsc();
unsigned __int64 __rdtscp( unsigned int * AUX );

Linux & gcc :

extern __inline unsigned long long
__attribute__((__gnu_inline__, __always_inline__, __artificial__))
__rdtsc (void) {
  return __builtin_ia32_rdtsc ();
}
extern __inline unsigned long long
__attribute__((__gnu_inline__, __always_inline__, __artificial__))
__rdtscp (unsigned int *__A)
{
  return __builtin_ia32_rdtscp (__A);
}

示例:

1: L1 cache及内存的延迟测量:

代码:

{
    ......
    /* flush cache line */
    _mm_clflush(&data[0]);

    /* measure cache miss latency */
    ts = rdtscp(&ui);
    m |= data[0];
    te = rdtscp(&ui);
    CALC_MIN(csci[0], ts, te);

    /* measure cache hit latency */
    ts = rdtscp(&ui);
    m &= data[0];
    te = rdtscp(&ui);
      /* flush cache line */
    _mm_clflush(&data[0]);

    /* measure cache miss latency */
    ts = rdtscp(&ui);
    m |= data[0];
    te = rdtscp(&ui);
    CALC_MIN(csci[0], ts, te);

    /* measure cache hit latency */
    ts = rdtscp(&ui);
    m &= data[0];
    te = rdtscp(&ui);
    CALC_MIN(csci[1], ts, te);
    CALC_MIN(csci[1], ts, te);
}

结果:

rdtscp指令自身耗时:X86: 31 X64: 33

架构 X86 X64
长度 BYTE WORD DWORD QWORD BYTE WORD DWORD QWORD
冷:内存 244 241 246 250 254 254 260 261
热:L1 31 31 31 31 35 35 35 35

问题:读取1个字节与8个字节的所用的时间是一样的,为什么?

2: 常见整型运算及多条指令执行周期:

代码:

{
    ......
    /* measure mul latency */
    ts = rdtscp(&ui);
    m *= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci[2], ts, te);

    /* measure div latnecy */
    ts = rdtscp(&ui);
    m /= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci[3], ts, te);

    /* measure 2*mul latnecy */
    ts = rdtscp(&ui);
    m *= *((U32 *)&data[0]);
    m *= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci2[0], ts, te);

    /* double div */
    ts = rdtscp(&ui);
    m /= *((U32 *)&data[0]);
    m /= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci2[1], ts, te);

    /* mul + div */
    ts = rdtscp(&ui);
    m *= *((U32 *)&data[0]);
    m /= *((U32 *)&data[0]);
    te = rdtscp(&ui);
    CALC_MIN(csci2[2], ts, te);

    /* measure float mul latency */
    ts = rdtscp(&ui);
    f = f * m;
    te = rdtscp(&ui);
    CALC_MIN(csci[4], ts, te);

    /* measure float div latency */
    while (!m)
        m = rand();
    ts = rdtscp(&ui);
    f = f / m;
    te = rdtscp(&ui);
    CALC_MIN(csci[5], ts, te);
}

结果:

指令周期
数据类型 整型 浮点数
指令组合 m* m/ m, m m, n m/, m/ m/, n/ m*, m/ f* f/
指行时间 2 20 4 4 48 26 24 17 26

问题:m及n的除法运算的耗时只比m的除法多了一点,但却明显少于m的两次除法,为什么?

注意事项:

  1. 考虑到CPU乱序执行的问题,rdtsc需要配合cpuid或lfence指令,以保证计这一刻流水线已排空,即rdtsc要测量的指令已执行完。后来的CPU提供了rdtscp指令,相当于cpuid + rdtsc,但cpuid指令本身的执行周期有波动,而rdtscp指令的执行更稳定。不过rdtscp不是所有的CPU都支持,使用前要通过cpuid指令查询是不是支持: 即CPUID.80000001H:EDX.RDTSCP[bit 27]是不是为1
  2. 多核系统:新的CPU支持了Invariant TSC特性,可以保证在默认情况下各核心看到的TSC是一致的,否则测量代码执行时不能调度至其它核心上。另外TSC是可以通过MSR来修改的,这种情况下也要注意: Invariant TSC: Software can modify the value of the time-stamp counter (TSC) of a logical processor by using the WRMSR instruction to write to the IA32_TIME_STAMP_COUNTER MSR
  3. CPU降频问题:第一代TSC的实现是Varient TSC,没有考虑到降频的问题,故在低功耗TSC计数会变慢,甚至停止;后来又有了Constant TSC,解决了降频的问题,但在DEEP-C状态下依然会发生停止计数的情况,所以又有了最新的Invariant TSC的特性: The time stamp counter in newer processors may support an enhancement, referred to as invariant TSC. Processor’s support for invariant TSC is indicated by CPUID.80000007H:EDX[8]. The invariant TSC will run at a constant rate in all ACPI P-, C-. and T-states. This is the architectural behavior moving forward. On processors with invariant TSC support, the OS may use the TSC for wall clock timer services (instead of ACPI or HPET timers). TSC reads are much more efficient and do not incur the overhead associated with a ring transition or access to a platform resource.
  4. 指令本身的时间开销 Pentinum Gold G5500T: 31 cycles Core i7-7820HQ: 25 cycles
  5. 权限问题(此指令可用于时序攻击,如Meltdown及Spectre): CR4.TSD: Time Stamp Disable (bit 2 of CR4) — Restricts the execution of the RDTSC instruction to procedures running at privilege level 0 when set; allows RDTSC instruction to be executed at any privilege level when clear. This bit also applies to the RDTSCP instruction if supported (if CPUID.80000001H:EDX[27] = 1).
  6. 计数器溢出可能:计算器本身是64位的,即使是主频4G的CPU,也要100多年才会溢出,对于我们的测量来说可以不用考虑
  7. 时序测量容易被干扰(线程调度、抢占、系统中断、虚拟化等),要求测量的指令序列尽量短,并且需要进行多次测量

Linux内核监控

本文将简单罗列Linux监控的实现方式,安全及审计软件的前提就是能在关键点上接管系统的执行流程,而关键点的接管必须依赖Linux内核的监控能力:

1 LSM HOOK

Linux内核中为发实现其安全机制,已经预留了LSM HOOK埋点,以4.4.131的内核为例,系统共提供了多达198个监控点回调,4.4.131是当前麒麟操作操作系统的内核版本,而较新的5.4.2内核已经支持多达216监控回调:

类别 钩子函数个数 功能
ptrace 2 Ptrace操作的权限检查
能力机制 3 Capabilities相关操作的权限检查
磁盘配额 2 配盘配额管理操作的权限检查
超级块 13 mount/umount/文件系统/超级块相关操作的权限检查
dentry 2 dentry相关操作的权限检查
文件路径 11 文件名/路径相关操作的权限检查
inode 27 inode相关操作的权限检查
file 13 file相关操作的权限检查
程序加载 5 运行程序时的权限检查
进程 27 进程/进程相关操作的权限检查
IPC 21 IPC消息/共享内存/信号量等操作的权限检查
proc文件系统 2 proc文件系统相关操作的权限检查
系统设置 2 日志,时间等相关操作的权限检查
内存管理 1 内存管理相关操作的权限检查
安全属性 7 对安全相关数据结构的操作的权限检查
网络 37 网络相关操作的权限检查
XFRM 11 XFRM架构想要关操作的权限检查
密钥 4 密钥管理相关操作的权限检查
审计 4 内核审计相关操作的权限检查
Android Binder 4 Android Binder架构有关操作的权限检查
总计 198

其中我们最关心的是进程、程序加载、内存及文件相关的监控回调,从数量及功能上已足够强大,但具体能否满足我们的需求,还要在实现过程中进行分析和验证。比如以进程创建为例,Linux内核的进程创建是通过sys_clone(sys_fork/sys_vfork)及sys_execve实现的,但LSM的监控点为了避免多入口的问题,放在了task_alloc这个点上:调用栈如下所示:

backtrace
#0  security_task_alloc (task=0xffff923cad2f8000, clone_flags=4001536) at security/security.c:1472
#1  0xffffffffa0a88ff4 in copy_process (clone_flags=4001536, stack_start=<optimized out>, stack_size=<optimized out>, child_tidptr=<optimized out>, pid=0x0, trace=<optimized out>, tls=<optimized out>, node=-1) at kernel/fork.c:1746
#2  0xffffffffa0a8a59f in copy_process (node=<optimized out>, tls=<optimized out>, trace=<optimized out>, pid=<optimized out>, child_tidptr=<optimized out>, stack_size=<optimized out>, stack_start=<optimized out>, clone_flags=<optimized out>) at kernel/fork.c:1574
#3  _do_fork (clone_flags=4001536, stack_start=<optimized out>, stack_size=<optimized out>, parent_tidptr=<optimized out>, child_tidptr=<optimized out>, tls=<optimized out>) at kernel/fork.c:2056
#4  0xffffffffa0a8a969 in SYSC_clone (tls=<optimized out>, child_tidptr=<optimized out>, parent_tidptr=<optimized out>, newsp=<optimized out>, clone_flags=<optimized out>) at kernel/fork.c:2166
#5  SyS_clone (clone_flags=<optimized out>, newsp=<optimized out>, parent_tidptr=<optimized out>, child_tidptr=<optimized out>, tls=<optimized out>) at kernel/fork.c:2160
#6  0xffffffffa0a03ae3 in do_syscall_64 (regs=0xffff923cad2f8000) at arch/x86/entry/common.c:287
#7  0xffffffffa1400081 in entry_SYSCALL_64 () at arch/x86/entry/entry_64.S:237
#8  0x00007ffc00600600 in ?? ()
#9  0x000056066c0ceec0 in ?? ()
#10 0x0000000000000000 in ?? ()

在进程创建这个点上我们需要取到哪些信息:主进程、子进程、调用栈及相应的符号信息等等,但security_task_alloc这个点不能满足我们的需求,但再利用程序加载(BPRM)的相关回调我们即可将所有的信息串联起来,有了这个信息我们就能够做进详细的检测与判定,以上就是我们解决问题的主要思路。

2 Syscall_Table HOOK

这种方式就类似于 SSDT HOOK,但Linux内核并没有类似于Windows内核的PatchGuard (KPP)的防护机制,目前天擎国产化就是使用的此技术,但在PKS系统上,可信计算以及澜起安全内存对syscall table以及内核镜像都是有安全度量以及内存防改保护。另外为了解决Meltdown,Linux内核引入的KPTI以及ARM64系统上引入的Syscall Table Wrapper (4.19之后)都给Syscall Table HOOK带来挑战

需要注意的事,Linux内核中会存存多个syscall table,比如X64为了支持32位的x86程序会保留32位移程序的syscall table,另外Linux还有一项特殊的syscall tabke专为X64_32程序使用,X64_32类别程序内部直接使用的是64位的syscall id

3 代码Inline HOOK

代码Inline hook做为针对Syscall Table hook的延伸,但同样亦面临可信度量及内存保护的挑战

4 ftrace & kprobe机制

Linux内核为了提升在线解决问题的效率,实现了动态插桩机制,可以在内核”任意函数“点进行插桩,用以输出参数及函数变量,甚至改变函数执行流程。当然这种技术主要是用于排错应急,如果用于生产环境还需要更多的技术验证。这种技术的明显限制是针对同一个函数只能进行一个插桩,并且插桩行为是能够被可信计算发现的,亦可被阻止。

5 中断向量HOOK

X86体系下应用层通过syscall或sysenter切换至内核模式,ARM体系下通过SVC或SWI可以切换至内核,切换模式的指令最终是通过自陷阱(Trap)触使CPU进行模式切换,并自动执行事先指定位置处的代码。我们可以通过接管中断向量的方式实现Syscall的HOOK,但是此方式会有以下难点:

  1. 入口片要处理相当多的初始化工作,只能用汇编级指令实现
  2. 针对开启KPTI的内核,要保证入口代码在Shadow内核空间

6 GhostHOOK

依赖于硬件PMU的HOOK实现方式,Intel及AMD在各自的CPU上均实现了类似的机制,ARM架构上的CP15协处理器亦实现了类似的功能,但相对Intel的PMU在功能上要弱一些,但均可以达成类似的HOOK效果。

当然通过高精度时间中断亦可达成同样效果

7 内核hot patch

ARM64平台可利用 aarch64_insn_patch_text 进行函数层的hook。

Windows系统通用回调

Windows系统通用回调 本文将针对Windows操作系统所提供系统回调操作做逐一分析,以了解每个回调所能达成什么样的功能及效果。比如部分回调只是用于通知,我们只能通过此回调来了解某一类型事件的发生,只能做审计,拦截动作需要通过其它途径实现;也有回调可以实现即时拦截,通过回调即可阻止恶意程序的攻击企图。 Windows系统在内核及应用层均有提供回调机制,下面分为两部分作介绍:

1 内核回调

内核回调机制 OS版本 功能描述 备注
PsSetCreateProcessNotifyRoutine WIN2K 只是进程创建及退出通知
PsSetCreateProcessNotifyRoutineEx VISTA SP1/SRV2008 可通过返回值阻止进程创建
PsSetCreateProcessNotifyRoutineEx2 WIN10 1703 可接收到WSL/PICO进程创建及退出通知;可阻止进程创建
PsSetCreateThreadNotifyRoutine (PsRemoveCreateThreadNotifyRoutine) WIN2K 线程创建及退出通知 创建时的context为创建者,可用以判断是不是远程线程
PsSetCreateThreadNotifyRoutineEx (PsRemoveCreateThreadNotifyRoutine) WIN10 线程创建及退出通知 创建时的context为新线程环境
PsSetLoadImageNotifyRoutine (PsRemoveLoadImageNotifyRoutine) WIN2K 模块加载通知:支持驱动及应用层DLL加载通知 无模块卸载通知
PsSetLoadImageNotifyRoutineEx (PsRemoveLoadImageNotifyRoutine) WIN10 1709 模块加载通知:支持驱动及应用层DLL加载通知 无模块卸载通知
IoRegisterBootDriverCallback (IoUnRegisterBootDriverCallback) WIN8 Boot-Start驱动加载通知,可拦截,但拦截的后果即BSOD 加载顺序问题;ELAM驱动最早加载,需要特殊签名
SeRegisterImageVerificationCallback (SeUnregisterImageVerificationCallback) WIN8.1 ? 驱动加载回调,可以验证驱动签名信息 函数未公开,目前Windows Defender会使用
ObRegisterCallbacks (ObUnRegisterCallbacks) VISTA SP1 SRV2008 针对进程及线程对象句柄的创建提供前置及后置回调,可修改句柄权限,如针对进程对象无VM映射权限。子进程继承句柄不会通知 WIN7系统可监控文件句柄的创建,需要修改未公开的系统结构(ObjectType->SupportsObjectCallbacks),WIN8后PG会监控。WIN10系统增加了桌面对象的监控支持
CmRegisterCallback (CmUnRegisterCallback) XP 注册表操作回调,可修改、转向或拦截原访问请求 XP/SRV2003/VISTA行为有差异
CmRegisterCallbackEx (CmUnRegisterCallback) VISTA 注册表操作回调,可修改、转向或拦截原访问请求
ExRegisterCallback
-- \Callback\SetSystemTime WIN2K 系统时钟修改回调
-- \Callback\PowerState WIN2K 电源状态改变回调(AC/DC,电源策略,待机或关机) 早于Power Manager的IRP_SET_POWER请求
-- \Callback\ProcessorAdd VISTA 动态增加新CPU事件通知
KeRegisterBoundCallback (KeDeregisterBoundCallback) WIN10 用以捕获应用层边界检测异常,可用于应用层HOOK
Standard Event Objects for VM : 所有 主要用于监控内存状态
-- \KernelObjects\HighMemoryCondition
-- \KernelObjects\LowMemoryCondition
-- \KernelObjects\HighPagedPoolCondition
-- \KernelObjects\LowPagedPoolCondition
-- \KernelObjects\HighNonPagedPoolCondition
-- \KernelObjects\LowNonPagedPoolCondition
-- \KernelObjects\LowCommitCondition
-- \KernelObjects\HighCommitCondition
-- \KernelObjects\MaximumCommitCondition
KeRegisterBugCheckCallback (KeDeregisterBugCheckCallback) WIN2K 系统出错准备蓝屏时的回调通知
KeRegisterBugCheckReasonCallback (KeDeregisterBugCheckReasonCallback) XP SP1 SRV2003 蓝屏后DUMP生成通知,可写入额外1-PAGE信息
FsRtlRegisterFileSystemFilterCallbacks XP 文件系统或过滤驱动回调,一般由I/o Manager,VM及CM发起
IoRegisterFsRegistrationChange (IoUnregisterFsRegistrationChange) 所有 文件系统注册事件通知回调 WIN2K: 已注册文件系统驱动不再通知;XP: 均会通知
IoRegisterFsRegistrationChangeEx (IoUnregisterFsRegistrationChange) WIN2K SP4 文件系统注册事件通知回调,忽略RAW设备 同IoRegisterFsRegistrationChange
IoRegisterFsRegistrationChangeMountAware (IoUnregisterFsRegistrationChange) WIN7 文件系统注册事件通知回调,忽略RAW设备 会额外处理与挂载/Mount的竞争问题
TmEnableCallbacks VISTA 文件事务操作回调
IoRegisterContainerNotification (IoUnregisterContainerNotification) WIN7 会话/Session改变通知,如新用户登录或登出,功能类似于用户层的WTSRegisterSessionNotification
KeRegisterProcessorChangeCallback (KeDeregisterProcessorChangeCallback) WIN2K 动态CPU添加事件回调 有Pre和Post处理
KeRegisterNmiCallback (KeDeregisterNmiCallback) SRV2003 发生不可屏蔽中断时的回调通知
IoRegisterShutdownNotification (IoUnregisterShutdownNotification) WIN2K IRP_MJ_SHUTDOWN请求回调
IoRegisterLastChanceShutdownNotification (IoUnregisterShutdownNotification) WIN2K IRP_MJ_SHUTDOWN请求回调 调用时机晚,在文件系统处理完毕之后
PoRegisterPowerSettingCallback (PoUnregisterPowerSettingCallback) VISTA 电源管理事件响应回调
IoRegisterPlugPlayNotification (IoUnregisterPlugPlayNotification[Ex]) WIN2K PNP事件回调(设备热插拔)
IoWMISetNotificationCallback XP WMI事件回调
DbgSetDebugPrintCallback 未公开 VISTA 捕获内核打印事件(DbgPrint)
IoRegisterPriorityCallback (IoUnregisterPriorityCallback) 未公开 WIN7 SP1 ? I/O 请求优先级调整
PoRegisterCoalescingCallback (PoUnregisterCoalescingCallback) 未公开 WIN8.1 CM和文件系统相关:在系统空闲的时候实施cache的聚合刷新
PsSetLegoNotifyRoutine 未公开 XP 类似TLS,可以实现线程终结时的回调通知

2 应用层回调

应用层回调 OS 功能 备注
LdrRegisterDllNotification (LdrUnregisterDllNotification) VISTA 可接收进程内DLL模块加载及卸载事件,不可拦截
ProcessInstrumentationCallback WIN7 可在程序每次Ring 0至3切换后收到通知,在系统服务调用结束时刻 需要进程注入后主动调用NtSetInformationProcess,需要SeDebugPrivilege等
RegisterServiceCtrlHandler(Ex) XP 在应用层服务中接收系统事件:设备热插拔、用户登录、电源管理等
RegisterDeviceNotification 所有 GUI程序获取硬件改变通知
RegNotifyChangeKeyValue WIN2K 监控注册表指定键的子键及值的改变
ReadDirectoryChange 所有 监控指定目录中的文件及子目录的变化
AddSecureMemoryCacheCallback (RemoveSecureMemoryCacheCallback) VISTA SP1 可监控Secure类型的共享内存的释放
LdrSetDllManifestProber 未公开 XP 可收到DLL模块加载事件,可用于拦截
LdrInitShimEngineDynamic 未公开 WIN7 可接收Shim Engine通知,可接管DLL加载等 调用时机有要求,需要R3 HOOK; 不同Windows版本如WIN7及8.1差别较大
RtlSetThreadPoolStartFunc 未公开 WIN2K 设置线程初始化及退出函数,kernel32内部使用

3 通用回调的限制

Windows系统虽然提供了回调接口,但因为性能等各种因素的原因还会限定回调的数量:

  • CmRegisterCallback限制为最多100个,无高度号设置,后注册的回调可能收不到请求
  • PsSetLoadImageNotifyRoutine限制为最多8个,64位系统共64个
  • PsSetCreateProcessNotifyRoutine限制为最多8个
  • PsSetCreateThreadNotifyRoutine限制为最多8个 不少驱动安装为了防止注册失败的情况选择了尽早启动并完成相关回调的注册,也有一些工具如PcHunter会通过DKOM方式进行动态扩展。 另外不同的OS版本的支持限制,在上表中也有说明,如Vista之后的Windows系统才开始支持注册表事务操作,这部分在使用中也要注意,Ob Callback也有类似的问题。

4 参考链接

  1. Magnesium Object Manager Sandbox, A More Effective Sandbox Method for Windows 7
  2. MSDN: Filtering Registry Calls
  3. Filter Manager Support for Minifilter Drivers
  4. MSDN: REG_NOTIFY_CLASS enumeration
  5. CodeMachine: Kernel Callback Functions
  6. OSR: Kernel Mode Extensions Driver
  7. WDK Samples: Registry Logging
  8. https://blog.csdn.net/whatday/article/details/52623878
  9. https://docs.microsoft.com/en-us/windows-hardware/drivers/kernel/handling-notifications