rCore-OS Lab1: A Trilobite OS

Well I admit that I am too lazy to transfer this article back to Chinese.

I am going to practice my operating system skills by learning through the rCore-OS of THU, which is a pretty OS written in Rust. It is Linux compatible and its target platform is RISC-V. In this article, we will build a very naive but bare metal program.

0x00 Get rid of standard library dependencies

This is the first challenge for any software developer start moving to system development: You can not rely on ANY standard libraries (glibc, uclibc, klibc or any other implementations), since the OS itself is the one responsible for providing these libs. Let’s try to get rid of them.

In Rust and C/C++ (and almost all programming languages), before running into main(), the execution environment will do some initialization work, where the std library and other standard libraries (GNU libc) may be used. Thus we have to tell Cargo there is no main and std in our target.

// os/src/main.rs
#![no_std]
#![no_main]

And we need to explicitly write a _start() function, which is the entry Cargo is looking for.

// os/src/main.rs
#[no_mangle]
extern "C" fn _start() {
    // Nothing here now
}

Besides, Cargo requires us to provide panic_handler or it will not compile. Usually the std will take care of that but now we have to manually add a panic_handler.

// os/src/lang_items.rs
use core::panic::PanicInfo;

#[panic_handler]
fn panic(_info: &PanicInfo) -> ! {
    // Nothing here now
}

Note that the rust-core can be used (and very useful) on bare metal.

Next, we need to make it possible to run our program directly on CPU without any OS support.

0x01 Make the CPU run it

For an odinary program, running it is easy: All you have to do is type it’s name in a shell and hit Enter, or double-click the exe file in Windows. That ease is benefiting from the OS. As we are creating an OS, things can get a little more complicated. Let’s first think about what will happen when the CPU starts to working.

The bootloadr for QEMU can be found at: https://github.com/itewqq/rCore-dev/tree/main/bootloader

When the CPU (riscv64 emulated by QEMU in our case) is powered on, the other general registers of the CPU are cleared to zero, and the PC register will point to the 0x1000 location. This 0x1000 location is the first instruction executed after the CPU is powered up (a small piece of boot code solidified in the hardware), and it will quickly jump to 0x80000000, which is the first instruction of the BootLoader program – RustSBI. After the basic hardware initialization, RustSBI will jump to the operating system binary code memory location 0x80200000 (for QEMU) and execute the first instruction of the operating system. Then our written operating system starts to work.

About the SBI: SBI is an underlying specification for RISC-V. The relationship between the operating system kernel and RustSBI, which implements the SBI specification, is somewhat like the relationship between an application and the operating system kernel, with the latter providing certain services to the former. However, SBI provides few services and can help the OS kernel to perform limited functions, but these functions are very low-level and important, such as shutting down the computer, displaying strings, and so on. If RustSBI provides services, then the OS kernel can call them directly.

So it’s clear that we have to put our built OS at the 0x80200000 address (for QEMU). By default, Cargo adopts a usermode memory layout which is not we expected, for example we will not get a entry address at 0x80200000 in the generated binary. To address that we need a custom linker script to make every section’s location right:

OUTPUT_ARCH(riscv)
ENTRY(_start)
BASE_ADDRESS = 0x80200000;

SECTIONS
{
    . = BASE_ADDRESS;
    skernel = .;

    stext = .;
    .text : {
        *(.text.entry)
        *(.text .text.*)
    }

    . = ALIGN(4K);
    etext = .;
    srodata = .;
    .rodata : {
        *(.rodata .rodata.*)
        *(.srodata .srodata.*)
    }

    . = ALIGN(4K);
    erodata = .;
    sdata = .;
    .data : {
        *(.data .data.*)
        *(.sdata .sdata.*)
    }

    . = ALIGN(4K);
    edata = .;
    .bss : {
        *(.bss.stack)
        sbss = .;
        *(.bss .bss.*)
        *(.sbss .sbss.*)
    }

    . = ALIGN(4K);
    ebss = .;
    ekernel = .;

    /DISCARD/ : {
        *(.eh_frame)
    }
}

Then we force Cargo to use it in linking:

// os/.cargo/config
[build]
target = "riscv64gc-unknown-none-elf"

[target.riscv64gc-unknown-none-elf]
rustflags = [
    "-Clink-arg=-Tsrc/linker.ld", "-Cforce-frame-pointers=yes"
]

继续阅读“rCore-OS Lab1: A Trilobite OS”

MIPS PWN 入门

MIPS是一种采取精简指令集(RISC)的指令集架构,突出特点是高性能,广泛被使用在许多电子产品、网络设备、个人娱乐设备与商业设备上,在路由器领域也被广泛应用。虽然今年MIPS所属公司已经宣布放弃对该架构继续进行研发设计,但是其作为x86、arm之后的第三大CPU架构阵营,现在市面上仍有大量的MIPS架构的产品,尤其是路由器芯片。此外,MIPS在学术界也非常受到追捧,很多超算竞赛冠军的设计方案都是MIPS的。就目前来看,MIPS的安全研究还是相对较为有意义的。

MIPS架构基础知识

常用汇编与流水线操作 在MIPS PWN中所常用到的汇编指令如下表所示:

image.png

MIPS架构为精简指令集, 常见的MIPS芯片流水线操作为五级, 如下图

wiki-Fivestagespipeline.png

其中IF =指令提取,ID =指令解码,EX =执行,MEM =存储器访问,WB =寄存器写回. 垂直轴是连续的指令: 横轴是时间. 在图示的情况中,最早的指令处于WB阶段,而最新的指令正在进行指令提取. 对于跳转/分支指令, 当其到达执行阶段且新的程序计数器已经产生时, 紧随其后的下一条指令实际上已经开始执行了. MIPS 规定分支之后的指令总是在分支目标指令之前执行,紧随分支指令之后的位置称为 分支延迟槽. 在没有任何可用操作时,延迟槽将填充空指令(nop)占位. 例如下面这段MIPS汇编代码中,
“`move $a0, $s1“`会在“`jalr“`跳转前执行

.text:0007F944                 move    $t9, $s0
.text:0007F948                 jalr    $t9              
.text:0007F94C                 move    $a0, $s1

这个特性在我们查找gadgets和构造payload的时候要多注意, 这也是MIPS上的PWN相比x86架构来说较为特殊的点之一.

寄存器与调用约定 常用的MIPS寄存器作用如下:

  • “`\$a0“` – “`\$a3“`:函数调用时的参数传递,若参数超过 4 个,则多余的使用堆栈传递
  • “`\$t0“`-“`\$t7“`:临时寄存器
  • “`\$s0“` – “`\$s7“`:保存寄存器,使用时需将用到的寄存器保存到堆栈
  • “`\$gp“`:全局指针,用于取数据(32K访问内);“`\$sp“`:栈指针,指向栈顶
  • “`\$fp“`:栈帧指针;“`\$ra“`:存储返回地址

MIPS的调用约定为被调用者实现堆栈平衡, 参数 1 ~ 4 分别保存在
“`\$a0“` ~ “`\$a3“` 寄存器中,剩下的参数从右往左依次入栈. MIPS的栈布局如下图所示, 某寄存器在堆栈中的位置不是确定的, 例如“`\$ra“`在某函数栈中的偏移是“`\$sp“`+N, 而在另一函数栈中的偏移是“`\$sp“`+M.

image.png

当CPU执行跳转到被调用函数后, 被调用函数将会开辟新的栈帧, 根据本函数内是否还有其他函数调用决定是否将
“`\$ra“` 入栈, 再将“`\$sp“` 入栈. 对于“`\$ra“`, 当本函数为叶子函数(函数内无其他函数调用), 则“`\$ra“`不入栈, 否则将“`\$ra“`入栈. 对于栈溢出攻击而言, 当函数为非叶子函数时, 可以直接通过覆盖栈上的“`\$ra“`来劫持控制流.

缓存非一致性
继续阅读“MIPS PWN 入门”

任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B

前言

难以置信, 遇到这个问题竟然是因为做一道CTF Reverse的题, 实际上我以前打ACM的时候都没有写过任意模数的K次剩余这种东西. 最简单的模质数的K次剩余的例题是
“`HDU 3930 Broot“`, 进阶版本(模任意奇数的K次剩余)的例题是“`BZOJ 2219 数论之神“`, 而终极版本(任意模数的K次剩余)似乎可以交的题只有“`51nod 1123“`, 截至本文写作时只有44个AC. 然而这个CTF题本身就有50多个通过了. ~~CTF>ACM 实锤~~ (暴论)

其实是因为这个Reverse的题里面幂指数是质数,所以会跟模数互质,然后就可以用RSA的方法来做了. 其次该题目更多的工作在于去花指令混淆上, 而非算法破解.

OK那么就来看一下这个问题从最简单的版本到终极版本怎么求解吧…

模质数的K次剩余

已知$a$, $b$, $p$, 求使得

$$
x^{a} \equiv b \quad(\bmod \ p)
$$

成立的所有 $x$. 其中 $p$ 是质数.

由于 $p$ 是质数, 所以 $p$ 存在原根 $g$ , 此时对于模 $p$ 意义下的任意数 $w$ ($0\le w \le p-1$) 存在唯一的 $i$ ($0\le i \le p-1$) 使得 $w\equiv g^i\quad(\bmod \ p)$.

由此可以将最终的答案用 $g$ 来表示: $x=g^{c}$, 带入上式转化为求解

$$
(g^{c})^{a}\equiv (g^{a})^c\equiv b \quad(\bmod \ p)
$$

此时 $g$, $a$, $b$, $p$, 已知, 只需要解出来 $c$. 此时相当于求解离散对数, 使用 Baby-Step-Giant-Step 可以在 $\mathcal{O}(\sqrt{p})$ 时间内得到一个特解 $x_0 \equiv g^{c} \quad(\bmod \ p)$.

在已知一个特解的情况下求出所有解是简单的, 由原根的性质可知 $g^{\varphi(p)}\equiv 1 \quad(\bmod \ p)$, 因此:

$$
\forall t \in \mathbb{Z}, x^{a} \equiv g^{c \cdot a+t \cdot \varphi(p)} \equiv b \quad(\bmod \ p)
$$

因此所有的解为:

$$
\forall t \in \mathbb{Z}, a \mid t \cdot \varphi(p), x \equiv g^{c+\frac{t \cdot \varphi(p)}{a}} \quad(\bmod p)
$$

上面幂次部分要能整除必须要有$\frac{a}{\operatorname{gcd}(a, \varphi(p))} \mid t$, 可以设 $t=\frac{a}{\operatorname{gcd}(a, \varphi(p))} \cdot i$, 于是得到所有的解为:

$$
\forall i \in \mathbb{Z}, x \equiv g^{c+\frac{\varphi(p)}{\operatorname{gcd}(a, \varphi(p))} \cdot i} \quad(\bmod p)
$$

HDU 3930 Broot 代码:

继续阅读“任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B”

Codeforces Round #700 (Div. 2) 题解

链接 https://codeforces.com/contest/1480

闲着没事翻了翻以前的博客,感觉自己之前的文章质量太低了,尤其是很多题解东一篇西一篇的非常乱,以后类似题解之类的就整套整套地写好了。

image.png

Round 700 Div.2给人的感觉是手速场,基本上没有什么很需要思考的点。
继续阅读“Codeforces Round #700 (Div. 2) 题解”

逆向分析某X视频APP通信协议

声明:破解他人的软件是违法行为,本文的逆向工程仅供学习研究用途。

最近朋友间流行一个国产的X视频App,其特点是使用国内网络便可以自由地观看视频。但是支持国内网络环境的在线服务往往会承担被审查的风险,因此有点好奇他的视频存储和获取是怎么实现的,于是便对其APP客户端进行了逆向分析。本文出发点仅仅是技术学习,因此所有与该App有关的信息都将打码。在下文中将称该App为JK,其对应的几个关键api接口部分字符使用x替换。

  • 目标平台:Android
  • 分析对象:JK.apk,Version=3.13.2
  • 分析工具:Charles,Jadx,IDA Pro,Frida

TL;DR 最终对JK App的视频请求协议逆向分析结果如下图所示:


APP视频获取协议逆向结果

继续阅读“逆向分析某X视频APP通信协议”

[差分][前缀和][细节] codeforces 1452E Two Editorials

codeforces 1452E Two Editorials

题目链接:https://codeforces.com/problemset/problem/1452/E

题意:一次比赛中 2 个dalao来讲题,总共有 $m$ 个选手来听讲,题目总数为 $n$ ,编号从 $1$ 开始到 $n$ 。每个dalao都只会选择连续的 $k$ 个题目进行讲解,两个人可以交叉。而每一个听讲的人都只会选择听一个dalao的讲题,这是由哪个dalao讲的题目中覆盖的他感兴趣的题目数量较多决定的,第 $i$ 个人想听的题目范围是 $[l_i,r_i]$ . 问两个大佬怎么选可以使得两个人所获得的得分加一块最多,其中得分是他们讲的每个题目收听的人数。

数据范围:$1 \leq n, m \leq 2000,1 \leq k \leq n$, $1 \leq l_{i} \leq r_{i} \leq n$

输出:两个人采取某种讲题方案后加一块能获得的最大分数

题解:

把每个听讲的人看成一条线段,问题可以抽象成在数轴上找到两个长度为k的区间使得上述分数最大。从数据范围来看,可以 $O(n^2)$ 枚举两个人讲题的起点,之后如果能使用滑动窗口动态维护, $O(1)$ 更新答案这题就做完了。那么自然可以想到枚举第一个人讲题的范围之后,第二个人的范围在遍历的过程中动态维护。如果我们使用前缀和来做的话,是可以 O1 得到两个人各自的和的,但是题目要求两个人之间如果有均覆盖到的听讲者,那么只有覆盖的较多的讲题人才有得分。这是一个对每个听众来说取max的操作,但是我们要在数轴的维度来说要做到 O1 动态维护就是比较难的。我们假设第一个人对于自己内部的的得分和为sum1.第二个人的得分为sum2.先不考虑取max的情况,此时sum1和sum2都可以通过简单的积分前缀和得到。我们考虑把这个max操作转化成几个不同数组的差分和求和操作。简单的画一下第二个样例,就可以意识到当枚举到第一个人的讲课区间 [i,iend] 的时候,听众对应的线段可以分为三类:(1)在iend之前结束的;(2)在iend之后开始的;(3)在iend之前开始,在iend之后结束的。
继续阅读“[差分][前缀和][细节] codeforces 1452E Two Editorials”

[娱乐][代理][CF] 使用cloudflare worker反向代理codeforces,支持登录和提交代码评测

作为一个退役的ACM选 (蒟)手(蒻),偶尔也会回codeforces上做做题娱乐娱乐。。

但是codeforces作为一个外国网站,在国内访问的话速度十分感人,你懂的。

虽然绝大多数 业内人士 都有不可描述的方法让自己访问到国外的网站,但是还是有一些刚接触比赛的同学需要一个比较快的访问途径。当然国内之前也有一些dalao自制的codeforces镜像,例如 https://codeforc.es/ 等。

我这里提供一种免费自行搭建codeforces反向代理的方法,借用了cloudflare免费提供的serveless服务:workers。关于workers的简单介绍可以参见官方的blog:

Cloudflare Workers的名称来自Web Workers,更具体地说是Service Workers,一个用于在web浏览器后台运行并拦截HTTP请求的脚本的W3C标准API。Cloudflare Workers是针对相同的标准API编写的,但是是在Cloudflare的服务器上运行,而不是在浏览器中运行。
以下是您可以使用的工具:
– 使用最新的标准语言功能执行任意JavaScript代码。
– 拦截和修改HTTP请求和响应URL,状态,标头和正文内容。
– 直接从您的Worker响应请求,或将其转发到其他地方。
– 将HTTP请求发送到第三方服务器。
– 以串行或并行方式发送多个请求,并使用响应组成对原始请求的最终响应。
– 在响应已经返回到客户端之后发送异步请求(例如,用于记录或分析)。
– 控制其他Cloudflare功能,例如缓存行为。
– 显然我们要达到反向代理的目的只需要处理两件事:
– 处理客户端的请求,修改参数之后发送给真正的服务端(codeforces.com)
– 处理codeforces.com返回的响应,修改参数后发给客户端
继续阅读“[娱乐][代理][CF] 使用cloudflare worker反向代理codeforces,支持登录和提交代码评测”

[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组$a$, $1 \le a_i \le 10^6$ ,满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1

MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1

本文同步发布于本人知乎文章https://zhuanlan.zhihu.com/p/258405554

1. Introduction

MIT 6.858 是麻省理工学院一门著名的计算机安全系列课程。跟其相类似的其他名校的安全类课程还有Standford CS155OSU 系统安全与软件安全等。虽然是比较硬核的大学课程,其实验环境对于现实生活中的安全攻防来说也还是相对较为理想的。不过对于想尽快地熟悉基础的系统安全攻防知识的新手来说,这些实验的容量已经足够了。整个课程有4次实验和一个最终的Final Project,其中所有的实验都围绕一个由课程教师构建的一个名为zoobar的web application来展开。四次实验的主要内容是:

  • Lab 1: you will explore the zoobar web application, and use buffer overflow attacks to break its security properties.
  • Lab 2: you will improve the zoobar web application by using privilege separation, so that if one component is compromised, the adversary doesn’t get control over the whole web application.
  • Lab 3: you will build a program analysis tool based on symbolic execution to find bugs in Python code such as the zoobar web application.
  • Lab 4: you will improve the zoobar application against browser attacks.

即分别围绕缓存区溢出攻击、权限分离、符号执行和浏览器攻击四个主题来展开。我将在blog里陆续更新之后的内容。这一次我们先来看第一次实验,Buffer Oveflows
继续阅读“MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1”

麻省理工学院(MIT)研究生学习指导–怎样做研究生 [转载]

麻省理工学院(MIT)研究生学习指导
怎样做研究生
本文的主旨是解释如何做研究。我们提供的这些建议,对于研究本身(阅读、写作和程序设计)、理解研究过程以及开始研究(方法论、选题、选导师和情感因素),都是极具价值的。

  1. 简介

这是什么?
并没有什么神丹妙药可以保证在研究中取得成功,本文只是列举了一些可能会对研究有所帮助的非正式意见。

目标读者是谁?
本文主要是为新入学的研究生而写。

如何使用?
要精读完本文,太长了一些,最好是采用浏览的方式。很多人觉得下面的方法很有效:先快速通读一遍,然后选取其中与自己当前研究项目有关的部分仔细研究。
本文被粗略地分为两部分。第一部分涉及研究者所需具备的各种技能:如阅读,写作和程序设计等等。第二部分讨论研究过程本身:即研究究竟是怎么回事,如何做研究,如何选题和选导师,如何考虑研究中的情感因素。很多读者反映,从长远看,第二部分比第一部分更有价值,也更让人感兴趣。

本文的主要内容包括: 继续阅读“麻省理工学院(MIT)研究生学习指导–怎样做研究生 [转载]”