Modeling Frames Stefan Klikovits Joachim Denil Alexandre Muzy Rick Salay University of Geneva University of Antwerp CNRS, I3S University of Toronto Carouge, Switzerland Antwerp, Belgium Université Côte d’Azur, France Toronto, Canada Stefan.Klikovits@unige.ch Joachim.Denil@uantwerpen.be Alexandre.Muzy@cnrs.fr rsalay@cs.toronto.edu Abstract—Modeling activities such as calibration, verification We illustrate the applicability of our approach using the and validation are often executed in under-specified environ- example of a traffic light (TL) system whose documentation ments. This hinders reproducibility, reduces re-usability and is unavailable. The TL regulates oncoming vehicle traffic next generally decreases the modeling precision and quality. This paper describes a framework for the definition of model frames. to a pedestrian crossing as shown in Figure 1. Model frames capture the context an activity/model is executed in While the system itself might appear trivial at first, its and facilitate re-use, replacement, validation and verification of environment is not. Checking the model’s validity relies on models. We show the application of the frames approach onto a specific assumptions. It is necessary, for example, to state how real-world example, introduce several kinds of frames and show much data is assumed to be necessary to truthfully certify their application on this case study. the model’s correctness or whether the time of day has any I. I NTRODUCTION influence on the TL’s behaviour. Without clear specification of these assumptions, the modeling processes might not be When it comes to systems modeling, much effort is spent clearly reproducible. The need for detailed frames specifica- on vigorously describing, verifying and validating models. The tions is underlined when system models are used to compose description of these activities’ execution environment however larger systems-of-systems, e.g. when combining traffic lights lacks the required emphasis and model interactions are often to model, verify and analyse the traffic behaviour of an entire performed in under-specified environments, where execution city. contexts are only partially documented at best. This paper is structured as follows: Section II introduces Motivated by scenarios such as the selection of suitable the frames concept. Section III documents the details of the models from model libraries, the (de-)composition of models, running example. Section IV describes a number of different sound environment documentations are gaining importance. frame types and Section V formalises the relations between These scenarios require a clear definition of model’s context the frame’s components and different types of frames. Section to test the validity and suitability of the resulting compositions. VI positions our research into a broader context and Section A more concrete example is the safety certification process: VII concludes. While repeated re-certifications are possible, the process re- quires a lot of resources (effort, time, money). Using a com- Sidewalk ponent’s valid context specification, the proof of correctness can be reduced by showing that modified/replaced components have the same behaviour within equal environments and hence Road maintain their properties. Sidewalk Zeigler [1] discovered early on that each model is sur- rounded by a structure which captures how it can be interacted Figure 1. Schema of the traffic light scenario with. This notion of an experimental frame (EF) helps docu- menting the information that is necessary to execute the model II. F RAMES itself. He primarily focussed on the activity of model execution Modelling frames capture all information that is required (not to be confused with model activity) and simulation. to capture both context and modelling activity. Considering a Denil et al. [2] recently observed that a model’s frame depends system (e.g. a traffic light), the latter can be the verification on the activity that is performed and describes why different of corresponding model’s behavior or the calibration model’s activities require different frames. parameters, etc. Model activities correspond to the different This paper extends the activity-based notion of Denil et al. phases of a model’s life cycle, such as creation, validation, and introduces a clear record of the context that the process verification and optimization of a model, etc. is executed in. The definition of a generic modeling activity An activity can be composed of a set of sub-activities. Then, frame (MAF) builds a clear foundation that allows for the it is necessary to capture the execution order of these sub- specification of model activities. MAF help in the creation, activities and which data are required (inputs) and produced re-use and adaption of models as well as the model-based (outputs). For example, a TL’s calibration process consists system synthesis. of two steps: 1) system data collection and 2) parameter calculation. The latter accounts for the observed data and assumptions: Both traffic lights in the system are connected produces calibrated parameter values. to the same controller and always show the same phase. Alternatively, an activity can be atomic, which states that Apart from the equality in the behaviour of the two traffic the developer chose to not further split it. This applies for lights, we also assume that there are only three phases (red, example to the data collection process which describes the green and yellow) that occur in the same order and that the recording of the TL’s phases and each phase’s length. Since it length of these phases is fixed (i.e. does not change under any is trivial, no further decomposition is needed. circumstances). In addition to an activity’s process, it is necessary to capture A. Creation Frame a model’s execution environment. This includes all necessary information, expressed as the objective(s), assumptions and Our first task is to create a model of the "real-life" TL constraints. In the TL scenario, the calibration process’ objec- system. To aid the creation of the model and make the process tive is to find the correct values for the phase lengths so that formally traceable, we define a model creation frame. Based the model reflects the system under study. Assumptions might on the definitions in the previous section, we identify the specify how much data is needed for the calibration process, process required to model the system and formalize the context e.g. 24 hours to verify unchanged behaviour during the night, of the model creation process, namely all assumptions and and a constraint might specify the minimum precision (e.g. constraints we choose on this process. ±0.1 sec). Since the modeling frame is a very general concept, the The concepts are visually depicted as an ontology in Figure high-level objective is stated as O1 : Create a model in order to 2. As can be seen, a frame captures the required system learn about the TL timing. Next, we try to capture assumptions and environment information. The frame itself consists of a towards the system: modeling activity (defined by inputs, outputs and a process A1 Time of day has no influence on the behaviour. description), a context (consisting itself of objectives, assump- A2 Weather has no influence on the behaviour. tions and constraints) and a set of zero or more sub-frames. A3 The sequence of phase colours is fixed. A4 The phase lengths are constant. As there are many different modeling activities, the figure We also specify constraints on our activity, namely that provides only a few examples. The “classical” activity of C1 : The model needs to have ample precision. C2 : The model modeling (model creation) corresponds to linking a system must be represented as state machine. and a model, it is displayed more prominently. We remind the reader that this list is non-exhaustive and Each modeling activity is related to a system activity. that a complete list of objectives, assumptions and constraints Depending on the action performed, a system can be either would exceed the scope of this work. analysed, i.e. the system remains unmodified (e.g. model creation) or synthesized, i.e. the system itself is changed (e.g. during model driven system calibration). In this paper we focus on system analyses. :Observe system under study Synthesis :Observation System Activity Analysis notes 1 Inputs :Conceptualise Outputs :Conceptual Environment * Process map System Modeling Activity :Model system Modeling under study Optimisation :Model Validation J represents Calibration Frame Verification ... ct era * int h J wit Sub-frames Objectives Figure 3. Modeling frame process for the traffic light as UML activity diagram Model Context Assumptions Constraints Following the definition of the context, it is necessary to Figure 2. An ontology of the frame concepts specify the process that has to be followed to perform the modeling activity. Although many formalisms are applicable, in this work the UML 2.0 Activity Diagram formalism was III. T RAFFIC L IGHT S YSTEM chosen for modeling the frame processes. Figure 3 displays the Applying the above definitions to the traffic light system process that is required to create a model and the artefacts that allows us to define various frames. To not exceed the scope of are created and used alongside. Reaching the end state means this publication, we limit ourselves to two frame descriptions the Objective has been achieved under the given assumptions (the model creation frame and the validation frame). while respecting the constraints. For clarification of the modeling processes below we first After the execution of the process (Figure 3) in the given provide some additional information about the system and its context, the finished model of the system is shown in Figure 4. It displays the order of colours and contains parameters for A3 Simulation speed does not influence measurements. the phase transition time parameters Tr , Tg , and Ty . C1 Precision of time measurements has to be in seconds or finer. after(Tr ) C2 The output of the simulation and data collection are Red Green (colour - time) tuples. after(Ty ) after(Tg ) Contexts can be written directly to the diagram, e.g. using UML notes. To increase the diagram’s legibility, we decided Yellow against their use in the figures here. As each subtask in the process is defined by its own frame, Figure 4. The state automaton of the traffic light each step should specify its own context. For spatial reasons we will not provide descriptions for each subtask, as the contexts are subsets of the validation frame’s context. B. Validation Frame The validation frame formalises the validation activity. IV. F RAME T YPES Within the frame (a subset of) the modeling frame’s assump- When comparing the traffic light scenario to other case tions are tested for correctness. If the assumptions hold, the studies it becomes evident that certain activities and frames model can be seen as valid with regards to the properties under tend to reoccur. This means that while adjusted to each consideration. individual scenario, the basic process concepts reoccur. In the The validation frame’s process is split into several subtasks following we provide a (nonexhaustive) list of frames that that can be executed in parallel. Each subtask has its own are essential for many projects and hence worth of study. We context and process defined in a separate frame. Figure 5 remind the reader that the presented frames are blueprints and displays the process defined to validate two assumptions of need to be adapted to each new situation. the modeling frame above. A. High-level Frames Next to the model creation and validation frames described above, the following non-exhaustive list of high-level frames has been discovered. Each of these activities consists of several sub-activities. Due to spatial constraints, we do not describe :Data :Simulation collection the processes in detail, but restrict ourselves to the list of subtasks. :Simulation :Observation Calibration frame: Calibration frames modify parameter data data values so that the model has close similarity to the real system. :Compare :Compare The steps involved in this activity are system data collection, sequences durations data analysis, and parameter calculation. Verification frame: A verification frame’s purpose is :Comparison :Comparison metric metric the review of the model’s correctness in terms of meeting the requirements, i.e. that the model can fulfil its purpose :Assess and produce the required information. In the TL scenario a verification frame could test whether the model’s precision is :Properties satisfied as high as specified. The verification frame’s sub-processes are model simulation, data collection, data comparison, and result assessment. Figure 5. Validation frame process for the traffic light as UML activity diagram Optimization frame: The optimization frame is responsi- ble for adapting the model’s parameters in order to improve The frame tests assumptions A3 and A4 , namely that the the model. The improvement itself can be of different kinds sequences of the light phases are set to Red → Green → Yellow (i.e. better execution performance, higher prediction precision, → Red . . . (Compare sequence) and that the transition etc.). The process itself is a loop, where the model’s param- times Tr , Tg , and Ty are constant (Compare durations). eters are iteratively changed, the model is executed and the A part of the context of the validation process is given as results analysed until the execution reaches the predefined follows: quality or a timeout. Sub-steps include parameter setting, O1 Assert that colour sequence is fixed. model execution, data comparison and result assessment. O2 Assert that light transition times are constant. Experimentation frame: Experimentation is the task of A1 48 hours of data gathering are sufficient. executing a model to test hypotheses, draw conclusions or A2 The system runs in standard (automatic) mode (i.e. it is gather data for other purposes. It is important to capture not remote influenced). the goals of the execution, as all activities (model setup, measurement setup, data gathering, data analysis) have to be to perform the activity, the context the activity is performed in, adapted towards these goals. and a (potentially empty) set of frames defining sub-activities: B. Basic Frames F rame = hActivity, Context, F rame∗ i The frames above clearly show that some subframes occur Definition 2 (Activity). Given a frame F , we define an activity repeatedly. One prominent example is the task of data col- act as follows: lection, which is required in almost every activity. While each instance of this activity might differ due to different data being Activity = hInputs, Outputs, P rocessi gathered, the base concept remains the same. In this section will describe three examples of such base Activity consists of the detailed information about Inputs, frames. They are building blocks of more complex (high- Outputs and the Process itself. The P rocess defines the order level) activities and reoccur repeatedly. Base frames are not in which the individual tasks of the activity are performed in necessarily atomic, but often on a lower level than the frames and the coordination of the tasks inputs and outputs. in the previous section. Definition 3 (Context). The context formalises the environ- Model execution frame: Execution means that a model ment an activity is performed in. It captures goals, expectations is brought into active state using a setup, whose exact process and restrictions in the form of Objectives, Assumptions and depends on the frame’s objective. Subsequently the model is Constraints. run using specific inputs, while at the same time the model’s output is being recorded. As this frame is very generic, a clear Context = hObjectives, Assumptions, Constraintsi context definition is paramount. Data collection frame: Data collection is the activity of Objectives: represent the set of properties that should be observing the system and recording information. Specifically, satisfied after the activity execution. the subtasks include the choice of data being collected (data Assumptions: is the set of preconditions in which the collection specification) and the setup of the measurement activity will lead to the objectives being satisfied. structures (measurement setup). Next, during the system ob- Constraints: is the set of properties that have to be upheld servation phase the raw data is collected and subsequently during the execution. corrected, cleaned and adapted to correct format (data adap- Definition 4 (F rame∗ ). The set of frames declared within a tation). frame represents the sub-frames that define the frame activity’s Data comparison frame: Data comparison is a task that type. If the set of frames is empty, then the activity is atomic, usually follows a data collection or model execution step. meaning there are no finer-grained sub-tasks. Otherwise the Within this frame two or more records of data are examined activity is an orchestrator, implying that the activity’s process for similarities and differences. The activity consists of the defines the order in which the sub-activities are executed and data adaptation, where the data is brought into comparable which data is passed between them. format, the actual data comparison itself and the assessment Formally, the type of the activity is defined as follows: of the comparison results. Within this frame it is important to clearly specify the comparison strategy and assessment method ( as constraints and the success criteria as objectives. atomic, iff F rame∗ = {} type(Activity) = orchestrator, otherwise V. F ORMALIZING F RAMES Above we have given the intuition and examples of frames. It is to be mentioned that virtually all activities can be In this section, we propose first steps toward a formalization divided into more finer-grained sub-processes and it is not of frames. The objective of the formalization is to provide possible to provide a general definition of a “good” granu- a basis for tasks such as reasoning about modeling activity larity. Factors that influence this choice include the activity re-use, composition and consistency. executor’s domain familiarity, the complexity of the task, etc. We suggest to choose a granularity that is detailed enough to A. Frame Definitions be non-ambiguous, but does not contain redundant (obvious) Having established a generic relation between the individual information. frame components, this section will provide formal definitions of the individual concepts. B. Frame Integrity Constraints First, the specification of a modeling frame (or simply: As defined, a frame’s objectives are captured within the frame) is provided. context together with assumptions and constraints. Hence, the objectives’ fulfilment depends on a frame’s activity, assump- Definition 1 (Modeling Frame). Assuming a model m of a tions and constraints. system which is surrounded by an environment, and an activity act that is a modeling activity performed on m, we define a Definition 5 (Frame Objective Fulfilments). Let F be a frame modeling frame to consist of all process information required consisting of an activity act and a context hO, A, Ci. The execution of the activity with the right assumptions and good Definition 8 (Top-Down Frame Refinement). Let F be a frame constraints leads to the fulfilment of the frame’s objectives. with activity act and context hO, A, Ci. The process act is ^ ^ ^ split into several steps, defined by the frames F10 , . . . , Fn0 . We F.A ∧ F.C ∧ F.act ⇒ F.O demand that that for each child frame all assumptions are where F.act = T rue iff the activity is completed. consistent with the parent frame assumptions. We require the same for constraints. This also implies that if the frame objectives are not ^ ^ satisfied, then the frame definition itself has to be changed ∀Fi0 : F.A ⇒ Fi0 .A (i.e. the activity and/or the context). ^ ^ In fact, constraints can be seen as refinements of activity ∀Fi0 : F.C ⇒ Fi0 .C objectives and a constraint’s satisfaction as an activity’s ob- For the bottom-up composition another viewpoint might jective. Hence, we define a constraint to be a refinement of an be more applicable. Since the new high-level activity will objective. be composed of several existing frames, the assumptions and Definition 6 (Objective refinement). Let F be a frame con- constraints of the new activity’s context are a union of the sisting of an activity act and a context hO, A, Ci. Let F.c be child frame’s assumptions and constraints. a constraint in the set of constraints C (c ∈ C) and F.o an Definition 9 (Bottom-Up Frame Composition). Let F be a objective in the set of objectives O (o ∈ O). We define c to frame with activity act and context hO, A, Ci to be composed be a refinement of a more coarse objective o. of several frames F10 , . . . , Fn0 . We require that the assumptions F.c ≤ F.o and constraints of F are the union of the constraints of the subframes Fi0 (i ∈ {1, . . . , n}) where x ≤ y denotes that x is weaker than or equal to y. ! ! n n This further leads to the conclusion that an activity has to [ [ F.A = Fi0 .A , F.C = Fi0 .C satisfy all constraints, otherwise an unsatisfied constraint c i=1 i=1 implies a failed objective o and the set of objectives O being non-fulfilled. In case an assumption/constraint is defined in multiple ^ subframes, the weakest assumption/constraint is chosen for the ¬F.c ⇒ ¬F.o ⇒ ¬ F.O parent frame. One such an objective refinement is presented in the TL case There exist several other composition and consistency re- study. The objective of the modeling frame is to learn about lationships between frames (e.g. the sequential composition). the traffic light timing. This objective leads to the constraint: Their description would however, exceed the bounds of this the measuring device has to have ample precision. Failing the publication and is therefore left out. constraint implies failure of the objective. VI. R ELATED W ORK A satisfaction of a constraint c through an activity act is The idea of framing a model with extra information about defined as follows: its context has been proposed by Zeigler [1]. He defined Definition 7 (Constraint satisfaction). Given a frame F con- an experimental frame as the conditions under which the sisting of an activity act and a context hO, A, Ci, act has to system is observed and experimented with. Zeigler defines satisfy each constraint c ∈ C. an operational view on this experimental frame with three components: (a) a generator that models that allowable system ∀c ∈ C : F.act ` F.c inputs to the model, (b) a transducer to observe and analyse where ` denotes satisfaction. the output of the model and (c) the acceptor to decide on the validity of the model. Rozenblit created an implementation C. Parent - Child Frame Relationship of the experimental frame in [3]. His implementation mends We demand consistency between parent and child frames. some of the gaps that the theoretical framework left open, Depending on whether composition or decomposition is per- such as initial conditions. Zeigler’s approach has been used formed, a different view points might be useful. The first one is in several works by Ören, where he studies the acceptability of particular interest for the top-down refinement of activities. of simulations [4]. Muzy and Traore extend the work of Such frame decomposition, where one frame’s (the parent’s) Zeigler by formalising the frame and providing a specification process is replaced by several sub-frames (child frames). We hierarchy [5]. Finally, our work is a generalisation of the demand that a parent frame’s context hO, A, Ci has to be work presented in [2] to different phases in the engineering or reflected within the the child frames. scientific process. There is a direct link between the contexts of the child Re-use of components in (component-based) software en- frames and their parent frames, namely that the concepts gineering is closely related to our contribution. One such have to be reflected within the sub-frames. This means that contribution for re-use is contract-based design. Contracts for a frame’s assumptions need to remain valid within the child software components by Meyer [6] structure the properties of frames. a component into a set of pre- and post-conditions, similar to frame assumptions and constraints. The Eiffel programming [4] T. I. Ören, “Concepts and criteria to assess acceptability of simulation language for example has Require and Ensure clauses to studies: A frame of reference,” Communications of the ACM, vol. 24, no. 4, pp. 180–189, 1981. express these conditions. Contract-based approaches for cyber- [5] M. K. Traoré and A. Muzy, “Capturing the dual relationship between physical systems typically use the terminology of assumptions simulation models and their context,” Simulation Modelling Practice and guarantees. Under the assumed conditions, the component and Theory, vol. 14, no. 2, pp. 126–142, 2006. [Online]. Available: http://dx.doi.org/10.1016/j.simpat.2005.03.002 promises to fulfil the guaranteed properties. Damm et al. [7] [6] B. Meyer, “Applying’design by contract’,” Computer, vol. 25, no. 10, pp. introduce the notion of Rich Components. Rich components 40–51, 1992. extend model components such that: (a) they cover all the [7] W. Damm, A. Votintseva, A. Metzner, B. Josko, T. Peikenkamp, and E. Böde, “Boosting re-use of embedded automotive applications through specifications of the involved viewpoints, (b) they contain a rich components,” Proceedings of Foundations of Interface Technologies, set of assumptions and guarantees with respect to the context vol. 2005, 2005. of the component, and (c) they provide classifiers to the [8] L. Benvenuti, A. Ferrari, L. Mangeruca, E. Mazzi, R. Passerone, and C. Sofronis, “A contract-based formalism for the specification of hetero- assumptions. Heterogeneous rich components extend these geneous systems,” in Specification, Verification and Design Languages, rich components to support the integration of heterogeneous 2008. FDL 2008. Forum on. IEEE, 2008, pp. 142–147. viewpoints on a system with different semantics originating [9] A. Benveniste, B. Caillaud, D. Nickovic, R. Passerone, J.-B. Raclet, P. Reinkemeier, A. Sangiovanni-Vincentelli, W. Damm, T. Henzinger, from multiple design layers and tools [8]. Benveniste et and K. G. Larsen, “Contracts for System Design,” INRIA, Research al. describe the mathematical foundations of three contract Report RR-8147, Nov. 2012. [Online]. Available: https://hal.inria.fr/ operators: refinement, composition and conjunction [9]. hal-00757488 VII. C ONCLUSION AND F UTURE W ORK In this paper we introduce a structured framework for the definition of modeling activities and their execution contexts, called frames. These frames not only specify the process that has to be applied, but also clearly capture the activity’s objectives, assumptions and constraints. Such a vigorous def- inition facilitates the reproducibility and modeling activities and validation, re-use and composition of the model itself. The paper identifies several generic parametrisable frame types. These frames can be used for various modeling sit- uations which require clear context definitions, in particular model validation and verification. In future we plan to extend our work into several directions. First, we aim to extend our research of common basic frames, frame types and the formalisations of the frame relations. Second, we intend to investigate how frames can support the development of safety cases and facilitate evidence reuse as part of a safety certification process. Next, we aim to facilitate the usage of frames by providing a domain-specific language and tool-support for the specification of frames, to support the automatic verification and validation of context and process relations. Lastly, we want to apply the framework on an industrial use case in order to verify its usability. This would further give us the opportunity to discover best practices and frame patterns which facilitate frame usability. Acknowledgements: We thank the organizers of the Com- puter Automated Multi-Paradigm Modelling (CAMPAM) 2017 workshop for providing a place where this research started. We also express our gratitude to Mamadou Traoré for his inputs and insights during CAMPAM 2017. R EFERENCES [1] B. P. Zeigler, Multifaceted Modelling and Discrete Event Simulation. London: Academic Press, 1984. [2] J. Denil, S. Klikovits, P. J. Mosterman, A. Vallecillo, and H. Vangheluwe, “The experiment model and validity frame in M&S,” Proceedings of the Symposium on Theory of Modelling and Simulation, 2017. [3] J. W. Rozenblit, “Exp—a software tool for experimental frame specifica- tion in discrete event modelling and simulation,” in Proceedings of the Summer Computer Simulation Conference, 1984, pp. 967–971.