# Midterm

You may use any resource that existed prior to this exam opening, including websites, books, etc; but should not consult friends, tutors, forums, or other interactive help for this exam.

You must not share any information about this exam (even how you felt about it) with any party (even others who have taken it) until after it closes at 2020-04-06 23:59 EDT.

The following are all of the form "inverting ____ requires". To invert function f we mean, given f(m), compute m. Assume that

• You do not have access to the original message (not even as private information)
• You do not have the time to use brute-force approaches.
Question 1 (1 pt; mean 0.97) (see above)

Inverting a cryptographically secure hash requires

Question 2 (1 pt; mean 0.87) (see above)

Inverting a public-key encryption requires

Question 3 (1 pt; mean 0.76) (see above)

Inverting a private-key encryption requires

Question 4 (1 pt; mean 0.88) (see above)

Inverting a symmetric-key encryption requires

Untrusted agent U sends me a message M and a message signature S created by agent A using public key K.

Question 5 (dropped) (see above)

Which of the following should I definitely not get from U?

This question has been dropped because of an ambiguity in its wording. The intent was to suggest that if U is my witness that K belongs to A, then U can simply give me U's public key instead of A's public key. Unfortunately, I failed to mention that K was not part of a certificate, and since certificates are commonly used to allow U to give me K in practice the question became too vague to measure learning.

Question 6 (1 pt; mean 0.55) (see above)

Assume

• H(message) is the hash function
• P(message, key) is the public/private encryption function
• Y(message, key) is the symmetric encryption function

Give C-syntax Boolean expression, like M == Y(H(M),K), which is true if and only if the message was signed by A.

Key: H(M) == P(S,K)

The following discuss caches

Question 7 (1 pt; mean 0.94) (see above)

Large cache blocks improve cache performance when the code exhibits

Question 8 (1 pt; mean 0.82) (see above)

Set-associative caches are used instead of fully-associative caches because set-associative caches

Question 9 (1 pt; mean 1) (see above)

Set-associative caches are used instead of direct-mapped caches because set-associative caches

Question 10 (1 pt; mean 0.94) (see above)

Which code has better locality? Assume i and j are stored in registers and a is a 10,000-element array.

Question 11 (1 pt; mean 0.28) (see above)

Because 1009 is prime, the following will set all 1009 elements of a to 0 as long as x is not a multiple of 1009:

for(int i=0; i<1009; i+=1)
a[(i*x)%1009] = 0;


Consider x values 2, 31, and 505. Order these values from slowest to fastest assuming we have a

• 4-way set-associative cache with 32 sets
• 4 entries of a can fit in a single cache block

Assume that the (i*x)%1009 takes the same number of cycles regardless of the values of i and x.

For 2, we access items 0, 2, 4, 6, 8, .... That gives us 1 cold miss, then 1 hit, then 1 cold miss, etc: 50% hit rate.

For 31, we access items 0, 31, 62, 93, ...., 992, 43, 74, 85, ... That means every read is a miss, and even once we wrap around we'd on new blocks: 0% hit rate.

For 505, we access items 0, 505, 1, 506, 2, 507, .... Two misses, then size hits; 2 misses then 6 hits, etc: 75% hit rate.

Question 12 (1 pt; mean 0.42) (see above)

In your TLB code, you had no block offset because there was just one entry per block. We had just one entry per block because

If you have 52-bit addresses cached in a 16MB 8-way set-associative L2 cache with 64-byte blocks

Question 13 (1 pt; mean 0.86) (see above)

The set index is how many bits? Answer as a base-10 integer

Key: 15
Question 14 (1 pt; mean 0.93) (see above)

The block offset is how many bits? Answer as a base-10 integer

Key: 6
Question 15 (1 pt; mean 0.91) (see above)

The tag is how many bits? Answer as a C expression that evaluates to the correct number. You may use

• constants like 52
• the following variables
• bob (the number of block offset bits)
• sib (the number of set index bits)
• the following function
• log2(n) the log-base-2 of n
• the operators +, -, *, /, and <<
Key: 52 - bob - sib

Question 16 (1 pt; mean 0.94) (see above)

When running in user mode,

Question 17 (1 pt; mean 0.66) (see above)

We often say that "each thread has its own stack memory"; we mean that each

Question 18 (2 pt; mean 1.52) (see above)

In a multi-threaded environment, which of the following pairs of instructions always runs atomically; that is, that the result of running them is the same as if no other instructions were run in between them?

I eat a meal consisting of a bowl of soup and a bowl of ice cream, using the same spoon for both.

Question 19 (1 pt; mean 0.79) (see above)

Which of the following is concurrent but not parallel?

Question 20 (1 pt; mean 0.85) (see above)

Which of the following is parallel but not concurrent?

A memory leak in a process is limited to that process: when the process terminates, all its allocated memory will be reclaimed (that is, deallocated and made available to other processes).

Question 21 (1 pt; mean 0.44) (see above)

How is process memory reclaimed?

1. The loader puts the process into memory. It does not do anything after that.

2. If this was what happened, that crashing would cause a system-wide memory leak.

Question 22 (1 pt; mean 0.48) (see above)

If a thread has a memory leak,

Question 23 (1 pt; mean 0.65) (see above)

Which of the following is commonly used to create a simple blocking mutex?

Question 24 (1 pt; mean 0.85) (see above)

Which of the following does not block: that is, it never suspends a thread?

Question 25 (1 pt; mean 0.92) (see above)

The x86 instruction lock cmpxchg is a hardware implementation of which of the following?

Question 26 (2 pt; mean 1.07)

Which of the following ensure that my code has no deadlocks?

1. I realize my writeup is vague, although I think lecture was clearer: message passing reduces the chance of, not prohibits possibility of, deadlock. This option was given half weight compared to the others to compensate for this partial ambiguity.