CS 105 Final Examination Solutions --- Fall 1998

CS 105 Final Examination Solutions -- Fall 1998

The diagrams below are intended to represents possible layouts for the wiring of a local area network. The lines represent the cables between machines and the little black squares (bumps?) the machines themselves.
For each layout, indicate whether it would be a possible topology for a token ring based network, an Ethernet or both.
Name the three transmission media most commonly used when installing local area networks. List them in order of increasing potential data rate/bandwidth.
1. twisted pair (telephone wire)
2. coaxial cable
3. fiber optic cable
In order to deliver packets correctly, the software on each Internet router must have available routing tables providing which of the following:
1. complete routes to every machine in the Internet,
2. the IP address of the every other router in the Internet,
3. --> the first step in a route to every other sub-network of the Internet, <--
4. the ethernet addresses of all of the machines on the networks to which the router is directly attached, or
5. the IP address of a domain name server.
Indicate whether each of the following is true or false.
1. Internet routers sometimes deliberately discard packets rather than forwarding them to their destinations.
  True
2. In a public key cryptography system it is possible for many individuals who do not trust one another to use the same key to encrypt messages.
  True
3. In an Ethernet, after sensing a collision a station will attempt to transmit again as soon as it detects that the network is idle.
  False
4. The Vigenere cipher is an example of a public key cryptosystem.
  False
5. Packet switching is more like message switching than circuit switching.
  True
6. The timeouts used in a retransmission scheme must be carefully adjusted to avoid causing network congestion.
  True
7. Modern cryptographic techniques have eliminated the security flaws that allowed Morris' Internet worm to gain unauthorized access to thousands of computers on the Internet.
  False
8. Parity bits are useful because they can detect the most commonly occurring errors on networks -- errors that damage only a single bit.
  False

Each of the following segments of HTML contains a simple error or errors. Show how to correct the problem(s). You can either rewrite the code to show the changes or mark the corrections on the original.

<FORM ACTION="http://www.cs.williams.edu/cgi-bin/select-year">
Please indicate your year:
<UL>
<LI><INPUT TYPE=RADIO NAME=YEAR VALUE=senior > 99 </INPUT>
<LI><INPUT TYPE=RADIO NAME=YEAR VALUE=junior > 00 </INPUT>
<LI><INPUT TYPE=RADIO NAME=YEAR VALUE=sophomore > 01 </INPUT>
<LI><INPUT TYPE=RADIO NAME=YEAR VALUE=frosh > 02 </INPUT>
</LI> </UL> 
<INPUT TYPE=SUBMIT>
</FORM>

<TABLE>
<TR>
<TH>Season</TH><TH>Tourists</TH>
</TR>
<TR>
<TD><FONT COLOR=00FF00><EM>Fall </FONT></EM>  </EM></FONT> 
</TD> <TD> Peepers </TD>
</TR>
<TR>
<TD><FONT COLOR=0000FF><EM>Spring </FONT></EM>  </EM></FONT>  </TD> 
<TD> Prospectives </TD>
</TR>
<TR>
<TD><FONT COLOR=FF0000><EM>Summer </FONT></EM>  </EM></FONT>  </TD> 
<TD> Theater </TD>
</TR>
<TR>
<TD><FONT COLOR=FFFFFF><EM>Winter </FONT></EM>  </EM></FONT>  </TD> 
<TD> Skiers </TD>
</TR>
</TABLE>

Write the HTML required to produce a simple tabular form like that shown below. Feel free to use any URL you want as the ACTION attribute of the form.

<FORM ACTION=''http://www.cs.williams.edu/anything''>
<TABLE BORDER=2>
<TR>
	<TD>
     <TABLE BORDER=0>
        <TR>
	   <TD>
		<INPUT TYPE=Radio Name=title Value=MR> Mr. <br>
 		<INPUT TYPE=Radio Name=title Value=MRS> Mrs. <br>
		<INPUT TYPE=Radio Name=title Value=MS> Ms. <br>
         </TD>
	   <TD>Enter your Name: <br><INPUT TYPE=TEXTFIELD>
          </TD>
        </TR>
   </TABLE>
       </TD>
	<TD><INPUT TYPE=SUBMIT></TD>
</TR>
</TABLE>
</FORM>

In our discussion of threats to privacy on the Internet, I portrayed the Internet router as a significant threat to privacy. Because all packets traveling from one sub-network to another must go through a router, a router in the wrong hands could eavesdrop on many "conversations".
So that you don't get a bad impression of routers, I should have pointed out that routers can also play an important role in ensuring security and privacy for network users. The administrators of a router (e.g. the staff in Jesup) can configure a router to be rather picky about which messages it will forward. For example, a router might be told not to forward any message to or from a particular machine on a network that stores sensitive information (e.g. the campus router might be told not to forward messages to or from the machine holding student academic records) to protect that machines from unauthorized attempts to access the data it holds. When used in this way the router is called a packet filter or "Firewall."
While a router functioning as a firewall could look at any part of an IP packet passing through, to keep things simple most such routers limit the information they use to decide whether each packet gets routed in the normal manner or discarded as a "violation." In particular, it is typical to only look at standard fields from the headers of the packets processed including:
- IP source and destination addresses - packet length

- TCP source and destination port numbers - TCP sequence numbers

Assuming only these fields can be used to decide how to handle a packet, indicate whether it would be possible to enforce each of the following access restrictions using a firewall. In each case, the firewall should enforce no more than the given restriction. Otherwise, the problem would be trivial (you could enforce any restriction by discarding all packets).
If you think the restriction is enforceable, indicate which packet header fields the firewall would have to check. If not, BRIEFLY indicate why.
1. Prevent any machine on the Amherst network from communicating with any machine on the Williams network through the Internet.
  Yes. Firewall would just use examine the IP source address of each incoming packet.
2. Prevent a particular Williams student (Kate?) from sending email off campus.
  No. The informaton that identifies the student as the sender of the mail is part of the contents of some TCP message rather than one of the header entries. The IP address does not identify the student since the message could be sent from any machine on campus.
3. Prevent machines in public labs and student rooms from accessing an on-campus machine used to store academic records.
  No. Packets between two machines on the Williams network would not have to go through the Router/firewall.
4. Limit machines that are off campus from accessing some machine on the Williams campus (wso.williams.edu?) as anything but a web server (i.e. don't allow machines off campus to even try to log in to the machine using Telnet or send mail to the machine, etc.).
  Yes. The Firewall would check for packets addressed to the TCP port for a web server (port 80) and the IP address for WSO.WILLIAMS.EDU.
In class, I introduced public key cryptography as a solution to the key distribution problem inherent in secret key cryptography. A skeptical mind, however, might have observed that switching to a public key system doesn't really solve the key distribution problem. To address the threat that an eavesdropper might impersonate someone we wanted to communicate with privately, we had to depend on the additional assumption of the existence of "certifying authorities" who everybody "trusts." The question is, what does "trust" mean.
To clarify the issue of trust, I'd like you to indicate which of the following things we must "trust" the certifying authority to do if we want to be sure we can communicate privately with anyone who has registered with a certifying authority we "trust."
Recall that when an individual or organization registers with a certifying authority it provides the certifying authority with "personal information" establishing its identity and it public encryption key.
Answer "yes" or "no" to each question below. You may provide a brief explanation.
Must you trust the certifying authority to:
1. Ensure that it keeps the "personal information" provided by those who have registered private?
  No, in fact many people might want to see the identifying information to verify that the key they obtain for a third party from the C.A. is associated with the third party they have in mind.
2. Keep the keys provided by those who register private?
  No, the C.A. will only be given a registrant's public key. Anyone who wants to can know this key without threatening the privacy of messages since the registrant alone will know the "private" decryption key.
3. Keep its own encryption key private?
  No. It's encryption key is again a public key.
4. Remain available on the network at all time so that it can be contacted when sites wish to begin communicating?
  No. The signed messages returned to those who register is all that is needed to initiation communication. The C.A. does not have to re-verify these messages when communication is initiated.

A (hopefully correct) version of the "pong" applet you completed in the last laboratory exercise is shown below. The questions on the following page refer to this code.

import java.awt.*;
import javaTools.*;

public class Pong extends AppletTemplate {
  double x,y,xspeed,yspeed;
  int paddleX;

  public void begin() {
    x = 100;
    y = 5;
    xspeed =2.5; 
    yspeed =4;
    paddleX = 100;
  }

  public void mouseMove(int x, int y) {
       paddleX = x;
  }

  public void mouseDown() {
        y = 5;
        yspeed = 4;
  }

  public void animate() {
        pen.clearRect();
        x = x + xspeed;
        y = y + yspeed;

        if (x > 200 ) {   xspeed = - xspeed; 	}
        if ( x < 0) {     xspeed = - xspeed ;	}
	
        if (y < 0 ) {     yspeed = -yspeed;	}
        if (y > 195) {
                if (x > paddleX-10 && x < paddleX+10 ) {
                        yspeed = - yspeed;
                        yspeed = 1.05 * -yspeed; <
>                        xspeed = 1.05 * xspeed;  
                } else {
                        y = 250;
                        yspeed = 0;
                }
        }
        pen.fillOval(x,y,6,6);
        pen.frameRect(paddleX-10,195,20,5);
  }
}

How (if at all) would the behavior of the applet change if the line:
```
	if (y < 0 ) {	yspeed = -yspeed; }
```
were deleted from the animate method. Be brief but precise in your description.
The ball would pass through the "top" of the playing area rather than bouncing off of it as expected.
How (if at all) would the behavior of the applet change if the last line of the animate method were replaced by the line:
```
        pen.frameRect(x-10,195,20,5);
```
The paddle would move back and forth across the screen so that its center was always lined up with the left edge of the ball. The position of the mouse would no longer control the paddle at all.
Suppose that to make the pong game a bit harder you decided that instead of having the ball's speed remain constant it should increase a little bit each time it hit the paddle. Show on the copy of the applet found on the preceding page how you would modify the applet so that the ball sped up by 5% each time it hit the paddle.

1. Assume that the following table represents a data value encoded using a two dimensional parity code which has been damaged by a transmission error that altered one bit of the message. Determine which bit was damaged. (You may assume that the original message contained 16 bits and that the 9 bits in the last column and last row were added to ensure that each row and column had odd parity.)
  
  0 1 1 0 1
  
  0 1 0 1 1
  
  0 1 0 0 0
  
  1 1 1 0 0
  
  1 1 1 0 1
2. If a single parity bit is used, any two-bit error will be undetectable. With two dimensional parity bits as in part (a), all two bit error are detectable (although you can't tell exactly which bit is damaged). Using a two-dimensional parity code, what is the smallest number of bits that must be damaged to produce an error that the code can not detect. Show an example to justify your answer.
  Suppose we start with the corrected verion of the method from the first part and then change four bits arranged in a rectangle as shown below:
  
  0 1 1 0 1
  
  0 1 0 1 1
  
  0 1 0 0 0
  
  1 1 1 0 0
  
  0 1 1 0 1
  
  -->
  0 0 1 1 1
  
  0 1 0 1 1
  
  0 0 0 1 0
  
  1 1 1 0 0
  
  0 1 1 0 1
  
  All rows and columns in the resulting table contain and odd number of 1's. So, if a receiver of this set of bits checked the parity there would be no hint that the four bits changed were in error.
In one of the homework assignments, you saw that the efficiency of several local area networks (Ethernet and token ring) decrease as the transmission rate increases. For this question, I'd like you to "discover" a similar property of techniques used in wide area networks.
In yet another homework problem, you considered the possibility of using sequence numbers that are only one bit long. In that assignment, you showed that it was not safe to have two packets outstanding at the same time if such a small range of sequence numbers is used. It turns out that it is a safe to communicate using only one bit sequence numbers if you never send the next message until the previous message has been acknowledged. This technique is called the "stop and wait" protocol and has actually been employed in widely used network software (have you ever heard of a file transfer program called "Kermit"). The "wait" part of this protocol refers to the fact that a computer has to wait until one message is acknowledged before sending the next message. This waiting reduces efficiency.
So, assume that S is the size of the messages begin sent, R the transmission rate (in bits per second, so S/R is the time required to transmit a message), A is the size of an acknowledgement in bits, and finally that T is the time it takes a message or acknowledgement to travel from the sender to the destination (or back again). Using these symbols, write a formula for the maximum efficiency with which messages can be sent from the sender to the receiver. Recall that we defined the efficiency as the time required to actually send the bits of a message divided by the total time devoted to the transmission of the message. In this case the total time will be the time from the beginning of the transmission of one message to the beginning of the transmission of the next message.
In your work, assume that no messages or acknowledgements actually ever get lost.
Efficiency = (S/R)/( (S/R) + (A/R) + 2T)

- IP source and destination addresses	- packet length
- TCP source and destination port numbers	- TCP sequence numbers