Lecture 2: Abstractions and bootstrapping
Prof. Eggert

Note prepared by: Yarong Guo and Shangcheng Ying

Top

A Problem in Building an OS: Complexity

This problem arises because of Moore's Law which states that number of transistors on an integrated chip at min cost doubles every 2 years. Not only chips, disk drives capacity (disk size, not i/o speed) is also getting larger at a fast speed. However, because of the effect of incommensurate scaling, it becomes hard to balance all the resources and to get the most out of it and there's a gap between hardware capacity and design capability.


  • Moore's Law

  • Hard drive capacity

The good news is that technology grows exponentially or d(technology)/dt = k×technology . This is because people can use advanced technology to develope more advanced technology. A better computer that can do faster computation can solve more complicated or bigger problems. For example, the very first successful computer UNIVAC had an Error Correcting Circuitry (ECC) for almost every chip in it. They had to have all the ECCs because they didn't have simulators and they were not sure what kinds of errors would occur. To make it simple, they just added ECCs. When simulater was later developed, they were able to throw away many ECCs by simulating.

Top

Server Hacking Example (tar Exploitation)


  • A physical server with 3 virtual servers

A example of the trouble caused by complexity is the virtual server business. Several virtual servers run on one physical server and the physical server has only one physical file system. Let's assume it's an ordinary unix file system and the virtual server provider usually does a backup of the files on the server. A common way to do it is to use the tar command.

$ cd /sr
$ tar –cf /backup/1 *

This process can be exploited to hack into the server and get other's file. The idea here is to exploit tar command. Suppose we have a file foo in our directory before tar is running. When tar tries to create a tar ball, it will do following commands:

opendir(",");//opens a directory
readdir(…);  //get all the files in the directory
lstat("foo");//get file status

At this step, the lstat function will follow the symbolic link. In order to hack into the system, we can use this simple command.

$ ln –sf /path/to/victim foo //replace foo with a symbolic link to victims file.

The idea here is to replace the actual file with a symbolic link to the victim's file right before tar opens and reads the file to make a backup:

open("foo");
...

Then later, the hacker can simply tell the administrator that he screwed up his file and needs that file and the administrator will get the hacked file from the backup. To fix this problem, a flag O_NOFOLLOW was introduced. With this flag turned on, tar will not follow symbolic links and thus solved this problem.

Top

Very Secured Word Counter


  • Sample output of the VSWC.

Consider the case where we have a very paranoid professor who concerns a lot about software security and needs a word counter. He doesn't trust anybody except you. He wants you to write all the code and build a Very Secured Word Counter (VSWC) which behaves robustly and leaves no holes for attacking. Suppose this his desktop's spec:

The input is a plain ASCII text file on disk and the output is just a number on screen. The code runs after the user press the power button. Basically, the machine does nothing but powers up, count the word, output the number and done. A word consists of [A-Za-z]+ only. The solution here is to use bootstrapping.

Top

Bootstrapping

When a computer boots up, it will first run the Basic Input/Output System (BIOS), some codes that helps computer to load an actual OS. This system is supplied by computer manufacturer and there's a specific part of ROM that is used to run BIOS. When the computer boots up, the CPU will set the instruction pointer pointing to the start of BIOS and run it. Generally, BIOS will first do some sanity check for the system. If all tests passed, it will start looking for all connected devices. Meanwhile, it will trying to identify the device that contains a Master Boot Record (MBR).

MBR is a special 512 bytes of data that is usually located at the first sector of a disk or other bootable devices. It's 512 bytes long because a disk sector was 512 bytes in the old days. A MBR is divided into 3 parts with first 446 bytes of 0x86 machine codes, next 64 bytes of partitioning information and last 2 bytes of signature indicating this chunk of data is a MBR. The signature is 0x55 followed by 0xAA. The 64 bytes partition information is further divided into 4 16-bytes partition table. It has information about how this device should be partitioned for use. For example, use which part of disk for root system, swap, etc. Each entry starts with a 4 bytes that tells the status of the partition (e.g. bootable), starting sector, size and type (e.g. swap).

When the BIOS found a MBR, it will load the first 446 bytes machine codes into memory starting at address 0x7c00 and the last BIOS code will call jmp 0x7c00. These machine codes are something we can have control off since we have control over the disk. So we want to write a small program that loads our VSWC into memory and put his program in 446 bytes and put it in MBR. When MBR gets executed, the VSWC is loaded and ready for execution.

For normal situations, what MBR will do is it looks in its partition table to find the bootable partition. Load the first sector of partition which is the volume boot record (VBR) into RAM. VBR will then load OS. This process is also so known as chain loading.


  • RAM map right after computer boots

  • Loading MBR into memory

  • Master Boot Record
Top

Master Boot Record Implementation


  • Loading our program into RAM

  • i/o bus map

Since we have control over the disk storage we can pick arbitrary free space on the disk to put our VSWC. Let's assume our machine code is compiled and placed starting at sector 1200 and occupies 45 consecutive sectors. Our goal is to make MBR to load these 45 sectors into the memory. Again we can pick arbitrary free spaces on RAM and assume we place the code starting at address 0x150000. Here is the original C code:

The main routine:

for (int i = 0; i < 45; i++)
   read_sector(i + 1200, /*Read disk sectors to RAM*/
      (char*)(0x150000+i*512));
goto 0x150,000; /*Not valid C code, but GCC will accept it.*/

Auxiliary functions:

void read_sector(int s, char *a) {
/*Since there's no OS yet, we can't use any
    C libraries. The only available methods to do
    input and output is through programmed i/o.
    Which interacts directly with i/o devices via
    device's controller.*/
/*By default, the first register on a disk has
    number 0x1f7 which gives device status. 0x40
    is the status code when the device is ready
    for commands. So wait until device is ready*/

   while !(inb(0x1f7) & 0xc0) != 0x40)
      continue;
//We can replace this two lines with wait_for_ready();

//Device is ready. Tell it what to do.
   outb(0x1f2,1); //register indicating # of sectors

/*The sector we are looking for is in the variable s.
    But a register in device controller can only
    one byte of data. So 8 bits a time.*/
   outb(0x1f3, s & 0xff);        //Bottom 8 bits of the sector #
   outb(0x1f4, (s >> 8) & 0xff); //Next 8 bits of the sector #.
   outb(0x1f5, (s >> 16) & 0xff);
   outb(0x1f6, (s >> 24) & 0xff);

/*Now we've told the device we need 1 sector
    starting at sector # s. So tell the disk to
    go ahead and grab it. This is done by setting the
    command register and with code 0x20 which is
    READ_SECTORS command.*/
    outb(0x1f7, 0x20);
/*command register IS the same as status
    register. It's not a mistake. When you read from
    it, it's a status register. When you write into
    it, it's a command register.


/*The disk starts reading the sector
    which requires sometime to replace the disk
    arm, rotate to the correct sector, etc. So
    we need to wait for the disk to tell us the
    data is ready.*/
    wait_for_ready();


/*The disk got the data and put it i a
    buffer. We now need to transfer the data into
    RAM. The buffer can hold a 32-bit word. For a
    sector of 512 bytes, we need to copy 128 words.
    insl does the loading into memory.*/
   insl(0x1f0, a, 128);
}

void wait_for_ready(void) {
   while !(inb(0x1f7) & 0xc0) != 0x40)
      continue;
}
Top

Very Secured Word Counter Implementation


//No library available. Have to define it.
#define isalpha(x) sa[x]

//1 when the corresponding ascii code is a character
static const char sa[256] = {0,0,0,0,…,1,…,0,0,0};

void main(void) {
   int nwords = 0; //words counter.
   bool inword = false;

   for (;;) {
      char buf[512];



   /*Keep reading the file from disk. Assume it
       is placed starting at sector 100000 and ends
       with a null character.*/
      read_sector(1000000, buf);

      for (int j = 0; j < 512; j++) {
         if (!buf[j]) { //Reached end of file.
            report_answer(nwords);
            return;
         }
         bool thisalpha = isalpha((unsigned char) buf[j]);

         nwords += thisalpha & ~inword; //~ is same as ! but faster (saves some instructions)

         inword = thisalpha;
      }
   }
}

There's a part of RAM that is used to store display information. Basically an array of 25×80 bytes starting at address 0xb8000. Each character on screen takes two bytes, one for ASCII code and the other one for attribute - color usually. More information can be found here. Now we simply want the count to be displayed on the monitor. So we can put our number somewhere inside that part of RAM.

void report_answer(int n) {
   uint8_t * p = (uint8_t *) 0xb8014;
   do {
      *p-- = '0'+ n % 10;//Get the number digit by digit and put in p
      *p-- = 0x07;//Lightgrey letter on black screen.
      n /= 10;
   }while(n);
}
Top