Qualifying examination for Software Engineering and Methodology

Fall, 2004

 

Directions: Answer any six of the nine following questions. For all answers provide citations of relevant literature sufficient to identify the source.

 

  1. One useful property of model checking algorithms is that they often generate counterexamples, if a bug exists. For what fragment of Computational Tree Logic (CTL) can useful counterexamples be generated? For what fragment of CTL is it not possible to generate useful counterexamples? Explain and provide examples.

 

  1. An Òanti-dependence" exists between two statements Si and Sk if Si uses a variable that is then defined in Sk. For instance, in the example below, Si uses X and Sk defines X.  Thus, there is an anti-dependence between Si and Sk.

 

Si: É = X (use of X)

<----- point immediately following the use of X

É

Sk: X =  É (definition of X)

 

One way to determine these dependencies is to compute the sets of definitions that are "reachable" from the point P immediately following the use.

    1. Give a data-flow framework to compute sets of definitions that can be "reached" from the end of each basic block.

                                                     i.     Indicate if this problem is an any- or all-paths problem

                                                      ii.     Indicate if the problem is a forward or backward data-flow problem

                                                        iii.     Give the definitions of the GEN, KILL, IN, and OUT sets for the problem

                                                        iv.     Give the initial values of the sets

                                                      v.     Give the algorithm

    1. Given the reachable definitions, how would you compute the anti-dependencies?

 

  1. Design patterns are an informal way of expressing design knowledge in a way that facilitates reuse.
    1. Give an example of a design pattern and describe a situation in which it might be used.
    2. Discuss the difference between design patterns and frameworks.
    3. Refactoring means changing existing code, without modifying its behavior, with the goal of improving some nonfunctional quality (e.g., maintainability and understandability). In your opinion, how could refactoring and design patterns benefit from each other? Discuss and provide examples.
    4. IDEs are commonly used to develop software and provide increasingly sophisticated support for various development activities. Discuss one or more ways in which support for design patterns could be provided, in an automated or semi-automated fashion, through an IDE.

 

  1. Informal (natural language) specifications are frequently used to describe the requirements for a software system.  Such specifications suffer from the well-known problems of ambiguity and lack of precision. Various approaches have been suggested to deal with this problem by making use of a formal notation and a systematic process.  However, formal specification of programs provides precision at the cost of extra effort.
    1. Give a brief critique of a few formal and semi-formal approaches that you know, including a description of their strengths and weaknesses.
    2. Talk about the benefits and the cost of using formal specifications and discuss whether, in your opinion, the additional benefits are sufficient to justify the added cost.
    3. Can you think of any way to reduce the cost of using formal specifications while preserving the precision of the formal approach?
    4. What role do you think formal methods will play in the specification process in the future? To what extent do you think they are going to succeed (or fail)? Justify your answer.

 

  1. The field of software engineering has, over the years, developed several important design principles, such as structured programming, information hiding, and modular design.
    1. Select three or more design principles that you consider important and indicate the extent to which they have been taken into account in the design of modern Object-Oriented languages, such as C++ or Java. In particular, discuss how mechanisms such as polymorphism and exception handling facilitate (or complicate) the application of those principles.
    2. Can you think of any way in which these languages could be modified to better enforce the principles you selected? (For example, by adding, modifying, or eliminating some language constructs.)

 

  1. In your work, you address the problem of identifying and preventing Denial of Service (DoS) attacks.
    1. DoS attacks seem to be especially problematic in the case of portable devices, such as PDAs and cell phones. Discuss the differences, if any, between a traditional PC platform and a portable device with respect to vulnerability to this kind of attacks. Discuss also whether your technique could be applied to such devices and, if so, whether it would need to be modified or extended.
    2. In your approach, you combine static and dynamic analyses. Describe how your technique benefits form the combined use of static and dynamic analyses over the use of purely dynamic (or purely static) approaches.
    3. Provide some additional examples of dynamic analyses that can be improved through the use of static analysis.
    4. Can you also think of ways in which dynamic analysis could benefit static analysis? Discuss and provide examples.

 

  1. Today, it is very difficult to publish any kind of software engineering work without a suitable empirical evaluation.
    1. Do you agree with the argument that, in general, empirical evaluation is of fundamental importance in software engineering research? Motivate your answer.
    2. Can you provide examples of software engineering research that would not necessarily require empirical evaluation?
    3. There are different ways in which empirical evaluation can be performed. Discuss the difference between a case study and a controlled experiment, including pros and cons of both. Provide an example of a situation in which a case study would be a more suitable empirical evaluation than an experiment and vice-versa.

 

  1. In preparing for this exam, you have read many papers and book chapters. Choose the article or book chapter from the reading list at you found most interesting. Choose also the article or book chapter that you liked the least.
    1. For the paper that you found most interesting:

                                                     i.     Explain its significance and describe how it contributed to the software-engineering body of knowledge. In particular, mention other, subsequent work that has been influenced by this paper.

                                                      ii.     Could the same paper be written today? Justify your answer.

    1. For the paper that you liked the least, explain why it did not interest you (e.g., because you think it was not a significant contribution or because you disagree with its content).

 

  1. Code-coverage criteria, such as statement coverage and branch coverage, provide a quantitative way to assess the extent to which software system has been exercised. However, a higher coverage level does not necessarily mean a higher probability of detecting re faults.
    1. Provide an example that consists of a program P and two test suites for P, T1 and T2, such that T1 achieves higher statement coverage than T2, but it reveals fewer faults.
    2. Explain your example: why is the statement-coverage level not correlated with the fault detection level in this case? Is there another coverage criterion for which such correlation would exist for the example considered?
    3. What are the main theoretical and technical problems that must be solved to use coverage measures in practice?
    4. What is the difference between statement and branch coverage? Provide an example of a program P and test suite T for P, such that T achieves 100% statement coverage, but not 100% branch coverage.
    5. Are path coverage and exhaustive testing the same thing? Motivate your answer.