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.