Zusammenfassung. Neben dem Kontrollfluss von Gescha¨ftsprozessen kann auch der Datenfluss Ursache einer fehlerhaften Prozessausfu¨hrung sein, daher ist die U¨berpru¨fung eines Prozessmodells auf Datenflussfehler ebenfalls wesentlich. Wir schlagen in diesem Beitrag eine Methode zur Abscha¨tzung von Datenflussfehlern fu¨r strukturierte Gescha¨ftsprozesse vor. Auf Grundlage der durch eine Datenflussanalyse abgeleiteten Datenflussinformation geben wir Fehlermengen fu¨r mo¨gliche und sichere Datenflussfehler eines Gescha¨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 Pra¨zision.
Neben der Verifikation von Gescha¨ftsprozessen hinsichtlich Kontrollflussfehlern,
wie Verklemmungen oder fehlender Synchronisation, ist die Analyse der
Verwendung von Prozessdaten zur Gewa¨hrleistung einer fehlerfreien Prozessausfu¨hrung
von Interesse [
Ein insbesonders fu¨r die Analyse des Datenflusses geeignetes Verfahren ist die
statische Datenflussanalyse [
das im weiteren Verlauf nicht lesend zugegriffen wird
auf das noch nicht lesend zugegriffen wurde
paralleles Schreiben oder Lo¨schen desselben Datums
Im vorliegenden Beitrag zeigen wir, wie das Verfahren der Datenflussanalyse zur U¨berpru¨fung eines strukturierten Gescha¨ftsprozesses auf Datenflussfehler genutzt werden kann. In Abschnitt 2 wird dazu zuna¨chst ein U¨ berblick zu Datenflussfehlern und dem hier verwendeten Prozessmodell gegeben. Danach erfolgt in Abschnitt 3 eine Beschreibung der Bestimmung von fehlenden, gelo¨schten sowie definierenden Daten mit Hilfe einer statischen Datenflussanalyse. Auf Grundlage der so fu¨r einen Prozess effizient ableitbaren Datenflussinformationen ko¨nnen wir dann in Abschnitt 4 Fehlermengen einfu¨hren, die Abscha¨tzungen zu den im Prozess enthaltenen Datenflussfehlern in Form sicherer und m¨oglicher Fehler bilden. Schließlich wird der Beitrag in Abschnitt 5 kurz zusammengefasst. 2 2.1
Datenflussfehler
In der Arbeit [
Prozessrepr¨asentation
Zur Durchfu¨hrung unserer Methode beno¨tigen wir ein Prozessmodell, dass die
Wiedergabe des Datenflusses innerhalb eines Prozesses gestattet. Zu diesem
Zweck werden erweiterte Workflow-Graphen genutzt, die gewo¨hnliche
WorkflowGraphen [
cond(V) read: B, G, U write: F, H destroy: / read: / write: U destroy: /
Fork
A1= write(A0) D1= write(D0) H4=π(H0, H2) H1= write(H4) read(A1) H5=π(H1, H2) read(H5) U5=π(U0, U2) U1 = write(U5) V4 =π(V0, V2) V1 = write(V4) D2 = destroy(D 1) Join
Split read(E1) G2 = write(G1) B2= destroy(B1)
Merge read(F 2) read(H3) read(U4) E2= destroy(E1) F3= destroy(F2) G4 = destroy(G3 )
B1= write(B0) G1 = write(G0) V5 =π(V0, V1) V2 = write(V5) cVo6n=dπ(V(V6)2, V1)
U6=π(U0, U1) U2 = write(U6) G3=Φ(G2, G1) B3= Φ(B2, B1)
U3 =Φ(U0, U2) read(B3) read(G3) U7=π(U3, U1) read(U7) F2= write(F1) H6=π(H0, H1) H2= write(H6) H3=Φ(H1, H2) V3 =Φ(V1, V2) U4 =Φ(U1, U3)
Abbildung 1 ist der erweiterte Workflow-Graph fu¨r den aus [
Im erweiterten Workflow-Graphen sind die Annotationen u¨bernommen, nur
dass diese nun im Format der Concurrent Static Single Assignment Form
(CSSAForm) [
Wert der Variablen Vi auf undefiniert.
Charakteristische Eigenschaft der CSSA-Form ist, dass jede Variable statisch einmal definiert ist, so dass fu¨r jede Variablendefinition durch die Instruktionen write oder destroy ein eigener Name eingefu¨hrt, und Variablenzugriffe entsprechend angepasst wurden (beispielsweise G1, . . . , G4 fu¨r Variable G). Treffen mehrere Definitionen einer Variablen auf verschiedenen Pfaden des Kontrollflusses in einem Knoten zusammen, wurden spezielle Instruktionen mit wie folgt definierten Φ-Funktionen eingefu¨gt, um die Definitionen zusammenzufassen: Definition 2 (Φ-Funktion). Eine Φ-Funktion fu¨r Variable V hat die Form Φ(V1, . . . , Vn), wobei die Operanden Vi den im Knoten der Funktion zusammenfließenden Definitionen von V entsprechen. Der Wert der Funktion ist der Operand Vi, der die zur Prozesslaufzeit tats¨achlich, beziehungsweise als letztes, ausgefu¨hrte Instruktion mit einer Definition der Variablen V repr¨asentiert.
Neben den Instruktionen mit Φ-Funktionen entha¨lt die CSSA-Form weitere spezielle Instruktionen mit π-Funktionen, um Schreib-/Lese-Konflikte zwischen parallelen Prozessaktivita¨ten modellieren zu ko¨nnen: Definition 3 (π-Funktion). Eine π-Funktion fu¨r Variable V hat die Form π(V1, . . . , Vn), wobei die Operanden Vi den im Knoten der Funktion konkurrierenden Definitionen von V entsprechen. Der Wert der Funktion ist der Operand Vi, der die zur Prozesslaufzeit letzte Definition von V repr¨asentiert. 3
Auf Grundlage der Repra¨sentation eines strukturierten Gescha¨ftsprozesses durch erweiterte Workflow-Graphen ko¨nnen dann Informationen zum Datenfluss abgeleitet werden. Fu¨r die Bestimmung der sicheren und mo¨glichen Fehler zu den in Tabelle 1 aufgefu¨hrten Fehlerarten werden Datenflussinformationen u¨ber die fehlenden, gel¨oschten und definierenden Daten des untersuchten Prozesses beno¨tigt.
Als fehlende Daten werden Variablen bezeichnet, die uninitialisiert sind oder gelo¨scht wurden. Dabei kann unterschieden werden, ob eine Variable fu¨r mindestens ein Ausfu¨hrungsszenario ein fehlendes Datum beschreibt, oder fu¨r alle mo¨glichen Prozessausfu¨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) ausgefu¨hrt wurde. Zur Darstellung der Datenflussinformation werden Wahrheitswerte genutzt, die angeben ob eine Variable ein fehlendes Datum beschreibt. Bedingt durch die Eigenschaft der CSSA-Form dass jede Variable statisch nur einmal definiert ist, ko¨nnen diese Werte den die Variablen definierenden Instruktionen zugewiesen werden: Definition 4 (Fehlende Daten). Fu¨r Instruktion s enth¨alt M ISSMUST (s) einen Wahrheitswert, der anzeigt ob die durch s definierte Variable auf allen Kontrollflusspfaden uninitialisiert/gel¨oscht ist und M ISSMAY (s) einen Wert, ob die Variable auf mindestens einem Pfad uninitialisiert/gel¨oscht ist. Ist die Instruktion s nicht vorhanden, gilt M ISSMUST (s) = M ISSMAY (s) = true.
Analog ergibt sich die Datenflussinformation zu gel¨oschten Daten, die angibt ob eine Variable im Prozess bereits gelo¨scht wurde: Definition 5 (Gelo¨schte Daten). Fu¨r Instruktion s enth¨alt DELMUST (s) einen Wahrheitswert, der anzeigt ob die durch s definierte Variable auf allen Kontrollflusspfaden gel¨oscht wurde und DELMAY (s) einen Wahrheitswert, der anzeigt ob diese Variable auf mindestens einem Pfad gel¨oscht wurde. Ist die Instruktion s nicht vorhanden, gilt DELMUST (s) = DELMAY (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 Prozessausfu¨hrung festlegen (beispielsweise {H1, H2} fu¨r Variable H3 in Abbildung 1), oder in allen: Definition 6 (Definierende Daten). Fu¨r Instruktion s enth¨alt die Menge DAT AMUST (s) alle Daten, welche den Wert der durch s definierten Variablen auf allen Kontrollflusspfaden festlegen und die Menge DAT AMAY (s) alle Daten, welche den Wert dieser Variablen auf mindestens einem Pfad festlegen. Ist die Instruktion s nicht vorhanden, gilt DAT AMUST (s) = DAT AMAY (s) = ∅.
Um die so definierten Datenflussinformationen fu¨r einen Gescha¨ftsprozess
exakt bestimmen zu ko¨nnen, ist eine Analyse der parallel ausfu¨hrbaren
Prozessaktivita¨ten notwendig. Grundsa¨tzlich ist eine solche Analyse Co-NP-schwer [
Fehlerart
(sichere Fehler)
(mo¨gliche Fehler)
u¨berschriebene Daten (sichere Fehler)
u¨berschriebene Daten
(sichere Fehler) (mo¨gliche Fehler)
(mo¨gliche Fehler)
(sichere Fehler)
s0: read(Vk) s0 postdominiert s ∪ S s0: cond(Vk) DAT AMUST (def (Vk)) ) } s0 postdominiert s { s | ( s : Vi = destroy(Vj) ∨ s : read(Vj) ∨ s : cond(Vj) ∨ s : Vi = write(Vj) ) ∧ Vj ist def iniert durch π−Funktion mit mehr als einem Operanden } { s | s : Vi = write(Vj) ∧ Vi ∈/ ( Ss0: Vl=destroy(Vk) DAT AMAY (def (Vk)) ∪ Ss0: Vl=write(Vk) DAT AMAY (def (Vk)) ) } { s | s : Vi = write(Vj) ∧ Vi ∈/ ( S s0: Vl=destroy(Vk) DAT AMAY (def (Vk)) s0 postdominiert s ∪ S s0: Vl=write(Vk) DAT AMAY (def (Vk)) ) } s0 postdominiert s { s | s : Vi = destroy(Vj)
∧ DELMUST (def (Vj)) = true } { s | s : Vi = destroy(Vj)
∧ DELMAY (def (Vj)) = true } { s | ( s : read(Vi) ∨ s : cond(Vi) ) ∧ @ s0 : Vj = destroy(Vi) in Basisblock von s ∧ Vi ∈/ ( S s00: read(Vk) ∧ s006=s DAT AMUST (def (Vk)) s00 postdominiert s ∪ S s00: cond(Vk) ∧ s006=s DAT AMUST (def (Vk)) ) } s00 postdominiert s
Fehlermenge { s | ( s : Vi = destroyM(VIjS)S∨M UsS: Tr(edaedf((VVjj))) = true } ∨ s : cond(Vj) ) ∧ { s | ( s : Vi = destroyM(VIjS)S∨M AsY: (rdeeafd(V(Vjj))) = true } ∨ s : cond(Vj) ) ∧ { s | s : Vi = write(Vj) ∧ Vi ∈/ ( Ss0: read(Vk) DAT AMAY (def (Vk))
∪ Ss0: cond(Vk) DAT AMAY (def (Vk)) ) } { s | s : Vi = write(Vj) ∧ Vi ∈/ ( S DAT AMUST (def (Vk)) 4
Nachdem Abscha¨tzungen fu¨r die fehlenden, gelo¨schten und definierenden Daten fu¨r einen Prozess bestimmt wurden, ko¨nnen dessen sichere und m¨ogliche Datenflussfehler abgeleitet werden. Zu diesem Zweck definieren wir fu¨r jeden der in Tabelle 1 aufgefu¨hrten Fehler zugeho¨rige Fehlermengen (vergleiche Definition 1): Die Menge sicherer Fehler entha¨lt Instruktionen, die den Fehler sicher und in allen Prozessausfu¨hrungen aufweisen, ist also eine Teilmenge der tatsa¨chlichen Fehler. Die Menge m¨oglicher Fehler entha¨lt Instruktionen, die den Fehler in einer Ausfu¨hrung aufweisen ko¨nnen, ist also eine Obermenge der tatsa¨chlichen Fehler. In Tabelle 2 sind die Fehlermengen dargestellt. Wie zu erkennen, konnten fu¨r alle Fehler, bis auf Inkonsistente Daten und Zu sp¨at gel¨oschte Daten, sowohl die Menge der sicheren, als auch die Menge der mo¨glichen Fehler angegeben werden.
Fehlerart sichere Fehler mo¨gliche Fehler
Redundante oder C1, F1, D1 C1, F1, D1, H1, H2, U1, U2, V1, V2, G1, u¨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 gelo¨schte Daten C1, A1 C1, A1, H1, H2, U1, U2, V1, V2, B1
Zu spa¨t gelo¨schte Daten / H3, H5, A1, B3, E1, G3, U4, U7, V6, A0
Die Menge Fehlende Daten (sichere Fehler) entha¨lt Instruktionen s der Instruktionstypen Vi = destroy(Vj), read(Vj) und cond(Vj), die fu¨r alle Kontrollflusspfade auf ein fehlendes Datum Vj zugreifen. Dazu wird u¨berpru¨ft, ob M ISSMUST fu¨r die Vj definierende Instruktion def (Vj) dem Wahrheitswert true entspricht. Die Menge Fehlende Daten (m¨ogliche Fehler) umfasst Instruktionen, die fu¨r einen Pfad auf ein fehlendes Datum zugreifen ko¨nnen, und wurde analog u¨ber die Wahrheitswerte in M ISSMAY definiert. Auf gleiche Weise ergeben sich die Fehlermengen Doppelt gel¨oschte Daten, nur das diese destroy-Instruktionen enthalten und als Datenflussinformation DELMUST , DELMAY genutzt wird.
Die Fehlermenge Redundante oder u¨berschriebene Daten (sichere Fehler) umfasst 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 AMAY (def (Vk)) fu¨r alle durch Instruktionen 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 erfu¨llt den Fehler. Die Menge Redundante oder u¨berschriebene Daten (m¨ogliche Fehler) ergibt sich analog, nur dass nun u¨berpru¨ft wird, ob eine durch Instruktion s : Vi = write(Vj) definierte Variable Vi nicht auf allen Kontrollflusspfaden gelesen wird, unter Ausnutzung der Datenflussinformation DAT AMUST und der Postdominanz-Relation.
In [
Die Menge Inkonsistente Daten (m¨ogliche Fehler) umfasst Instruktionen, die auf ein Datum zugreifen, auf das auch eine parallel ausgefu¨hrte Instruktion schreibend oder lo¨schend zugreift. Da solche Schreib-/Lese-Konflikte im erweiterten 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 a¨hnlicher Weise zu den hier na¨her erla¨uterten Fehlermengen ergeben sich dann auch die Mengen zu den Datenflussfehlern Nicht gel¨oschte Daten und Zu sp¨at gel¨oschte Daten.
Eine auf diese Weise durchgefu¨hrte Abscha¨tzung fu¨r die Datenflussfehler im Beispielprozess aus Abbildung 1 ist in Tabelle 3 dargestellt. Aus Gru¨nden der U¨ bersichtlichkeit wurden nicht Instruktionen, sondern die zugeho¨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¨oschte Daten Variablen, die durch eine Instruktion geschrieben aber spa¨ter nicht gelo¨scht werden. Die Fehlermengen beschreiben offenbar recht gut die im Prozess enthaltenen Fehler. Die Mengen sicherer Fehler repra¨sentieren so nur tatsa¨chlich immer im Prozess auftretende Fehler. Die Mengen mo¨glicher Fehler repra¨sentieren nahezu nur Fehler, die fu¨r mindestens eine Prozessausfu¨hrung auch tatsa¨chlich auftreten. Lediglich bei U4 in der Fehlermenge Fehlende Daten und G2 in der Fehlermenge Redundante oder u¨berschriebene Daten handelt es sich um keine tatsa¨chlichen Fehler. 5
In der vorliegenden Arbeit haben wir eine Methode vorgestellt, die es fu¨r strukturierte Gescha¨ftsprozesse erlaubt, Abscha¨tzungen fu¨r Datenflussfehler effizient zu bestimmen. Zu diesem Zweck werden erweiterte Workflow-Graphen als Prozessmodell genutzt, die die Durchfu¨hrung einer Datenflussanalyse begu¨nstigen. Basierend auf den durch Datenflussanalyse ableitbaren Informationen zu fehlenden, gelo¨schten und definierenden Daten konnten dann Fehlermengen fu¨r sichere und mo¨gliche Datenflussfehler angegeben werden. Die Methode bietet neben ihrer Effizienz den weiteren Vorteil, dass alle in einem Prozess enthaltenen Datenflussfehler in einem Schritt abgescha¨tzt werden ko¨nnen. Im Gegensatz dazu liefert ein Ansatz auf Grundlage einer Modellpru¨fung immer nur einen Fehler als Gegenbeispiel zur untersuchten Eigenschaft. Zuku¨nftige Arbeiten sollen die praktische Relevanz dieser Vorteile anhand von Fallstudien weiter untersuchen.