I’ve always been curious about the internal implementations of operating systems. I recently deployed kanidm in my home lab, and I’ve leaned a lot about how does linux authentication works during this process. These paragraph is licensed under CC-BY-NC-SA 4.0. I’m writing this post to share my thoughts and share my translation of this fantastic blog from Firstyear in Chinese.
The Unix access rights flags setuid and setgid (short for set user identity and set group identity) allow users to run an executable with the file system permissions of the executable’s owner or group respectively and to change behaviour in directories.
While I was learning Operating Systems at my school, it suddenly occurred to me that I don’t know how sudo works. Based on my little knowledge of Linux, I made the following assumption:
There should be a syscall for elevating privileges
sudo collects user’s password, and pass it to the syscall
However, almost immediately, I found some problems of my assumption:
sudo asks for the password of the current user, not the root user; and who is allowed to sudo is stored in sudoers
So the syscall for elevating privileges should be able to know who can do that
But it is unlikely that the syscall reads the sudoers file
sudo supports controlling which command a user is allowed to run
This is too complicated to be integrated into the kernel.
After some digging, I found the syscall setuid. It is able to set the uid of the current process. After some further searching, I found that this syscall is only for lowering the permissions: You have to have CAP_SETUID to run it. Then, in a scenario like sudo, when does the permission “elevation” happens?
After some trial, I discovered that when sudo is asking for password, the uid of it’s process is already 0, which means that the binary file sudo have something unique which makes it can directly be run as root. At this point, the answer is quite obvious: the only reasonable answer is that the permission is stored in the file system. Again, after some searching, I found that the file system maintains some special permission other than regular rwx. sudo uses setuid:
The Unix access rights flags setuid and setgid (short for set user identity and set group identity) allow users to run an executable with the file system permissions of the executable’s owner or group respectively and to change behaviour in directories.
So, the permission is temporarily elevated to root (who is the owner of sudo). sudo itself can determin whether the user is able to maintain the root permission or switch to other users. That is also why sudo breaks if you run chmod -R 755 /usr/bin.
This my first understanding of linux authentication system.
国际上，知名的编译器有 GNU （Gnu is Not Unix) 组织的 『GCC （the GNU Compiler Collection）』是Linux中最知名的编译器，也是世界范围内应用最广泛的编译器，支持C、C++、Objective-C、Fortran等多种语言。由UIUC研发，并被苹果公司广泛应用的『LLVM编译基础设施（Low-Level Virtual Machine Compiler Infrastructure）』通过分离编译器前后端并通过LLVM这一中间语言桥接，实现了多种语言与ISA支持，并提供强大的优化能力。除了上述两个开源的编译器之外，也有大量闭源的编译器被广泛应用：由Intel公司开发的 『ICC （Intel C++ Compiler）』主要面向Intel平台，由于其出色的定向（面向Intel x86和amd64架构CPU）的优化能力以及向量化（vectorization）能力，被广泛应用在HPC场景。由微软公司开发的『MSVC（MicroSoft Virtual C++）』主要面向Win/x86场景，随后适配amd64以及arm32、arm64架构，作为Win 32开发的主要编译器，也得到了广泛的应用。
现有的『国产』编译器中，『太极（Taichi）』[2]收获了很多的关注。作为一门领域特定的编程语言（Domain Specific Programming Language），其具有优秀的GPU开发能力，相较CUDA等传统库，更容易上手、使用。另一个获得广泛关注乃至争议的语言是『木兰』。木兰作为一款面向嵌入式平台的小型编译器，由于在宣传上的失误以及广大群众对于『中芯』等项目的恐惧，木兰受到了很大的批评以及指责。笔者个人认为，单从技术上来看，在面向嵌入式平台的同时提供基于Python的『套皮』模拟器，是十分正常且合理的，并不能因其使用了Python而受到批评。
HU Y. The taichi programming language[C/OL]//SIGGRAPH ’20: ACM SIGGRAPH 2020 Courses. Association for Computing Machinery, 2020: 1–50. https://doi.org/10.1145/3388769.3407493. ↩︎
It is well known that we should not change the problem statement during the contest. But, we also know that a company named “Hua***” liked to change problem statement during the contest .
There were some breathtaking errors in the problem statements during the 2021 ICPC Asia Regionals Online Contest (I). So, naturally, we needed to change these statements.
For example, problem A needs change. As we all know, the word “lexicographic” means "order of the dictionary(字典序), ‘a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols.’ ", but somehow the person who wrote this problem misinterpreted the word as “ascending”.
Naturally, during reasonable contests, what he needs to do is to update the testcase data, changing it from ascending order to lexicographic order, matching the problem statement, then rejudge all submissions of
this problem. But, he doesn’t think it that way. “Why changing testcase data while we can change the problem statement?” Surely he didn’t know that submitting “Wrong Answer” would add penalty(罚时) to the team’s time cost. I mean, otherwise, why would he do this？
Can you help him change all “lexicographic” to “ascending”?
Input
The first line of input contains a integer $n$. $(1 \leq n \leq 100)$.
In the following $n$ lines, each line contains a string. It is guaranteed that the length of the string is less than $100$ characters, and the string only contains a to z.
Output
Output updated problem statements, replace all lexicographic by ascending.
Examples
Example 1
Input
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 print the labels of all the busiest nodes in lexicographic order separated by spaces
Output
1 2 3 4 5 6 7 8 9 10 11 12 13 14
print the labels of all the busiest nodes in ascending order separated by spaces
Example 2
Input
1 2
1 whoalexicographic
Output
1
whoalexicographic
In the first example, we replace “lexicographic” on the 10th line to
“ascending”.
In the second example, we do nothing because we don’t need to replace
word containing “lexicographic”.
