=Paper=
{{Paper
|id=None
|storemode=property
|title=Effiziente Abschätzung von Datenflussfehlern in strukturierten Geschäftsprozessen
|pdfUrl=https://ceur-ws.org/Vol-705/paper10.pdf
|volume=Vol-705
|dblpUrl=https://dblp.org/rec/conf/zeus/HeinzeAM11
}}
==Effiziente Abschätzung von Datenflussfehlern in strukturierten Geschäftsprozessen==
https://ceur-ws.org/Vol-705/paper10.pdf
Effiziente Abschätzung von Datenflussfehlern
in strukturierten Geschäftsprozessen
Thomas S. Heinze1 , Wolfram Amme1 , Simon Moser2
1
Friedrich-Schiller-Universität Jena
{T.Heinze,Wolfram.Amme}@uni-jena.de
2
IBM Entwicklungslabor Böblingen
smoser@de.ibm.com
Zusammenfassung. Neben dem Kontrollfluss von Geschäftsprozessen
kann auch der Datenfluss Ursache einer fehlerhaften Prozessausführung
sein, daher ist die Überprüfung eines Prozessmodells auf Datenflussfeh-
ler ebenfalls wesentlich. Wir schlagen in diesem Beitrag eine Methode
zur Abschätzung von Datenflussfehlern für strukturierte Geschäftspro-
zesse vor. Auf Grundlage der durch eine Datenflussanalyse abgeleiteten
Datenflussinformation geben wir Fehlermengen für mögliche und sichere
Datenflussfehler eines Geschäftsprozesses an. Der Vorteil dieses Ansatzes
besteht zum einen in der Effizienz der Analyse, andererseits aber auch
in der Identifikation und Lokalisation von Fehlern in einem Schritt. Als
Nachteil ergibt sich hingegen der Verlust absoluter Präzision.
1 Einführung
Neben der Verifikation von Geschäftsprozessen hinsichtlich Kontrollflussfehlern,
wie Verklemmungen oder fehlender Synchronisation, ist die Analyse der Verwen-
dung von Prozessdaten zur Gewährleistung einer fehlerfreien Prozessausführung
von Interesse [5]. Typische Fehler in diesem Zusammenhang sind beispielsweise
der lesende Zugriff auf noch uninitialisierte oder bereits gelöschte Daten, das
parallele Schreiben und Lesen von Daten oder das Überschreiben ungelesener
Daten. Enthält ein Prozessmodell auch Informationen zur Verwendung der Pro-
zessdaten, in Form der durch Prozessaktivitäten geschriebenen, gelesenen und
gelöschten Daten, kann eine Überprüfung auf derartige Datenflussfehler erfolgen.
Ein insbesonders für die Analyse des Datenflusses geeignetes Verfahren ist die
statische Datenflussanalyse [2, 3]. Im Gegensatz zu Verifikationstechniken die auf
einer vollständigen Modellprüfung beruhen erlaubt die Datenflussanalyse eine ef-
fiziente Ableitung von konservativer Datenflussinformation, verzichtet aber im
Gegenzug auf exakte Ergebnisse. Auf diese Weise kann der exponentielle Verifika-
tionsaufwand vermieden werden, der sich sonst bei einer präzisen Analyse ergibt.
Der hohe Aufwand ist dabei auf die zur Überprüfung des Datenflusses notwen-
dige Identifikation parallel ausführbarer Prozessaktivitäten zurückzuführen, die
schon für strukturierte Prozesse und unter Ausschluß von Schleifen exponentielle
Kosten verursachen kann [1]. Zusätzlich wird auch keine endliche Abstraktion
für die in einem Geschäftsprozess auftretenden Daten benötigt, da lediglich der
Datenfluss zwischen den Prozessaktivitäten berücksichtigt werden muss.
Fehlende Daten Zugriff auf ein uninitialisiertes oder gelöschtes Datum
Redundante Daten Schreiben eines Datums durch eine Prozessaktivität auf
das im weiteren Verlauf nicht lesend zugegriffen wird
Überschriebene Daten Überschreiben eines Datums durch eine Prozessaktivität
auf das noch nicht lesend zugegriffen wurde
Inkonsistente Daten Zugriff einer Prozessaktivität auf ein Datum und dazu
paralleles Schreiben oder Löschen desselben Datums
Nicht gelöschte Daten Fehlendes Löschen für ein geschriebenes Datum
Doppelt gelöschte Daten Zweimaliges Löschen ein und desselben Datums
Zu spät gelöschte Daten Letzter lesender Zugriff einer Prozessaktivität auf ein
Datum ohne sich unmittelbar anschließendes Löschen
Tabelle 1. Datenflussfehler (Anti-Muster) nach [5]
Im vorliegenden Beitrag zeigen wir, wie das Verfahren der Datenflussanaly-
se zur Überprüfung eines strukturierten Geschäftsprozesses auf Datenflussfehler
genutzt werden kann. In Abschnitt 2 wird dazu zunächst ein Überblick zu Daten-
flussfehlern und dem hier verwendeten Prozessmodell gegeben. Danach erfolgt in
Abschnitt 3 eine Beschreibung der Bestimmung von fehlenden, gelöschten sowie
definierenden Daten mit Hilfe einer statischen Datenflussanalyse. Auf Grundla-
ge der so für einen Prozess effizient ableitbaren Datenflussinformationen können
wir dann in Abschnitt 4 Fehlermengen einführen, die Abschätzungen zu den im
Prozess enthaltenen Datenflussfehlern in Form sicherer und möglicher Fehler
bilden. Schließlich wird der Beitrag in Abschnitt 5 kurz zusammengefasst.
2 Grundbegriffe
2.1 Datenflussfehler
In der Arbeit [5] wird eine Sammlung der in Geschäftsprozessen auftretenden
Datenflussfehler beschrieben. Dabei werden mehrere Anti-Muster vorgestellt, die
Schwachstellen hinsichtlich einer fehlerfreien Verwendung von Prozessdaten dar-
stellen. Wir beziehen uns im Folgenden auf diese, in Tabelle 1 angegebenen,
Anti-Muster, wenn wir von Datenflussfehlern sprechen. Im Gegensatz zu [5] wird
hier für die Anti-Muster Redundante Daten und Überschriebene Daten keine
Unterscheidung zwischen Fehlern, die immer auftreten, und solchen, die nur in
bestimmten Ausführungsszenarien auftreten, vorgenommen. Stattdessen werden
für alle Anti-Muster die Begriffe sicherer und möglicher Fehler definiert:
Definition 1 (Sicherer/Möglicher Datenflussfehler). Ein sicherer Fehler
tritt unabhängig vom zur Ausführungszeit tatsächlich gewählten Kontrollfluss ei-
nes Prozesses immer auf. Ein möglicher Fehler ist ein Kandidat für einen Fehler
der in mindestens einer Prozessausführung auftreten kann.
2.2 Prozessrepräsentation
Zur Durchführung unserer Methode benötigen wir ein Prozessmodell, dass die
Wiedergabe des Datenflusses innerhalb eines Prozesses gestattet. Zu diesem
Zweck werden erweiterte Workflow-Graphen genutzt, die gewöhnliche Workflow-
Graphen [4] mit Datenflussannotationen versehen. Auf der rechten Seite von
read(A0 )
C1 = write(C0 )
E 1 = write(E0 )
F 1 = write(F0 )
B1 = write(B 0 )
G1 = write(G0 )
read: A Fork V5 = π (V 0 , V 1 )
write: C, E, F V2 = write(V5 )
destroy: /
A 1= write(A0 )
D 1= write(D0 )
H 4= π (H 0 , H 2 ) V6 = π (V 2 , V 1 )
read: / cond(V6 )
H 1= write(H4 )
write: B, G, V
destroy: / Split
read: /
write: A, D, H cond(V) read(E 1)
destroy: /
G2 = write(G1 )
B2 = destroy(B 1 )
U 6= π (U 0 , U 1 )
U2 = write(U6 )
read: E read: /
write: G write: U
destroy: B destroy: / G 3= Φ (G2 , G1 )
Merge
B3 = Φ (B 2, B 1)
read(A1 ) U3 = Φ (U0 , U2 )
H 5= π (H 1 , H 2 )
read: A,
A H
read: B, G, U read(H5 ) read(B 3 )
write: U, V
destroy: D write: F, H U 5= π (U 0 , U 2 ) read(G3 )
destroy: / U1 = write(U5 ) U 7= π (U 3 , U 1 )
V4 = π (V 0 , V 2 ) read(U7 )
V1 = write(V4 ) F 2 = write(F 1)
D2 = destroy(D 1) H 6= π (H 0 , H 1 )
read: F, H, U H 2= write(H6 )
write: /
destroy: E, F, G Join
H 3= Φ (H1 , H2 )
read(F 2) V3 = Φ (V1 , V2 )
read(H3 ) U4 = Φ (U1 , U3 )
read(U4 )
E 2 = destroy(E1 )
F 3 = destroy(F 2 )
G4 = destroy(G3 )
Abb. 1. Beispielprozess in BPMN-Notation (l.) und als Workflow-Graph (r.)
Abbildung 1 ist der erweiterte Workflow-Graph für den aus [5] übernommenen
Beispielprozess dargestellt. Zum Vergleich bildet die linke Seite den Prozess auch
in BPMN-Notation ab. In der BPMN-Darstellung sind die Prozessknoten mit
Annotationen versehen, die in den Knoten gelesene, geschriebene oder gelöschte
Daten in Form von Variablen (A,B,...) bezeichnen. Ferner wurde die bedingte
Aufspaltung des Kontrollflusses mit der Verzweigungsbedingung versehen.
Im erweiterten Workflow-Graphen sind die Annotationen übernommen, nur
dass diese nun im Format der Concurrent Static Single Assignment Form (CSSA-
Form) [2] vorliegen. Zu diesem Zweck wurden die auf Daten operierenden Pro-
zessaktivitäten auf vier Instruktionstypen abgebildet:
– read(Vi ) liest das Datum in Variable Vi ,
– cond(Vi ) bestimmt den Wert einer Verzweigungsbedingung über Variable Vi ,
– Vi = write(Vj ) überschreibt die alte Definition des Datums in Variable Vj
mit einem neuen Datum und legt dieses in der Variablen Vi ab,
– Vi = destroy(Vj ) löscht das Datum in Variable Vj und setzt dadurch den
Wert der Variablen Vi auf undefiniert.
Charakteristische Eigenschaft der CSSA-Form ist, dass jede Variable statisch
einmal definiert ist, so dass für jede Variablendefinition durch die Instruktio-
nen write oder destroy ein eigener Name eingeführt, und Variablenzugriffe ent-
sprechend angepasst wurden (beispielsweise G1 , . . . , G4 für Variable G). Treffen
mehrere Definitionen einer Variablen auf verschiedenen Pfaden des Kontrollflus-
ses in einem Knoten zusammen, wurden spezielle Instruktionen mit wie folgt
definierten Φ-Funktionen eingefügt, um die Definitionen zusammenzufassen:
Definition 2 (Φ-Funktion). Eine Φ-Funktion für Variable V hat die Form
Φ(V1 , . . . , Vn ), wobei die Operanden Vi den im Knoten der Funktion zusam-
menfließenden Definitionen von V entsprechen. Der Wert der Funktion ist der
Operand Vi , der die zur Prozesslaufzeit tatsächlich, beziehungsweise als letztes,
ausgeführte Instruktion mit einer Definition der Variablen V repräsentiert.
Neben den Instruktionen mit Φ-Funktionen enthält die CSSA-Form weitere
spezielle Instruktionen mit π-Funktionen, um Schreib-/Lese-Konflikte zwischen
parallelen Prozessaktivitäten modellieren zu können:
Definition 3 (π-Funktion). Eine π-Funktion für Variable V hat die Form
π(V1 , . . . , Vn ), wobei die Operanden Vi den im Knoten der Funktion konkurrie-
renden Definitionen von V entsprechen. Der Wert der Funktion ist der Operand
Vi , der die zur Prozesslaufzeit letzte Definition von V repräsentiert.
3 Datenflussinformation
Auf Grundlage der Repräsentation eines strukturierten Geschäftsprozesses durch
erweiterte Workflow-Graphen können dann Informationen zum Datenfluss abge-
leitet werden. Für die Bestimmung der sicheren und möglichen Fehler zu den in
Tabelle 1 aufgeführten Fehlerarten werden Datenflussinformationen über die feh-
lenden, gelöschten und definierenden Daten des untersuchten Prozesses benötigt.
Als fehlende Daten werden Variablen bezeichnet, die uninitialisiert sind oder
gelöscht wurden. Dabei kann unterschieden werden, ob eine Variable für min-
destens ein Ausführungsszenario ein fehlendes Datum beschreibt, oder für alle
möglichen Prozessausführungen. In unserem Beispiel aus Abbildung 1 entspricht
die Variable A0 immer einem fehlenden Datum, die Variable B3 hingegen nur
dann, falls die Instruktion B2 = destroy(B1 ) ausgeführt wurde. Zur Darstellung
der Datenflussinformation werden Wahrheitswerte genutzt, die angeben ob ei-
ne Variable ein fehlendes Datum beschreibt. Bedingt durch die Eigenschaft der
CSSA-Form dass jede Variable statisch nur einmal definiert ist, können diese
Werte den die Variablen definierenden Instruktionen zugewiesen werden:
Definition 4 (Fehlende Daten). Für Instruktion s enthält M ISS M U ST (s)
einen Wahrheitswert, der anzeigt ob die durch s definierte Variable auf allen
Kontrollflusspfaden uninitialisiert/gelöscht ist und M ISS M AY (s) einen Wert,
ob die Variable auf mindestens einem Pfad uninitialisiert/gelöscht ist. Ist die
Instruktion s nicht vorhanden, gilt M ISS M U ST (s) = M ISS M AY (s) = true.
Analog ergibt sich die Datenflussinformation zu gelöschten Daten, die angibt
ob eine Variable im Prozess bereits gelöscht wurde:
Definition 5 (Gelöschte Daten). Für Instruktion s enthält DELM U ST (s)
einen Wahrheitswert, der anzeigt ob die durch s definierte Variable auf allen
Kontrollflusspfaden gelöscht wurde und DELM AY (s) einen Wahrheitswert, der
anzeigt ob diese Variable auf mindestens einem Pfad gelöscht wurde. Ist die
Instruktion s nicht vorhanden, gilt DELM U ST (s) = DELM AY (s) = f alse.
Die Datenflussinformation zu definierenden Daten entspricht hingegen der
Menge von Daten, in Form von durch write-Instruktionen definierten Variablen,
die den Wert einer Variablen in mindestens einer Prozessausführung festlegen
(beispielsweise {H1 , H2 } für Variable H3 in Abbildung 1), oder in allen:
Definition 6 (Definierende Daten). Für Instruktion s enthält die Menge
DAT AM U ST (s) alle Daten, welche den Wert der durch s definierten Variablen
auf allen Kontrollflusspfaden festlegen und die Menge DAT AM AY (s) alle Daten,
welche den Wert dieser Variablen auf mindestens einem Pfad festlegen. Ist die
Instruktion s nicht vorhanden, gilt DAT AM U ST (s) = DAT AM AY (s) = ∅.
Um die so definierten Datenflussinformationen für einen Geschäftsprozess ex-
akt bestimmen zu können, ist eine Analyse der parallel ausführbaren Prozessak-
tivitäten notwendig. Grundsätzlich ist eine solche Analyse Co-NP-schwer [1]. Da-
her verzichten wir auf die exakte Bestimmung und ermitteln stattdessen konser-
vative Abschätzungen. Zu diesem Zweck wird das Verfahren der statischen Da-
tenflussanalyse angewendet. Dieses erlaubt für die Charakterisierung eines Da-
tenflussproblems durch ein System rekursiver Gleichungen eine Fixpunktlösung
zu berechnen, die eine Abschätzung zur gesuchten Information bildet. Das Glei-
chungssystem zu den definierenden Daten ergibt sich beispielsweise wie folgt:
DAT AM U ST (s) = i∈{1,...,n} DAT AM U ST (def (Vi )) für s : V = Φ(V1 , . . . , Vn )
T
DAT AM U ST (s) = i∈{1,...,n} DAT AM U ST (def (Vi )) für s : V = π(V1 , . . . , Vn )
T
DAT AM AY (s) = i∈{1,...,n} DAT AM AY (def (Vi )) für s : V = Φ(V1 , . . . , Vn )
S
DAT AM AY (s) = i∈{1,...,n} DAT AM AY (def (Vi )) für s : V = π(V1 , . . . , Vn )
S
DAT AM U ST (s) = DAT AM AY (s) = {Vi } für s : Vi = write(Vj )
DAT AM U ST (s) = DAT AM AY (s) = ∅ sonst
Wie zu erkennen, werden darin jeder Instruktion s eines Prozesses Gleichun-
gen DAT AM U ST (s) und DAT AM AY (s) zugeordnet. Die Datenflussinformation
für eine write-Instruktion s bildet gerade die Menge, die als einziges Element
die durch s definierte Variable enthält. Für eine Instruktion mit Φ- oder π-
Funktion ergeben sich die Mengen DAT AM U ST und DAT AM AY als Schnitt
beziehungsweise Vereinigung der Datenflussinformation zu den die Operanden
definierenden Instruktionen (Instruktion def (Vi ) für Operand Vi ). Da das Glei-
chungssystem über endlichen Mengen und monotonen Funktionen definiert ist,
ist dessen Konvergenz sichergestellt. Für die Fixpunktbestimmung kann dann
ein Algorithmus zur Datenflussanalyse auf CSSA-Form genutzt werden [2, 3],
der diesen in höchstens quadratischer Zeit bezüglich der Anzahl von Prozess-
instruktionen berechnet. Aufgrund des beschränkten Platzes wird hier auf die
Angabe der Fixpunktgleichungen zu fehlenden und gelöschten Daten verzichtet.
Fehlerart Fehlermenge
Fehlende Daten { s | ( s : Vi = destroy(Vj ) ∨ s : read(Vj )
(sichere Fehler) ∨ s : cond(Vj ) ) ∧ M ISS M U ST (def (Vj )) = true }
Fehlende Daten { s | ( s : Vi = destroy(Vj ) ∨ s : read(Vj )
(mögliche Fehler) ∨ s : cond(Vj ) ) ∧ M ISS M AY (def (Vj )) = true }
Redundante oder { s | s : Vi S
= write(Vj )
überschriebene Daten ∧ Vi ∈ / ( s0 : read(Vk ) DAT AM AY (def (Vk ))
∪ s0 : cond(Vk ) DAT AM AY (def (Vk )) ) }
S
(sichere Fehler)
Redundante oder { s | s : Vi S
= write(Vj )
überschriebene Daten ∧ Vi ∈ /( s0 : read(Vk ) DAT AM U ST (def (Vk ))
s 0 postdominiert s
DAT AM U ST (def (Vk )) ) }
S
(mögliche Fehler) ∪ s0 : cond(Vk )
s0 postdominiert s
Inkonsistente Daten { s | ( s : Vi = destroy(Vj ) ∨ s : read(Vj )
(mögliche Fehler) ∨ s : cond(Vj ) ∨ s : Vi = write(Vj ) )
∧ Vj ist def iniert durch π−Funktion mit mehr
als einem Operanden }
Nicht gelöschte Daten { s | s : Vi S= write(Vj )
(sichere Fehler) ∧ Vi ∈ / ( s0 : Vl =destroy(Vk ) DAT AM AY (def (Vk ))
∪ s0 : Vl =write(Vk ) DAT AM AY (def (Vk )) ) }
S
Nicht gelöschte Daten { s | s : Vi S= write(Vj )
(mögliche Fehler) ∧ Vi ∈ / ( s0 : Vl =destroy(Vk ) DAT AM AY (def (Vk ))
s0 postdominiert s
S M AY
∪ s0 : Vl =write(Vk ) DAT A (def (Vk )) ) }
s0 postdominiert s
Doppelt gelöschte Daten { s | s : Vi = destroy(Vj )
(sichere Fehler) ∧ DELM U ST (def (Vj )) = true }
Doppelt gelöschte Daten { s | s : Vi = destroy(Vj )
(mögliche Fehler) ∧ DELM AY (def (Vj )) = true }
Zu spät gelöschte Daten { s | ( s : read(Vi ) ∨ s : cond(Vi ) )
(mögliche Fehler) ∧ @ s0 : V Sj = destroy(Vi ) in Basisblock von s
∧ Vi ∈ / ( s00 : read(Vk ) ∧ s00 6=s DAT AM U ST (def (Vk ))
s00 postdominiert s
S M U ST
∪ s00 : cond(Vk ) ∧ s00 6=s DAT A (def (Vk )) ) }
s00 postdominiert s
Tabelle 2. Fehlermengen (s, s0 , s00 bezeichnen Instruktionen des Prozesses)
4 Abschätzung sicherer und möglicher Fehler
Nachdem Abschätzungen für die fehlenden, gelöschten und definierenden Daten
für einen Prozess bestimmt wurden, können dessen sichere und mögliche Daten-
flussfehler abgeleitet werden. Zu diesem Zweck definieren wir für jeden der in
Tabelle 1 aufgeführten Fehler zugehörige Fehlermengen (vergleiche Definition 1):
Die Menge sicherer Fehler enthält Instruktionen, die den Fehler sicher und in
allen Prozessausführungen aufweisen, ist also eine Teilmenge der tatsächlichen
Fehler. Die Menge möglicher Fehler enthält Instruktionen, die den Fehler in einer
Ausführung aufweisen können, ist also eine Obermenge der tatsächlichen Fehler.
In Tabelle 2 sind die Fehlermengen dargestellt. Wie zu erkennen, konnten für
alle Fehler, bis auf Inkonsistente Daten und Zu spät gelöschte Daten, sowohl die
Menge der sicheren, als auch die Menge der möglichen Fehler angegeben werden.
Fehlerart sichere Fehler mögliche Fehler
Fehlende Daten A0 A0 , B3 , U7 , U4
Redundante oder C1 , F1 , D1 C1 , F1 , D1 , H1 , H2 , U1 , U2 , V1 , V2 , G1 ,
überschriebene Daten davon redundant: G2 , E1 , B1
C1 , D1 davon redundant: C1 , D1 , G2 , E1 , B1
Inkonsistente Daten / H4 , H5 , H6 , U5 , U6 , U7 , V4 , V5 , V6
Nicht gelöschte Daten C1 , A1 C1 , A1 , H1 , H2 , U1 , U2 , V1 , V2 , B1
Doppelt gelöschte Daten ∅ ∅
Zu spät gelöschte Daten / H3 , H5 , A1 , B3 , E1 , G3 , U4 , U7 , V6 , A0
Tabelle 3. Abgeleitete Fehler für den Beispielprozess aus Abbildung 1
Die Menge Fehlende Daten (sichere Fehler) enthält Instruktionen s der In-
struktionstypen Vi = destroy(Vj ), read(Vj ) und cond(Vj ), die für alle Kon-
trollflusspfade auf ein fehlendes Datum Vj zugreifen. Dazu wird überprüft, ob
M ISS M U ST für die Vj definierende Instruktion def (Vj ) dem Wahrheitswert true
entspricht. Die Menge Fehlende Daten (mögliche Fehler) umfasst Instruktionen,
die für einen Pfad auf ein fehlendes Datum zugreifen können, und wurde analog
über die Wahrheitswerte in M ISS M AY definiert. Auf gleiche Weise ergeben sich
die Fehlermengen Doppelt gelöschte Daten, nur das diese destroy-Instruktionen
enthalten und als Datenflussinformation DELM U ST , DELM AY genutzt wird.
Die Fehlermenge Redundante oder überschriebene Daten (sichere Fehler) um-
fasst write-Instruktionen, die Daten schreiben auf die im Prozess nie lesend, also
durch Instruktionen read oder cond zugegriffen wird. Zu diesem Zweck wird die
Menge aller im Prozess auf mindestens einem Kontrollflusspfad gelesenen Daten
bestimmt, als Vereinigung der Mengen DAT AM AY (def (Vk )) für alle durch In-
struktionen s0 : read(Vk ) und s0 : cond(Vk ) gelesenen Variablen Vk . Ist eine durch
Instruktion s : Vi = write(Vj ) definierte Variable Vi kein Element dieser Menge,
wird nie lesend auf Vi zugegriffen und die Instruktion erfüllt den Fehler. Die Men-
ge Redundante oder überschriebene Daten (mögliche Fehler) ergibt sich analog,
nur dass nun überprüft wird, ob eine durch Instruktion s : Vi = write(Vj ) defi-
nierte Variable Vi nicht auf allen Kontrollflusspfaden gelesen wird, unter Ausnut-
zung der Datenflussinformation DAT AM U ST und der Postdominanz-Relation.
In [5] wird zusätzlich eine Unterscheidung zwischen redundanten und über-
schriebenen Daten vorgenommen. Um auch eine solche Unterscheidung durch-
zuführen, kann die Menge s: Vl =write(Vk ) DAT AM AY (def (Vk )) aller auf min-
S
destens einem Kontrollflusspfad überschriebenen Variablen bestimmt werden. Ist
die durch eine write-Instruktion definierte Variable kein Element dieser Menge,
wird sie in keinem Fall überschrieben und muss daher redundant sein.
Die Menge Inkonsistente Daten (mögliche Fehler) umfasst Instruktionen, die
auf ein Datum zugreifen, auf das auch eine parallel ausgeführte Instruktion
schreibend oder löschend zugreift. Da solche Schreib-/Lese-Konflikte im erweiter-
ten Workflow-Graphen bereits mittels π-Funktionen gekennzeichnet sind, ergibt
sich die Fehlermenge als Menge aller Instruktionen, die auf eine durch π-Funktion
mit mehr als einem Operanden definierte Variable zugreifen. In ähnlicher Weise
zu den hier näher erläuterten Fehlermengen ergeben sich dann auch die Mengen
zu den Datenflussfehlern Nicht gelöschte Daten und Zu spät gelöschte Daten.
Eine auf diese Weise durchgeführte Abschätzung für die Datenflussfehler im
Beispielprozess aus Abbildung 1 ist in Tabelle 3 dargestellt. Aus Gründen der
Übersichtlichkeit wurden nicht Instruktionen, sondern die zugehörigen Variablen
angegeben. So enthalten die Mengen zum Fehler Fehlende Daten Variablen, die
fehlende Daten beschreiben und auf die durch eine Instruktion zugegriffen wird,
und die Mengen zum Fehler Nicht gelöschte Daten Variablen, die durch eine
Instruktion geschrieben aber später nicht gelöscht werden. Die Fehlermengen
beschreiben offenbar recht gut die im Prozess enthaltenen Fehler. Die Mengen
sicherer Fehler repräsentieren so nur tatsächlich immer im Prozess auftretende
Fehler. Die Mengen möglicher Fehler repräsentieren nahezu nur Fehler, die für
mindestens eine Prozessausführung auch tatsächlich auftreten. Lediglich bei U4
in der Fehlermenge Fehlende Daten und G2 in der Fehlermenge Redundante oder
überschriebene Daten handelt es sich um keine tatsächlichen Fehler.
5 Zusammenfassung
In der vorliegenden Arbeit haben wir eine Methode vorgestellt, die es für struk-
turierte Geschäftsprozesse erlaubt, Abschätzungen für Datenflussfehler effizient
zu bestimmen. Zu diesem Zweck werden erweiterte Workflow-Graphen als Pro-
zessmodell genutzt, die die Durchführung einer Datenflussanalyse begünstigen.
Basierend auf den durch Datenflussanalyse ableitbaren Informationen zu fehlen-
den, gelöschten und definierenden Daten konnten dann Fehlermengen für siche-
re und mögliche Datenflussfehler angegeben werden. Die Methode bietet neben
ihrer Effizienz den weiteren Vorteil, dass alle in einem Prozess enthaltenen Da-
tenflussfehler in einem Schritt abgeschätzt werden können. Im Gegensatz dazu
liefert ein Ansatz auf Grundlage einer Modellprüfung immer nur einen Fehler
als Gegenbeispiel zur untersuchten Eigenschaft. Zukünftige Arbeiten sollen die
praktische Relevanz dieser Vorteile anhand von Fallstudien weiter untersuchen.
Literatur
[1] Callahan, David ; Subhlok, Jaspal: Static Analysis of Low-level Synchronization.
In: ACM SIGPLAN Notices 24 (1989), Nr. 1, S. 100–111
[2] Lee, Jaejin ; Midkiff, Samuel P. ; Padua, David A.: Concurrent Static Single
Assignment Form and Constant Propagation for Explicitly Parallel Programs. In:
Languages and Compilers for Parallel Computing, 10th International Workshop,
LCPC’97, Minneapolis, Minnesota, USA, August 7-9, 1997, Proceedings, Springer,
1998 (LNCS 1366), S. 114–130
[3] Moser, Simon ; Martens, Axel ; Görlach, Katharina ; Amme, Wolfram ; God-
linski, Artur: Advanced Verification of Distributed WS-BPEL Business Processes
Incorporating CSSA-based Data Flow Analysis. In: 2007 IEEE International Con-
ference on Services Computing (SCC 2007), 9-13 July 2007, Salt Lake City, Utah,
USA, IEEE Computer Society Press, 2007, S. 98–105
[4] Sadiq, Wasim ; Orlowska, Maria E.: Analyzing Process Models Using Graph
Reduction Techniques. In: Information Systems 25 (2000), Nr. 2, S. 117–134
[5] Trc̆ka, Nikola ; van der Aalst, Wil M. ; Sidorova, Natalia: Data-Flow Anti-
patterns: Discovering Data-Flow Errors in Workflows. In: Advanced Information
Systems Engineering, 21st International Conference, CAiSE 2009, Amsterdam, The
Netherlands, June 8-12, 2009, Proceedings, Springer, 2009 (LNCS 5565), S. 425–439