Algorithmus

Um einen Algorithmus anzugeben, der das Problem eines sicheren Name-Stamp Protokolls $T=\{\alpha_i,\beta_j\}$ auf Grundlage des eingeführten NFA $A = (Z,\Sigma,\delta,S,E)$ löst konstruieren wir nun eine Menge von Zustandstupeln wie folgt:

$$C = \{(z_i,z_j) \in Z \times Z \;\vert\; \overline{x} = \lam... ...\wedge\; \hat{\delta}(\{z_i\},x) \cap \{z_j\} \neq \emptyset\}$$

d.h. die Menge aller Zustandstupel für die ein Wort bestehend aus Buchstaben entlang des Pfades vom ersten zum zweiten Zustand des Tupels das Protokoll zerstört. Nach obiger Definition läßt sich die Frage nach der Sicherheit eines Name-Stamp Protokolls jetzt wie folgt formulieren.

Definition 26 (Sicheres Name-Stamp Protokoll (3))
Sei $T=\{\alpha_i,\beta_j\}$ ein Name-Stamp Protokoll, $A = (Z,\Sigma,\delta,S,E)$ der zugehörige NFA und $C$ die wie oben hierzu konstruierte Menge. $T$ ist sicher gdw

$$(S \times E) \cap C = \emptyset$$

Der folgende Algorithmus konstruiert die Menge $C$ und bestimmt somit in ${\cal O}(n^3)$, ob ein gegebenes Name-Stamp Protokoll sicher ist. Die Eingabelänge $n$ ist hierbei für ein gegebenes Name-Stamp Protokoll wie oben angegeben definiert.

CheckSecurity2( $T=\{\alpha_i,\beta_j\}$, $A = (Z,\Sigma,\delta,S,E)$)
1	$C := \{(z_i,z_i) \;\vert\; z_i \in Z\}$
2	$Q := C$
3	while $Q \neq \emptyset$ do
4	$(z_i,z_j) :=$head$(Q)$
5	if $(z_j,z_k) \in C$ and $(z_i,z_k) \notin C$ then
6	$C:=C \cup \{z_i,z_k\}$
7	$Q:=Q \cup \{z_i,z_k\}$
8	end
9	if $(z_k,z_i) \in C$ and $(z_k,z_j) \notin C$ then
10	$C:=C \cup \{z_k,z_j\}$
11	$Q:=Q \cup \{z_k,z_j\}$
12	end
13	if $\sigma\tau = \lambda$ and $z_i \in \delta(z_k,\sigma)$ and $z_l \in \delta(z_j,\tau)$ and $(z_k,z_l) \notin C$ then
15	$C:=C \cup \{z_k,z_l\}$
16	$Q:=Q \cup \{z_k,z_l\}$
17	end
18	end
19	if $(S \times E) \cap C = \emptyset$return true else return false
20	end

Der Algorithmus terminiert, da die Menge der Zustandstupel endlich ist und jeder Zustandstupel nur einmal der Queue $Q$ hinzugefügt wird. Beweise zu Korrektheit und Komplexität des Algorithmus sind in [2] zu finden.