—— Summon, Light!

一、研究背景

Google为了向广大的用户提供服务，拥有很多的数据中心和三种不同类型的网络，包括数据中心网络（具有逻辑上集中的控制平面）、软件定义的广域网B4（支持多种流量类别并使用集中式流量工程）以及全球广域网B2（用于面向用户的流量，采用了分散式流量工程）。

二、文章要解决的主要问题

面对规模、网络演变和复杂性，保持高可用性是一项挑战。例如，对于面向用户的流量，Google的内部可用性目标是每月停机时间不超过几分钟。

维持这种高可用性尤其困难，是由于以下三个原因。首先是规模和异构性：Google的网络遍布全球，在这种规模下，网络中某些组件的故障很普遍。第二个是演进的速度：网络不断变化以响应不断增长的流量需求以及新服务的推出。第三是管理复杂性：尽管控制平面已经在发展以应对网络的复杂性，但是管理平面却没有跟上步伐。

三、文章提出的主要技术方法

对于每一次重大的故障，以反思报告的形式详细地记录故障事件、原因、解决方法。本文主要是对反思报告进行分析，从中汲取分布式系统高可用性设计原则。

本文将故障事件分为六类不同的影响类别：黑洞，其中到目标集或来自一组来源的访问量完全被黑洞；高优先级流量的高/低丢包；较低优先级流量的流量高/低丢包；以及，没有影响。为了区分高/低丢包，我们基于可用性目标设计了丢失阈值。

所有网络故障的根本原因可以直接分为硬件故障，软件错误和配置错误，但是，从这种粗略的分类来看，除了增加硬件冗余，加固软件，避免配置错误的一般建议之外，很难得出有关如何应对这些根本原因的具体见解。因此，本文对根本原因进行了更细致的分类，从而为提高网络可用性提供了有用的见解。

首先将根本原因分为数据平面、控制平面、管理平面三大类。当然，故障可以是多个根本原因导致的。

一、研究背景

在线社交网络（Online social network，OSN）的数据可以用来做很多的事情，比如推荐新的朋友，针对性的广告，还有社交关系的分析。

但若直接共享OSN的原始信息，就很有可能会泄露用户的隐私和敏感信息，所以在共享前需要先对原始信息进行匿名化处理。

二、文章要解决的主要问题

差分隐私（Differential Privacy）正广泛应用在匿名化中，利用差分隐私的方法对真实数据加噪声后，敌手将无法区分出真实数据和带噪声数据。

由于不能直接对图结构添加噪声，通常需要将图抽象为某一个模型，并转化为能数值表示的数据。

已有的dK模型和HRG模型，分别是从特定的角度去描述原来的图，度数分布信息无法描述聚集系数信息，聚集系数信息也无法描述度数分布信息。

那么，能否找出一种实用指标全面地描述原来的图，并且找到一种匿名化机制使得这种实用指标能保持下来？

三、文章提出的主要技术方法

本文认为，持续同调（Persistent Homology）作为一种新颖的方法，可以在不同距离分辨率和不同维度下跟踪全图拓扑特征，可以将持续同调与差分隐私相结合，来保持图的实用指标。

听说考得好写在简历里很不错，正好也保持一下写题的水平。
仅含题解，代码详见Github，喜欢的话点个star呀。

201912

201912-1 报数

水题。按提意模拟一下。

201912-2 回收站选址

水题。由于一定要在垃圾处建垃圾站，枚举所有垃圾即可。

201912-3 化学方程式

算是词法解析题吧，啥都不管，直接top-down一把梭。

201912-4 区块链（20分）

感觉是个sb题，但是最开始数据结构没设计对，后面就改不对了，一直Wrong Answer。。。

这两天复习组合数学，仔细品了品八种放球问题，感觉还是挺有意思的。
放球问题的基本表述是：将$n$个球放入$m$个盒子中（每个球都必须放到某个盒子里），有多少种方案？
由于有$3$个方面的条件，所以总共有$2^3=8$种，按熟悉程度分别介绍吧。

1. 将$n$个无区别的球放入$m$个有区别的盒子中，不允许空盒

使用经典的插空法，把$m-1$个板插入$n-1$个空中，自然划分出$m$个区，对应$m$个有区别的盒子，如图所示。

方案数$=C_{n-1}^{m-1}$。
该问题等价于求$\sum_{i=1}^{m}{x_{i}}=n$的正整数解的个数。

2. 将$n$个无区别的球放入$m$个有区别的盒子中，允许有空盒

使用经典的隔板法，把$m-1$个板与$n$个球放在一起。“允许有空盒”意味着板和板可以紧邻地放在一起，这时候就要换一种思维方式，也就是从位置的角度来考虑，在$n+m-1$个位置中选$m-1$个放隔板，剩下的$n$个放球。

方案数$=C_{n+m-1}^{m-1}$。
该问题等价于求$\sum_{i=1}^{m}{x_{i}}=n$的非负整数解的个数，通过换元法可以转化为问题1。

3. 将$n$个有区别的球放入$m$个有区别的盒子中，允许有空盒

第1个球有$m$种选择，第2个球也有$m$种选择，第3个……。
方案数$=m \times m \times \cdots \times m = m^{n}$。

4. 将$n$个有区别的球放入$m$个无区别的盒子中，不允许空盒

这是第二类斯特林数的定义。
方案数$=S(n,m)$，递推式为$S(n,m)= S(n-1,m-1) + S(n-1,m) \times m$，包含了两种情况，

1. 第$n$个球单独放一个盒子，也就是之前的$n-1$个球放入了$m-1$个盒子；
2. 第$n$个球放入已经存在的盒子，由于不能有空盒，此时$m$个盒子内部的情况肯定是不一样的，所以可以直接乘以$m$。

Oblivious Transfer一般译为“不经意传输”，也有人译为“茫然传输”。

在不经意传输中，有两个参与者Alice（发送方）和Bob（接收方）。Alice输入一个位 $b\in \{ 0,1 \}$，Alice和Bob通过一定方式交互后，Bob只能以$\frac{1}{2}$的概率接收到 $b$（对Alice的隐私性），而且，Alice无法知道Bob是否得到了 $b$（对Bob的隐私性）。Bob可以确信地知道他是否得到了 $b$（正确性）。

不经意传输还有其他的形式，如$2$取$1$不经意传输协议:

Alice的输入为$2$个位 $b_{0},b_{1} \in \{ 0,1 \}$，Bob的输入位为$c\in \{ 0,1 \}$，Alice和Bob通过一定方式交互后，Bob可以得到 $b_{c}$（正确性），Alice无法知道Bob的选择 $c$（对Bob的隐私性），Bob无法同时得到 $b_{0}$ 和 $b_{1}$（对Alice的隐私性）。

同理也可以得到$n$取$1$不经意传输协议和$n$取$m$不经意传输协议的概念。

不经意传输协议是设计其它密码协议的基础，可以构造更为复杂的协议，如不经意电路计算。

以上转载自：不经意传输（Oblivious Transfer）

各个课的作业都做得太久了，
但是又无法接受明明还有时间却不把一件事情搞好。

组合数学的小论文用 $\LaTeX$ 写的，写了好久，
但是竟然没找到一个正常的中文期刊模板，只好自己随便搞了。

姑且还是放上来吧。

本文要解决的问题是网络中的负载均衡问题，什么是负载均衡呢？负载均衡是云计算的基础组件，是网络流量的入口，是一个既经典又重要的问题。用户输入的流量通过负载均衡器按照某种负载均衡算法把流量均匀的分散到后端的多个服务器上，接收到请求的服务器可以独立的响应请求，达到负载分担的目的。从产品形态角度来说，可以分为硬件负载均衡和软件负载均衡。硬件负载均衡器常见的有F5、A10，它们的优缺点都比较明显，优点是功能强大，有专门的售后服务团队，性能比较好，缺点是缺少定制的灵活性，维护成本较高；现在的互联网公司更活跃的思路是通过软件负载均衡来实现，这样可以满足各种定制化需求，常见的软件负载均衡有Nginx、Haproxy。本文中实现的Ananta也属于一种软件负载均衡。

本文的作者都是微软的员工，主要动机是在保证Web服务仍然高并发高可用的情况下尽可能地减小负载均衡的花费，为此他们设计并实现了Ananta。这是一种在商品硬件上运行并且支持横向扩展（scale-out）的layer-4（connection-level）负载均衡器，可以同时满足了多租户云计算环境中的性能、可靠性和操作要求。

在具体介绍之前首先需要介绍本文中的一些基本概念：

• DIP：private Direct IP address，私有的直接IP地址，专用网内部的任何一台虚拟机或者本地机器都会被分配一个DIP，即仅在本专用网内使用的专用地址；
• VIP：public Virtual IP address，公有的虚拟IP地址，一般情况下一个服务会被分配一个VIP；
• 服务：在本文中，“服务”和“租户”将作为可替换的概念；
• NAT：Network Address Translation，网络地址转换，当专用网内部需要提供对外服务时，外部地址发起主动连接，由路由器或者防火墙上的网关接收这个连接，然后将连接转换到内部，此过程是由带有公网IP的网关替代内部服务来接收外部的连接，然后在内部做地址转换，此转换称为NAT，主要用于内部服务对外发布；
• SNAT：Source Network Address Translation，源网络地址转换，内部地址要访问公网上的服务时（如web访问），内部地址会主动发起连接，由路由器或者防火墙上的网关对内部地址做地址转换，将内部地址的私有IP转换为公网的公有IP，网关的这个地址转换称为SNAT，主要用于内部共享IP访问外部；
• 横向扩展：横向扩展是一种可以通过简单地添加更多类似容量的设备来处理更多带宽的模型；
• 纵向扩展：纵向扩展是一种为了处理更多带宽需要更高容量的设备的模型。

Ananta的设计原则有两条：

1. 横向扩展网络内（in-network）处理：传统的NAT和负载平衡算法需要了解所有活动的（active）流，因此同一VIP的所有流量都必须通过相同的负载平衡器，这迫使负载均衡器只能进行纵向扩展。而路由器遵循横向扩展模型，这是因为它们不维护任何需要跨路由器同步的每流（per-flow）状态。Ananta的设计将负载均衡所需的网络内功能简化，使得多个网络元素可以同时处理同一VIP的数据包，而无需每流状态的同步。
2. 将工作负载卸载（offload）到端系统：端系统中的管理程序已经可以进行高度可扩展的网络处理。Ananta利用此分布式可扩展平台，将重要的数据平面和控制平面功能卸载到终端系统中的管理程序。

Ananta是一个松散耦合的分布式系统，包含三个主要组件：Ananta管理员（Ananta Manager，AM)，多路复用器（Multiplexer，Mux)和主机代理（Host Agent，HA)，如图2所示。

AM实现了Ananta的控制平面。他提供配置VIP的API，他会根据VIP的配置来配置HA和Mux池，并且监视DIP运行状况的任何更改。AM还负责跟踪Mux和主机的健康状况，并采取适当的行动。

5 函数调用约定

创建一个栈帧的最重要步骤是主调函数如何向栈中传递函数参数。主调函数必须精确存储这些参数，以便被调函数能够访问到它们。函数通过选择特定的调用约定，来表明其希望以特定方式接收参数。此外，当被调函数完成任务后，调用约定规定先前入栈的参数由主调函数还是被调函数负责清除，以保证程序的栈顶指针完整性。

函数调用约定通常规定如下几方面内容：

1. 函数参数的传递顺序和方式

最常见的参数传递方式是通过堆栈传递。主调函数将参数压入栈中，被调函数以相对于帧基指针的正偏移量来访问栈中的参数。对于有多个参数的函数，调用约定需规定主调函数将参数压栈的顺序（从左至右还是从右至左）。某些调用约定允许使用寄存器传参以提高性能。

2. 栈的维护方式

主调函数将参数压栈后调用被调函数体，返回时需将被压栈的参数全部弹出，以便将栈恢复到调用前的状态。该清栈过程可由主调函数负责完成，也可由被调函数负责完成。

3. 名字修饰（Name-mangling）策略

又称函数名修饰（Decorated Name）规则。编译器在链接时为区分不同函数，对函数名作不同修饰。

若函数之间的调用约定不匹配，可能会产生堆栈异常或链接错误等问题。因此，为了保证程序能正确执行，所有的函数调用均应遵守一致的调用约定。

0x0 Toddler’s Bottle

0x00 fd

首先稍微学习一下file descriptor，然后登录上去看看到底是什么情况。

1
2
3
4
5
6
7
8
9
10
11

fd@ubuntu:~$ ls -alh
total 40K
drwxr-x---  5 root   fd   4.0K Oct 26  2016 .
drwxr-xr-x 92 root   root 4.0K Aug 12 10:28 ..
d---------  2 root   root 4.0K Jun 12  2014 .bash_history
-rw-------  1 root   root  128 Oct 26  2016 .gdb_history
dr-xr-xr-x  2 root   root 4.0K Dec 19  2016 .irssi
drwxr-xr-x  2 root   root 4.0K Oct 23  2016 .pwntools-cache
-r-sr-x---  1 fd_pwn fd   7.2K Jun 11  2014 fd
-rw-r--r--  1 root   root  418 Jun 11  2014 fd.c
-r--r-----  1 fd_pwn root   50 Jun 11  2014 flag

可以看到除了隐藏文件就是 fd fd.c flag ，所以目标就是获取flag中的内容然后提交到网站上。
但是由于权限问题我们是不能直接查看flag文件的，实际上在不能成为root的情况下只有通过可执行文件fd才有可能操作flag文件，因为fd带有Set UID权限，在它运行的时候可以暂时获得fd_pwn这个用户的权限。那么剩下的那个fd.c文件可以推测是fd文件的源代码。
另外，fd用户对当前目录没有write权限，所以要通过查看fd.c分析fd的行为。

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char buf[32];
int main(int argc, char* argv[], char* envp[]){
        if(argc<2){
                printf("pass argv[1] a number\n");
                return 0;
        }
        int fd = atoi( argv[1] ) - 0x1234;
        int len = 0;
        len = read(fd, buf, 32);
        if(!strcmp("LETMEWIN\n", buf)){
                printf("good job :)\n");
                system("/bin/cat flag");
                exit(0);
        }
        printf("learn about Linux file IO\n");
        return 0;

}

程序里用到的file descriptor竟然不是open返回的，而是根据命令行参数变换出来的，也就是说要给出一个数字，使得这个数字作为文件描述符对应的文件里的内容是特定的字符串。这在正常情况下是不可能的，因为一个文件的文件描述符只在同一个进程里是确定的，更何况当前用户也不能新建文件。但是UNIX下确实有三个文件的文件描述符是绝对确定的，它们就是 stdin stdout stderr 。所以只要让fd变量等于0，我们就可以输入任意的内容，我觉得至少有三种方法：

1. 非常普通的输入0x1234对应的十进制数，./fd 4660
2. 看起来太fancy但是实际上非常有用的命令，涉及到shell语言的弱引用以及python的命令行执行字符串

1

./fd `python -c "print 0x1234"`

3. gdb可用，应该可以直接set fd甚至set buf（没有实际尝试）