Reflections on Trusting Trust

参考 Reflections on Trusting TrustRunning the “Reflections on Trusting Trust” Compiler

The moral is obvious. You can’t trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code.

步骤一

如何编写一个自我复制程序Quine)?使用 Java 编写的代码如下,还是有点难的。最开始想直接打印,但是打印语句需要包含完整的程序,而完整的程序又包含打印语句,是一个循环依赖的过程。要把循环解开,就只能在字符串中包含基本的行,经过特殊处理得到正确的输出,最简单的方式是使用占位符。似乎不能使用转义字符,因为反斜杠在字符串中也需要转义,所以根本没办法打印出相同的行。更短的示例可以参考 Quine Programs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {
public static void main(String[] args) {
char n = 10;
String t = new String(new char[]{'"', '"', '"'});
String s = """
public class Main {
public static void main(String[] args) {
char n = 10;
String t = new String(new char[]{'"', '"', '"'});
String s = %s;
System.out.printf(s, t + n + s + t);
}
}
""";
System.out.printf(s, t + n + s + t);
}
}

步骤二

如何构建一个自编译的编译器(即由要编译的语言编写的编译器),是一个先有鸡还是先有蛋的问题,解决方案是引导Bootstrapping)。简单来说,首先使用机器支持的语言编写编译器 A 的源代码,编译器 A 可以编译目标语言的子集。然后使用目标语言的子集编写编译器 B 的源代码,经过编译器 A 编译得到编译器 B 的二进制文件。之后就可以不断重复,得到支持完整目标语言的编译器。

1
2
if (c == 'v') return 11; // 旧编译器可以识别
if (c == 'v') return '\v'; // 新编译器才能识别

论文提到的例子是,在目标语言中添加 \v 符号,表示垂直制表符。由于旧编译器不识别该符号,所以使用垂直制表符的 ASCII 码 11 扩展旧编译器的源代码,旧编译器编译扩展后的源代码得到新编译器,新编译器就能够识别 \v 符号。

步骤三

修改编译器,以匹配指定模式,如果匹配则错误地编译源代码,这是特洛伊木马(Trojan horse)。可以在编译器中插入指定的匹配模式(后门,backdoor),使其匹配 login 命令的源代码。如果用户使用该编译器编译 login 命令,则命令会被错误编译,从而可以使用指定的密码登录系统的任意用户。

最关键的是,如果再添加一个针对编译器自身的匹配模式,在识别到当前正在编译编译器时,将特洛伊木马插入到新编译器中,则可以实现类似步骤二中的“学习”过程。也就是说,即使编译器 B 的源代码是正确的,使用包含以上两个匹配模式的编译器 A 编译,得到的编译器 B 的二进制文件依然包含两个特洛伊木马。最终,编译器 B 仍会错误地编译 login 命令,而编译器 B 的源代码却是正确的。

论文提到,将特洛伊木马插入到新编译器中,使用的是步骤一的自我复制程序。我看半天才理解这句话,可以这么想,特洛伊木马需要获取自身的代码,然后插入到新编译器的特定位置,类似自我复制需要输出自身的代码。

快速傅里叶变换(FFT)

参考 Reducible

问题

如何求两个 \(n\) 次多项式 \(A(x)\) 和 \(B(x)\) 的乘积 \(C(x)\)?最简单的方式是使用乘法分配律对每个系数做乘积,时间复杂度为 \(O(n^{2})\)。

$$ A(x)=a_{0}+a_{1}x^{1}+\cdots+a_{n-1}x^{n} \\ B(x)=b_{0}+b_{1}x^{1}+\cdots+b_{n-1}x^{n} \\ C(x)=c_{0}+c_{1}x^{1}+\cdots+c_{2n}x^{2n} $$

另一种想法是:① 在多项式 \(A(x)\) 和 \(B(x)\) 上取 \(2n+1\) 个点 \(x_{i}\),其中 \(i=0,1,\cdots,2n\),求出对应的函数值。② 根据 \(C({x_{i}})=A(x_{i})\cdot B(x_{i})\),可以得到 \(C(x)\) 上的 \(2n+1\) 个点。③ 使用拉格朗日插值,化简得到 \(C(x)\) 的表达式。总时间复杂度为 \(O(n^{2})\),如果能够将 ① 和 ③ 的时间复杂度优化为 \(O(n\log{n})\),那么就能够降低总时间复杂度。

优化步骤 ①

可以发现,对于偶函数 \(f(x)=f(-x)\),对于奇函数 \(f(x)=-f(-x)\)。如果将多项式分解为偶函数和奇函数两部分,则可以可以利用对称性快速求点值。不妨设 \(n\) 为偶数,将 \(n-1\) 次多项式 \(P(x)\) 划分为偶函数和奇函数两部分。

$$ \begin{align}P(x)&=p_{0}+p_{1}x^{1}+\cdots+p_{n-1}x^{n-1} \\&=(p_{0}+p_{2}x^{2}+\cdots+p_{n-2}x^{n-2})+(p_{1}+p_{3}x^{3}+\cdots+p_{n-1}x^{n-1}) \\&=(p_{0}+p_{2}x^{2}+\cdots+p_{n-2}x^{n-2})+x(p_{1}+p_{3}x^{2}+\cdots+p_{n-1}x^{n-2})\end{align} $$

设 \(P_{e}(x)=p_{0}+p_{2}x^{1}+\cdots+p_{n-2}x^{\frac{n}{2}-2}\),\(P_{o}(x)=p_{1}+p_{3}x^{2}+\cdots+p_{n-1}x^{\frac{n}{2}-2}\),则 \(P(x)=P_{e}(x^{2})+xP_{o}(x^{2})\)。此时,如果取 \(n\) 个点 \(\pm x_{0},\pm x_{1},\cdots,\pm x_{\frac{n}{2}-1}\),则只需要计算 \(P_{e}(x_{i}^{2})\) 和 \(P_{o}(x_{i}^{2})\),就能够通过以下方式得到两个函数值。

$$ P(x_{i})=P_{e}(x_{i}^{2})+x_{i}P_{o}(x_{i}^{2}) \\ P(-x_{i})=P_{e}(x_{i}^{2})-x_{i}P_{o}(x_{i}^{2}) $$

所以,要求 \(P(x)\) 上的 \(n\) 个点值,等价于求 \(P_{e}(x^{2})\) 和 \(P_{o}(x^{2})\) 上的 \(\frac{n}{2}\) 个点值,即点 \(x_{0},x_{1},\cdots,x_{\frac{n}{2}-1}\) 的值。此时,原问题被分解为两个相同的子问题,并且子问题的大小只有原问题的一半,如果子问题能够按照原问题的方式继续分解,则可以得到时间复杂度为 \(O(n\log{n})\) 的算法。

但是,\(P_{e}(x^{2})\) 和 \(P_{o}(x^{2})\) 不能继续分解,因为定义域 \(x^{2}\geq 0\),点 \(x_{0}^{2},x_{1}^{2},\cdots,x_{\frac{n}{2}-1}^{2}\) 不构成正负对,也就不能利用对称性求点值。如果能够取到一组构成正负对的点,在子问题中所有正点依然构成正负对,那么就可以继续递推。此时,需要引入复数,例如,取点 \(\pm 1,\pm i\) 构成正负对,子问题中 \(1^{2},i^{2}\) 等价于 \(1,-1\) 依然构成正负对。

那么对于 \(n-1\) 次多项式,如何取满足条件的 \(n\) 个点?假设取某个点 \(z\),那么必然要取 \(-z\),在子问题中 \(z\) 变为 \(z^{2}\),那么必然要取 \(-z^{2}\),以此类推,假设 \(n\) 为 \(2\) 的幂(总是可以通过对高次项补系数 \(0\) 取到),则最终得到 \(z^{n}\)。也就是说,所有取值的 \(n\) 次方都相等,不妨设 \(z^{n}=1\),求解方程可以得到 \(n\) 个单位根,即为满足条件的 \(n\) 个点。

设复数 \(z=a+bi\),则极坐标表示为 \(z=r(cos(\varphi)+isin(\varphi))\),根据欧拉公式,有 \(z=re^{\varphi i}\)。要求 \(z^{n}=1\),即求 \(r^{n}e^{\varphi ni}=e^{2k\pi i}\),得出 \(r=1,\varphi =\frac{2k\pi}{n}\),所以 \(z=e^{\frac{2k\pi}{n}i}\),其中 \(k=0,1,\cdots,n-1\)。设 \(w_{n}=e^{\frac{2\pi}{n}i}\),则 \(n\) 个单位根分别为 \(w_{n}^{0},w_{n}^{1},\cdots,w_{n}^{n-1}\),它们将复平面中的单位圆 \(n\) 等分。

观察单位根的性质,有 \(w_{n}^{k}=-w_{n}^{k+\frac{n}{2}}\),\(w_{n}^{k}=w_{\frac{n}{2}}^{\frac{k}2}\),所以 \(w_{n}^{0},w_{n}^{1},\cdots,w_{n}^{\frac{n}{2}-1}\) 和 \(w_{n}^{\frac{n}{2}},w_{n}^{\frac{n}{2}+1},\cdots,w_{n}^{n-1}\) 构成正负对。在子问题中,\(w_{n}^{0},w_{n}^{1},\cdots,w_{n}^{\frac{n}{2}-1}\) 变为 \(w_{n}^{0},w_{n}^{2},\cdots,w_{n}^{n-2}\),等价于 \(w_{\frac{n}{2}}^{0},w_{\frac{n}{2}}^{1},\cdots,w_{\frac{n}{2}}^{\frac{n}{2}-1}\),前半和后半依然构成正负对,以此类推。从复平面的角度思考,更容易理解。

根据上述讨论,单位根的正负对性质,在所有子问题中都成立,所以求 \(n-1\) 次多项式 \(P(x)\) 的 \(n\) 个点值,可以使用递归分治的方式求解。当 \(n=1\) 时,多项式是常数,\(P(w_{1}^{0})\) 就是该常数值。当 \(n>1\) 时,如果已知 \(P_{e}(x^{2})\) 和 \(P_{o}(x^{2})\) 在 \(w_{n}^{k}\) 的点值,其中 \(k<\frac{n}{2}\),则利用之前推出的 \(P(x)=P_{e}(x^{2})+xP_{o}(x^{2})\) 公式可以得到以下两个函数值。

$$ P(w_{n}^{k}) =P_{e}(w_{n}^{2k})+w_{n}^{k}P_{o}(w_{n}^{2k}) \\ P(-w_{n}^{k}) =P(w_{n}^{k+\frac{n}{2}}) =P_{e}(w_{n}^{2k+n})+w_{n}^{k+\frac{n}{2}}P_{o}(w_{n}^{2k+n}) =P_{e}(w_{n}^{2k})-w_{n}^{k}P_{o}(w_{n}^{2k}) $$

优化步骤 ③

步骤 ① 是已知系数,求 \(n-1\) 次多项式 \(P(x)\) 在 \(n\) 个 \(n\) 次单位根位置的值,可以看作矩阵相乘的形式。

$$ \left[\begin{matrix}P(w_{n}^{0}) \\P(w_{n}^{1}) \\P(w_{n}^{2}) \\\vdots \\P(w_{n}^{n-1})\end{matrix}\right]=\left[\begin{matrix}w_{n}^{0} & w_{n}^{0} & w_{n}^{0} & \cdots & w_{n}^{0} \\w_{n}^{0} & w_{n}^{1} & w_{n}^{2} & \cdots & w_{n}^{n-1} \\w_{n}^{0} & w_{n}^{2} & w_{n}^{4} & \cdots & w_{n}^{2(n-1)} \\\vdots & \vdots & \ddots & \vdots \\w_{n}^{0} & w_{n}^{n-1} & w_{n}^{2(n-1)} & \cdots & w_{n}^{(n-1)(n-1)}\end{matrix}\right]\left[\begin{matrix}p_{0} \\p_{1} \\p_{2} \\\vdots \\p_{n-1}\end{matrix}\right] $$

步骤 ③ 是已知 \(n\) 个点值,求多项式的系数,可以看作上述变换的逆变换。

$$ \left[\begin{matrix}p_{0} \\p_{1} \\p_{2} \\\vdots \\p_{n-1}\end{matrix}\right]=\left[\begin{matrix}w_{n}^{0} & w_{n}^{0} & w_{n}^{0} & \cdots & w_{n}^{0} \\w_{n}^{0} & w_{n}^{1} & w_{n}^{2} & \cdots & w_{n}^{n-1} \\w_{n}^{0} & w_{n}^{2} & w_{n}^{4} & \cdots & w_{n}^{2(n-1)} \\\vdots & \vdots & \ddots & \vdots \\w_{n}^{0} & w_{n}^{n-1} & w_{n}^{2(n-1)} & \cdots & w_{n}^{(n-1)(n-1)}\end{matrix}\right]^{-1}\left[\begin{matrix}P(w_{n}^{0}) \\P(w_{n}^{1}) \\P(w_{n}^{2}) \\\vdots \\P(w_{n}^{n-1})\end{matrix}\right] $$
$$ \left[\begin{matrix}w_{n}^{0} & w_{n}^{0} & w_{n}^{0} & \cdots & w_{n}^{0} \\w_{n}^{0} & w_{n}^{1} & w_{n}^{2} & \cdots & w_{n}^{n-1} \\w_{n}^{0} & w_{n}^{2} & w_{n}^{4} & \cdots & w_{n}^{2(n-1)} \\\vdots & \vdots & \ddots & \vdots \\w_{n}^{0} & w_{n}^{n-1} & w_{n}^{2(n-1)} & \cdots & w_{n}^{(n-1)(n-1)}\end{matrix}\right]^{-1}=\frac{1}{n}\left[\begin{matrix}w_{n}^{0} & w_{n}^{0} & w_{n}^{0} & \cdots & w_{n}^{0} \\w_{n}^{0} & w_{n}^{-1} & w_{n}^{-2} & \cdots & w_{n}^{-(n-1)} \\w_{n}^{0} & w_{n}^{-2} & w_{n}^{-4} & \cdots & w_{n}^{-2(n-1)} \\\vdots & \vdots & \ddots & \vdots \\w_{n}^{0} & w_{n}^{-(n-1)} & w_{n}^{-2(n-1)} & \cdots & w_{n}^{-(n-1)(n-1)}\end{matrix}\right] $$

如果将步骤 ① 表示为 \(FFT(w_{n},p_{0},p_{1},\cdots,p_{n-1})\),则步骤 ③ 为 \(IFFT(w_{n},P(w_{n}^{0}),P(w_{n}^{1}),\cdots,P(w_{n}^{n-1}))=\frac{1}{n}FFT(w_{n}^{-1},P(w_{n}^{0}),P(w_{n}^{1}),\cdots,P(w_{n}^{n-1}))\)。