Explain briefly mechanisms that software on a desktop computer can use to securely generate secret keys for use in cryptographic protocols. [5 marks] (b) Give two different ways of implementing residual information protection in an operating system and explain the threat addressed by each. [5 marks] (c) Consider the standard POSIX file-system access control mechanism: (i) Under which conditions can files and subdirectories be removed from a parent directory? [2 marks] (ii) Many Unix variants implement an extension known as the "sticky bit". What is its function? ) What problem do real-time scheduling algorithms try to solve? [2 marks] (b) Describe one static priority and one dynamic priority real-time scheduling algorithm. You should discuss the issue of admission control, and comment on the data structures that an implementation would need to maintain and on how these would be used to make scheduling decisions. [8 marks] (c) A designer of a real-time system wishes to have concurrently executing tasks share a data structure protected by a mutual exclusion lock. (i) What scheduling problem could arise here? [2 marks] (ii) How could this problem be overcome? [2 marks] (d) The designer also wishes the real-time system to use demand paged virtual memory for efficiency. What problems could arise here, and how could they be overcome? [6 marks] 6 Numerical Analysis I (a) For Single Precision in the IEEE binary floating-point standard (IEEE 754) the precision is defined as 24, and the exponent requires 8 bits of storage. With reference to IEEE Single Precision, explain the terms exponent, significand, precision, sign bit, normalised number, denormal number. [6 marks] (b) Explain the term hidden bit. What are the values of the hidden bit for normalised and denormal numbers? How is the exponent stored and why? How are the exponent, significand and sign bit arranged in memory? [4 marks] (c) Let x denote the floating-point representation of a number x. Define the terms absolute error (x) and relative error (x) in representing x. How are x and x related? Define machine epsilon (m). [3 marks] (d) Assume x = y = z = m. Using worst-case analysis, estimate xy, xy. Find an expression for w where w = z xy. [4 marks] (e) Working to 4 significant decimal digits only, compute w when x = 2.018, y = 2.008, z = 4.058. Given m ' 0.5 103 , how many significant decimal digits of w can be relied on? [3 marks]

(iii) On a POSIX system that lacks support for the "sticky bit", how could you achieve an equivalent effect? [2 marks] (d) VerySafe Ltd offer two vaults with electronic locks. They open only after the correct decimal code has been entered. The VS100 - a low-cost civilian model - expects a 6-digit code. After all six digits have been entered, it will either open or will signal that the code was wrong and ask for another try. The VS110 - a far more expensive government version - expects a 40-digit code. Users of a beta-test version of the VS110 complained about the difficulty of entering such a long code correctly. The manufacturer therefore made a last-minute modification. After every five digits, the VS110 now either confirms that the code has been entered correctly so far, or it asks for the previous five digits again. Compare the security of the VS100 and VS110

Let be a PCF type. (a) Consider the PCF terms head : (nat ) tail : (nat ) nat repeat : (nat ) nat given by the following definitions head = fn s : nat . s(0) tail = fn s : nat .fn n : nat. s(succ n) repeat = fix fn f : (nat ) nat .fn s : nat .fn n : nat. if (zero n) then (head s) else if (zero pred n) then (head s) else f (tail s)

pred(pred n) Show that [[fn s : nat . tail tail(repeat s) ]] = [[fn s : nat . repeat(tail s) ]] in the domain (N [[ ]]) (N [[ ]]) . [6 marks] (b) Define a closed PCF term shuffle : (nat ) (nat ) nat such that [[head]] [[shuffle]] s t = [[head s]] [[tail]] [[shuffle]] s t = [[shuffle]] t ([[tail]] s) for all s, t ( N [[ ]] ). Briefly justify your answer. (c) (i) Define the notion of least pre-fixed point fix (f) in a domain D of a continuous function f in the function domain (D D). [3 marks] (ii) Prove that [[repeat]] v [[fn s : nat . shuffle s s]] in the domain (N [[ ]]) (N [

Describe the general idea of how program verification may be mechanised using verification conditions. Discuss what can be done completely automatically and what requires manual assistance. [5 marks] Describe the difference between deep and shallow semantic embeddings of one language in another and compare and contrast the benefits of each. What is the point of embedding Floyd-Hoare logic in higher order logic? [5 marks] Discuss possible commercial uses of formal software verification. How would you justify its use? [5 marks] 3 Digital Communication II What information does a host require to transmit an IP datagram to a given destination IP address? [3 marks] Describe how the host determines this information. How does this change in the presence of subnets? [3 marks] Routing protocols can be classified as either link-state or vector distance. (a) Briefly describe the operation of each of these schemes. [4 marks] (b) In which case does the overall state converge more rapidly after a change? Justify your answer. [2 marks] (c) Which scheme is more scalable? Justify your answer. [2 marks] Sketch a design for a transport protocol providing reliable data transmission over IP multicast. What are the main issues here? Which changes within the network could lead to a more efficient implementation? [6 marks] 2 CST.2000.8.3 4 Comparative Architectures Outline the design of a simple dynamic branch prediction cache which would provide a high degree of accuracy for branches that exhibit a strong bias in one or other direction (for example, loop-closing branches). [5 marks] Give an example of a simple code sequence containing branches that would be mispredicted by your design, and describe how it would behave. [5 marks] By storing a record of a branch's recent behaviour it is possible to devise prediction caches which are able to predict accurately branches whose behaviour follows some short regular pattern. Revise your prediction cache design to make use of a four-bit "local history" for each entry. [5 marks] How would this predictor perform with a branch exhibiting the following repeating sequences? (T = taken, N = not-taken) (a) NTTNNTTNNTTN... (b) NTTNNTNTTNNT... (c) TNTTTTTNTTTT... [5 marks] 5 Business Studies What are the differences between profit and loss and cash flow statements? [5 marks] What are the differences between debt and equity finance? [5 marks] What is an option and how might it be valued? [5 marks] Comment on the current prices of high-tech stocks.

The environmental agency is setting up an SQL database to monitor long-term

trends in the climate. Data are collected from observatories of a number of difffferent

kinds.

Flood risk is of particular concern. Each water authority measures river levels and

rates of flow hourly at major points, and records reservoir levels daily.

In addition, the agency maintains weather stations both inland and at sea. These

record precipitation (rainfall etc.), temperature, sunshine, air pressure and wind.

Values of new precipitation, temperature, pressure, and wind speed and direction

are taken hourly; gusts of over 60 m.p.h. are noted whenever they occur.

Maximum and minimum temperature and pressure, the total number of hours of

sunshine and the total precipitation are recorded daily. Inland stations can be

grouped by water authority.