pk.org: Computer Security/Exams

Exam 2 Study Guide

The one-hour study guide for exam 2

Paul Krzyzanowski

Disclaimer: This study guide attempts to touch upon the most important topics that may be covered on the exam but does not claim to necessarily cover everything that one needs to know for the exam. Finally, don’t take the one hour time window in the title literally.

Last update: Fri Oct 30 13:49:02 2026

Week 5: Hash Pointers, Blockchains, Merkle Trees, and Bitcoin

Bitcoin combines hash functions, digital signatures, and proof of work to maintain a shared transaction history without a central authority. Its cryptography consists of hash pointers that link blocks into a blockchain, Merkle trees that tie each block’s transactions to its header, digital signatures that authorize payments, and proof of work that makes adding a block expensive. Every transaction is public.

Hash Pointers and Blockchains

A hash pointer stores a reference to data together with a cryptographic hash of that data, so a reader can detect whether the data changed. A blockchain is a linked list in which each block holds a hash pointer to the previous block. The newest block is identified by a head pointer, and the first block is the genesis block.

Changing any block changes its hash, which invalidates the hash pointer in the next block, and so on up to the head. An attacker who alters a block must therefore recompute every hash pointer between that block and the head. The chain is a tamper-evident log. Protecting only the head pointer, for example by storing it securely or signing it, is enough to detect tampering anywhere in the chain.

A distributed ledger such as Bitcoin has no single head pointer that one authority can protect, since every participant holds its own copy of the chain and there is no central authority. Recomputing the hashes is easy, so an attacker who can distribute a rewritten chain could pass it off as the real one. Bitcoin instead makes adding each block computationally expensive through proof of work, so that rewriting history requires redoing that work for every block after the change.

Merkle Trees

A Merkle tree is a binary tree of hashes. Each leaf is the hash of one data item, each parent is the hash of its two children joined in order, and the single hash at the top is the Merkle root. Changing any item changes the root.

A Merkle proof, or proof of inclusion, is the set of sibling hashes along the path from one item to the root, together with their left-or-right positions. The verifier hashes the item, combines it with each sibling in turn, and compares the result with a trusted root. A proof for a balanced tree of \(n\) items contains about \(\log_2 n\) hashes. The item and the proof can come from an untrusted source, but the root must be obtained securely. A matching root establishes that the item belongs to the collection.

Bitcoin and Its Goals

Bitcoin is a decentralized payment system. A conventional payment system relies on a bank as a trusted third party that keeps the account balances, checks that a payer has the funds, and records each transfer. Bitcoin replaces the bank with a public ledger, a history of every transaction, replicated across many independent computers. Anyone can run one of these computers, verify the history, and submit payments without registering with any authority.

Removing the central authority creates two problems that the rest of the design solves. The first is identifying who may spend funds when there are no names or accounts, which Bitcoin does with cryptographic keys. The second is double spending. Digital data can be copied, so a payer can sign two transactions that spend the same funds. Each signature is valid on its own, so the participants need a way to agree on a single transaction history that decides which payment counts.

Users are pseudonymous rather than anonymous. Transactions do not carry names, but every transaction is public, and outside information can link an address to a person.

Keys, Signatures, and Addresses

Bitcoin identifies participants by keys rather than names or accounts. A user creates an elliptic curve public/private key pair on their own computer, and that key pair is the only information the user needs to keep in order to control funds. The private key signs transactions, and anyone can verify the signature with the public key. A valid signature shows that the signer holds the private key. It does not reveal who that person is, and it does not show whether the funds have already been spent.

A private key must be generated unpredictably and kept secret. A stolen key lets the thief spend the funds, and a lost key makes them permanently inaccessible, since there is no central authority that can reset it. A wallet is software that generates and stores a user’s keys and uses them to create transactions. It does not hold balances or transactions. Those are determined by the public ledger.

An address tells a sender how to construct an output that the recipient can spend. It contains a hash of the recipient’s public key plus a checksum. Spending the output requires presenting a public key that hashes to that value and a valid signature under that key. Hashing the key makes the address shorter and keeps the public key off the blockchain until the output is spent, in which case it appears as the owner of the transaction that is doing the spending. The checksum detects typing errors.

Transactions and Unspent Outputs

Bitcoin has no account balances. The ledger is the history of transactions, and the system tracks unspent transaction outputs (UTXOs). Each output records an amount and the condition for spending it. A user’s balance is the sum of the UTXOs that the user’s keys can spend.

A transaction has the following parts:

Verification and Replication

A full node is a computer that holds a complete copy of the blockchain, the ledger of every transaction since the genesis block. It verifies every block and transaction in that copy for itself rather than trusting any other node, and from that history it maintains the current UTXO set. For each new transaction, it checks that every referenced output exists and is unspent, that no output is used twice, that each public key hashes to the required value, that each signature is valid, and that the outputs do not exceed the inputs. The node takes the input amounts from the earlier outputs, not from the transaction.

A verified transaction is not yet part of the blockchain. The node holds it in memory as a pending transaction, and it does not change the confirmed UTXO set until a block containing it joins the node’s chain. Different nodes can hold conflicting pending transactions, so local verification cannot settle which of two competing spends will count.

There is no master copy of the blockchain. Full nodes around the world each hold their own copy, and no node has authority over another. A lightweight client can use a Merkle proof and an accepted block header to check that a transaction is in a block, but it relies on full nodes and miners for the other checks.

Blocks and Proof of Work

Miners collect pending transactions into blocks. Each block has a header and an ordered list of transactions. The header contains the following fields:

The block hash is the double SHA-256 hash of the header. Changing any transaction changes the Merkle root, the block hash, and the link from the next block.

Proof of work requires the block hash, interpreted as a 256-bit integer, to be at most the value of the target. Hash outputs cannot be predicted, so a miner repeatedly changes the nonce and hashes the header again until the result qualifies. A smaller target leaves fewer acceptable hashes and makes the search harder. Finding a qualifying header is expensive, but checking one takes a single hash computation. The nonce has a limited range, and trying every value usually does not produce a hash below the target. Miners therefore also vary other permitted header data, including the set of transactions, which changes the Merkle root and gives them a new header to search.

A miner’s hash rate is the number of hashes it can try per second. As the network’s total hash rate changes, the difficulty adjustment periodically recomputes the target so that blocks continue to arrive about every ten minutes on average. Every node derives the required target from the chain, so a miner cannot choose an easier one.

Agreement, Chain Selection, and Reorganization

Chain selection is how Bitcoin resolves double spending. Two transactions can carry valid signatures while spending the same output, and signatures alone cannot settle which one counts. Only an agreed history can.

Two miners can find valid blocks at about the same time. Both blocks extend the same previous block, so the chain forks into two competing branches, and nodes that received different blocks first temporarily follow different branches. To choose between branches, each node assigns every branch it knows about a score, which is its accumulated work, the total proof of work that its blocks represent. The node follows the valid branch with the highest score. Miners extend the branch they follow, so one branch soon gains more work than the other, and every node converges on it.

The work credited to a block is determined by the target it was mined under, with a smaller target counting for more work. It is not the number of hash attempts the miner actually made. When all blocks have the same target, the branch with the most work is also the longest one, which is why the rule is often described as following the longest chain. Branch selection depends only on work and validity. There is no vote among nodes, and running more nodes does not add mining power. Valid proof of work does not make invalid transactions acceptable, because every node validates each block’s contents independently.

When a competing branch overtakes the one a node had followed, the node performs a chain reorganization. It undoes the abandoned branch’s changes to its UTXO set and applies the winning branch. Transactions from the abandoned branch become pending again if they are still valid. A transaction that conflicts with a spend in the winning branch is rejected.

The 51% Attack and Confirmations

A 51% attack refers to control of a majority of the network’s hash rate, not of nodes or coins. An attacker with that much hash rate can mine a private branch faster than the honest miners on average, replace recent blocks, double-spend its own funds, and keep chosen transactions out of blocks. It cannot forge other users’ signatures or create coins beyond what the rules allow, because every full node checks those rules. An attacker with less than half the hash rate can still succeed by luck, but the chance falls as more blocks are added.

A transaction has one confirmation when it is in a block in the active chain and gains another with each later block. More confirmations make a transaction more expensive to reverse, since an attacker would have to redo the work of every block since then. The protocol does not require any number of confirmations. The recipient decides how many to wait for, weighing the value of the payment against the delay, and six is the traditional guideline for valuable payments. No number of confirmations is a guarantee.

Mining Rewards

The first transaction in every block is the coinbase transaction (no relationship to the Coinbase company). It has no inputs and lets the miner claim the block reward, which consists of newly created bitcoin, called the block subsidy, plus the fees of the block’s transactions. Nodes reject a block whose coinbase claims more than the rules allow.

The subsidy halves on a fixed schedule, which limits the total supply to about 21 million BTC and makes fees a growing share of the reward over time. The reward is the incentive for miners to participate. Mining consumes electricity and hardware, and without payment for finding blocks there would be no reason to do it, and no proof of work to protect the chain. A reward in an abandoned branch cannot be spent, so miners are paid only for blocks the network accepts.

What You Don’t Need to Study

The following are not required for exams:

Week 6: Access Control

Access control decides which subjects may perform which operations on which objects. The hardware and kernel mechanisms below are what make those decisions enforceable, and the models that follow are different ways of stating the policy.

Protection and the Operating System

Access control decides which subjects may perform which operations on which objects and enforces those decisions. A security policy defines what access should be allowed, and protection is the set of mechanisms that enforce it.

An operating system provides processes with controlled access to shared resources: the processor, memory, files and devices, and the network. Programs execute instructions and access mapped memory directly, within limits enforced by the hardware. A system call transfers control to the kernel to request an operating system service, and the kernel checks whether the request is allowed before performing it.

Three things have to be true for protection to work at the operating system level. The operating system must:

  1. Protect itself from the programs it runs.

  2. Protect programs from each other.

  3. Stay in control, so that a process cannot hold the processor forever.

The kernel and the hardware that enforce these properties form the core of the trusted computing base, the set of components whose failure means the security of the whole system fails.

The hardware provides three mechanisms:

Execution transfers from user mode to kernel mode through controlled entry points defined by the kernel at boot time. The transfer occurs in three ways:

  1. A system call, which the program makes deliberately to request a service.

  2. A fault, when an instruction cannot complete without kernel intervention. A fault can indicate an invalid operation or a valid memory access that requires the kernel to supply a page.

  3. A hardware interrupt, when a device or the timer needs attention.

The Reference Monitor

The reference monitor is the part of a system that checks every attempt by a subject to reach an object against the policy. It has three requirements:

  1. It is invoked on every access.

  2. It is tamperproof: the programs it controls cannot change it.

  3. It is small enough to be analyzed and tested.

In an operating system, the kernel’s access checks and the hardware mechanisms it configures implement the reference monitor. The MMU enforces memory permissions, while system calls mediate requests for kernel services. User-mode code cannot modify the kernel, but these protections do not prevent bugs in the kernel itself. The size of a modern kernel makes the third requirement difficult to satisfy. A database server or a web application is its own reference monitor for the data it manages, and its enforcement depends entirely on the correctness of that code.

Subjects, Objects, and the Access Matrix

A subject is an active entity that requests access, almost always a process. A principal is the identity on whose behalf a subject acts, usually a user account. An object is a passive resource: a file, a device, a socket, a region of memory, or another process. A right is an operation a subject may perform on an object.

Authorization is the access decision in the following sequence:

  1. Identification is a claim of identity.

  2. Authentication verifies the claim.

  3. Authorization decides what the authenticated principal may do.

The access matrix describes every permission in a system: one row per subject, one column per object, and in each cell the set of rights the subject has over the object, such as read, write, execute, append, and delete.

A row defines a protection domain, the complete set of objects and rights available to a process. Several processes can share the same protection domain. A process operates within a protection domain and exercises that domain’s rights. Deleting an object removes its column from the matrix, while revoking a right removes only that right from a cell.

Other rights govern how permissions are managed or which domain a process uses:

The matrix is a model rather than a data structure. A real one would be enormous and almost entirely empty, so systems store it in one of two compressed forms:

An open file descriptor is a capability: the permission check happens once, when the file is opened, and the descriptor is then presented on every read and write without rechecking the file’s permissions. A descriptor passed to another process carries the access with it.

A confused deputy is a program that holds authority of its own and can be tricked into using that authority for a caller who lacks it. The deputy’s rights are checked and the caller’s are not, so any program that runs with more privilege than its caller must check what the caller is entitled to. Capabilities can avoid the problem by having the caller supply a capability for each object. The program uses that capability rather than its own authority, and the system enforces the permissions the capability grants.

Discretionary and Mandatory Control

Access control is divided into two families, based on who controls access permissions:

Nearly every system implements some of both.

Unix File Permissions

Unix file permissions are a foundation for understanding access control because the same basic model is used by Linux, Android, BSD, QNX, and macOS. These systems span servers, phones, personal computers, and embedded devices. In this section, “Unix” refers broadly to systems that use this permission model.

Every file has an owner, a group, and nine permission bits, stored in the file’s inode with the rest of its metadata. One set of three bits applies to the owner, one to members of the file’s group, and one to everyone else (which Unix calls “other”), and within each set one bit grants read, one write, and one execute permission. This is a compact ACL with three fixed entries that fit in the inode, so reading the file’s metadata also retrieves its permissions without an additional disk read.

The permission check examines only one set of bits: the owner’s if the process’s effective user ID matches the owner, otherwise the group’s if the process belongs to the file’s group, otherwise the other bits.

A binary file can be executable without being readable, because the kernel loads it; a script cannot, because the interpreter has to read it.

For a directory, read access allows listing the names in the directory, write access allows creating, deleting, or renaming entries, and execute access allows the directory to be searched to reach something inside it. Deleting a file requires write and execute permission on the directory, not write permission on the file, because deletion removes a name from the directory.

Default Permissions and the umask

Most programs (particularly scripts and cross-platform environments like Java and Python) request read and write permission for everyone when creating files and leave the restriction to the environment. The umask is an inherited per-process value listing the permission bits to remove at file creation. The usual default removes write permission for the group and everyone else, which leaves new files readable by every user on the machine.

The Access Check Happens at Open

The permission check runs once, when a file is opened, and not on each read or write. A process that holds an open descriptor keeps its access even if the file’s permissions change afterward. A program that creates a file with permissive bits and then restricts them leaves a window of time in which another process can open the file and keep it open. To avoid this race condition, the file should be created with the right permissions in the first place.

Users, Groups, and Root

A principal on a Unix system is represented by a numeric user ID. A process also contains an effective group ID and a list of supplementary groups. Membership in any of them counts as membership in a file’s group.

User ID 0 is root, the superuser. Root can bypass most discretionary permission checks. However, mandatory controls such as SELinux (Security-Enhanced Linux, described below) apply to root too.

A process inherits its user ID from its parent. The login program runs as root and takes on the user’s identity before starting the user’s shell, which is a domain transfer. In this case, the change is permanent: the process gives up its ability to restore root privileges.

Running with Someone Else’s Authority

A process has more than one user ID. Its real user ID identifies the account that started it, and its effective user ID is the one the kernel uses for permission checks. These are usually the same.

Some legitimate actions, such as changing a password, require a privilege the user should not hold in general. If a program’s setuid (“set user ID”) bit is set, a process that runs it gets the file owner’s user ID as its effective user ID rather than the ID of whoever ran it. The real user ID is unchanged, so the kernel still knows who started the process. A setgid bit does the same for the group ID.

Running a setuid program is a domain transfer, and its code must enforce which privileged operations the caller is entitled to request. The program is a deputy, and exploiting a bug in a setuid-root program can give an attacker root privileges.

Several defensive rules follow from that:

A setuid program that checks whether its caller may access a file by name and then opens the file by name has a time-of-check to time-of-use race condition: the filename can be made to refer to a different file between the check and the use, allowing an attacker to access a different file.

Least Privilege and Privilege Separation

The Principle of Least Privilege states that every program and every user should operate with the smallest set of privileges needed to complete the job. It limits damage rather than preventing mistakes. On Unix the principle is applied with identities: each service runs as its own user, a server that must start as root gives up root before it reads anything from the network, and administrators use sudo for individual privileged commands.

Privilege separation is the structure for programs that cannot give up root entirely. The program is divided into a small privileged part that does only the operations needing privilege and a larger unprivileged part that does everything else, connected by a narrow channel. The unprivileged part handles everything an attacker can send, so a bug there yields a process with little authority, and the attack surface of the privileged code shrinks to the requests the channel accepts.

Full Access Control Lists

The nine Unix permission bits express only three entries: owner, group, and others. Linux and macOS also support access control lists (ACLs) with entries for additional users and groups, while Windows NT and its successors have used ACLs from the start. A full ACL takes a variable amount of space, and the filesystem determines how it is stored.

Some ACL systems support explicit deny entries as well as allow entries. Inheritance lets newly created files and directories receive permissions from their parent directory.

Full ACLs can express any column of the access matrix. The drawback is that nobody can see the matrix: with inherited entries, named users, and deny entries, determining a user’s effective permissions requires evaluating all applicable rules.

Why Discretionary Control Is Not Enough

Discretionary control has three limits that no setting of the permission bits can fix:

Mandatory access control removes these limits by enforcing rules that users and programs cannot override.

Multilevel Security and Bell-LaPadula

The Bell-LaPadula model describes multilevel security: a system that holds information at several levels of sensitivity and prevents it from flowing downward. Objects are given a classification from an ordered set of levels (Unclassified, Confidential, Secret, Top Secret), and a user’s clearance sets the highest level at which their processes may operate. A process can run at that level or a lower one. Two rules protect confidentiality:

  1. The simple security property, or no read up: a subject may read an object only if its operating level is at least as high as the object’s classification. For example, a subject operating at Secret may read a Confidential file but cannot read a Top Secret file.

  2. The star property, or no write down: a subject may write an object only if the object’s classification is at least as high as the subject’s operating level. For example, a subject operating at Secret may write to a Top Secret file but cannot write to a Confidential file.

Here, writing means adding information without reading the object. An operation that both reads and writes must satisfy both rules, so the subject and object must be at the same level.

A third rule, the discretionary security property, says that ordinary permissions still apply within those limits: an owner can restrict access further but cannot extend it past what the labels allow.

The star property prevents programs from disclosing information to lower classification levels. A program operating at Secret could read a Secret file and attempt to write its contents to an Unclassified one. The star property forbids that write, whether the disclosure is deliberate or accidental. Under this rule, information may flow to the same or a higher classification level, but never to a lower one.

The model has three limits:

  1. Information cannot flow down, so declassifying and sanitizing require trusted subjects that are exempt from the star property, and the security of the system then rests on those programs.

  2. It does not protect integrity: a low-clearance subject may write (or overwrite) a Top Secret file.

  3. Covert channels can bypass the modeled access controls. For example, a Secret process could signal bits to an Unclassified process by varying its CPU use, causing delays the other process can measure.

Compartments and Multilateral Security

Clearance levels order information by sensitivity. Need to know divides it within a level: a clearance establishes that a person may be trusted at a level, and a separate decision establishes which information at that level the person needs. A compartment is a category of information, such as information about a specific project. Clearance at Secret does not grant access to every Secret compartment. The full Bell-LaPadula label combines a level with a set of compartments. Separating access by compartment as well as by level is called multilateral security.

A subject may read an object only if two tests both pass: its operating level is at least as high as the object’s classification, and its compartment set includes every compartment in the object’s label. When both pass, the subject’s label dominates the object’s. Dominance replaces the level comparison in both rules: a subject may read only what its label dominates and write only to what dominates its label. A subject missing even one of the object’s compartments cannot read it.

Two labels can be incomparable, meaning neither dominates the other. The set of labels ordered by dominance forms a lattice, which can be represented as a directed graph. Each node is a label, and arrows point toward labels that dominate it. Information may flow along these arrows or remain at the same label.

The overhead is administrative: every distinct combination of compartments is in effect a new label, and combining information from two compartments produces a label that readers of either compartment alone cannot see.

Outside government, Bell-LaPadula has seen little use, because organizations’ access policies rarely reduce to an ordering of levels.

The Biba Integrity Model

Bell-LaPadula does not protect trustworthy data from being corrupted by sources that should not write it. The Biba model has the same structure and the opposite goal. Subjects and objects carry integrity levels, where a high level means the data is trusted and the subject is trusted to produce it. The two rules are Bell-LaPadula’s reversed:

  1. No read down: a subject may read an object only if the object’s integrity level is at least as high as the subject’s. A trusted process may not take input from an untrusted source.

  2. No write up: a subject may write an object only if the subject’s integrity level is at least as high as the object’s. An untrusted process may not modify trusted data.

Biba protects trusted data from contamination. The strict rules are a poor fit for real systems because programs that process untrusted input are the normal case.

Windows Mandatory Integrity Control implements a restricted form of Biba: processes and securable objects have integrity levels, and the default rule prevents a process from modifying an object at a higher level regardless of the object’s discretionary permissions. It does not enforce Biba’s no-read-down rule. Its first main use was running a browser at low integrity, so that an exploited browser could not modify the user’s or the system’s files.

The Chinese Wall Model

The Chinese Wall model is for firms that serve clients who compete with each other. Its access decision depends on what a subject has already done. Objects are organized in a two-level hierarchy: each object belongs to one company dataset, which is all the data the firm holds about one client, and each dataset belongs to one conflict of interest class, which groups the datasets of companies that compete.

The read rule is: a subject may read an object in a company dataset only if everything the subject has previously read is either in the same dataset or in a different conflict of interest class.

Before the first read, every dataset is available. After an employee reads one airline’s data, the other airlines in that class are denied, and companies in other classes are still available. The system must record every access, and the record persists across login sessions.

For example, an advertising agency places Rutgers and NYU in the same conflict of interest class. Once an employee reads data from the Rutgers dataset, they cannot read data from the NYU dataset.

The write rule prevents information from passing between competing clients through another dataset. A subject may write to a company dataset only if it may read that dataset and has no permission to read data from any other company dataset, except sanitized data. Sanitized data has been altered so that it cannot be traced to its source company. Reading sanitized data does not create a conflict, and it may flow between datasets. Creating sanitized data requires a trusted procedure outside the ordinary write rule.

For example, the advertising agency also serves Delta Air Lines, whose dataset belongs to a different conflict of interest class from the universities. Alice may read Rutgers and Delta data, while Bob may read NYU and Delta data. Without the write rule, Alice could copy Rutgers data into Delta’s dataset, where Bob could read it. The write rule prevents this by denying Alice permission to write to Delta’s dataset while she has permission to read Rutgers data.

The model is a dynamic form of separation of duties, the principle that a task capable of causing serious harm is divided so that one person cannot complete it alone.

Type Enforcement

Bell-LaPadula and Biba compare ordered labels. The threat on a server is a compromised program, and the policy a server needs is a list of which programs may perform which operations on which files, and only those operations. With ordered labels, permissions follow from positions in a hierarchy. Allowing a program to read one file may also allow it to read files at lower levels, even if the policy should forbid those reads. Type enforcement allows each permission to be specified independently.

Type enforcement is an implementation of the access matrix in which the rows and columns are classes rather than individuals.

Every subject is assigned a domain, which is a class of subjects, and every object a type, a class of objects. A policy is a list of rules, each allowing a domain to perform certain operations on a type, and anything the policy does not allow is denied. There is neither a hierarchy nor a notion of up or down. Grouping processes and files into classes reduces the number of rules needed to describe their permissions, which keeps the size of the matrix manageable.

SELinux is the implementation of type enforcement in the Linux kernel. Its check is a second reference monitor that runs after the ordinary permission bits, and either check can deny access. The benefit appears when a program is compromised: the process is still running in its domain, so even if running as root, it can touch only what the policy allows that domain. The drawback is a potentially large policy set, and a missing rule can make a program fail with a permission error.

Role-Based Access Control

In an organization, rights are associated with jobs. Role-based access control (RBAC) models that with four kinds of entities:

Permissions are assigned to roles and users are assigned to roles. A user never holds a permission directly, and the roles active in a user’s session define what the user can do.

The benefit is administrative: permissions associated with a job can remain stable while users change as people are hired, leave, or change positions.

Roles resemble Unix groups: both let an administrator manage permissions for many users together. A group is a collection of users, while a role is a collection of permissions associated with a responsibility, such as processing payroll. In RBAC, users receive permissions through their assigned roles. Group-based systems may also grant permissions directly to individual users.

A session records which of a user’s assigned roles are currently active, allowing the user to activate only the permissions needed for a specific task. Switching active groups can serve a similar purpose. RBAC makes the distinction between assigned roles and active roles an explicit part of the access control model.

Roles usually correspond to job functions, with permissions such as approving a payment or issuing a refund, but they can also group file access or narrower technical permissions. RBAC is used within applications, databases, directory services, and cloud platforms. Its defining feature is how permissions are assigned and activated, rather than the kinds of operations they control.

RBAC fails when roles multiply: a role for every combination of permissions anyone has ever needed produces role explosion, with the structure harder to audit than the permissions were. Attribute-based access control (ABAC) generalizes roles to rules that test attributes of the subject, the object, and the environment, such as the user’s department, the document’s classification, and the time of day.

The Models Compared

Each model decides the same question, whether a subject may perform an operation on an object, from a different kind of label and a different rule:

Model What the label is The rule What it protects
Discretionary Owner and permission entries The owner decides Whatever the owner chooses
Bell-LaPadula Classification and clearance No read up, no write down Confidentiality
Bell-LaPadula with compartments Level plus compartments Read only what the label dominates Need to know
Biba Integrity level No read down, no write up Integrity
Chinese Wall Company dataset and conflict class One dataset per conflict class, fixed by the first access Conflict of interest
Type enforcement Domain and type Only what a rule allows Confinement of programs
Role-based Role Permissions follow the role Administrative scale

A real system runs more than one model, with one layered above another. Bell-LaPadula assumes discretionary permissions beneath it, and a Linux server with SELinux runs the Unix bits with type enforcement above them. An Android phone runs three layers:

  1. Unix permissions, with each app as its own user, keep apps out of each other’s files.

  2. SELinux confines each app’s process to what the policy grants.

  3. The Android framework’s permission model decides whether an app may use the camera or read contacts.

Each layer expresses rules that the one below it cannot.

What You Don’t Need to Study

The following are not required for the exam:

Week 7: Memory Vulnerabilities and Defenses

Memory-safety bugs violate an object’s bounds or lifetime. They can expose secrets, corrupt data, or let an attacker redirect a program’s execution.

Hijacking and Injection

Control-flow hijacking redirects a program’s execution, usually by corrupting a return address or a function pointer. Code injection places the attacker’s own instructions in the program and arranges to run them. A stack buffer overflow often does both at once. Hijacking and injection are related actions rather than separate categories.

Running code in another process gives the attacker that process’s access. This is worth doing when the program runs with more privilege than the attacker has, when it runs on a machine the attacker cannot log in to, or when it holds secrets the attacker cannot otherwise read. A setuid program runs with its owner’s privileges, so a setuid-root program can give an attacker root. Making a network service run attacker code is remote code execution.

Behind each of these is a program that made an assumption about its input without checking it. A vulnerability is a weakness that can be exploited; an exploit is the input or program that takes advantage of it. The same bug can crash one build and allow code execution on another, because exploitability depends on the surrounding code, the memory layout, and the defenses in place. Encryption and signatures do not make a vulnerable parser memory-safe: the receiving program still has to parse the input, sometimes before it can verify it.

Memory Layout and the Stack

A process runs in its own virtual address space, divided into regions: the read-only text segment of instructions, the data and BSS segments of global variables, the heap for dynamically allocated memory, and a stack for each thread. The program writes to the stack, the heap, and its globals, so all three can be overflow targets. The text segment is read-only.

The stack supports function calls. In the conventional x86 layout used here, each call gets a stack frame holding its stack-passed arguments, saved registers, local variables, and a return address that the processor jumps to when the function returns. Arguments and locals can instead live in registers, and return-address handling varies by architecture. In this layout a local array sits at a lower address than the return address, and arrays fill toward higher addresses, so a write that runs off the end of a local array moves toward the saved return address.

Stack Buffer Overflows

A buffer overflow writes more data into an array than it can hold, overwriting whatever is next in memory. Writing past an array is undefined behavior in C: the processor checks page permissions, not array bounds, so the write usually succeeds silently and the problem surfaces later. When the overflow reaches the return address, the function’s return can send the processor to an invalid address (a crash, which is a denial of service), to existing code, or to attacker-supplied instructions in the buffer.

An overflow that changes a nearby decision variable rather than the return address is a data-only attack: the program runs its own instructions in order and still does the wrong thing. Whether a given overflow reaches a particular variable or the return address depends on how the compiler laid out the frame.

gets() cannot be used safely because it is never told the size of its buffer. The counted functions take a length, but each counts something different: strncpy writes n bytes, padding short strings with null bytes but possibly leaving longer strings unterminated, strncat limits the bytes appended rather than the destination size, and snprintf counts the terminating null within its limit. They prevent an overflow only when the programmer passes the right size, leaves room for the terminating null, and handles truncation. That size has to come from the destination’s capacity, not from sizeof applied to a pointer, which yields only the pointer’s width. The flaw is a missing or wrong size check, not any one function name.

Shellcode is machine code an attacker places in memory to run after a hijack, written to avoid bytes the input path rejects, such as null bytes, and to fit whatever space the bug makes available. A NOP sled is a run of do-nothing instructions before the shellcode that widens the range of addresses a jump can land on. Neither helps once the target memory is non-executable.

Reading Past a Buffer

An out-of-bounds read accesses memory beyond an object’s bounds. It can disclose secrets or pointers when the program exposes the result, or it can crash the program. A leaked pointer reveals the base of a randomized region and undermines address randomization for that region. Reading past a buffer is a vulnerability on its own, separate from the write overflows above.

Heap Corruption and Lifetime Errors

Heap memory is handed out by an allocator that keeps bookkeeping for each block. Traditional allocators often store that metadata next to the user data; others keep it separately. An overflow out of one block can corrupt a neighboring object or the allocator’s metadata, and in older allocators a forged pointer could produce an arbitrary write to an address of the attacker’s choosing. Overwriting a function pointer or a C++ vtable pointer redirects the next call.

Two errors violate an object’s lifetime rather than its bounds. A use-after-free uses a pointer after the memory is freed; if the attacker arranges for the freed block to be reused for their own data, the stale pointer leads into it. A double-free frees the same block twice, which can corrupt the allocator’s bookkeeping or make a hardened allocator abort. These are temporal errors, as opposed to the spatial errors of overflows, and they are hard to find because the symptom appears far from the cause. Type confusion uses an object as a type it is not, so the code reads its fields with the wrong layout and may treat ordinary data as a pointer.

Integer Errors

Fixed-width integer types have limited ranges. Unsigned overflow wraps in a way C defines; signed overflow is undefined behavior, so a compiler may assume it never happens and drop a check that depends on it. An integer error becomes a memory error when a wrapped size produces an allocation smaller than the code believes, followed by writes that overrun it. Checking that a size calculation fits before performing it, and rejecting a negative length before it is converted to an unsigned size, closes that path. A signed-to-unsigned mismatch lets a negative length pass a signed upper-bound check and then become a huge value when passed as an unsigned size to a copy function. Narrow protocol fields and the 32-bit default int keep these bugs reachable even on 64-bit systems.

An off-by-one error reads or writes one position past a boundary. A write one position past can corrupt a saved value or the low byte of a pointer, and it can be the start of a larger overflow.

Defenses

No single defense closes the hole. Each answers a specific attack and leaves something open, so they are deployed in layers.

The first layer prevents and finds bugs before release:

When a bug survives, the next layer makes it harder to exploit. Non-executable memory stops the processor from running injected code and forces attackers to reuse existing code. NX is the hardware page permission, DEP is the operating-system protection built on it, and W^X is the policy that no page is writable and executable at the same time. They are related, not three names for one thing.

Non-executable memory does not stop code reuse. A return-to-libc attack redirects execution to an existing library function, and return-oriented programming (ROP) generalizes it by chaining short instruction sequences called gadgets, each ending in a return, with the chain supplying successive gadget addresses and any operands they need. A sufficient set of gadgets can perform arbitrary computation without injecting any code.

Three more defenses raise the cost of a surviving bug:

Hardware and compiler checks detect invalid control transfers, pointer tampering, and invalid memory accesses:

Defense in depth combines these independent measures so an exploit must defeat every one on its path, which pushes an attacker toward rarer and less reliable conditions. A data-only attack bypasses most of them, so a memory-safe language is the deeper fix. Rowhammer is a reminder that these defenses assume memory holds what was written to it, which repeated access to dense DRAM can violate.

What You Don’t Need to Study

Week 8: Command Injection and Input Validation Attacks

Injection turns untrusted data into instructions. Unsafe name resolution directs a program to a file, executable, or library the attacker chose. Containment assumes that some program will be compromised anyway and limits what it can see, do, and consume.

Command Injection

An interpreter is any component that parses text into actions: a database engine, a shell, an expression evaluator, a template engine, or a logging library. Injection occurs when input from outside the program reaches an interpreter as part of a command and the interpreter reads some of it as instructions.

Three conditions produce injection:

  1. An interpreter.

  2. Input the program does not control.

  3. A command built by pasting that input into a string.

Removing any one removes the attack, and most defenses remove the third.

The root cause is that the program does not separate data from instructions. Only the interpreter knows which characters are syntax, and it cannot tell which characters the programmer wrote.

Command injection does not need memory bugs. The program’s own interpreter runs the attacker’s command with the program’s privileges, so the defenses against memory corruption do not apply.

SQL Injection

A query built by string concatenation lets a quote in the input close the programmer’s string. The rest of the input is then treated as SQL. A comment marker will discard whatever the programmer wrote after it. This can allow an attacker to bypass a login, read or modify other tables, and, in some databases, reach files or programs on the server.

Two variations extend the basic attack:

The defenses fall into an order of preference:

Syntax, special characters, and available operations differ among databases, so a filter or escaping function written for one might be wrong for another.

Document databases that take queries as structured objects are subject to operator injection: an object containing a query operator is supplied where a string was expected. The defense is to check or convert types before the value reaches the query.

Shell Command Injection

The standard C library functions system(), popen(), and their equivalents in other languages pass a string to sh -c, which gives the shell’s whole language to the attacker. Shell metacharacters separate commands, pipe output, run commands conditionally, substitute a command’s output into the line, redirect input and output, and expand wildcards. Filtering can be error-prone and double quotes still allow command substitution inside the string.

The defenses, in order:

  1. Do not invoke a shell. Use a library call, or start the program directly with an argument vector (execve(), or subprocess.run() with a list), so that each argument arrives as one string that no shell parses.

  2. Guard against argument injection, since the program being run still parses its own command line and a value beginning with - can be read as an option. For some programs. the fixes are -- to end options, rejecting option-like values, or prefixing a file name with ./.

  3. If a shell is unavoidable, fix the command structure, validate each value, and quote with a function written for that shell. Quoting is secondary because the rules differ between shells and the shell is not always the only program that parses the arguments.

  4. Apply the Principle of Least Privilege, so that an injected command inherits as little authority as possible. This is a design principle rather than a fix for one bug, and it limits the damage from every bug that the other defenses miss.

Interpreters Hidden in Libraries

eval() takes a string and runs it as code in the program’s own language, so input meant to be a number or an expression can contain function calls, imports, or a command that starts a shell.

The difference from shell command injection is the interpreter. The shell parses a command line, while eval() sends the input to the language interpreter itself, with every library the program has loaded. The fix is the same: parse the input as a number or with a data parser, which cannot run anything, rather than evaluating it.

Libraries also contain interpreters that programmers do not know about:

Validating and Sanitizing Input

Three terms describe how input is handled before it reaches an interpreter:

Separation is preferred because it does not depend on predicting the interpreter. Validation is still needed after it, since a bound value can be the wrong value.

An allowlist defines what is permitted and rejects everything else. A denylist names what is forbidden and permits everything else, which makes it a prediction about what the attacker will write, and an interpreter can construct the forbidden string after the filter has run.

Canonicalization converts every equivalent representation of an input into one chosen form. The rule is to decode and canonicalize first, then validate, and never decode again, since a check on one representation does not cover the one the interpreter will see.

Four more rules follow from the same idea:

  1. Sanitization has to match the context of use, because SQL, a shell, HTML, and a file path have different special characters.

  2. Validating at a program’s entry points and trusting everything inside fails for the same reason second-order injection does.

  3. Checks in the browser are bypassed by sending the request directly.

  4. Length limits do not stop injection.

Path Traversal and Path Equivalence

Path traversal uses .. in a supplied path to reach files outside the intended directory. The component can appear anywhere in the path and can be encoded so a check made before decoding does not see it. Searching for the characters is not foolproof, since legitimate names contain dots and a .. that stays inside the tree is harmless. The property to enforce is where resolution ends.

Path equivalence is the fact that many strings may refer to the same file: through . and redundant separators, case-insensitive filesystems, Unicode normalization, symbolic links, and hard links. A symbolic link makes a path that passes every textual check resolve somewhere else.

The defenses, from weakest to strongest:

  1. Canonicalize with realpath() and check the prefix, including its trailing separator.

  2. Have the kernel enforce the restriction during resolution, so .. and links cannot leave a directory.

  3. Map an identifier to a file instead of accepting a path.

  4. Run with permissions that limit what a traversal reaches.

Time-of-Check to Time-of-Use

A TOCTOU race condition occurs when a program checks a name and then uses it, and the binding between the name and the object changes in between, usually through a symbolic link or directory entry the attacker controls.

Two cases are the classic ones:

The defenses share one rule, which is to operate on the object rather than on the name:

Privilege separation removes the race condition by having a process with the user’s own permissions open the file and pass the descriptor to the privileged part.

Inherited Environment, Search Paths, and Library Injection

A program inherits environment variables, open descriptors, a working directory, and a file-creation mask from whatever started it, which may be the attacker. A search path such as PATH decides which program runs when a script names one, so a counterfeit placed earlier in the path runs first. The fixes are absolute paths and an environment the privileged program constructs itself.

Library injection makes a program load library code the attacker controls, and that code runs with the program’s authority. It takes two forms:

In both cases, a library or program loaded by name from a location the attacker can influence is code the attacker chose.

Function interposition replaces or wraps one function that a program expected to get from a shared library. The loader resolves each function name to the first definition it finds, so a preloaded library that defines rand() or the clock function replaces it without modifying the program, and a wrapper can record a function’s arguments and then call the original. Interposition has legitimate uses in debugging and testing. In an attacker’s hands it captures data, changes arguments, or makes an authentication check return success.

Code That Arrives by Package Name

A package name resolves to code that runs with the installer’s privileges, and installing a package can run its install scripts before the package is ever imported.

Three attacks exploit the choice of which package a name resolves to:

The defenses bind a name to a repository, run builds with few credentials and limited network access, and pin and review dependencies.

Containment

Operating system access control identifies users, not programs, so a compromised process holds every right of its user and the permission model cannot express a rule about one program.

The Principle of Least Privilege is a design principle: a program should run with the fewest permissions its job needs. Three ways to approach it fall short:

  1. A dedicated account for the service still reaches every world-readable file.

  2. Dropping privileges depends on the program’s own code.

  3. Privilege separation depends on the program’s own code.

Containment enforces limits from outside the process. The limits hold after the process is taken over, apply to programs never written to restrict themselves, and allow code that was never trusted, such as apps, web scripts, and dependencies, to run at all. The environment that confines a program is a sandbox.

A confined process has to be kept from more than files:

The kernel or hypervisor that enforces a boundary is part of the trusted computing base, since the boundary holds only if that layer is correct.

Every mechanism is judged by five questions:

  1. What does it restrict?

  2. Who enforces it?

  3. What interface can the confined code still reach?

  4. What overhead does it add?

  5. How does it fail?

The second question places each mechanism at one of four levels: a user-level monitor process, a language runtime, the kernel, or the hypervisor. Each level trusts everything beneath it, and going down the list the enforcement gets stronger and the interface narrower.

chroot and Jails

chroot changes where path resolution starts for a process and its children. It restricts only names:

Jails added a private process view, a network address, and a restricted root.

The lessons are that hiding names is not the same as restricting operations, and that root inside a boundary has to be a weaker root than root outside.

System Call Filtering

The system call interface is the natural point for complete mediation, since a process acts on the world only through it.

Early sandboxes placed a monitor in a separate process, which had three problems:

seccomp-BPF moves the filter into the kernel. A process installs a filter that the kernel runs on every system call. The filter sees the call number and its integer arguments and allows the call, fails it, or kills the process.

The filter never reads process memory, so it cannot see a file name and cannot decide which files a process may open. Its purpose is to remove the kernel code behind unused calls from a process’s reach.

The overhead per call is small. The real work is a correct policy, which breaks the program if too strict and adds little if too loose.

AppArmor

AppArmor restricts a program by pathname: a profile attached to the program lists the files it may read, write, or execute, along with its network access.

The check runs inside the kernel after the path has been resolved, on the object actually being opened, so the race condition that defeats an external monitor does not apply.

The two kernel mechanisms divide the work: seccomp-BPF limits which system calls a process can make and cannot see names, while AppArmor allows the call and limits which objects it reaches.

Path-based rules are easier to write than label-based ones such as SELinux, but a file with two names can fall under two rules.

Language Runtime Sandboxes

A language runtime such as the Java virtual machine, a JavaScript engine, or WebAssembly confines a program from inside. It verifies code before running it, checks every index and type, and manages memory itself, so the program cannot form a pointer, read outside its memory, or make a system call. The program reaches the outside only through the library the runtime exposes.

The sandbox is only as correct as the runtime, which is a large program in C or C++. A memory bug in the runtime gives the program native code in the host process. A language sandbox needs an operating system boundary beneath it, which is how browsers are built.

Application Sandboxes and Permission Models

Phones make the application, rather than the user, the principal:

Shared resources such as the camera and contacts are reached only through system services that check permissions before acting.

Permission models moved from install-time, all-or-nothing grants to requests at first use that the user can refuse or revoke, with finer grants such as approximate location and one-time access.

The model has three limits:

An escape needs a bug in the kernel or in a system service the app can reach.

Namespaces, Control Groups, and Capabilities

Three Linux kernel features confine groups of processes, and each controls a different thing:

A user namespace maps root inside to an unprivileged user outside. That lets ordinary users create other namespaces, and it also lets them reach kernel code that once required root, a steady source of privilege-escalation bugs.

Containers

A container is a process started in new namespaces, placed in control groups, given reduced capabilities, run under a seccomp filter and an AppArmor or SELinux profile, with a root filesystem built from an image. The container runtime does the setup; the kernel itself does not know what a container is. Containers were built for packaging and deployment, and isolation was a side effect.

The benefits, at close to zero overhead:

A container escape gives code inside access to resources outside. The routes to one follow from the shared kernel:

Containers separate cooperating services well and are not, on their own, a boundary for hostile code. Rootless runtimes and running containers inside virtual machines reduce what an escape reaches.

Virtual Machines

A hypervisor, or virtual machine monitor, presents a complete computer to each guest operating system. The confined code is an entire operating system, and the interface it reaches is virtual hardware.

Three parts of the machine are handled differently:

A Type 1 hypervisor runs on the hardware. A Type 2 hypervisor runs under a host operating system, which then joins the trusted computing base.

Each guest has its own kernel, so a kernel bug in one guest stays in that guest, and the interface exposed to a guest is far narrower than a system call interface. A guest application’s system calls enter the guest kernel, not the hypervisor, which is the central difference from a container.

The overheads are transitions into the hypervisor, I/O through emulation, memory for a kernel per guest, boot time in seconds, and another operating system to patch.

The risks:

Containers inside a virtual machine share that guest’s kernel, and an escape from the container still leaves the hypervisor boundary around the guest. Cloud providers separate customers this way.

Virtualization-Based Security

Virtualization-based security uses a hypervisor that starts before the operating system to protect parts of that operating system from its own kernel. A secure environment whose memory the normal kernel cannot touch decides which kernel code pages may execute and holds the credentials used to authenticate to other machines.

The limits:

Comparing the Mechanisms

The strength of a boundary depends on three things:

  1. The size of the interface the confined code can reach.

  2. The correctness of the layer that enforces it.

  3. The correctness of its configuration.

A virtual machine has the smallest interface and strongest enforcement and adds the most overhead. A system call filter adds almost none and narrows the interface without closing it. Real systems layer them.

Every mechanism assumes the layer beneath it is honest: a filter trusts the kernel, a container trusts the kernel it shares, a virtual machine trusts the hypervisor, and the hypervisor trusts the firmware and the processor.

What You Don’t Need to Study

These exclusions apply to the command injection and containment material. Injection into web pages, prompt injection and AI security, and covert channels are not part of this material. We will cover these topics later.

The following are not required for the exam: