=Paper=
{{Paper
|id=Vol-2907/paper13
|storemode=property
|title=Master Channel Places for Communication Structured Acyclic Nets
|pdfUrl=https://ceur-ws.org/Vol-2907/paper13.pdf
|volume=Vol-2907
|authors=Mohammed Alahmadi
|dblpUrl=https://dblp.org/rec/conf/apn/Alahmadi21
}}
==Master Channel Places for Communication Structured Acyclic Nets==
https://ceur-ws.org/Vol-2907/paper13.pdf
Master Channel Places for Communication Structured
Acyclic Nets
(Short Paper)
Mohammed Alahmadi
School of Computing, Newcastle University
1 Science Square, Newcastle upon Tyne, NE4 5TG, United Kingdom
m.s.h.alahmadi2@ncl.ac.uk
Abstract. We propose an extension of communication structured acyclic nets
(CSA-nets) based on coloured tokens. CSA-nets provide a way for representing
relationships between sets of acyclic nets. Relationships between the component
acyclic nets are represented, in particular, by channel places. For large CSA-nets,
the number of channel places can make the model difficult to visualise and anal-
yse. To address this, we propose to apply mechanisms found in the domain of
coloured Petri nets, introducing master channel places which collapse possibly
many channel places into a single node. Such places could help in the visualisa-
tion, comprehension and analysis of CSA-nets.
Keywords: structured occurrence net, structured acyclic net, coloured net, chan-
nel place
1 Introduction
A complex evolving system (CES) can be viewed as a system of subsystems that are
concurrently interacting with each other. Also, such a system is often characterised by
a dynamically changing structure and features as well as intricate and large behavioural
patterns. Structured occurrence nets (SONs) [4,6,7] are a formalism to represent be-
haviours of CES systems using various relationships.
Communication structured acyclic nets (CSA-nets) are an extension of SONs. They
have the ability to model behaviours of component subsystems using acyclic nets (rather
than occurrence nets) as well as synchronous and asynchronous communications be-
tween component subsystems through channel places. A major application area of CSA-
nets are (cyber)crime investigations that have gained a significant interest in recent years
and have already been discussed in [1] in the context of the SON model.
What may hinder effective criminal investigations is the complexity and large vol-
ume of information which, in turn, presents a major challenge to the investigators in
terms of both interpreting the crime and making the right decision. Bearing in mind
that accurate criminal investigation process not only helps in interpreting the crimes [9],
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons Li-
cense Attribution 4.0 International (CC BY 4.0).
234 Mohammed Alahmadi
but also can offer suggestions on how to prevent them [3], improving visualisation and
analysis of CSA-nets is an important issue.
Criminal investigations are difficult to capture formally due to a high number of the
various types of information, resulting from the different sources of information being
involved, that need to be interpreted. As a result, criminal investigations are perceived
as complicated tasks presenting a major challenge to investigators. Despite the fact that
such a huge quantity of information is of high importance, its volume may distract
the investigator leading to inaccurate/delayed decisions. Accurate visualisation of such
complicated information would result in a better understanding of the criminal cases. In
particular, it would help the investigators to detect the causality and dynamic behaviours
involving the events which, in turn, would help to analyse and detect crimes.
The papers [1,2,9] recommend large-scale investigations to be supported by formal
methods and tools. Unfortunately, there is a shortage of suitable tools that can be used.
The foundation of the present work are CSA-nets which are a new framework that can
be used for the modelling of CES systems and can be modified for handling large-scale
investigations.
In this paper, we propose to improve the visualisation and analyses of CSA-nets
by introducing the concept of master channel places which add folding mechanism to
otherwise plain CSA-nets. We present our ideas with help of intuitive examples, leaving
out their formalisation and the associated proofs.
2 Communication structured acyclic nets (CSA-nets)
Structured occurrence nets (SONs) [6] are a Petri net based model for the representation
of the execution behavior of complex systems. They are an extension of the occurrence
nets which represent the causality and concurrency information relating to a single sys-
tem execution [8].
In general, a CSA-net consists of several acyclic nets linked through different types
of formal relationships. They are intended to capture information about: (i) the interac-
tion between actual/excepted behaviors; and (ii) the collected evidence to be analysed.
CSA -nets can represent different actions of dynamic evolving systems [4]. Each compo-
nent acyclic net represents a local view of the system’s behaviour which is, in general,
easy to interpret. The hurdle is that an analogous representation at the global system
level leads to a complex visualisations, especially in evolving systems. This decreases
the system interpretability.
A particular formal model we are using in this paper are the communication struc-
tured acyclic nets (CSA-nets), where the individual acyclic nets are linked by channel
places capable of modelling both asynchronous and synchronous communication be-
tween different subsystems. In other words, the events are used to link the acyclic nets
with each other through the channel . Figure 1(a) shows an example of CSA-net with
two ‘horizontal’ occurrence nets (the upper one exhibiting concurrency) connected by
two channel places, q1 and q2 . The idea is that these places establish communication
links. When the channel places are used asynchronously, the CSO-net can generate, e.g.,
the step sequence {d}{a, b}{e, c}. In addition, when they are used synchronously, the
step sequence {d}{a, b, c}{e} can be executed. That is, there is an instantaneous trans-
Master Channel Places for Communication Structured Acyclic Nets 235
a
(a) d e
b
q1 q2
c
a
(b) d e
b
q2 q1
Q
q1 q2
c
Fig. 1. A CSO-net and the corresponding version with a master channel place.
fer of tokens generated by a and b to transition c. Such a feature can, in particular, be
used to model synchronous communication between the component occurrence nets.
In this paper, we are concerned with Communication Structured Acyclic Nets (CSA-
nets) which generalise CSO-nets by using (safe) acyclic nets (with forward and back-
ward conflicts) instead of (conflict-free) occurrence nets. Figure 2(a) shows an example
of CSA-net which, intuitively, combines two executions, one involving transitions a and
c, and the other involving b, d, c and e. CSA-nets support a robust and effective struc-
ture that reduces complexity when compared to other representations, however, they
lack the ability to visualise large designs at a time. More precisely, only one token can
be represented in one channel place at any time. So, the idea behind this work is to
improve and extend CSA-nets to be able to better visualise bigger nets, and so enhance
the model visualisation and analysis.
3 Master channel places
In our ongoing work, we propose to allow channel places to represent more than one
token at a time. Figures 1(b) and 2(b) respectively show the CSO-net of Figure 1(a)
236 Mohammed Alahmadi
a
b d
(a) q1 q2
c e
a
q1
b d
q1 q2
(b)
q1 q2
c e
Fig. 2. A CSA-net and a corresponding version with master channel place.
and CSA-net of Figure 2(a) where the two channel places were replaced by single place.
Moreover, we added annotations on the arcs adjacent to the new places, and adjusted the
execution rules. What is important to emphasize is that the annotations are sets of the
original channel places (the curly brackets of sets are not shown). The execution rules
follow the standard idea of Coloured Petri Nets which ensure that the tokens ‘flowing’
along the arcs match the annotations (the tokens in master channel places are simply
the original channel places).
Therefore, we propose to introduce master channel places (MCPs), which intro-
duce conciseness to CSA-net by collapsing (folding) channel places into master channel
places. These master channel places allow representing more than one token and allow
the component acyclic nets to communicate through a unique channel place. Inside a
master channel place, there will be a set of tokens represented by a unique colours. A
specific token will appear in the master channel place without conflicting with other
tokens in each execution since a master channel place is colour-safe due to the fact that
the original CSA-net was safe. This enhances SON visualisation contributing to a more
readable and understandable model.
Master Channel Places for Communication Structured Acyclic Nets 237
c2 e2 c3 e3 c4 e4 c5
c0 e0 c1 e1 e8 c10 e9 c11 e10 c12
c6 e5 c7 e6 c8 e7 c9
q1 q2 q3 g0 q4 q5 q6
q0
master channel place
q0
q1 q2 q3 q4 q5 q6
c15 e13 c16 e14 c17 e15 c18
c13 e11 c14 e12 e19 c23 e20 c24 e21 c25
c19 e16 c20 e17 c21 e18 c22
g1
Fig. 3. A CSO-net with a single master channel place.
Figure 3 shows another example of using a master channel place. It can be observed
that the display is well-structured and, in particular, that any crossing of the arcs ad-
jacent to the original channel places is avoided which enhances the representation of
the CSA-net. In fact, introducing a single master channel place may lead to introducing
an unwanted crossing of arcs. This is illustrated in Figure 4. If one introduced a single
master channel place for the CSO-net in Figure 4(a) then (without placing it ‘outside’
the outline of the underlying occurrence nets which in general is not acceptable since
the individual acyclic nets will be too large to fit in a single screen), crossing would be
unavoidable.
A way of addressing this issue is to generate more than one master channel place,
as shown in Figure 4(b). This leads to an interesting problem of choosing the number
and placement of the master channel places (automatically or semi-automatically) to
optimize the visualisation of CSA-nets which is the topic of our ongoing study.
4 Master channel places with variable annotations
So far we discussed an extension to coloured master channel places which do not affect
the structure of the component acyclic nets. This has a positive effect on visualisation
and the size of the model under investigation. However, the coloured net aspect we
have introduced can be used to introduce more concise representation in the component
acyclic nets as well without losing a highly intuitive acyclic net representation of the
plain acyclic/occurrence nets. In particular, by the same mechanism we can collapse
(fold) a set of transitions into a parameterised one. An initial idea is illustrated in Fig-
ure 5, where we use the coloured net mechanism to collapse two original transitions
238 Mohammed Alahmadi
a b
q1 q2
(a) c d
q3 q4
e f
a b
q1 q2
q1 q2
(b) c d
q3 q4
q3 q4
e f
Fig. 4. A CSO-net and its version with two master channel places.
into a parameterised one. This uses typed channel place variables to achieve a desired
effect through passing variable to collapsed transition. This process will increase com-
prehension and make larger systems under investigation easier to handle.
5 Conclusions
This paper proposed an extension of the Communication Structured Acyclic Nets (CSA-
nets) based on multi-coloured tokens by introducing master channel places which col-
lapse many channel places into a single node. Such extension contributes positively to
a better visualisation while optimising the model size. The ongoing work is focused
on both the formalization of the proposed idea and the development of algorithms for
(semi)automatic construction and placement of master channel places, extending the
coloured net approach to the component acyclic nets without losing the intuitive ap-
peal of causality based representation they convey, and implementing the new type of
CSA -nets in the S ON C RAFT tool [5].
Master Channel Places for Communication Structured Acyclic Nets 239
b
a c
d
(a) q1 q2
e
f
b
a q1 c
d
q2
(b)
x : {q1 , q2 }
g[x]
Fig. 5. A CSA-net with an arc adjacent to the channel place annotated with a variable.
Acknowledgement
I would like to acknowledge financial support provided by University of Jeddah. Also, I
would like to thank the reviewers for their insightful comments on the submitted paper.
References
1. Talal Alharbi and Maciej Koutny. Domain name system (dns) tunnelling detection using
structured occurrence nets (sons). In Proceedings of the International Workshop on Petri Nets
and Software Engineering (PNSE 2019). Newcastle University, 2019.
2. Chris Bogen and David Dampier. Preparing for large-scale investigations with case domain
modeling. In Refereed Proceedings of the 5th Annual Digital Forensic Research Workshop,
DFRWS 2005, Astor Crowne Plaza, New Orleans, Louisiana, USA, August 17-19, 2005, 2005.
3. Derek T Hughes. Smartfiles–ict innovation in complex criminal investigations. International
Journal of Innovative Computing, 5(1), 2015.
4. Maciej Koutny and Brian Randell. Structured occurrence nets: A formalism for aiding system
failure prevention and analysis techniques. Fundam. Informaticae, 97(1-2):41–91, 2009.
240 Mohammed Alahmadi
5. Bowen Li, Maciej Koutny, and Brian Randell. Soncraft: A tool for construction, simulation
and verification of structured occurrence nets. School of Computing Science Technical Report
Series, 2016.
6. Brian Randell. Occurrence nets then and now: the path to structured occurrence nets. In
International Conference on Application and Theory of Petri Nets and Concurrency, pages
1–16. Springer, 2011.
7. Brian Randell and Maciej Koutny. Failures: Their definition, modelling and analysis. In
International Colloquium on Theoretical Aspects of Computing, pages 260–274. Springer,
2007.
8. Brian Randell and Maciej Koutny. Structured occurrence nets: Incomplete, contradictory and
uncertain failure evidence. School of Computing Science Technical Report Series, 2009.
9. Prajakta Yerpude. Predictive modelling of crime data set using data mining. International
Journal of Data Mining & Knowledge Management Process (IJDKP) Vol, 7, 2020.