Open-ended Portion (80%)

Select one of the following questions per team.

All open-ended questions should use the parameters for BOOM shown in the table below, unless otherwise specified. These should already match the CS152SWPredBoomConfig and CS152SmallBoomConfig configurations provided with the lab.

BOOM open-ended configurations

	Option 1	Option 2
Configuration	CS152SWPredBoomConfig	CS152SmallBoomConfig
Issue width	3	1
Fetch width	4	4
ROB	96 entries	32 entries
Issue slots	32 entries	8 entries
Integer register file	96 physical registers	52 physical registers
FP register file	64 physical registers	48 physical registers
LDQ/STQ	16 entries	8 entries
Max branches	12 branches	8 branches
L1D capacity	16 KiB
L1D associativity	4 ways
MSHRs	2 MSHRs

Designing Your Own Branch Predictor

The version of BOOM provided in the CS152SWPredBoomConfig uses a simple bimodal predictor consisting of a Branch History Table (BHT) of 256 2-bit saturating counters. This was the same scheme implemented by the MIPS R10000, although with 512 entries instead. For this problem, your goal is to build an improved branch predictor for BOOM that performs better than this baseline.

Feel free to scour the abundance of literature and historical examples for ideas. The branch-prediction sections of Computer Architecture: A Quantitative Approach (Hennessy and Patterson) survey the common dynamic branch prediction techniques and are a good starting point. A good design to look into is the two-level tournament branch predictor from the Alpha 21264 (R. E. Kessler, “The Alpha 21264 Microprocessor,” IEEE Micro, 1999), which combines three predictors:

• A global predictor with a 4096-entry table of 2-bit saturating counters indexed by the global history of the last 12 branches

• A local predictor with a 1024-entry table of 10-bit branch patterns indexed by PC, which is then used to index a set of 3-bit counters

• An arbiter (or “choice”) predictor with a 4096-entry table of 2-bit counters indexed by global history, used to select either the global or local prediction as the final one

Especially impressive designs could attempt to beat the hardware TAGE predictor that ships with BOOM. A ready-made configuration is provided for the comparison — CS152TAGELBoomConfig is the same core as CS152SWPredBoomConfig with a different hardware predictor:

cd ${LAB3ROOT}/sims/verilator
make CONFIG=CS152TAGELBoomConfig
make CONFIG=CS152TAGELBoomConfig run-bmark-tests

The Chisel implementations of various predictor components, including TAGE, BTBs, BHTs, and the RAS, are available in ${LAB3ROOT}/generators/boom/src/main/scala/v3/ifu/bpd.

C++ Framework

For the implementation, we will leverage the C++ branch predictor framework that exists in BOOM, which lets one more easily construct software models of a branch predictor’s intended functional behavior for rapid prototyping and verification.

Although it presents a relatively simplified interface compared to a real hardware predictor module, it is flexible enough to admit a wide space of potential designs while abstracting away much of the complexity of the surrounding logic in the core.

Implement your branch predictor design in ${LAB3ROOT}/generators/boom/src/main/resources/csrc/predictor_sw.cc. This file contains three functions to modify:

Function	Description
initialize_branch ↪ _predictor()	This is called at the beginning of simulation and can be used to initialize global state.
predict_branch()	This is called to provide a prediction for a branch or jump instruction with the given PC (ip). The global history of the most recent branches is passed as a bit vector in hist. The globalHistoryLength config parameter defaults to 32 for the C++ predictor. The prediction is returned by assigning 1 for taken and 0 for not taken to the variable pointed to by pred.
update_branch()	This is called to update the predictor state with branch resolution information. Updates occur non-speculatively in program order. ip provides the PC of the branch or jump instruction, hist provides the global history, and taken provides the outcome of the branch or jump.

Both predict_branch() and update_branch() may be called multiple times per cycle. Remember that the branch predictor is inherently accessed speculatively, so you may see requests for branches that are later squashed by the pipeline.

Simulating

Build the simulator¹ and run the benchmark suite using the same flow as the directed portion (note the different top-level configuration):

cd ${LAB3ROOT}/sims/verilator
make CONFIG=CS152SWPredBoomConfig
make CONFIG=CS152SWPredBoomConfig run-bmark-tests

After the first build, each time you edit predictor_sw.cc rebuild the simulator with the rebuild-csrc target, which recompiles the C++ predictor model and relinks the simulator in a few seconds without re-elaborating the Chisel design:

make CONFIG=CS152SWPredBoomConfig rebuild-csrc

To run an individual benchmark only (e.g., dhrystone; you may need to run run-bmark-tests first to set up symlinks):

make CONFIG=CS152SWPredBoomConfig run-binary LOADMEM=1 \
    BINARY=output/chipyard.harness.TestHarness.CS152SWPredBoomConfig/dhrystone.riscv

Reading the .out summary

The .out file is the simulator’s console output with a branch-prediction summary appended at the end. BOOM traces every branch and indirect jump as it commits, and counts one as mispredicted when the front end fetched the wrong path and had to be redirected once the branch resolved in Execute. The last three lines are the aggregate result for the run:

Mispredicted 13/77.0 jalrs, 0.16883116883116883
Mispredicted 550/6468 brs, 0.08503401360544217
Mispredicted 563/6545.0 all, 0.08601986249045072

Each line is mispredicted / executed followed by the misprediction rate, for conditional branches (br), indirect jumps and returns (jalr), and both together. Here 8.5% of conditional branches missed, i.e., 91.5% prediction accuracy — this is the number to report, and the brs line is the one to quote: your predictor supplies direction predictions for conditional branches, while jalr misses come from target prediction in the BTB and RAS, which you are not modifying. (Direct jumps are excluded, since their target is known at fetch.)

Finding the branches that hurt

Above the summary are five top-20 lists of individual branch sites, which are how you work out why a benchmark underperforms. They list the same branches sorted five ways: by misprediction rate (highest and lowest), by number of mispredictions, by number of correct predictions, and by number of executions. Every entry has the form (PC, mispredicted/executed, misprediction rate, type):

(0000000080002046, 794/796, 0.9975, br)

The conditional branch at PC 0x80002046 committed 796 times and was mispredicted on 794 of them. The two lists sorted by misprediction rate are dominated by branches that execute once or twice and cost nothing; the lists sorted by count — frequently mispredicted and most frequent — are the ones worth attacking. To identify a PC, search for the address in the benchmark’s disassembly (see Benchmarks below).

Validating your predictor without a simulation

A full RTL run takes minutes per benchmark, which is a slow way to discover that a table index was off by one. Instead, you can replay a captured branch trace through your predictor as an ordinary host program.

First capture a trace. It records every committed branch, so it depends only on the program and not on your predictor. You only need to capture this once per benchmark and reuse it for every following design you try:

cd ${LAB3ROOT}/sims/verilator
make CONFIG=CS152SWPredBoomConfig run-binary LOADMEM=1 \
    BINARY=output/chipyard.harness.TestHarness.CS152SWPredBoomConfig/median.riscv \
    BPD_TRACE=${LAB3ROOT}/lab/open1/traces/median.trace

That is an ordinary run — it still writes median.log and median.out — with BPD_TRACE additionally saving one <pc> <taken> <br|jalr> record per committed branch. Then, after each edit to predictor_sw.cc:

make -C ${LAB3ROOT}/lab/open1 check              # replay every trace in lab/open1/traces/
make -C ${LAB3ROOT}/lab/open1 check WORST=10     # ...and list the worst branch sites

trace              branches   mispredicted   accuracy
median.trace           6422            527     91.79%

This compiles your predictor_sw.cc together with a small driver and feeds each committed conditional branch through predict_branch() and update_branch(), maintaining a 32-bit global history the way the hardware does. The result is a plain host binary, so gdb, printf and -fsanitize=address all work normally on it.

Treat the number as a guide rather than a result. The hardware calls predict_branch() speculatively for every slot of every fetch packet and passes the global history as of fetch, whereas the replay calls it once per committed branch in program order. A predictor that modifies its state inside predict_branch() will therefore look better offline than it does in simulation. In our testing, a design that replayed at 91.8% measured 90.8% in RTL. Iterate without the simulator, then confirm with run-bmark-tests and report the numbers from the .out files.

Benchmarks

The source code for all benchmarks can be found in ${LAB3ROOT}/toolchains/riscv-tools/riscv-tests/benchmarks/. First initialize the riscv-tests submodule:

git submodule update --init ${LAB3ROOT}/toolchains/riscv-tools/riscv-tests

The disassemblies that correspond to the pre-installed binaries are available at ${RISCV}/riscv64-unknown-elf/share/riscv-tests/benchmarks/*.riscv.dump.

Submission

Option 1

Present the IPC and branch-prediction accuracy results of your custom predictor on all benchmarks in a single table. Describe your design approach and any implementation challenges in detail, and explain your predictor’s performance characteristics. Be sure to cite the appropriate sources if you borrowed from existing concepts. Then, answer the following questions:

• How did you calculate the amount of state your branch predictor has?

• How do certain parameters (e.g., number of entries) impact accuracy?

• Which branches or patterns were easier or harder to predict?

• What kind of application code do you expect your predictor to perform better or worse on?

• Do you foresee any challenges with the implementation of your predictor algorithm as a hardware block within a superscalar, out-of-order core?

• What changes or alternative approaches would you pursue as future work if more time were available?

Feel free to reach out to your GSI if you need help understanding BOOM, branch prediction schemes, or anything else regarding this problem.

Recreating Spectre Attacks

It turns out that BOOM, like many out-of-order processors, is susceptible to a class of microarchitectural side-channel attacks that exploit branch prediction, speculative execution, and cache timing to leak information from memory, bypassing security mechanisms such as virtual memory and bounds checks. These first came to prominence with the Spectre and Meltdown vulnerabilities disclosed in 2018. For this problem, your goal is to mount a Spectre attack on BOOM to extract secret data from protected kernel memory.

Background

First read the Spectre paper (Kocher et al., Spectre Attacks: Exploiting Speculative Execution, IEEE S&P 2019) and the Google Project Zero post to understand the basic principles and techniques behind the Spectre exploit. The proof-of-concept in Appendix C of the paper may be a useful reference as you write your code.

Although not the focus of this problem, it is also worth reading a little about Meltdown (Lipp et al., Meltdown: Reading Kernel Memory from User Space, USENIX Security 2018), a closely related variant that arises from deferred TLB permissions checks.

Attack Scenario

In this scenario, you control a malicious adversary that runs as an unprivileged program in user mode (U-mode) on top of the RISC-V proxy kernel (pk), a lightweight execution environment that assumes the role of a minimalistic operating system. pk is designed to support tethered RISC-V implementations with limited I/O capability and thus handles I/O-related system calls by proxying (forwarding) them to a host – in this case, the machine running the simulation.

pk itself runs in the higher-privilege supervisor mode (S-mode) but shares the same virtual address space as the user program. The lower 2 GiB of the virtual address space is reserved for the user program, while pk is mapped into the upper portion after 0x80000000.² This is a common technique in operating systems to facilitate more efficient communication between kernel and user space. For our purposes, this fact merely makes it slightly easier to reason about the addresses of the secret data and the privileged code being targeted.³

The objective of the adversary is to learn the values of a contiguous 128-byte array in the static .data.secret section in pk, representing a secret key. This data is ordinarily inaccessible to user programs, as it resides in a page with supervisor-only read permissions.

We deliberately introduce a few artificial conditions to simplify the task without compromising the fundamental methodology:

• The secret data is placed at a fixed virtual address that is already known.

• The attack vector is a custom syscall handler in pk that contains a vulnerable Spectre gadget by design.

• The Spectre gadget leaks only one bit at a time to minimize noise from cache thrashing.

The Spectre gadget, shown here lightly edited, is very similar to the canonical example for Spectre Variant 1 (bounds check bypass):

uint8_t leak_array[128]; // Two 64-byte cache lines

int sys_leak(size_t index, int shift)
{
    if (index < sizeof(leak_array)) {
        uint8_t data = leak_array[index];
        index = (data >> shift) & 0x1;
        return leak_array[index * 64];
    }
    return -1;
}

The first array access, which involves an index controlled by the adversary through a syscall argument, can be used to speculatively read an arbitrary byte in memory. The second array access then reads from different cache lines depending on the data value and the shift argument.

Note that the bounds check in the if statement prevents the results of invalid accesses from becoming architecturally visible. However, side effects in the cache induced by the data-dependent load persist after speculative execution, and these side effects can be measured to infer data values. While several approaches to cache-based covert channels exist, a Prime+Probe attack is likely the most practical option given that BOOM does not presently implement an unprivileged cache flush instruction.⁴

The overall flow of the attack would proceed as follows:

1. Training step: Mistrain the branch predictor to strongly predict that the if condition for the bounds check will be true, generally by repeatedly invoking the syscall with valid inputs.

2. Prime step: Fill the cache sets that leak_array would map to with known lines.

3. Exploit step: Invoke the syscall with malicious arguments. Although the bounds check actually fails, the if condition is mispredicted as true, so the if body is speculatively executed. The inputs are specially crafted so that the out-of-bounds load points to a secret byte, of which one bit is used to construct the pointer for another load that evicts one of the primed lines. The misspeculated execution path is eventually reverted when the branch is resolved, but the cache state remains perturbed.

4. Probe step: Determine which line was evicted by measuring the access time to each line. The cache set that previously held the evicted line corresponds to the value of the leaked bit.

5. Repeat for enough samples to gain sufficiently high confidence.

It is not necessary to follow this procedure exactly. You may want to experiment with variations to improve accuracy and/or throughput.

Reverse Engineering

A pre-built pk-spectre executable is already provided along with the Lab 3 infrastructure. To figure out the virtual addresses of various symbols in pk (e.g., leak_array), refer to the symbol table in the fully linked binary:

riscv64-unknown-elf-readelf -s ${LAB3ROOT}/lab/open2/pk-spectre > pk.sym

To figure out the instruction PCs to compare to the BOOM traces, look at the disassembly:

riscv64-unknown-elf-objdump -d ${LAB3ROOT}/lab/open2/pk-spectre > pk.dump

To figure out the addresses of the secret data and to verify your results, dump the .data.secret section contents:

riscv64-unknown-elf-objdump -s -j .data.secret ${LAB3ROOT}/lab/open2/pk-spectre

Data words are displayed in big-endian byte order, i.e., the most significant (leftmost) byte in a word is stored at the lowest address. (The test data comes from the digits of π.)

Development and Testing

To help you start writing your code, ${LAB3ROOT}/lab/open2/spectre.c contains an example skeleton with helper functions to invoke the syscall and read the cycle counter. To compile:

cd ${LAB3ROOT}/lab/open2
make

Feel free to modify the user program however you wish: add a custom linker script, mix in assembly files, etc.

To run the simulation:⁵

cd ${LAB3ROOT}/sims/verilator
make CONFIG=CS152SmallBoomConfig run-spectre

The disassembled instruction trace and the console log go to ${LAB3ROOT}/sims/verilator/output/chipyard.harness.TestHarness.CS152SmallBoomConfig/pk-spectre.out and pk-spectre.log, respectively. Your attacker’s output (the leaked bytes) appears in pk-spectre.log.

To enable logging of dispatched instructions in BOOM, open ${LAB3ROOT}/generators/chipyard/src/main/scala/config/CS152BoomConfigs.scala and add enableDispatchPrintf = true to the BoomCoreParams(...) in the WithNCS152SmallBooms config, then rebuild (make CONFIG=CS152SmallBoomConfig).⁶ This should help give you a sense of the size of the speculative execution window prior to the branch mispredict recovery. (The enableDispatchPrintf field is added to BOOM by ${LAB3ROOT}/lab/patches/boom-dispatch-printf.patch, which build-setup.sh applies automatically.)

To quickly test cache eviction/measurement code and other utility functions, you can write a bare-metal program in ${LAB3ROOT}/lab/open2/baremetal.c. Simulations are much shorter, as this avoids waiting for pk to initialize and load the user program. This code executes in machine mode (M-mode) with physical addressing, and only a limited subset of libc is supported. Note: It is not possible to perform the entire attack in a bare-metal environment, as the victim syscall and secret data are not available without pk.

make CONFIG=CS152SmallBoomConfig run-binary-hex BINARY="${LAB3ROOT}/lab/open2/baremetal.riscv" 

Submission

Option 2

Your Spectre attack code should be submitted through Gradescope. In your report, explain how your code works, and describe any challenges encountered and solutions that you used. Then, answer the following questions:

• What is the accuracy and performance (cycles per secret byte) of your attack?

• What changes could you adopt to increase the speed (in cycles per secret byte) of your attack? What are the tradeoffs or disadvantages of such techniques?

• What are some hardware and/or software countermeasures against Spectre that you can think of? Discuss the advantages and disadvantages of each.

Feel free to reach out to your GSI if you need help understanding Meltdown/Spectre, BOOM, riscv-pk, or anything else regarding this problem.

Feedback Portion

In order to improve the labs for the next offering of this course, we would like your feedback. As in Lab 2, this is not part of your report: instead, fill out the Lab 3 feedback form. Every student should submit the form individually, including the questions about your team. It asks how long each portion took you, what you liked and disliked most, what you would change, what else you would like to explore in the open-ended portion, whether you are interested in modifying hardware designs as part of the lab, and how the work was divided within your team.

Feel free to write as much or as little as you prefer (a point will be deducted only if the form is left completely empty).

1. The build system has been slightly modified for this lab to avoid re-elaborating Chisel if only C++ resource files have been changed. ↩

2. This offset is specifically chosen such that this virtual address range is identical to the physical address range where pk resides, i.e., VA = PA. ↩

3. Meltdown can be mitigated in hardware by not forwarding faulting loads or in software by separating the user and kernel address spaces, accomplished through kernel page-table isolation (KPTI) in Linux. Neither of these, however, defends against Spectre. ↩

4. Flush+Reload is theoretically possible since the L2 cache controller provides a mechanism to flush specific lines, which also evicts from the L1 due to the inclusive property, but the requisite MMIO control registers are not exposed to U-mode by default. ↩

5. The 1-wide BOOM configuration is preferred as it simulates much more quickly. ↩

6. You may also want to disable enableBranchPrintf to make the log more readable. ↩