Abstractions and Bootstrapping

Review of Last Lecture

Another problem in building an OS is COMPLEXITY.

This problem arises because of Moore's Law, which states that the number of transistors in an integrated circuit (IC) approximately doubles every 2 years.

Hard Drive growth is an example of incommensurate scaling, in which capacity increases faster than speed. The speed of disk drives was 3600 RPM at its lowest to 7200 RPM.

d(technology)/dt = k* technology (the rate of growth of technology is proportional to technology.

Very first successful computer: UNIVAC1
Almost all circuits had error-correcting because there were no simulators to simulate the computer.

Second version of the UNIVAC1 was the UNIVAC2. Many of the error-correcting redundancy was eliminated by simulating the UNIVAC2 on the UNIVAC1.

The Trouble with Complexity

As systems become more complex, there can be more components that can have bugs and lead to insecurities.

Virtual Server Business

Suppose we run a virtual server business and offer server backup as a service. The virtuals servers reside on a single physical server with one filesystem. Each virtual server has a unique share that is only accessible by itself.

How do we exploit the service and access another client's backups?

The backup command is:

$cd tr
$tar -cf /backup/ | *  #(-c: create; -f: file)

Exploit

While tar is running:

#create random file
	$echo ordinary > foo
 	# tar will opendir(",") readdir (",") lstat("foo")
#make foo a symbolic link to other client's backup file (obtain by guessing)
	$ln -sf /path/to/victim foo
	# tar will open("foo",...) and will copy other user’s file to your backup.

Fix

Use O_NOFOLLOW flag to operate on the file itself, not on the target of the symlink This flag is set for the open system call and will set the open system call to not follow/open symbolic links.

Layout of Memory

When the machine is turned on (i.e. power button is pressed), the instruction pointer points to the Basic Input/Output System (BIOS). As shown in the diagram above, the BIOS is hard coded into a read-only part of memory.

Basic Input/Output System

The BIOS is the first piece of software that is run when the computer is turned on. Historically, the BIOS was stored in read-only memory (ROM) that could not be modified. The BIOS is presently stored in electronically erasable programmable read-only memory (EEPROM). This makes the BIOS modifiable and allows it to be easily updated with new versions. The BIOS serves a number of purposes when the computer boots up. These purposes include:

1. Testing the system
2. Looking for attached devices
3. Looking for a device containing a Master Boot Record (MBR)

BIOS Chain Loading

Bios chain loading refers to pulling in multiple sectors from a device into ram and then running the instructions or data. Typically, the BIOS loads the MBR, which then loads the Volume Boot Record (VBR). The VBR then loads and runs the operating system. The chain-like architecture of loading the operating system can be clearly seen.

Master Boot Record

The MBR is usually the first sector of a partitioned device that is run when a computer boots up after the BIOS has ran. Historically, the MBR is 512 bytes on a x86 machine.

As seen above, the first 446 bytes contains x86 machine code that is run after the BIOS initializes the computer. The next 64 bytes is the partition table, which is divided into four 16-byte parts. The partition table contains information such as the status (e.g. bootable), type of partition, starting sector, and size (in sectors). The last two bytes are the signature bytes with the value 0x55 and 0xAA, respectively. Since an Intel machine is little endian, these bytes appear as 0xAA55.

Input/Output to a Device

In order for the CPU to read and write from and to a device, respectively, hardware registers are used. The CPU can set control information through a device’s hardware register and read and write using different device hardware registers. An illustration is given below:

An example of code for communicating with a device and reading from is shown below:

//Code below will wait until the device is ready and free. 0x1f7 is the status register of device

while((inb(0x1f7) & 0xc0) != 0x40)  //void wait_for_ready(void)
	continue;

outb( 0x1f2, 1); //register on device indicating # of registers to be read.

// Four code statements below send the beginning sector number to disk controller
outb( 0x1f3, s & 0xff);
outb( 0x1f4, (s>>8) & 0xff);
outb( 0x1f5, (s>>16) & 0xff);
outb( 0x1f6, (s>>24) & 0xff);

outb( 0x1f7, 0x20); //0x1f7 is the command  register on the device and 0x20 is the read sectors command.

wait_for_ready(); // wait until the disk controller has the necessary data

insl (0x1f0, a, 128); //Takes data from disk controller and stores into ram
// 0x1f0 is the data register
// a is the pointer to memory
// 128 is the number of words to read (count of 32-bit words)

Powering On the Computer

As stated above, when the power button is pressed, the BIOS initializes the computer, finds the MBR, and runs the code in the MBR. This is achieved by first copying the MBR into ram. The BIOS reads the 1st sector (the MBR) of the device that contains the MBR to Random Access Memory (RAM) at memory address: 0x7c00. A jump statement is then issued (jmp 0x7c00) and the MBR is run from RAM.

The Paranoid Professor's Very Secure Word Count (VSWC) Program

Suppose you are commissioned by a very paranoid professor to build a very secure word count program for a top-secret proposal he is writing on a file. He does not trust anybody except for you, so you will have to write all the code.

1. Intel core i3-2130 (3 MiB Cache)
2. 4 GiB dual channel DDR3
3. 1TB hard drive, 7200 rpm SATA
4. 3 MiB cache
5. Boots in x86 mode

Input:
An ascii text file on disk.
A word is defined as [A-Za-z]+

Output:
The number of words in the text file displayed on the monitor.

Issues:
1. Power switch - How to run our program when the power switch is pressed? Answer: Bootstrapping sequence.
2. Disk input - How to read the text file from disk?
3. Screen output- How to display the number of word count on the monitor?

Assuming now that VSWC is too big to fit in the MBR (i.e. too big to fit in 446 bytes), it is necessary to pull in multiple sectors into ram to run our program. This is referred to as "chain loading".

VSWC - Master Boot Record

Our application is 45 sectors long and occupies sectors 1200 through 1244 on disk. The task of the MBR is to read these sectors into RAM and run our application. The pseduocode/code in the 446 bytes of the MBR, which is written into 0x7c00 is:

0x7c00: 

for (i=0; i < 45; i++)
	read_sector(i+1200, (char *) 0x150000 + i * 512);
goto 0x150000;
copy of read_sector

void read_sector(int s, char *a) {
	//Programmed I/O (very traditional)
}

VSWC - The Application

Now that the VSWC application is in RAM, it can be run by the CPU. The VSWC program is given by:

#define isalpha(x) s a[x]
static const char a[256] = {...}; //contains valid bytes

void main(void) {
	int nwords = 0; // # of words in program
	bool inword = false; //true if still in word
	for (;;) {
		char buf[512]; 
		read_sector(1,000,000 , buf);
		for (int j = 0; j < 512; j++) {
			bool thisalpha = isalpha((unsigned char) buf[j]); //if valid char then true
			nwords += thisalpha & ~inword; //if end of word, increment by 1
			inword = thisalpha;
		}
			if (!buf[j]) { 
				report_answer(nwords); //report at the end
				return;
			}
	}
}

void report_answer (int n) { // This code will write number of words to stdout
	unit16_t p = (unit16_t *) 0xb8014;
	do {
	*p-- = ‘0’ + n % 10;
	n /= 10;

	} while (n);
}

To output to the monitor, a memory address is written into in RAM. This memory address contains the information that will be outputted to the screen.

Conclusion

At this point, the VSWC program is complete and professor is able to count the number of words in his file. However, this approach to running our program does not scale up well and is difficult to make changes to our program