The functional architecture focuses on decomposing functionality into modules that offer certain features. These features require interactions in order to complete their functionality. However, functional architectures typically only focus on the static aspects of the system design. Additional modeling techniques, such as message sequence charts are often used in the early phases of software design to indicate how the software should behave. In this paper we investigate the use of process discovery techniques to discover from these scenarios the internal behavior of individual components. Based on event logs, this paper presents an approach (1) to derive the information flows between features, (2) identify the internal behavior of features, and (3) to discover the order between features within a module. The approach results in a sound workflow model for each module. We illustrate the approach using a running example of a payment system.
One of the principle tasks of a software architect is to design a software
system [
An important aspect of software architecture is the functionality it offers.
To decompose and specify the functionality of software, the authors of [
Features interact with other features via information flows to offer their
functionality. However, FAM only offers a static view on this interaction, i.e., the
information flow only shows possible interactions, but imposes no order on or
dependencies between these flows. Thus, to show how functionality is offered
by the system, the architect requires additional models. One way is to define
scenarios on top of the models, in which the architect can specify which features
interact in which order. These scenario then result in event logs, that can be
analyzed using process mining techniques [
In software product organizations, time to market is often a more important
priority than having a properly documented software architecture. Consequently,
architecture documentation is often outdated or even missing [
The first question focuses on the discovery of information flows: given an event log, is it possible to derive which features interact? Next, we investigate whether it is possible to derive the internal behavior of features based on event logs. In other words, we focus on the question how does a feature use its information flows to complete its functionality. The last question deals with the high-level view of the functional architecture. To execute the system’s functionality, the features within a module are called in a certain order. Can process discovery techniques be used to discover these orders?
The remainder of this paper is structured as follows. To illustrate the approach, Sec. 2 presents a running example which we will use throughout the paper. Next, Sec. 3 presents the basic notions used in the paper. Section 4 introduces the functional architecture model in more detail, after which in Sec. 5 we will focus on solving the three questions posed in the introduction. Section 6 concludes the paper. 2
As an running example, consider the Payment System as introduced in [
As the software evolved into the current system, no precise model exists that specifies the behavior of this system. The system only recorded the order in which the different features of the modules have been called in an event log, as shown in Tbl. 1. Each pair in the table represents the feature and the module to which that feature belongs. For readability, the features and modules are abbreviated in this event log.
The system is decomposed into three modules: the Debtor module (X), the Payment (Y) module, and the Creditor (Z). Based on the event log, the software architect finds the following features: – Receive transaction request (A); – Reject transaction (B); – Accept transaction (C); – Cancel transaction (D); – Initiate payment (E); – Send payment details (F); – Archive transaction request (G). – Send transaction request (H); – Reject transaction request (I); – Initiate creditor (J); – Cancel transaction (K); – Initiate payment (O); – Handle payment (M); – Archive transaction (N). – Start transaction (Q); – Handle transaction (S).
G
A B C D E
F Debtor
H I J K O M
N Payment
Q
S Creditor
Fig. 1. Initial functional architecture model of the running example Case Trace 1 (H, Y), (A, X), (B, X), (G, X), (I, Y), (N, Y) 2 (H, Y), (A, X), (B, X), (I, Y), (G, X), N, Y) 3 (H, Y), (A, X), (B, X), (I, Y), (N, Y), (G, X) 4 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (K, Y), (D, X), (G, X), (N, Y) 5 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (K, Y), (D, X), (N, Y), (G, X) 6 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (K, Y), (N, Y), (D, X), (G, X) 7 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z),( O, Y), (E, X), (F, X), (G, X), (M, Y), (S, Z), (N, Y) 8 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (O, Y), (E, X), (F, X), (G, X), (M, Y), (N, Y), (S, Z) 9 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (O, Y), (E, X), (F, X), (M, Y), (G, X), (S, Z), (N, Y) 10 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (O, Y), (E, X), (F, X), (M, Y), (G, X), (N, Y), (S, Y) 11 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (O, Y), (E, X), (F, X), (M, Y), (S, Z), (G, X), (N, Y) 12 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (O, Y), (E, X), (F, X), (M, Y), (S, Z), (N, Y), (G, X) 13 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (O, Y), (E, X), (F, X), (M, Y), (N, Y), (G, X), (S, Z) 14 (H, Y), (A, X), (C, X), (J, Y), (Q, Z), (S, Z), (O, Y), (E, X), (F, X), (M, Y), (N, Y), (S, Y), (G, X)
Based on this information, the architect can draw the modules with their features, as shown in Fig. 1. In the remainder of this paper, we investigate a method to use event logs, such as the one shown in Tbl. 1, to complete the diagram and derive a behavioral specification of the system. 3
Let S be a set. The powerset of S is denoted by PpSq “ tS1 | S1 Ď Su. We use |S| for the number of elements in S. Two sets U and V are disjoint if U X V “ H. Some set S with relation ď is a partial order, denoted by pS, ďq, iff ď is reflexive, i.e. a ď a for all a P S, antisymmetric, i.e. a ď b and b ď a imply a “ b for all a, b P S, and transitive, i.e. a ď b and b ď c imply a ď c for all a, b, c P S. Given a relation R Ď S ˆ S for some set S, we denote its transitive closure by R`, and the transitive and reflexive closure by R˚.
A bag m over S is a function m : S Ñ IN , where IN “ t0, 1, . . .u denotes the set of natural numbers. We denote e.g. the bag m with an element a occurring once, b occurring three times and c occurring twice by m “ ra, b3, c2s. The set of all bags over S is denoted by IN S . Sets can be seen as a special kind of bag where all elements occur only once; we interpret sets in this way whenever we use them in operations on bags. We use ` and ´ for the sum and difference of two bags, and “, ă, ą, ď, ě for the comparison of two bags, which are defined in a standard way.
A sequence over S of length n P IN is a function σ : t1, . . . , nu Ñ S. If
n ą 0 and σpiq “ ai for i P t1, . . . , nu, we write σ “ xa1, . . . , any. The length
of a sequence is denoted by |σ|. The sequence of length 0 is called the empty
sequence, and is denoted by . The set of all finite sequences over S is denoted
by S˚. We write a P σ if a 1 ď i ď |σ| exists such that σpiq “ a. Concatenation
of two sequences ν, γ P S˚, denoted by σ “ ν; γ, is a sequence defined by σ :
t1, . . . , |ν| ` |γ|u Ñ S, such that σpiq “ νpiq for 1 ď i ď |ν|, and σpiq “ γpi ´ |ν|q
for |ν| ` 1 ď i ď |ν| ` |γ|. A sequence σ can be projected over some set U ,
denoted by σ|U , and is inductively defined by |U “ , pxay; σq|U “ xay; σ|U if
a P U , and pxay; σq|U “ σ|U otherwise.
Petri Nets A Petri net [
Let N “ xP, T, F y be a Petri net. Given a node n P pP Y T q, we define its preset N‚n “ tn1 | pn1, nq P F u, and its postset n‚N “ tn1 | pn, n1q P F u. We lift the notation of preset and postset to sets. Given a set U Ď pP Y T q, N‚U “ ŤnPU N‚n and U N‚ “ ŤnPU n‚N . If the context is clear, we omit the N in the subscript.
A marking of N is a bag m P IN P , where mppq denotes the number of tokens in place p P P . If mppq ą 0, place p is called marked in marking m. A Petri net N with corresponding marking m is written as pN, mq and is called a marked Petri net. Given a marked Petri net pN, mq, transition t is enabled, denoted by pN, mqrty, if ‚t ď m. If transition t is enabled in pN, mq, it can fire, resulting in a new marking m1, denoted by pN, mqrtypN, m1q, such that m1 ` ‚t “ m ` t‚. We lift the firing of transitions to the firing of sequences in a standard way, i.e., a sequence σ P T ˚ of length n is enabled in pN, mq if markings m0, . . . , mn exist, such that m “ m0 and pN, mi´1qrσpiqypN, miq for all 1 ď i ď n. A marking m1 is reachable from some marking m in N , denoted by pN, mqr˚ypN, m1q, if a firing sequence σ P T ˚ exists such that pN, mqrσypN, m1q. A marking m1 is a home marking of pN, mq, if for all markings m2 with pN, mqr˚ypN, m2q, we have pN, m2qr˚ypN, m1q.
A special class of Petri nets are the workflow nets [
Open Petri Nets Within a network of asynchronously communicating systems,
messages are passed between the elements within the network. The approach we
follow is based on Open Petri nets [
An important behavioral property for OPNs is termination: an OPN should always have the possibility to terminate properly. We identify two termination properties: weak termination and soundness. Definition 2. Let xP, I, O, T, F, i, f y be an OPN. It is weakly terminating, if for every reachable marking of the marked Petri net pxP Y I Y O, T, F y, iq a marking f P Ω can be reached.
It is sound, if for every reachable marking of the marked Petri net pxP, T, F y, iq a marking f P Ω can be reached.
Communication between OPNs is done via the interface places. Two OPNs can only communicate if the input places of the one are the output places of the other, and vice versa.
Definition 3. Two OPNs A and B are composable, denoted by A ‘ B, if and only if pIA X OBq Y pOB X IAq “ pPA Y TA Y IA Y OAq X pPB Y TB Y IB Y OBq.
If A and B are composable, they can be composed into a new OPN, denoted by A‘B, with A‘B “ xP, I, O, T, F, i, Ωy where P “ PAYPB YG; I “ pIAYIBqzG; O “ pOA Y OBqzG; T “ TA Y TB; F “ FA Y FB; i “ iA ` iB; and f “ ΩA Y ΩB with G “ pIA X OBq Y pOB X IAq.
Event Logs and Behavioral Profiles Although event logs are defined as a
tuple consisting of a set of case identifiers, events, and an attribute mapping [
Given a marked Petri net pN, mq with N “ xP, T, F y, an event log L Ď T ˚ is called complete with respect to pN, mq iff traces σ1, σ2 P T ˚ exist such that pN, mqrσ1; xa, by; σ2ypN,) implies a ăL b for all a, b P T . 4
To model the overview of a system, the modules it consists of, and the features
these modules offer, we propose the use of the functional architecture model
(FAM). The functional architecture of a system is “an architectural model which
represents at a high level the software products major functions from a usage
perspective, and specifies the interactions of functions, internally between each
other and externally with other products” [
An example is shown in Fig. 2(a). The FAM contains 1 context module, E, 7 modules, A, B, C, D, X, Y and Z. Modules have features, depicted by the rounded rectangles. For example, module C contains two features, K and L. Between features of different modules, information flows exist, e.g., the information flow pF, q, Lq between modules A and C. (a) Example Model
G A t H B X F s q u v Z
K r N
C D Y
L M
O E – M is a finite set of modules; – C is a finite set of context modules; – F is a finite set of features; – h : M Ñ M is the hierarchy function, such that the transitive closure h˚ is irreflexive; – m : F Ñ M Y C is a feature map that maps each feature to a module, possibly in the context, and this module does not have any children, i.e. h´1pmpF qq “ H for all F P F; – Ñ Ď F ˆ Λ ˆ F is the information flow, with Λ the label universe, such that for pA, l, Bq PÑ we have mpAq ‰ mpBq. The labels for the information flows are unique per feature, i.e., pA, l, Bq and pA, l, Cq imply B “ C for all labels l P Λ and pA, l, Bq, pA, l, Cq P Ñ.
Although the information flows define the possible interactions between modules, it remains a static overview of the system. Therefore, one can use scenarios on top of the functional architecture, e.g. by creating an overlay, highlighting the information flows that are executed and the order in which they should occur. Formally, we represent a scenario as a partial order.
Definition 5. Let F “ xM, C, F, h, m, Ñy be a FAM. A scenario of F is a pair pS, ăq with S ĎÑ, such that pS, ďq with ď “ ă˚ is a partial order.
An example is shown in Fig. 2(b). The scenario implied by the overlay can be represented by a partial order induced by pO, p, F q ă pF, q, Lq, pF, q, Lq ă pK, s, Hq, pF, q, Lq ă pK, r, N q, pK, r, N q ă pN, u, Hq, pK, s, Hq ă pH, t, Gq, pN, u, Hq ă pH, t, Gq, pK, r, N q ă pM, v, Hq, and pM, v, Hq ă pH, t, Gq.
However, such scenarios are typically not specified. Another important drawback of such scenarios is their analyzability. Although each scenario can be checked, the consistency between the different scenarios remains a difficult task. Therefore, in the remainder of this paper, we search for a method to derive the behavioral specification as a network of asynchronously communicating systems, given the system execution data produced by the actual system in the form of event logs. 5
In this section, we study the possibilities process mining [
The behavioral specification of a system is three-fold: (1) communication between modules via their features, (2) the internal behavior within each feature, and (3) the order in which features are called within a module. In this section, we explore all three types of behavioral specification to come to a composed system of asynchronously communicating systems.
In the remainder, let L be an event log over a set of features T , and let R : T Ñ M , with M the set of modules, be a function that maps each feature onto the module that contains that feature. 5.1
Communication between Features Communication between modules within a system is asynchronous of nature: messages are sent between features in order to complete their functionality. Within an event log, we need to consider the order in which events or features occur. For example, given some trace σ, if the resource is different for two subsequent events, i.e., Rpσpiqq ‰ Rpσpi ` 1qq, then this might indicate that the former sends a message to the latter. This is expressed by the communication successor.
Definition 6 (Communication successor). Let L Ď T ˚ be an event log. We define the communication successor relation ÎL Ď T ˆ T by A ÎL B iff RpAq ‰ RpBq, σpiq “ A, and σpi ` 1q “ B for some σ P L and 1 ď i ă |σ|.
Although at first sight the communication successors seem to work, we need to remember the concurrent nature of asynchronous communication. Consider for example the communication between modules M and N as depicted in Fig. 3, and
Case Trace 1 A, E, F, G, B, C 2 A, E, F, B, G, C 3 A, E, B, F, G, C 4 A, E, B, F, C, G 5 A, E, F, B, C, G 6 A, B, E, F, G, C 7 A, B, E, F, C, G the corresponding allowed sequences in Tbl. 4. We have A Î E, which is indeed the communication as modeled in the composition M ‘ N . However, we also find G Î B, indicating a possible communication between G and B. Listing all communication successors, we get A Î E, G Î B, F Î B, B Î G, G Î C, E Î B, B Î F , F Î C, C Î G, and B Î E. Observe that because of the asynchronous nature of the communication, features B and E are concurrently enabled in Fig. 3. Assuming the event log to be complete, this should become visible in the communication successor relation, as for the normal successor relation on event logs. by: Definition 7 (Communication behavioral profile). Let L Ď T ˚ be an event log, and ÎL Ď T ˆ T the corresponding communication successor relation.
The communication behavioral profile is the 3-tuple pÑc, kc, `cqLCom defined – A Ñc B iff A ÎL B and B ÎL A; – A kc B iff both A ÎL B and B ÎL A; and – A `c B iff both A ÎL B and A ÎL B.
Calculating the behavioral profile of the communicating transitions using the communication successor relation, results in the communication behavioral profile as shown in Tbl. 3. It shows that B and E are concurrently enabled. Following the behavioral profile, we see that the causal relation of the behavioral profile correctly identifies the feature communication.
Using the communication behavioral profile, we can construct the information flows from an event log as follows. If A Ñ B in the communication behavioral
Debtor Payment Creditor
A B C D E F G H I J K O M N Q S profile of the event log, then an information flow pA, x, Bq exists, with x a fresh label. This results in the following translation: Definition 8 (Generated FAM). Let L be an event log, and pÑc, kc, `cqLCom be its communication behavioral profile. Its corresponding functional architecture model xM, C, F, h, m, Ñy is defined by: – M “ RpLq; – C “ H; – F “ T ; – h “ H; – m “ R; and – Ñ“ tpA, x, Bq | A Ñc B, and x P Λ a fresh labelu.
After constructing the communication behavioral profile for the running example, shown in Tbl. 4, we can complete the functional architecture model. Based on the given system execution data, we see for example that feature H communicates with feature A, and feature S sends messages to features K and O, and receives messages from feature M . The complete functional architecture of the running example is shown in Fig. 4. 5.2
Internal Behavior of Features As can be seen in the running example, features can send and receive multiple messages. For example, feature S sometimes sends a message to feature K and sometimes to feature O. Therefore, the next step in discovering the functional C D E
F
K O M N
architecture is to reconstruct the internal behavior of each of the features. For this, we create for each of the features an event log, containing the features that it communicates with. We call this the feature log.
Definition 9 (Feature log). Let L Ď T ˚ be an event log, and let F P T be some feature. Let pÑc, kc, `cqLCom be the corresponding communication behavioral profile. The feature log LF is defined by LF “ tσ|CpF q | σ P L, F P σu where CpF q “ tA | A Ñc F _ F Ñc Au.
Consider for example feature S in the running example. This feature communicates with features K, O and M , i.e., CpSq “ tK, O, M u. Its feature log is the projection of the log on these features, i.e., LS “ txKy, xO, M yu.
On these feature logs, we apply the inductive miner [
YtppA´F , tq | t P T, λptq “ A, A Ñc F qu. where xP¯, T¯, F¯, ¯i, f¯y is the discovered workflow net.
In our running example, each of the 16 features are transformed into a feature net. Most of the features are simple, like for feature H and A, consisting of pM-S
O M
K pH-A
A pH-A
H pJ-C pJ-Q
C Q pS-K pK-D
S D Feature S
Feature H
Feature A
Feature J
Feature K
a single transition sending a message to A, and receiving a message from H,
respectively. A more complex feature net is the net for feature S, which internally
decides whether it sends a message to K or to O. Figure 5 depicts some of the
feature nets generated using the inductive miner [
Definition 11 (Module Log). Let L Ď T ˚ be an event log. Let M P RngpRq be a module. Let pÑc, kc, `cq be the corresponding communication behavioral profile. The Module log LM is defined by LM “ tσ|tF |RpF q“Mu | σ P Lu.
Within the running example, we obtain three module logs, one for each of the modules. For example, module Debtor, has module log LDebtor “ txA, B, Gy, xA, C, D, Gy, xA, C, E, F, Gyu, and for Creditor we have LCreditor “ txQ, Sy,
B
I
H K
J N
O M
Q S Module Debtor
Module Payment
Module Creditor xQ, S, Syu. Again applying the inductive miner results in the three workflow nets as depicted in Fig. 7. Notice that, although feature S occurs twice in one of the sequences, the algorithm only adds a single feature S in the resulting workflow model.
Composition of Feature Nets and Module Nets Last step in the process is to combine the feature nets generated for each of the features with the generated module nets. This results in an open Petri net for each of the modules, defining the interaction between the different modules.
In the module net, each feature is represented by a single transition. Next step is to refine each feature by its feature net. For this, we first define the refinement of a transition by a workflow model on open Petri nets, as shown in Fig. 6. This refinement connect each input place of the refined transition with each of the transitions in the postset of the initial place of the workflow, and similarly each output place of the refined transition with each of the transitions in the preset of the final place of the refining workflow. It is straight-forward to prove that if (1) the initial net is sound, (2) each input place of the refined transition is 1-bounded, i.e., it can contain at most one token, and (3) workflow net W is sound, then the refinement yields a sound result.
H I J K O M pH-A pB-I pC-J pK-D pO-E pF-M pJ-Q pS-K pS-O pM-S
Q S pJ-Q pS-K pS-Q pM-S G
The result of refining each feature by its feature net is shown in Fig. 8. As features G and N have no feature net defining communication, these transitions are not refined.
To verify whether the resulting open Petri nets are a true representation of the system, one can compose the nets into a single Petri net, and execute each of the sequences of the event log of Tbl. 1 on the resulting model, which in this example is possible. Further analyzing the resulting model shows that its only deadlocks are desirable markings: either all modules reach their final place, without any pending tokens, or the Creditor module remains untouched, while the Debtor and Payment module reach their final place. 6
Within this paper, we discussed a method to automatically generate a functional architecture model from an event log together with a mapping of each feature to the module that offers that functionality. We showed how the information flows can be derived from the communication behavioral profile. This profile not only identifies the information flow for the static structure of the functional architecture, but additionally offers sufficient information to construct the internal behavior for each of the features, and between the features within a module. Lastly, we showed how to compose feature and module nets into an open Petri net.
Discovering the interaction between different modules is not new. Tchniques
like service mining [
In [
The core idea of this paper is twofold: firstly to derive the information flows
for a Functional Architecture Model, and secondly to derive the internal behavior
for each of the modules within the architecture. Within software architecture,
this is called Software Architecture Reconstruction [
Although the approach presented in this paper shows an application of the behavioral profile to discover feature interaction, additional research is required. First, the current approach requires the event log to be complete, i.e., if the log grows, the successor relation should not change. Further, for the generation of the internal feature behavior, we assume that if the sending feature is present in the event log, it enables all possible events, which is possibly a too strict assumption that deserves further investigation.
The approach in this paper is very flexible, as we derive individual models
for the features and modules. For this, we apply standard process discovery
algorithms returning sound workflow models. However, their composition in general
does not result in a sound system of asynchronously communicating systems.
Further research is required to study the conditions under which this can be
guaranteed. For this, we want to identify conditions which on the one hand
result in correct models, and on the other hand have a positive effect on model
quality as described by [
Not only does this approach provide useful insights for the software architect,
we expect the approach applicable to business process management as well, as
for the discovery of separate business processes, the Business Process Modelling
and Notation offers the swimlane notion. Therefore, we plan to implement the
approach in the Process Mining toolkit ProM [
Acknowledgements The authors would like to thank the anonymous reviewers for their valuable feedback, and Sjaak Brinkkemper, Fabiano Dalpiaz, Garm Lucassen, Leo Pruijt and Erik Jagroep for the fruitfull discussions and valuable input on architecture and software products.