感谢HOMOLAB的精彩文章，让我对SSD有了更为科学的认识 PART I 固态硬盘（SSD）基础 1.1 发展历史与演进 NAND Flash 原理：1145141919810个浮栅晶体管平铺堆叠（发配到模电区）。把晶体管在不同挡位的电压（浮栅晶体管捕获存储的电子数量差异导致电压不同）当作信息。 比特数与存储密度 单元 数据量（二进制位数） SLC 1 MLC 2 TLC 3 QLC 4 性能与耐用性 从SLC➡MLC➡TLC➡QLC： 存储数据难度上升：主控在写入数据时，需要精确地控制浮栅中电子的数量； 读取数据的难度上升：主控在读取数据时，也必须非常精确地判断当前电压属于哪个区间，否则可能导致误读； 耐久性降低：存储信息越多，对电压精度要求越高。擦写次数越多，浮栅的磨损就越大，电压状态就越不稳定。 原因：如QLC，将16种不同的电压状态挤在一个小小的浮栅晶体管里，就好比在一条狭窄的公路上行驶16辆车。每辆车之间的安全距离会变得非常小。 1.2 SSD 的基本构成 NAND Flash 存储芯片：浮栅晶体管堆叠，有着比较玄学的寿命说 Block（擦除的最小单位） ➡ Page（读写最小单位）➡ Cell 主控（Controller）：硬盘里管理数据的大脑，在如今SSD产品损坏的案例里一般是由于主控物理暴毙或者固件暴毙导致的 DRAM 缓存（不是都有） 无缓（DRAMless SSD） 有缓（DRAM SSD）：存储FTL表，便于寻址 PART II SSD工作原理 2.1 读写与擦除 REW（Read-Erase-Write） 固态的擦除是以block为单位、读写以page为单位，nand的物理特性决定了他不能覆盖写入。因此如果我们要对一个已有数据的page进行写入，那么必须先要把这个page所在的block中的数据读出，block清空后再把所有数据写进去。 2.2 核心技术与机制 PART III SSD性能参数与协议 3.1 关键性能指标 IOPS（Input/Output Operations Per Second）：如英文名，硬盘每秒钟能够处理的输入/输出操作次数。 传统指标：随机和顺序是HDD时代传承下来的概念，在SSD中或许不再适用，但仍然被广泛使用。 顺序读写（Sequential Read/Write）： 顺序读写是指数据在存储介质上连续存储和读取的方式，通常用于大文件传输或连续数据流的处理。参数通过用大文件进行读写测试来获得。 随机读写（Random Read/Write）：随机读写是指数据在存储介质上分散存储和读取的方式，通常用于小文件或随机访问的数据。一般使用大量小文件进行读写测试。 相关论述文章《随机 稳态 缓外 无知以及谎言,不存在的随机写入》总结： SSD数据存储在NAND的多个页（Page）中，页是SSD的最小读写单位； SSD读取数据时，一般需要根据FTL（Flash Translation Layer）将逻辑地址转换为物理地址； FTL表的查询需要时间，如果一个文件分布在临近的物理空间上,那么对其进行读写的操作就不需要多次查询FTL表从而节省开销； FTL表的映射是非线性的，物理上连续的存储单元未必在逻辑上是连续的； 对于一个大块的连续文件写入而言,看起来是顺序写入，但数据不会集中在某一个NAND的某一个DIE的某一个plane的某一个block,而是分布在不同NAND上的不同block中； 因此，顺序读写和随机读写的概念对于SSD并不完全适用，SSD的性能更多地取决于其内部结构和数据管理方式；因此，顺序读写和随机读写的概念对于SSD并不完全适用，SSD的性能更多地取决于其内部结构和数据管理方式； 缓外速度（Sustained Write Speed）：在SLC Cache技术应用后产生的概念 定义：缓外速度是指在SSD的SLC Cache被填满后，数据写入到TLC或QLC NAND Flash时的速度。通常情况下，SLC Cache可以提供更高的写入速度，而缓外速度则较低。 备注：缓外速度不等同于SSD的实际写入速度，在如今常常导致用户对SSD性能的误解。实际上，连续大容量写入分多个阶段（关键词：SLC Cache释放、REW、Writeback惩罚、TLC/QLC直写、GC回收），而这受到厂家设计策略的影响，部分用户观察到的缓外速度没有太大的意义。 WAF（Write Amplification Factor） 定义：写放大因子，表示实际写入的数据量与原始数据量的比率。 产生原因：SSD是以页为单位进行读写，但由于NAND Flash的特性，无法直接覆盖写入，因此需要先擦除整个块（Block），然后再写入新的数据。这种操作会导致实际写入的数据量大于原始数据量，从而产生写放大现象。 WAF与脏盘度（Dirty Page）：WAF与脏盘度密切相关，较高的脏盘度意味着更多的数据需要被擦除和重写，从而增加了写放大现象。 3.2 消费级常见接口与协议 SATA（Serial ATA） 传输速率：SATA III的最大传输速率为6 Gbps（约750 MB/s）。 特点：SATA接口是传统的硬盘接口，主要用于连接机械硬盘和早期的SSD。 目前SATA接口的SSD产品性价比较低 NVMe（Non-Volatile Memory Express） 传输速率：NVMe接口的传输速率远高于SATA接口，理论上可以达到32 Gbps（约4 GB/s）甚至更高。 特点：NVMe接口专为SSD设计，能够充分发挥NAND Flash的高速性能，具有更低的延迟和更高的并发处理能力。 UFS（Universal Flash Storage） 传输速率：UFS 3.0的最大传输速率为23.2 Gbps（约2.9 GB/s）。 特点：UFS接口主要用于移动设备，如智能手机和平板电脑，具有更低的功耗和更高的性能。 CFexpress（CompactFlash Express） 传输速率：CFexpress 1.0的最大传输速率为1 GB/s，CFexpress 2.0可以达到2 GB/s。 特点：CFexpress接口主要用于专业相机和摄像机，支持PCIe和NVMe协议，具有高性能和低延迟。 SD Express（Secure Digital Express） 传输速率：SD Express的最大传输速率为985 MB/s。 特点：SD Express是SD卡的最新标准，支持PCIe和NVMe协议，主要用于移动设备和相机。 PART IV 主控与固件深度解析 4.1 SSD主控的功能与作用 SSD主控是固态硬盘的核心组件，负责管理数据的读写、擦除和存储。它的主要功能包括： 数据管理：主控负责将数据从主机传输到NAND Flash，并在需要时将数据从NAND Flash传输回主机。 地址映射：主控使用FTL（Flash Translation Layer）将逻辑地址转换为物理地址，以便正确地读写数据。 垃圾回收：主控定期执行垃圾回收操作，以释放被删除或过时数据占用的空间，从而提高SSD的性能和寿命。 性能优化：主控通过各种技术（如SLC Cache、OP等）来优化SSD的性能和耐用性。 固件更新：主控可以通过固件更新来修复错误、改进性能或添加新功能。 4.2 固件的优化策略 4.2.1 SLC Cache 产生原因：SLC Cache是为了提高SSD的写入性能而设计的。由于SLC（单层单元）具有更高的写入速度和耐用性，SSD制造商通常会将一部分TLC或QLC NAND Flash配置为SLC Cache（主控只需要区分两种电压状态），以便在写入数据时先使用SLC Cache进行高速写入。 种类： 全盘SLC Cache：将整个SSD的部分空间配置为SLC Cache，通常在SSD的容量较大时使用。比较考验主控的算法设计能力。 分区SLC Cache：将SSD的部分空间划分为SLC Cache，通常在SSD的容量较小或中等时使用。 动态SLC Cache：根据实际写入需求动态分配SLC Cache的大小，通常在SSD的空闲空间较多时，SLC Cache会较大。比较考验主控的算法设计能力。比较出色的产品：Solidigm P41 Plus(QLC) 写入流程（与主控、算法与固件有关，此处仅仅阐释常见的SLC Cache写入流程）： FOB阶段：主控将数据写入SLC Cache，SLC Cache的写入速度通常较快，因为SLC只需要区分两种电压状态（0和1）。 Transition过渡态：当剩余空间处于一定低线时，SSD内部将并未完整写入的page进行整理、触发GC回收机制将标记删除的数据从Nand上物理的删除掉。由于还有部分未写入的page可以利用,因此R-E-W惩罚为中等,并发效率受到一定程度的限制。 R-E-W惩罚：在这一阶段，由于GC回收和数据整理的需求，SSD的写入性能可能会受到影响，导致写入延迟增加。 GC回收：当所有的空间都不可用或者可用度很低，SSD不得不实时性的进行垃圾的释放(GC回收)：读取垃圾文件所在块上的其他有效数据➡擦除整个块➡把这些数据整理并腾挪到其他地方。 Steady稳态：GC回收、R-E-W进入了一个动态均衡的状态，因而性能维持在一条线上。主控和NAND成为当前的主要瓶颈（对于主控来说，它在这一高负载的情况下需要频繁的进行GC回收的处理、写入与读取数据的命令分配、磨损平衡的计算、数据纠错等操作） 4.2.2 地址映射表（FTL） 定义：FTL（Flash Translation Layer）是SSD中的一种关键技术，负责将逻辑地址映射到物理地址，以便正确地读写数据。 优化策略：为了提高FTL的性能，SSD制造商通常会采用多种优化策略，如： 使用DRAM缓存：在SSD中增加DRAM缓存，以提高映射表的查询速度。 采用分层映射：将映射表分为多个层次，以减少查找时间。类比内存中的多级页表。 进行预读和预写：根据访问模式预测数据的读写需求，提前加载或写入数据。 4.2.3 OP（Over-Provisioning） 定义：OP（Over-Provisioning）是指在SSD中预留一部分额外的空间，以提高性能和延长寿命。 原理：通过增加闲置空间，OP可以减少写放大现象，提高垃圾回收效率，从而提升SSD的整体性能和耐用性。 注意事项： OP的大小需要根据实际使用场景进行合理配置，过大或过小都会影响SSD的性能。 OP的使用需要与其他优化策略结合，以达到最佳效果。 4.3 Writeback惩罚的原理与影响 定义：Writeback惩罚是指在SSD中，由于数据写入策略和垃圾回收机制的影响，导致写入性能下降的现象。 原因：当SSD的SLC Cache被填满后，数据需要写入到TLC或QLC NAND Flash中，这个过程通常会比SLC写入慢得多。此外，在进行垃圾回收时，SSD需要读取、擦除和重写数据，这也会导致写入性能下降。 影响：Writeback惩罚会导致SSD在高负载情况下出现明显的性能下降，影响用户的使用体验。 4.4 SSD维护 4.4.1 S.M.A.R.T.表 功能：S.M.A.R.T.可以实时监测SSD的各项指标，如温度、写入/读取错误率、剩余寿命等，并在出现异常时发出警告。 关键指标： 03：可用备用空间，代表SSD中已使用Over-Provisioning的大小。 0E：介质与数据完整性错误计数，只要大于0则表示存在潜在的介质损坏风险。 4.4.2 TRIM 定义：TRIM是一种命令，允许操作系统通知SSD哪些数据块不再使用，从而帮助SSD进行垃圾回收。 方法：大多数现代操作系统（如Windows、Linux和macOS）都支持TRIM命令，用户无需手动操作。
第一章 计算机网络体系结构 I.计算机网络概述 概念 计算机网络是互连的、自治的计算机集合。 由节点（Node）和连接这些节点的链路（Link）组成。 组成 组成部分：硬件、软件、协议 工作方式： 边缘部分：用户直接使用的主机 核心部分：网络的基础设施，如路由器、交换机等 功能组成： 通信子网：负责数据传输 资源子网：负责资源管理 功能 数据通信 资源共享 分布式处理 提高可靠性 负载均衡 交换技术 种类 交换技术 特点 优点 缺点 电路交换 1.需要建立物理连接通道2.传输过程中通道被==独占== 1.通信时延2.适用于实时通信3.能够完全有序传输 1.建立连接时间长2.线路利用率低灵活性差3.难以实现差错控制 报文交换 1.报文封装全部信息2.==全部存储==后再转发3.无需建立连接 1.适用于短报文传输2.适用==不确定==通信量3.线路可靠4.动态分配线路 1.转发时延长2.缓存开销大3.难以实现差错控制 分组交换 1.报文分割成==固定长度==的分组2.==存储转发==3.无需建立连接 1.减少出错概率2.简化缓存3.流水线加速 1.存在存储转发时延2.需要额外信息量3.可能出现乱序、丢失、重复分组 [!Important] 报文转发和分组转发存在处理延迟，即上图中的空隙 分组转发花费时间和中间节点数量有关系，一些情况下可以简便运算 区别 计算机的数据传送往往是突发式的，采用电路交换时通信线路的利用率很低。报文交换和分组交换不需要建立连接（即预先分配通信资源），在传送计算机的突发数据时可以提高通信线路的利用率 将报文构造成若干个更小的分组进行分组交换，比将整个报文进行报文交换的时延要小，并且还可以避免太长的报文长时间占用链路，有利于差错控制，同时具有更好的灵活性。 分类 分布范围 广域网（WAN） 城域网（MAN） 局域网（LAN） 个人区域网（PAN） 传输技术 广播式网络 点对点网络 拓扑结构 总线型 星型 环型 网状型 关于差别，在通信效率、可靠性、扩展性、成本等方面出题 网络性能指标 [!Important] 速率中的K、M、G表示的是十进制，分别为10^3、10^6、10^9 速率 带宽 模拟信号：频率范围（Hz） 计算机网络：最高数据传输速率 吞吐量：单位时间通过网络的实际数据量 时延 发送时延 t_s = 数据块长度/发送速率 传播时延 t_c = 信道长度/传播速率 处理时延 排队时延 总时延 = 发送时延 + 传播时延 + 处理时延 + 排队时延 时延带宽积: 传播时延 * 带宽 往返时延 RTT=|发送报文时间 - 接收确认ack时间| ！信道利用率 U 空闲时延 D_0、当前时延 D D = \frac{D_0}{1-U}，U 越大，当前时延 D 越大 II.计算机网络体系结构 分层结构 分层基本原则 每层实现特定功能 各层间由可以互相通信的接口 下层独立于上层，即没有上层也能工作 上层==单向==使用下层服务 结构元素 实体 实体：在通信过程中能够发送或接收信息的硬件或软件模块 对等实体：在通信过程中能够相互通信的实体 协议数据单元（PDU）：对等层水平传递的数据单元，分为数据和控制信息 服务数据单元（SDU）：对等层垂直传递的数据单元，服务上层 协议控制信息（PCI）：对等层水平传递的控制信息 [!Note] 第n层收到的PDUs称为n-1层的SDUs，加上第n层的PCI就构成了n层的PDUs ！协议、接口、服务 协议（水平关系） 协议 含义 作用 举例 语法 数据格式 数据的结构和编码 TCP 报文的格式由语法决定 语义 具体操作流程 何时发何种控制信息、如何应答 TCP 三次握手具体操作 同步（时序） 操作条件、时序 明确数据交互的顺序流程 TCP 连接的建立、关闭报文时序 接口 服务访问点 SAP（Service Access Point）：同一节点内相邻层之间的接口，提供服务访问点 服务（垂直关系） 服务原语：服务提供者和服务用户之间的通信操作 请求：服务用户向服务提供者发出的请求，请求服务提供者执行某种操作 指示：服务提供者向服务用户发出的指示，要求服务用户执行某种操作 响应：服务用户向服务提供者发出的响应，表示对指示的响应 证实：服务提供者向服务用户发出的证实，表示对请求的证实 服务分类 面向连接服务和无连接服务：是否建立连接 可靠服务和不可靠服务：是否保证数据传输的可靠性 有应答服务和无应答服务：是否需要对数据传输进行应答 OSI参考模型 低三层为通信子网，高三层为资源子网 层次 名称 传输单位 功能 协议 1 物理层 比特 1.规定物理接口参数2.规定信号意义和电气特征 IEEE802.3 2 数据链路层 帧 1.速率协调2.差错检测（==只能丢弃==）3.流量控制 SDLC、HDLC、STP、PPP、 3 网络层 数据包 点到点 1.差错、拥塞控制2.路由选择3.分组交换4.流量控制 IP、ICMP、IGMP、ARP、RIP、OSPF 4 传输层 段 端到端 1.差错控制2.流量控制3.拥塞控制 TCP、UDP 5 会话层 数据 1.建立、==同步==、释放会话2.建立恢复点 6 表示层 数据 1.数据格式转换2.数据==加密、压缩== 7 应用层 数据 1.提供用户接口2.文件传输3.电子邮件4.远程登录 HTTP、FTP、SMTP、POP3 [!Tip] 流量控制： 数据链路：相邻节点之间的流量控制 网络层：==整个网络==中的流量控制 传输层：端到端的流量控制 TCP/IP参考模型 网络接口层 与OSI的物理层和数据链路层对应 功能：定义网络接口标准 以太网、令牌环、FDDI、ATM、PPP、SLIP 网际层 与OSI的网络层对应 功能：IP寻址、路由选择、分片、差错检测 协议：IP、ICMP、ARP、RARP 传输层 与OSI的传输层对应 功能：差错控制、流量控制、拥塞控制 协议：TCP、UDP 应用层 与OSI的应用层、表示层、会话层对应 功能：提供用户接口、文件传输、电子邮件、远程登录 协议：HTTP、FTP、SMTP、POP3 ！OSI与TCP/IP对比 OSI 是理论模型，TCP/IP 是实际模型 OSI 七层，TCP/IP 四层 OSI 在网络层支持面向连接和无连接服务，而 TCP/IP 只支持无连接服务 OSI 的传输层只提供端到端可靠传输，而 TCP/IP 的传输层提供不可靠传输 UPD 和可靠传输 TCP 第二章 物理层 实现功能： “透明”传输比特流； 物理接口特性 机械特性：形状尺寸、引脚设计 电气特性：信号电压、阻抗、传输速率、距离限制 功能特性：规定接口各电缆作用（网线八根作用）、电压波形含义 过程特性：信号时序关系 I.通信原理 基本名词 数据、信号和码元 数据：传送信息的实体 信号：数据的电气和电磁表现 码元：不同离散数字的基本波形 模拟数据（信号）是连续的 数字数据（信号）是离散的 信源、信道和信宿 信源：产生和发送数据的源头 信宿：接收数据的终点 信道： 基带信号是数字0/1；宽带信号是模拟波形 数字信道传输数字信号；模拟信道传输模拟信号 速率、波特和带宽 码元传输速率（波特率Baud/s） 信息传输速率（比特率b/s） 带宽 模拟信号通信：频率范围Hz 计算机网络：最高数据传输速率b/s 传输方式 串行并行 局域网：串行 计算机内部：并行 同步异步 同步传输 外同步：外加时钟 内同步：信号编码同步 ==异步传输==：字节间异步，字节内同步 单工双工 单向：广播 半双工：对讲机 全双工：互联网 编码与调制 数字数据->数字信号 归零（RZ）编码 0：前低后零 1：前高后零 不归零（NRZ）编码（==无自同步==） 0：低电平 1：高电平 曼彻斯特编码：以太网 设定初始信号形式 码元必定在中间跳变 码元==中间==电平变化表示信号0/1 差分曼彻斯特编码 码元==开始==无跳变表示1，有跳变表示0 模拟数据->数字信号 奈奎斯特定理：f_{采样}≥2*f，才能完整保留信号信息 数字数据->模拟信号 调幅（AM）：载波振幅变化表示0、1 调频（FM）：载波频率变化表示0、1 调相（PM）：载波相位变化表示0、1 正交幅度调制（QAM）：R = B*log_{2}（mn） 信道容量 奈奎斯特定理（无干扰） 奈奎斯特速率v = 2Wlog_{2}V W：信道频率带宽范围（Hz） V：码元离散电平数量 香农定理（有噪声） 香农速率C = Wlog_{2}(1+\frac{S}{N}) W：信道频率带宽范围（Hz） \frac{S}{N}：信噪比 [!Note] 计算时注意“二进制”、“十六进制”等字眼，是波特值的含义，则要在v和C中选出最小的 分贝值的大小为 d=10log_{10}(\frac{S}{N})，注意转换 信道复用 频分复用 FDM：不同用户用不同频率的信道，限于模拟信号 时分复用 TDM：分时服务用户 波分复用 WDM：（光的）波长 ！码分复用 CDM 码片m_i：分给每个站码片 m_i，码片之间正交 码片向量：码片 m_i 的1为1，0为-1 站点发送：比特1为码片向量，比特0为码片销量负值 站点接收：与自身码片向量相乘，除以码片长度 II.传输介质 双绞线 同轴线缆 光纤：==外低（反射率）内高（反射率）== 多模：光的全反射；光源为发光二极管 单模：直径小于光的波长，光沿直线；光源为半导体激光 无线传输： 无线电波 激光、红外线、微波 III.物理层设备 中继器 功能：整形、放大并转发数字信号 “5-4-3”原则：5段通信介质由4个中继器连接，最多挂载3个计算机 [!Tip] 放大器放大的是模拟信号 两端可以是不同介质，如无线有线，则两端可以是不同的链路层协议 集线器（Hub） 功能：多端口中继器；整形、放大信号，扩大网络范围 ==半双工== 第三章 数据链路层 实现功能： 封装成帧 透明传输 差错检测 I.数据链路层概述 相关名词 链路：从一个节点到相邻节点的通信信道，中间==无交换节点== 数据链路：链路+链路层协议 帧：数据链路层传输的数据单元 PDU ！服务 无确认的无连接服务：不需要建立连接，不需要确认，如以太网 有确认的无连接服务：不需要建立连接，需要确认，如无线局域网 有确认的面向连接服务：需要建立连接，需要确认，如PPP 设备 交换机（多接口网桥） 工作流程 自学习：收到帧，发现转发表中没有此帧的源MAC和目的MAC，记录MAC和对应接口，并广播到==其他==所有接口 转发：收到帧，转发表中有目的MAC表项，转发到对应接口 工作模式 直通交换：只检查帧首目的MAC地址，直接转发 存储转发：存储到内存中进行检错，错则丢，无损则转发 特点 隔离冲突域：星型一对一 不隔离广播域：广播帧都会被转发 ！功能 封装成帧 在数据前后加上帧首部和帧尾部 帧首部和帧尾部 帧首部：帧起始标志、地址、控制、协议 帧尾部：校验和 以太网V2的MAC帧格式（左尾右首） FCS 数据载荷 类型 源地址 目的地址 4B 46-1500B 2B 6B 6B PPP的帧格式（左尾右首） 标志 FCS 数据载荷 协议 控制 地址 标志 1B 2B 最大1500B 2B 1B 1B 1B 帧定界 帧同步 透明传输 传输的数据不受特殊字符的影响 字符填充：在数据中插入转义字符，如HDLC的ESC(11111101) 字符计数：在帧首部加入帧长度 流量控制 控制==发送方==发送速率，防止接收方缓存溢出 OSI体系中，数据链路层有流量控制的功能 TCP/IP体系中，流量控制由==传输层==负责 差错检测 通过确认重传、CRC检测帧中的错误 CRC：检测帧内位错，将帧看成多项式，除以生成多项式，余数作为校验码 确认重传：帧丢失，超时重传 通信质量好的线路，仅进行CRC检测，重传由上层协议处理 通信质量差的线路，进行确认重传 II.组帧 功能：将网络层递交的分组封装成帧 问题：帧定界、帧同步、透明传输 字符计数法：帧首部添加==计数字段==记录该帧的字节数 字节填充法： 添加SOH、EOT标识帧头帧尾 数据段中存在”SOH、EOT、ESC“字符，前面添加ESC进行转义 （==HDLC==）零比特填充法： 使用01111110标志帧开始和结束 数据字段中每连续5个”1“后自动添加一个”0“ 违规编码法：使用数据传输方式中不用的编码标识首尾 III.差错控制 检错编码 奇偶检验码：数据中”1“的个数 循环冗余码CRC 约定 G(x) = x^{n_k}+x^{n_{k-1}}+···+x^{n_1} 冗余码计算：在源数据后加 G(x) 中 Max(x_{n_k}、x_{n_{k-1}}···x_{1}) 位，进行除法计算 纠错编码 海明码距 d_{min} 检错数量 r = d_{min}-1 校正错误数量 r = (d_{min}-1)/2 海明码：见车爹PPT IV.流量控制和可靠传输 流量控制 流量控制指由==接收方控制发送方==的发送速率。 数据链路层控制的相邻结点之间的流量；传输层控制端到端流量 数据链路层控制方法：接收方是否返回ACK控制；传输层控制方法：接收方在ACK设置窗口值调整发送方的发送窗口 可靠传输 可靠传输是指发送方数据能被接收方正确接收 有线网络数据链路层不负责可靠运输 无线网络数据链路层负责可靠运输 停止等待协议(S-W) 一次只发送一帧 超时重传 一位比特编号 设置帧缓冲区用于重传 后退N帧协议(GBN) 发送方在发送窗口内连续发送 接收方发现丢失一帧，后面全无效 接收方可累计确认，只确认最新连续的一位 发送方接收到ACK后，可直接将窗口后滑 选择重传(SR) 发送方在发送窗口内连续发送 接收方必须每帧都发送确认 接收方检测到错误帧就发送NAK，要求==立即重传==要求的帧 [!Tip] 注意题目中的帧数和帧序号比特数区别 帧序号比特数k：2^k - 1 >= n V.介质访问控制 随机访问控制 ALOHA协议 纯ALOHA协议 发送方：随机发送数据帧，发送成功则等待下一帧，发送失败则等待随机时间后重传，直到发送成功 时隙ALOHA协议 发送方：等待下一个时隙发送数据帧，发送成功则等待下一帧，发送失败则等待下一个时隙后重传，直到发送成功 CSMA协议 1-坚持CSMA协议 发送方：要发送信号时，持续监听信道，信道空闲则发送数据帧，直到发送成功 非坚持CSMA协议 发送方：要发送信号时，若信道忙则等待随机时间后再次监听信道，信道空闲则发送数据帧，直到发送成功 p-坚持CSMA协议 发送方：要发送信号时，若信道忙则等待随机时间后再次监听信道，信道空闲则以概率p发送数据帧，以概率1-p继续等待 CSMA/CD协议 总线型有线网络 半双工通信 发送阶段：检测冲突 争用期 t=2τ ：代表信号在端到端往返的最大时间，若在此时间内没有检测到冲突，则发送成功 最小帧长L_{min} = 2τ*v：保证在发生冲突时，发送方能检测到冲突； 10Mbps以太网：t= 51.2μs，L_{min} = 512bit =64B ！冲突阶段：截断二进制 二进制指数退避算法：R = rand(0,1,···,2^k-1)，k=min(n,10)，n为冲突次数 重传推迟时间t_{backoff} = R*2τ 发送失败：当n >= 16时，发送失败 ！CSMA/CA协议 无线局域网 发送阶段 源站检测信道空闲，等待==DIFS==长度的时间准备发送 源站检测信道空闲，使用==随机避让算法==延迟 [可无此阶段]信道预约阶段 源站广播发送==RTS==报文 目的站等待==SIFS==后，发出==CTS==，通信范围接收到此帧的其他站保持静默（处理隐蔽站问题） 数据传输阶段 源站接收到CTS，等待SIFS后开始发送 目的站接收完数据后，等待SIFS后发送ACK帧回应直到源站接收 此阶段对于其他站为NAV（信道忙）时间 IFS（InterFrame Space）:帧间间隔 DIFS：分布式协调IFS，只在源站侦测到空闲后触发 SIFS：短IFS，在任意类型帧间触发 RTS（Request To Send）：请求发送控制帧 源地址 + 目的地址 本次通信所需时间：SIFS + CTS + SIFS + 数据帧 + SIFS + ACK 即对面接收完RTS开始，到己方接收完ACK结束 CTS（Clear To Send）：允许发送控制帧 给源站明确的发送指令 指示其他站在预约期内保持静默 预约期：SIFS + 数据帧 + SIFS +ACK 即对面接收完CTS开始，到对面接收到ACK结束 NAV（Network Allocation Vector） 预约时间/信道被分配时间 在CTS中标明，NAV = SIFS + 数据帧 + SIFS + ACK 随机避让算法 基本退避时间 2τ 退避计时器在第k次：R=rand(0,1,···，2^{k+2}-1)，k<=6 退避时间 2τ*R 轮询访问 令牌传递协议 源站按环路连接，令牌轮流传递； 一个站点拥有令牌后 无数据发送，则立即传给下一站 有数据发送，将令牌中插入数据发送，每次只能发送一帧； 数据帧在环路循环转发，目的站收到后复制再继续转发； 源站收到后检验帧，出错则重发，否则生成新令牌并传递给下一站。 VI.局域网 概览 介质访问控制方法：CSMA/CD、令牌总线、令牌环 局域网拓扑：以太网、令牌环、FDDI IEEE802定义： 逻辑链路控制（LLC）：无确认无连接、带确认无连接（帧加序号）、面向连接、高速传送、寻址、竞争处理 介质访问控制（MAC）：组帧、差错控制、透明传输 以太网V2/802.3 结构：逻辑总线型、物理星型（一交换机连多终端） CSMA/CD协议 无连接、无确认、不可靠 曼彻斯特编码 网卡（网络适配器）：数据==串并联转换==、直接丢弃差错帧、正确帧触发中断 MAC地址：6B = 48b 以太网V2 MAC帧 MAC层：MAC帧 物理层：前导码（8B，7B前同步码+1B帧开始定界符）+ 以太网MAC帧（64B~1518B） [!TIP] 以太网==没有帧停止定界==，由于使用曼彻斯特编码，发送完一帧后出现电平不变现象，接收方视其为帧结束（类似违规编码思想） 高速以太网 速率 帧间间隔 通信方式 介质访问控制协议 100Mbps 9.6μs 全双工+半双工 CSMA/CD==（半双工）== 1Gbps 0.96μs（缩短信道长度到100M） 全双工+半双工 10Gbps 全双工 全双工不需要访问控制 无线网802.11 802.11帧有==4个地址== 有固定基础设施 基本服务集（BSS）：一个AP + 几个移动站 AP接入点基站： 服务及标识符SSID（WIFI名） 信道Channl 扩展服务集（ESS）：一个分配系统DS + 几个基本服务集BSS DS连接各BSS的基站AP 自组织网络：节点平等，所有节点都有路由功能 802.11帧 结构 地址字段分配 方向 地址1（接） 地址2（发） 地址3（末） 地址4 发送给AP设备 AP地址 源地址 目的地址 — 发送给终端设备 目的地址 AP地址 源地址 — VLAN服务802.1Q 划分方式 基于物理接口 基于MAC地址 基于IP地址 ！802.1Q帧 [!TIP] 比普通V2帧长度多4B，最大帧长1522B 添加后，需要重新计算FSC 结构： TPID：0X8100 PRI：优先级 VID：标识符，==12位== VII.广域网 PPP协议 用户与ISP的通信协议 数据层面：不可靠、无序号和确认 控制层面：面向连接 只保证CRC检错实现无差错接收 面向==字节==、全双工 组成部分 链路控制协议LCP：配置测试链路连接，协商参数 网络控制协议NCP：对接兼容多种网络层协议 组帧方法（规范） ！PPP帧 结构 首尾标志字段F：0X7E，定界符（与V2帧相比，有尾定界符） 同步传输：零比特填充法，防止0x7E（01111110）在内部出现 异步传输：转义字符0x7D 地址字符A：0xFF，无用 控制字符C：0x03，无用 协议字符P：0x0021->IP数据报；0xC021->LCP数据 数据载荷：0~1500B（不用CSMA/CD，无需最小帧长） 帧检验FCS：CRC检验冗余码 连接过程 flowchart TD A[链路静止] --> |物理层链路建立| B[链路建立] B --> |LCP协商失败|A B --> |LCP配置协商|C[鉴别] C --> |鉴别失败|D[链路终止] D --> |LCP链路终止|A C --> |鉴别成功|E[网络层协议] E --> |NCP配置协商|F[链路打开] F --> |链路故障或终止|D 无连接 -> 物理链路 -> LCP链路（控制）-> NCP链路（数据） 第四章 网络层 I.网络层功能 屏蔽了各种局域网的异构细节，如链路层协议、网络层协议（IPv4和IPv6） 路由转发 路由选择 分组转发 服务方式 虚电路 面向连接 保证可靠性 设虚电路号码VCID 建立连接时：分组首部使用完整地址 后续：只使用VCID 工作流程 虚电路建立 A：呼叫请求 -> B B：呼叫应答 -> A 数据传输 A：数据 -> B B：ACK -> A 虚电路拆除 A：释放请求 -> B B：释放应答 -> A 分类 永久性虚电路（PVC） 交换型虚电路（SVC）：临时 数据报 无连接、不可靠 SDN网络 架构 数据平面：终端设备 + 路由器（感觉已经算是交换机了） 控制平面：远程控制服务器计算路由 接口 南向接口：转发设备（路由器）与控制服务器建立连接的接口，如Overflow协议 北向接口：给上层开发者设计应用 东西接口：SDN控制服务器之间的接口 拥塞控制 判断方式：负载增加，吞吐量降低 开环控制 静态，设计时预计所有情况 闭环控制 动态，运行时对反馈的拥塞情况进行调整 闭环：即运行时有反馈环 II.IPv4 IPv4地址 4B = 32bit 分类编址 主机号全0：网络地址标识 主机号全1：广播地址 划分规则： 特殊地址： 划分子网编址 分类编址 + 子网掩码，使部分主机号作为网络号，划分出多个子网 范围：主机号全0、全1无法使用 路由表变化：目的网络地址 + 子网掩码 + 下一跳地址 无分类编址CIDR 去除ABC分类编址的思想，只使用掩码标识网络号长度 从ISP分到网络号后，仍然能自定义掩码长度来划分子网 V4首部格式 段名 长度 作用 版本 4b 协议版本为4 首部长度 4b 单位为4B，长度范围20B~60B，数值范围0101~1111 区分服务 8b 区分类别和优先级，很少使用 总长度 16b 单位为1B，首部长度 + 数据载荷长度 标识 16b 分片后通过同一标识合并 标志 3b MF：1表示后面还有分片，0表示没有；DF：1表示允许分片，0表示不允许 片偏移 13b 单位为8B，数值×8代表本段第一个字节在原数据载荷中的位置 生存时间 8b TTL，每转发一次跳数减1 协议 6b 表示数据载荷协议类型（如TCP、UDP等） 首部校验和 16b 用于检测首部差错 计算分片 片偏移计算（8B整数） 生存时间判断 优化技术 NAT：路由器构建NAT表，将外网地址+端口和内网地址+端口进行映射 NAT路由要看到传输层的端口号 转发时会改变源或者目的IP地址 路由聚合：路由器对需要聚合的网络寻找最长前缀，并和变长掩码一起存入路由表 特殊路由： 特定主机路由：*.*.*.*/32，定位到单个主机 默认路由：0.0.0.0/0，路由表无其他项则走默认路由 ARP 地址解析协议 网络层/数据链路层，自生成报文 每个主机、路由都有ARP表 已知IP地址，需要询问MAC地址 动态维护，一般2min更新 ARP请求报文 主机A发送广播，目的MAC地址为全1 目的主机B收到后，自身ARP表记录A的源IP和源MAC ARP响应报文 主机B单播回应 内容为自身MAC地址 主机A更新ARP表 DHCP 协议 ICMP 网际控制协议 IP报文 网络层数据报转发时状态信息交互 ICMP差错报告报文 终点不可达：路由器/主机==不能交付报文==时向源发送 源点抑制：路由器/主机因为==拥塞==丢弃报文时向源发送 超时：路由器收到TTL==为0==的报文时向源发送，若收不到全部分片则全部丢弃 参数问题：路由器/主机收到==首部字段校验和错误==时丢弃报文，并向源发送 改变路由（重定向）：路由器向源发送，告知源有更好的路由 不发送ICMP差错报告的情况 ICMP差错报告报文，不发送ICMP差错报告 特殊地址不发（广播、回环） 多分片报文只发送一次，后续分片不发 ICMP询问报文 回送请求和应答：PING（应用层） 时间戳请求和应答：Traceroute（网络层） 地址掩码请求和应答 路由器请求和通告 III.IPv6 128b = 16B 基本首部长度固定，选项通过扩展首部实现，扩展首部算在有效载荷内 不能分片，只能由源端分片，目的端合并 中间路由接收到太长的数据报会丢弃报文，并发送ICMP差错报告 V6首部格式 段名 长度 作用 版本 4 内容6 通信量类 8 区分类别和优先级 流标号 20 类似于v4首部标识，同一个“流”内流标号相同 有效载荷长度 16 单位1B，除基础首部的字段长度（包含扩展首部），最大65535 下一个部首 8 无扩展首部时：数据载荷协议类型（TCP/UDP）有扩展首部时：第一个扩展首部类型 跳数限制 8 TTL，路由器转发-1，0则丢弃 V6地址 表示方法 冒号十六进制：每4个十六进制数（2Byte）之间用冒号隔开 左侧0省略：两个冒号间的十六进制数中最前面的一串0可以省略不写；冒号间全为0，可省略只写一个 连续0压缩：多个连续0，可只填俩个冒号，==只能出现一次==，多个则无法定位 可结合点分十进制后缀 地址类型 未指明地址：0:0:0:0:0:0:0:0，::/128，只能作为源地址 回环地址：0:0:0:0:0:0:0:1，::1/128，只有一个 多播地址：FF00::/8，用于多播通信 本地链路地址：FE80::/10，私有地址，只能在本地链路使用 全球单播地址：除了以上，其他都是 全球路由前缀 子网标识 接口标识 48b 16b 64b [!TIP] 由于接口标识可对MAC地址进行编码，所以可以通过IPv6地址直接找到MAC地址，==省去ARP协议== V4和V6地址转换 双栈：同时支持V4和V6 隧道：V4数据报封装在V6数据报中 NAT64：V6数据报封装在V4数据报中 IV.路由协议 RIP协议 应用层，UDP封装 基于距离向量 路由器到直连网络的距离定义为1 只和==相邻==路由器交换自己的路由表 周期30s交换更新路由表，180秒无报文则此路由失效 收敛：每个路由器都知道到达本自治系统AS内各网络的最短距离和下一跳路由器 计算流程： A向相邻的B发送路由表a B将a中所有距离条目加上与A的距离，下一跳改为A 和自身路由表进行比较，选最短的 存在问题：网络N1突然失效，相邻路由器更新成16不可达之后，被相邻其他无法获取到N1状态的路由器路由表影响，16不可达被覆盖为可达。直到多次后才能确认不可达。 OSPF协议 网络层，IP数据报 基于链路状态（量化为代价） 支持CIDR 有鉴别，保证安全 链路状态有32位序号，越大越新 代价计算 cost = 100Mbps/链路带宽 cost大于1则保留整数，小于1则记为1 链路状态表：相邻路由 + 代价 区域划分：为适配大规模网络，OSPF将一个自治系统AS再划分为多个==区域==，限制洪泛范围，减少通信量，但OSPF更复杂了 ==主干==区域连接若干区域 主干路由器：主干区域内的路由器，包含边缘 区域内路由器：只在区域内，不连接主干路由器 区域边界路由器：属于主干路由器，与其他区域连接 链路建立和维护 问候（hello） 建立邻居表 发送周期10s，若40s未收到某方hello则视为其已经不可达 链路状态更新分组（LSU） 链路状态通告（LSA）：直连网络 + 邻居路由器的链路状态信息 ==可靠==的洪泛发送 可靠：需要收到的路由器发送==链路状态确认==报文 洪泛：向所有相邻路由器发送，它们收到后继续转发给相邻 链路状态数据库（LSDB） 每一个路由器都存储，记录链路状态通告（LSA） 通过洪泛使得网络中所有LSDB一致 报文类型 基本工作流程 BGP协议 EGP：与RIP、OSPF内部网关协议（IGP）相对的外部网关协议 连接多个AS的协议 非选择最佳，只求能比较好的到达 基本概念 各AS选择某个路由器作为BGP发言人 BGP发言人运行BGP + AS内部网关协议 目的：构造出AS间不存在环路的树形结构连通图 路径向量：（AS1，AS2） 报文 V.IP多播 基本概念 一对多 多端口转发 IPv4中使用D类多播地址：1110****.*.*.* ==224==.0.0.0 ~ ==239==.255.255.255 一个D类地址代表一个多播组 ！局域网硬件多播 解决本地局域网内多播数据包分发问题 IPv4地址映射多播MAC地址 多播MAC号：前25比特相同，01：00：5E：0 ：··· 后23位来自多播IP地址后23位 由于D类前4位为1110，后23位映射到多播MAC，有32-4-23=5位没映射到MAC地址上，使得一个MAC地址对应2^{5}=32个IP上 在网络层还需要过滤非目的IP的报文（IP和MAC双匹配） 因特网多播 解决多播组设备寻址问题 IGMP 多播路由器运行IGMP，监视本局域网内多播组成员变化 路由器不知道多播组成员数量和网络分布情况 IGMP报文类型 成员报告报文：设备->多播路由器，加入 成员查询报文：多播路由器->设备，是否存活 离开组报文：设备->多播路由器，直接退出 多播路由选择协议 目标：为每个多播组建立多播转发树，使报文只转发一次 IP多播组沿多播转发树洪泛，能传到所有拥有多播成员的多播路由器 多播路由器再进行硬件多播 VI.移动IP 原因：移动设备在某个网络下获得了IP地址 设备在移动状态下需要在不同网域下使用网络 正在提供服务的服务器也需要定位到此设备，移动设备IP不能改变 解决方法：代理 设备在归属地获得永久（归属）地址，上级路由称为归属代理 设备移动到其他网络下 设备使用代理发现协议，在外地网络注册，并提供永久地址和归属代理地址 外地代理通过以上信息与归属地代理建立IP隧道 归属地代理==接收==到数据后，转发给外地代理，外地代理转发给移动设备 移动主机==发送==数据时，交给外地代理直接转发，不需要送给归属代理 第五章 传输层 I.概述 物理层+数据链路层+网络层 -> 主机到主机通信 传输层 -> 进程到进程通信 端口号 区分计算机类进程的数据报文 同设备内一个端口只能建立一个连接 长度：2B 范围：0 ~ 65535（2^{16}-1） 分类 熟知端口：0~1023 登记端口：1024~49151 临时端口：49152~65535 复用分用 复用 TCP/UDP 复用：理解为应用报文打包 IP复用：传输层报文打包为IP报文 分用：理解为解包并分流到各自应用进程 II.UDP 无连接不可靠，不使用流量控制和拥塞控制 检查到错包就丢弃 支持广播、多播、单播 伪首部序号为17 UDP首部 源端口 目的端口 长度 校验和 2B 2B 2B 2B 源端口：可选，不需要时全0 目的端口： 长度：首部+数据，最小8（首部长度） 校验和：需要加上12B伪首部 III.TCP 面向连接 可靠 对==报文段==进行确认 面向字节流 伪首部中序号为6 TCP首部 序号：32b，代表本报文段第一个字节序号 确认号：32b，指出期望收到对方下一个TCP报文段的数据载荷的第一个字节的序号 数据偏移：4b，数据报长度，单位4B 保留：6b，无用置0 短状态：1有效 URG：紧急报文，首先传送 ACK：为1则确认字段有效 PSH：尽快交付，不保留在缓冲区 RST：复位，释放连接再重新连接 SYN 连接请求报文：SYN=1，ACK=0 连接确认报文：SYN=1，ACK=1 FIN：终止位，代表要求释放连接 窗口：16b，代表接收方所允许的对方发送的数据量（rnwd) 校验和：12b，伪首部+首部+数据载荷计算反码算数运算求和 紧急指针：16b，URG=1时才有效，指明紧急数据的长度，单位1B 建立连接 三次挥手 第一次：SYN=1,ACK=0，==SYN占用一个序号== 第二次：SYN=1,ACK=1，==SYN占用一个序号== 第三次：ACK=1，可带可不带数据，不带数据则不占用序号 [!TIP] 采用“三报文握手”而不是“两报文握手”来建立TCP连接，是为了防止已失效的TCP连接请求报文段突然又传送到了TCP服务器进程，因而导致错误。 左边： CLOSED SYN-SENT ESTABLISHED 右边： CLOSED LISTEN SYN-RCVD ESTABLISHED 四次挥手 第一次：FIN=1,ACK=1，==FIN占用一个序号== 第二次：ACK=1，继续传送数据 第三次：FIN=1,ACK=1，数据传送完，使用FIN表示准备断开 第四次：ACK=1，对方收到后断开，己方等待2MSL [!TIP] 等待2MSL是防止第四次丢失，导致对面无法关闭 左边： ESTABLISHED FIN-WAIT1 FIN-WAIT2 TIME-WAIT CLOSED 右边： ESTABLISHED CLOSE-WAIT LAST-ACK CLOSED 流量控制 接收窗口（rwnd)：发送方维持，代表缓冲区能接受的容量 实现端到端的流量控制（两个进程直接），数据链路层是节点之间的流量控制 滑动窗口+持续计时器 拥塞控制 种类 开环控制：初始即设计好一切情况 闭环控制：引入反馈，边监测边调整 拥塞窗口（cwnd)：发送方的窗口大小 发送上限 = min[cwnd, rwnd] 慢开始 拥塞窗口cwnd从1开始，每经过一次确认（时隔1TTL）后乘2 慢开始门限（ssthresh)：到达限制后cwnd进入拥塞避免 拥塞避免 cwnd到达ssthresh后，每次加一 直到发生超时（拥塞）或者收到三次确认报文，进入下一种调整模式 快重传 报文丢失（非拥塞状态） 接受方发送三次确认报文冗余ACK 发送方立即重传对方所需报文段 快恢复 收到==三次确认报文==后进行 ssthresh调为当前cwnd一半 cwnd调为当前一半 进入拥塞避免 第六章 应用层 I.网络应用模型 C/S模型 服务器：总是打开，提供服务，面向任务 客户机：请求服务，面向用户 特点： 体系内计算机地位不平等 客户机间不直接通信 可扩展性不佳 P2P模型 对等方（Peer）：任意一对计算机，直接相互通信 可扩展性好 网络健壮性好 II.动态主机配置协议（DHCP） 动态分配地址 基于UDP，主机端口68，服务器67 ！工作流程 客户端加入：客户端广播DHCP发现，源地址全0，目的地址全1 服务器接手：DHCP服务器收到后，广播DHCP提供，源地址服务器地址，目的地址全1 客户端接受此服务器，广播DHCP请求，源地址全0，目的地址全1 服务器广播DHCP确认，分配IP地址，源地址服务器地址，目的地址全1 报文 种类 目的 源IP 目的IP DHCP发现 客户端寻找DHCP服务器 0.0.0.0 255.255.255.255 DHCP提供 DHCP服务器确认给此客户端提供服务 服务器地址 255.255.255.255 DHCP请求 客户端要求分配IP 0.0.0.0 255.255.255.255 DHCP确认 服务器分配IP 服务器地址 255.255.255.255 III.域名系统（DNS） 命名系统，方便记忆 基于UDP协议，53号端口 域名服务器 根域名服务器：被所有本地域名服务器所知 顶级域名服务器：com、cn、site等 权限域名服务器 本地域名服务器 解析过程 递归查询 本地主机向本地域名服务器查询 本地域名服务器向根域名服务器查询 根域名服务器向顶级域名服务器查询 ··· 主机->本地->==根域名==->顶级域名->权限域名 根域名负载大 ，基本不用 主机和本地域名服务器之间只使用递归查询 迭代查询 本地主机向本地域名服务器查询 本地域名服务器： 向根域名服务器查询 向顶级域名服务器查询 向权限域名服务器查询 本地域名服务器向主机返回结果 IV.文件传输系统（FTP） 交互式访问，允许用户指明==文件类型和格式== 控制连接：端口21，TCP 数据连接：端口20，TCP 会话过程，服务器保留用户状态信息，追踪用户在远程目录树位置 控制连接 传输控制信息 会话期间保持打开 数据连接 接收到文件传输请求后，创建数据传送进程和数据连接 传送完毕后关闭 模式 主动模式PORT：客户端发送PORT命令和==客户端随机开放端口号x==，服务器通过20与x连接 被动模式PASV：客户端发送PASV命令，==服务器在本地开放随机端口y==，告知客户端 选择权都在客户端上 网络文件系统NFS FTP：修改服务器上文件，先==全部==下载到本地，修改完再传回 NFS：远程打开文件，在文件特定位置读写修改 V.电子邮件（Email） 组成结构 用户代理UA：程序，如QQ邮箱、Outlook软件 邮件服务器：用于发送、接收邮件 邮件发送和读取协议：存取协议 现状：用户通过浏览器使用HTTP协议发送邮件，SMTP只在服务器之间 邮件格式和MIME 格式 信封：从内容自动提取目的人和标题 内容 首部 FROM To Subject 主体内容 MIME 由于SMTP只能传输7位ASCII码文件，需要MIME进行内容扩展，可以讲图片音视频等转换为7位ASCII，并读取恢复 ！发送协议IMAP SMTP==服务器==端口号：25 连接建立 发送方SMTP服务器（客户端）与接收方SMTP服务器建立TCP连接 接收方服务器发出220服务就绪 客户端发送HELLO+客户端主机名 接收方发送250 OK 邮件发送 客户端发送MAIL FROM+主机名 接收方服务器准备好则发送250 OK 客户端发送RCPT TO+收件人地址 接收方服务器准备好则发送250 OK 客户端发送DATA命令 接收方服务器准备好则发送250 OK 客户端发邮件内容，.代表结束 接收方服务器准备好则发送250 OK 客户端发送QUIT 接受方服务器发送221，==主动断开== 接收协议POP3和IMAP POP3 TCP，端口110 工作方式 下载并保留：主机下载完邮件保留在SMTP服务器上 下载并删除：主机下载完邮件删除SMTP服务器的文件 IMAP 允许用户创建文件夹，并移动位置 允许用户只获取邮件部分报文 VI.万维网WWW URL 统一资源定位符 <协议>://<域名（或IP）>:<端口>/<路径> [!TIP] 当浏览器输入URL开始访问(无缓存）： 主机向本地域名服务器发出DNS查询 本地域名服务器 向根域名服务器查询 向顶级域名服务器查询 向权限域名服务器查询 本地域名服务器将结果IP返回主机 主机发起TCP连接请求，三次握手后建立连接 主机发出HTTP请求 服务器处理请求，返回HTTP报文 主机收到报文后进行处理 传输结束，四次挥手结束TCP连接 HTTP 无连接，TCP确保可靠连接 无状态，引入Cookie后实现了有状态 Cookie 网站服务器为用户生成Cookie识别码，在服务器中存储用户信息 网站服务器发送给用户的响应报文中有"Set cookie: ****" 用户在自己的Cookie文件中存储此信息 用户下次访问时，在请求报文中添加Cookie值 服务器识别后提供个性化服务 非持续连接 HTTP1.0：==每个元素==传输都建立一次TCP连接，*2TTL开销** 持续连接 HTTP1.1：建立一次TCP连接后保持，主机发出请求，服务器发送文件 非流水线：一次请求，一个文件 流水线：可连续发送请求（可视为一次），服务器连续发送多个文件 [!WARNING] ！发送大文件时，需要注意TCP窗口大小（遵循慢启动） 报文结构 请求报文 方法+URL+版本：GET xidian.edu.cn HTTP1.1 首部字段名+值：Keep Alive：1 响应报文 版本+状态码+短语：HTTP1.1 202 Accepted
第一讲 引言 网络安全核心地位的关键目标 保密性（Confidentiality） 数据保密性 隐私性 完整性（Integrity）(包括不可否认性、真实性) 数据完整性 系统完整性 可用性（Availability） 真实性（Authenticity） 可追溯性（Accountability） 安全攻击 被动攻击 在未经用户同意和认可的情况下将信息或数据文件泄露给系统攻击者，但对数据信息不做任何修改 常见手段 搭线监听 无线截获 其他截获 应对措施：重点在于预防 主动攻击 涉及某些数据流的篡改或虚假流的产生 分类 阻断攻击 伪造攻击 重放攻击 篡改攻击 拒绝服务攻击 应对措施 自动审计 入侵检测 完整性恢复 安全机制 安全机制要具备检测、防御或从安全攻击中恢复的能力，没有单一的机制能够提供所有的安全服务 特定的安全机制（specific security mechanisms） 加密， 数字签名， 访问控制，数据完整性，认证交换，流量填充，路由控制，公证等 普遍的安全机制（pervasive security mechanisms） 可信功能，安全标签，事件检测，安全审计跟踪，安全恢复 安全服务 可认证性 Authentication 访问控制 Access Control 机密性 Confidentiality 完整性 Integrity 不可否认性 Non-repudiation 可用性 Availability 第二讲 传统加密技术 密码学 密码编码学 研究内容：主要研究对信息进行编码，实现对信息的隐蔽 特征 密码编码学常用运算：代替与置换 所用的密钥数：单钥与双钥 处理明文的方法：分组密码与流密码 密码分析学 研究内容：主要研究如何破解密文的方法 攻击的两种常用方法 密码分析学： cryptanalytic attack 穷举攻击： brute-force attack 保护密码算法还是密钥 与维护算法的保密性相比，维护密钥的保密性更容易。 万一密钥暴露了，Alice 和 Bob 可以很容易地更换密钥；而万一算法被攻破，重新设计一个很好的加密算法要难得多。 万一有多对人员需要加密其通信，这些人可以使用相同的算法和不同的密钥，而使用不同的程序则太难。 加密算法 凯撒密码：共有密钥25个、移位、替换 单表代替密码：任意地打乱字母的顺序，密钥数目： 26！＞ 4 × 10^{26} playfair 密码：多字母代替密码，密钥空间：25！≈1.6×10^{25} Hill 密码 加密：C≡KP mod 26，其中，K为密钥矩阵，P、C分别为明、密文分组 解密：P≡K^{-1}C mod 26 维吉尼亚密码 置换密码 第三讲 分组密码与 DES Feistel 密码结构 混淆和扩散 混淆：使得密文的统计特性与密钥的取值之间的关系尽量复杂 扩散：明文的统计特征消散在密文中，使得明文和密文之间的统计关系尽量复杂 DES 加解密 两次置换（初始置换和初始逆置换） 密钥控制下的十六轮迭代加密 轮密钥生成 DES 是一种用 56 位密钥来加密 64 位数据的方法 雪崩效应 明文或者密钥的某一位发生变化，会导致密文很多位的变化 第四讲 代数基础 模运算性质 对称 传递 计算2^{64} mod 2012 \begin{flalign*} &2^2 =4 mod 2012\\ &2^4 =16 mod 2012\\ &2^8 =256 mod 2012\\ &2^{16}=65536 ≡1152 mod 2012\\ &2^{32}=1152^2 ≡1196 mod 2012\\ &2^{64}=1196^2 ≡1896 mod 2012& \end{flalign*} 欧几里得算法（辗转相除法） 求gcd(1970, 1066) \begin{flalign*} &令a=1970，b=1066\\ &1970=1×1066+904\\ &1066=1×904+162\\ &904=5×162+94 \\ &…… …… \\ &10=1×6+4\\ &6=1×4+2\\ &4=2×2\\ &因此gcd(1970, 1066)=2 & \end{flalign*} 求乘法逆元 已知28与81互素，求81 mod 28的逆元。 \begin{flalign*} &81=2×28+25\\ &28=1×25+3\\ &25=8×3+1\\ \\ &1=25-8×3\\ & =25-8×(28-25)\\ & =(-8)×28+9×(81-2×28)\\ & =9×81+(-26)×28\\ &所以81×9≡1 mod 28，同时 28×（－26）≡1 mod 81, 81 mod 28的逆元为9\\ &而28 mod 81的逆元为－26≡55& \end{flalign*} 群环域基本概念 群：群是定义了一个二元运算“•”的集合G，表示为(G，•)$，并且满足以下公理： 封闭性 结合律 单位元 逆元 环：设R是至少含有两个元素的集合，R中定义了两种运算“+”和“•”，如果代数系统<R,+, • >满足以下公理，则称其为环 R关于加法构成交换群 R关于乘法构成半群，即乘法满足封闭性和结合律 分配律 域：设F是至少含有两个元素的集合，F中定义了两种运算“+”和“•”，如果代数系统<F,+, • >满足以下公理，则称其为域 F是一个整环 有乘法逆元：对于任意a ∈F，存在a-1∈F，使得a • a -1=a-1 • a=1成立 基于多项式的有限域构造及运算 密码学中为什么用 GF(2^m) 第五讲 AES 加密 AES 加解密过程 字节代替 行移位 列混合 轮密钥加 轮函数四步：字节代替、行移位、列混合、轮密钥加（注：最后一轮无列混合） AES 密钥生成过程 第六讲A 分组密码工作模式 2DES 加密：C = EK2(EK1(P)) 解密：P = DK1(DK2(P)) 双重 DES 为什么不行？（中间相遇攻击） 中间相遇攻击是一种针对双重加密算法的攻击，需要一个已知的明、密文对，本质上，明文在双重加密中被加密产生中间值，密文在双重加密中被解密产生中间值，表查找方式可以用这种方法改进对密钥的蛮力尝试。 已知明文攻击可以成功对付密钥长度为 112 位的 2DES C = E_{K2}(E_{K1}(P)), X = E_{K1}(P) = D_{K2}(C) 用所有可能的密钥加密明文并存储 用所有可能的密钥解密密文，并与存储的X匹配。如果有相等的，那么获得一组可能的密钥对，并用新的明密文对验证。 概率分析：2^{112}/2^{64}=2^{48}，2^{48}/2^{64}=2^{-16}，两组明密文对后，正确密钥的概率是1-2^{-16}；三组明密对后，正确密钥的概率是1-2^{-80} 付出数量级为 O(256),比攻击单DES的O(255)多不了多 为什么需要分组密码工作模式 如果待加密的消息过长，需要将消息分组后，一组一组的使用加密算法，然后输出密文。在这一过程存在两个问题： 分组密码不能隐蔽数据模式，即相同的明文分组对应着相同的密文分组，容易受到攻击 分组加密不能抵抗重放、插入和删除攻击等。把分组密码算法用在不同环境时，环境不同要求也不同。 为了满足不同要求，需要通过改变分组密码输入和输出的形式，得到分组密码的不同工作模式。 五种工作模式的具体构造及特点 模式 特点 典型应用 电码本 ECB 用相同的密钥分别对明文组加密 单个数据的安全传输 密文分组链接 CBC 有 IV 加密算法的输入是上一个密文组合下一个明文组的异或 加密长度大于 64 位明文 P、认证 密文反馈 CFB 有 IV 分组任意，安全性优于 ECB 模式加、解密都使用加密运算（不用解密运算） 加密长度大于 64 位的明文，分组随意；可作为流密码使用、认证 输出反馈 OFB 有 IV 抗消息流篡改攻击的能力不如 CFB 噪声信道上的数据流的传输,比如卫星通信 计数器 CTR 有 IV 硬(软)件效率：并行、预处理、随机访问、可证明的安全性、简单性：只用到加密算法 分组传输，高速需求的应用 第六讲B 随机数与流密码 随机数基本概念 （随机数在密码学中的）应用 临时交互号，用于防止重复攻击 会话密钥产生 RSA算法中密钥的产生 （对随机数产生的）要求 随机性和不可预测性 基于密码学的随机数生成 循环加密：设E为加密算法，C为计数器，预置其初值为0，K_m为保密的主密钥，每加密一次，产生一个随机数，同时计数器的值加1 用DES的输出反馈方式产生 流密码的基本原理 消息的处理以字节为单位以流的方式进行 伪随机密钥流 keystream 密钥流与明文进行按位的异或运算 (XOR) 密钥的随机性破坏明文中的统计规律 C_i = M_i \ \ XOR \ \ StreamKey_i 不能重复使用密钥流，否则将被破译 第七讲 数论基础 素数基本概念 费马小定理、欧拉定理、素性检测概率算法 离散对数的基本概念 第八讲 公钥密码学与RSA 对称密码弱点 密钥量大 密钥管理困难：传递、换发、保存 无法实现网络中的数字签名、消息认证、用户认证等应用 系统中有 n 个用户，两两进行保密通信： 每个用户需要有 n-1 个密钥 总密钥数C(n,2) = n(n-1)/2 Shamir 盒及公钥密码基本原理 Shamir 盒模型的两点启示： 不事先交换密钥就能进行秘密通信 加密、解密的密钥可以分开 公钥密码基本原理： 使用两个不同的密钥，一个用于加密，一个用于解密 用于加密的密钥 E_k 可以公开，用于解密的密钥D_k 保密 E_k 与 D_k 之间有联系，但不能由 E_k很容易地算出 D_k RSA 公钥密码基本原理及计算 RSA算法密钥的建立 选择素数：p = 17 \& q = 11，计算n = p q =17 x 11 = 187 计算 ø(n) = (p–1)(q-1) = 16 * 10 = 160 选择 e: gcd(e, 160) = 1; 选择 e = 7 确定 d: d*e = 1 mod 160 且 d < 160 d = 23 因为 23 *7=161= 10 * 160+1 公钥 PU = { 7, 187 }，私钥 PR = { 23, 187 } 明文消息：m = 88 (<187) 加密：c = 887 mod 187 ≡ 11 解密：m = 1123 mod 187 ≡ 88 第九讲 其他公钥密码体制 (重点)Diffie-Hellman 密钥交换 中间人攻击 Darth生成两个随机数X_{D1}和X_{D2}，随后计算相应的公钥Y_{D1}和Y_{D2}; Alice将Y_A传递给Bob; Darth截获了Y_A，将Y_{D1}传给Bob，同时计算 K_{2}=\left(Y_{A}\right)^{X_{D 2}} \bmod q Bob收到Y_{D1}，计算 K_{1}=\left(Y_{D1}\right)^{X_{B}} \bmod q Bob将Y_B传给Alice; Darth截获了Y_B，将Y_{D2}传给Alice，Darth计算 K_{1}=\left(Y_{B}\right)^{X_{D1}} \bmod q Alice收到Y_{D2}，计算 K_{2}=\left(Y_{D2}\right)^{X_{A}} \bmod q ElGamal 密码体制 困难问题：离散对数问题 特点：加密是概率算法—有随机数参与 加密过程 设m为明文，随机选择整数k，k与p-1互素，计算 c_1 ≡ g^k mod p c_2 ≡ my^k mod p 密文c=(c1, c2) 解密过程 收到密文c=(c1, c2)后，接收方进行如下计算 \begin{array}{l} c_{2} \cdot\left(c_{1}^{x}\right)^{-1}=m y^{k} \cdot\left(g^{k x}\right)^{-1} =m g^{k x}\left(g^{k x}\right)^{-1} \equiv m \bmod p \end{array} 第十讲 密码学Hash函数 Hash 函数的基本特性、基本设计框架 任意长度的明文进行变换得到相应的函数值，称为散列值(长度固定)。 用途：消息认证码、数字签名预处理、从口令衍生密钥等。 特性： 对任意长度输入进行变换，得到固定长度输出 求逆不可行 抗原像攻击/单向性 对给定 x，很难找到x’≠x，使得h(x’)=h(x) 抗弱碰撞性 很难找到一对不同的x, x’，使得 h(x’)=h(x) 抗强碰撞性 满足1-2为单向散列函数，1-3为弱散列函数，1-4 为强散列函数 CVL 为最终的哈希输出 生日攻击基本原理 攻击者产生一份合法的明文，再产生232个不同的明文变形，构成一个合法明文组； 生成一份非法明文，构造232个不同的非法明文变形，产生一个非法明文组； 分别对以上两个组产生散列值，在两组明文中找出具有相同散列值的一对明文。如果没有找到，则再增加每组明文变形的数目，直至找到。由 “生日悖论”可知，其成功的概率很大； 于是，攻击者找到了一则与合法明文（至少内容合法）具有相同散列值的非法明文。 第十一讲 消息认证码 消息认证码如何设计？基于hash和基于密码的(大致思路) 基于密码 hash 函数的 MAC**：**HMAC 不用分组密码，而用 hash 函数来产生 MAC，因为 hash 函数一般都较快 没有出口限制，(分组密码有出口限制) hash 函数不依赖于密钥，所以不能直接用于 MAC 建议: KeyedHash = Hash( Key || Message ) 基于密码的：采用分组密码（DES）的链接工作（CBC 模式）模式，并把最后分组作为 MAC 看复习PPT，最好能直接画出框图 CMAC：基于密码的消息认证码，框架与 DAA 类似，加密用 AES 和 3DES 实现 第十二讲 数字签名 数字签名的基本特性和用途，如何构造 （私钥签名，公钥验证） 特性： 签名值必须依赖于所签的消息 必须使用对于发送者唯一的信息，以防止伪造和否认 产生签名比较容易 识别和验证签名比较容易 伪造数字签名在计算上是不可行的。包括已知数字签名，伪造新的消息和已知消息，伪造数字签名 保存数字签名的拷贝是可行的 第十三讲 密钥管理与分发 典型的基于对称加密的密钥分发方案（步骤） 公钥基础设施 公钥基础设施 (PKI) 系统是有硬件、软件、人、策略和程序构成的一整套体系 公钥基础设施实体： 端实体 签证机构 CA 注册机构 RA 证书撤销列表发布 CRL 证书存储库 公钥分发机制、X.509 证书、PKI 基本概念 第十四讲 用户认证 Needham-Schroeder 认证协议、Kerberos 基本原理及步骤、基于公钥的远程认证步骤 第十五讲 传输层安全 SSL 协议设计思路、SSL 握手协议过程以及其能对抗攻击的原因 SSL握手协议的具体交互过程 建立安全协商：交换 Hello 消息，对于算法、交换随机值等协商一致 服务器鉴别：交换必要的密码参数，以便双方得到统一的 premaster secret 客户端鉴别和密钥交换：交换证书和相应的密码信息，以便进行身份认证产生 master secret 结束：把安全参数提供给 SSL 记录层检验双方是否已经获得同样的安全参数 SSL的安全性 保护主密钥 保护服务器的私钥 使用良好的随机数 证书链检查 算法选择（强度） 第十六讲 IP安全 IPSec 基本原理、AH、ESP、传输模式、隧道模式、密钥管理基本思路 IPsec 优点 对应用和最终用户透明 在防火墙或路由器中实现时可以防止 IP 旁路 需要时 IPSec 可以提供个人安全性 弥补 IPv4 在协议设计时缺乏安全性考虑的不足 IPsec 两种模式：传输模式和隧道模式 传输模式为上层协议提供保护，用于两台主机间的端到端通信 隧道模式对整个 IP 数据包提供保护
一、 分布式计算概述 1. 分布式系统定义 分布式系统是由一组通过网络进行通信，为了完成共同的任务而协调工作的计算机节点组成的系统 1.1 消息传递模型（Shared-Nothing） 节点之间通过消息传递进行通信 内部运算速度快，但通信速度慢 1.2 分布式计算与并行计算 分布式计算是并行计算的一种特殊形式 并行计算 指令并行 CPU多核并行：多线程编程 多CPU并行（一致性内存共享）：多进程编程 多CPU并行（非一致性内存共享）：分布式计算 基于GPU的并行计算 多机并行计算 1.3 分布式与云计算 云计算 用户角度：是一种服务/应用/交付模式，方便用户随时随地通过网络访问应用程序、存储数据，不是一种技术 与分布式计算的关系 云计算是目标，分布式计算是手段 分布式计算是实现云计算的核心技术之一（还有虚拟化技术，网络通信技术，安全技术等） 2. 构建分布式系统的收益 提高计算能力 提高存储能力 提高网络吞吐能力 提高可靠性 提高可扩展性 提高安全性 实现资源共享 实现跨时空协同服务 3. 分布式系统衡量指标 业务层性能 时间复杂度 空间复杂度 通信复杂度 可扩展性：系统能够适应业务量的增长 容错性：系统在部分节点失效时，仍能正常工作 并发性：系统能同时处理多个请求 透明性：用户感知不到系统的分布式特性 开放性：节点可以动态加入或退出系统 安全性：系统能抵御各种攻击 可观测/可维护性：系统能够监控自身的运行状态，及时发现故障并修复 简记：扩容，容错，并发，透明，开放，安全，可观测 4. 设计分布式系统的挑战 与性能衡量指标 类似 5. 分布式计算任务的分类 5.1 OLTP（联机事务处理） 实时处理大量的短小的事务请求，每个事务请求的处理时间很短，通常是几毫秒到几秒钟 5.2 OLAP（联机分析处理） 对大量的历史数据进行分析，通常是对大量数据进行聚合计算，每个计算任务的处理时间很长，通常是几分钟到几小时 5.3 流式计算 对大量的实时数据进行分析，通常是对数据进行过滤、聚合、统计等操作，每个计算任务的处理时间很短，通常是几毫秒到几秒钟 6. 分布式系统架构模式 6.1 客户端-服务器模式 负载均衡技术 如何架构 通过DNS轮询 通过反向代理 通过负载均衡器 带来的收益 提高系统的可扩展性，弹性增减节点 提高系统的可靠性 提高系统的性能 常用的负载均衡算法及优劣 轮询：简单，均衡，但不考虑节点的负载情况 随机：简单，均衡，但不考虑节点的负载情况 最少连接：考虑节点的负载情况，但不考虑节点的性能 最少响应时间：考虑节点的负载情况，考虑节点的性能，但不考虑节点的可用性 哈希：考虑节点的负载情况，考虑节点的性能，考虑节点的可用性，但不支持动态增减节点 一致性哈希：考虑节点的负载情况，考虑节点的性能，考虑节点的可用性，支持动态增减节点 6.2 主从模式 主从模式的概念 主节点 负责处理客户端的请求，维护系统的状态 从节点 负责处理主节点分配的任务，不维护系统的状态 主从模式的优缺点 优点 提高系统的可扩展性 提高系统的可靠性 提高系统的性能 缺点 主节点成为瓶颈 从节点的状态不一致 6.3 总线模式 总线模式的概念 不同节点通过总线进行通信 消息发送与接受者解耦 异步 分工 6.4 对等模式 对等模式的概念 系统中的所有计算节点任务分工都是对等的 完全相同的软件在不同的节点上运行，只是初始化参数不同 对等模式的优缺点 优点 不会出现单点故障 无需维护系统的状态 缺点 效率低 7. 分布式中间件的概念 7.1 中间件在计算机系统中的位置 中间件是介于操作系统和应用程序之间的软件，它为应用程序提供服务，为操作系统提供接口 7.2 中间件的作用 为开发者提供高层的抽象接口 提高互操作性和可移植性 提供分布式系统的基础设施 7.3 中间件的基本表现形式 独立的后台进程 语言编译/解释器的一部分 函数库 二、分布式系统节点通信技术 1. 基于Socket的通信技术 1.1 Socket的概念 Socket是一种通信机制，它允许不同节点上的应用程序通过网络进行通信 是传输层和网络层提供给应用层的接口 1.2 基于流式Socket（TCP） 建立连接（三次握手） 客户端向服务器发送连接请求 服务器向客户端发送连接确认 客户端向服务器发送连接确认 发送请求 客户端向服务器发送请求 返回响应 服务器向客户端发送响应 关闭连接 1.3 基于数据报Socket（UDP） 发送请求 客户端向服务器发送请求 返回响应 服务器向客户端发送响应 与TCP的区别：没有建立连接的过程，不可靠，不保证数据的顺序 1.4 并发服务技术 多线程——线程池 优点：线程复用，减少线程创建和销毁的开销 多路复用（事件驱动技术） 优点：单线程，减少线程切换的开销，适用于并发连接数少，连接时间短，IO密集的场景 2. 远程过程调用RPC（上层通信技术） 凤凰架构 RPC是一种通信机制，它允许不同节点上的应用程序通过网络进行通信，它是Socket的高级封装，使应用程序可以像调用本地函数一样调用远程函数 2.1 RPC的基本原理 序列化/反序列化 序列化：将对象转换为字节序列 反序列化：将字节序列转换为对象 插桩/代理（stub/skeleton） 插桩：客户端调用本地函数，插桩将函数调用转换为网络消息 代理：服务器端接收网络消息，代理将网络消息转换为函数调用 实现RPC语义的应用层协议 负责远程对象的集中注册与管理 点对点通信的缺点 关系复杂，耦合度高 可扩展性差 2.2 RPC中间件的作用——注册中心的作用 服务启动时，将服务的地址注册到注册中心，客户端从注册中心获取服务地址，实现服务发现 优点： 动态增减节点，负载均衡，容错 2.3 接口描述语言IDL 作用：定义接口，实现语言无关，平台无关，网络协议无关 2.4 RPC调用模式 同步调用 客户端调用远程函数，等待远程函数返回结果 异步调用 客户端调用远程函数，不等待远程函数返回结果，继续执行后续操作 远程函数执行完毕后，通知客户端 3. 基于HTTP的通信技术 Web Service 优点：跨平台，跨语言，跨网络 缺点：效率低，不支持异步调用 RESTful 优点：效率高，支持异步调用 缺点：不支持跨语言，跨网络 4. 基于消息队列（MOM）中间件的通信技术 优势 异步通信，提高系统的并发性 解耦，提高系统的可扩展性 削峰填谷，提高系统的可靠性 通信模式 消息队列 一对一（一个队列，一个消费者） 一对多（一个队列，多个消费者） 发布/订阅 一对多，广播 投递模式 At Most Once 消息可能会丢失，但不会重复投递 At Least Once 消息不会丢失，但可能会重复投递 Exactly Once 消息不会丢失，不会重复投递 缓存模式 持久化 消息持久化到磁盘 非持久化 消息不持久化到磁盘 三、 模型问题 1. 设计分布式系统的挑战 1.1 不可靠的网络——信道故障 传输延迟的不确定性 网络断裂 丢包 乱序 1.2 不可靠的节点 部分节点失效 单点失效 1.3 不可靠的时钟 2.分布式系统的模型 2.1 节点故障模型 fail-stop模型 节点失效后，不会再次恢复 fail-stop-restart模型 节点失效后，会再次恢复 byzantine模型 节点失效后，会再次恢复，但是恢复后的节点可能会发生任意行为 2.2 链路模型 任意链路 丢包、重复包、内容篡改、伪造、乱序、传输延迟抖动 有主动攻击者存在的情况 一般损失链路 只存在丢包、重复包、乱序和传输延迟抖动 链路会发生断裂（Partition），但断裂持续时间是有限的 可靠链路 发送者发出的每个消息都可以被正确接收 但是： 存在传输延迟抖动 接收到消息的顺序可能和发送顺序不一致 可靠FIFO链路 发出的每个消息都可以被正确接收并且不会乱序 如何基于弱假设链路实现强假设链路 如何基于“任意链路” 实现“一般损失链路”？ 利用纠错码、HASH函数、消息认证码、加密算法等手段； 利用SSL/TLS/HTTPS协议 如何基于“一般损失链路” 实现“可靠链路”？ 发送者持续地尝试重传数据包，直到收到ACK； 利用数据包序列号等手段实现去除重复数据包 如何基于“可靠链路”实现“可靠FIFO链路”？ 利用数据包序列号，对收到的数据包进行排序，然后按序列号由小到大依次向应用层投递 2.3 时间同步模式 同步模式 消息传输延迟不超过已知的上限 节点以已知速度执行算法 异步模式 消息传输延迟没有上限 节点在运行期间可能会暂停任意长的时间 部分同步模式 系统大部分时间工作在同步模式； 但在有限时间段（该时间段长度不可预知）内工作在异步 模式； 四、 时钟问题 1. 物理时钟 1.1 单调钟的概念 按照一定频率持续自增； 其绝对值无意义，相对值表示延时或时间差； Java：System.nanoTime() 1.2 墙钟的概念 和日常生活中的日历、天文事件对应的时钟 世界墙钟标准：协调世界时（Coordinated Universal Time） 可能会发生倒流现象（NTP时钟校正、闰秒） System.currentTimeMillis() （1970-1-1 午夜 0点以来的秒数 1.3 NTP实现时钟同步的原理 Cristian算法 客户端发送请求包，以其本地时钟T_1为时间戳 服务器在收到请求T_2及其本地时钟 服务器发送一个带有其本地时钟T_3和T_2的包 客户端在本地对其接收服务器响应的时间戳T4T_4 目标：将时钟校正为 T_3 + ?_{resp} ?_{resp} = \frac{(T_2 - T_1) + (T_3 - T_4)}{2} 2. 逻辑时钟 2.1 Lamport时钟 Happen-Before关系 如果事件a和b是同一个节点（单进程/线程）中的两个事件,事件a发生在事件b之前，那么a \to b 如果a事件是 “节点P_1发送消息m到P_2”，b事件是“节点P_2接收消息m”，那么a \to b 如果a \to b且b \to c，那么a \to c(传递性) 如果a ↛ b且b ↛ a，那么a和b是并发事件 Lamport时钟 每个节点维护一个逻辑时钟，初始值为C_i 每个节点在执行一个事件生（消息产生、消息发送、消息接收都是事件）时，将逻辑时钟加1 每个节点在发送消息时，将逻辑时钟加1，并将当前逻辑时钟作为消息的时间戳 每个节点在接收消息时，将逻辑时钟更新为“当前逻辑时钟”和“消息时间戳”中较大的值加1 2.2 向量逻辑时钟 基本算法 设分布式系统包含 n 个节点N_1,N_2,...,N_n，节点N_i的向量时钟T形式为： T = (T_1,T_2,...,T_n) 其中T[i] = T_j表示节点N_i的逻辑时钟,T[j]表示N_i所知道的关于节点N_j的最大标量时钟值 向量时钟的更新 节点N_i在执行一个事件时，将自己的标量时钟自增； 节点N_i在发送消息时，将当前向量时钟T作为消息的时间戳； 当收到其它节点发送的消息<m,T_m>时，节点N_i将自己的向量时钟T更新为： T[j] = max(T[j],T_m[j]) T[i] = T[i] + 1 优缺点 优点 可以检测出因果关系 缺点 向量时钟的长度随节点数目增加而增加，不适合大规模系统 2.3 向量时钟的应用 全序广播 因果排序广播 五、 分布式存储 1. 复制（多副本）技术 1.1 多副本复制带来的收益和挑战 收益 提供冗余 应对节点失效 提高吞吐率 改善访问性能 挑战 硬件成本 保持一致性困难 1.2 主从技术复制 单主复制 一个领导者，多个从属者 优点：简单 缺点：主节点成为瓶颈 同步复制: 领导者将每个写操作发送给所有从属者，直到所有从属者都确认写操作后，领导者才能确认写操作 异步复制： 领导者将每个写操作发送给所有从属者，但不等待从属者确认写操作，而是立即确认写操作 链式复制： 从属者将写操作发送给其他从属者，而不是领导者，形成一个链式结构 混合复制： 部分从属者采用同步复制，部分从属者采用异步复制 多主复制 无主复制 2. 分布式系统一致性模型 2.1 一致性模型的概念 多个客户端同时访问分布式系统，系统应该保证客户端看到的数据是一致的 2.2 强一致性（线性一致性） 分布式系统对外提供的服务，与单机系统对外提供的服务一致，即客户端看到的对系统的操作是与物理世界真实发生的顺序一致的 2.3 最终一致性和弱一致性 最终一致性 系统保证在没有新的更新操作时，系统最终会达到一致状态 适用于读操作远远多于写操作的场景 弱一致性 系统不保证在没有新的更新操作时，系统最终会达到一致状态 适用于读操作远远多于写操作的场景 2.4 CAP定理 CAP定理指出，对于一个分布式系统来说，不可能同时满足以下三点,最多只能同时满足两点 一致性（Consistency） 所有节点在同一时间具有相同的数据 可用性（Availability） 保证每个请求不管成功或者失败都有响应 割舍分区容错性（Partition tolerance） 系统中任意信息的丢失或失败不会影响系统的继续运作 3. 分布式共识协议 3.1 共识协议的作用 利用共识协议，分布式系统可以在不同节点之间达成一致，从而保证分布式系统的一致性 多副本主从复制 异步通信 容错 3.2 复制状态机的概念 状态机 状态机是一个抽象的数学模型，它包含一组状态和一组操作，每个操作都将状态从一个状态转换为另一个状态 目标：让所有节点的状态机保持一致 用处：某节点的状态机失效，可立即切换到另一个节点的状态机 实现： 每个节点维护一个日志，日志中记录了所有状态机执行的操作 利用共识协议，让所有节点的日志保持一致 3.3 共识协议和分布式一致性的关系 共识协议是分布式一致性的基础 一致性是对用户的承诺 共识协议是实现一致性的手段 3.4 按容错模型分类 失效停止模式共识协议 最多允许f = (n-1)/2个节点失效 Paxos Raft 过程： Leader接收客户端请求，存入日志 将新增日志复制给其他节点 确认日志复制成功，提交日志，执行日志中的命令 Leader选举过程： Leader失效 Follower发现Leader失效，发起选举 超过半数节点投票给某个Follower，该Follower成为新的Leader 修改朝代号，通知其他节点 Zab 拜占庭模式共识协议 原理：通过多数派原则，保证系统的一致性 PBFT VFT 4. 分区（分片）技术 4.1 分区带来的收益和挑战 收益 提高系统的可扩展性 提高系统的可靠性 提高系统的性能 挑战 数据分布不均匀 跨分区查询 事务处理 4.2 分区技术的分类 按主键范围分区 将主键的值按范围划分到不同的分区 均匀分区 将主键的值按范围均匀划分到不同的分区 优点：容易实现点查询，范围查询，排序等操作 缺点：不适合数据分布不均匀的场景 不均匀分区 将主键的值按范围不均匀划分到不同的分区 优点：可处理数据偏斜，热点查询 缺点：需要全局索引，导致查询多了一次网络开销 哈希分区 确定性，随机性，无碰撞性 简单哈希分区 将主键的值通过哈希函数计算，得到哈希值，再通过哈希值对分区数取模，得到分区号 一致性哈希分区 将主键的值通过哈希函数计算，得到哈希值，再通过哈希值对分区数取模，得到分区号 优点： 可处理数据分布不均匀，热点查询； 不用全局索引，减少网络开销 不用事先知道数据分布情况 缺点： 效率低，需要多次哈希计算 在分区数变化时，数据迁移量大 物理储存少时容易出现偏斜和热点问题 4.3 分区技术带来的挑战 分布式事务概念(ACID) 原子性（Atomicity） 事务是一个不可分割的工作单位，事务中的操作要么全部成功，要么全部失败 一致性（Consistency） 事务执行前后，系统的状态保持一致 隔离性（Isolation） 事务的执行不会相互影响 持久性（Durability） 事务执行成功后，对系统的影响是永久的 4.4 分区和复制组和使用 节点内有多个分区，每个分区有多个副本 每个节点充当某些分区的领导者，其他分区充当从属者 4.5 HDFS分布式文件系统 HDFS系统架构 NameNode(主节点) 负责管理文件系统的命名空间，维护文件系统的元数据 DataNode(从节点) 负责管理文件系统的数据块，维护文件系统的数据块副本 HDFS工作机制 读操作 客户端向NameNode发送读请求， NameNode返回数据块所在的DataNode列表 客户端直接从最近的DataNode读取数据 写操作 客户端向NameNode发送写请求 NameNode根据负载均衡策略，返回数据块所在的DataNode列表，共3个 客户端将3个数据节点构成一个流水线，将第一个数据块写入流水线 再向NameNode获取下一个数据块对应的3个DataNode列表 数据复制方法 cd /home/aweip/Software/Distribute/hadoop/hadoopspark/ docker-compose up -d docker-compose down ssh -p 2222 root@localhost start-dfs.sh cd /root/share/mapreduce hadoop fs -mkdir /input mvn clean mvn package hadoop fs -put ./grades.txt /input hadoop jar ./target/AvgGradeStudent.jar com.org.xidian.MapReduceAvgGradeStudent /input/grades.txt /output1 hadoop fs -cat /output1/part-r-00000 cd ../mapreduce2 mvn clean mvn package hadoop jar ./target/AvgGradeClass.jar com.org.xidian.MapReduceAvgGradeClass /input/grades.txt /output2 hadoop fs -cat /output2/part-r-00000 cd ../mapreduce3 mvn clean mvn package hadoop fs -put ./child-parent.txt /input hadoop jar ./target/FatherSon.jar com.org.xidian.MapReduceFatherSon /input/child-parent.txt /output3 hadoop fs -cat /output3/part-r-00000
一、概述 1.【重点】基本概念 CIA(机密性、完整性和可用性) 机密性 Confidentiality：避免信息的非授权泄露 加密(Encryption) 访问控制(Access control) 认证(Authentication) 授权(Authorization) 物理安全(Physical security) 完整性 Integrity：确保信息不被非授权修改的属性 备份(Backup)：定期归档 数据校验和(Checksum)：计算一个函数将文件内容映射为一个数值。 数据纠错码(data correcting codes)：检测并纠正数据 保护元数据(metadata)：描述数据的数据。 可用性 Availability：确保授权用户能够对信息进行及时访问和修改的属性（目标用户能使用权限） 物理保护：在物理环境恶劣变化时也能够保护信息的可用性。。 计算冗余：在部分计算机或者存储设备失效的情况下依然可以提供信息。例如采用磁盘冗余阵列(RAID)和多台计算机。 3A(保证，真实性，匿名性) Assurance 保证：指计算机系统中信任 （个人理解为权限及其分配问题）如何被提供和管理 系统资源的管理和保护：确保系统资源如何在设定策略下使用 信息使用方式的管理：确保信息如何在设定策略下使用 信任管理： 策略(policy)： 指人或者系统对他们或者其他个体的行为预期 权限(permission)： 指在与人和系统交互时所允许的行为 保护(protection)： 指为了实施权限和策略所提供的机制 例子：在线音乐系统(为用户如何访问歌曲设定策略；为购买特定歌曲的用户提供访问权限；为系统提供保护以防止用户未授权的访问) Authenticity 真实性：确定人或者系统所发布的声明、策略和权限真实性的能力 真实性的满足能够确保在线交易的可行性。 不可抵赖性(Nonrepudiation)：一个人或者系统不能否认其所发布的真实声明 主要工具： 数字签名(digital signatures)： 一种加密计算方法，允许人或者系统以唯一的方式认可与其相关数据的真实性。数字签名可实现不可抵赖性。 与纸质签名类比 原题关注：数字签名为确保真实性工具 Anonymity 匿名性：确保特定的记录或者交易不归因于任何个体的属性。 不希望隐私泄露，如个体的医疗记录、购物记录等 确保匿名性的方法： 数据聚集(Aggregation) 数据混淆(Mixing) 使用代理(Proxy) (笑死) 使用化名(Pseudonym) 2. 十大安全原则 机制的经济性 故障安全默认配置 完备调停 ……这么多条考个锤子 3. 【重点】四种控制访问模型 访问控制矩阵：定义访问权限的表。 优点： 很容易确定主客体对的访问控制权限； 管理者能够简单、直观地观察访问控制； 关系控制粒度细。 缺点： 缺乏可扩展性，访问控制矩阵有可能会很大。 个人总结：详尽但是体积庞杂 访问控制列表：对于每个客体o，定义列表L， L为客体o的访问控制列表，该列表列举了所有对客体o有访问权限的主体。 优点： 与访问控制矩阵比小很多，可将客体的列表以元数据形式存储。 缺点： 枚举每个主体的访问权限复杂度高。这种枚举是必须的，例如将一个主体从系统中移除的时候。 个人总结：精炼但关系复杂 ​ 能力列表：本质上，能力列表使用访问控制矩阵的每一行并忽略其空白单元格。 优缺点与访问控制列表类似。 基于角色的访问控制：定义角色，并对角色指派访问控制权限，而不是直接对主体。 优点： 存储高效，降低需要记录的规则数量 缺点： 在目前操作系统中未实现。 个人总结：不错，牛逼，很好，不过在梦里才有。 3. 【重点】加密概念 加密(Encryption)：一种手段使得通信双方(Alice和Bob)在易受窃听的不安全信道上建立保密通信。 比如两方通信经过加密解密算法，关键词：对称与非对称加密，公钥私钥 数字签名(Digital Signatures)：公钥加密体制可以用来构造数字签名。 密码学哈希函数(Cryptographic Hash Function)：消息M的一个校验和，需要满足单向性和抗碰撞性。 消息认证码(Message Authentication Codes)：共享密钥，A发送消息与其哈希值，B收到消息再本地验证所收到消息的哈希值。 数字证书：比如https，可信机构对网站颁布证书 4. 实现和可用性相关问题 效率和可用性：计算机安全解决方案应该高效； 【基本理解】对密码的字典攻击：暴力破解会逐一尝试所有可能的组合密码，而字典式攻击会使用一个预先定义好的单词列表(可能的密码)； 社会工程(Social Engineering) …… 二、物理安全 1. 弹子锁 钥匙凹凸对应锁内圆柱高低分布 变成了__的形状 2. 身份认证技术 条形码：登机牌 磁条卡漏洞：易于读取和复制，如初高中破解饭卡水卡 智能卡：包含一个集成电路，可选配一个具有读写功能的板载微处理器 【重点】SIM 卡安全 SIM卡具有集成电路卡ID（ICCID），这是一个唯一的18位数字，用于硬件识别； SIM卡包含128位密钥。 此密钥用于向移动网络验证电话； PIN在访问卡上的信息时作为额外的安全机制 【重点】GSM挑战 - 响应协议 手机连接并发送其IMSI到网络提供商拥有的本地基站； IMSI匹配网络提供商的数据库中的用户，则基站将128位随机数发送到手机； 随机数由手机编码存储在SIM卡中，用户的密钥使用A3的专有加密算法，从而产生发送回基站的密文； 基站使用其存储的用于用户密钥的值来执行相同的计算。 密文匹配，则手机被认证享受相应连接服务。 3. 针对计算设备的攻击 环境攻击：攻击（指物化环） 窃听 信号发射：检测信号 键盘记录器 4. ATM ATM交易的当前行业标准是Triple DES（3DES）密码系统，这是一种传统的对称密码系统，具有高达112位的安全性。 三、 操作系统安全 1. 【重点】进程安全 信任传递 进程间通信 读写文件 共享内存 管道(pipe)和套接字(socket) 信号(signal) 进程监控 Windows系统可以使用任务管理器查看；Linux可以使用ps、top、pstree、kill等命令 管理和日志 事态感知：记录那些进程正在运行、哪些计算机在联网；如果操作系统遇到任何意外或者可疑操作，都会留下重要线索。 2. 【重点】内存与文件系统安全 内存安全 五段内存区中，每一段都有自己的访问权限，由操作系统执行这些权限； 对操作系统安全至关重要：不允许进程访问其他进程的地址空间； 加强地址空间边界保护； 操作系统一般将地址空间分为两个区：用户空间和内核空间。内核空间是为操作系统内核功能保留的特殊空间，有着最为严格的访问特权。 虚拟内存安全 Windows系统中，虚拟内存页面存储在C:\pagefile.sys中 Linux系统需用户自己设定一个硬盘分区作为交换分区，存储内存页面 关闭计算机时，硬盘上的虚拟内存页面会被删除 虚拟内存安全问题：如果攻击者突然将计算机断电，没有正常关闭计算机，此时虚拟内存页面可能未被删除攻击者通过外部介质引导另一个操作系统，能够查看这些文件并重建部分内存，导致信息泄露 解决办法：对硬盘内容进行加密 认证 通过身份验证 防范字典攻击：使用密码盐(password salt)技术：它是一种加密技术，使用随即位作为散列函数或加密算法的部分输入，从而增加输出的随机性 文件权限 Linux的权限控制 Windows的傻逼权限设计 文件描述符 存储在文件描述符表中的索引值，用来索引特定文件 漏洞：当程序以高权限打开文件描述符，但未关闭，然后又创建了低权限的进程，那么新进程就能够读写相关文件，但子进程本身不具有打开该文件的权限。 符号链接 快捷方式以及Linux软连接 漏洞：恶意方会利用符号链接诱使应用程序执行不良的操作 3.【理解掌握】应用程序安全 编译和链接 DLL注入：通过共享库向程序注入任意代码的过程。优点是便于调试，缺点是潜在的安全风险，恶意用户能向合法程序注入自己的代码。 缓冲区溢出攻击 当缓冲区是局部变量或帧的参数时，用户的输入可能覆盖返回地址，改变程序的执行； 攻击者利用栈缓冲区的脆弱性，在栈中注入恶意代码，覆盖当前调用的返回地址，从而将执行权限传递给攻击者的恶意代码。 格式化字符串攻击 C库函数如果不输入格式化信息，而是直接使用printf(str)，会出现漏洞； 攻击者指定所使用的格式化字符串作为输入，并可以将输入写入内存的任意位置。如果写入的位置正好覆盖了返回地址、函数指针等，则攻击者能够取得控制权，并在程序的上下文中执行任意代码。 四、恶意软件 1. 内部攻击 内部攻击(insider attack)是指控制和保护资产的内部人员利用安全漏洞进行的攻击。也就是内部中出了一个内鬼 后门 后门(backdoor) 是程序中隐藏的功能或命令，有时也称为活门，它允许用户执行一些操作，在正常情况下，这些操作是不允许用户执行的。 逻辑炸弹 逻辑炸弹(Logic bomb)是一种程序，它根据一定的逻辑条件执行恶意操作。 2. 【重点】计算机病毒 计算机病毒是一种能自我复制的计算机指令或程序代码，它通过修改其他文件与程序来插入代码，且能进一步自我复制 病毒的另一个特性是其复制需要某种类型的用户协助，如打开电子邮件附件或共享USB驱动器； 特征 传染性； 隐蔽性：代码短小精悍，隐藏巧妙； 潜伏性：病毒内部有一套触发机制，不满足触发条件时，除了传染外什么都不破坏； 多态性：不断变种，以防查杀； 破坏性：一旦出发，后果极为严重。 四个阶段 潜伏阶段：此阶段，病毒只是存在——病毒很低调并避免被检测到； 繁殖阶段：此阶段，病毒进行自我赋值，感染新系统中的新文件； 触发阶段：此阶段，一些逻辑条件导致病毒从潜伏或繁殖阶段转换为执行病毒预定的操作； 行动阶段：病毒会执行恶意的操作，这些执行是早已设计好的，成为有效载荷。 3. 恶意软件攻击 主要考病毒、蠕虫和木马的区别 计算机蠕虫 计算机蠕虫是一种恶意程序，不需将自己注入其他程序就能传播自己的副本，并且不需要与人交互。 从技术角度而言，计算机蠕虫不是计算机病毒（不会感染其他程序) 木马 表面上，它会执行一些有用的任务， 同时会隐形地执行具有负面后果的任务（间谍） Rootkits 修改系统实用程序或操作系统本身来防止检测 4. 对策 签名：一个签名是一个病毒指纹，如果文件中包含签名，则文件被感染 类似于病毒抗原，签名数据库用来储存计算机病毒特征 黑/白名单 启发式分析：用于识别新的和“零日”恶意软件 零日攻击：指利用未公开或未修复的安全漏洞进行的攻击，这种攻击往往能够造成巨大的破坏，因为厂商或用户没有足够的时间和手段来防范。名称来源于开发人员发现漏洞时补丁存在的天数：零天 代码分析：根据说明，防病毒软件可以确定该程序是否是恶意的，即程序 包含删除系统文件的说明 执行仿真 在隔离的仿真环境中运行代码 监控目标文件所采取的操作 5. 网络安全I 1. 以太网 基本概念 以太网包括通信所使用的物理介质以及链路层的协议标准IEEE 802.3，是现有局域网采用的最通用的技术标准； 不同帧在以太网电缆上同时传输时会产生冲突，需要丢弃并重传冲突帧。 2.【理解】 ARP欺骗(链路层，ARP spoofing) ARP 地址解析协议，链路层； 功能是将给定主机的网络层地址解析为主机的硬件地址。 ARP协议简单高效，但缺乏身份认证，容易受中间人攻击。 ARP欺骗 原理：攻击者可以向某一主机发送伪ARP应答报文，使其发送的信息无法到达预期的主机或到达错误的主机 预防措施 检查相同MAC地址是否在局域网中多次出现； 静态ARP表：网络管理员手动指定路由器的ARP缓存来将具体的MAC地址和特定的IP地址进行绑定。 更加复杂和灵活的措施：anti-arpsroof、XArp、Arpwatch，这些程序会仔细检查所有的ARP数据包，并与所存储的ARP表项记录做比较，以检测并防止ARP欺骗。 3.【理解】IP欺骗(IP spoofing) IP 网络层协议 功能是尽力将一个数据包从源节点路由到目的节点 IP包路由：如果数据包的目的地址与发送数据包的主机在同一个局域网内，则使用ARP协议确定目的地址的MAC地址，并发送包；反之，数据包被传送至局域网的网关处，网关根据路由表来确定如何转发数据包； TTL(time-to-live)：每个数据包在路由过程中的生存周期，用跳数来决定，一般最大跳数为255； 路由器操作：对每个数据包执行丢弃、发送或转发三个操作； 路由协议： OSPF(Open shortest path first)协议决定如何在自治系统中路由数据包，其策略是数据包应沿最短路径传输。 BGP (Border gateway protocol)决定如何在自治系统之间路由数据包。 IP地址欺骗(IP spoofing) 原理：恶意用户产生的IP数据包中的源IP地址是伪造的，以便冒充其他系统或发件人的身份。 如果攻击者用假冒的源IP地址，那么他不会收到服务器的响应。服务器会把数据包返回给具有假冒IP地址的主机。 拒绝服务攻击 应对措施 边缘路由器在配置时，可以阻止源地址在域内，但实际地址是域之外的数据包； IP追踪技术：追踪数据包返回到实际源地址的路径。根据追踪到的信息，可以向各种自治系统发送请求，要求自治系统阻止来自该路径的数据包，直到确定恶意软件或恶意用户被清除为止。 4. 【理解】网际控制消息协议(网络层，ICMP) ICMP协议：用于在主机、路由器之间传递控制消息。 ICMP消息类型 回显请求(echo request) 回显响应(echo response) 超时(time exceeded) 目的地不可达(destination unreachable)。 5. 数据包嗅探 Wireshark：网络数据包分析软件。功能是撷取网络封包，并尽可能显示出最为详细的网络数据包资料。 使用WinPCAP作为接口，直接与网卡进行数据报文交换。使用时网卡被设置为混杂(promiscuous)模式。 防止嗅探 使用以太网交换机替代集线器，但不适用于无线网络； 检测网卡是否被设置为混杂模式； 高层协议使用加密防止敏感信息泄露，如HTTPS协议。 6. 传输层协议 端口：16比特的端口号，用来标识应用层不同服务。 UDP：无连接的、不可靠但速度快。 TCP：面向连接的、可靠的。 【重点】TCP会话劫持 TCP序列号预测：TCP序列预测攻击企图猜测TCP会话时的初始序列号，以建立伪造的TCP会话。 攻击者针对受害客户端发动拒绝服务攻击； 攻击者向服务器发送一个SYN包，将源IP地址伪造成受害客户端的IP地址； 等待服务器向客户端发送响应之后，攻击者通过发送一个ACK数据包来结束TCP握手，该数据包的序列号是预测的下一个序列号； 攻击者以受害客户端名义向服务器发送请求。 盲注入(Blind injection)：注入包含命令的数据包，从而建立将响应返回给攻击者的连接。 ACK风暴(Blind injection) 盲注入后客户端不会向服务器发送同步消息，导致不同步现象 此时，客户端和服务器会向对方发送ACK消息，每一方都想告诉对方需要开始使用正确的序列号。 这种反复的通信被称为ACK风暴。 完全会话劫持 (complete session hijacking) 当攻击者与目标服务器或客户端在同一网段时，攻击者可以完全劫持已有的TCP会话。使用数据包嗅探攻击，攻击者可以知道建立会话时数据包的序列号。 完全会话劫持与ARP欺骗结合的中间人攻击：攻击者首先使用ARP欺骗，将会话双方的通讯流暗中改变，这种改变对会话双方来说是透明。其次，攻击者利用完全会话劫持来截获会话双方的所有消息 针对会话劫持的安全措施 在IP层或者应用层使用认证和加密 网站应避免创建以安全身份验证措施开始，但后来切换到未加密交换的会话，这样会产生的风险。 7. DOS攻击 任何旨在使计算机或系统不可用或无法执行基本功能的攻击 TCP泛滥攻击 DNS放大攻击 8. IP地址回溯 IP地址回溯能够确定数据包的真实来源，而不依赖于数据包头部的IP地址。 【重点】数据包标记技术：路由器基于数据包的相关路径信息确定地或者概率地标注转发数据包。 节点采样：不在每个数据包中追加路径信息，而使用IP数据包中的一个字段就可以记录路径信息。 6. 网络安全II 1. DNS 域名系统（DNS）：应用层协议，负责将域名映射到IP地址。 域名解析 DNS数据包：DNS查询和应答是通过UDP数据包传输的，但当请求或应答超出512B时，会用TCP替代UDP。 DNS攻击 网络嫁接与网络钓鱼： 攻击者把网站发送的请求解析成自己恶意服务器的伪装IP地址，导致受害人浏览或下载不需要的内容 网络嫁接的一个主要用途是将域名解析为一个网站，该网站表面与所请求网站相同，但实际上是恶意网站，这种攻击被称为网络钓鱼 DNS缓存中毒 攻击者欺骗DNS服务器缓存保存虚假的DNS记录 当域名服务器出现以下情况时，缓存可能会中毒 忽略标识符 具有可预测的ID 接受未经请求的DNS记录 2. 防火墙 防火墙：一种集成的安全措施集合，旨在防止对网络计算机系统未经授权的访问。 防火墙策略：部署防火墙过滤流入或流出的流量，基于的预定义规则集称为防火墙策略 有 无 3. 【重点】隧道技术 TCP数据包的内容是不加密的，如果有人窃听TCP连接，他会知道该会话中有效载荷的所有内容； 在隧道协议中，客户端和服务器之间的通信自动加密。 【重点】SSH 客户端通过一个TCP会话连接到服务器； 客户端与服务器交换管理细节的信息，如支持的加密方法、各自协议的版本，每一方都要选择另一方支持的一组协议； 客户端和服务器进行密钥交换，创建共享的秘密会话密钥，用会话密钥加密双方的通信（但不用于身份验证）。 公共密钥身份验证，客户端向服务器发送自己的公钥； 服务器检查是否这密钥已存储在其授权的密钥列表之中。如果在，服务器使用客户的公钥加密挑战，并将其发送给客户端； 客户用自己的私钥解密挑战，并向服务器发回响应，证明自己的身份； 服务器向客户端发送可接受身份验证列表，客户端将按顺序尝试。 一旦身份验证已顺利完成，服务器允许客户端访问相应的资源，如命令提示符； IPSec IPSec定义了一组协议，为IP数据包提供机密性和真实性; 每个协议都能运行在两种模式下，传输模式或隧道模式 传输模式：在原数据包的数据之前，会插入额外的IPSec的头信息，只对数据包的有效载荷继续加密或身份验证 隧道模式：构造一个新的数据包，将IPSec头信息和整个原数据包（包括它的头）一起封装为新数据包的有效载荷； 虚拟专用网络VPN（了解） 尽管使用不受信任的网络进行传输，VPN也能提供数据的保密性、完整性 远程访问VPN：允许授权的用户访问私有网络，一般将这种私有网络称为内网； 站点到站点VPN：旨在为两个或更多远程网络提供安全的桥梁 4. 入侵检测 考点：真阳假阳 入侵检测事件两种类型的错误 误报：当事件是良性活动而不是入侵时就发出警报（浪费时间和资源）； 漏报：当事件是入侵的恶意事件，未发出警报（系统受到损害，管理员未察觉）； 【重点】基率谬误：根据理解进行简单计算 假设IDS准确度为99％，假阳性或假阴性的概率为1％ 入侵检测系统生成1,000,000+100个日志条目，1,000,000个良性事件，100个恶意事件 假阴性的概率为1％：100个恶意事件中，99个将被检测为恶意，有1个假阴性； 假阳性的概率为1％：1,000,000个良性事件中，10,000个将被错误地识别为恶意事件。 7. Web安全 1. 网络钓鱼 伪造网页以欺诈方式获取敏感资料； 用户一般是从垃圾邮件中访问网络钓鱼页面。 混淆方式 错误拼写URL链接（粤利粤） URL混淆： Unicode 攻击 之前了解过的Cyrillic和ASCII字符 移除或伪造地址栏 2. 可移动代码 可执行、通过网络发送、在目标电脑上执行的代码程序。 JavaScript ：直接由浏览解释的脚本语言。 ActiveX控件：是一个开放的集成平台，为开发人员提供了一个快速而简便的在 Internet 和 Intranet 创建程序集成和内容的方法。Java插件：可以将Java编译后的程序添加到其他项目中。 集成的Java虚拟机：是运行所有Java程序的抽象计算机，是Java语言的运行环境。 3. Cookies 存储在计算机上、与特定服务器关联的一小部分信息。 访问特定网站时，可能会将信息存储为cookie 每次重新访问该服务器时，cookie都会被重新发送到服务器用于在会话中保存状态信息 可以保存敏感信息 4. 【重点】XSS跨站脚本攻击 攻击者将脚本代码注入Web应用程序生成的页面 网站输入框内输入恶意代码，服务器将合并到返回的页面使得代码被运行 通常在有漏洞的程序中插入Javascript，VBScript，ActiveX或Flash以欺骗用户 XSS发起条件： Web服务器没有对用户输入进行有效性验证或者验证强度不够； 允许用户在表格或编辑框中输入不相关字符； 存储并允许把用户输入显示在返回给终端的页面上，而没有去除非法字符或者重新进行编码。 客户端对于XSS的防御： 基于代理 分析浏览器和Web服务器之间的HTTP通信量； 寻找HTML中的特殊字符； 执行Web页面之前对它们进行编码。 应用层防火墙 分析HTML页面中可能导致敏感信息泄漏的超链接； 对于使用不良请求的一系列链接进行停止操作。 审计制度 监视JavaScript代码的执行，并将操作与高级策略进行比较，以检测恶意行为。 5. 【重点】SQL注入攻击 通过把SQL命令插入到Web表单提交或输入域名或页面请求的查询字符串，最终达到欺骗服务器执行恶意的SQL命令 SQL注入条件 web应用程序从表单中获取用户输入； 用户输入的信息直接用于构造提交到数据库的SQL查询； SQL注入之万能密码：' or '1'='1 SQL 注入的防范 使用预编译语句，绑定变量； 对用户提交的数据和输入参数进行严格的过滤； 过滤逗号，单引号，分号等； 如果 select，delete，from，”，union 之类的字符串同时出现多个的话，要重视； 对用户提交参数的长度进行判断 使用安全函数：比如 OWASP ESAPI； 摒弃动态SQL语句，改用存储过程来访问和操作数据； 最小权限原则：避免 Web 应用直接使用 root，dbowner 等高权限账户直接连接数据库。 8.密码学概述 1. 加密基本概念 场景 (Scenario) Alice希望发送一条消息（明文P）给Bob。 通信信道是不安全的，有可能被窃听。 如果Alice和Bob之前已经协商好了一个对称加密方案和一个密钥K，那么该消息就可以加密后再进行传输（密文C）。 符号 (Notation) 密钥K 加密算法E_K(P) 解密算法D_K(C) 密文长度通常和明文长度相同 加密/解密是所有n位二进制序列(n-bit arrays)构成的集合上的(双射)置换函数 效率 (Efficiency) 加密算法E_K(P)和解密算法D_K(C)必须是高效的 一致性 (Consistency) 对密文解密后可恢复出明文: D_K(E_K(P))=P 2. 【理解区分】攻击者的主要类型 唯密文攻击(ciphertext-only attack) 攻击者收集一个或多个消息的密文； 已知明文攻击(known-plaintext attack) 攻击者收集一个或多个 明文—密文对； 选择明文攻击(chosen-plaintext attack) 攻击者可收集指定的明文对应的密文信息; 选择密文攻击(chosen-ciphertext attack) 攻击者可收集指定的密文对应的明文信息。 3. 替换密码和频率分析 n位二进制位的英语文本信息熵2^{1.25*n/8}≈2^{0.16n} 4. 一次一密 每次都是完全随机地选择移动量，在密文中字母表的每个字母出现的概率几乎相同 弱点：密钥块的长度m必须和明文的长度n相同 5. 分组密码 明文和密文具有固定的长度b（例如，128位）； 长度为 n 的明文被划分为 m 个序列块 P[0], …, P[m-1]（n ≤ bm＜ n + b）； 每条消息被划分成一系列的块，基于这些数据块来进行加密或解密。 高级加密标准（AES）：AES加密算法的128位版本进行十轮的处理 每一轮都对128位的数组（state）执行可逆替换; 初始stateX_0是明文P与密钥K的异或： X_0 = P XOR K; 第 i 轮 (i = 1, …, 10 ) 接受 state X_{i-1} 作为输入，并产生 state X_{i-1}; 最后一轮输入密文C：C = X_{10}; 6. 【区分】分组密码优缺点 电子密码本（ECB）模式 （最简单的一种模式） 优点：ECB模式适合于数据较少的情况，比如密钥和初始向量的加密； 缺点：对于文件和图片这类很长的消息，ECB模式可能是不安全的，因为ECB模式会揭示在分组流中出现的模式，即相同的分组会使用相同的加密方式。 密码分组链接（CBC）模式 优点： 没有在明文中泄露明文的模式； 是最常用的模式之一； 快速且相对简单。 缺点 需要所有数据块进行有序的可靠传输； CBC模式不适用于允许丢包的应用程序，如音频流和视频流。 7. 流密码 密钥流 伪随机序列 S = S[0], S[1], S[2], …… 可以每次生成1位或者1个字节 流密码 密钥流和明文流进行对位异或操作 C[i] = S[i]⊕P[i]; 适用于快速写入的任意长度的明文，例如流媒体数据. 同步流密码 密钥流的生成只依靠密钥K 如果明文是带有序列号的包，那么同步流密码可在不可靠信道下工作 自同步流密码 使用密钥K和前q个密文来生生成密钥流 在接收到q个密文后会自动与密钥流生成器同步，如果数字被丢弃或添加到明文流中，更容易恢复 8. 【计算】 1. 辗转相除法 指用于计算两个正整数a，b的最大公约数 gcd(a, b) = gcd(b, \text{ a mod b}) EuclidGCD算法的最大迭代次数为 1 +\text{2 log max(a ,b)} 2. 【会算逆元】乘法逆元 一个正整数 n 的剩余类可表示成以下集合的形式 Z_n = {0, 1, 2, …, (n -1)} 令 x 和 y 是 Z_n 中的元素，则 \text{xy mod n = 1}, 我们称 y 是 x 在 Z_n 的 乘法逆元，记作y = x^{-1} 3. RSA密码系统 4. 哈希函数 h将可变长度的消息P作为输入，产生固定长度的Hash值x = h(P)，称函数值h(P)为P的哈希值或消息摘要。 碰撞(collision)：指的是存在两个消息P和Q被映射到相同的哈希值，即 h(P) = h(Q) 碰撞是不可避免的 哈希值的计算时间应该和输入消息的长度成正比 生日攻击 攻击者可以通过生日攻击的蛮力技术来对密码学Hash函数进行攻击，主要危害其抗碰撞性，主要步骤如下： 随机产生消息序列X_1, X_2, X_3,… 对于每个X_i计算Hash值y_i = h(X_i)并且检测y_i是否等于y_j ( j < i ) 直至找到碰撞即停止 1/2长度：通常根据输出大小的一半来考虑加密散列函数安全，比如256位抗冲突Hash函数的安全是128位 5. 消息认证码 密码学哈希函数h(K, M)有两个输入: 密钥K和消息M 9. 安全模型与实践 1. 策略、模型与信任基本概念 安全策略（5部分） 主体（Subject）：与系统交互的代理，可以根据特定的个人定义，也可以根据个人群体在组织中可能持有的角色或级别来定义。 个人可以通过姓名或职称来识别，可以用术语来定义组。此类别还包括外部人员，如攻击者和来宾。 客体（Object）：客体是安全策略要保护和管理的信息与计算资源。 信息包括重要文档、文件与数据库，计算资源包括服务器、工作站和软件。 行动（Action）：主体对客体可能（或不可能）执行的操作。 操作一般包括文档的读取和写入、在web服务器上更新软件以及访问数据库的内容。 权限（Permission）：主体、操作与客体之间的映射，权限明确规定允许或禁止哪些操作。 保护（Protection）：策略中包含的特定安全特性或规则，以帮助实现特定的安全目标，如保密性、完整性、可用性或匿名性 安全模型：是一种抽象的、为管理员指定安全策略提供概念语言。 2. 访问控制模型 Bell-La Padula模型：信息只能从低安全级别流向高安全级别 军事分级层次结构； 系统有四种安全级别：最底层的是不保密（unclassified）、然后安全性呈升序的分别是秘密（confidential）、机密（secret）、绝密（top - secret）； 每个文件归类于一个安全级别； 每个用户都会在一个安全级别得到放行许可（clearance）。 Biba模型：信息只能从较高的完整性级别下降到较低的完整性级别 Biba模型的完整性级别表明对象和用户的可信度或准确度，而不是确定保密级别； 不允许从下一级阅读，也不允许写到上层。 低水印模型：对Biba模型的扩展，它放宽了“不可向下读”的限制 克拉克-威尔逊模型：不处理文档机密性或完整性，而是处理执行事务的系统 中国墙模型：每个用户只能从每个利益冲突类访问一个资源 3. 渗透测试 从攻击者(黑客)的角度测试系统和体系结构的安全性，在固定时间内必须获得的具有预定目标的“模拟攻击” 4. 【重点】Kerberos 基于可信第三方（Trusted Third Party，TTP）的认证协议； MIT的雅典娜项目组（Athena Group）开发的认证服务系统。 Kerberos使用票据（ticket）的概念作为证明用户身份的令牌。票据是存储会话密钥的数字文件。在登录会话中，通常会发送会话密钥，然后代替在kerberized服务中的密码； 在身份验证过程中，客户端会收到两个票据 票据授予票据（ticket-granting ticket，TGT）：用户和会话密钥的全局标识符； 服务票据（service ticket）：对用户进行身份验证，确定用户能否使用特殊服务。 票据都有时间戳，用于表明票据的有效期限； 为了实现安全的身份验证，Kerberos使用可信第三方作为密钥分发中心（key distribution center，KDC）,由两个部分组成： 身份验证服务器（authentication server，AS）：用于执行用户身份验证。 票据授予服务器（ticket granting server，TGS）：用于向用户授予票据。 身份验证服务器维护存储用户和服务密钥的数据库。对用户提供的密码执行单向散列来生成用户的密钥。 身份验证大致流程： 客户端与身份验证服务器（AS）互相进行身份验证； 客户端与票据授予服务（TGS）互相进行身份验证； 客户端与服务（S）互相进行身份验证，此要为客户端提供服务。 身份验证： 1.用户在客户端计算机上输入用户名和密码，执行哈希（hash）函数对输入进行散列操作，形成客户端的密钥。 客户端与AS联系，AS作如下反应： 使用客户端密钥KC（存储在AS数据库中）加密客户端-TGS的会话密钥KGT。 使用TGS密钥KT（存储于AS数据库中）加密票据授予票据（TGT）。TGT包括密钥KCT和有效期。 客户端使用KC解密TGS会话密钥KCT。为了请求服务，客户端向TGS发送如下两个消息： TGT（仍然使用TGS的密钥KT加密）和所请求服务名称S。 验证令牌（authentication token）由客户ID和时间戳组成，使用客户端TGS会话密钥KCT进行加密。 TGS使KT解密TGS，从而得到客户端TGS的会话密钥KCT和TGT的有效期。在有效期之内，TGS使用密钥KCT解密身份验证令牌，向客户端发送如下两个消息： 使用KCT加密的新的客户端-服务器会话密钥（client-server session key） KCS。 使用具体服务的密钥KS加密客户端-服务器票据（client-server ticket），其中TGS已知密钥KS 。票据包含客户端ID、网络地址、有效期、密钥KCS。 在对客户端-服务器会话密钥KCS解密后，为了使服务对客户端进行身份验证，客户端发送以下两个消息： 在上个步骤中，TGS发送的客户端-服务器的票据。 使用KCS加密的客户端ID和时间戳。 服务使用自己的密钥KS解密客户端-服务器的票据，得到客户端-服务器的会话密钥KCS 。使用KCS解密客户端ID和时间戳。最后，为了向客户端证码自己的身份，它使用时间戳加1，并用KCS重新加密送回客户端。 客户端使用KCS解密并验证这个响应，如果验证成功，就可以开始客户端-服务器的会话了。 Remark：在票据授予票据的有效期内，客户端为了访问多个服务，可以一直重复协议中的步骤3~7。 5. 安全存储 加密文件系统（EFS） 磁盘加密 BitLocker 10. 分布式应用程序的安全 1. 数据库安全 为了解决一致性和可靠性问题，大多数数据库在执行更新时使用两阶段提交协议 (two-phase commit)。 最小特权原则 (Least-privilege principle)：实现适当的访问控制应遵循最小特权原则，使每个用户都拥有完成自己任务所必需的权限，但除此之外，不再拥有其他的权限。 特权分离原则 (Separation of privilege principle)：实现适当的访问控制还应遵循特权分离原则，以便不同的用户具有不同的权限，这取决于他们需要执行的不同任务。 推理攻击 即使删除或屏蔽掉身份信息，攻击者仍能将其他的信息与数据库结合，得到底层的数据。 2. 垃圾邮件 Spamhaus黑名单（SBL） 后续不重要，知道即可……
题目内容 自行拍摄同一场景不同角度的两幅图像,编程实现图像的拼接： 基于图像特征点提取的相关内容,选择相关特征点匹配算法(SIFT、SURF、HOG)完成特征点提取； 利用 RANSAC 算法实现特征点匹配； 利用图像几何变换算法实现图像变换和拼接。 原理分析 操作步骤： 给定图像，调用 opencv 库中 SIFT（SURF，HOG）算子分别对两幅图像进行特征点提取,计算获得特征点及其描述子； 对第一步两张图片的结果进行匹配，具体方法有 BF(Brute-Force),暴力特征匹配方法和 FLANN 最快邻近区特征匹配，最终获得匹配点； 利用 RANSAC 算法，计算单应性矩阵，去除误匹配点，获得内点； 对第一幅图像进行透视变换，将第二幅图像复制到变换后的图像上，得到拼接后的图像。 SIFJ 原理： 建立高斯差分金字塔 首对图像做不同尺度的高斯模糊； 对图像做降采样(隔点采样)。 关键点的确定 选取图像的局部极值点； 局部极值点的确定主要通过将该位置像素点与空间中相邻的 26 个点比较。 构建关键点描述子 将 16x16 窗口划分为 4x4 单元格； 为每个像素计算边缘方向， 为边缘方向建立直方图； 计算每个单元格的方向直方图，16 个单元格 * 8 方向 = 128 维描述符； 将该 128 维向量归一化到单位长度。 RANSAC 的算法步骤: 假定模型（如直线方程），并随机抽取 N 个（以 2 个为例）样本点，对模型进行拟合； 由于不是严格线性，数据点都有一定波动，假设容差范围为： sigma，找出距离拟合曲线容差范围内的点，并统计点的个数； 重新随机选取 N 个点，重复第一步~第二步的操作，直到结束迭代； 每一次拟合后， 容差范围内都有对应的数据点数，找出数据点个数最多的情况，就是最终的拟合结果。 设计与实现 使用语言：Python 使用的库：opencv-python, numpy, matplotlib.pyplot 注：由于 SIFT（现已版权到期）和 SURF 的版权问题，使用 python 为 3.7 版本，opencv-python库版本为 3.4.2.16 特征点提取，选择特征点匹配算法 def feature_points_extraction(src: np.ndarray, method: str) -> tuple: if method == 'SIFT': sift = cv.xfeatures2d.SIFT_create() kp, des = sift.detectAndCompute(src, None) elif method == 'SURF': surf = cv.xfeatures2d.SURF_create() kp, des = surf.detectAndCompute(src, None) elif method == 'HOG': hog = cv.HOGDescriptor() kp, des = hog.compute(src) else: raise ValueError('method error') return kp, des特征点匹配及图像拼接 特征点匹配及图像拼接 def feature_points_matching(src1: np.ndarray, src2: np.ndarray, method: str): kp1, des1 = feature_points_extraction(src1, method) kp2, des2 = feature_points_extraction(src2, method) FLANN_INDEX_KDTREE = 0 # 建立FLANN匹配器的参数 index_params = dict(algorithm=FLANN_INDEX_KDTREE, trees=5) # 配置索引，密度树的数量为5 search_params = dict(checks=50) # 指定递归次数 match = cv.FlannBasedMatcher(index_params, search_params) # 建立匹配器 matches = match.knnMatch(des1, des2, k=2) # 得到匹配的关键点 good = [] # 良好的匹配点 for m, n in matches: # 通过比值测试筛选出好的匹配点 if m.distance < 0.75 * n.distance: # 0.75是经验值 good.append([m]) if len(good) > MIN: src_pts = np.float32([kp1[m[0].queryIdx].pt for m in good]).reshape(-1, 1, 2) # queryIdx是第一幅图像中的描述子索引 dst_pts = np.float32([kp2[m[0].trainIdx].pt for m in good]).reshape(-1, 1, 2) # trainIdx是第二幅图像中的描述子索引 M, mask = cv.findHomography(src_pts, dst_pts, cv.RANSAC, 5.0) # 获取单应性矩阵，RANSAC是随机采样一致性算法，作用是去除异常值， #原理：随机选择一些点，计算出单应性矩阵，然后计算所有点到单应性矩阵的距离，距离小于阈值的点认为是内点， #然后计算内点的比例，如果比例大于设定的阈值，就认为这个单应性矩阵是正确的，否则就重新随机选择一些点， #计算单应性矩阵，直到达到设定的迭代次数 # 展示匹配点 img3 = cv.drawMatchesKnn(src1, kp1, src2, kp2, good, None, flags=2) plt.imshow(img3),plt.title('Matching points'),plt.xticks([]),plt.yticks([]) plt.show() h, w = src1.shape[0], src1.shape[1] # 获取图像的高和宽 pts = np.float32([[0, 0], [0, h - 1], [w - 1, h - 1], [w - 1, 0]]).reshape(-1, 1, 2) # 获取图像的四个顶点 dst = cv.perspectiveTransform(pts, M) # 对四个顶点进行透视变换 src2 = cv.polylines(src2, [np.int32(dst)], True, 255, 3, cv.LINE_AA) # 画出变换后的图像 else: print("Not enough matches are found - %d/%d" % (len(good), MIN)) dst = cv.warpPerspective(src1, M, (src2.shape[1] + src1.shape[1], src2.shape[0])) # 将第一幅图像进行透视变换 dst[0:src2.shape[0], 0:src2.shape[1]] = src2 # 将第二幅图像复制到变换后的图像上 return dst 实验结果 原图如下所示，以不同角度选取了建筑室内的图片，经 SURF 与 RANSAC 算子处理，可见匹配中绝大部分为正确匹配，只有极少量的误匹配，可忽略不计。 经过透视变换后， 左右图以良好的角度拼接在了一起， 结果如下：
题目内容 自选一张图像，编程实现以下操作： • 分别采用 Sobel 算子和 Canny 算子滤波，进行边缘提取； • 显示原始图像以及不同滤波器滤波后的结果； • 对于 Sobel 滤波结果，显示 x 方向的梯度、y 方向的梯度、梯度幅度、梯度角度等； • 对于 Canny 算子滤波，显示滤波后边缘检测结果，并分析不同滤波结果的差异。 原理分析 Sobel 算子原理分析 Sobel算子是高斯导数的一般近似，是多用于边缘检测的离散性差分算子。 Sobel算子有两组不同的卷积因子 S_x,S_y.可以为一张图片做水平和垂直方向的平面卷积。 S_x = \left[ \begin{matrix} -1 & 0 & +1\\ -2 & 0 & +2 \\ -1 & 0 & +1 \end{matrix} \right] S_y = \left[ \begin{matrix} -1 & -2 & -1\\ 0 & 0 & 0 \\ +1 & +2 & +1 \end{matrix} \right] 假设要对一张图中的（ x,y ） 像素 (预设图片已处理为uint8格式) 使用Sobel算子，首先分别用两个卷积因子分别对该点做卷积。 x方向上的卷积为： G_x=A*S_x y方向上的卷积为： G_y=A*S_y 那么，该点的梯度幅值和方向为： G=\sqrt{G_x^2+G_y^2} θ=arctan (G_y/G_x) 如果梯度幅值G大于了阈值，那么这个点就可以被考虑成边缘点。 Canny 算子原理分析 Canny 算子是计算机视觉中应用最广泛的边缘检测算子之一。 Canny 算子进行边缘检测的步骤： 用高斯导数进行滤波降噪 现实中由于采集设备、环境干扰等多方面的原因导致采集到的图像信息都是含有大量噪声信息的, 高斯滤波可以将图像中的噪声部分过滤出来，使图像更平滑。 高斯滤波处理在图像上反映出来的是一个加权平均的过程，距离中心点越近的部分，其权重越大，反之越小，而权值的分布，则符合正态分布，对于一个二维图像来说，则符合二维高斯分布。 高斯滤波器（ksize = 5 , k = 2）的计算公式如下： G[i,j]=\frac{1}{ 2πσ^2 } e^{-\frac{(i-k-1)^2+(j-k-1)^2}{2σ^2}} 计算获得高斯卷积核后，对图像进行卷积操作。 获得梯度的幅值与方向 利用上述[1. Sobel 算子原理分析]，对平滑后的图像用Sobel算子进行卷积处理，获得图像的梯度幅值数组与方向数组。 非最大值抑制（NMS） 通俗意义上是指寻找像素点局部最大值，将非极大值点所对应的灰度值置为0，这样可以剔除掉一大部分非边缘的点。 首先要确定像素点C的灰度值在其8值邻域内是否为最大。 图1中蓝色的线条方向为C点的梯度方向，这样就可以确定其局部的最大值一定分布在这条线上，即出了C点外，梯度方向的交点dTmp1和dTmp2这两个点的值也可能会是局部最大值。 因此，判断C点灰度与这两个点灰度大小即可判断C点是否为其邻域内的局部最大灰度点。如果经过判断，C点灰度值小于这两个点中的任一个，那就说明C点不是局部极大值，那么则可以排除C点为边缘。 阈值化边缘: 设定双阈值（滞后阈值） T1>T2 Step1: 当边缘像素强度>T1时，该边缘保留 Step2：对T1>边缘像素强度>T2，当其与强边缘连接时才是边缘 找连通域（8个方向） 设计与实现 使用语言：Python 使用的库：opencv - python, numpy, matplotlib.pyplot 源码：test.py, main.py(见文件) 主要功能函数： 边缘补偿 def padding(image: np.ndarray, ksize: int) -> np.ndarray: '''在进行卷积操作前，对图像边缘进行补偿，避免边缘像素损失 ksize: 卷积核大小 pad: 需要补偿的边缘像素宽度 pad计算公式: pad = ksize//2 返回值： padded_out ''' h, w = image.shape[0], image.shape[1] pad = ksize//2 padded_out = np.zeros((h+2*pad, w+2*pad)) out_copy = image.copy() padded_out[pad:pad+h, pad:pad+w] = np.uint8(out_copy) return padded_out Sobel算子 def sobel_filter(image: np.ndarray): '''利用Sobel算子对图像进行卷积 sobelX = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]]) sobelY = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]]) 返回值： Gx:x方向梯度 Gy:y方向梯度 Ga:梯度幅度 theta:梯度角度 ''' sobelX = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]]) sobelY = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]]) pad = 1 h, w = image.shape[0], image.shape[1] tmp = padding(image, ksize=3) Gx = np.zeros([h + 2*pad, w+2*pad]) Gy = np.zeros([h + 2*pad, w+2*pad]) Ga = np.zeros([h + 2*pad, w+2*pad]) theta = np.zeros([h + 2*pad, w+2*pad]) for y in range(h): for x in range(w): #Gx[y + 1, x + 1] = np.sum(sobelX * tmp[y:y + 3, x:x + 3]) #Gy[y + 1, x + 1] = np.sum(sobelY * tmp[y:y + 3, x:x + 3]) Gx[y + 1, x + 1] = abs(np.sum(sobelX * tmp[y:y + 3, x:x + 3])) Gy[y + 1, x + 1] = abs(np.sum(sobelY * tmp[y:y + 3, x:x + 3])) Ga[y + 1, x + 1] = np.sqrt((Gx[y + 1, x + 1] ** 2 + Gy[y + 1, x + 1] ** 2)) if Gx[y + 1, x + 1] == 0: theta[y + 1, x + 1] = np.pi / 2 else: theta[y + 1, x + 1] = np.arctan(Gy[y + 1, x + 1] / Gx[y + 1, x + 1]) * 180/ np.pi #theta[y + 1, x + # 1] = np.arctan(Gy[y + 1, x + 1] / Gx[y + 1, x + 1]) Gx = Gx[1:1 + h, 1:1 + w].astype(np.uint8) Gy = Gy[1:1 + h, 1:1 + w].astype(np.uint8) Ga = Ga[1:1 + h, 1:1 + w].astype(np.uint8) theta = theta[1:1 + h, 1:1 + w].astype(np.uint16) return Gx, Gy, Ga, theta 高斯模糊（平滑） def gauss_filter(image: np.ndarray, sigma) -> np.ndarray: """计算高斯卷积核，填充图像并卷积滤波 高斯卷积核计算公式为： G(x,y) = (1/(2*pi*(sigma)^2))*e^(-(x^2+y^2)/2*sigma^2) 返回值： blur_img """ h, w = image.shape[0], image.shape[1] # 获得高斯卷积核 ksize = 5 k = ksize // 2 kernel = np.zeros([ksize, ksize]) for x in range(ksize): for y in range(ksize): kernel[y, x] = np.exp(-((x - k) ** 2 + (y - k) ** 2)/(2 * (sigma ** 2))) kernel /= (sigma * np.sqrt(2 * np.pi)) kernel /= kernel.sum() # 图像补边 tmp = padding(image, ksize) blur_img = np.zeros([h + 2 * k, w + 2 * k]) # 卷积计算 for y in range(h): for x in range(w): blur_img[y + k, x + k] = np.sum(kernel * tmp[y:y + ksize, x:x + ksize]) blur_img = blur_img[k:k + h, k:k + w].astype(np.uint8) return blur_img 非极大值抑制 def NMS(Ga: np.ndarray, theta: np.ndarray) -> np.ndarray: '''对梯度幅值进行非极大值抑制,凸显图像边缘 num_1,num_2:像素点Ga[i,j]梯度方向前后的经过插值运算获得的梯度值 若Ga[i, j]不是最大值,则该像素点归0 返回值： nms_img ''' h, w = Ga.shape[0], Ga.shape[1] nms = np.copy(Ga[1:-1, 1:-1]) for i in range(1, h-1): for j in range(1, w-1): angle = theta[i, j] weight = np.tan(angle) if angle > np.pi / 4: d1 = [0, 1] d2 = [1, 1] weight = 1 / weight elif angle >= 0: d1 = [1, 0] d2 = [1, 1] elif angle >= -np.pi / 4: d1 = [1, 0] d2 = [1, -1] weight *= -1 else: d1 = [0, -1] d2 = [1, -1] weight = -1 / weight g1 = Ga[i + d1[0], j + d1[1]] g2 = Ga[i + d2[0], j + d2[1]] g3 = Ga[i - d1[0], j - d1[1]] g4 = Ga[i - d2[0], j - d2[1]] num_1 = g1 * weight + g2 * (1 - weight) num_2 = g3 * weight + g4 * (1 - weight) if num_1 > Ga[i, j] or num_2 > Ga[i, j]: nms[i - 1, j - 1] = 0 nms_img = nms[0:h - 2, 0:w - 2].astype(np.uint8) return nms_img 双阈值进行边缘的检测和连接 def threshold_edge(nms: np.ndarray, threshold_low: int, threshold_high: int) -> np.ndarray: '''强化图像边缘，去除无关细节 threshold_low, threshold_high: 设定的上下阈值 对图像进行遍历 若该像素点的幅值低于threshold_low,说明不是边缘点，去除，置为黑色 若该像素点的幅值高于threshold_high,说明是边缘点，加强，置为白色 返回值： output_img ''' visited = np.zeros_like(nms) output_img = nms.copy() h, w = output_img.shape[0], output_img.shape[1] def dfs(i, j): if i >= h or i < 0 or j >= w or j < 0 or visited[i, j] == 1: return visited[i, j] = 1 if output_img[i, j] > threshold_low: output_img[i, j] = 255 dfs(i - 1, j - 1) dfs(i - 1, j) dfs(i - 1, j + 1) dfs(i, j - 1) dfs(i, j + 1) dfs(i + 1, j - 1) dfs(i + 1, j) dfs(i + 1, j + 1) else: output_img[i, j] = 0 for y in range(h): for x in range(w): if visited[y, x] == 1: continue if output_img[y, x] >= threshold_high: dfs(y, x) elif output_img[y, x] <= threshold_low: output_img[y, x] = 0 visited[y, x] = 1 for y in range(h): for x in range(w): if visited[y, x] == 0: output_img[y, x] = 0 return output_img Canny滤波算子 def canny_filter(img: np.ndarray, threshold_low: int, threshold_high: int, sigma) -> np.ndarray: ''' canny滤波算子 返回值:smoothed_img, ga, nms_img, canny_img(前三者供比较) ''' # 高斯平滑 smoothed_img = gauss_filter(img, sigma) # sobel求导 gx, gy, ga, theta = sobel_filter(smoothed_img) # 非极大值抑制 nms_img = NMS(ga, theta) # 双阈值检测连接 canny_img = threshold_edge(nms_img, threshold_low, threshold_high) return smoothed_img, ga, nms_img, canny_img 实验结果 Sobel滤波结果 图像分析：原图以灰度模式读入后，x图，y图分别是sobel算子卷积后获得的图像在相应方向的导数值，会缺失另一个方向的边缘信息；direction图来自x，y两图像的各像素点平方和的根号，表示图像的梯度幅度，可视为sobel算子获得的边缘图；theta图像来自对direction各点的arctan值，范围为（-π，+π），用plt中的camp进行色彩映射。 Canny算子滤波结果 图像分析：原图在灰度模式读入后进行高斯模糊，获得更为柔和的smoothed_img，其中sigma对后续图像的细节留存量有影响，sigma越大，细节越少，当然也对噪点平滑力度更大；此时利用sobel算子求出图像梯度幅度，即ga图，噪点减少但图像边缘不够锐利；再进行非极大值抑制后获得nms_img, 图像边缘更加细致明确，但还有很多多余的细节；最后经过双阈值进行边缘检测与连接对重要边缘信息进行强化，所选的阈值范围决定筛选边缘信息的强度。 参考资料 知乎：边缘检测（Canny算子）实现原理 知乎：canny算子中的非极大值抑制是什么原理 博客园：python使用matplotlib:subplot绘制多个子图
TNND，终于到这里了 Hello World 什么经典开局 程序样例 [aweip@manjaro ~]$ mkdir bin; cd bin [aweip@manjaro ~]$ vim hello.sh #!/bin/bash # Program: # To shows "Hello World!" # History: # 2022/07/24 AweiP First release PATH=/bin:/sbin:/usr/bin:/usr/sbin:/usr/local/bin:/usr/local/sbin:~/bin export PATH echo -e "Hello World! \a \n" exit 0 第一行 #!/bin/bash 在宣告这个 script 使用的 shell 名称 程序内容的说明： 除了第一行的『 #! 』是用来宣告 shell 的之外，其他的 # 都是『批注』用途 ，第二行以下就是用来说明整个程序的基本数据。 主要环境变量的宣告 ： 务必要将一些重要的环境变量设定好 主要程序部分 ：这个例子当中，就是 echo 那一行 执行成果告知 (定义回传值) ：利用 exit 这个指令来让程序中断，并且回传一个数值给系统 执行结果 [aweip@manjaro ~]$ sh hello.sh Hello World ! 简单加减乘除求余(即+-*/%) [aweip@manjaro ~]$ vim multiplying.sh #!/bin/bash # Program: # Inputs 2 integer numbers; program will cross these two numbers. # History: # 2022/07/24 PATH=/bin:/sbin:/usr/bin:/usr/sbin:/usr/local/bin:/usr/local/sbin:~/bin export PATH echo -e "Input 2 numbers\n" read -p "first: " firstnu read -p "second: " secnu total=$((${firstnu}*${secnu})) echo -e "\nThe result of ${firstnu} x ${secnu} is ==> ${total}" script 的执行方式差异 (source, sh script, ./script) 直接执行的方式来执行 script sh test.sh 使用这种执行方式时， script 是在子程序的 bash 内执行 ，当test.sh 执行完毕后， 子程序 bash 内的所有数据便被移除 （变量作用域仅在fork出的子程序中） 利用 source 来执行脚本：在父程序中执行 source test.sh 善用判断式 利用 test 指令的测试功能 例子：test -e /dmtsai && echo "exist" || echo "Not exist" 关于某个档名的『文件类型』判断 测试的标志 代表意义 -e 该『档名』是否存在？ (常用) -f 该『档名』是否存在且为文件(file)？ (常用) -d 该『文件名』是否存在且为目录(directory)？ (常用) 关于文件的权限侦测，如 test -r filename 表示可读否 (但 root 权限常有例外) 测试的标志 代表意义 -r 侦测该档名是否存在且具有『可读』的权限？ -w 侦测该档名是否存在且具有『可写』的权限？ -x 侦测该档名是否存在且具有『可执行』的权限？ -u 侦测该文件名是否存在且具有『SUID』的属性？ -g 侦测该文件名是否存在且具有『SGID』的属性？ -s 侦测该档名是否存在且为『非空白文件 ​ ....... 利用判断符号 [ ]