[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

The problem of computer security can be divided roughly into two parts: a local part, consisting of protection mechanisms built into an operating system, and a more global part, consisting of higher-level defenses spanning multiple machines or entire networks against insider and outsider attacks. We'll start by talking about local protection mechanisms, and then continue with a discussion of practical attacks and defense against them.

1. Goals of computer security

Computer security has traditionally been seen (especially in a military context) as motivated by a broader goal of information security. There are a number of ways to define information security; a classic definition involves the so-called CIA triad of confidentiality, integrity, and avaialability. Confidentiality says that users who are not supposed to receive secret information don't get it. Integrity says that information should be preserved against tampering. Availability says that data should be accessible by those who are entitled to it when they need it.

It's easy to imagine these issues coming up in a military context: we want to keep the enemy from knowing where our forces are and what they are doing (confidentiality), while keeping track of what the enemy is doing (integrity/availability). But the general approach of the CIA model also applies in civilian contexts where we care about the usefulness of information: credit histories are generally subject to confidentiality or privacy protections (so, for example, we can't base your 422/522 grade on your crummy credit history), and are only useful if they can't easily be modified (so you can't escape bankruptcy by paying the neighborhood script kiddie $100 to fix your record) and are available when needed (by say the loan officer at the local bank). Similar considerations apply to other private data, such as medical histories or video rental records (in the United States), or just about any record with your name on it (in Europe).

Other classes of attacks don't exactly fit in the CIA model (but can be made to fit with enough pushing). Some examples from SGG §15.1 include theft of service (where I consume your valuable resources through impersonation or some other breach of your security) and denial of service (where I temporarily prevent you from using some resource; SGG distinguishes this from breach of availability by using the latter only for permanent destruction).

2. Protection

Basic idea: A computer system contains many resources, some of which we want to protect from malicious or foolish users. A protection mechanism restricts what some processes can do. Examples include filesystem protections used to keep users from accidentally trashing system files (or, on timesharing systems, from reading or damaging each other's files), memory protections used to keep insane user processes from damaging system resources, and digital rights management used to make would-be consumers of valuable copyrighted material pay what they owe.

2.1. Principle of least privilege

A common feature of most protection systems is the principle of least privilege, the computer security equivalent of the need to know principle in traditional military security. The idea is that no users or programs should be given any more power than they need to get their tasks done. So a web server, for example, should have access to the network port it listens to and the files it is serving, but should probably not have access to user home directories or system configuration files. This is true even if the server solemnly promises not to abuse this access; if the system enforces that the web server can read my collection of embarrassing love letters, there is no possibility that a bug or misconfiguration of the server might expose them to Google's all-powerful search engine. Similarly, it is generally best to protect the installed software base of a system from ordinary users, who might damage or corrupt the software by accident on a single-user system (possibly by downloading malicious trojan horses or viruses), or who might deliberately corrupt software on a shared system to obtain access to other users' data. A reasonable security system will allow users to be locked out of such access under normal conditions.

There is a conflict between the principle of least privilege and the goals of simplicity and accessibility. Taken to an extreme, the principle of least privilege would demand that every access to every file be constrained by the specific needs of the task at hand: my word processor, for example, might be allowed to read its own word processing files but would be prevented from examining my web browser cache. Conversely, my web browser might not be allowed to look at by word processing documents. Such a system would prevent several possible attacks on my data (e.g. a corrupted web browser secretly uploading all my valuable trade secrets), but in practice nobody uses it because the cost of keeping track of which programs can legitimately access which data exceeds the security benefits for all but the most paranoid users, and additional complications arise with unanticipated uses (like wanting to upload my documents to a coursework submission website). So in practice the principle of least privilege is usually implemented approximately.

2.2. Users, roles, and groups

The mechanism for such approximate privileges is the notion of a user or sometimes more specifically a role. Each user represents an agent with interests distinct from that of other users; these may correspond to real human beings, or may consist of virtual users representing some subsystem with special privileges (or especially restricted privileges) like a web server or the filesystem. A typical user-based protection system will by default provide the same privileges to each program running under control of a particular user regardless of what task the program is executing; the assumption is that users can be trusted to look out for their own interests, and that a user's right hand does not need protection from their left.

For some purposes it makes sense to subdivide a user further into distinct roles with different privilege levels. So, for example, the owner of a particular machine might normally work as a normal user with no special privileges (thus providing protection against accidents or malicious code), but will occasionally adopt a more powerful role to install new software or perform system maintenance. From the point of view of the underlying system, there is not much difference between a single user with multiple roles and multiple users, but a particular implementation may condition adopting particular roles on already identifying as a particular user (e.g. sudo in Unix-like systems or administrator privileges in Windows).

For convenience, it may also be useful to categorize users into groups, where all members of a given group are given the same privileges with respect to particular objects. So, for example, users on a Windows machine might be members Administrator group, allowing them to invoke Administrator privileges when needed. A Linux machine might put users in the audio group to give them access to the speaker and microphone, or the cdrom group to give them access to the CD/ROM device. A daemon group might include system daemons that need powers common to all system daemons (like the ability to append to log files).

2.3. Protection domains

A protection domain defines operations a process may perform at a given time; the power to execute a particular operation on a particular object is called an access right and a protection domain is essentially a bundle of access rights. In a user-based system the domain of a process will generally be determined by the identity of the user that runs the process; however, more complex systems might allow per-process protection domains or even per-procedure protection domains.

Protection domains may be static or dynamic. In the former case, the access rights of a process are fixed; in the latter, there may be some mechanism for granting a process new access rights or removing rights it already has. Dynamic protection domains are often necessary if we are fanatical about least privilege: the access rights that a process needs at one point in its execution may be different from those it needs later. But because of the complexity of fine-grained dynamic control of access rights, a more practical solution might be to combine static or near-static domains with domain switching, where a process can obtain a new bundle of rights when needed. Examples of domain switching are the switch to kernel mode in a system call (or the more general ring gateway mechanism in Multics), the setuid bit in Unix that allows a program to specify that it should be run with the privileges of the program owner in addition to those of the user that calls it, and mechanisms for switching roles as described above.

2.4. Access matrices

An access matrix specifies the relation between protection domains and access rights. In full generality we could have a system that allows each entry in an access matrix to be specified separately; in practice, most systems establish simpler protection policies from which the access matrix is implicitly derived.

By convention, each row of the access matrix corresponds to a protection domain, and each column to an object. Each entry gives a list of access rights to that particular object. So we might have a matrix that looks like this:

Tetris high score list

A's diary




read, write, delete





print, disable

Here B can read A's diary but not write to it or delete it. Both A and B can append to the Tetris high score list, and both can print, but only B is allowed to turn the printer off.

2.4.1. Who controls the access matrix?

Typically each column of the access matrix corresponds to an object that is owned or created by a particular user. It is natural to give this user control over the entries in the column. The right to modify entries in the access matrix may also be controlled by the access matrix itself, through an explicit owner right.

2.4.2. Copy rights

An access right may provide the right to copy or transfer the right to new domains. So, for example, I might have read* access to an object, which means that not only may I read the object but I may grant read access to other domains. There are several variants of this: a transfer right allows me to copy my access right to a different domain provided I give it up myself; a limited copy right allows me to copy the underlying right to a new domain without also granting the right to copy it further.

2.4.3. Confinement

One problem with copy or owner rights is that they can allow privileges to escape to domains that shouldn't have them. We may want, for example, to guarantee that none of the TOP SECRET data on our system is ever visible to a user with only SECRET clearance, but if we allow an owner to adjust access rights arbitrarily the owner can easily grant rights to the data to anybody they like. In this particular case we can impose a ring structure on data where high-confidentiality data is never expose to low-confidentiality domains, but in more general cases it may be very difficult to enforce exactly the restrictions we want. We also quickly run into computational limits: once a protection system allows users to grant each other rights under reasonably sophisticated conditions, it may become NP-hard to detect if a particular user can obtain a particular right through normal execution of the system. So the problem of confinement is generally considered be unsolvable at the software level, and for applications where it is critical is usually enforced externally (e.g. via locked rooms).

2.5. Implementation

There are basically two standard mechanisms for specifying access rights: access control lists and capabilities. The difference is that an access control list is associated with an object, while capabilities are associated with a domain.

2.5.1. Access control lists

In the most general form, an access control list or ACL describes exactly the column in the access matrix associated with a particular object. So a file might state that it can be read by any administrator and appended to by any system daemon (using in this case groups as protection domains). Similarly, a subdirectory in a version-control system might be readable by John Q. Tester, readable and writable by Jane C. Developer, and allow updates to its permissions by Hieronymous J. Administrator. These values would most likely be stored in a data structure along with the protected object, e.g. in the inode in a filesystem.

Some systems provide weaker versions of access control lists. For example, standard Unix file permissions are divided into read, write, and execute access rights (the last has a special meaning for a directory, allowing a user to find a file by name in a directory but not list all files). For each file, these can be set separately for (a) the owner of the file, (b) a single group that the file belongs to, and (c) arbitrary users. So it is possible to create a file that anybody can read but only the owner can write to, but it is difficult to create a file that A and B can both read but only C can write to (it's necessary to create a new group containing only A and B), and it's impossible to create a file that only A and B can read but only B and C can write to (since you would need two groups, and each file can only be assigned to one group). So Unix necessarily violates the principle of least privilege in some plausible scenarios. In practice, these issues are usually worked around by building setuid daemon processes that enforce arbitrarily convoluted access control, but this can be expensive.

2.5.2. Capabilities

An alternative approach is to store rows of the access matrix instead of columns. Here each protection domain carries with it a list of capabilities, tokens that indicate particular access rights for particular objects. These capabilities may be transferable to other protection domains with or without the supervision of the operating system, depending on the implementation.

An example of a capability is a Unix file descriptor. When a file is opened, the kernel checks the current user against its access permission. But once the kernel returns a file descriptor, further access to the file requires no additional permission checks, and indeed changes to the permission bits at this point will not affect use of the file descriptor. File descriptors are mostly not transferable (unless you are running Mach); the only case where they are transferred is as the result of a fork or exec system call.

A more sophisticated capability mechanism allows transfer of capabilities between processes. This allows for very fine-grained control of access rights. For example, if I want to run a word-count program on one of my valuable files, instead of running the program with all of my privileges (possibly allowing it to read or write any of my other files), I could give it only the capability representing read access to the particular file I want it to look at.

The usual difficulty with capabilities is that they are harder than ACLs to keep track of. Given a particular resource, it is easy to figure out exactly which users can access it. This is especially true if capabilities are transferable or if they are represented externally (say by using cryptographically signed certificates).

3. Implementation

Protection domains and access matrices only describe what we want to protect. The question remains of how we actually do it.

3.1. Authentication

The first problem that arises is: how do we know which user we are dealing with? This is the problem of authentication. Some options:

3.1.1. Something you know

Like a password. Here the idea is that if only I know what my password is, the system can trust anybody who types in my password to be me. There are some well-known problems with this:

The moral: Passwords provide only minimal security under typical circumstances. And yet (a) we still use them for everything, and (b) the most valuable passwords (like 4-digit banking PINs or non-resettable Social Security Numbers) are often the weakest! Why is this? (My guess: There is much psychological comfort in letting users think they are in control of their own security.)

3.1.2. Something you have

We can strengthen passwords somewhat by replacing them with cryptographic authentication mechanisms using e.g. public-key cryptography. Many public-key cryptosystems can be adapted to give digital signatures, where I can sign a document using my private key and anyone who knows my public key can verify the signature. So now instead of a password dialog that looks like this:

we have something that looks more like this:

The difference is that the digitally signed document is presumably unforgeable by anybody who doesn't have access to my private key, and can't be reused at a later time to cause trouble. Note that this type of system may still be vulnerable to man-in-the-middle attacks.

Secret keys have to be stored somewhere; for typical public-key systems the length of a secure key is long enough (starting at around 1024 bits) that it is impractical to have a user remember one. So this means storing the keys on the user's personal computer or better yet on some device that the user carries around with them. Various smartcards, dongles, and bits of jewelry have been marketed for this purpose, and it would be trivial to implement a system that keeps cryptographic keys on a USB device. Nobody I know carries one. So to the extent that we currently use cryptographic authentication (at least in civilian contexts), we mostly are relying on the security of our personal computing devices.

There is a long history of authentication tokens other than cryptographic keys: physical keys, ATM cards, signet rings and other seals (as found in Europe) and chops (as found in East Asia) all work on the something-you-have principle.

3.1.3. Something you are

If a computer could identify a user directly, we wouldn't need any other authentication. Possibilities here generally involve some form of biometrics, such as fingerprint or retinal scanning, face recognition, or more exotic measurements like measuring typing characteristics, voiceprints, or walking gait. These all share several serious problems:

3.1.4. Two-factor authentication

Because individual authentication mechanisms are weak, a common approach is to require two-factor authentication, where the user must demonstrate their identity in two different ways (that hopefully have different vulnerabilities). So an ATM machine demands both an ATM card (that is hard to copy) and a PIN (that is hard to steal); this protects me against pickpockets and against muggers who aren't willing to actually drag me to the nearest ATM to make sure the PIN I gave them isn't bogus. Because of the strength of two-factor authentication, current US banking regulations demand that on-line banking be done using it. Unfortunately, many banks have successfully convinced regulators to interpret requiring a username (factor 1) and a password (factor 2) entered on separate web pages as qualifying.

3.2. Authorization

Here the issue is the design and implementation of access policies. The main problem as discussed previously is the trade-off between convenience and least privilege. For users, this usually means separating roles, so that the identity I use to buy books from Amazon is not the same identity I use to tell Yale where to send my paycheck. However, there are still vulnerabilities here, since somebody (or some program) I delegate my authority to may misuse it: a compromise web browser or web proxy, for example, may use my Amazon password to send large amounts easily-fenced jewelry to the summer home in Moldova I didn't know I had.

3.3. Enforcement

Even if we know who a user is and what access rights they have, we still have the problem of enforcement. It doesn't matter if my filesystem correctly determines that user evil isn't allowed to read file sensitive.txt if it then goes ahead and lets them read it anyway. This can be particularly difficult dealing with an operating system containing millions of lines of code of variable quality, some obtained from questionable sources, and all running with full kernel privileges; any flaw can potentially be exploited to obtain access to protected objects.

To the extent that there is a solution here, it is made up in practice of several pieces:

Minimize the size of the trusted computing base
If we can reduce the amount of code with full access to the hardware, we reduce the problem of eliminating bugs. This is often used as an argument for microkernel designs (where the kernel can be as small as a few thousand lines of code) or exokernel designs (where hardware is partitioned between processes directly and protection is limited to restricting access to particular memory regions or disk cylineders); however, this may just push the issue of enforcement off into user-level processes that implement their own security policies. An alternative is to implement security directly in hardware: for example, digital rights management for HDTV is implemented in part by only doing the final decryption of the video image inside the display device itself, reducing reliance on the trustworthiness of path leading to it.
Partition the system to contain faults

That is, apply the principle of least privilege by separating components into distinct protection domains as much as possible. So for example a web server can be run inside a restricted subsystem that hides most of the normal filesystem (a chroot jail in Unix terms) or even inside a virtual machine with no access to the underlying hardware. Similar techniques can be applied to device drivers, filesystems, etc.: if there is no reason for my wireless driver to touch the superblock on my filesystem, then I probably shouldn't let it.

Rely on trusted code
If I'm worried about buggy code breaking my machine, then I should only run thoroughly-debugged code that is certified as such by somebody I trust. To a first approximation, this is the security mechanism most users rely on most, and ultimately any user of somebody else's code (including assemblers or compilers—see the famous compiler hack by Thompson) must do this. Violating this trust is also the most effective practical way to subvert security, since it doesn't rely on finding bugs.

3.4. Intrusion detection and recovery

Try as we might to secure a system, there is still a possibility of compromise. We'd like to detect such a compromise and recover from it as quickly as possible. Detecting breaches comes under the heading of intrusion detection, which typically consists of extensive logging and accounting (so we can see what our system has been doing) and auditing (so we can check what is going on against what we think should be going on. Logging ideally occurs in a form that can't be disabled and can't be erased by attackers,1, although even a protected file in a filesystem that might be compromised my help against stupid attackers. Auditing typically involves studying log files, the filesystem, and/or kernel memory to look for signs of a breach. This can be done by looking for positive signs of compromise (e.g. virus scanners looking for virus signatures) or by looking for unexpected changes (e.g. virus scanners looking for files that have changed but shouldn't have). The ultimate difficulty with auditing is the problem of weeding out false positives: often, human intervention is required to detect if some file really should have changed (or if I really did mean to send lots of jewelry to my summer home in Moldova).

Recovery from intrusion is often difficult. Because it is hard to tell exactly what has been compromised, and because the tools we use to observe the system may themselves have been compromised, often the only safe course is to reinstall from a more secure backup.

4. Practical attacks and defenses

4.1. Attacks on individual machines

4.1.1. Buffer overflow and other code injection exploits

An attackers' goal on a single machine is privilege escalation, where I execute code in a limited protection domain that somehow obtains access to a more powerful domain. One common method for doing this is code injection, where I can convince some privileged process to execute code of my choosing. Some variants:

Buffer overflow
A program reads some parameter from the user that it stores in a 512-byte buffer allocated on the stack. The attacker supplies a 1037-byte value for the parameter that overwrites some other part of the stack, seizing control of the process by changing some other variable or possibly even code. Solution: Don't write anything critical in a programming language that doesn't check array bounds (this generally means C and C++). Problem: Everything is already written in C or C++. A less effective but more feasible solution is to carefully insert array bounds checks everywhere in your existing C or C++ code.
Code injection

I cleverly replace all my buffer-overflow-prone C/C++ code with code written in some exciting scripting language like Perl, Python, TCL, Ruby, Visual Basic, or (since I'm using a database anyway) SQL. Part of my program generates scripting commands on the fly of the form do something; do something else; open database record for <username>; do something with it; etc, where commands are separated by semicolons and username is supplied by the user. Everything goes great until some smart-aleck named HaHa; delete all database records signs up for my free web service. Solution: Be very careful about quoting and using user-supplied input.

Symlink attacks

Long ago (1970s and 1980s), it was possible to break into a BSD machine by creating a symbolic link /tmp/foo to some setuid shell script. Since shell scripts work by having (a) the shell program start (under the uid that the script is setuid to) and then (b) open and read the shell script file, a clever attacker could redirect the symbolic link between steps (a) and (b). Most Unixes no longer allow setuid shell scripts for this reason.

4.1.2. Viruses

A virus copies itself into executable programs on disks so that it obtains new privileges when these programs are run by a different user. Before widespread networking, these were the main automated security threat. Solution: Carefully limited access rights, integrity scanning for executables (including not executing unsigned executables, since a virus hopefully can't forge signatures), user education.

4.1.3. Trojan horses

A trojan horse is a program that claims to do something good but really does something evil. These are often automated versions of social engineering attacks: for example, a user may receive an executable file that claims to be a self-extractive archive of a notice of impending court proceedings or something equally threatening. Solution: Don't let users run programs they find on the street unless they can really convincingly argue that the program is trustworthy.

4.1.4. Worms

Automated program that uses local privilege escalation exploits, network buffer overrun exploits, and trojan horse trickery to propagate itself from one machine to another. First appeared in fiction (The Shockwave Rider by John Brunner). Now all too real. Solution: Close the holes the worms rely on.

4.2. Network attacks

4.2.1. Replay attacks

I record your password going over the wire and reuse it. Solution: encrypt everything.

4.2.2. Man-in-the-middle attacks

I pretend to be your bank to you and pretend to be you to your bank. Anything your bank asks for to authenticate you, I from you, and vice versa. Once we are authenticated to the bank, I hijack your connection and drain your accounts.

To execute a man-in-the-middle attack, I have to be able to insert myself in the middle. Some ways to do this are compromising DNS (so that bank.com goes to my IP address), tricking you via phishing email into following a bogus URL (to say, bαnk.com), compromising your network connection by compromising some intermediate router (it may help if your Netgear wireless access point still has the default administrative password netgear), or compromising your computer or web browser so I can intercept your credentials directly (don't download Firefox extensions from bαnk.com).

Man-in-the-middle attacks are particularly difficult to deal with because no matter how clever your authentication protocol, the attacker can simulate it from both ends. The only solution is to have some shared secret that allows the remote end to authenticate itself; hence the security certificates in web browsers (which don't actually help much against typical users, who have been trained to happily click accept this certificate buttons).

5. How much of a problem is security?

For normal users, the history of computer security looks like this:

  1. A popular operating system or program ships with an easily exploited, catastrophic vulnerability.
  2. Nefarious bad guys exploit the vulnerability to do something highly costly and visible.
  3. Either vulnerability is quickly patched, or damage is contained through some other means.
  4. Process repeats.

The effect of this is that the most dangerous vulnerabilities tend to be the ones that are fixed first, or at all. There is a sense in which this is economically optimal. It also fits well with the pattern for physical security, where a plausible rule of thumb is that the number of security devices on the front door of a house is roughly equal to one or two plus the number of times the house has been broken into.

But: The efficiency of computers also means they are efficient at propagating worms, viruses, etc. It is theoretically possible to infect every vulnerable Windows machine on the open Internet using a new remote exploit in less than a minute. If the worm that does this is sufficiently malicious (e.g. erasing all infected hard drives and then doing denial of service on all nearby routers), the damage to the world economy could be quite high. Perversely, our best hope against such nightmares may be the trickle of annoying but not very dangerous worms, which highlight existing vulnerabilities and force them to be fixed.


  1. The one case of logging that I personally had some unhappy involvement with many years ago took the form of a line printer in a locked machine room. (1)

2014-06-17 11:58