Transcript Slides - Choong

Operating Systems
CS3013 / CS502
WEEK 6
PROTECTION
MULTIMEDIA SYSTEMS
REVIEW
Agenda
2
 Protection
 Multimedia Systems
 Review
Objectives
3
 Explain possible threats to the system
 Explain domain and access matrix
 Differentiate access control list and capabilities
Concepts
4
 Protection:
 Mechanisms and policy to keep programs and users from
accessing or changing stuff they should not do
 Internal to OS
 Chapter 14 in Silbershatz
 Security:
 Issues external to OS
 Authentication of user, validation of messages, malicious or
accidental introduction of flaws, etc.
 Chapter 15 of Silbershatz
The First Computer Virus
5
 Reading assignment:–
 Ken Thompson, “Reflections on Trusting Trust,”
Communications of ACM, vol.27, #8, August 1984, pp. 761-763
 Three steps
 Program that prints a copy of itself
 Training a compiler to understand a constant
 Embedding a Trojan Horse without a trace
Step 1 – Program to print copy of itself
6
 How do we do this?
 First, store character array representing text of
program




Body of program
Print declaration of character array
Loop through array, printing each character
Print entry array as a string
 Result: general method for program to reproduce
itself to any destination!
Step 2 – Teaching constant values to compiler
7
…
/* reading string constants */
if (s[i++] == '\\')
if (s[i] == 'n') insert ('\n');
elseif (s[i] == 'v') insert ('\v');
elseif …
 Question: How does compiler know what integer
values to insert for '\n‘, '\v‘, etc.?
Step 2 – Teaching constant values to compiler
8
 Answer: In the first compiler for this machine type, insert
the actual character code
 i.e., 11 (decimal) for ‘\v’, etc.
/* reading string constants */
if (s[i++] == '\\')
if (s[i] == 'n') insert ('\n');
elseif (s[i] == 'v') insert (11);
elseif …
 Next: Use the first compiler to compile itself!
Step 2 – Teaching constant values to compiler
9
 Result: a compiler that “knows” how to interpret the
sequence “\v”

And all compilers derived from this one, forever after!
 Finally: replace the value “11” in the source code of
the compiler with ‘\v’ and compile itself again
 Note: no trace of values of special characters in …
 The C Programming Language book
 source code of C compiler
 I.e., special character values are self-reproducing
Step 3 – Inserting a Trojan Horse
10
 In compiler source, add the text
if (match(sourceString, pattern)
insert the Trojan Horse code
where “pattern” is the login code (for example)
 In compiler source, add additional text
if (match(sourceString2, pattern2)
insert the self-reproducing code
where “pattern2” is a part of the compiler itself
 Use this compiler to recompile itself, then remove source
Step 3 – Inserting a Trojan Horse
11
 Result: an infected compiler that will
 Insert a Trojan Horse in the login code of any Unix system
 Propagate itself to all future compilers
 Leave no trace of Trojan Horse in its source code
 Like a biological virus:
 A small bundle of code that uses the compiler’s own
reproductive mechanism to propagate itself
Program Threats
12
 Trojan Horse
 Code segment that misuses its environment
 Exploits mechanisms for allowing programs written by users to be
executed by other users
 Spyware, pop-up browser windows, covert channels
 Trap Door
 Specific user identifier or password that circumvents normal security
procedures
 Could be included in a compiler
 Logic Bomb
 Program that initiates a security incident under certain circumstances
 Stack and Buffer Overflow
 Exploits a bug in a program (overflow either the stack or memory
buffers)
C Program with Buffer-overflow Condition
13
#include <stdio.h>
#define BUFFER SIZE 256
int main(int argc, char *argv[])
{
char buffer[BUFFER SIZE];
if (argc < 2)
return -1;
else {
strcpy(buffer,argv[1]);
return 0;
}
}
Layout of Typical Stack Frame
14
Modified Shell Code
15
#include <stdio.h>
int main(int argc, char *argv[])
{
execvp('\bin\sh', '\bin \sh', NULL);
return 0;
}
Hypothetical Stack Frame
After the attack
Before the attack
16
Effect
17
 If you can con a privileged program into reading a
string into a buffer unprotected from overflow, then
…
 …you have just gained the privileges of that program
in a shell!
Program Threats – Viruses
18
 Code fragment embedded in legitimate programs
 Very specific to CPU architecture, operating system,
applications
 Usually borne via email or as a macro
 E.g., Visual Basic Macro to reformat hard drive
Sub AutoOpen()
Dim oFS
Set oFS =
CreateObject(’’Scripting.FileSystemObject’’)
vs = Shell(’’c:command.com /k format
c:’’,vbHide)
End Sub
Program Threats
19
 Virus dropper inserts virus onto the system
 Many categories of viruses, literally many thousands of
viruses










File
Boot
Macro
Polymorphic
Source code
Encrypted
Stealth
Tunneling
Multipartite
Armored
Goals of Protection
20
 Operating system consists of a collection of objects
(hardware or software)
 Each object has a unique name and can be accessed
through a well-defined set of operations.
 Protection problem – to ensure that each object is
accessed correctly and only by those processes that
are allowed to do so.
Guiding Principles of Protection
21
 Principle of least privilege
 Programs, users and systems should be given just enough
privileges to perform their tasks
 Separate policy from mechanism
 Mechanism: the stuff built into the OS to make protection
work
 Policy: the data that says who can do what to whom
Domain Structure
22
 Access-right = <object-name, rights-set>
where rights-set is a subset of all valid operations
that can be performed on the object.
 Domain = set of access-rights
Conceptual Representation – Access Matrix
23
 View protection as a matrix (access matrix)
 Rows represent domains
 Columns represent objects
 Access(i, j) is set of operations that process executing
in Domaini can invoke on Objectj
Textbook Access Matrix
24
 Columns are access control lists (ACLs)
 Associated with each object
 Rows are capabilities
 Associated with each user, group, or domain
Unix & Linux
25
 System comprises many domains:–
 Each user
 Each group
 Kernel/System
 (Windows has even more domains than this!)
Unix/Linux Matrix
26
file1
file 2
file 3
device
domain
User/Domain 1
r
rx
rwx
–
enter
User/Domain 2
r
x
rx
rwx
–
User/Domain 3
…
rw
–
–
–
–
 Columns are access control lists (ACLs)
 Associated with each object
 Rows are capabilities
 Associated with each user, group, or domain
Changing Domains (Unix)
27
 Domain = uid or gid
 Domain switch via file access controls
 Each file has associated with it a domain bit (setuid bit).



rwS instead of rwx
When executed with setuid = on, then uid or gid is temporarily
set to owner or group of file.
When execution completes uid or gid is reset.
 Separate mechanism for entering kernel domain
 System call interface
General (textbook) representation
28
 Domains as objects added to Access Matrix
Practicalities
29
 At run-time…
 What does the OS know about the user?
 What does the OS know about the resources?
 What is the cost of checking and enforcing?
 Access to the data
 Cost of searching for a match
 Impractical to implement full Access Matrix
 Size
 Access controls disjoint from both objects and domains
ACLs vs. Capabilities
30
 Access Control List: Focus on resources
 Good if resources greatly outnumber users
 Can be implemented with minimal caching
 Can be attached to objects (e.g., file metadata)
 Good when the user who creates a resource has authority over
it
 Capability System: Focus on users
 Good if users greatly outnumber resources
 Lots of information caching is needed
 Good when a system manager has control over all resources
Both are needed
31
 ACLs for files and other proliferating resources
 Capabilities for major system functions
 The common OSs offer BOTH
 Linux emphasizes an ACL model


provides good control over files and resources that are file-like
Windows 2000/XP emphasize Capabilities
provides good control over access to system functions (e.g.
creating a new user, or doing a system backup…)
 Access control lists for files

…and good management, too!
32
 What do we need to know to set up a new user or to
change their rights?
 …to set up a new resource or to change the rights of
its users?
 …Who has the right to set/change access rights?
 No OS allows you to implement all the possible
policies easily.
Enforcing Access Control
33
 User level privileges must always be less than OS
privileges!


For example, a user should not be allowed to grab exclusive
control of a critical device
or write to OS memory space
 …and the user cannot be allowed to raise his
privilege level!
 The OS must enforce it…and the user must not be
able to bypass the controls
 In most modern operating systems, the code which
manages the resource enforces the policy
(Traditional) Requirements–System Call Code
34
 No user can interrupt it while it is running
 No user can feed it data to make it


violate access control policies
stop serving other users
 No user can replace or alter any system call code
 No user can add functionality to the OS!
 Data must NEVER be treated as code!
“Yeah, but …”
35
 No user can interrupt it while it is running
 Windows, Linux routinely interrupt system calls
 No user can feed it data to make it
 violate access control policies
 stop serving other users
 No user can replace or alter any system call code
 Except your average virus
 No user can add functionality to the OS!
 Except dynamically loaded device drivers
 Data must NEVER be treated as code!
 “One man’s code is another man’s data” A. Perlis
Saltzer-Schroeder Guidelines
36
 System design should be public
 Default should be no access
 Check current authority – no caching!
 Protection mechanism should be
 Simple, uniform, built into lowest layers of system
 Least privilege possible for processes
 Psychologically acceptable
 KISS!
Agenda
37
 Protection
 Multimedia Systems
 Review
Objectives
38
 Identify multimedia
 Explain JPEG and MPEG compression
 Explain OS issues relevant to multimedia
Multimedia Systems
39
 Requirements and challenges for audio and video in




computer systems
Systems for multimedia
Compression and bandwidth
Processor scheduling
File, disk, and network management
What is “multimedia”?
40
 Audio and video within a computer system


CD’s & DVD’s
Computer hard drive
 Live broadcast & web casts

Webcams, Skype, …
 Video on demand

Pause, fast forward, reverse, etc.
 Interactive meetings


Presentations with 2-way audio
Teleconferencing
 Interactive gaming
 …
Requirements
41
 “Smooth” audio and video
 Deterioration in quality >> jerky playback
 Note: human is more sensitive to jitter in audio than to jitter in
video!
 Audio/video on PC’s doing something else
 Multiple concurrent streams
 Video & multimedia servers
 TiVo, etc.
 Wide range of network bandwidths
System and OS Challenges
42
 Bandwidths and Compression
 Jitter
 Processor Scheduling
 Disk Scheduling
 Network Streaming
Some System Architectures
43
 Simple:
 Data paths for audio/video that are separate from
computational data paths
 Modern
 Fast system bus, CPU, devices
 Video server
 Disk farm and multiple streams
Video Server
44
 Multiple CPUs
 Disk farm
 1000s of disks
 Multiple high-bandwidth network links
 Cable TV
 Video on demand
 Internet
Why Compression? – Audio
45
 22,050 Hz  44,100 samples/sec
 16 bits per sample
 Two channels  176,000 bytes/sec
 1.4 mbits/sec
 Okay for a modern PC
 Not okay for 56 kb/sec modem (speed) or iPod (space)!
 MP-3 ≈ 0.14 mbits/sec (10:1)
 Same audio quality!
 Compression ratio varies with type of music
Why Compression? – Video
46
 “Standard” TV frame = 640 × 480 pixels @ 25-30
frames/sec (fps)

9,216,000 pixels/sec = 27,648,000 bytes/sec
 HDTV = 1280 × 720 pixels @ 30 fps
 82,944,000 bytes/sec
 Typical movie ≤ 133 minutes
 approx. 220 gigabytes!
 DVD holds ~ 4.7 gigabytes
 average of ~ 620 kilobytes/sec!
 “Standard” movie of 133 minutes requires serious
compression just to fit onto DVD
Video Compression Requirements
47
 Compression ratio > 50:1
 i.e., 220 gigabytes:4.7 gigabytes
 Visually indistinguishable from original
 Even when paused
 Fast, cheap decoder
 Slow encoder is okay
 VCR controls
 Pause, fast forward, reverse
Video Compression Standards
48
 MPEG (Motion Picture Experts Group)


Based on JPEG (Joint Photographic Experts Group)
Multi-layer
Layer 1 = system and timing information
 Layer 2 = video stream
 Layer 3 = audio and text streams

 Three standards

MPEG-1 – 352 240 frames; < 1.5 mb/sec ( < VHS quality)


MPEG-2 – standard TV & HDTV; 1.5-15 mb/sec


Layer 3 = MP3 Audio standard
DVD encoding
MPEG-4 – combined audio, video, graphics

2D & 3D animations
JPEG Compression
49
 Convert RGB into YIQ
 Y = luminance (i.e., brightness) ~ black-white TV
 I, Q = chrominance (similar to saturation and hue)
Reason: Human eye is more sensitive to
luminance than to color (rods vs. cones)
 Down-sample I, Q channels


i.e., average over 2×2 pixels to reduce resolution
lossy compression, but barely noticeable to eye
 Partition each channel into 8×8 blocks
 4800 Y blocks, 1200 each I & Q blocks
JPEG Compression
50
JPEG Compression
51
JPEG Compression
52
 Calculate Discrete Cosine Transform (DCT) of each
8×8 block
 Divide 8×8 block of DCT values by 8×8 quantization
table

Effectively throwing away higher frequencies
 Linearize 8×8 block, run-length encode, and apply a
Huffman code to reduce to a small fraction of
original size (in bytes)
Huffman Code
53
 Encoding Algorithm
 Order by frequency of characters and build a binary
tree
 Example


“aaaabbbccd”
“this is an example
of huffman code”
JPEG Compression
54
 Store or transmit 8×8 quantization table followed by
list of compressed blocks
 Achieves 20:1 compression with good visual
characteristics

Higher compression ratios possible with visible degradation
 JPEG algorithm executed backwards to recover
image

Visually indistinguishable from original @ 20:1
 JPEG algorithm is symmetric
 Same speed forwards and backwards
MPEG Compression
55
 JPEG-like encoding of each frame
 Takes advantage of temporal locality
 I.e., each frame usually shares similarities with
previous frame

encode and transmit only differences
 Sometimes an object moves relative to background
 find object in previous frame, calculate difference, apply
motion vector
Temporal Locality (example)
56
Consecutive Video Frames
MPEG Compression
57
 Three types of frames
 I-frame: Intracoded or Independent.
Full JPEG-encoded frame
 Occurs at intervals of a second or so
 Also at start of every scene


P-frame: Predictive frame


Difference from previous frame
B-frame: Bidirectional frame

Like p-frame but difference from both previous and next frame
I B B B P B B B P B B B P B B B I B B B P B B B P
MPEG Compression
58
 Non-uniform data rate!
 Compression ratios of 50:1 – 80:1 are readily
obtainable
 Asymmetric algorithm


Fast decode (like JPEG)
Encode requires image search and analysis to get high quality
differences
 Decoding chips on graphics cards available
MPEG Problem
59
 Cannot simply skip frames
 Next desired frame might be B or P derived from a skipped
frame
 Options:
 Separate fast forward and fast reverse files


MPEG encoding of every nth frame
Display only I and P frames

If B frame is needed, derive from nearest I or P
“Movie” File Organization
60
 One MPEG-2 video stream
 Multiple audio streams
 Multiple languages
 Multiple text streams
 Subtitles in multiple languages
 All interleaved
Challenge
61
 How to get the contents of a movie file from disk or
DVD drive to video screen and speakers.



Fixed frame rate (25 or 30 fps)
Steady audio rate
Bounded jitter
 Classical problem in real-time scheduling
 Obscure niche become mainstream!
 See Silbershatz, Chapter 19
Processor Scheduling for Real-Time
Rate Monotonic Scheduling (RMS)
62
 Assume m periodic processes
 Process i requires Ci msec of processing time every Pi msec.
 Equal processing every interval — like clockwork!
 Assume
m
Ci
1

i 1 Pi
 Let priority of process i be
1
Pi
 Let priority of non-real-time processes be 0
Processor Scheduling for Real-Time
Rate Monotonic Scheduling (RMS)
63
 Then using these priorities in scheduler guarantees
the needed Quality of Service (QoS), provided that
m
1
Ci
 m(2 m  1)

i 1 Pi
 Asymptotically approaches ln 2 as m  ∞
 I.e., must maintain some slack in scheduling
 Assumes fixed amount of processing per periodic
task

Not MPEG!
Processor Scheduling for Real-Time
Earliest Deadline First (EDF) Scheduling
64
 When each process i become ready, it announces
deadline Di for its next task.
 Scheduler always assigns processor to process with
earliest deadline.

May pre-empt other real-time processes
Processor Scheduling for Real-Time
Earliest Deadline First (EDF) Scheduling
65
 No assumption of periodicity
 No assumption of uniform processing times
 Theorem: If any scheduling policy can satisfy QoS
requirement for a sequence of real time tasks, then
EDF can also satisfy it.

Proof: If i scheduled before i+1, but Di+1 < Di, then i and i+1
can be interchanged without affecting QoS guarantee to either
one.
Processor Scheduling for Real-Time
Earliest Deadline First (EDF) Scheduling
66
 EDF is more complex scheduling algorithm
 Priorities are dynamically calculated
 Processes must know deadlines for tasks
 EDF can make higher use of processor than RMS
 Up to 100%
 However, it is usually a good idea to build in some
slack
Multimedia File & Disk Management
67
 Single movie or multimedia file on PC disk
 Interleave audio, video, etc.


So temporally equivalent blocks are near each other
Attempt contiguous allocation

Avoid seeks within a frame
Audio
Frame
Text
Frame
File organization – Frame vs. Block
68
 Frame organization





Small disk blocks (4-16 Kbytes)
Frame index entries point to starting block for each frame
Frames vary in size (MPEG)
Advantage: very little storage fragmentation
Disadvantage: large frame table in RAM
 Block organization





Large disk block (256 Kbytes)
Block index entries point to first I-frame of a sequence
Multiple frames per block
Advantage: much smaller block table in RAM
Disadvantage: large storage fragmentation on disk
Frame vs. Block organization
69
smaller
larger
File Placement on Server
70
 Random
 Striped
 “Organ pipe” allocation
 Most popular video in center of disk
 Next most popular on either side of it
 Etc.
 Least popular at edges of disk
 Minimizes seek distance
Disk Scheduling
71
 Scheduling disk activity is just as important as
scheduling processor activity

Advantage:– Predictability

Unlike disk activity of ordinary computing
 In server, there will be multiple disk requests in each
frame interval

One request per frame for each concurrent video stream
Disk Scheduling
72
 SCAN (Elevator) algorithm for each frame interval
 Sort by cylinder #
 Complete in time for start of next frame interval
 Variation – SCAN–EDF:
 Sort requests by deadline
 Group similar deadlines together, apply SCAN to group
 Particularly useful for non-uniform block sizes and frame
intervals
Network Streaming
73
 Traditional HTTP
 Stateless
 Server responds to each request independently
 Real-Time Streaming Protocol (RTSP)
 Client initiates a “push” request for stream
 Server provides media stream at frame rate
Pull vs. Push server
74
Bandwidth Negotiation
75
 Client (or application) provides feedback to server to
adjust bandwidth
 Examples:
 Windows Media Player
 RealPlayer
 Quicktime
Conclusion
76
 Multimedia computing is challenging
 Possible with modern computers
 Compression is essential, especially for video
 Real-time computing techniques move into
mainstream

Processor and disk scheduling
 There is much more to this subject than fits into one
class
Agenda
77
 Protection
 Multimedia Systems
 Review
Questions
78
 What are two functions of an OS?
 What “layer” is above the OS?
 What “layer” is below the OS?
 What causes OS to change?
 Or, why aren’t we still running MS-DOS?
 What is a process?
 What is a file?
Questions
79
 Name 3 operating system structures
 Give one advantage of each
 Give one disadvantage of each
 What is a PCB?
 Usually the PCB is in OS memory only. Assume we
put the PCB into a processes address space. What
problems might this cause?
Questions
80
 How does a shell work? Or … arrange the commands
in order:

wait()

pid = fork()

exec()

gets()

while(1) {}
Questions
81
 List steps that occur during interrupt
 What is (average) waiting time?
 Explain how SJF works
 True or False?
 FCFS is optimal in terms of avg waiting time
 Most processes are CPU bound
 The shorter the time quantum, the better
Questions
82
 What is a “race condition”?
 What are 3 properties necessary for a correct “critical
region” solution?
 What does Test_and_Set do?
 What is one major advantage of semaphores over
the Test_and_Set or Peterson’s solution?
Possible Outputs
83
int main() {
int *num, shm_id
shm_id = shmget(502)
num = (int *) shmat(shm_id)
fork()
*num = *num + 1
printf("%d\n", *num)
}
Possible Outputs
84
int num = 0;
int main() {
fork();
num = num + 1
printf("%d\n", *num)
}
 What if fork() was spawn()?
Questions
85
 What is internal fragmentation?
 What is external fragmentation?
 What is compaction?
 Does paging have fragmentation?
 No? Then why not?
 Yes? Then what kind?
 What are the overheads associated with paging?
Questions
86
 True or False?
 With paging, a process’ logical address spaces is contiguous
 With paging, a process’ physical address spaces is contiguous
 Paging reduces the size of the possible address space used by a
process
 The logical address space cannot be bigger than the physical
address space
 Processes have big address spaces because they always need
them
Questions
87
 Page faults
 What is a page fault?
 What does an OS do during a page fault?
 What is a Page Replacement Algorithm?
 What is “Belady’s Anomaly”?
 How does the Optimal algorithm work?
 What is thrashing?
 How do we fix it?