# Lösungsvorschlag Software Architecture And Engineering FS13

Wechseln zu: Navigation, Suche

Sample (Student-) Solution to the exam of 2013, when the course was held by P.Müller and M.Vechev.

## Part 1

1. I agree
2. Extract Method
3. an event, a condition, and an action
4. bad practice because it may duplicate bugs, making it hard to fix all occurrences of a bug.
5. to reduce the complexity of combinatorial testing by testing each pair of parameter values.

## Part 2

### Task 1, Control Flow Graph

1. b1 = (names == null);
2. throw new NullPointer Exception("names must not be null");
3. File file = null; int i = 0;
4. b2 = (i < names.length);
5. String name = names[i];
6. b3 = (file == null);
7. file = new File(name);
8. file = new File(file, name);
9. i++;
10. return file;

Notes:

• From 1. to 2. if b1. 1. to 3. if not b1.
• 4. To 10. if not b2. 4. to 5. if b2.
• 6. to 7. if b3, 6. to 8. if not b3.
• 7. and 8. can be switched.

### Task 2

n Reach(n) ReachOut(n)
1 $\varnothing$ $\varnothing$
2 $\varnothing$ $\varnothing$
3 $\varnothing$ file3, i3
4 file3, file7, file8, i3, i9 file3, file7, file8, i3, i9
5 file3, file7, file8, i3, i9 file3, file7, file8, i3, i9
6 file3, file7, file8, i3, i9 file3, file7, file8, i3, i9
7 file3, file7, file8, i3, i9 file7, i3, i9
8 file3, file7, file8, i3, i9 file8, i3, i9
9 file7, file8, i3, i9 file7, file8, i9
10 file3, file7, file8, i3, i9 file3, file7, file8, i3, i9

### Task 3

(3,6), (7,6), (8,6), (3,8), (7,8), (8,8), (3,10), (7,10), (8,10)

### Task 4

(3,4), (9,4), (3,5), (9,5), (3,9), (9,9)

### Task 5

 Test input DU-Pais covered [] (3,10) ["one", "two", "three"] (3,6), (7,6), (7,8), (8,6), (8,8), (8,10) ["one"] (3,6), (7,10)

(3,8)

## Part 3

### 1. Decision Table

 social not social city not city high budget low budget hostel camping site hotel city not city hostel camping site

### 2.

S = Bool(Social), C = Bool(City), H = Bool(Budget high),

1. (S=1, C=1)
2. (S=1, C=0)
3. (S=0, C=1, H=1)
4. (S=0, C=1, H=0)
5. (S=0, C=0)

## Part 4

### Task 1

The Visitor Pattern is suitable for this library. The user would use it by implementing the Visitor interface the library provides. The library would store the analyzed program's structure internally and allow visitors to visit it.

### Task 3

This class should be an implementation of the AnalyzedProgramVisitor above

## Part 5

### 1. trace semantics

$c_{0}:=$
$c_{1}:=$
$c_{2}:=[x\rightarrow 2,y\rightarrow -3]$
$[[P]]=\{c_{0},c_{0}\times c_{1},c_{0}\times c_{1}\times c_{2}\}$


### 2. over-approximation

None of these above


### 3. under-approximation

$\{1,\{x\rightarrow 0,y\rightarrow 0\}\}$


## Part 6

### 1. complete lattice

yes


### 2. result

$a\sqcup b=d$
$a\sqcup d=d$
$c\sqcap d=a$
$e\sqcap f=f$


### 3. function

f


### 4. monotone

No, because $b\sqsubseteq d{\text{ , but }}g(b)\sqsubseteq g(d)$ doesn't hold.


## Part 7

### 1. Galois connection

$\alpha (a)=f$
$\alpha (b)=f$
$\alpha (c)=g$
$\alpha (d)=h$
$\alpha (e)=i$

$\gamma (f)=b$
$\gamma (g)=c$
$\gamma (h)=d$
$\gamma (i)=e$


### 2. monotone galois

Definition:
Let (A, ≤) and (B, ≤) be two partially ordered sets. A monotone Galois connection between these posets consists of two monotone functions: $\alpha ()$ : A → B and $\gamma ()$ : B → A, such that for all a in A and b in B, we have

                 $\alpha (a)$ ≤ b if and only if a ≤ $\gamma (b)$.


$\alpha ()$ unchanged

change $\gamma ()$ to :

$\gamma (g)=e$
$\gamma (i)=e$


still monotone but not galois connection because: $e\leq \gamma (g)=e$ but $\alpha (e)=i\nleq g$

Yes

### 4. Galois connections

a. Yes
b. $F^{\#}(c)=c$
c. No, because $\alpha (F(\gamma (c)))=d\not \sqsubseteq F^{\#}(c)=c$


## Part 8

### 1. complete lattice

yes


### 2. programm

$1:x\rightarrow \bot ,y\rightarrow \bot ,i\rightarrow [-\infty ,\infty ]$
$2:x\rightarrow [0,\infty ],y\rightarrow \bot ,i\rightarrow [-\infty ,\infty ]$
$3:x\rightarrow [0,\infty ],y\rightarrow [0,\infty ],i\rightarrow [-\infty ,\infty ]$
$4:x\rightarrow [0,\infty ],y\rightarrow [0,\infty ],i\rightarrow [0,\infty ]$
$5:x\rightarrow [0,\infty ],y\rightarrow [0,\infty ],i\rightarrow [-\infty ,\infty ]$
$6:x\rightarrow [0,\infty ],y\rightarrow [0,\infty ],i\rightarrow [-\infty ,\infty ]$
$7:x\rightarrow [0,\infty ],y\rightarrow [0,\infty ],i\rightarrow [-\infty ,0]$


### 3. concrete trace

$<1:[x\leftarrow 0,y\leftarrow ..,i\leftarrow ..]>\cdot <2:[x\leftarrow 0,y\leftarrow ..,i\leftarrow ..]>$ since this trace belongs to the concretization of the invariants at label 0 and 1 but is in contradiction to the concrete at label 2 where x is 1.

## Part 9

### 1. abstract interpretation

automated: Interate F to a fix point
manual: Define the domain (includes $F^{\#}$), define the semantic meaning of the abstract transformer


### 2. predicate abstraction Diese Aufgabe wurde noch von niemandem gelöst und wartet noch immer auf einen Musterlöser. Hast du dieses Fach bereits besucht? Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine plausible Lösung für diese Frage notierst!

### 3. SMT solver Diese Aufgabe wurde noch von niemandem gelöst und wartet noch immer auf einen Musterlöser. Hast du dieses Fach bereits besucht? Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine plausible Lösung für diese Frage notierst!

### 4. time complexity Diese Aufgabe wurde noch von niemandem gelöst und wartet noch immer auf einen Musterlöser. Hast du dieses Fach bereits besucht? Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine plausible Lösung für diese Frage notierst!

## Part 10

### 1.

$pct=(x_{0}=2*y_{0})\wedge (x_{0}>y_{0}-99)$


### 2.

We use symbolic execution which has support to store intervals in the symbolic store. When reaching a for loop, we do not split execution (as we would normally do) but increase the interval of the symbolic variables.

Something like this ;-)