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

Preview (16 of 137 Pages)

100%

Purchase to unlock

Loading page image...

Distributed Systems, Edition 5: Chapter 1 Solutions.fm1Distributed Systems: Concepts and DesignChapter 1Exercise Solutions1.1Give five types of hardware resource and five types of data or software resource that can usefullybe 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 thelocal user). Most other servers, such as file servers, do some computation for their clients, hence their cpuis a shared resource.memory:cache server (holds recently-accessed web pages in its RAM, for faster access by other localcomputers)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 thecontent of windows.printer:networked printers accept print jobs from many computers. managing them with a queuingsystem.network capacity:packet transmission enables many simultaneous communication channels (streams ofdata) 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, butsometimes generated on-the-fly).file:file servers enable multiple clients to share read-write files. Conflicting updates may result ininconsistent 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 bookingsystem, etc.database:databases are intended to record the definitive state of some related sets of data. They have beenshared ever since multi-user computers appeared. They include techniques to manage concurrent updates.newsgroup content:Thenetnewssystem makes read-only copies of the recently-posted news itemsavailable to clients throughout the Internet. A copy of newsgroup content is maintained at each netnewsserver that is an approximate replica of those at other servers. Each server makes its data available tomultiple clients.video/audio stream:Servers can store entire videos on disk and deliver them at playback speed to multipleclients simultaneously.exclusive lock:a system-level object provided by a lock server, enabling several clients to coordinate theiruse of a resource (such as printer that does not include a queuing scheme).

Loading page image...

Distributed Systems, Edition 5: Chapter 1 Solutions.fm21.2How might the clocks in two computers that are linked by a local network be synchronized withoutreference to an external time source? What factors limit the accuracy of the procedure you havedescribed? How could the clocks in a large number of computers connected by the Internet besynchronized? 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 timetto send a message and a reply between computer A and computer B is measuredby repeated tests; then computer A sends its clock settingTto computer B. B sets its clock toT+t/2. The settingcan be refined by repetition. The procedure is subject to inaccuracy because of contention for the use of thelocal network from other computers and delays in the processing the messages in the operating systems of Aand 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 itshould carry out Cristian’s protocol with all of them. The protocol can be initiated by each in turn. Additionalinaccuracies arise in the Internet because messages are delayed as they pass through switches in wider areanetworks. For a wide area network the accuracy is probably within 5-10 ms. These answers do not take intoaccount the need for fault-tolerance. See Chapter 10 for further details.1.3Consider the implementation strategies for massively multiplayer online games as discussed inSection 1.2.2. In particular, what advantages do you see in adopting a single server approach forrepresenting the state of the multiplayer game? What problems can you identify and how mightthey be resolved?1.3 Ans.The advantages of having a single server maintain a representation of the game are that: (1) there is a singlecopy and hence no need to maintain consistency of multiple copies; and (2) clients have a single place to goto 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 affectingthe performance and scalability of the approach. To handle failure, it would be necessary to introducereplication, which in turn would require a solution to maintaining consistency across replicas. There are anumber of solutions to improving performance and scalability including running the server on a clusterarchitecture as described in Section 1.2.2, or again using replication and load balancing within the distributedenvironment. Alternatively, a peer-to-peer solution can be adopted. These techniques are covered throughoutthe book.1.4A user arrives at a railway station that she has never visited before, carrying a PDA that is capableof wireless networking. Suggest how the user could be provided with information about the localservices and amenities at that station, without entering the station’s name or attributes. Whattechnical challenges must be overcome?1.4 Ans.The user must be able to acquire the address of locally relevant information as automatically as possible. Onemethod is for the local wireless network to provide the URL of web pages about the locality over a localwireless network.For this to work: (1) the user must run a program on her device that listens for these URLs, and which givesthe 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 thatcorresponds to the physical spread of the place itself.1.5Compare and contrast cloud computing with more traditional client-server computing? What isnovel about cloud computing as a concept?1.5 Ans.In this chapter, cloud computing is defined in terms of: (1) supporting Internet-based services (whetherapplication, storage or other computing-based services), where everything is a service; and (2) dispensing withlocal data storage or application software. (1) is completely consistent with client-server computing and indeed

Loading page image...

Distributed Systems, Edition 5: Chapter 1 Solutions.fm3client-server concepts support the implementation of cloud computing. (2) highlights one of the key elementsof cloud computing in moving to a world where you can dispense with local services. This level of ambitionmay or may not be there in client-server computing. As a final comment, cloud computing promotes a view ofcomputing as a utility and this is linked to often novel business models whereby services can be rented ratherthan being owned, leading to a more flexible and elastic approach to service provision and acquisition. This isa 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, butlargely a business innovation in terms of viewing computing services as a utility.1.6Use the World Wide Web as an example to illustrate the concept of resource sharing, client andserver. What are the advantages and disadvantages of HTML, URLs and HTTP as coretechnologies 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'scomputer. The Web server accesses local files containing the Web pages and then supplies them to clientbrowser processes.HTML is a relatively straightforward language to parse and render but it confuses presentation with theunderlying data that is being presented.URLs are efficient resource locators but they are not sufficiently rich as resource links. For example, they maypoint 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 manytypes of content transfer and other types of service. Its verbosity (HTML messages tend to contain manystrings) 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 inefficiencythat we have mentioned.1.7A server program written in one language (for example C++) provides the implementation of aBLOB 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 themare attached to an internet. Describe the problems due to each of the five aspects of heterogeneitythat need to be solved to make it possible for a client object to invoke a method on the serverobject.1.7 Ans.As the computers are attached to an internet, we can assume that Internet protocols deal with differences innetworks.But the computers may have different hardware - therefore we have to deal with differences ofrepresentation of data items in request and reply messages from clients to objects. A common standard will bedefined 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 operationsto send and receive messages or to express invocations. Thus at the Java/C++ level a common operation wouldbe 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 datastructures such as strings, arrays, records. A common standard will be defined for each type of data structurethat must be transmitted between the object and its clients and a way of translating between that data structureand each of the languages.We may have different implementors, e.g. one for C++ and the other for Java. They will need to agreeon the common standards mentioned above and to document them.

Loading page image...

Distributed Systems, Edition 5: Chapter 1 Solutions.fm41.8An open distributed system allows new resource sharing services such as the BLOB object inExercise 1.7 to be added and accessed by a variety of client programs. Discuss in the context ofthis 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 toExercise 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 BLOBobject was implemented. The implementors must conform to those standards. In addition, the interface to theBLOB object must be published so that when it is added to the system, both existing and new clients will beable to access it. The publication of the standards allows parts of the system to be implemented by differentvendors and to work together.1.9Suppose that the operations of the BLOB object are separated into two categories – publicoperations that are available to all users and protected operations that are available only to certainnamed users.State all of the problems involved in ensuring that only the named users can use aprotected operation. Supposing that access to a protected operation provides information thatshould 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. Theproblems are:•defining the identities of the users. Using these identities in the list of users who are allowed to accessthe 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 userpretending 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 interceptedby unauthorised users.1.10The INFO service manages a potentially very large set of resources, each of which can be accessedby users throughout the Internet by means of a key (a string name). Discuss an approach to thedesign of the names of the resources that achieves the minimum loss of performance as the numberof resources in the service increases. Suggest how the INFO service can be implemented so as toavoid 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 thesolution 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. namesstarting with A at server 1, with B at server 2 and so forth. There could be more than one level of partitioningas in DNS. To avoid performance bottlenecks the algorithm for looking up a name must be decentralised. Thatis, the same server must not be involved in looking up every name. (A centralised solution would use a singleroot server that holds a location database that maps parts of the information onto particular servers). Somereplication is required to avoid such centralisation. For example: i) the location database might be replicated

Loading page image...

Distributed Systems, Edition 5: Chapter 1 Solutions.fm5at multiple root servers or ii) the location database might be replicated in every server. In both cases, differentclients must access different servers (e.g. local ones or randomly).1.11List the three main software components that may fail when a client process invokes a method ina server object, giving an example of a failure in each case. To what extent are these failuresindependent of one another? Suggest how the components can be made to tolerate one another’sfailures.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 arriveThe 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 causea 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 messageafter it has sent an invocation request message. Instead of making the user wait forever for the reply, a clientprocess 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 beabsolutely immune to lost messages. But if a server stores information about its clients it might eventually failif clients crash without informing the server (so that it can remove redundant information). (See statelessservers 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 survivingprocesses.1.12A 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 theserver. 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 beprevented.1.12 Ans.For concurrent executions - more throughput in the server (particularly if the server has to access a disk oranother service)Against - problems of interference between concurrent operationsExample:Client A’s thread reads value of variable XClient B’s thread reads value of variable XClient A’s thread adds 1 to its value and stores the result in XClient B’s thread subtracts 1 from its value and stores the result in XResult: X := X-1; imagine that X is the balance of a bank account, and clients A and B are implementing creditand 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 usesynchronized operations such as credit and debit.

Loading page image...

Distributed Systems, Edition 5: Chapter 1 Solutions.fm61.13A service is implemented by several servers. Explain why resources might be transferred betweenthem. Would it be satisfactory for clients to multicast all requests to the group of servers as a wayof achieving mobility transparency for clients?1.13 Ans.Migration of resources (information objects) is performed: to reduce communication delays (place objects ina server that is on the same local network as their most frequent users); to balance the load of processing andor storage utilisation between different servers.If all servers receive all requests, the communication load on the network is much increased and servers mustdo unnecessary work filtering out requests for objects that they do not hold.1.14Resources in the World Wide Web and other services are named by URLs. What do the initialsURL denote? Give examples of three different sorts of web resources that can be named by URLs.1.14 Ans.URL - Uniform Resource Locator3 of the following - a file or a image, movies, sound, anything that can be rendered, a query to a database or toa search engine.1.15Give an example of an HTTP URL.List the three main components of an HTTP URL, stating how their boundaries are denoted andillustrating 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 ("HyperTextTransport 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 Webserverresearch/distrib/book.html.The hostnamewwwis location independent so we have location transparency in that the addressof a particular computer is not included. Therefore the organisation may move the Web service toanother computer.But if the responsibility for providing a WWW-based information service moves to anotherorganisation, the URL would need to be changed.

Loading page image...

Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm1Distributed Systems: Concepts and DesignChapter 10Exercise Solutions10.1Early file-sharing applications such as Napster were restricted in their scalability by the need tomaintain a central index of resources and the hosts that hold them. What other solutions to theindexing 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 mustinvoke 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 arepotentially 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 localizedinformation sharing may be more suitable. For example, each node contacts other nodes with GUIDs inthe same range as its own to discover the resources they have available or can access. This would offerquick response with a subset of the available resources and possibly more resources with a slowerresponse.10.2The problem of maintaining indexes of available resources is application-dependent. Consider thesuitability 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 byBitTorrent, supplemented by atrackerservice for each resource that holds up-to-date information aboutthe current locations of available replicas.b) Solution (ii) is suitable; the updates can be disseminated in a slow algorithm that provides eventualconsistency.c) This is difficult to achieve in a totally scalable manner. Some partitioning of the files as in Ivy andOceanstore is needed. Clients must hold the GUIDs or other reference to the group of hosts responsiblefor the portions of the store they are interested in.10.3What are the main guarantees that users expect conventional servers (e.g. web servers or fileservers) to offer?10.3 Ans.

Loading page image...

Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm2The main guarantees are:•to maintain a consistent state of the objects that they store;•to make their service continuously available.10.4The 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 abreach of trust or a criminal act? Would they be breaches of trust if they occurred on a personal computer thatwas 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 twoare 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 aPC.iii)The attacks described in Section 7.1.1 are always a breach of trust or a criminal attack for servers. Butfor a PC the perpetrator may be the owner who may attack a user who is sharing the resources of theircomputer with impunity.iv)Hard disk failures, network failures, program bugs. These are not normally due to breaches of trust orcriminal 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 mustbe designed to cope with the looser interpretation of trust for PCs.10.5Peer-to-peer systems typically depend onuntrustedandvolatilecomputer systems for most oftheir 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 Exercise10.4 by discussing the possible ways in which each of them is likely to differ according to thefollowing attributes of the computers used:i) ownershipii) geographic locationiii) network connectivityiv)country or legal jurisdictionWhat does this suggest about policies for the placement of data objects in a peer-to-peer storage service?10.5 Ans.ownershipThe owner of a computer is likely to act in a manner that maximizes his benefit, regardless ofthe fact that some of its resources are shared by others. The notion of trust is relative to ownership, so actionsof type (b) or even (c) may be classified as acceptable.geographic locationComputers are subject to events of type (a) according to their geographic location.network connectivityPortions of a network may become separated, making communication between themimpossible. This might enable the owners in a disconnected portion to act against the interest of the majority.country or jurisdictionThe affects the ‘freedom of speech’ issue since governments or courts maypersecute the owners of information or order the deletion of data. The latter can be addressed by ensuring thatthere are replicas in several countries/jurisdictions.

Loading page image...

Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm310.6Assess the availability and trustworthiness of the personal computers in your environment. Youshould 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 youhave 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.7Explain how the use of the secure hash of an object to identify and route messages to it ensuresthat it is tamper-proof. What properties are required of the hash function? How can integrity bemaintained 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 derivedfrom the secure hash.•More importantly, even if the routing mechanism and some peer nodes are compromised, a client canrequest the content of the object and check its validity by computing the secure hash and comparing itwith the GUID.•The secure hash must be a one-way function for which it is computationally infeasible to generate twoobjects that hash to the same result. Else an attacker could store one value and then replace it with theother at a later date.10.8It 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 anonymitymight be improved.10.8 Ans.The general argument is that although TCP/IP messages contain the IP addresses of the source and destinationnodes, when an application-level multi-hop routing overlay is used, only the previous and next node in theroute can be discovered when packets are intercepted or logged somewhere in the network. A GUID does notby itself provide any information about the location of the node that hosts it. But if an attacker can gainknowledge of the contents of some of the routing tables, this property is compromised. Furthermore, anattacker with eavesdropping access at several points in the network could send ‘probe’ messages to specificGUIDs and observe the resulting IP traffic. This is likely to reveal quite a lot of information about the locationof the GUID.So the propositions that clients and resource hosts can remain anonymous is only true for weak attackerswith limited access to the network.This resistance to attacks might be improved by generating several outgoing messages for each incomingrequest at an intermediate node, all but one of the messages would be treated as a ‘dummy’ message anddestroyed at the next node. This would incur a substantial additional cost in network traffic.10.9Routing algorithms choose a next hop according to an estimate of distance in some addressingspace. Pastry and Tapestry both use circular linear address spaces in which a function based on theapproximate numerical difference between GUIDs determines their separation.Kademliausesthe XOR of the GUIDs. How does this help in the maintenance of routing tables? Does the XORoperation provide appropriate properties for a distance metric?

Loading page image...

Distributed Systems, Edition 5: Chapter 10 Solutions (peer-peer).fm410.9 Ans.The Kademlia paper states that the symmetry of the XOR operation ensures a simple and efficient routingmechanism. It results in symmetric routing tables being which isn’t true for some other routing algorithms. (Itis for Pastry, but not for Chord). Symmetry means that nodes can learn new routing information from incomingmessages, since the routes they have taken are reversible. In Kademlia the XOR of the GUIDs for the sourceand destination nodes is treated as a numeric distance metric and this results in a sensibly-behaved distancemetric (see Kademlia paper Section 2.1).10.10When the Squirrel peer-to-peer web caching service was evaluated by simulation, 4.11 hops wererequired 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 supportsthe 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 ofnodes participating in the overlay. The Cambridge data was based on 105 nodes whereas the Redmond datainclided 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.11In unstructured peer-to-peer systems, significant improvements on search results can be providedby the adoption of particular search strategies. Compare and contrast expanded ring search andrandom 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 withincreasing time-to-live values until a particular item is found. The approach is therefore quite heavyweight interms of the message traffic generated but can be very effective if items are found locally, for example withpopular items which are likely to be heavily replicated. A random walk strategy is one where a walker is setout on a random path until an item is found. This can greatly decrease the number of messages generated butat the expense of significant increases in the average time to find an item. This can be reduced by havingmultiple walkers (changing the the granularity of coverage).In summary, expanded ring search can be used when minimizing delay is more important than thenumber of messages generated and can be very effective if items are likely to be local. Random walk strategiescan be used when the number of messages should be kept under control and this can be fine-tuned in multiplewalker variants.

Loading page image...

Distributed Systems, Edition 5: Chapter 11 solutions (security).fm1Distributed Systems: Concepts and DesignChapter 11 Exercise Solutions11.1Describe some of the physical security policies in your organization. Express them in terms thatcould 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.00to 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 timesand 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.2Describe some of the ways in which conventional email is vulnerable to eavesdropping,masquerading, tampering, replay, denial of service. Suggest methods by which email could beprotected 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 mailhost on a local network:WeaknessTypes of attackremedySender is unauthenticated.Masquerading, denial ofservice.End-to-end authentication with digital signatures(e.g. using PGP)Message contents notauthenticated.Tampering, masquerading. End-to-end authentication with digital signatures(e.g. using PGP).Message contents in theclear.Eavesdropping.End-to-end encryption (e.g. using PGP).Delivery and deletion fromPOP/IMAP server isauthenticated only by alogin with password.Masquerading.Kerberos or SSL authentication of clients.Sender’s clock is notguranteed.False dating of messages.Include time certificates from a trusted timeservice.

Loading page image...

Distributed Systems, Edition 5: Chapter 11 solutions (security).fm211.3Initial exchanges of public keys are vulnerable to the man-in-the-middle attack. Describe as manydefences 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 someother 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 characterstring that is derived from the key with a standard one-way function - that was delivered by a separatechannel (e.g. on a business card).11.4PGP is often used to secure email communication. Describe the steps that a pair of users using PGPmust take before they can exchange email messages with privacy and authnticity guarantees. Whatscope is there to make the preliminary negotiations invisible to the users? (The PGP negotiationis 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 secureemail communication. It provides digital signatures for the authentication of messages string encryption fortheir secrecy and integrity. The signatures are made using the SHA-1 algorithm to make a digest of the messageand 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 bythe 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 toencrypt messages. Users’ public/private keys should be changed from time-to-time. (No keys should be usedindefinitely in a secure system because of the danger thst they may be compromised through inadvertentdisclosure or as a result of an attack.) To achieve the rotation of public/private key pairs, PGP must generateand store multiple key pairs and give each pair a label or identifer.Key management is based on akey ringheld by each user and a collection of PGP key servers accessibleon the Internet that hold only the public keys of registered PGP users. The key ring is simply a small databaseholding keys in data structures that are secure. They are secured using secret key encryption with apass phrasethat 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 thepass phraseto decrypt the keyring entries. If users are equippedwith smart cards or other physical access keys, the pass phrase could be supplied from the card.11.5How could email be sent to a list of 100 recipients using PGP or a similar scheme? Suggest ascheme 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 keyntimes (once in the publickey of each user) with a scheme where the members of a group would share a single session key. Themanagement and renewal of the shared key can be more easily achieved if the mailing list members arerepresented as members of a multicast group (pp. 436et seq.).11.6The implementation of the TEA symmetric encryption algorithm given in Figure 11.8–11.10 is notportable between all machine architectures. Explain why. How could a message encrypted usingthe 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 thesame at the sender (encrypter) and the receiver (decrypter). To make it work for all architectures, we wouldneed to transmit messages in a network-standard byte order, and to re-order the bytes to suite the localarchitecture on receipt.

Loading page image...

Distributed Systems, Edition 5: Chapter 11 solutions (security).fm311.7Modify the TEA application program in Figure 11.9 to use cipher block chaining (CBC).11.7 Ans.Left for the reader.11.8Construct a stream cipher application based on the program in Figure 11.9.11.8 Ans.Left for the reader.11.9Estimate 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 attackprogram 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 yourcalculations to obtain the time for a 50,000 MIPS parallel processor (or an Internet consortiumwith 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) ofplain text with the corresponding encrypted text. A program can be constructed with an inner loop ofNinstructions, to generate all possible key values in the range 0 – (256- 1) and apply the an encryption algorithmto the plain text with each key value in turn. If it takesTencseconds to apply the encryption algorithm to an 8-byte plain text, then we have the following estimate of the average timetto crack a key of lengthLby bruteforce:t2L2-----N2000106×()⁄+Tenc()=secondsIf N= 10 (i.e. we require an inner loop of 10 instructions) andTenc= 8/(18.963 x 106) seconds for the DESalgorithm (i.e. the fastest time to encrypt 8 bytes given in Figure 7.13), we have:t255102000106⋅()⁄818.963106⋅()⁄+()1.78108×≈=secondsi.e. about 500 years. A 200,000 MIPs parallel processor is 100 times faster, so assuming an efficient parallelalgorithm, the cracking time would be ~5 years.For IDEA, the equation is:t2128102000106⋅()⁄818.963106⋅()⁄+()1.51032×≈=secondsor about 5 x 1024years!11.10In the Needham and Shroeder authentication protocol with secret keys, explain why the followingversion of message 5 is not secure:A→B:{NB}KAB11.10 Ans.The purpose of message 5 is for A to convince B thatKABis fresh. B will be convinced if it knows that A hasKAB(because it will know that A cannot be merely re-playing overheard messages). The suggested version ofmessage 5 is not secure because A would not need to knowKABin order to send it, it could be sent by copyingmessage 4.11.11Review the solutions proposed in the discussion of the 802.11 Wireless Equivalent Privacyprotocol design, outlining ways in which each solution could be implemented and discussing anyunresolved issues or drawbacks. (5 answers)11.11 Ans.i) Sharing a single key:

Loading page image...

Distributed Systems, Edition 5: Chapter 11 solutions (security).fm4Solution, 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 authoritysuch as the administrator of the network. As a simple (primitive) solution could get the certificate using aphysical channel (e.g. on a memory stick from the sys admin). But a more sophisticated scheme would havethe sys admin establish a database contianing a set of certificates for authorized users. The users wouldestablish their identities using public key certificates in order to utilize their authorization. Once theauthorization has occured, the protocol to establish a shared encryption key would proceed in a manner similarto (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 thatthe 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 explicittermination 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 keyswithout disruption of communication using a protocol similar to the TLSchange cipher specmechanism.Drawbacks: the TLS mechanism must be implemented everywhere. It may not be possible to perform a cipherchange without interruping a real-time datastream.11.11 Ans.iv) The RC4 stream cipher weaknessSolution: Provision for the negotiation of cipher specificationsthe main problem is the inflexibility of hardwiring the cipher spec into the protocol definition. Solution is toallow communication partners to negotiate a cipher algorithm as in TLS. This requires a handshake protocol,similar to thechange cipher specmechanism required in the previous answer.11.11 Ans.v) Users often didn’t deploy the protectionSolution: Better default settings and documentation.The issue here is the importance given to security by administrators and users. It’s worth noting that the failureto do so has resulted in several recorded incidents of loss of privacy and some decisions to suspend the use ofWiFi networks.

Loading page image...

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

Preview Mode

This document has 137 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools