CS111 Lecture 1 Scribe Notes

Enforced prerequisites for this class:

• CS 32 - you can program (in C)
• CS 33 - you can program at the machine level (including x86 assembly)
• CS 35L - basic software construction

Recommended prior coursework:

• CS 131 - programming languages
• CS M151B - architecture
• CS 118 - networking (note that CS111 is a pre-req here)

Time spent on this class (hours/week):

	Official Numbers (registrar)	Actual Numbers (reality)
Lecture	4	3.7
Lab (discussion)	2	1.7
Outside Study	9	20

There are 18 lecture sessions.

Each highlighted category adds up to 1/3 of the final grade.

Item	Count	Fraction of Grade (each)	Notes
Midterm	1	1/9	100 minutes (in class). Open-book/-note, but no electronics.
Final	1	2/9	180 minutes. Open-book/-note, but no electronics.
Labs	4	1/12 (1/3 total)	Teams of 1 or 2. Teams can be different each time.
Mini-labs	2	1/15 (2/15 total)	To be done solo. 'WeensyOS' on syllabus.
Design problem	1	1/15 (2/15 total)	Can be done in teams of 2. Pick 1 of 4 labs to extend. Include a report.
Scribe notes	1	1/20	Can be done in teams of 4. Due on CourseWeb one week after the corresponding lecture.
Research paper	1	1/15	2-3 pages summarizing recent work done in an open area of operating systems; topics will be suggested later.

Due Dates, Late Policy:

• Assignments are due at 23:59:59 on the dates listed in the syllabus.
• Scribe notes are due one week after the lecture.
• Drop-dead date: Friday, June 6, is the last day for submitting assignments.
• If an assignment is turned in after the deadline, a penalty of 2^(N-1) percent off the assignment is applied, where N is the number of days/partial days since the deadline. For example, there will be a penalty of 1% for turning in an assignment from one second after the deadline to 23:59:59 the next day.

Background: N virtual servers run atop a real server with a file system. One directory exists for each virtual server in root. Users of one virtual server can only see the contents of that virtual server’s directory.
Virtual servers are backed up from the server (which has root access) using the command: tar -cf of /dev/rmt (tape storage device). This walks through the entire tree, finds all files, and stores the files sequentially to tape.
Virtual servers (e.g., virtual server 5) can be restored by technicians using the command: tar –xf /dev/rmt/vm5. This should only grab files found in sub-tree vm27.

Security Flaw: An attacker can read files off another virtual server. In this example, the victim is vm6. Naive idea: Use a symlink: ln -s ../vm6/etc/passwd myfile. This doesn't work because if you try to cat /myfile, the system resolves to no such file.

The exploit:

1. cd /
2. Make a regular file: echo foo > myfile
3. While the virtual server is being backed up (tar is being run):
   1. Remove regular file: rm myfile
   2. Quickly replace regular file with a symbolic link to a file located on a different virtual server: ln –s /vm6/etc/passwd
4. After the backup is done, call and ask a technician to restore your virtual server, because you 'accidentally' wiped all of your data.

The tar command normally does not copy the file pointed to by a symbolic link; it normally just records the file pointed to. Since the file created in step 2 is a regular file, when tar is run, tar sees the regular file and proceeds to copy it. If this regular file is removed and then replaced with a symbolic link before tar has had a chance to copy the regular file, tar will copy the file pointed to by the symbolic link (which it has access to because it is run from the real server). This file can then be restored to the attacker's virtual server by an unaware technician.

Background: The DNS (Domain Name System) maps URL addresses to IP addresses. Root servers located around the globe resolve URL requests down a certain number of levels. Root servers know about .edu and ucla.edu, but may not know about cs.ucla.edu, so they would ask a subsidiary server (e.g., dns.ucla.edu) to resolve cs.ucla.edu.
The problem with this system was that it took too long to resolve URL requests. The browser would appear hung up during the time it took to resolve a URL request. To speed up the URL resolution process, DNS servers were given a cache to store recently resolved addresses.

Security Flaw: A security hole results from a design flaw; a DNS cache can be "poisoned" (the IP address for a URL stored in the cache is incorrect), so that users who ask that DNS server to resolve that specific URL will be given an incorrect IP address. Steps:

1. Ask a DNS server to resolve a URL address not within its cache (most likely an uncommon URL, for example llb.com)
2. Send a forged IP address to the DNS server at the right time--before the root server's response is received, so that the DNS server will store the forged IP address in its cache.

Here, only one URL can be hijacked at a time. However, in 2008, Dan Kaminsky discovered how to make the attack more plausible by hijacking an entire domain instead of individual IP addresses. There is not yet a complete fix for this vulnerability.

operating system, American Heritage Dictionary (4th ed., 2000):
software designed to control the hardware of a specific data processing system in order to allow users and application programs to make use of it.
Among other shortcomings of this definition, the word 'specific' suggests very obsolete technologies, before cross-machine software.

From Encarta: master control program of a computer.
'Who's in charge?'

From Wikipedia (602065231, 05:09, 31 March 2014):
A collection of software that manages computer hardware, resources and provides common services for computer programs.

The best definition of 'operating system' seems to be from Wikipedia. The operating system has taken a step away from controlling and towards managing.

Textbook's definition: A system is a set of interconnected components that has a specified behavior observed at the interface within its environment.

Trade-offs. After you achieve a goal in one part of your system, other aspects of your system will become at least slightly worse.

Example: Sorting a somewhat large array.
We want to sort a 1-GB array of 2^20 entries that are 1KiB each.

We could do a quicksort: qsort(a, I<<20, I<<10, cmp). This is O(N log N).

However, it would be faster to quicksort an index array of 4-byte integers holding pointers to each element in the array: qsort(i, I<<20, sizeof(int), cmp')
This way, the copying overhead is reducted by a factor of 256. However, there are a number of drawbacks:

• If you store in an array this way, later accesses aren't sequential
• Uses 0.5% more RAM
• More complicated
• cmp' function is slower than cmp
• Dereferencing slowness afterwards to access sorted elements

Not everything scales at the same rate.

Economies of scale: Adam Smith used the example of a pin factory to show the advantages of division/specialization: A town can produce many more pins if a few people form a pin factory to handle the entire supply of pins, as opposed to if everyone makes their own pins as needed.
Waterbed effect disadvantage: There will be some waste/overproduction.

There are also diseconomies of scale: For example, a 100Base-T switch. 100Base-T networks use a star topology. This sort of network layout is cheap for n<=8, but no more nodes. Really big (>1000) switches of this sort are not produced, because the central part of the switch does not scale well.
As another example, O(N^2) algorithms also do not scale well.

Example: A change in a module of a system affects other parts, which may lead to a crash. This happens all the time in chaotic systems (including things like earthquakes), and we’ll deal with this in the next lecture. An important requirement of most system designs is to limit the impact of failures.