Skip to content
Textbook Guides

Solution Manual For Distributed Systems: Concepts And Design, 5th Edition

Solution Manual For Distributed Systems: Concepts And Design, 5th Edition is your go-to resource for solving complex textbook problems with clear solutions and explanations.

Preview 16 of 137 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Distributed Systems, Edition 5: Chapter 1 Solutions.fm 1 Distributed Systems: Concepts and Design Chapter 1 Exercise Solutions 1.1 Give five types of hardware resource and five types of data or software resource that can usefully be shared. Give examples of their sharing as it occurs in distributed systems. 1.1 Ans. Hardware: CPU: compute server (executes processor-intensive applications for clients), remote object server (executes methods on behalf of clients), worm program (shares cpu capacity of desktop machine with the local user). Most other servers, such as file servers, do some computation for their clients, hence their cpu is a shared resource. memory: cache server (holds recently-accessed web pages in its RAM, for faster access by other local computers) disk: file server, virtual disk server (see Chapter 8), video on demand server (see Chapter 15). screen: Network window systems, such as X-11, allow processes in remote computers to update the content of windows. printer: networked printers accept print jobs from many computers. managing them with a queuing system. network capacity: packet transmission enables many simultaneous communication channels (streams of data) to be transmitted on the same circuits. Data/software: web page: web servers enable multiple clients to share read-only page content (usually stored in a file, but sometimes generated on-the-fly). file: file servers enable multiple clients to share read-write files. Conflicting updates may result in inconsistent results. Most useful for files that change infrequently, such as software binaries. object: possibilities for software objects are limitless. E.g. shared whiteboard, shared diary, room booking system, etc. database: databases are intended to record the definitive state of some related sets of data. They have been shared ever since multi-user computers appeared. They include techniques to manage concurrent updates. newsgroup content: The netnews system makes read-only copies of the recently-posted news items available to clients throughout the Internet. A copy of newsgroup content is maintained at each netnews server that is an approximate replica of those at other servers. Each server makes its data available to multiple clients. video/audio stream: Servers can store entire videos on disk and deliver them at playback speed to multiple clients simultaneously. exclusive lock: a system-level object provided by a lock server, enabling several clients to coordinate their use of a resource (such as printer that does not include a queuing scheme).

  2. Page 2
  3. Page 3
    Read page 3 as text

    Distributed Systems, Edition 5: Chapter 1 Solutions.fm 2 1.2 How might the clocks in two computers that are linked by a local network be synchronized without reference to an external time source? What factors limit the accuracy of the procedure you have described? How could the clocks in a large number of computers connected by the Internet be synchronized? Discuss the accuracy of that procedure. 1.2 Ans. Several time synchronization protocols are described in Section 10.3. One of these is Cristian’s protocol. Briefly, the round trip time t to send a message and a reply between computer A and computer B is measured by repeated tests; then computer A sends its clock setting T to computer B. B sets its clock to T + t /2. The setting can be refined by repetition. The procedure is subject to inaccuracy because of contention for the use of the local network from other computers and delays in the processing the messages in the operating systems of A and B. For a local network, the accuracy is probably within 1 ms. For a large number of computers, one computer should be nominated to act as the time server and it should carry out Cristian’s protocol with all of them. The protocol can be initiated by each in turn. Additional inaccuracies arise in the Internet because messages are delayed as they pass through switches in wider area networks. For a wide area network the accuracy is probably within 5-10 ms. These answers do not take into account the need for fault-tolerance. See Chapter 10 for further details. 1.3 Consider the implementation strategies for massively multiplayer online games as discussed in Section 1.2.2. In particular, what advantages do you see in adopting a single server approach for representing the state of the multiplayer game? What problems can you identify and how might they be resolved? 1.3 Ans. The advantages of having a single server maintain a representation of the game are that: (1) there is a single copy and hence no need to maintain consistency of multiple copies; and (2) clients have a single place to go to discover this state. There may also be advantages to having a global view of the entire systems state. The potential problems are that this single server may fail and may also become a bottleneck affecting the performance and scalability of the approach. To handle failure, it would be necessary to introduce replication, which in turn would require a solution to maintaining consistency across replicas. There are a number of solutions to improving performance and scalability including running the server on a cluster architecture as described in Section 1.2.2, or again using replication and load balancing within the distributed environment. Alternatively, a peer-to-peer solution can be adopted. These techniques are covered throughout the book. 1.4 A user arrives at a railway station that she has never visited before, carrying a PDA that is capable of wireless networking. Suggest how the user could be provided with information about the local services and amenities at that station, without entering the station’s name or attributes. What technical challenges must be overcome? 1.4 Ans. The user must be able to acquire the address of locally relevant information as automatically as possible. One method is for the local wireless network to provide the URL of web pages about the locality over a local wireless network. For this to work: (1) the user must run a program on her device that listens for these URLs, and which gives the user sufficient control that she is not swamped by unwanted URLs of the places she passes through; and (2) the means of propagating the URL (e.g. infrared or an 802.11 wireless LAN) should have a reach that corresponds to the physical spread of the place itself. 1.5 Compare and contrast cloud computing with more traditional client-server computing? What is novel about cloud computing as a concept? 1.5 Ans. In this chapter, cloud computing is defined in terms of: (1) supporting Internet-based services (whether application, storage or other computing-based services), where everything is a service; and (2) dispensing with local data storage or application software. (1) is completely consistent with client-server computing and indeed

  4. Page 4
    Read page 4 as text

    Distributed Systems, Edition 5: Chapter 1 Solutions.fm 3 client-server concepts support the implementation of cloud computing. (2) highlights one of the key elements of cloud computing in moving to a world where you can dispense with local services. This level of ambition may or may not be there in client-server computing. As a final comment, cloud computing promotes a view of computing as a utility and this is linked to often novel business models whereby services can be rented rather than being owned, leading to a more flexible and elastic approach to service provision and acquisition. This is a key distinction in cloud computing and represents the key novelty in cloud computing. To summarise, cloud computing is partially a technical innovation in terms of the level of ambition, but largely a business innovation in terms of viewing computing services as a utility. 1.6 Use the World Wide Web as an example to illustrate the concept of resource sharing, client and server. What are the advantages and disadvantages of HTML, URLs and HTTP as core technologies for information browsing? Are any of these technologies suitable as a basis for client- server computing in general? 1.6 Ans. Web Pages are examples of resources that are shared. These resources are managed by Web servers. Client-server architecture. The Web Browser is a client program (e.g. Netscape) that runs on the user's computer. The Web server accesses local files containing the Web pages and then supplies them to client browser processes. HTML is a relatively straightforward language to parse and render but it confuses presentation with the underlying data that is being presented. URLs are efficient resource locators but they are not sufficiently rich as resource links. For example, they may point at a resource that has been relocated or destroyed; their granularity (a whole resource) is too coarse- grained for many purposes. HTTP is a simple protocol that can be implemented with a small footprint, and which can be put to use in many types of content transfer and other types of service. Its verbosity (HTML messages tend to contain many strings) makes it inefficient for passing small amounts of data. HTTP and URLs are acceptable as a basis for client-server computing except that (a) there is no strong type- checking (web services operate by-value type checking without compiler support), (b) there is the inefficiency that we have mentioned. 1.7 A server program written in one language (for example C++) provides the implementation of a BLOB object that is intended to be accessed by clients that may be written in a different language (for example Java). The client and server computers may have different hardware, but all of them are attached to an internet. Describe the problems due to each of the five aspects of heterogeneity that need to be solved to make it possible for a client object to invoke a method on the server object. 1.7 Ans. As the computers are attached to an internet, we can assume that Internet protocols deal with differences in networks. But the computers may have different hardware - therefore we have to deal with differences of representation of data items in request and reply messages from clients to objects. A common standard will be defined for each type of data item that must be transmitted between the object and its clients. The computers may run different operating systems, therefore we need to deal with different operations to send and receive messages or to express invocations. Thus at the Java/C++ level a common operation would be used which will be translated to the particular operation according to the operating system it runs on. We have two different programming languages C++ and Java, they use different representations for data structures such as strings, arrays, records. A common standard will be defined for each type of data structure that must be transmitted between the object and its clients and a way of translating between that data structure and each of the languages. We may have different implementors, e.g. one for C++ and the other for Java. They will need to agree on the common standards mentioned above and to document them.

  5. Page 5
    Read page 5 as text

    Distributed Systems, Edition 5: Chapter 1 Solutions.fm 4 1.8 An open distributed system allows new resource sharing services such as the BLOB object in Exercise 1.7 to be added and accessed by a variety of client programs. Discuss in the context of this example, to what extent the needs of openness differ from those of heterogeneity. 1.8 Ans. To add the BLOB object to an existing open distributed system, the standards mentioned in the answer to Exercise 1.7 must already have been agreed for the distributed system To list them again: • the distributed system uses a common set of communication protocols (probably Internet protocols). • it uses an defined standard for representing data items (to deal with heterogeneity of hardware). • It uses a common standard for message passing operations (or for invocations). • It uses a language independent standard for representing data structures. But for the open distributed system the standards must have been agreed and documented before the BLOB object was implemented. The implementors must conform to those standards. In addition, the interface to the BLOB object must be published so that when it is added to the system, both existing and new clients will be able to access it. The publication of the standards allows parts of the system to be implemented by different vendors and to work together. 1.9 Suppose that the operations of the BLOB object are separated into two categories – public operations that are available to all users and protected operations that are available only to certain named users. State all of the problems involved in ensuring that only the named users can use a protected operation. Supposing that access to a protected operation provides information that should not be revealed to all users, what further problems arise? 1.9 Ans. Each request to access a protected operation must include the identity of the user making the request. The problems are: • defining the identities of the users. Using these identities in the list of users who are allowed to access the protected operations at the implementation of the BLOB object. And in the request messages. • ensuring that the identity supplied comes from the user it purports to be and not some other user pretending to be that user. • preventing other users from replaying or tampering with the request messages of legitimate users. Further problems. • the information returned as the result of a protected operation must be hidden from unauthorised users. This means that the messages containing the information must be encrypted in case they are intercepted by unauthorised users. 1.10 The INFO service manages a potentially very large set of resources, each of which can be accessed by users throughout the Internet by means of a key (a string name). Discuss an approach to the design of the names of the resources that achieves the minimum loss of performance as the number of resources in the service increases. Suggest how the INFO service can be implemented so as to avoid performance bottlenecks when the number of users becomes very large. 1.10 Ans. Algorithms that use hierarchic structures scale better than those that use linear structures. Therefore the solution should suggest a hierarchic naming scheme. e.g. that each resource has an name of the form ’A.B.C’ etc. where the time taken is O(log n) where there are n resources in the system. To allow for large numbers of users, the resources are partitioned amongst several servers, e.g. names starting with A at server 1, with B at server 2 and so forth. There could be more than one level of partitioning as in DNS. To avoid performance bottlenecks the algorithm for looking up a name must be decentralised. That is, the same server must not be involved in looking up every name. (A centralised solution would use a single root server that holds a location database that maps parts of the information onto particular servers). Some replication is required to avoid such centralisation. For example: i) the location database might be replicated

  6. Page 6
    Read page 6 as text

    Distributed Systems, Edition 5: Chapter 1 Solutions.fm 5 at multiple root servers or ii) the location database might be replicated in every server. In both cases, different clients must access different servers (e.g. local ones or randomly). 1.11 List the three main software components that may fail when a client process invokes a method in a server object, giving an example of a failure in each case. To what extent are these failures independent of one another? Suggest how the components can be made to tolerate one another’s failures. 1.11 Ans. The three main software components that may fail are: • the client process e.g. it may crash • the server process e.g. the process may crash • the communication software e.g. a message may fail to arrive The failures are generally caused independently of one another. Examples of dependent failures: • if the loss of a message causes the client or server process to crash. (The crashing of a server would cause a client to perceive that a reply message is missing and might indirectly cause it to fail). • if clients crashing cause servers problems. • if the crash of a process causes a failures in the communication software. Both processes should be able to tolerate missing messages. The client must tolerate a missing reply message after it has sent an invocation request message. Instead of making the user wait forever for the reply, a client process could use a timeout and then tell the user it has not been able to contact the server. A simple server just waits for request messages, executes invocations and sends replies. It should be absolutely immune to lost messages. But if a server stores information about its clients it might eventually fail if clients crash without informing the server (so that it can remove redundant information). (See stateless servers in chapter 4/5/8). The communication software should be designed to tolerate crashes in the communicating processes. For example, the failure of one process should not cause problems in the communication between the surviving processes. 1.12 A server process maintains a shared information object such as the BLOB object of Exercise 1.7. Give arguments for and against allowing the client requests to be executed concurrently by the server. In the case that they are executed concurrently, give an example of possible ‘interference’ that can occur between the operations of different clients. Suggest how such interference may be prevented. 1.12 Ans. For concurrent executions - more throughput in the server (particularly if the server has to access a disk or another service) Against - problems of interference between concurrent operations Example: Client A’s thread reads value of variable X Client B’s thread reads value of variable X Client A’s thread adds 1 to its value and stores the result in X Client B’s thread subtracts 1 from its value and stores the result in X Result: X := X-1; imagine that X is the balance of a bank account, and clients A and B are implementing credit and debit transactions, and you can see immediately that the result is incorrect. To overcome interference use some form of concurrency control. For example, for a Java server use synchronized operations such as credit and debit.

  7. Page 7
    Read page 7 as text

    Distributed Systems, Edition 5: Chapter 1 Solutions.fm 6 1.13 A service is implemented by several servers. Explain why resources might be transferred between them. Would it be satisfactory for clients to multicast all requests to the group of servers as a way of achieving mobility transparency for clients? 1.13 Ans. Migration of resources (information objects) is performed: to reduce communication delays (place objects in a server that is on the same local network as their most frequent users); to balance the load of processing and or storage utilisation between different servers. If all servers receive all requests, the communication load on the network is much increased and servers must do unnecessary work filtering out requests for objects that they do not hold. 1.14 Resources in the World Wide Web and other services are named by URLs. What do the initials URL denote? Give examples of three different sorts of web resources that can be named by URLs. 1.14 Ans. URL - Uniform Resource Locator 3 of the following - a file or a image, movies, sound, anything that can be rendered, a query to a database or to a search engine. 1.15 Give an example of an HTTP URL. List the three main components of an HTTP URL, stating how their boundaries are denoted and illustrating each one from your example. To what extent is a URL location transparent? 1.15 Ans. http://www.dcs.qmw.ac.uk/research/distrib/index.html • The protocol to use. the part before the colon, in the example the protocol to use is http ("HyperText Transport Protocol"). • The part between // and / is the Domain name of the Web server host www.dcs.qmw.ac.uk. • The remainder refers to information on that host - named within the top level directory used by that Web server research/distrib/book.html. The hostname www is location independent so we have location transparency in that the address of a particular computer is not included. Therefore the organisation may move the Web service to another computer. But if the responsibility for providing a WWW-based information service moves to another organisation, the URL would need to be changed.

  8. Page 8
    Read page 8 as text

    Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm 1 Distributed Systems: Concepts and Design Chapter 10 Exercise Solutions 10.1 Early file-sharing applications such as Napster were restricted in their scalability by the need to maintain a central index of resources and the hosts that hold them. What other solutions to the indexing problem can you identify? 10.1 Ans. The choice is application-dependent: i) The web can be used, but this requires manual intervention to announce new resources and users must invoke a search engine to find the resources they want (maybe via a web service interface). ii) If the aim is to provide access to all resources for all users, some form of reliable replication is needed. Chapter 15 details several with differing costs and consistency models. Gossip and Bayou are potentially scalable to internet-wide. They offer availability guarantees, but only after ‘convergence’ which may be slow. iii)If guaranteed availability isn’t required (as in media file sharing) then some form of localized information sharing may be more suitable. For example, each node contacts other nodes with GUIDs in the same range as its own to discover the resources they have available or can access. This would offer quick response with a subset of the available resources and possibly more resources with a slower response. 10.2 The problem of maintaining indexes of available resources is application-dependent. Consider the suitability of each of your answers to Exercise 10.1 for (i) music and media file sharing, (ii) long-term storage of archived material such as journal or newspaper content, (iii) network storage of general-purpose read-write files. 10.2 Ans. a) Solution (i) is suitable for slowly - changing collections of resources such as media files. It is used by BitTorrent, supplemented by a tracker service for each resource that holds up-to-date information about the current locations of available replicas. b) Solution (ii) is suitable; the updates can be disseminated in a slow algorithm that provides eventual consistency. c) This is difficult to achieve in a totally scalable manner. Some partitioning of the files as in Ivy and Oceanstore is needed. Clients must hold the GUIDs or other reference to the group of hosts responsible for the portions of the store they are interested in. 10.3 What are the main guarantees that users expect conventional servers (e.g. web servers or file servers) to offer? 10.3 Ans.

  9. Page 9
    Read page 9 as text

    Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm 2 The main guarantees are: • to maintain a consistent state of the objects that they store; • to make their service continuously available. 10.4 The guarantees offered by conventional servers may be violated by: i) physical damage to the host; ii) Errors or inconsistencies by system adminstrators or their managers; iii)successful attacks on the security of the system software; iv)hardware or software errors. Give two examples of possible incidents for each type of violation. Which of them could be described as a breach of trust or a criminal act? Would they be breaches of trust if they occurred on a personal computer that was contributing some resources to a peer-to-peer service? Why is this relevant for peer-to-peer systems? 10.4 Ans. i) Power failure, earthquake, flood, act of war or sabotage, owner throws the computer away. The last two are breeches of trust for servers, but the owner of a PC is free to throw it away. ii) Accidental deletion of a file, permission failure, there are many possible errors in system administration. Maybe not a breach of trust, but repeated occurrences are a serious matter in a service, though not on a PC. iii)The attacks described in Section 7.1.1 are always a breach of trust or a criminal attack for servers. But for a PC the perpetrator may be the owner who may attack a user who is sharing the resources of their computer with impunity. iv)Hard disk failures, network failures, program bugs. These are not normally due to breaches of trust or criminal acts. Servers are configured to ‘fail over’ to use alternative hardware and backup copies of data. The the software they run is probably more carefully validated before it is put into use. The differences in what is ‘trusted behaviour’ for servers and PCs is relevant because peer-to-peer system must be designed to cope with the looser interpretation of trust for PCs. 10.5 Peer-to-peer systems typically depend on untrusted and volatile computer systems for most of their resources. Trust is a social phenomenon with technical consequences. Volatility (i.e. unpredicatable availability) also is often due to human actions. Elaborate your answers to Exercise 10.4 by discussing the possible ways in which each of them is likely to differ according to the following attributes of the computers used: i) ownership ii) geographic location iii) network connectivity iv)country or legal jurisdiction What does this suggest about policies for the placement of data objects in a peer-to-peer storage service? 10.5 Ans. ownership The owner of a computer is likely to act in a manner that maximizes his benefit, regardless of the fact that some of its resources are shared by others. The notion of trust is relative to ownership, so actions of type (b) or even (c) may be classified as acceptable. geographic location Computers are subject to events of type (a) according to their geographic location. network connectivity Portions of a network may become separated, making communication between them impossible. This might enable the owners in a disconnected portion to act against the interest of the majority. country or jurisdiction The affects the ‘freedom of speech’ issue since governments or courts may persecute the owners of information or order the deletion of data. The latter can be addressed by ensuring that there are replicas in several countries/jurisdictions.

  10. Page 10
    Read page 10 as text

    Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm 3 10.6 Assess the availability and trustworthiness of the personal computers in your environment. You should estimate: Uptime : hours per day when the computer is operating and connected to the Internet. Software consistency : is the software managed by a competent technician? Security : is the computer fully protected against tampering by its users or others? Based on your assessment, discuss the feasibility of running a data sharng service on the set of computers you have assessed and outline the problems that must be addressed in a peer-to-peer data sharing service. 10.6 Ans. Answer is dependent on your local system environment. 10.7 Explain how the use of the secure hash of an object to identify and route messages to it ensures that it is tamper-proof. What properties are required of the hash function? How can integrity be maintained even if a substantial proportion of peer nodes are subverted? 10.7 Ans. • If the routing mechanism is secure, then objects will only be contactable at an address that is derived from the secure hash. • More importantly, even if the routing mechanism and some peer nodes are compromised, a client can request the content of the object and check its validity by computing the secure hash and comparing it with the GUID. • The secure hash must be a one-way function for which it is computationally infeasible to generate two objects that hash to the same result. Else an attacker could store one value and then replace it with the other at a later date. 10.8 It is often argued that peer-to-peer systems can offer anonymity for (i) clients accessing resources (ii) the hosts providing access to resources. Discuss each of these propositions. Suggest a way in which the resistance to attacks on anonymity might be improved. 10.8 Ans. The general argument is that although TCP/IP messages contain the IP addresses of the source and destination nodes, when an application-level multi-hop routing overlay is used, only the previous and next node in the route can be discovered when packets are intercepted or logged somewhere in the network. A GUID does not by itself provide any information about the location of the node that hosts it. But if an attacker can gain knowledge of the contents of some of the routing tables, this property is compromised. Furthermore, an attacker with eavesdropping access at several points in the network could send ‘probe’ messages to specific GUIDs and observe the resulting IP traffic. This is likely to reveal quite a lot of information about the location of the GUID. So the propositions that clients and resource hosts can remain anonymous is only true for weak attackers with limited access to the network. This resistance to attacks might be improved by generating several outgoing messages for each incoming request at an intermediate node, all but one of the messages would be treated as a ‘dummy’ message and destroyed at the next node. This would incur a substantial additional cost in network traffic. 10.9 Routing algorithms choose a next hop according to an estimate of distance in some addressing space. Pastry and Tapestry both use circular linear address spaces in which a function based on the approximate numerical difference between GUIDs determines their separation. Kademlia uses the XOR of the GUIDs. How does this help in the maintenance of routing tables? Does the XOR operation provide appropriate properties for a distance metric?

  11. Page 11
    Read page 11 as text

    Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm 4 10.9 Ans. The Kademlia paper states that the symmetry of the XOR operation ensures a simple and efficient routing mechanism. It results in symmetric routing tables being which isn’t true for some other routing algorithms. (It is for Pastry, but not for Chord). Symmetry means that nodes can learn new routing information from incoming messages, since the routes they have taken are reversible. In Kademlia the XOR of the GUIDs for the source and destination nodes is treated as a numeric distance metric and this results in a sensibly-behaved distance metric (see Kademlia paper Section 2.1). 10.10 When the Squirrel peer-to-peer web caching service was evaluated by simulation, 4.11 hops were required on average to route a request for a cache entry when simulating the Redmond traffic, whereas only 1.8 were required for the Cambridge traffic. Explain this and show that it supports the theoretical performance claimed for Pastry. 10.10 Ans. The answer is simply that the number of routing hops required in Pastry is O(log N) where N is the number of nodes participating in the overlay. The Cambridge data was based on 105 nodes whereas the Redmond data inclided 36000 nodes. The simulated performance is almost exactly the same as the theoretical: ln(36000)/ ln(105) = 2.26; 4.11/1.8 = 2.28. 10.11 In unstructured peer-to-peer systems, significant improvements on search results can be provided by the adoption of particular search strategies. Compare and contrast expanded ring search and random walk strategies, highlighting when each approach is likely to be effective. 10.11 Ans. An expanded ring search is a variant of a flooding based strategy whereby flood messages are sent out with increasing time-to-live values until a particular item is found. The approach is therefore quite heavyweight in terms of the message traffic generated but can be very effective if items are found locally, for example with popular items which are likely to be heavily replicated. A random walk strategy is one where a walker is set out on a random path until an item is found. This can greatly decrease the number of messages generated but at the expense of significant increases in the average time to find an item. This can be reduced by having multiple walkers (changing the the granularity of coverage). In summary, expanded ring search can be used when minimizing delay is more important than the number of messages generated and can be very effective if items are likely to be local. Random walk strategies can be used when the number of messages should be kept under control and this can be fine-tuned in multiple walker variants.

  12. Page 12
    Read page 12 as text

    Distributed Systems, Edition 5: Chapter 11 solutions (security).fm 1 Distributed Systems: Concepts and Design Chapter 11 Exercise Solutions 11.1 Describe some of the physical security policies in your organization. Express them in terms that could be implemented in a computerized door locking system. 11.1 Ans. For QMUL Computer Science Department (as in 2000): • staff have access to all areas of the department except the offices of others, at all hours; • students of the department have access to teaching laboratories and classrooms at all times except 0.00 to 0.400 and to other areas of the department, except private offices, during office hours; • students of other departments taking courses in Computer Science have access to classrooms at all times and to teaching laboratories at designated times according tothe the courses taken; • visitors have access to the Departmental Office during office hours; • a master key holder has access to all offices. Note: – Access rights should be withdrawn when a user ceases to be a member of staff or a student. – Changes in policy should be immediately effective. 11.2 Describe some of the ways in which conventional email is vulnerable to eavesdropping, masquerading, tampering, replay, denial of service. Suggest methods by which email could be protected against each of these forms of attack. 11.2 Ans. Possible weaknesses for a typical mail system with SMTP delivery and client pickup from POP or IMAP mail host on a local network: Weakness Types of attack remedy Sender is unauthenticated. Masquerading, denial of service. End-to-end authentication with digital signatures (e.g. using PGP) Message contents not authenticated. Tampering, masquerading. End-to-end authentication with digital signatures (e.g. using PGP). Message contents in the clear. Eavesdropping. End-to-end encryption (e.g. using PGP). Delivery and deletion from POP/IMAP server is authenticated only by a login with password. Masquerading. Kerberos or SSL authentication of clients. Sender’s clock is not guranteed. False dating of messages. Include time certificates from a trusted time service.

  13. Page 13
    Read page 13 as text

    Distributed Systems, Edition 5: Chapter 11 solutions (security).fm 2 11.3 Initial exchanges of public keys are vulnerable to the man-in-the-middle attack. Describe as many defences against it as you can. 11.3 Ans. 1. Use a private channel for the delivery of initial keys, such as a CDROM delivered by hand or by some other rellable method. 2. Include the Domain Name in the certificate and deal only with the correct corresponding IP address. 3. If certificates are delivered through the network, validate them with a ‘key fingerprint’ – a character string that is derived from the key with a standard one-way function - that was delivered by a separate channel (e.g. on a business card). 11.4 PGP is often used to secure email communication. Describe the steps that a pair of users using PGP must take before they can exchange email messages with privacy and authnticity guarantees. What scope is there to make the preliminary negotiations invisible to the users? (The PGP negotiation is an instance of the hybrid scheme.) 11.4 Ans. PGP is based on a hybrid protocol like those described on pages 264 and 281. Its primary use is for secure email communication. It provides digital signatures for the authentication of messages string encryption for their secrecy and integrity. The signatures are made using the SHA-1 algorithm to make a digest of the message and RSA or DSS for signing with the sender’s private key. The message is (optionally) encrypted with 3DES or IDEA, using a one-time session key generated by the sender, which is encrypted using RSA with the recipient’s public key and sent with the message. PGP is required to generate public/private key pairs for each user and the one-time session keys used to encrypt messages. Users’ public/private keys should be changed from time-to-time. (No keys should be used indefinitely in a secure system because of the danger thst they may be compromised through inadvertent disclosure or as a result of an attack.) To achieve the rotation of public/private key pairs, PGP must generate and store multiple key pairs and give each pair a label or identifer. Key management is based on a key ring held by each user and a collection of PGP key servers accessible on the Internet that hold only the public keys of registered PGP users. The key ring is simply a small database holding keys in data structures that are secure. They are secured using secret key encryption with a pass phrase that the use must type in order to allow applications to access the keys in the keyring. If PGP is thoroughly integrated into an email or other application the necessary actions to generate keys, access the key ring and perform signing and encryption on email messages can all be triggered automatically. The only user action required is the input of the pass phrase to decrypt the keyring entries. If users are equipped with smart cards or other physical access keys, the pass phrase could be supplied from the card. 11.5 How could email be sent to a list of 100 recipients using PGP or a similar scheme? Suggest a scheme that is simpler and faster when the list is used frequently. 11.5 Ans. The idea of this exercise is to contrast the need for PGP to encrypt the session key n times (once in the public key of each user) with a scheme where the members of a group would share a single session key. The management and renewal of the shared key can be more easily achieved if the mailing list members are represented as members of a multicast group (pp. 436 et seq .). 11.6 The implementation of the TEA symmetric encryption algorithm given in Figure 11.8–11.10 is not portable between all machine architectures. Explain why. How could a message encrypted using the TEA implementation be transmitted to decrypt it correctly on all other architectures? 11.6 Ans. Byte ordering is an issue. The algorithm as presented assumes that the 4 bytes in a 32-bit word are ordered the same at the sender (encrypter) and the receiver (decrypter). To make it work for all architectures, we would need to transmit messages in a network-standard byte order, and to re-order the bytes to suite the local architecture on receipt.

  14. Page 14
    Read page 14 as text

    Distributed Systems, Edition 5: Chapter 11 solutions (security).fm 3 11.7 Modify the TEA application program in Figure 11.9 to use cipher block chaining (CBC). 11.7 Ans. Left for the reader. 11.8 Construct a stream cipher application based on the program in Figure 11.9. 11.8 Ans. Left for the reader. 11.9 Estimate the time required to crack a 56-bit DES key by a brute-force attack using a 500 MIPS (million instruction per second) workstation, assuming that the inner loop for a brute-force attack program involves around 10 instructions per key value, plus the time to encrypt an 8-byte plaintext (see Figure 11.13. Perform the same calculation for a 128-bit IDEA key. Extrapolate your calculations to obtain the time for a 50,000 MIPS parallel processor (or an Internet consortium with similar processing power). 11.9 Ans. Suppose we have a computer with a 64-bit, 2000 MIP cpu, and a short sample (8 bytes or one 64-bit word) of plain text with the corresponding encrypted text. A program can be constructed with an inner loop of N instructions, to generate all possible key values in the range 0 – (2 56 - 1) and apply the an encryption algorithm to the plain text with each key value in turn. If it takes T enc seconds to apply the encryption algorithm to an 8- byte plain text, then we have the following estimate of the average time t to crack a key of length L by brute force: t 2 L 2 ----- N 2000 10 6 × ( ) ⁄ + T enc ( ) = seconds If N= 10 (i.e. we require an inner loop of 10 instructions) and T enc = 8/(18.963 x 10 6 ) seconds for the DES algorithm (i.e. the fastest time to encrypt 8 bytes given in Figure 7.13), we have: t 2 55 10 2000 10 6 ⋅ ( ) ⁄ 8 18.963 10 6 ⋅ ( ) ⁄ + ( ) 1.78 10 8 × ≈ = seconds i.e. about 500 years. A 200,000 MIPs parallel processor is 100 times faster, so assuming an efficient parallel algorithm, the cracking time would be ~5 years. For IDEA, the equation is: t 2 128 10 2000 10 6 ⋅ ( ) ⁄ 8 18.963 10 6 ⋅ ( ) ⁄ + ( ) 1.5 10 32 × ≈ = seconds or about 5 x 10 24 years! 11.10 In the Needham and Shroeder authentication protocol with secret keys, explain why the following version of message 5 is not secure: A → B: {N B } K AB 11.10 Ans. The purpose of message 5 is for A to convince B that K AB is fresh. B will be convinced if it knows that A has K AB (because it will know that A cannot be merely re-playing overheard messages). The suggested version of message 5 is not secure because A would not need to know K AB in order to send it, it could be sent by copying message 4. 11.11 Review the solutions proposed in the discussion of the 802.11 Wireless Equivalent Privacy protocol design, outlining ways in which each solution could be implemented and discussing any unresolved issues or drawbacks. (5 answers) 11.11 Ans. i) Sharing a single key:

  15. Page 15
    Read page 15 as text

    Distributed Systems, Edition 5: Chapter 11 solutions (security).fm 4 Solution, use a public-key based protocol for negotiating individual keys. How would authorized users establish their credentials? They would need a certificate signed by an authority such as the administrator of the network. As a simple (primitive) solution could get the certificate using a physical channel (e.g. on a memory stick from the sys admin). But a more sophisticated scheme would have the sys admin establish a database contianing a set of certificates for authorized users. The users would establish their identities using public key certificates in order to utilize their authorization. Once the authorization has occured, the protocol to establish a shared encryption key would proceed in a manner similar to (or even using) SSL/TSL. 11.11 Ans. ii) Base stations are never authenticated: Solution, base stations should supply a certificate. The certificate could be supplied as part of the exchange that is described above. Care is needed to ensure that the public key in the base-station certificate is used to establish the shared key. 11.11 Ans. iii) Inappropriate use of a stream cipher: Solution: Negotiate a new key after a time less than the worst case for repetition. An explicit termination code would be needed, as is the case in TLS. The worst case for repetition is in the order of hours. A base station should initiate the negotiation of new keys without disruption of communication using a protocol similar to the TLS change cipher spec mechanism. Drawbacks: the TLS mechanism must be implemented everywhere. It may not be possible to perform a cipher change without interruping a real-time datastream. 11.11 Ans. iv) The RC4 stream cipher weakness Solution: Provision for the negotiation of cipher specifications the main problem is the inflexibility of hardwiring the cipher spec into the protocol definition. Solution is to allow communication partners to negotiate a cipher algorithm as in TLS. This requires a handshake protocol, similar to the change cipher spec mechanism required in the previous answer. 11.11 Ans. v) Users often didn’t deploy the protection Solution: Better default settings and documentation. The issue here is the importance given to security by administrators and users. It’s worth noting that the failure to do so has resulted in several recorded incidents of loss of privacy and some decisions to suspend the use of WiFi networks.

  16. Page 16
    Read page 16 as text

    Distributed Systems, Edition 5: Chapter 12 solutions(dist files).fm 1 Distributed Systems: Concepts and Design Chapter 12 Exercise Solutions 12.1 Why is there no open or close operation in the interface to the flat file service or the directory service. What are the differences between our directory service Lookup operation and the UNIX open? 12.1 Ans. Because both services are stateless. The interface to the flat file service is designed to make open unnecessary. The Lookup operation performs a single-level lookup, returning the UFID corresponding to a given simple name in a specified directory. To look up a pathname, a sequence of Lookups must be used. Unix open takes a pathname and returns a file descriptor for the named file or directory. 12.2 Outline methods by which a client module could emulate the UNIX file system interface using our model file service. 12.2 Ans. Left to the reader. 12.3 Write a procedure PathLookup(Pathname, Dir) → UFID that implements Lookup for UNIX-like pathnames based on our model directory service. 12.3 Ans. Left to the reader. 12.4 Why should UFIDs be unique across all possible file systems? How is uniqueness for UFIDs ensured? 12.4 Ans. Uniqueness is important because servers that may be attached to different networks may eventually be connected, e.g. by an internetwork, or because a file group is moved from one server to another. UFIDs can be made unique by including the address of the host that creates them and a logical clock that is increased whenever a UFID is created. Note that the host address is included only for uniqueness, not for addressing purposes (although it might subsequently be used as a hint to the location of a file). 12.5 To what extent does Sun NFS deviate from one-copy file update semantics? Construct a scenario in which two user-level processes sharing a file would operate correctly in a single UNIX host but would observe inconsistencies when running in different hosts. 12.5 Ans. After a write operation, the corresponding data cached in clients other than the one performing the write is invalid (since it does not reflect the current contents of the file on the NFS server), but the other clients will not discover the discrepancy and may use the stale data for a period of up to 3 seconds (the time for which cached blocks are assumed to be fresh). For directories, the corresponding period is 30 seconds, but the consequences are less serious because the only operations on directories are to insert and delete file names.

121 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.