标记类型

  • 斜体：看看就行
  • 正常：正常掌握
  • 粗体/emoji❗：重点掌握

此处仅罗列大纲，因为往年学长总结很好，这里就不重新总结了，仅个人复习使用大纲

第一章

信息安全技术架构❗

注意有一个图，四层，信息安全金三角：CIA架构

信息安全四要素：CACA

信息安全层次划分❗❗❗

  • 内容安全
  • 数据安全
  • 运行安全
  • 物理安全

存在一个三级框架，每个夹在两层中间

  • 信息对抗
  • 信息安全
  • 系统安全

信息安全的诱因与威胁❗❗

根本原因：冯诺伊曼结构
直接原因：自身缺陷+开放性+黑客攻击
常见攻击：就是漏洞类型随便写几个

网络安全的任务
信息安全的任务
内容安全的任务
信息对抗的任务

第二章

整体框架❗❗

5个问题，及问题的解决方法
互联网络信息内容安全识别引擎架构

第三章

搜索引擎架构❗❗❗

那个图

七页逻辑图看一下不会考默写啥的❗

三个步骤

  1. 爬行与抓取
  2. 预处理
  3. 排名

爬行与抓取

网页为节点，hyperlink为有向边，深度优先|广度优先
从种子url提取待抓取url，待抓取url进行预处理分析后放入网页库并将这些url放入已抓取url中，同时从这些url中可以得到下一步的待抓取url

问题

  • 网页爆炸性增长——需要高效率
  • 服务器陷阱，法律问题，重复url，停电等

服务器保护：
robot.txt是crawer需要遵守的文件，但是也可以不遵守，君子协定
服务器陷阱，64k的NULL或嵌套重复url，超深路径

解决：
没有完美的解决，需要经常分析历史数据
太长url不爬，只爬静态内容，清除非文本的url等

爬虫需要：❗

  • 快
  • 可扩展性
  • 友好性
  • 健壮
  • 持续搜集
  • 时新性

高性能爬虫

爬虫架构
那个大图抽象一下即可

典型的DNS请求是异步的，若不采取措施，DNS地址解析会是爬虫的一个瓶颈
解决：

  • 缓存服务器
    大缓存容量，跨DNS系统的刷新保持内容，不同于普通DNS定期刷新，这里面向爬虫进行缓存的刷新
  • 预取client
    为了减少等待查找涉及新主机的地址的时间：尽早将主机名投给DNS系统
    提前拿url并给DNS，解析完之后方cache中等待使用
    通常用UDP实现，用不着等待解析的完成

网页抓取慢
并发抓取——瓶颈在处理器和硬盘

  1. 多线程/进程
    通常用阻塞的系统调用
    问题：
    内存地址空间不够
    互斥
    磁盘访问代价
  2. 异步非阻塞socket
    更高效的存储管理，不需要等网络操作的完成，网页抓取的完成不相互影响

Bloom filter——消除访问过的url❗
用来检测一个元素是不是集合中的一个成员。如果检测结果为是，该元素不一定在集合中；但如果检测结果为否，该元素一定不在集合中
牺牲了正确率和时间以节省空间

检测重复网页
完全重复网页可以md5
近似网页不能md5——Shingling

负载均衡：

  • 持续性负载
    通过提高服务器能力解决
  • 临时性负载
    使用缓存代理技术

分布式计算

  • 主从模式
  • p2p模式（一个圈）

任务如何划分？——一致性哈希❗
简单划分，直接把buckets给机器
问题：机器数目变化
一致性哈希——无需集中目录，也无需担心节点失效的一种查找元素位置的方法
目标：将item均匀的分布在不同的BUCKET中——负载均衡
使用cache机制的规则——3个
哈希值组成一个圈，计算出来的哈希值可以放在圈上，cache服务器也放在圈上。对象使用哈希值增大方向遇到的第一个服务器，若服务器减少，则有关的请求直接搜寻下一个服务器，若服务器增加，则只需要在圈上增加一个节点，仅需变动部分对象，比简单划分的几乎变动所有对象简单很多

网页排序

PageRank❗❗❗

每个节点给一个1/N的初始值（也可以是1）
排名泄露：存在节点没有出度，则最终所有PR趋向0
排名下沉：没有入度，PR趋于0
排名上升：形成圈，则成圈的几个网页PR只增不减

解决排名上升公式

a=0.85(一般)

Markov过程收敛，需要

  1. A为随机矩阵
  2. A是不可约的
  3. A是非周期的


先别急，我真忘了这玩意考不考，我十分希望不考，这明显就不是给大学生学的东西，应该是给高中生学的！

现象
链入链接从根本上决定PageRank大小
链入链接相同情况下，链出链接也影响PageRank的大小
评价：
总体：什么影响PR值
局部：链入相同时看链出，看最多，看最少

PR算法应用困难

  1. 现实世界与假想模型不同
  2. 实际计算中需要计算80亿网页

计算难点：

  1. 计算机容量限制
  2. 收敛问题-硬计算会很慢

索引

一个搜索引擎需要做的几件事

  1. 自动下载尽可能多的网页
  2. 建立快速有效的索引
  3. 根据相关性对网页进行公平准确的排序

信息检索模型
四元组[D, Q, F, R(qi, dj)]
– D: 文档集的机内表示——关键词
– Q: 用户需求的机内表示——查询式
– F: 文档表示、查询表示和它们之间的关系的模型框架(Frame)

  • R(qi, dj): 排序函数，给query qi 和document dj评分

布尔模型

Q：与或非
F：二值判断标准

正排索引
对于一个文档，所有的关键词排成一行，有的置1，没有的置0
目标文档所需关键词做一个类似的行，要的词置1不要的词置0，其他不管
然后这两行&一下，如果等于目标文档的行，则通过

倒排索引
对每个关键词建一行，行对应是文档，文档中有的对应位置1，没有的置0
目标需要关键词的行做bool运算，最后得到一行，行中置1对应的文档是结果
过程

  1. 找词
  2. 取地址列表
  3. 计算标识符

索引储存

  • 动态语料库
  • 静态收集
    -索引压缩
    <前缀长度，后缀>
    数字保存与上一数字的插值

布尔模型优点

  1. 查询简单易于理解
  2. 方便控制查询结果

布尔模型问题

  1. 不支持部分匹配
  2. 很难控制被检索的文档数量
  3. 很难对输出排序
  4. 很难自动反馈——提示用户如何更改查询式

向量空间模型

文档D(Document)
索引项t（Term）——检索词
特征项权重Wk（Term Weight）
相似度S（Similarity）

根据相似度对输出结果进行排序
支持自动的相关反馈

tf-idf
– tfij = 词项j在文档i中的频率——有除N和不除N两种
反应这个词对这篇文章是否更重要——越多越重要
– df j = 词项j的文档频率= 包含词项j的文档数量
– idfj = 词项j的反文档频率= log2 (N/ df j)——不一定2也可以是10
反映这个词在总体上是否重要——越多越不重要
TF-IDF = TF x IDF

查询式的词项权重

相似度计算
最佳的相似度计算方法并不存在

作用

  1. 排序
  2. 反馈
  3. 控制数量

计算方式

  1. 内积
    内积值没有界限
    对长文档有利
  2. 余弦

向量空间优点：

  1. 提高搜索性能
  2. 输出更合理
  3. 可以排序

缺点：

  1. 标引词之间被认为是相互独立
  2. 随着Web页面信息量的增大，查询结果会逐渐偏离用户需求
  3. 隐含语义索引模型是向量空间模型的延申

扩展布尔模型

先用布尔模型的出满足条件的文档，然后用向量空间法排序

如果“与”应用于布尔查询，结果集可能太窄，如果”或“应用于布尔查询时，就和纯向量查询没有区别——提出扩展布尔模型

扩展布尔模型的或关系
用到（0，0）的距离作为我的评价，越大越好
平方和除以二在开方

扩展布尔模型的与关系
用到（1，1）的距离作为我的评价，越小越好
用1减去与1的距离的平方和除以二再开方

忽略布尔关系的话，向量空间查询式和布尔查询式是相同的

p-norm模型

p=1时和向量空间中的内积相似
p=∞时模糊逻辑模型

第四章

网络流监控模式

  • 串联监控模式
    通过网关监控
    • 需要改变现有网络架构
    • 有延时
    • 故障直接断网
  • 旁路监控模式
    通过交换机的端口镜像实现监控
    • 部署方便，不影响现有网络架构
    • 不会造成延时
    • 故障不影响正常运行
    • 局限性
      • 数据获取
        需要交换机支持端口镜像
      • 数据管控
        采用发送RST来断开TCP，不能禁止UDP，UDP需要镜像设备通知防火墙管理

旁路检测技术

  • 数据分流
    • 分光器
    • 路由交换
    • HUB
  • 数据汇聚
  • 报文抓取
    • 这个图很重要
    • 影响性能因素
      • 系统调用
      • 数据拷贝
      • 计算校验和
      • 网卡中断
  • 报文抓取过程优化
    • 报文捕获后直接给用户态专用协议栈抽取，而不是过机器的协议栈走系统调用再解码，这样做可以由原来的三次拷贝编程一次拷贝，并且只用了一个缓冲空间
  • 协议还原
  • 内容抽取
  • 数据耦合方法

关键技术

他上课说没什么用，喜欢出原理性东西，代码啥的不用，进程通信是重点

进程通信技术——UNIX

进程通信方法（IPC）
Unix IPC包括：管道、FIFO、信号
System V IPC包括：System V消息队列、System V信号灯、System V共享内存区
Posix IPC包括：Posix消息队列、Posix信号灯、Posix共享内存区

进程通信技术：
管道，命名管道，信号，报文队列，共享内存，信号量，套接口

linux进程要素：
一段可执行程序，专用系统堆栈空间，进程控制块，独立存储空间

内存映射技术
共享内存：最有效的进程间通信方式，也是最快的IPC方式
一块物理内存被映射到进程AB各自的进程地址空间
需要同步机制，互斥锁或信号量都可以

mmap()系统调用
将文件映射到进程地址空间

  1. page cache和swap cache
    一个被访问文件的物理页面都驻留在这两个里面
  2. 文件与address_space的对应
    address_space中一个偏移量能确定上面两个的一个页面
  3. 调用mmap
    只是再进程空间中新增一块缓冲区，但没有建立进程空间到物理页面的映射。因此第一次访问这个空间时引发一次缺页异常
  4. 缺页异常处理
    现在swapcache中找页面，要是没找到则看这个页面是不是在swaparea里，要是还没有就建立一个页面更新页表
    对于普通文件映射情况则在pagecache里找页面
  5. 多进程映射同一个共享内存区域
    建立线性地址与物理地址的映射后，进程实际访问的一定是同一个共享内存区域的物理页面

使用mmap的两种共享内存方式

  1. 使用普通文件提供的内存映射
    • 使用于任何进程
    • 打开或创建一个文件，再调用mmap
  2. 使用特殊文件创建匿名内存映射
    • 适用于有亲缘关系的进程
    • 父进程先mmap再fork

Linux设备
字符设备，块设备，网络设备

设备文件与设备号
用户通过设备文件访问设备，每个设备用一个主设备号和次设备号标识

设备驱动的功能
管理IO设备
上层软件的抽象操作与设备操作的转换

VFS是虚拟文件系统

内核模块
Linux内核运行时动态扩展的一种技术
Linux设备驱动以内核模块形式实现
一组可以加载/卸载的代码

设备驱动的结构

  • 驱动与内核的接口
    • 注册/卸载
    • VFS接口
    • 数据交互
    • 中断注册
  • 硬件设备接口
    • 硬件探测
    • 初始化
    • 读写访问
    • 设备控制

Linux数据包接受过程
物理层->链路层->网络层->传输层

TCP/IP与以太网
以太网和TCP/IP可以说是相辅相成的
以太网提供MAC地址连线
TCP/IP提供32位IP地址

载波监听，冲突检测

以太网的广播通讯
在以太网中，所有的通讯都是广播的
通常在同一个网段的所有网络接口都可以访问在物理媒体上传输的所有数据

网卡的MAC地址是唯一的48位

网络接口应该响应的两种数据帧

  • 与自己MAC匹配的数据帧
  • 广播数据帧

数据接受过程

  1. 网卡收到数据，单片程序判断自己是否该收
  2. 若该收则向CPU中断，然后把包给驱动程序分析，驱动程序分析完将数据交付操作系统
  3. 若不该收则直接丢弃，CPU根本不知道

网卡的四种接收模式：

  1. 广播模式：能接受网络中广播信息
  2. 组播模式：网卡能接收组播数据
  3. 直接模式：只有目的网卡能接受数据
  4. 混杂模式：能接受一切通过他的数据

Libpcap

不是很重点

Libpcap (Packet Capture library)，即数据包捕获函数库，可用于捕获经过网络接口(只要经过该接口，目标地址不一定为本机)的数据包，采用libpcap可以捕获本地网络数据链路层上的数据

基于BPF系统
BPF主要由两部分组成：Network tap和Packet Filter

Libnet

libnet提供的接口函数主要用于实现数据包的构造和发送
libpcap提供的接口函数主要用于实现数据包截获(接收)
libnids提供的接口函数主要实现了开发网络入侵监测系统(nids)所必须的一些结构框架
libicmp封装的是ICMP数据包的主要处理过程(构造、发送、接收等)

Libnet概述
功能:数据包构造和发送
可以不用程序员去整解析报文啥的，可以方便快速简单的完成报文组装工作

Libnids

在libnet和libpcap的基础上开发的，封装了开发NIDS所需的许多通用型函数
linids提供的接口函数监视流经本地的所有网络通 信，检查数据包等

Libnids原理，一个大图

libnids的每级回调函数可以是多个
可以有多个ip/tcp/udp_callback
libnids的IP回调函数已经进行分片重组
ip_callback不会存在ip分片

数据结构
tuple4：用于描述一个地址端口对，它表示发送方IP和端口以及接收方IP和端口
half_stream：此数据结构用来描述在tcp连接中一端的所有信息，可以使客户端也可以是服务端
tcp_stream:描述的是一个TCP连接的所有信息

开发示例
jflow，tcp.c

第五章

串匹配概念

尤其是信息检索和生物计算领域中的许多共同需求

  1. 文本：由若干个字符组成的有限序列
  2. 模式：也称为关键字，由若干个字符组成的有限序列
  3. 模式集：指所有需要匹配的模式形成的集合
  4. 最小模式长度：假设模式集中各个模式长度分别为l1,l2,…lr,那么最小模式长度是指所有模式长度的最小值
  5. 前缀：两个字符串 p和x，若存在字符串v（v可为空串），使得p=xv成立，称x为p的前缀
  6. 后缀：两个字符串p和x,若存在字符串u（u可为空串）,使得p=ux成立，称x为p的后缀
  7. 子串：两个字符串p和x,若存在字符串u,v（u,v可以为空串），使得p=uxv成立，称x为p的子串
  8. 字符集：在模式或文本中所有可能出现的字符形成的集合，记为Σ ，其大小记为|Σ|。

单模匹配
在一个文本text(设长度为n)中查找某个特定的子串pattern(设长度为m)。如果在text中找到等于pattern的子串，则称匹配成功，函数返回pattern在text中出现的位置(或序号)，否则匹配失败

多模匹配
在一个文本text(设长度为n)中查找某些特定的子串patterns(设长度为m)。如果在text中找到等于patterns中的某些子串，则称匹配成功，函数返回pattern在text中出现的位置(或序号)，否则匹配失败

BF算法

简单，时间复杂度差

KMP

KMP算法根据前缀模式可以使模式向前推进若干字符位置（依前缀模式长度而定），而不只是一个字符，避免了重复比较，同时也实现了文本指针的无回朔

“前缀”指除了最后一个字符以外，一个字符串的全部头部组合

移动位数 = 已匹配的字符数 - 对应的部分匹配值

next数组求解方法

第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。
首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1

KMPnext可以把next中全部减一，如果当前位于首位相同还能再减一
每次不匹配时可以右移i-kmpNext[i]位

BM

速度最快算法
算法对模式从最右端自右向左扫描。在不匹配（或完全匹配）时，用两个预先计算的函数bad character和good suffix 来确定指针在正文中移动的距离

只要尾部不匹配，则在模式串中找一样的坏字符对齐，否则将整个匹配串移到坏字符后面
后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
如果”坏字符”不包含在搜索词之中，则上一次出现位置为 -1
后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
如果”好后缀”在搜索词中没有重复出现，则它的上一次出现位置为 -1

移动是坏字符和好后缀的最大值

计算出字符集中每个字符的偏移值bmBC[i],对于未在模式中出现的字符，偏移为m,否则取m-i-1,(其中i为字符在模式中的位置)

我是真没看懂那两个东西是咋算的

AC算法

多模式匹配问题在生物计算、信息检索及信号处理领域有着非常广泛的应用

自动机（Automata）：确定型有限自动机DFA(Deterministic finite automata)是一个五元组M = {S,Σ,δ,s0,S1}

  1. 拆分关键字，生成状态图
  2. 使用状态机

时间复杂度为O(n)

树形有限自动机

笔记-考点