Define access control lists and capabilities, and discuss their relative strengths and weaknesses. [5 marks] Describe how the access control list mechanisms work in Unix.  You have been asked to build a funds transfer system in which a payment is authorised only once it has been approved by both a manager and an accountant at a bank branch. How would you implement this system using Unix security mechanisms as the foundation? [10 marks] 6 Data Structures and Algorithms Describe Larsen's method of dynamic hashing that enables a record to be located on a disk given its key using just one disk transfer and only a modest amount of information held in main memory. [10 marks] In Larsen's method each key has associated pseudo-random sequences of probe and signature values. Discuss what properties these sequences should have. Outline an algorithm that could be used to compute the n th probe-signature pair for a given key. You may assume that the key is a character string. [6 marks] Briefly discuss why Larsen's method is not used in most current filing systems.

 

A lander for the planet Mars has initial mass M0 = m(0) kilograms which includes F0 = f(0) kilograms of fuel. It is released from an orbiter at time zero at height H0 = h(0) with an initial downwards velocity of zero. It must touch down at less than 1 metre per second. Its downward force is Mg (where g is constant) and this is countered by a rocket motor that is pre-programmed to generate a time-varying upwards force of u(t). The motor burns fuel at a mass rate proportional to the force it develops. This is summarised in these equations: dm(t) dt = −αu(t) dv(t) dt = u(t) − gm(t) m(t) dh(t) dt = v(t) A discrete-time computer simulation of the landing uses time steps ∆t. Using a programming language of your choice or pseudo code: (i) Give a suitable state vector for the system. Include setup code that suitably initialises the state vector. [1 mark] (ii) Give state update assignments for one time step based on simple linear projections assuming a function u(t) has been provided. [2 marks] (iii) Give code for the various stopping conditions. These include a safe landing, a fatal crash or running out of fuel. [1 mark] (iv) Why does a simple linear projection lead to a velocity modelling error in every time step. What determines the error magnitude and does it compound over successive steps?

The difference between implementation-defined behaviour and unspecified behaviour in the C standard, and an example of each sort of behaviour. Also briefly discuss why these loosely specified behaviours exist in the C standard instead of being strictly defined. [5 marks] (d) The role of a debugger such as LLVM's lldb in locating bugs in C code, including the use of breakpoints and watchpoints in an interactive debugger and how symbol tables are useful. [5 marks] 3 Compiler Construction Consider the following context-free grammar of expressions E ::= n | (E, E) where n ranges over integers. (a) Present a right-most derivation of the expression ((21, 18), 17). [2 marks] (b) List the LR(0) items for this grammar. [2 marks] (c) Describe the states of the deterministic finite automata associated with an LR(0) parser for the grammar presented above. Explain your method of constructing these states. [4 marks] (d) Describe the calculation of the goto function associated with an LR(0) parser for the grammar above. How is the goto function used by the parser? [4 marks] (e) Carefully describe the LR(0) parsing associated with your derivation in (a). That is, show each transition of the parser and how it performs shift and reduce operations. [8 marks] 3 (TURN OVER) CST.2015.3.4 4 Compiler Construction (a) Consider a programming language with nested function declarations that allows only first-order functions. That is, functions are not treated as values and can neither be passed as arguments nor returned by functions. Lambda lifting and static links are two common methods of implementing such a language using a run-time stack. Describe these methods and discuss their advantages and disadvantages. [6 marks] (b) Now suppose we are dealing with a programming language that supports higher-order functions that can be passed as arguments and returned as results. Give an example, in ML-like pseudo-code, where the techniques that you have described in (a) can no longer be used. Justify your answer. [6 marks] (c) Carefully explain the techniques you might use to compile the example that you presented in (b). [8 marks] 4 CST.2015.3.5 5 Concepts in Programming Languages (a) Identify three programming or implementation concepts stemming from Algol or Fortran which are still mainstream ideas, noting whether they arose from Algol or Fortran. [3 marks] (b) Give two comparable now-mainstream ideas, but excluding ideas directly involving typing, which arose other than from Algol and Fortran. [2 marks] (c) At machine-code level, a structured value typically contains some form of tag indicating which of several variant forms the data may take (e.g. 'leaf' versus 'branch'); this determines how subsequent fields are to be interpreted (e.g. as pointers, strings or floating-point values). (i) Give code to show how type declarations in Java, ML and Pascal may be used to describe such structured values, following the above description as closely as possible. [5 marks] (ii) For one of your type declarations identify a source of type unsafety that can arise. [2 marks] (d) What is the principal difference between statically typed and dynamically typed languages? Identify one early and one more modern statically typed language. Identify one early and one more modern dynamically typed language. [3 marks] (e) What is the principal difference between type-safe and type-unsafe languages? Identify one type-safe language and one type-unsafe language, from any era. [2 mark

 

What function does this systolic array perform and what is its space and time
complexity for processing N items by first writing all N items and then reading
N items? [4 marks]
3 (TURN OVER)
CST.2015.5.4
2 Computer Design
(a) What is the von Neumann bottleneck and why can it limit performance on
today's RISC machines? [4 marks]
(b) What computer architecture techniques are used to mitigate the effects of the
von Neumann bottleneck on RISC machines as compared to early computers
like EDSAC? [4 marks]
(c) How do RISC machines enforce memory protection for applications with disjoint
data sets? [4 marks]
(d) What is segmented addressing (e.g. as used on x86 machines)? [4 marks]
(e) If non-volatile random access memory had similar performance and cost to
DRAM, how would this change the memory hierarchy? Justify your answer.
[4 marks]
4
CST.2015.5.5
3 Computer Design
(a) Consider a multicore processor running the MSI cache coherence protocol in
each core's private caches. The caches are connected to each other and memory
via a snoopy bus.
(i) What is a cache coherence protocol and in what systems is it needed?
[4 marks]
(ii) What events would lead a cache to issue a bus transaction if it holds a block
of data in state S? [4 marks]
(iii) When and why does data need to be flushed back to memory in this
protocol? [4 marks]
(b) (i) What are the semantics of load linked and store conditional instructions?
[4 marks]
(ii) Describe the synchronisation method that the following code performs by
adding comments to it.
membar
label1: ll r2, 0(r1)
sub r2, r2, #1
sc r2, 0(r1)
beqz r2, label1
label2: load r2, 0(r1)
bneq r2, label2
[4 marks]
5 (TURN OVER)
CST.2015.5.6
4 Computer Networking
The following equation provides a simple way to estimate the throughput of a TCP
connection, as a function of the loss probability p, the round-trip time RTT, and the
maximum segment size MSS.
TCP Throughput = r
3
2
MSS
RTT√p
(a) Alice wants to send a large amount of data to Bob over a network path with
RTT = 100 ms, p = 0.01, and MSS = 10, 000 bits. What is the expected
throughput in Mbit/s? [2 marks]
(b) With the aid of a clearly labelled diagram showing window-size versus time,
derive the above equation. [10 marks]
(c) Alice has two options to improve the throughput: halving either the RTT or the
loss probability p. If both cost the same, which is more cost effective and why?
[2 marks]
(d) Consider your derivation of the equation in part (b). State three assumptions
that are made and describe when these assumptions may not hold in reality.

(a) In the above network, use Dijkstra's shortest-path algorithm to compute the
shortest path from E to all network nodes. Show your working in a table: each
column indicating a destination node, each row indicating an iteration of the
algorithm. [10 marks]
(b) In 2008 an ISP was reported to have hijacked traffic for YouTube causing traffic
for YouTube to be diverted into the ISP's network.

Despite YouTube using only three addresses, each browser's YouTube URL
requests are ultimately routed to the closest of over a dozen data-centres Google
operates world-wide.
(i) Describe two concepts from the course that make this possible. [2 marks]
(ii) State the smallest advertised netblock that would identify all YouTube
addresses. [1 mark]
(iii) In an attempt to resolve the problem, YouTube advertised the netblock
208.65.153.0/24, but this was the same netblock as advertised by the rogue
ISP. Why would this not solve the problem? [2 marks]
(iv) YouTube advertised two smaller netblocks, each one half of 208.65.153.0/24.
Why should this now work? [2 marks]
(v) BGP networks may optionally filter net that in (b)(iii).
Estimate the size of the netblock filter. [1 mark]
(vi) Why does BGP implement such filtering? [2 marks]
7 (TURN OVER)
CST.2015.5.8
6 Computer Networking
(a) An older home-network router has an upload bandwidth of 1Mbit/s to the
Internet, and a 100kbyte first-in first-out (FIFO) buffer for packets awaiting
transmission. Packets have a maximum transmission unit (MTU) of 1500
bytes.
(i) If the buffer is completely full, how long does it take the router to transmit
all of the bytes in the buffer? [2 marks]
(ii) Suppose the router supports two FIFO queues, one high-priority for
interactive applications (like Voice over IP) and the other lower-priority for
all remaining traffic. If a VoIP packet arrives when the queue for interactive
applications is empty, what is the maximum time before the router starts
transmitting the VoIP packet? (Assume that the router does not preempt
any ongoing packet transmission.)

 

) indicate a typical range of values in a 1Gbit/s local area network with link-length less than 500m. State your assumptions throughout. [4 × 3 marks] (c) A lecturer remarks that "centralised multiplexing" offers potential gains in efficiency over non-centralised multiplexing. Give two reasons why this could be so. In each, state clearly what feature must be centralised to achieve these gains. [4 marks] 8 CST.2015.5.9 7 Concurrent and Distributed Systems (a) (i) Name the four necessary conditions for deadlock. [2 marks] (ii) Which of these conditions is frequently precluded in operating-system kernel designs in order to prevent deadlocks and why? [2 marks] (b) Deadlocks are not limited to locks; cycles of waiting on condition variables can also lead to the "deadly embrace". (i) Explain why it might be more difficult to debug deadlocks involving condition variables than those simply involving locks. [2 marks] (ii) Briefly describe a condition-variable API change that might allow this problem to be solved in some cases; explain why it cannot always help. [2 marks] (c) FreeBSD's WITNESS feature checks statically defined and dynamically discovered lock orders. Each time a lock is acquired, any previously undiscovered graph edges involving lock types currently held by the thread and the newly acquired lock type will be added to the graph. Cycle detection is performed, and debug information is printed if a previously unreported cycle is discovered. (i) Describe a common code structure in which programmers are likely to be able to define a static order between two lock types. [2 marks] (ii) Describe a common case in which programmers are likely to rely instead on dynamic discovery of an order between two lock types. [2 marks] (iii) Unlike the deadlock-detection algorithm presented in lecture, the WITNESS algorithm does not remove edges when locks are released. Explain why WITNESS's behaviour might be more useful in practice. [2 marks] (iv) WITNESS is subject to false positives: warnings can be emitted due to legitimate cycles even though, by design, the cycle could never trigger an actual deadlock. Describe a situation in which this might arise, and explain why deadlock could never occur. [3 marks] (v) WITNESS, as written, is intended to be used with mutexes and other lock types providing mutual exclusion. A developer might na¨ıvely extend WITNESS to support reader-writer locks (rwlock) by introducing graph edges for both read and write acquires as it does for mutex acquires. Explain why this might not always lead to the desired result. [3 marks] 9 (TURN OVER) CST.2015.5.10 8 Concurrent and Distributed Systems (a) (i) Define the term capability. [2 marks] (ii) What two fields must RBAC-based ACL entries always contain? [2 marks] (b) Network-Attached Secure Disks (NASD) utilise file managers and block servers. File-manager RPCs exchange an authorised user ID, password, and object ID for a keyed cryptographic capability granting block access: f(k, ObjID, rights). (i) Describe the consequences of a user learning the value of key k. [2 marks] (ii) Alice obtains a capability for object Oi . Bob then issues an RPC to the file manager revoking Alice's access to Oi . Describe what occurs when Alice performs her next block-server read on Oi . [2 marks] (iii) Explain why it might be desirable, from a security perspective, to add a timeout field t, protected by the keyed hash, to the capability. [2 marks] (iv) Developers extend NASD to support Quorum-replicated block servers. What new failure mode may arise during a Quorum block write, relative to unmodified NASD capabilities, in adding capability timeouts? [2 marks] (c) The Andrew File System (AFS) is authenticated and encrypted using Kerberos; ACLs expressing positive and negative rights for users and groups. Multiuser AFS clients (e.g., UNIX servers) build a secure RPC connection for each local user, authenticated with their Kerberos ticket, and issue RPCs (e.g., file read) on their behalf only via their own connection. If no suitable Kerberos ticket is available (e.g., the ticket has expired, the user has destroyed their ticket, or a job is running unattended), then an insecure connection is used instead. (i) The group system:anyuser holds the union of unauthenticated (anonymous) users and all authenticated users. Explain why an ACL granting read access to system:anyuser via a positive entry, but denying read access to user rnw via an overriding negative entry, might prove problematic. [2 marks] (ii) Describe the consequences to AFS authentication and authorisation of a malicious local user gaining root access on a multiuser client. [2 marks] (iii) An AFS client uses the unauthenticated Network Time Protocol (NTP) to synchronise its clock with the AFS server. Attacker Mallory is able to inspect, drop, and insert packets between the AFS client and server (e.g., by controlling a network switch). Describe an attack that allows Mallory to inject malicious content into the client's AFS cache, but that does not allow Mallory to write content directly to the AFS server.