Repositorio Institucional de Documentos

2013 52 Ricardo Julio Rodríguez Fernández Perfomance Analysis and Resource Optimisation of Critical Systems Modelled by Petri Nets Departamento Director/es Informática e Ingeniería de Sistemas Merseguer Hernáiz, José Javier Júlvez Bueno, Jorge Emilio Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Ricardo Julio Rodríguez Fernández PERFOMANCE ANALYSIS AND RESOURCE OPTIMISATION OF CRITICAL SYSTEMS MODELLED BY PETRI NETS Director/es Informática e Ingeniería de Sistemas Merseguer Hernáiz, José Javier Júlvez Bueno, Jorge Emilio Tesis Doctoral Autor 2013 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Performance Analysis and Resource Optimisation of Critical Systems Modelled by Petri Nets Ricardo Julio Rodr´ıguez Fern´andez Ph.D. DISSERTATION Dpto. de Inform´atica e Ingenier´ıa de Sistemas Universidad de Zaragoza Advisors: Dr. Jorge Emilio J´ulvez Bueno Dr. Jos´e Javier Merseguer Hern´aiz Junio de 2013 A Mar´ıa y su paciencia infinita. ¸ Mi locura es sagrada. No me toquen. (Iliana Godoy) Quod quisque possit, nisi tentando nesciat. (No se puede saber de lo que cada uno es capaz si no se pone a prueba) (Publilius Syrus) Agradecimientos Mis primeras palabras de agradecimiento son para Jorge J´ulvez y Jos´e Merseguer, grandes profesionales – muy grandes – y mejores personas, que me han sabido guiar a buen puerto en todo momento en esta carrera de fondo llena de desniveles. Me han dejado mi libertad de cr´ıtica, pensamiento y acci´on, siempre aderezada con unos toques de advertencia cuando me descarriaba demasiado del objetivo. Gran parte de este trabajo es gracias a ellos, as´ı que chicos, una vez m´as, muchas gracias! No me puedo olvidar de Javi, mi padrino cient´ıfico, quien tambi´en met´ıa en vereda a la cabra cuando tiraba demasiado para el monte, y con quien he disfrutado buenos momentos tanto profesionales como personales. Tampoco al resto de gente – y algunos antiguos compa˜neros de promoci´on – con quien he tenido el gusto de compartir laboratorio durante este per´ıodo (Irina, Est´ıbaliz, Jorge, Roberto, Guillermo, Juan. . . ), sobremesas y discusiones bizarras (Javier, Jorge, Diego, Nacho, Roberto), compartido horas de trabajo en com´un, tanto en Espa˜na como en otros lugares (Simona, Rafa, Catia), y, compartido tambi´en, sobre todo, muchas horas de cantina y otros menesteres (Ritu, Jes´us, Diego). Tampoco puedo olvidarme de esas grandes personas y buenos amigos que he tenido el gusto de conocer y trabajar con ellos durante mis estancias en Cardiff, como Omer, Yaser, Ioan o Raquel, con quienes he compartido muy buenos momentos que han hecho que me sintiera como en casa. Por ´ultimo, a mi familia (gracias por apoyarme siempre, dejarme estudiar lo que quise, y pagarme una educaci´on en una universidad p´ublica), amigos y ex-compa˜neros y amigos de promoci´on (Fergus, Jacobo), quienes han tenido el gusto – o la desgracia, seg´un el d´ıa. . . – de soportar mis idas y venidas, mis cambios de humor, mis frustaciones y alegr´ıas, durante este largo per´ıodo. En resumen, a todos aquellos con los que en alg´un momento me he cruzado durante este periplo de cuatro a˜nos, que hoy llega a su final, y que me han tenido que sufrir de un modo u otro. Gracias. CONTENTS CONTENTS III Applications 101 8 Case Study: a Secure Database System 103 8.1 System Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 8.2 Experiments and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 8.2.1 Performance Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 108 8.2.2 Resource Optimisation Maximising Throughput . . . . . . . . . . . . 112 8.2.3 Resource Optimisation Minimising Cost while Adding FT Techniques 113 8.3 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 9 Case Study: an E-Commerce System 117 9.1 System Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 9.2 Experiments and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9.2.1 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9.2.2 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 9.3 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 10 Performance Analysis of Data-Intensive Workflows 127 10.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 10.2 Model Transformation: From a DAG to a SMG . . . . . . . . . . . . . . . . 129 10.3 A Metric for Quantifying the Effectiveness of Throttled Data Transfers . . . 129 10.3.1 Metric Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 10.4 An Automating Data-Throttling Analysis Method . . . . . . . . . . . . . . 132 10.4.1 Experiments and Discussion . . . . . . . . . . . . . . . . . . . . . . . 136 10.4.2 Impact on the Workflow Makespan . . . . . . . . . . . . . . . . . . . 138 10.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 IV Tool Support 145 11 The PeabraiN Tool: A PIPE Extension 147 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 11.2 PeabraiN Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 11.2.1 Implemented Features . . . . . . . . . . . . . . . . . . . . . . . . . . 148 11.2.2 Framework Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 11.2.3 Example of Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 11.2.4 Tool Availability and Installation Requirements . . . . . . . . . . . . 153 11.3 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 iii CONTENTS CONTENTS V Conclusions 155 12 Conclusions and Open Problems 157 12.1 Thesis Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 12.2 Main Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 12.3 Future Work and Open Problems . . . . . . . . . . . . . . . . . . . . . . . . 160 Relevant Publications Related to this Dissertation 163 Bibliography 165 iv List of Figures 2.1 A UML Use Case (UML-UC) diagram of a payment system. . . . . . . . . . 19 2.2 A UML Deployment Diagram (UML-DD) of a secure database system. . . . 20 2.3 A UML State-Machine Diagram (UML-SM) of a computer keyboard. . . . . 21 2.4 A UML Sequence Diagram (UML-SD) of a financial reporting system. . . . 22 2.5 Phases on a FT technique (adapted from [Avizienis et al., 2004]). . . . . . . 23 3.1 (a) SecAM profile and library, (b) SecAM UML extensions (subpackages). . . 30 3.2 The SecAM::Resilience package. . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 A UML-State Machine diagram with SecAM::Resilience annotations. . . . 33 3.4 The SecAM::Cryptographic package. . . . . . . . . . . . . . . . . . . . . . 34 3.5 An encrypted communication (symmetric, hardware, and 256 bits). . . . . . 35 3.6 The SecAM::SecurityMechanisms package. . . . . . . . . . . . . . . . . . . 36 3.7 A deployment scenario composed by a DMZ and different bastions. . . . . . 38 3.8 The SecAM::AccessControl package. . . . . . . . . . . . . . . . . . . . . . 39 3.9 A UML-SD with access control policy. . . . . . . . . . . . . . . . . . . . . . 40 4.1 Transformation rule T R of a transition tfsubject to fail (faulty transition). 44 4.2 Integration between a PN-based system model and a PN-based FTT. . . . . 45 4.3 PN-based model of Error Detection and faulty activity inside the system. . 46 4.4 PN-based models of Recovery model: (a) and (b) isolation & reconfiguration. 48 4.5 Petri net representation of a packet-routing algorithm. . . . . . . . . . . . . 50 4.6 Petri net representation of a packet-routing algorithm with a FT technique. 51 4.7 Schedule time-line showing activation of reactive and proactive recoveries . 54 4.8 Scheduler UML state-machine diagram. . . . . . . . . . . . . . . . . . . . . 55 4.9 PRR controller UML state-machine diagram. . . . . . . . . . . . . . . . . . 56 4.10 UML Sequence Diagram of the SwitchOverFailing Fault-Tolerant Technique. 58 4.11 UML Sequence Diagram of the Ping&Restore Fault-Tolerant Technique. . . 60 5.1 A process to estimate the system performance while adding SMs and FTTs. 65 6.1 Example MG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 v LIST OF FIGURES LIST OF FIGURES 6.2 Another MG example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.3 Throughput of graph s1488............................ 82 6.4 Example of a supermarket system. . . . . . . . . . . . . . . . . . . . . . . . 86 7.1 Results of initial marking with respect to probability of error. . . . . . . . . 98 8.1 SDBS Deployment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.2 SDBS Update Customer’s Data scenario. . . . . . . . . . . . . . . . . . . . 105 8.3 PN of the SDBS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 8.4 Throughput of the SDBS with variable number of users. . . . . . . . . . . . 110 8.5 Different resources configurations and their associated cost. . . . . . . . . . 112 9.1 ECS Performance-Annotated Application Model. . . . . . . . . . . . . . . . 119 9.2 ECS SMs-FTTs-Enabled Application Model. . . . . . . . . . . . . . . . . . 122 9.3 ECS Performance Analysis Results. . . . . . . . . . . . . . . . . . . . . . . . 124 10.1 (a) Workflow tasks and (b) its transformation to PN. . . . . . . . . . . . . . 129 10.2 Automated Data-Throttling Analysis Flowchart. . . . . . . . . . . . . . . . 133 10.3 A workflow with 6 task and multiple inter-tasks dependencies. . . . . . . . . 134 10.4 PN-based abstract workflow with explicit data-transfer transitions. . . . . . 136 10.5 Makespan of workflow depicted in 10.3 with different network topologies. . 137 10.6 Montage workflow for 5 input files. . . . . . . . . . . . . . . . . . . . . . . . 139 10.7 Buffer waiting time in (a) task mImgTbl and (b) mConcatFit. . . . . . . . . 142 11.1 PeabraiN software architecture. . . . . . . . . . . . . . . . . . . . . . . . . . 150 11.2 Integration of PeabraiN in the PIPE tool. . . . . . . . . . . . . . . . . . . . 151 11.3 UML Sequence Diagram for executing performance estimation module. . . . 152 11.4 PeabraiN: Snapshot of execution results (resource optimisation). . . . . . . 153 vi List of Tables 3.1 Security attributes and SecAM packages in which they are covered. . . . . . 31 4.1 Valid combinations of error handling and fault handling techniques. . . . . 47 4.2 New (a) p-semiflows and (b) t-semiflows of the PN in Figure 4.6. . . . . . . 50 4.3 Visit ratios modification for different error handling techniques . . . . . . . 53 4.4 CPN initial marking, token colour definition and functions. . . . . . . . . . 57 6.1 Experiment results showing improvement of upper bound. . . . . . . . . . . 80 6.2 Graph throughput and CPU time comparative. . . . . . . . . . . . . . . . . 81 8.1 Experimental parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 8.2 Experimental results for number of requests {15,20,21,22,23 . . . 30}. . . . . 109 9.1 Experimental parameters: system resources and number of instances. . . . . 121 9.2 Experimental parameters: execution times of system actions. . . . . . . . . 121 10.1 Mean & standard deviation values of buffer waiting time for Montage. . . . 132 10.2 Metric values computed for the considered Montage workflows. . . . . . . . 132 10.3 Makespan for Montage workflow with 5 input files. . . . . . . . . . . . . . . 138 10.4 Buffer waiting time of Montage tasks under different configurations. . . . . 140 vii List of Algorithms 1 The regrowing strategy algorithm. . . . . . . . . . . . . . . . . . . . . . . . . 77 2 The iterative strategy algorithm for computing upper throughput bounds. . . 85 3 The resource optimisation heuristics. . . . . . . . . . . . . . . . . . . . . . . . 95 4 An algorithm to compute initial marking maintaining a given throughput. . 97 ix Chapter 1 Introduction and State of the Art 1.1 Motivation Complex, large scale and distributed systems are required to fulfil their mission despite the presence of security issues. Today, one of the main challenges in the software engineering area is to devise methods for the development of such critical systems. The system requirements, also called properties, are expressed in the initial phases when developing a system. A system requirement defines how a system should be (functional) or should perform (non-functional). Functional requirements are devoted to calculations, data processing or any other functionality that defines what the system is supposed to behave. On the contrary, nonfunctional requirements (or non-functional properties, NFPs) involve how the system is supposed to perform its activities (e.g., how many customers per unit of time can be attended by a service, how many bytes per second can be transferred by a network device, or how many bytes per unit of time can be ciphered with a cipher algorithm). Examples of NFPs are performance, dependability or security of a system. Several works in the literature [Devanbu and Stubblebine, 2000, Wing, 2003, McGraw, 2004, Barnum and McGraw, 2005, Khan and Zulkernine, 2008, Mouratidis and Giorgini, 2008] remark that security has not been conceived as an integral part of the development process and claim for it. Nowadays, most of the systems are deployed without taking into account security. Thus, after a security disaster the systems usually need to be redesigned, accounting for security from the beginning. This “fix it later” approach can lead to severe consequences, such as the huge cost of reimplementing or redeploying all the system, as well as economic losses [Randimbivololona, 2001] due to the unavailability of services or the disclosure of personal customers data (as the case of Sony PlayStation Network or RSA company breach in 2011). Thus, the new generation of development methods have to face challenges never intended before, where security plays a main role. In our opinion, these methods need to address at 1 Section 1.1 1. Introduction and State of the Art least the following issues to start considering the menaces to security successfully: 1. They should provide an integrated approach. By integrated we mean the need of considering security as a first-class citizen in all the stages of the software and systems life-cycle: Analysis, Design, Implementation, Testing, Deployment and Maintenance. So security needs to be integrated in the life-cycle of systems as functional properties (FP) are today. As we mentioned before, many works in the literature [Devanbu and Stubblebine, 2000,Wing, 2003,McGraw, 2004, Khan and Zulkernine, 2008,Mouratidis and Giorgini, 2008] claim for the necessity for this integration. 2. The methods should promote the analysis of system security even before the deployment of the system. This challenge links with the previous one since the analysis of security is then just considered as a new stage inside the life-cycle. For instance, as it was pointed out in [Randimbivololona, 2001], the cost of verification in the avionics system domain is the 50% of overall costs when the system is already deployed. This trend should change when analysis is really coupled with the development, thus saving costs. 3. The methods should promote a unified view of the security issues. Nowadays, we realise that the different – and sometimes orthogonal – aspects of security (e.g., access control or cryptography) are dealt by specialised communities that unfortunately do not share goals nor even vocabulary. This fact impairs communication and the possibility to integrate advances from different communities. 4. These methods should not be oblivious to the current software engineering (SE) techniques. For example, the Model-Driven Development (MDD) paradigm can play an important role in the generation of models for the analysis of security in software systems. Moreover, large scale and distributed systems are deployed in heterogeneous environments where they are subject to suffer security issues, such as intrusion attempts, confidential data theft or other type of attacks. For example, a Denial-of-Service (DoS) attack [Garber, 2000] sends multiple requests to a server with the intention of consuming its resources and, in last term, bringing it down. These harmful actions clearly have an impact on the functionality of servers that might not be able to attend all incoming requests, and finally might cut their services off by saturation. Relevant efforts of software designers are devoted to devise the security strategies suitable to protect information and computational systems against not authorised accesses. Indeed, when designing critical systems it is fundamental to study the attacks that may occur and plan how to react to them. The occurrence of attacks in software systems leads software designers to introduce different Fault-Tolerant Techniques (FTTs), such as recov2 1. Introduction and State of the Art Section 1.2 FT techniques and other security mechanisms are incorporated. Recall that FT systems (i.e., systems that incorporate FT techniques) can be naturally modelled as Discrete Event Systems (DES) where resources are shared, also called Resource Allocation Systems (RAS) [Colom, 2003]. In this dissertation, we focus on FT systems using shared resources modelled as Petri nets (PNs) – more precisely, as process Petri nets [Tricas, 2003]. Performance analysis. Performance estimation using PNs is a topic which has been broadly studied. Some works are concerned to the exact computation of analytical measures of the performance [Ajmone Marsan et al., 1995], while others overcome the state explosion problem providing performance bounds [Ramchandani, 1974,Chiola et al., 1993, Campos et al., 1992,Liu, 1995]. The use of performance bounds, on which our approach is based, avoids the necessity of calculating the whole state space. The advantage of using performance bound computation is the reduced computing time, but its drawback is the difficulty to assess how accurate the computed bound is with respect to the real system performance. One of the first works on performance bounds computation is [Ramchandani, 1974], where strongly connected Marked Graphs (MGs) with deterministic timing are considered, and the reachability of the computation bound is proved. Some other works that compute performance bounds use linear programming techniques [Chiola et al., 1993, Campos et al., 1992], in the same way that our approach. These bounds are frequently calculated by using the first order moment (i.e., the mean) of the distributions associated to the firing delay. In [Liu, 1995], the second order moment is used to obtain a sharper (i.e., more accurate) performance bound. Other works provide bounds for queueing systems instead of PN models like our approach does, e.g., [Haddad et al., 2005, Casale et al., 2008, Osogami and Raymond, 2010]. Haddad et al. give in [Haddad et al., 2005] space complexity upper and lower bounds for Stochastic Petri nets with product-form solution. In [Casale et al., 2008], Casale et al. propose performance upper and lower bounds for closed queueing networks with general independent and non-renewal services. They use linear programming techniques on the queue activity probabilities. Osogami and Raymond provide in [Osogami and Raymond, 2010] upper and lower bounds on the tail distribution of the transient waiting time for a general independent services queue. They use the two first moments of the service time and interarrival time, and solve it through semidefinite programming (SDP), a convex optimisation technique used for optimisation of complex systems. On the contrary, our approach introduced in Chapter 6 uses first order moment and linear programming techniques. This thesis proposes in Chapter 6 an improvement of upper bound computation for the particular case of MGs and of process Petri nets by using regrowing techniques (that is, by adding more components to the initial bottleneck of the net). We have also applied our approach for getting improved performance bound to the domain of scientific workflow, as it is summarised in Chapter 10. Petri nets 9 Section 1.2 1. Introduction and State of the Art and their extensions have been widely used for the specification, analysis and implementation of scientific workflows [van der Aalst and van Hee, 2004] (e.g., GWorkflowDL [Pellegrini et al., 2008, Vossberg et al., 2008], Grid-Flow [Guan et al., 2006] or FlowManager [Aversano et al., 2002]). In Chapter 10, we propose the use of ordinary PNs for deriving performance models of pure graph-based workflows. An analysis of the overhead for scientific workflows in Grid environments was given by Nerieri et al. in [Nerieri et al., 2006]. The analysis includes both load imbalance and data movement, with these being identified as the most significant sources of overhead. As discussed in this paper, Park & Humphrey [Park and Humphrey, 2008] already analysed the problem of load imbalance and data throttling for scientific workflows. They proposed a process envelope based framework for throttling data transfers. Nonetheless, they do not provide any analysis method in order to automatically obtain such data-throttling values. The proposal that we describe in Chapter 10 gives a method that can automatically derive (sub-optimal) values for them. Lastly, it is worth mentioning the work in [Aalst et al., 2002], where a Petri net structural analysis is undertaken for business workflows. A specific class of Petri nets, WF-nets, is used and tailored towards workflow analysis. WF-nets can model workflows with different kind of control operations such as sequence, choice, synchroniser, fork or merge. The types of structural analysis that can be undertaken includes correctness, deadlock analysis or liveness. Resource optimisation analysis. Finally, resource optimisation and its usage have been already studied for workflow Petri nets (WF-nets) [Li et al., 2004] or some variants [Wang and Zeng, 2008,Hee et al., 2001,Chen et al., 2008]. The underlying PN model of WF-nets are free choice nets (FCNs). However, the kind of systems we are considering cannot be modelled through FCNs: in the systems we consider, it may exist conflicts in the resources acquirement synchronisation, which is not allowed in FCNs. Li et al. propose in [Li et al., 2004] an approach to estimate the resource availability by using Continuous Time Markov Chains (CTMCs) and compute the turnaround time (i.e., the shortest response time) by performing reduction operations on the original WF-net. This performance analysis has an exponential complexity in the worst case, whilst our approach has a polynomial complexity due to the use of linear programming (LP) techniques. Resource usage could be computed in our approach by calculating the average marking of resource places in the PN system. Wang and Zeng provide in [Wang and Zeng, 2008] a method for computing the best implementation case for a workflow represented by a PN model, based on the reachability graph. Such a method, however, can suffer scalability problems if the workflow size is large. Van Hee et al. give in [Hee et al., 2001] an algorithm to compute optimal resource allocation in stochastic WF-nets. Such an algorithm suffers from scalability problems because its complexity depends on the number of resources. On the contrary, our approach only depends on the net structure, no matters the number of resources in the system. Therefore, for large systems with great number of resources our approach is 10 1. Introduction and State of the Art Section 1.3 more tractable than the one in [Hee et al., 2001]. Chen et al. propose in [Chen et al., 2008] a new PN model, called Resource Assignment Petri Net (RAPN), to define how resources are shared and assigned among different and concurrent project activities. The computation of the execution project time considers deterministic timing and, unlike our approach, such a new PN model is not able to model activities that utilise and release the same resource intermittently. This thesis proposes, in Chapter 7, several approaches to minimise the cost of compensation needed for maintaining a given throughput in a FT system. Another important issue related to resource sharing is deadlock prevention. The common use of system resources in concurrent systems may lead to deadlock problems, i.e., a process waits for the evolution of other process/es, while the latter is/are also waiting for the former to evolve. In order to deal with such problems, there exist deadlock prevention or avoidance policies which may be applied for assuring the liveness property and therefore to avoid deadlocks [Colom et al., 1990,Tricas et al., 2000,Ezpeleta and Valk, 2006,Wu et al., 2008, Lopez-Grao and Colom, 2011,Hu et al., 2012,Li et al., 2012]. 1.3 Outline The balance of this dissertation is as follows. Chapter 2 introduces the preliminary concepts needed to follow the rest of the dissertation, such as Petri nets (PNs), UML diagrams and Fault Tolerance. The rest of this dissertation has been divided in five main parts: Design of Critical Systems,Performance Analysis,Applications,Tool Support and Conclusions. The first part of this dissertation is composed of Chapters 3 to 5 and it is mainly devoted to the contributions related to the specification of security and the design of critical systems. Namely, Chapter 3 introduces a UML profile focused on security, called SecAM, which has served for expressing security properties into UML designs in several publications. Then, Chapter 4 introduces a set of Fault-Tolerant (FT) techniques, expressed in UML models and directly into PN models, which allows to make easier the addition of these FT techniques into software designs. Lastly, Chapter 5 is devoted to performance prediction of critical systems by means of a model-based methodology which combine Fault-Tolerant Techniques (FTTs), such as recovery procedures, and/or Security Mechanisms (SMs). The second part of this dissertation is related to the contributions on performance analysis theory. Chapter 6 introduces a bunch of strategies for the upper throughput bound computation on Petri nets. Recall that we are dealing with critical systems that incorporate FT techniques to deal with any unexpected situation, and these additions may have an impact on system performance. Thus, Chapter 7 introduces a set of algorithms to compensate the throughput degradation in critical systems. The third part of this dissertation is devoted to applications of the theory introduced in previous chapters. Namely, Chapter 8 considers the design of a Secure Database System (SDBS) where the approaches presented in Chapters 6 and 7 are tested. Lastly, Chapter 10 11 Section 1.3 1. Introduction and State of the Art addresses the application of approaches presented in Chapter 6 to other scientific domain, more precisely, scientific workflows. Chapter 10 also introduces a quantitative metric for workflows, and a data-throttling strategy for improving the use of bandwidth and input buffers of workflow tasks. The forth part of this dissertation is related to tool support. Chapter 11 introduces PeabraiN, a tool developed as a side product during this dissertation that implements some of the approaches presented in Chapters 6 and 7. Finally, Chapter 12 in the fifth part summarises the major contributions of this dissertation and establishes the current open problems. 12 Chapter 2 Preliminary Concepts This chapter introduces some basic concepts that are needed to follow the rest of this dissertation. We start defining Petri nets (PNs) in the untimed and timed framework, and introducing a special class of PNs – more precisely, Process Petri net (PPN), which is a basis for our approach – and related concepts, such as upper throughput bounds. Secondly, the Unified Modelling Language (UML) is addressed by describing the semantics of the diagrams that we use in this dissertation. Lastly, the concepts related to Fault Tolerance are introduced. 2.1 Petri Nets This section introduces some basic concepts regarding the class of Petri nets (PNs) we are considering in this dissertation. Firstly, we define process Petri nets in the untimed framework. Then, timed Petri net systems are defined. In the following, the reader is assumed to be familiar with Petri nets (see [Murata, 1989] for a gentle introduction). 2.1.1 Untimed Petri Nets Definition 1 A Petri net [Murata, 1989] (PN) is a 4–tuple N=hP, T, Pre,Posti, where:  Pand Tare disjoint non-empty sets of places and transitions (|P|=n,|T|=m) and  Pre (Post) are the pre–(post–)incidence non-negative integer matrices of size |P|× |T|. The preand post-set of a node v∈P∪Tare respectively defined as •v={u∈ P∪T|(u, v)∈F}and v•={u∈P∪T|(v, u)∈F}, where F⊆(P×T)∪(T×P) is the set of directed arcs. A Petri net is said to be self-loop free if ∀p∈P, t ∈T t ∈•pimplies 13 Section 2.1 2. Preliminary Concepts t6∈ p•.Ordinary nets are Petri nets whose arcs have weight 1. The incidence matrix of a Petri net is defined as C=Post −Pre. A vector m∈Z|P| ≥0which assigns a non-negative integer to each place is called marking vector or marking. Definition 2 APetri net system, or marked Petri net S=hN,m0i, is a Petri net N with an initial marking m0. A transition t∈Tis enabled at marking mif m≥Pre(·, t), where Pre(·, t) is the column of Pre corresponding to transition t. A transition tenabled at mcan fire yielding a new marking m′=m+C(·, t) (reached marking). This is denoted by mt −→m′. A sequence of transitions σ={ti}n i=1 is a firing sequence in Sif there exists a sequence of markings such that m0t1 −→m1t2 −→m2... tn −→mn. In this case, marking mnis said to be reachable from m0by firing σ, and this is denoted by m0σ −→mn. The firing count vector σ∈Z|T| ≥0 of the firable sequence σis a vector such that σ(t) represents the number of occurrences of t∈Tin σ. If m0σ −→m, then we can write in vector form m=m0+C·σ, which is referred to as the linear (or fundamental)state equation of the net. The set of markings reachable from m0in Nis denoted as RS(N,m0) and is called the reachability set. A place p∈Pis k−bounded if ∀m∈RS(N,m0),m(p)≤k. A net system Sis kbounded if each place is k-bounded. A net system is bounded if there exists some k for which it is k-bounded. A net Nis structurally bounded if it is bounded no matter which m0is the initial marking. Two transitions t,t′are said to be in structural conflict if they share, at least, one input place, i.e., •t∩•t′6=∅. Two transitions t,t′are in equal conflict if Pre(·, t) = Pre(·, t′)6=0, where 0is a vector with all entries equal to zero. A transition tis live if, for each marking m∈RS(N,m0) there exists a marking m′ reachable from mwhere transition tis enabled. A marked Petri net Sis live when every transition is live. Hereafter, we assume that Sswe work with are live. Ap-semiflow is a non-negative integer vector y≥0such that it is a left anuller of the net’s incidence matrix, y⊤·C= 0. In the sequel, we omit the transpose symbol in the matrices and vectors for clarity. A p-semiflow implies a token conservation law independent from any firing of transitions. A t-semiflow is a non-negative integer vector x≥0such that is a right anuller of the net’s incidence matrix, C·x= 0. A p- (or t-)semiflow vis minimal when its support, kvk={i|v(i)6= 0}, is not a proper superset of the support of any other p- (or t-)semiflow, and the greatest common divisor of its elements is one. A Petri net is said to be conservative (consistent) if there exists a p-semiflow (t-semiflow) which contains all places (transitions) in its support. A Petri net is said to be strongly connected if there is a directed path joining any pair of nodes of the net structure. A state machine is a particular type of ordinary Petri nets where each transition has exactly one input arc and exactly one output arc. More formally: 14 2. Preliminary Concepts Section 2.1 Definition 3 [Murata, 1989] A state machine is a subclass of Petri nets such that ∀t∈ T, |t•|=|•t|= 1. Marked graphs (MGs) are a subclass of ordinary Petri nets that are characterised by the fact that each place has exactly one input and exactly one output arc. More formally: Definition 4 [Murata, 1989] A marked graph (MG) is an ordinary Petri net such that ∀p∈P, |•p|=|p•|= 1. In this dissertation, we deal with Petri nets that model systems where resources are shared. Examples of this kind of systems can be found in manufacturing, logistics or web services systems. In general, these systems represent real-life problems where some items are processed and require the use of different resources (which are shared) during its processing. These systems can be naturally modelled in terms of process Petri nets, a subclass of Petri net whose inner structure is a strongly connected state machine. More formally: Definition 5 [Tricas, 2003] A process Petri net (PPN) is a strongly connected self–loop free Petri net N=hP, T, Pre,Postiwhere: 1. P=P0∪PS∪PRis a partition such that P0={p0}is the process-idle place, PS6=∅, PS∩P0=∅, PS∩PR=∅,PSis the set of process-activity places and PR={r1,...,rn}, n > 0, PR∩P0=∅is the set of resources places; 2. The subnet N′=hP\PR, T, Pre,Postiis a strongly connected state machine, such that every cycle contains p0. 3. For each r∈PR, there exist a unique minimal p-semiflow associated to r,yr∈N|P|, fulfilling: kyrk∩PR={r},kyrk∩PS6=∅,kyrk∩P0=∅and yr(r) = 1. This establishes how each resource is reused, that is, they cannot be created nor destroyed. 4. PS=Sr∈PR(kyrk\{r}). Definition 5 implies that PP Ns are conservative and consistent. Intuitively, Definition 5 establishes a kind of nets where: a) there is a process using different shared resources; b) every place in the net is covered by some p-semiflow and uses at least one resource; c) the number of instances of each resource remains constant; and d) resources cannot change its type. Let N=hP, T, Pre,Postibe a PPN. A vector m0∈Z|P| ≥0is called acceptable initial marking [Tricas, 2003] of Nif: 15 Section 2.1 2. Preliminary Concepts 1) m0(p)≥1, p ∈P0; 2) m0(p) = 0,∀p∈PS; and 3) m0(r)≥yr(r),∀r∈PR, where m0(r) is the capacity, i.e., number of items, of the resource rand yris the unique minimal p-semiflow associated to r. Definition 6 Aprocess Petri net system, or marked process Petri net S=hN,m0i, is a process Petri net Nwith an acceptable initial marking m0. 2.1.2 Timed Petri Nets In order to be able to use Petri nets for systems performance evaluation, the inclusion of the notion of time must be considered. There are two ways of introducing the notion of time in Petri nets, either in places or transitions. Since transitions are representing the actions of a system, which have associated some duration, we associate such a duration to the firing delay of transitions [Ramchandani, 1974]. Besides, we consider that the firing delays of transitions follow an exponential distribution functions. A Petri net model where a set of exponential rates is considered (one for each transition in the model) is called a Stochastic Petri net (SPN) model [Florin and Natkin, 1985, Ajmone Marsan et al., 1995]. These rates characterise the probability distribution function of the transition delay, which follow an exponential distribution function and are obtained as the inverse of the mean. These rates are considered to be marking-independent, i.e., its values are constant. In this dissertation, we consider that the average service time of a transition tcan be zero, i.e., it fires in zero units of time. These transitions are called immediate transitions. Otherwise, transition tis a timed transition. The exponential transitions are graphically represented by a white box, whilst immediate transitions are black boxes. It will be assumed that all transitions in conflict are immediate. An immediate transition tin conflict will fire with probability r(t) Pt′∈Ar(t′), where Ais the set of enabled immediate transitions in conflict and r(t)∈N>0is the routing rate associated to transition t. The firing of immediate transitions consumes no time. When a timed transition becomes enabled, it fires following an exponential distribution with mean δ(t). More formally, we will consider the following timed Petri net classes: Definition 7 AStochastic Petri Net (SPN) [Florin and Natkin, 1985] system is a pair hS, δ, riwhere S=hP, T, Pre,Post,m0iis a Petri net system, δ∈R|T| ≥0is a positive real function such that δ(t)is the mean of the exponential firing time distribution associated to transition t∈Tand r∈N|T| >0is the vector of routing rates associated to transitions. Definition 8 AStochastic Marked Graph (SMG) is a Stochastic Petri net whose underlying Petri net is a Marked Graph. 16 2. Preliminary Concepts Section 2.1 Definition 9 A Stochastic Process Petri net (SPPN) system is a Stochastic Petri net system whose underlying Petri net is a Process Petri net. There exist different semantics for the firing of transitions, being infinite and finite server semantics the most frequently used. Given that infinite server semantics is more general (finite server semantics can be simulated by adding self-loop places), we will assume that the timed transitions work under infinite server semantics. The average marking vector, m, in an ergodic [Ross, 1983] Petri net system is defined as [Florin and Natkin, 1989]: m(p) = AS lim τ→∞ 1 τZτ 0 m(p)udu (2.1) where m(p)uis the marking of place pat time uand the notation = AS means equal almost surely. Similarly, the steady-state throughput, χ, in an ergodic Petri net is defined as [Florin and Natkin, 1989]: χ(t) = AS lim τ→∞ σ(t)τ τ(2.2) where σ(t)τis the firing count of transition tat time τ. By definition, all the places of a SPPN are covered by p-semiflows, and therefore it is structurally bounded. In this work, we will assume that the SPPN under study is a live and structurally bounded net with Freely Related T-semiflows (i.e., a FRTnet) [Campos and Silva, 1992]. It is known that the Markov process that describes the time evolution [Ajmone Marsan et al., 1995] of these nets is ergodic [Campos and Silva, 1992], i.e., when the observation period tends to infinite, the estimated values of average marking and steady-state throughput tend to a certain value, what implies the existence of the above limits. The vector of visit ratios expresses the relative throughput of transitions in the steady state. The visit ratio v(t) of each transition t∈Tnormalised for transition ti,vti(t), is expressed as follows: vti(t) = χ(t) χ(ti)=Γ(ti)·χ(t),∀t∈T(2.3) where Γ(ti) = 1 χ(ti)represents the average inter-firing time of transition ti. The visit ratios of two different transitions t, t′in equal conflict must be proportional to the corresponding routing rate r(t),r(t′) defining the conflict resolution condition r(t)· vti(t′) = r(t′)·vti(t). This condition can be also written in vector form as: R·vti= 0 (2.4) where Ris a matrix containing as many rows as pairs of transitions in equal conflict. 17 Section 2.2 2. Preliminary Concepts In FRT-nets, the vector of visit ratios vexclusively depends on the structure of the net and on the routing rates [Campos and Silva, 1992]. The vector of visit ratios vnormalised for transition ti,vti, can be calculated by solving the following linear system of equations [Campos and Silva, 1992]: C R·vti= 0 vti(ti) = 1 (2.5) 2.2 The Unified Modelling Language This section introduces briefly the main Unified Modelling Language (UML) diagrams that we use in this dissertation. Mainly, they are: UML Use Case (UML-UC) diagrams, UML Deployment Diagrams (UML-DD), UML State Machine (UML-SM) diagrams and UML Sequence Diagrams (UML-SD). In the following, the reader is assumed to be familiar with UML (see [OMG, 2005] for a gentle introduction). UML, standard de facto as modelling language, is a powerful language which allows to represent from architectural to behavioural aspects of the systems. The focus in UML in this dissertation is motivated by the fact that UML is well-known by the system designers and they are very familiar with its use for designing. The UML is a semi-formal language developed by the Object Management Group (OMG) to specify, visualise and document models of software and non-software systems. UML has gained widespread acceptance in the software development process for the specification of software systems based on the object-oriented paradigm. UML provides several types of diagrams which allow to capture different aspects and views of the system. A UML model of a system consists of several diagrams which represent the functionality of the system, its static structure, the dynamic behaviour of each system component and the interactions among the system components. UML defines twelve types of diagrams, divided into three main categories:  Static diagrams, which are intended to model the structure (logical and architectural) of the system. They are: class diagram,object diagram,component diagram and deployment diagram.  Behavioural diagrams, which are intended to describe system dynamics, and they are subdivided in: sequence diagram,collaboration diagram,use case diagram,statemachine diagram and activity diagram.  Diagrams to organise modules, allowing to reduce complexity of the system. There exist packages,subsystems and models. 18 Part I Design of Critical Systems 25 Chapter 3 A UML Profile for Security In this chapter we summarise the main contributions of this dissertation related to the design of a UML extension focused on security [Rodr´ıguez et al., 2010, Rodr´ıguez and Merseguer, 2010, Rodr´ıguez et al., 2012d]. This extension is performed through profiling. Briefly, a UML profile defines a set of stereotypes and tagged values that allow the expression of non-functional properties (such as performance, dependability or security), which are eventually attached to UML model elements extending its semantics. 3.1 Motivation As we claimed in Section 1.1, there is a need to express security as a Non-Functional Property (NFP) into the design of systems. This need is even more important when the system is deployed in a harmful environment, where the system may be the victim of persistent and targeted attacks. The approach we present in this chapter encompasses all the challenges that we identify to be addressed by new generation of development methods (see Section 1.1) relying on the Unified Modelling Language (UML) [OMG, 2005]. UML is the current standard modelling language, both for the industry and the software engineering research community. We propose a domain specific language, built as a UML profile, called SecAM (which stands for Security Analysis and Modelling) that integrates with the UML for the modelling and analysis of security. Integration SecAM is used to annotated security issues in the requirements, design and deployment models of the UML. Therefore the security specification is integrated with the system functional specification, i.e., with the system models. The rest of the stages will use these models for development, then providing the necessary integrated view of security in all the stages of the life-cycle. Analysis SecAM is conceived so that it allows to leverage the system models for security 27 Section 3.2 3. A UML Profile for Security analysis purposes. Sometimes the very same models can be directly used for analysis, sometimes they are transformed into formal models that allow analysis (e.g., Fault trees or Petri nets). Unified view and vocabulary SecAM uses the standard Value Specification Language (VSL) [OMG, 2009]. VSL aims at the specification of NFPs, say performance, dependability and security. Through this language the different communities researching security gain a common vocabulary for expressing the security properties they manage. Current SE techniques SecAM resorts to current software engineering trends. For example, the model-driven paradigm (MDD) to transform system models into formal models of analysis or the profiling mechanism, later explained. In the following, we introduce the SecAM profile that integrates with the UML for the modelling and analysis of security. The SecAM profile was originally published in [Rodr´ıguez et al., 2010] and used in several manuscripts such as [Rodr´ıguez and Merseguer, 2010,Rodr´ıguez et al., 2012d]. 3.2 SecAM UML profile The basis that support the SecAM profile are well-known, rely on standards and mean the current mainstream in software engineering with UML. At this regard, SecAM relies on the “UML profile for Modelling and Analysis of RealTime and Embedded systems” (MARTE) [OMG, 2009]. MARTE is an Object Management Group (OMG) standard defined using the “profiling” mechanism, a current innovative software engineering technique, as proposed by the fourth principle in the previous section. Profiling was introduced by UML to indeed add new capabilities to the language. A UML profile is just an extension of the UML defined in terms of: Stereotypes They are concepts in the target domain that will be added to the UML. For example, in SecAM we will add stereotypes for the security concepts, e.g., attack or intrusion. Tags The attributes of the stereotypes. For example, for the attack stereotype, as we will show later, we will define attributes such as its type,objective or location. Constraints They are formulae that apply to stereotypes and UML elements to extend their semantics. Another important feature of MARTE is that it provides an analysis framework called Quantitative Analysis Model (GQAM). SecAM inherits GQAM, what confers it the analysis 28 3. A UML Profile for Security Section 3.2 capabilities that we defended in the previous section, second principle. The analysis in MARTE addresses the schedulability and performance NFPs, while in SecAM the security. MARTE has been specialised for dependability modelling and analysis, leading to the definition of a Dependability Analysis and Modelling (DAM) profile [Bernardi et al., 2011]. MARTE and DAM together provide the basic bricks on which we build on our profile proposal in the security context. Aside of MARTE, SecAM is not the first attempt to enlarge UML for the analysis of NFPs. The Dependability Analysis and Modelling (DAM) profile [Bernardi et al., 2011] also follows this technique, in particular to introduce the dependability1NFP in UML. The relations between MARTE, SecAM and DAM are described in Figure 3.1(a). The VSL referred before is the language all they share and then what justifies the third principle in the Section 3.1. SecAM relies on MARTE and DAM, as shown in Figure 3.1(a). The result is a common and powerful UML framework that can be used for the joint specification of different NFPs, concretely performance and schedulability (from MARTE), dependability (from DAM) and security (from SecAM). Like MARTE and DAM, the SecAM profile is organized in two main packages, namely the SecAM UML Extensions, that includes the set of stereotypes, and the SecAM Library. The latter contains basic (typically enumeration types) and complex types, used to define the stereotype tags and composite security NFPs. The SecAM stereotypes are divided in sub-packages: Cryptographic,SecurityMechanisms, Resilience and AccessControl as in Figure 3.1(b). In the following, we introduce each package first depicting the stereotypes and tagged-values, and giving some explanation over them. Then, a small example for putting on each package in practice is introduced. The rationale of this organisation has been to address different security issues, typically dealt by independent research communities. We have used a breadth-first approach to provide common basis for the specification of security in UML. Obviously, the profile is an open proposal, that can be refined to add new modelling capabilities of security in application domains. The stereotypes in the first three sub-packages (cryptography, mechanisms and resilience) can be applied to behavioural diagrams, while the latter to structural diagrams. Each sub-package deals with a subset of well-known security attributes [Pfleeger and Pfleeger, 2006] (integrity, availability, confidentiality, authorisation, non-repudiation, authenticity) and, as shown in Table 3.1, the sub-packages overlap with respect to attribute coverage. These packages are largely explained in the sequel. 3.2.1 SecAM::Resilience package The Resilience package, depicted in Figure 3.2, was initially proposed in [Rodr´ıguez et al., 2010] to enable the specification in UML behavioural diagrams 1By dependability here we understand: availability, reliability, safety and maintainability. 29 Section 3.2 3. A UML Profile for Security <<profile>> MARTE <<profile>> DAM <<profile>> SecAM <<modelLibrary>> SecAM_Library SecAM_UML_Extensions <<modelLibrary>> SecAM::SecAM_Library Basic_SECA_Types Complex_SECA_Types <<profile>> MARTE::VSL::DataType <<modelLibrary>> MARTE::MARTE_Library::BasicNFP_Types <<import>> <<apply>> <<import>> <<import>> <<import>> <<import>> <<import>> (a) (b) Figure 3.1: (a) SecAM profile and library, (b) SecAM UML extensions (subpackages). 30 3. A UML Profile for Security Section 3.2 Security SecAM packages attributes (P1) (P2) (P3) (P4) Integrity √ √ √ Availability √ √ Confidentiality √ √ √ Authorisation √ Non-repudiation √ Authenticity √ (P1): Cryptographic; (P2): SecurityMechanisms (P3): Resilience; (P4): AccessControl Table 3.1: Security attributes and SecAM packages in which they are covered. of attacks, vulnerabilities and intrusion concepts, and their causal relationships (i.e., the AVI chain) [Avizienis et al., 2004], as well as to support vulnerability stochastic analysis. It contains two stereotypes, SecaAttackGenerator and SecaStep. They specialise the DAM stereotypes DaFaultGenerator and DaStep, respectively. Hence, by inheritance, they can be applied to all those UML behavioural model elements that can be stereotyped with the latters. For example, SecaStep can stereotype actions, activities, trigger events, transitions and states in UML State Machines diagrams, messages and fragments in UML Sequence Diagrams. These two stereotypes have the attributes depicted in Figure 3.2 (left side), i.e., attack of SecaAttackGenerator and vulnerability and intrusion of SecaStep. The definition of the types of these attributes appears in Figure 3.2 (right side). Herein, we add a new complex type to represent the concept of coordinated attacks (SecaCoordAttack). A coordinated attack allows attackers to avoid an intrusion detection by splitting a malicious attack pattern in several sub-patterns (attacks attribute). It can be classified (type attribute) as [Braynov, 2003]: a cumulative attack, where simultaneous attacks are initiated to overcome computer limitations; a replicated attack, where several attacks to replicated services occur to bring down the entire service structure; or a mixed attack, i.e., a combination of the previous ones. For probabilistic analysis purposes, we have characterized a coordinated attack by its occurrence probability (occurrenceProb), that is the joint probability of the occurrences of single attacks it coordinates. Considering several sources [Barnum, 2008, Hansman and Hunt, 2005, Hussain et al., 2003] new attributes have been also added to the Attack class; i.e., class, kind,objective and location. The different classes of attacks (ClassOfAttack) are compliant to the taxonomy defined by Hansman and Hunt in [Hansman and Hunt, 2005], e.g., virus or worm, which define how an attack works. On the other hand, an attack can be of different kind (KindOfAttack) [Barnum, 2008], depending on the method adopted by the attacker to succeed in the intent, e.g., injection or 31 Section 3.2 3. A UML Profile for Security <<stereotype>> SecaAttackGenerator attack : SecaAttack <<stereotype>> DAM::DaFaultGenerator <<profile>> SecAM::Resilience <<tupleType>> DAM::DaFault ocurrenceProb : NFP_Real[*] <<tupleType>> SecaCoordAttack type : CoordinationType attacks : SecaAttack[2..*] / ocurrenceProb : NFP_Real[*] <<tupleType>> SecaIntrusion successProb : NFP_Real origin : SecaVulnerable cause : SecaAttack <<tupleType>> SecaVulnerable degree : Degree composed : SecaVulnerable[*] <<tupleType>> SecaAttack type : TypeOfAttack class : ClassOfAttack location : AttackLocation objective : AttackObjective kind: KindOfAttack[*] <<stereotype>> DAM::DaStep <<stereotype>> SecaStep vulnerability : SecaVulnerable intrusion : SecaIntrusion <<Constant>> Injection <<Constant>> ResourceModification <<Constant>> ProtocolManipulation <<Constant>> Analysis <<Constant>> APIabuse <<Constant>> BruteForce <<Constant>> Flooding <<Constant>> Spoofing <<Constant>> SocialEngineering <<enumeration>> KindOfAttack <<Constant>> Denial-Of-Service <<Constant>> RunArbitraryCode <<Constant>> PrivilegeScalation <<Constant>> DataModification <<Constant>> InformationLeakage <<enumeration>> AttackObjective <<Constant>> Single-source <<Constant>> Multi-source <<Constant>> Reflector-source <<enumeration>> AttackLocation <<Constant>> Virus <<Constant>> Worm <<Constant>> BufferOverflow <<Constant>> ResourceConsuming <<Constant>> Physical <<Constant>> Password <<Constant>> InformationGathering <<Constant>> Trojan <<enumeration>> ClassOfAttack <<Constant>> Cumulative <<Constant>> Replicated <<Constant>> Mixed <<enumeration>> CoordinationType <<Constant>> Active <<Constant>> Passive <<enumeration>> TypeOfAttack <<modelLibrary>> SecAM::SecAM_Library <<import>> Figure 3.2: The SecAM::Resilience package. resource modification. If we focus on the objective of the attack (AttackObjective), that is, what the attack is able to provoke in the system, we can distinguish: denial of service, run arbitrary code, privilege escalation, data modification and information leakage. Finally, considering from where the attack is actuating, three different locations [Hussain et al., 2003] can be identified (AttackLocation): single-source (originated at only one host), multisource (replicated over multiple hosts), and reflector-source (the attacker uses legitimate hosts to attack the victim, hiding so his identity or amplifying his attack [Paxson, 2001]). In Figure 3.3 we put on practice the Resilience extensions, as UML notes, with a twofold purpose: 1) to characterize from a qualitative point of view the possible attacks to a server host, the activities of the server that are vulnerable to such attacks as well as the consequences of an intrusion; 2) to provide quantitative input parameters for carrying out vulnerability analysis. Observe that the annotations could appear clumsy even for a simple model then affecting the readability and/or scalability of profiling approaches. However, they are introduced for illustration purposes. Indeed, most of the current UML-CASE tools provide support to profiling techniques through proper visualization features. The values assigned to tags are expressed using the VSL syntax. In particular, for complex NFP different values can be set: a value or variable name prefixed by the dollar symbol (value property); the origin of the NFP (source), e.g., an estimated or measured value; the type of statistical measure (statQ), e.g., a mean or a variance. Figure 3.3 depicts a simple UML State Machine diagram representing a server attending customer requests. Such requests come from a WAN connection which can be exploited 32 3. A UML Profile for Security Section 3.2 do / processCustomer(c) Hung Processing attendCustomer(c) $1=(occurrenceProb=(value=$attProb, source=est); type=Active; class=ResourceConsuming; kind=Flooding; objective=Denial-of-Service) $2=(degree=High) «secaAttackGenerator» {attack=$1} «secaStep» {kind=intrusion; intrusion=(successProb=(value=$succProb,source=assm); cause=$1;origin=$2)} «secaStep» {hostDemand= (value=$process,unit=s,statQ=mean,source=est); kind=vulnerable;vulnerability=$2} «secaStep» {prob=(1 - $attProb*$succProb)} Figure 3.3: A UML-State Machine diagram with SecAM::Resilience annotations. by external attackers (transition stereotyped secaAttackGenerator). The expected attack (attack tagged-value) is classified as active, resource-consuming, denial-of-service and flooding. The probability of an attack (occurrenceProb) is specified as an input parameter (attProb). The do-activity in the Processing state (stereotyped secaStep) is highly vulnerable to attacks (vulnerability tagged-value). We have used hostDemand to specify the estimated mean time duration (in seconds) of the do-activity as a parameter (process). The state Processing owns two immediate outgoing transitions, the annotations attached to the latter are meant to resolve the conflict in a probabilistic manner. When the incoming request is an attack, then an intrusion arises that leads to a process crash. Otherwise, the process terminates correctly. The transition from Processing to Hung is an intrusion step; it may occur with a probability attProb ·succProb, where attProb is the probability of an attack and succProb is the probability that, given an attack, it finally succeeds. 3.2.2 SecAM::Cryptographic package Cryptography [Menezes et al., 1996] is primarily used to gain confidentiality over the communications between pairs; however, it also supports data integrity and authentication. Confidentiality assures that information is not disclosed to those unauthorised to own it, while data integrity guarantees the information keeps unaltered. Finally, authentication happens at two levels: entity authentication, that ensures two (or more) participants on a communication are identified, and data origin authentication that guarantees the information has been delivered from the origin. The Cryptographic package has been devised to support mainly the specification of cryptographic design rather than its analysis as it happened with the resilience package. So, by adding contextual information to the UML models, such as when an encryption/decryption takes place and the main characteristics of these processes. 33 Section 3.2 3. A UML Profile for Security <<modelLibrary>> SecAM::SecAM_Library <<import>> <<Constant>> Software <<Constant>> Hardware <<Constant>> Biometric <<enumeration>> KeyType <<Constant>> Assymmetric <<Constant>> Symmetric <<enumeration>> KeyKind <<Constant>> Zero <<Constant>> Bit <<Constant>> Byte <<enumeration>> PaddingScheme <<Constant>> ECB <<Constant>> CBC <<Constant>> CFM <<Constant>> OFM <<Constant>> CTR <<enumeration>> OperationMode <<Constant>> Synchronous <<Constant>> Asynchronous <<enumeration>> StreamType <<Constant>> Periodic <<Constant>> NonPeriodic <<enumeration>> Perioricity <<Constant>> vulnerable <<Constant>> intrusion <<Constant>> cryptographic <<Constant>> messageDigest <<enumeration>> SecStepKind size : NFP_Integer type : KeyType kind : KeyKind[0..1] cipher : SecaCipher[0..1] <<tupleType>> SecaKey type : StreamType perioricity : Perioricity key : SecaKey <<tupleType>> SecaStream size : NFP_Integer padding : PaddingScheme[0..1] opMode : OperationMode <<tupleType>> SecaBlock errorRate : NFP_Real operationalRate : NFP_Real kind : CipherKind <<tupleType>> SecaCipher <<Constant>> Stream <<Constant>> Block <<enumeration>> CipherKind kind : SecStepKind vunerable : SecaVulnerable intrusion : SecaIntrusion cryptographic : SecaKey hash : SecaMessageDigest <<stereotype>> SecaStep <<stereotype>> DAM::DaStep length : NFP_DataSize padding : PaddingScheme[0..1] opMode : OperationMode blocks : SecaBlock [1..*] <<tupleType>> SecaMessageDigest key : SecaKey <<tupleType>> SecaMAC SecAM::Cryptography <<profile>> Figure 3.4: The SecAM::Cryptographic package. Figure 3.4 depicts the set of extensions for specifying cryptography into UML behavioural models. The SecaStep stereotype, already considered in the Resilience subpackage, is now used to specify a cryptographic step through the new tags: kind, cryptographic and hash. The cryptographic tag is a complex type (SecaKey) that enables to characterize the key, either asymmetric or symmetric (KeyKind). The latter can be of different types, depending on how/where it is deployed (KeyType): software, hardware (i.e., cryptographic devices) or biometric (e.g., fingerprint, facial recognition or retinal scanning). A cipher (SecaCipher) can be either a block or stream cipher, depending on the algorithm, and it uses a key. It is characterized by an error rate, i.e., the ratio of errors that the cipher can suffer during the process of encryption/decryption, and an operational rate, i.e., the number of encrypted/decrypted bits per time unit. A stream cipher (SecaStream) uses a key-stream to cipher/decipher plain text, which generates a stream of secret bits given an initial key. It can be either self-synchronous (i.e., ciphertext-auto-key, CTAK) or synchronous (i.e., key-auto-key, KAK), depending whether the used key-stream is influenced or not by the ciphered/deciphered text. Besides, a stream cipher can be either periodic or non-periodic (e.g., Vernam cipher, running-key), depending on the self-repetition of the key-stream. A block cipher (SecaBlock) has a block size, that is the number of characters (or bits) of the plain text message which can be ciphered at a time. Normally, the partition of the message into blocks is not exact and, therefore, a padding scheme is needed to “fill the gaps” then existing several padding schemes. Besides, a block cipher uses an operation mode (OperationMode) which determines its encryption/decryption scheme. Several operation modes have been proposed; without loss of generality, we rely on the ones approved by NIST [Dworkin, 2001]. 34 3. A UML Profile for Security Section 3.3 must be greater or equal than Secret. However, relying on the final user for the definition of the OCL constraints that define the access control policies may result in a non-trivial issue. For this reason, we are working on an automatic methodology to make it easier. For instance, providing check lists for collecting security attributes and then deriving the OCL constraints automatically. This an interesting step which deserves further study. 3.3 Concluding Remarks There exists a real need to devise new methods for the development of complex, large scale and distributed systems which are exposed to malicious security issues. The profile we present here is an asset, inside UML, for these methods to take advantage of the four principles that we devised: integration, analysis, unified view and leveraging of current trends in software engineering. A solution which tackles these security issues should consider them as an integrated approach, that is, considering security in the early stages of the software and systems lifecycle. Besides, such solution should also promote the analysis of system security before the deployment stage, a unified view of security issues and, at the same time, fit properly into the current software engineering techniques. SecAM presents a powerful UML framework for the specification and analysis of security. SecAM is made of different sub-packages, each one targeting a subset of well-known security attributes: integrity, availability, confidentiality, authorisation, non-repudiation, authenticity. A plug-in for Eclipse tool (built on MARTE-DAM profile plug-in) has been developed. However, this plug-in is in a (very) early development phase thus is not fully operative and not yet released. As future work, we plan to develop plug-ins for applying SecAM into UML tools, e.g., Eclipse (through a fully operative plug-in) or ArgoUML. Moreover, SecAM needs to be applied in complex case studies, and further extensions have to be developed for addressing concrete application domains. Besides, we aim at extending the transformation to other interesting dependability/security analysis models, such as Fault Trees or Bayesian Networks. We also plan to define model-to-model (M2M) transformations to automatically compute SecAM derived taggedvalues, to verify SecAM UML-profiled model for consistency (i.e., using OCL constraints) as well as to compute vulnerability related metrics. 41 Chapter 4 Fault-Tolerant Techniques for Critical Systems This chapter summarises the main contributions of this dissertation related to the modelling of Fault-Tolerant techniques (FTTs). The proposed models have resulted in several publications [Rodr´ıguez and Merseguer, 2010,Rodr´ıguez et al., 2012d,Rodr´ıguez et al., 2013b]. 4.1 Motivation As we claim in Section 1.1, large scale and distributed systems deployed in heterogeneous environments are subject to be a target of harmful attacks, with the intent of performing an intrusion, confidential data theft or other type of attacks. These systems, whose provided services may suffer some degradation due to errors and failures triggered by attacks, are commonly called degradable systems. Normally, degradable systems include Fault-Tolerant (FT) techniques [Avizienis, 1997, Avizienis et al., 2004] that provide mechanisms to deal with failures inside the system and mitigate the consequences of faults. Some examples of FT techniques are: switching system requests between non-faulty components, adding watch-dogs for checking liveness of system components, or software exception handlers. A degradable system equipped with a FT technique is called a FT system. Therefore, when designing critical systems it is fundamental to study the attacks that may occur and plan how to react from them. The occurrence of attacks in software systems leads software designers to introduce the aforementioned FT Techniques (FTTs), such as recovery procedures, and/or Security Mechanisms (SMs), such as encryption of data, in order to react to intrusions. This chapter addresses the issue of integrating already developed fault-tolerant (FT) techniques into software designs for their analysis through automatically obtained formal models (as it is shown in Chapter 5). More precisely, this chapter is subdivided in two 43 Section 4.2 4. Fault-Tolerant Techniques for Critical Systems (a) Original model (b) Transformed model Figure 4.1: Transformation rule T R of a transition tfsubject to fail (faulty transition). main sections, one of them devoted to a review of FT concepts [Avizienis et al., 2004, Avizienis, 1997] and our proposal of compositional Petri net (PN) models for FT techniques, and a second one where we propose a UML model library containing FT techniques that are ready to use in UML designs of critical systems. Firstly, we introduce a compositional PN model for FTTs based on the basic concepts of FT given in Section 2.3. These compositional PN models allow us to make sensitive performability analysis easier when some FT parameters change (e.g., expected failure rate or activity timing related to recovery actions). Thus, these FT models can be useful for evaluating different FT approaches in the same system model. Lastly, we introduce a UML model library which models different FTTs, namely: a Proactive-Reactive Recovery technique (inspired in the one given in [Sousa et al., 2010a]), Switch Over Failing technique and Ping And Restore technique. These UML models can be transformed to PN models using well-known techniques [Distefano et al., 2011, G´omez-Mart´ınez and Merseguer, 2006] (see [Balsamo et al., 2004] for an extensive survey on this topic), and they may allow to test different techniques for the same design to find the ones fitting better. However, such PN models are more complex than the Process PNs that we introduced in Section 2.1 – indeed, they belong to the class of Generalised Stochastic Petri Nets (GSPNs), and therefore these models cannot be analysed with the methods presented in the Part II of this dissertation but with simulation. 4.2 Compositional PN Models for Fault Tolerance In this section, we provide compositional PN-based models for the Fault-Tolerant (FT) techniques based on the basic concepts of FT given in Section 2.3. Recall that a FT technique may involve both error detection – concurrent or preemptive – and recovery phases – divided in error handling (rollback, rollforward or compensation) and fault handling (diagnosis, isolation, reconfiguration or reinitialisation). Consider we have a system modelled with a PN in which there is an activity (represented by a timed transition Tf) which is subject to fail. We called it faulty transition, as it may lead to a fault. Before adding any FT technique to the system, we apply a transformation rule T R in the PN. This transformation rule allows us to apply our approach in the general 44 4. Fault-Tolerant Techniques for Critical Systems Section 4.2 Figure 4.2: Integration between a PN-based system model and a PN-based FT technique. case, and it is not modifying the behaviour of the original PN model anyhow. Figure 4.1 shows how this transformation rule TR works: two immediate transitions tand t′and two places •Tfand T• fare added just from(to) transition Tf, and all input(output) places of transition Tfare accordingly connected to transition tand t′. Figure 4.2 depicts the interaction between a PN that models the behaviour of a given system and a PN that models a FT technique. A PN-based FT model is subdivided in Error Detection and Recovery sub-models. Each sub-model represents respectively the phases involved in a FT technique. In the sequel, we explain each model and its interactions in detail. 4.2.1 PN Error Detection Model Figure 4.3(a) depicts the PN model for error detection. The timed transition Tdetect represents how long the error detection activity takes. Note that this transition is abstracting the behaviour for detecting an error, so that it may be refined into a more complex model representing error detection in more detail (Detection phase in Figure 4.3(a)). After error detection activity takes place, the presence of an error is discriminated. When an error arises (transition terr), then a token is put on place p|eed. Otherwise, a token is put on place p|ned. The integration between the Error Detection model and the System model is done through labelled places p|sed, p|eed (a labelled place pis defined as p|label). We have followed the compositional rules over the places defined in [Donatelli and Franceschinis, 1996, Bernardi et al., 2001] to combine models using labelled places: pairs of places with matching labels are superposed. Figure 4.3(a) depicts the places p|sed, p|ned added to the system model. The origin of the incoming arc of place p|sed depends on the type of error detection, and synchronises the execution of error detection model with the system model: when con45 Section 4.2 4. Fault-Tolerant Techniques for Critical Systems current, the arc added is the red-dashed one (from tto p|sed); otherwise (preemptive), the green-dotted arc is considered (from Tfto p|sed). Note that the place p|ned is synchronised with T• f(which indeed is added to the system by transformation rule TR). (a) Error Detection model (b) Places p|sed, p|ned added to the system model Figure 4.3: PN-based model of Error Detection and faulty activity inside the system. This simple model allows us to represent the most common error detection techniques, e.g., to validate input data, or intermediate data generated and reused during a faulty transition (it can be concurrently done), or to validate output after a faulty transition execution (preemptive). 4.2.2 PN Recovery Model The recovery phase involves two steps, a first (optional) step of error handling (rollback, rollforward or compensation) and a second one of fault handling technique (diagnosis, isolation, reconfiguration or reinitialisation). Following the definitions given in [Avizienis et al., 2004], we have grouped the fault handling techniques in two groups: diagnosis and reinitialisation techniques; and isolation and reconfiguration. This decision is based on the abstracted behaviour of these techniques, as we explain henceforward. We have composed models that represent valid combinations of the recovery phase as it is shown in Table 4.1. This classification is made based on how the techniques work. For instance, we believe that a rollforward technnique cannot be combined 46 4. Fault-Tolerant Techniques for Critical Systems Section 4.2 Rollforward Rollbackward (& compensation)∗(& compensation)∗ Diagnosis √ √ Isolation √ √ Reconfiguration X√ Reinitialisation X√ Table 4.1: Valid combinations of error handling and fault handling techniques. The symbol ∗means optional. with reconfiguration or reinitialisation, because reconfiguration switches the request to spare components, while reinitialisation updates and records a new system configuration. Thus, we consider that to move to a future correct state after recovering is meaningless. Figure 4.4(a) shows the PN model of diagnosis and reinitialisation FT recovery techniques. Place p|eed is superposed with the one of Error Detection model, and place p|T• fis superposed with place T• fin the system model. A token in place p|eed indicates that an error has been detected. Once transition trm is fired, a (optional) compensation activity may take place (Compensation phase). Then, recovery activity takes place (abstracted in Recovery phase). As in the previous model of error detection, we have represented compensation and recovery phases as a single timed transitions (Tcand Trec, respectively). These transitions may be refined into a more complex models representing compensation and recovery activities in more detail. Finally, the token flow is redirected through place p|rtn. The superposition of this place depends on the error handling technique used: it will be a place which becomes eventually marked after the faulty transition Tfis fired (rollforward), or which was eventually marked before its firing (rollback). In both cases and to keep conservativeness of the model, place p|rtn must belong to the p-semiflow associated to the resource r(we called it faulty resource), being rthe inner resource used by faulty activity. Although a transition Tfcan represent an activity where several resources are being used, for the sake of simplicity in this paper we assume that the fault is caused by the use of the inner resource (i.e., the last one acquired). Otherwise, note that after the recovering phase other resources acquired after faulty resource should be released to keep conservativeness. The difference between diagnosis and reinitialisation technique can be established by the duration of the recovery phase. For instance, when diagnosis technique is considered, the recovery phase will have a much lower duration than when reinitialisation is taken into account due to the actions that are performed. Figure 4.4(b) shows the PN model of isolation and reconfiguration FT recovery techniques. This case is identical to the previous until the (optional) compensation phase. After the compensation phase takes place, the type of the fault is discriminated [Avizienis et al., 2004] as intermittent (that is, the fault is transient) or solid (i.e., 47 Section 4.2 4. Fault-Tolerant Techniques for Critical Systems (a) Diagnosis & reinitialisation (b) Isolation & reconfiguration Figure 4.4: PN-based models of Recovery model: (a) and (b) isolation & reconfiguration. the faults whose activation is reproducible). When the fault is intermittent, as proposed in [Avizienis et al., 2004], normal execution can keep going on and token is returned to place p|rtn (as before, the superposed place depends on the type of error detection). On the contrary, when a solid fault is detected, the faulty resource is excluded from normal service delivery – as indicated by both isolation and reconfiguration techniques – and the token is moved to the place p|safe. We assume that place p|safe is superposed with the place previous to acquire the faulty resource r, i.e., p|safe =•tacq, where tacq is the transition where faulty resource ris acquired. In the case of isolation and reconfiguration, the recovery phase is called Maintenance phase, because it involves the participation of an external agent [Avizienis et al., 2004]. We have modelled maintenance phase as a single transition TMT T R that represents the Mean Time To Repair (MTTR) spent on fixing the faulty resource. As in the previous case, this model can be refined to a more complex maintenance model. Anyhow, after maintenance phase takes place the fixed resource is returned to place p|ir, which is superposed to the resource place pr. As in the previous techniques, the difference between isolation and reconfiguration technique can be established by the duration of the maintenance phase. For instance, when isolation technique is considered, the maintenance phase will have a much greater duration 48 4. Fault-Tolerant Techniques for Critical Systems Section 4.2 than when reconfiguration is taken into account. Finally, note that most of the FT techniques can be modelled with the proposed models. For instance, a watchdog can be modelled as a reconfiguration FT technique with concurrent error detection and rollforward (or rollback), and a check-pointing and rollback can be modelled as a reinitialisation FT technique. Unfortunately, other FT techniques, such as nversion programming or combined proactive-reactive techniques [Sousa et al., 2010a] cannot be adapted to the proposed model and some tweaks must be done. We aim to extend these models to cover all FT techniques as a future work. Running example Let us consider a packet-routing algorithm inside a router where packets arrive and after checking source and destination of the packets, they are filtered following some defined rules. Figure 4.5 depicts a PN modelling such an algorithm. The PN marking represents the number nP of packets (initial marking of the process-idle place, p0), the number nT of threads attending the incoming packets (initial marking of p2) and the number nS of filtering-threads (initial marking of p7). The number nC denotes the capacity of the system. We consider that this number is equal to the number nP of packets, therefore place p′ 0becomes implicit and we omit it for analysis. Packets arrive to the router following an exponential distribution of mean δ0= 5 milliseconds1. The amount of time for checking packet headers (i.e., source, destination) is represented by transition T2, which follows an exponential distribution of mean δ2= 2 milliseconds. The algorithm’s decision is represented by place p5and its outgoing arcs: either transition t4is fired (then the packet must be discarded, which happens with a probability of 0.75), or transition t5is fired. In the latter case, once some filtering-thread is available, it is used. Such a use is represented by T7and takes, on average, δ7= 1 millisecond to complete. Finally, T9represents the final step of the algorithm, that consists in routing the packet(acknowledgement) properly to its destination(source) and takes, in terms of time, about 2 milliseconds, i.e., δ9= 2. This running example will be used henceforward to illustrate our approach. Suppose that the filtering activity may fail, i.e., the faulty transition is T7. The router manufacturer is interested in adding a watchdog (recall it can be modelled as a reconfiguration FT technique) into the algorithm such that the threads that fail (they are hanged) are discarded, and they are cleaned with a fixed internal timer. In this case, the error detection model is concurrent, as the failure can be detected during normal operation; and the error handling technique used is rollback: when an error is detected, the packet is filtered by another thread, when available. The resulting PN after adding the FT technique described above is depicted in Figure 4.6. In Section 6.4, this running example is used for sensitive performability analysis. 1We use δias an abbreviation for δ(Ti) 49 Section 4.2 4. Fault-Tolerant Techniques for Critical Systems Figure 4.5: Petri net representation of a packet-routing algorithm. y′ 1=y1∪{•T7, T • 7, p1 4} y′′ 1=y1∪{p1|sed, p1 2, p1 3, p1|eed, p1 4}x′2=x2∪{t′ 1, t′ 2, T1 detect, t1 noError} y′ 2=y2∪{•T7, T • 7, p1 4}x3={t′ 1, T7, T1 detect, t1 err, t1 rm, t1 int} y′′ 2=y2∪{p1|sed, p1 2, p1 3, p1|eed, p1 4}x4={t6, t′ 1, T7, T1 detect, t1 err, t1 rm, t1 sld, T1 MT T R} y′ 3=y3∪{•T7, T • 7, p1 4, p1 5} y′′ 3=y3∪{p1|sed, p1 2, p1 3, p1|eed, p1 4, p1 5} (a) (b) Table 4.2: New (a) p-semiflows and (b) t-semiflows of the PN in Figure 4.6. 4.2.3 Analysis of PN-based FT Models This subsection analyses how some structural properties are modified when the proposed FT models are added (namely, the p-semiflows and t-semiflows) and how visit ratios properties are as well affected. P-semiflows Let us analyse how minimal p-semiflows are modified. The addition of the proposed FT models provokes that, for each p-semiflow yrassociated to a resource rthat makes use of the faulty transition tf(i.e, kyrk∩{•tf, t• f} 6=∅), yris transformed into two p-semiflows y′ r,y′′ r,y′ r6=y′′ rsuch that kyrk ⊂ ky′ rk,kyrk ⊂ ky′′ rk. This transformation is due to the FT models consume/produce tokens from/to the original p-semiflows. These p-semiflows cover all places added by the FT technique, thus the net remains conservative. For instance, the minimal initial p-semiflows are, in Figure 4.5: y1= {p0, p1, p3, p4, p5, p6|safe, p8|rtn, p9, p10, p11},y2={p2, p3, p4, p5, p6|safe, p8|rtn, p9, p10, p11} and y3={p7|ir, p8|rtn, p9}. The minimal p-semiflows of the PN in Figure 4.5 that contain 50 4. Fault-Tolerant Techniques for Critical Systems Section 4.3 Token colour definitions type D is {1. . . nDevices} type G is {G1. . . G⌈nDevices k⌉} subtype Giis {(k·(i−1) + 1) . . . k ·i} var i :D, g :G Initial marking m0(Enable) = Xi∈D m0(nextGroup) = G1 m0(Idle) = 1 m0(maxParallel) = k Functions definitions belonging(g:G) = Xi∈G cSubset(g:G) = Xi∈D|i∋G allDevices() = Xi∈D Table 4.4: CPN initial marking, token colour definition and functions. (i.e., affected by attacks), it brings down such a machine and brings up a new (and clean) replica. Note that in both FTTs the machine replica may have a different operating system or software capabilities, as a way of mitigating incoming illegal requests. UML Modelling Figure 4.10 illustrates the UML Sequence Diagram (UML-SD) of the SwitchOverFailing FTT interacting with a web server. Grey notes indicate the system performance properties and they are specified as annotations by means of the MARTE profile. For example, the gaStep stereotype represents a part of the scenario (defined in sequence with other actions) for which it is possible to indicate the demands of such a part on the system resources, such as its execution on the host processor (called its hostDemand attribute). Each external incoming request is sent to the WatchDog that analyses it; such an analysis requires processing resources (hostDemand) of $ analyse milliseconds (ms), which is a mean value to be estimated. Note that the request may be an attack or not, and it can be either detected or not detected. When the request is not an attack, the web server redirects the request to other services inside the system. Successful attack detection occurs with a probability of $ hitRate. When the attack is detected and the threshold is reached, the WatchDog prepares a redundancy replica to be switched on, starts it (which has a duration of 70.1 seconds [Sousa et al., 2010a]), and then it switches off the server receiving the attacks, which has a cost of 0.6 seconds [Sousa et al., 2010a]. When the request is an attack but it is not detected, then the server collapses and it needs to be repaired, and we assumed it lasts for 30 minutes. For such a duration the server is inoperative, i.e., it is not attending 57 Section 4.3 4. Fault-Tolerant Techniques for Critical Systems alt [r is an attack] d : WatchDog ws : webServer 8: login(r) 1: loginRequest(r) 1.1.1: analyseRequest(r, nAttacks) ws1 : webServer 1.1: newLoginRequest(r) alt [r is detected as attack] 4: switchOn(ws1) 2: ws1= prepareNextReplica() «gaStep» {hostDemand= (value=0.5; unit=ms; statQ=mean; source=mea)} 4.1: start() alt [nAttacks > threshold] 3: switchO  (ws) 3.1: shutdown() «gaStep» {hostDemand= (value=0.6; unit=s; statQ=mean; source=mea)} 5: request clear 7: request clear 6: repair() «gaStep» {hostDemand= (value=70.1; unit=s; statQ=mean; source=mea)} «gaStep» {prob=$hitRate} sd SwitchOverFailing «gaStep» {hostDemand= (value=$analyse; unit=ms; statQ=mean; source=est)} «gaStep» {hostDemand= (value=30; unit=min; statQ=mean; source=mea)} Figure 4.10: UML Sequence Diagram of the SwitchOverFailing Fault-Tolerant Technique. 58 4. Fault-Tolerant Techniques for Critical Systems Section 4.4 new requests, because it represents the maintenance time, i.e., someone locally or remotely must fix the error or restart the server. It is worth to notice that input parameters of the model, such as $ analyse, $ hitRate, are values set by the IDS which implements this FTT. That is, this model will be useful for performing sensitive analysis of different IDS solutions. Figure 4.11 depicts the UML-SD of the Ping&Restore FTT interacting as well with a web server. The cyclic behaviour of the monitor is as follows. It waits a certain amount of time ( $ wait ms) and then initialises a variable m, which counts the number of replicas in a non-functional state. The monitor sets a timeout having a duration of $ tOut ms and iterates up to kmachines to be recovered, asking whether each machine is alive. When the machine answers, then the monitor cancels the timeout. Otherwise, the timeout is expired and the current machine is marked for recovering. When the number of machines to be recovered are reached or all machines have been inspected, then the monitor iterates preparing a new replica, switches off the faulty machine and switches on the new replica. As in the previous case, it is worthy of mention that input parameters of the model, such as $ wait, $ tOut, are values useful for performing sensitive analysis of different monitor solutions. 4.4 Concluding Remarks Security attacks aim at system vulnerabilities that, when achieve success, may lead to system failures. As an attempt to mitigate these effects, software designers use to introduce Fault-Tolerant Techniques (FTTs) and/or Security Mechanisms (SMs). In this chapter, we have proposed some models that represent common FT techniques, with the idea of combining such models with software behavioural designs. The combined model is useful for dependability assessment, as it will be shown in Chapter 5. The key point we look for is to gain a “library” of UML models representing FT techniques ready to use in critical designs. The use of our approach should otherwise bring several benefits from the point of view of a software engineer. The easy integration of FT techniques into software designs and the existence of such “library” may allow to test different techniques for the same design to find the ones fitting better. Such “library” will also free the engineer of worrying about how to model FT and concentrate on the problem domain. Finally, it is well-known that the use of formal models early in the life-cycle to prove requirements is less expensive than other approaches. As future work, we plan to develop a plug-in for common UML design tools, such as ArgoUML, Visual Paradigm or MagicDraw, which incorporates the UML FT models introduced in this chapter, thus to provide guidelines to software designers about the best choices of Fault-Tolerant techniques and security mechanisms for the attacks systems may suffer. 59 Section 4.4 4. Fault-Tolerant Techniques for Critical Systems alt loop loop m [m < k] [server is not down] loop t : timer m : monitor ws1 : webServer ws : webServer 6: 11.1: 11: switchOn(ws1) 10.1: 10: switchO  (ws) 9: ws1 = 8: 7: t expired 5: ack 4: setTimeOut(t) 3: isAlive(ws) 1: wait() 2: initialise(m = 0) cancelTimeOut(t) increment(m) shutdown() prepareNextReplica() start() sd Ping&Restore «gaStep» {hostDemand= (value=$wait; unit=ms; statQ=mean; source=est)} «gaStep» {hostDemand= (value=0.6; unit=s; statQ=mean; source=mea)} «gaStep» {hostDemand= (value=70.1; unit=s; statQ=mean; source=mea)} «gaStep» {hostDemand= (value=0.5; unit=ms; statQ=mean; source=mea)} «gaStep» {hostDemand= (value=$tOut; unit=ms; statQ=mean; source=est)} Figure 4.11: UML Sequence Diagram of the Ping&Restore Fault-Tolerant Technique. 60 Chapter 5 Model-Based Performance Prediction of Critical Systems This chapter introduces a model-based methodology for performance prediction of critical systems which combine Fault-Tolerant Techniques (FTTs), such as recovery procedures, and/or Security Mechanisms (SMs), such as encryption of data, in order to react to intrusions. The proposed methodology was originally published in [Rodr´ıguez et al., 2012d]. 5.1 Motivation Communication networks are globally used to perform many transactions: electronic purchases, bank transfers or even stock exchanges can be accomplished with a computer connected to a network. This new concept of electronic market allows to perform almost everything remotely, so saving a lot of time to the users. The main drawback in this domain is that some bad human behaviours may occur: spam or junk mails, viruses, trojan horses or other attacks are commonly suffered. For example, with the Denial-of-Service (DoS) attack [Garber, 2000] multiple requests are sent to a server with the intention of consuming its resources and, in last term, bringing the server down. These harmful actions clearly have an impact on the functionality of servers that might not be able to attend all incoming requests, and finally might bring down their services for saturation. Relevant efforts of software designers are devoted on devising the security strategies suitable to protect information and computational systems against not authorised accesses. In fact, when designing critical systems it is fundamental to study the attacks that may occur and plan how to react from them. The occurrence of attacks in software systems leads software designers to introduce different Fault-Tolerant Techniques (FTTs), such as recovery procedures, and/or Security Mechanisms (SMs), such as encryption of data, in order to react to intrusions. 61 Section 5.1 5. Model-Based Performance Prediction of Critical Systems Despite these efforts, it is necessary to consider the costs that have to be incurred to guarantee a certain security level in critical systems. In fact, the security costs can be very relevant and may span along different dimensions, such as budgeting, performance and reliability [Menasc´e, 2003,Menasc´e and Virgilio, 2000]. In this paper we focus on the security costs related to the system performance. FTTs and SMs inevitably consume system resources hence they influence the performance, even affecting its full operability. Therefore, the necessity of balancing security and performance in these systems becomes clear: security strategies must assure that the system guarantees a minimal level of functionality. The work in this chapter steps towards this goal. We define a model-based methodology able to quantitatively estimate the system performance while introducing some FTTs and/or SMs aimed at protecting critical systems. Such a methodology is able to inform software designers about the performance degradation the system may incur, thus supporting them to find appropriate security strategies while minimising performance penalties. To this end, we make use of a library of models that represent a subset of FTTs (already introduced in Section 4.3) and SMs ready to be composed. Once a system model is built, in order to conduct a joint analysis of security and performance with our approach it is necessary: (i) to specify the appropriate security annotations (e.g. the confidentiality of some data), and (ii) to annotate the model with performance related data (e.g. the system operational profile). Thereafter, such an annotated model can be automatically transformed into a performance model whose solution quantifies the prediction of performance properties for the system under design. The starting point of this work can be found in [Rodr´ıguez and Merseguer, 2010, Cortellessa et al., 2010a, Cortellessa and Trubiani, 2008], where we introduced a preliminary set of models aimed at representing the most common security strategies: models for FTTs have been introduced in [Rodr´ıguez and Merseguer, 2010], whereas models for SMs have been presented in [Cortellessa et al., 2010a]. This work jointly considers FTTs and SMs with the aim to enlarge the set of alternatives in the hands of software designers while making critical systems more secure. The final goal is to allow the addition of security strategies to a given system model thus to enable a model-based performance analysis. The setting where our approach works is Unified Modelling Language (UML) [OMG, 2005] for software modelling and Generalized Stochastic Petri Nets (GSPNs) [Ajmone Marsan et al., 1995] for performance analysis. UML models are aimed at representing the architecture of critical software systems. Such models can be extended for specific purposes through a technique called profiling [Lagarde et al., 2007,Selic, 2007]. A UML profile defines a set of stereotypes and taggedvalues which are used to extend its semantic. In this work, we use two profiles: (i) the Modelling and Analysis of Real-Time and Embedded Systems (MARTE) profile [OMG, 2009] for the specification of performance properties that enable the performance analysis; (ii) and the Security Analysis and Modelling (SecAM) profile [Rodr´ıguez et al., 2010] (see Section 3.2) for the specification of security properties. 62 5. Model-Based Performance Prediction of Critical Systems Section 5.2 UML annotated models are transformed into GSPN models, i.e., formal models representing the system for performance analysis purposes. This choice has been driven by two main factors: (i) GSPNs provide a formal notation which avoids any source of ambiguity while representing the stochastic behaviour of systems; (ii) GSPNs have a clear graphical notation and several tools have been developed for analysis. The transformation from UML to GSPN can been carried out using well-established tools, such as ArgoSPE [G´omez-Mart´ınez and Merseguer, 2006], ArgoPN [Delatour and de Lamotte, 2003] or ArgoPerformance [Distefano et al., 2011]. In the following, we firstly introduce the SMs that we consider for this work (namely, Encryption,Decryption,Digital Signature and Verification). The FTTs that we consider for this work have been previously introduced in Section 4.3. Lastly, we introduce a modelbased methodology to quantify the security-performance trade-off in critical systems where FTTs and SMs are considered. Chapter 9 introduces a case study where this methodology is applied. 5.2 Security Mechanisms The Security Mechanisms (SMs) were initially introduced in [Cortellessa and Trubiani, 2008, Cortellessa et al., 2010a], where Cortellesa and Trubiani introduced a set of UML models representing the most common security mechanisms. The SMs that we consider here are: Encryption, which refers to the usage of mathematical algorithms to transform data into a form that is unreadable without knowledge of a secret (e.g. a key); Decryption, which is the inverse operation of Encryption and makes the encrypted information readable again; the Digital Signature, which is a mathematical scheme for demonstrating the authenticity of a digital message or document through its Generation and Verification. Some preliminary operations, such as the generation of public and secret keys and the process of obtaining a certificate from a certification authority, are executed once by all software entities involved in the security annotations. The generation of public and private keys involves a software component that sets the key type and length thus to generate the public and the private keys. The process of obtaining a certificate from a certification authority involves a software component that sends its information and its public key; the certification authority checks the credentials and, if trusted, generates the certificate and sends it back to the software component. Encryption. The sender of the message decides the type of algorithm to use and the key length. The encryption can be of two different types: (i) asymmetric encryption (i.e., by public key); (ii) symmetric encryption (i.e., by a shared secret key). For asymmetric encryption the sender sets the padding scheme it requires and verifies the receiver’s certificate if it is not already known. Finally, the encryption algorithm is executed on the message with the public key of the receiver. For symmetric encryption the sender sets the algorithm 63 Section 5.3 5. Model-Based Performance Prediction of Critical Systems mode, performs a key-exchange protocol if a shared key is not already exchanged, and requires the exchange of certificates. Finally, the encryption algorithm is executed on the message with a session key obtained combining the keys generated by the sender and the receiver. Decryption. After receiving the encrypted message, the algorithm type and the key length are extracted, and the decryption algorithm is executed to obtain the plain text. Digital Signature Generation. The hash function algorithm must be specified, and the digest is generated. The encryption algorithm is applied on the digest by using the software component private key. Digital Signature Verification. A message and the digital signature are received as inputs. Two operations are performed: the first one is to calculate the digest; the second one is the actual execution of the encryption algorithm applied on the input digital signature producing a forecast of the real signature. The last computation involves the verification of the digital signature which compares the forecast digital signature with the received one, in order to confirm the verification. The models of the aforementioned security mechanisms are not reported, for further details please refer to [Cortellessa et al., 2010a]. 5.3 A Model-Based Methodology to Quantify SecurityPerformance Trade-off In this section we recall the model-based methodology presented in [Rodr´ıguez et al., 2012d] that allows to quantify the trade-off between the security strategies previously introduced to cope with the security attacks and the consequent performance degradation. In Figure 5.1 the process that we propose is reported. The process has been partitioned in two sides: on the top-hand side all models that can be represented with a software modelling notation (e.g. UML) appear; on the bottom-hand side all models represented with a performance modelling notation (e.g. GSPN) appear. The starting point of the process is a Performance-Annotated Application Model that is a static and dynamic representation of a software system. For the sake of simplicity, we assume that such a model is annotated with performance parameters related to the application such as the expected workload and system operational profile. The standard MARTE profile [OMG, 2009] has been adopted to specify performance parameters in our UML models. ASecurity-Annotated Application Model is obtained by introducing security annotations in the former. Such annotations specify where security strategies have to be inserted, namely which software services have to be protected and how (e.g. some data must be encrypted). Security annotations have been incorporated by the Resilience package of the Security Analysis and Modelling (SecAM) profile [Rodr´ıguez et al., 2010,Rodr´ıguez et al., 2011] that en64 5. Model-Based Performance Prediction of Critical Systems Section 5.3 Software notation (e.g. UML) Performance-Annotated APPLICATION MODEL (annotated with MARTE) Performance notation (e.g. GSPN) Security-Annotated APPLICATION MODEL (annotated with SecAM) SMs-Enabled APPLICATION MODEL Enabling Security Mechanisms Enabling Fault-Tolerant Techniques PERFORMANCE MODEL SMs-FTTs-Enabled APPLICATION MODEL Annotating Security FTTs-Enabled APPLICATION MODEL <<profile>> SecAM:: Resilience Merging Security Strategies Security Mechanisms Library Fault-Tolerant Techniques Library Figure 5.1: A process to estimate the system performance while adding Security Mechanisms and Fault-Tolerant Techniques. ables the specification of attacks, vulnerabilities and intrusions in UML models (see Section 3.2.1 for more details). Security attacks are characterised with their kind (i.e., flooding, spoofing or brute force), type (i.e., active or passive), objective (i.e. DoS, run arbitrary code or privilege escalation), class (i.e. virus, worm or buffer overflow) and occurrence rate (i.e. the probability of success). The task of Enabling Security Mechanisms has been already presented in [Cortellessa et al., 2010a]. This step is driven by the security annotations specified in the application model, and a SMs-Enabled Application Model is finally obtained. As an example, if a security annotation specifies that data must be kept secret, an additional pattern with the steps needed for the encryption mechanism must be introduced in the system model. Such a pattern is one of the mechanisms modelled in our Security Mechanisms Library (see Section 5.2). The task of Enabling Fault-Tolerant Techniques consists in embedding the appropriate fault-tolerant techniques in the system model, and a FTTs-Enabled Application Model is finally obtained. As an example, if an attack annotation specifies that spoofing can be performed for a certain service, an additional pattern with the steps needed for the FTT acting against such an attack must be introduced in the system model wherever the service is invoked. Such a pattern is one of the techniques modelled in our Fault-Tolerant Techniques Library (see Section 4.3.2). Note that both the security strategies we consider (i.e., SMs and FTTs) can be analysed in isolation or can be jointly analysed while merging the previous models (i.e., the SMsEnabled and FTTs-Enabled models) and a SMs-FTTs-Enabled Application Model is finally obtained. A key aspect of our approach is the composability of models, and this is achieved through 65 Section 5.4 5. Model-Based Performance Prediction of Critical Systems two features: (i) entry points for FTTs and SMs are unambiguously defined by security annotations, and (ii) models in the SMs and FTTs libraries have been designed to be easily composable with application models. Shaded boxes of Figure 5.1 represent the models that can be finally transformed into GSPN-based Performance Model(s). This step involves not only a transformation between modelling notations1, but an additional task is necessary to appropriately instrument the target performance model, because security strategies inevitably introduce additional performance parameters to be set in the model. The definition of such parameters is embedded in the security libraries where they are defined in an application-independent way. For example, the encryption mechanism introduces additional parameters affecting system performance, such as the complexity and resource requirements of the encryption algorithm, its mode of operation (e.g. CBC), the lengths of the keys, etc. Hence, the GSPN performance model finally generated has to be carefully parameterised with proper performance data. The GSPN performance models can be solved by means of any available formal model analysis tools, such as the PeabraiN [Rodr´ıguez et al., 2012a] simulator (Chapter 11 introduces PeabraiN in more detail), and the model evaluation provides performance indices that jointly take into account the security strategies as well as the performance features of critical systems. Note that such a trade-off analysis can be conducted on multiple security settings by only modifying the security annotations and re-running the steps of our approach. In fact, in Figure 5.1 we can define a certain multiplicity in the security annotations to emphasise that different strategies can be adopted for the same system design according to different settings. Finally we observe that several types of analysis can be conducted on the models built with this approach: (i) a performance model with a set of security requirements can be compared with one without security to simply study the performance degradation introduced from certain security strategies; (ii) the performance estimates from different performance models can be compared to each other to study the trade-off between security and performance across different design configurations. This model-based approach is put on evidence in a case study introduced in Chapter 9. 5.4 Concluding Remarks In this chapter we provided a model-based methodology able to quantitatively estimate the system performance while introducing Fault-Tolerant Techniques (FTTs) and/or Security Mechanisms (SMs) aimed at protecting critical systems. The main goal of this methodology is to introduce different security models and compose them with software architectural models, thus to support software designers to find appropriate security strategies while 1Well consolidated techniques have been exploited to transform software models (e.g. UML models) into performance models (e.g. GSPN), see [Balsamo et al., 2004] for an extensive survey on this topic. 66 6. Strategies for Upper Throughput Bound Computation in PNs Section 6.2 W. L=λ·W(6.1) Let pbe a place such that |p•|= 1, and p•={t}, then the pair (p, t) can be seen as a simple queueing system to which, if the limits of average marking and steady-state throughput exist, Little’s formula can be directly applied [Campos and Silva, 1992]: m(p) = (Pre(p, t)·χ(t)) ·υ(p) (6.2) where Pre(p, t)·χ(t) is the output rate of tokens from place p, which in steady state is equal to the input rate, and υ(p) is the average residence time at place p, i.e., the average time spent by a token in place p. The average residence time, υ(p), is the sum of the average waiting time due to a possible synchronisation and the average service time, δ(t). Therefore, equation (6.2) becomes: m(p) = (Pre(p, t)·χ(t)) ·υ(p)≥(Pre(p, t)·χ(t)) ·δ(t) (6.3) where the service time δ(t) is a lower bound for the average residence time υ(p), i.e., δ(t)≤υ(p), since place phas only one output transition. Given that conflicting transitions are assumed to be immediate, equation (6.3) can also be applied to any pair (p, t), t∈p• and tbeing a transition in conflict. Hence, the following system of inequalities can be derived [Campos and Silva, 1992] from (2.3) and (6.3): Γ(ti)·m≥Pre ·Dti(6.4) where Γ(ti) is the average interfiring time of transition tiand Dtiis the vector of average service demands of transitions,Dti(t) = δ(t)·vti(t) (the vector of visit ratios vtiis normalised for transition ti). In the following, we omit the superindex tiin Dtifor clarity. Let us notice that strongly connected SMGs have a single minimal t-semiflow that is equal to 1. This implies that the steady-state throughput is the same for every transition. Therefore, a single scalar variable Θ = 1 Γsuffices to express the throughput bound to be computed for all transitions. Proposition 1 The solution Θof the following LPP provides an upper bound for the steady-state throughput of the transitions of a strongly connected Freely Related T-semiflows (FRT) net [Chiola et al., 1993]: Maximize Θ : m(p)≥δ(p•)·Θ∀p∈P(6.5a) m=m0+C·σ(6.5b) σ≥0 (6.5c) 73 Section 6.2 6. Strategies for Upper Throughput Bound Computation in PNs Figure 6.1: Example MG. The first constraint (6.5a) is obtained from (6.3), while the second and third constraints (6.5b), (6.5c) establish that mmust be a solution of the state equation. The value of Θ is the exact throughput in the particular case of timed MG with deterministic delays associated to the firing delays [Ramchandani, 1974,Ramamoorthy and Ho, 1980]. The LP problem (LPP) in (6.5) can be transformed in its dual, which after some manipulations becomes in a LPP to compute a lower bound for the average inter-firing time of transition ti,Γlb(ti), [Campos and Silva, 1992]: Γ(ti)≥Γlb(ti) = maximum y·Pre ·D subject to y·C=0 y·m0= 1 y≥0 (6.6) As a side product of the solution of (6.6), yrepresents the slowest p-semiflow of the system, thus LPP (6.6) can also be seen as a search for the most constraining p-semiflow. This p-semiflow will be the one with the highest ratio y·Pre ·D y·m0 . Sn upper bound Θ(ti) for the steady-state throughput can be calculated as the inverse of the lower bound for the average inter-firing time Γlb(ti), that is, Θ(ti) = 1 Γlb(ti). For instance, let us consider the Marked Graph (MG) shown in Figure 6.1. The initial marking is: m(p1) = m(p2) = 1 and the rest of places have marking equal to 0. We assume that the firing delay of each transition follows an exponential distribution with mean δ1=δ3=δ5= 1, δ2=δ4= 2, respectively. The net has three cycles: {p1, p3, p5},{p1, p4, p6} 74 6. Strategies for Upper Throughput Bound Computation in PNs Section 6.2 and {p2, p4, p7}. The token/delay ratio of each cycle is 1 5,1 4and 1 3, respectively. The critical cycle, or bottleneck, is the one with minimum token to delay ratio, thus in our case, the bottleneck cycle is the one composed of places {p1, p3, p5}whose throughput is equal to 1 5. Hence, the initial throughput bound is 1 5and the initial bottleneck is ylb ={p1, p3, p5}. Assume again pbe a place such that |p•|= 1, and p•={t}. The equation (6.5a) can be also expressed as follows: m(p) = δ(t)·Θ(t) + µ(p) where µ(p)≥0 is the slack of place p. For every place pin the critical cycle (i.e., bottleneck) of a SMG, it necessarily holds that µ(p) = 0. For example, the slacks of the places of the SMG in Figure 6.1 are µ(p1) = µ(p3) = µ(p5) = 0, µ(p2) = 0.16, µ(p4) = 0.08, µ(p6) = 0.12 and µ(p7) = 0.16. In general, the same optimal value of the objective function in LPP (6.5) can be achieved for different slack vectors. In fact, the particular value of vector µwill depend on the algorithm used by the LP solver. 6.2.1 Tight Marking This section takes advantage of the degree of freedom of slacks in order to produce a marking, called tight marking and denoted ˜m, such that each transition has at least one input place with null slack. This marking will greatly ease the task of adding to the initial bottleneck cycle those cycles that have low ratio token/delay. Definition 10 A marking vector ˜m ∈R|P|is called a tight marking vector of a SMG if it satisfies: ˜m =m0+C·σ(6.7a) ∀p:˜m(p)≥δ(p•)·Θ (6.7b) ∀t∃p∈•t:˜m(p) = δ(p•)·Θ (6.7c) where ˜m ∈R|P|,σ∈R|T|, and Θ = 1 Γlb is the solution of (6.6). A place psatisfying the condition ˜m(p) = δ(p•)·Θis called tight. Since the places of the critical cycle do not have slack, they fulfil (6.7c) and hence are tight. On the other hand, non-critical places may have some positive slack. The tight marking exploits this flexibility by adjusting the marking in such a way that each transition has at least one input place that is tight. It can be shown that a tight marking exists for each SMG [Carmona et al., 2009]. Moreover it can be computed efficiently by solving an LPP. 75 Section 6.3 6. Strategies for Upper Throughput Bound Computation in PNs Proposition 2 [Carmona et al., 2009] A tight marking of a SMG can be computed by solving the following LPP: Maximize Σσ: δ(p•)·Θ≤˜m(p)for every p∈P ˜m =m0+C·σ σ(tp) = k (6.8) where tpis a transition that belongs to a critical cycle and kis any real constant number. The proof of the Proposition 2 can be found in [Carmona et al., 2009]. Since we are dealing with MGs, each row of the incidence matrix Ccontains a single positive (1) and a single negative (−1) value, while all other values are zeros. Therefore, the first two constraints of (6.8) can be transformed into a system of difference constraints and hence the LPP (6.8) can be efficiently solved by using the Bellman-Ford algorithm [Cormen et al., 2001]. Recalling the SMG shown in Figure 6.1, if we calculate the tight marking we obtain ˜m(p1) = 0.2, ˜m(p2) = 0.6, ˜m(p3) = 0.4, ˜m(p4) = 0.2, ˜m(p5) = 0.4, ˜m(p6) = 0.6, ˜m(p7) = 0.2. 6.3 Regrowing Strategy for Stochastic Marked Graphs This section presents an iterative strategy to grow the critical cycle and to compute an upper throughput bound in SMGs. The idea of the strategy is to add in each iteration the cycle that is potentially more restrictive than the others and then calculate the throughput. Such a throughput cannot be higher than the one in the previous iteration, since more constraints have been added to the net. The iteration process will stop when no significant improvement of the bound is achieved. Algorithm 1 represents the overall regrowing strategy used to compute throughput bounds. The algorithm needs as input data the Stochastic Marked Graph (SMG) to be analysed, hN, δi, and the degree of precision (ε > 0) to be achieved. As output data, the upper throughput bound, Θ, and the bottleneck cycle of the SMG, sccN′, are obtained. Firstly, an upper throughput bound of hN, δiis calculated according to (6.6), which will be the initial upper bound. Then, the tight marking of the system is computed by using the LPP shown in (6.8). The vector of slacks µis computed in step 3. The iteration process (steps 7–14) is repeated until no significant improvement is achieved with respect to the last iteration. In steps 8–11, a new set of places and transitions is added to the current bottleneck. To achieve this, steps 8–9 look for the place qthat is connected to the current bottleneck sccN′, i.e., q•∈sccN′, and has minimum slack. Then steps 10–11 build the new bottleneck by adding place qand the tight places that connect the current bottleneck to q. For brevity, in the algorithm we use p∈ N (p•∈ N) to denote that a place p(transition p•) is contained 76 6. Strategies for Upper Throughput Bound Computation in PNs Section 6.3 Input:hN, δi,ε Output: Θ, sccN′ 1Θ = Upper throughput bound of Naccording to (6.6) 2˜m = Tight marking according to (6.8) 3µ(p) = ˜m(p)−δ(p•)·Θ,∀p∈P 4N′= Graph resulting of removing from Nevery arc {p, p•}such that µ(p)>0 5sccN′= Strongly connected component of N′ 6Θ′= 0 7while Θ−Θ′ Θ≥εdo 8Q={q|q∈P, q 6∈ N′, q•∈sccN′} 9pm={q|µ(q) = min p∈Qµ(p)} 10 N′= Graph resulting of adding arc {pm, p• m}to N′where {pm, p• m} ∈ N 11 sccN′= Strongly connected component of N′ 12 Θ′= Θ 13 Θ = Throughput of sccN′ 14 end Algorithm 1: The regrowing strategy algorithm. in the set of places (transitions) of N. When there exist several identical critical cycles, i.e, with the same token to delay ratio, steps 5 and 11 choose any of them. In step 13, the throughput of the new bottleneck is taken as the new upper bound. In the next iteration, this new upper bound will be compared with the previous one in order to, depending on the degree of improvement achieved, either continue or finish the iteration process. Let us illustrate how the algorithm 1 works by applying it to the SMG depicted in Figure 6.2. The delays are δ1= 1.2, δ2= 1, δ3= 1.5, δ4=δ5= 1, δ6= 0.75, δ7= 1, δ8= 1.25 and δ9= 0.5, and the initial critical cycle is composed by {Pcb, Tcb}={{p2, p4},{t1, t3}}. The throughput bound of the critical cycle is Θcb = 0.370370 and the places which are connected (through a transition t∈T) to the critical cycle are p1and p14, having slacks µ(p1) = 0.1852 and µ(p14) = 1.0556. Hence, the place with minimum slack is p1. By regrowing the current bottleneck the new one is obtained, composed by {Pcb′, Tcb′}= {{p1, p2, p3, p4},{t1, t2, t3}}, which has a throughput of Θcb′= 0.322581, which is 12.9% lower than the throughput of the previously bottleneck {Pcb, Tcb}. Let us assume that ε= 0.001. As the relative difference between Θcb and Θcb′ is 0.12903 (as commented previously), the iteration process carries on. At this moment, the places connected to the current bottleneck are p10 and p14. The addition of the place p10 which has minimum slack produces a new bottleneck compounded of {{p1, p2, p3, p4, p6, p7, p8, p9, p10},{t1, t2, t3, t4, t5, t6, t7}} , being the new throughput Θ = 77 Section 6.3 6. Strategies for Upper Throughput Bound Computation in PNs Figure 6.2: Another MG example. 0.297914, which is an improvement of 7.647% with respect to the previous bottleneck {Pcb′, Tcb′}and 19.563% with respect to the original bottleneck {Pcb, Tcb}. Again, a new regrowing is possible because the relative difference is greater than ε. In this case, the candidate places to be chosen are p5,p11 and p14, which have slacks µ(p5) = 0.0556, µ(p11) = 0.9815 and µ(p14) = 1.0556. The addition of p5produces a new bottleneck with Θ = 0.297914, which is an improvement of 3.193% with respect to the previous bottleneck. For the next regrowing, the candidate places are p11,p14 and p15. By adding the place p11 (µ(p11) = 0.9815) we obtain a bottleneck whose relative throughput is lower than εwith respect to the previous bottleneck, thus, the algorithm finishes. In summary, after four iterations, the throughput bound obtained is 22.132% lower than the original Θ calculated by LPP in (6.6). 6.3.1 Experiments and Discussion In this section we test the algorithm given in previous section on a set of SMGs of the ISCAS benchmarking [Brglez et al., 1989]. After applying the regrowing strategy, the obtained results are discussed. Experimental Setting The structure of the SMGs to be analysed is obtained from the strongly connected components of the ISCAS graphs. The initial marking of each place is a natural number which 78 6. Strategies for Upper Throughput Bound Computation in PNs Section 6.3 is randomly selected in the interval [1 ...10]. The value of the δ(t) of each transition tis a real number randomly selected from the interval [0.1...1]. The overall strategy has been implemented on MATLAB1, while simulations of SMGs have been performed by the GreatSPN [Baarir et al., 2009] simulation tool using a confidence level of 99% and an accuracy of 1%. The simulations have been run in a machine with a Pentium IV 3.6GHz processor and 2GB DDR2 533MHz RAM. 1http://www.mathworks.com/products/matlab/ 79 Section 6.3 6. Strategies for Upper Throughput Bound Computation in PNs Graph Size % Size Regrowing Initial Θ |P| |T| |P′|(%) |T′|(%) steps thr. bound s1423 1107 792 79 (7.13%) 76 (9.59%) 3 0.236010 0.235213 (0.34%) s1488 1567 1128 91 (5.8%) 86 (7.62%) 6 0.201300 0.173127 (13.99%) s208 27 24 27 (100%) 24 (100%) 3 0.409390 0.377683 (7.75%) s27 54 44 19 (35.18%) 18 (40.9%) 1 0.305960 0.304987 (0.31%) s349 187 146 26 (13.9%) 24 (16.44%) 2 0.340320 0.327867 (3.66%) s444 92 68 14 (15.21%) 12 (17.64%) 2 0.181670 0.181260 (0.22%) s510 1038 734 45 (4.33%) 40 (5.45%) 5 0.133030 0.117819 (11.43%) s526 113 92 18 (15.93%) 16 (17.39%) 2 0.313490 0.305860 (2.43%) s713 271 208 11 (4.06%) 10 (4.8%) 1 0.428720 0.427840 (0.2%) s820 1162 848 40 (3.44%) 38 (4.48%) 2 0.161060 0.147483 (8.43%) s832 1293 948 84 (6.5%) 78 (12.04%) 5 0.239429 0.208798 (12.79%) s953 415 312 88 (11.36%) 82 (26.28%) 6 0.369214 0.337811 (8.50%) Table 6.1: Experiment results showing improvement of upper bound. 80 6. Strategies for Upper Throughput Bound Computation in PNs Section 6.3 Graph Original thr. ΘOriginal Θ% CPU time (s) CPU time (s) thr. thr. s1423 59948.980 8.283 0.222720 0.235270 5.63% s1488 36717.156 7.165 0.168760 0.172154 2.01% s208 0.492 0.492 0.376892 0.376892 0% s27 2166.002 0.954 0.305082 0.306166 0.35% s349 141.210 0.441 0.328340 0.327398 −0.28% s444 2278.231 0.205 0.181069 0.181260 0.11% s510 13669.814 1.358 0.117500 0.118040 0.46% s526 129.181 0.344 0.270010 0.305860 13.27% s713 628.503 0.405 0.411630 0.427840 3.94% s820 20775.811 0.788 0.144770 0.147699 2.02% s832 16165.863 1.914 0.196920 0.208873 6.07% s953 453.850 19.155 0.327910 0.338644 3.27% Table 6.2: Graph throughput and CPU time comparative. Experimental Results Table 6.1 shows the obtained results by our approach. The degree of accuracy for Algorithm 1 has been set to ε= 0.005. The first column is the graph name, followed by its size (number of places, |P|, and transitions, |T|). In the next column, it is shown the size of the net sccN′(|P′|,|T′|) produced by the algorithm. The column Regrowing steps shows the number of regrowing steps needed by the algorithm. The last columns of Table 6.1 show the initial upper throughput bound calculated by using the LPP (6.6), and the improved upper throughput bound, Θ, computed by the algorithm. Such a bound is computed by solving the Markov Chain associated to sccN′when it is handleable by the computer, and by simulation otherwise (see [Ajmone Marsan et al., 1995] for an example of Markov Chain analysis). The last column shows the percentage of improvement with respect to the original upper throughput bound. As it can be seen, our method is able to get a sharper upper bound than the original bound in a few regrowing steps, and the improvement varies from 0.2% (which indicates that the original upper bound is already very tight) up to 14%. We conjecture that the improvement depends on the structure of the graph. It is also worth mentioning that our approach uses a very low percentage of the size of the original graph, in most of cases this percentage is lower than 10%. Table 6.2 summarises a comparative between the original throughput bound and the improved upper throughput bound and between the CPU time needed for both computations. The first column is the graph name, followed by the CPU time consumed to calculate the original throughput and to calculate the improved upper throughput bound Θ. The 81 Section 6.3 6. Strategies for Upper Throughput Bound Computation in PNs 1 2 3 4 5 6 0.165 0.17 0.175 0.18 0.185 0.19 0.195 0.2 0.205 Regrowing steps Throughput Original upper thr. bound Improved upper thr. bound Real throughput Figure 6.3: Throughput of graph s1488. next columns are its original throughput and the improved upper throughput bound, Θ. The last column shows the relative error of Θ with respect to the original throughput. Due to the size of original graphs, the task of calculating their throughput is an unfeasible task in reasonable time. For this reason, the simulation parameters have been set to a confidence level of 95% and an accuracy of 4%. Owing to this reason, the values of Θ in Table 6.1 and in Table 6.2 can slightly vary. The negative relative errors are caused by such confidence level and accuracy degree. As it can be observed in the results shown in Table 6.2, the improved throughput bound varies from a value really close to the real throughput, to a value which is 13% over the real throughput. The latter case, which deserves further analysis, might be due to the existence of slow cycles far away from the critical cycle. Finally, Figure 6.3 shows the real throughput of the graph s1488 (solid line), the original upper throughput bound (dashed line, result of LPP (6.6)) and the improved upper throughput bound (dot-dashed line) in each step of the strategy. As it can be observed, the improved bound gets close to the real throughput after few steps. The main results that can be extracted from both tables can be summarised as follows:  a sharp upper bound is obtained after few regrowing steps; 82 6. Strategies for Upper Throughput Bound Computation in PNs Section 6.5 and transitions with low token to delay ratio. The bound is refined until no significant improvement is obtained. The outputs of both methods are an accurate estimate for the steady state throughput, and as a by-product, a subnet representing the bottleneck of the system. The first approach has been applied to a set of Stochastic Marked Graphs of different sizes, where the results show that few iterations suffice to obtain accurate bounds and that, in general, such bounds are due to relatively small subnet bottlenecks of the system. The second approach has been applied to a running example. Given that both techniques make intensive use of linear programming techniques and the number of required iterations is usually low, their complexity and computational time are also low. Such system bottlenecks represent the targets on which potential methods for performance optimisation might focus. 89 Chapter 7 Compensation of Throughput Degradation in FT Systems This chapter introduces the main contributions of this dissertation related to the compensation of throughput degradation caused by any activation of faults in a degradable system. Recall that degradable systems usually incorporate Fault-Tolerant (FT) techniques to mitigate the consequences of fault activations, then conforming a FT system. As it is claimed in Section 1.1, many of these FT systems are complex systems using shared resources, and can be naturally modelled as Discrete Event Systems (DES), more precisely as Resource Allocation Systems (RAS) [Colom, 2003]. Recall that we focus on FT systems using shared resources modelled as a special class of Petri nets (PNs) called Process Petri nets (PPNs). The outcome of this chapter have been mainly published in [Rodr´ıguez et al., 2013a] and [Rodr´ıguez et al., 2013b]. 7.1 Motivation The throughput of a FT system can be degraded (that is, it becomes lower) by the activation of faults, or the presence of errors or failures into the system. Thus, it is important to know the expected failure rate of the overall system when designing it, because some analysis might be carried out aiming at minimising the throughput degradation caused by faults. Compensation of a throughput degradation in a FT system can be performed by two main actions: either the number of items of resources is increased, or the timing of FT techniques is decreased. However, neither the number of resources (for example, the number of servers in a web system) can always be increased as desired, nor the timing of FT techniques can be performed in zero time (ideal time). In the real world, each project of a new system manages a budget, and this budget limits the number of resources that can be acquired and the time of FT techniques that can be improved. The major findings of this chapter are threefold. Firstly, we propose an iterative heuris91 Section 7.2 7. Compensation of Throughput Degradation in FT Systems tics to gauge in the best possible way the number of resources needed so that the overall system throughput is maximised for Stochastic Process Petri nets (SPPNs). The other results target to FT systems modelled as SPPN where the compositional PN models for FT (introduced in Section 4.2) are added: we propose an iterative algorithm to compute the number of resources that mitigate the impact of activation of faults in a FT system; and lastly, we propose an Integer Linear Programming Problem (ILPP) that minimises the cost of compensation needed for maintaining a given throughput in a FT system. 7.2 Maximising Throughput through Resource Optimisation In this section we propose a heuristic strategy to gauge the number of resources a system, modelled as a Process Petri net, should allocate. Our approach for resource optimisation is similar to Goldratt’s principle [Goldratt and Cox, 1986]: once the system’s bottleneck is identified, the associated resource is increased. 7.2.1 Calculating the Next Constraining Resource Let us recall LPP (6.6) to calculate an upper throughput bound of a SPPN. The most constraining p-semiflow, y, will have just one marked place in its support due to the net structure (see Definition 5). Assume that the marked place corresponds to a resource place (not the process-idle place), then given that yconstrains the throughput of the whole system, the addition of more instances to the resource place will result in an increase in the system throughput. At a certain moment, the resource becomes saturated and adding more instances does not improve the throughput. This occurs because the constraining p-semiflow has changed. Note that the upper throughput bound will linearly increase with the number of tokens of the resource place because it is the only place in kykhaving tokens and the equation y·Pre ·Dis linear. Hence, the resource r1contained in the support of the most constraining p-semiflow yr1, can be increased until yr1is no longer the bottleneck p-semiflow. Let m0∆be the initial marking vector m0with an increase α1of the resource r1, i.e., m0∆=(m0(p), p 6=r1 m0(p) + α1, p =r1 (7.1) The p-semiflow yr1is not the only constraining p-semiflow if the following equation holds: yr1·Pre ·D yr1·m0∆≤yr2·Pre ·D yr2·m0∆(7.2) where yr26=yr1is a p-semiflow. Note that the p-semiflow yr2will contain in its support the next most constraining resource r2, and, by definition, r16=r2. 92 7. Compensation of Throughput Degradation in FT Systems Section 7.2 The number α1of instances of the resource place r1, contained in the most constraining p-semiflow yr1, which need to be added to obtain the next constraining resource r2, contained in the next most constraining p-semiflow yr2, can be easily computed by solving the following LPP: minimum α1 subject to yr2·Pre ·D=yr1·Pre ·D yr2·C= 0 yr2(r1) = 0 (7.3) yr2·m0∆=yr1·m0∆ m0∆=(m0(p), p 6=r1 m0(p) + α1, p =r1 α1,yr2≥0 where yr1is the p-semiflow which contains r1in its support, yr2is the p-semiflow which contains r2in its support and m0∆represents the initial marking vector m0with the increase α1in r1. Constraints yr2·Pre ·D=yr1·Pre ·Dand yr2·m0∆=yr1·m0∆are both parts (dividend and divisor, respectively) of equation (7.2) equalled. Constraint yr2·C= 0 ensures that yr2is a left annuler of the incidence matrix, hence a p-semiflow of the net. Finally, constraint yr2(r1) = 0 is added to avoid a product of two optimisation variables (the variable α1and the variable yr2(r1) in equation yr2·m0∆=yr1·m0∆). Moreover, the variable α1∈R≥0therefore, the linearity of the optimisation problem is ensured. Both α1and the next constraining p-semiflow yr2are obtained when the LPP is solved. Note that the increase of a resource r1does not affect the ratio y·Pre ·D y·m0 of any other minimal p-semiflow ywhich contains another resource in its support (see definition of the process Petri nets class in Section 2.1). Notice that, as in Section 6.4, a LPP is used to solve a problem that deals with integer values as the number of resources. This relaxation of the real domain remarkably decreases the complexity of the approach (the complexity of solving a LPP is polynomial), at the cost of some loss of precision in the results. Once both α1and the next constraining p-semiflow yr2are obtained, LPP (7.3) can easily be extended to calculate the next constraining resource and the number of tokens, i.e., instances, to be increased of both places: 93 Section 7.2 7. Compensation of Throughput Degradation in FT Systems minimum α1+α2 subject to y′·Pre ·D=yr1·Pre ·D y′·C= 0 y′(r1) = 0,y′(r2) = 0 (7.4) y′·m0∆=yr1·m0∆ y′·m0∆=yr2·m0∆ m0∆=   m0(p), p 6∈ {r1, r2} m0(p) + α1, p =r1 m0(p) + α2, p =r2 α1, α2,y′≥0 where m0∆represents the initial marking vector m0with the increase α1of place r1and the increase α2of place r2, and yr1(yr2) is the p-semiflow which contains r1(r2) in its support. As in LPP (7.3), constraint y′·C= 0 ensures that y′is a left annuler of the incidence matrix, and hence y′is a p-semiflow of the net. Besides, constraints y′(r1) = 0 and y′(r2) = 0 ensure linearity of the optimisation problem. Constraints y′·m0∆=yr1·m0∆,y′·m0∆= yr2·m0∆are the key of this LPP because both values of α1and α2can be obtained from these equations. Note that y′·Pre·D=yr2·Pre·Dis not a constraint in LPP (7.4). This is a consequence of the result of LPP (7.3): from the latter LPP where r1is calculated, it is imposed that yr2·Pre ·D=yr1·Pre ·D. The addition of this constraint does not add new information to LPP (7.4). LPP (7.4) can be generalised for more resources, as is shown in step 5 of the Algorithm 3. 7.2.2 An Iterative Strategy for Resource Optimisation This subsection presents an iterative heuristics that aims at maximising the throughput by increasing the number of resources appropriately. The main idea of the strategy is to estimate the inflexion points where the constraining p-semiflows change, and hence to estimate the increase in resources needed. More precisely, each unit of a resource has an associated cost and the strategy establishes how to spend a given budget such that the throughput is maximised. The strategy ends either when there is no budget to spend, all resources have been dimensioned, or the last computed p-semiflow indicates an increase in the process-idle place. Algorithm 3 shows the resource optimisation heuristics. For the input, the algorithm needs the SPPN system to be analysed, hS,s,ri, the set of resources and the process-idle place of the system, Rand p0(respectively), the assigned budget to be spent, budget, and 94 7. Compensation of Throughput Degradation in FT Systems Section 7.2 Input:hS,s,ri, R, p0, budget, c Output:n 1Calculate initial bottleneck y1by solving LPP (6.6) 2k= 0; cost = 0; n′=0 3while cost < budget and k6=|R|and kyk+1k∩{p0}=∅do 4k=k+ 1; cost′=cost;n=n′;A={p|p∈P, p ∈ kyj∩Rk},∀j∈ {1. . . k} 5 minimum k X j=1 αj subject to yk+1·Pre ·D=y1·Pre ·D yk+1·C=0 yk+1·m∆ 0=yj·m∆ 0,∀j∈ {1. . . k} m0∆=m0(p) + αj, p ∈A m0(p), otherwise yk+1(p) = 0, p ∈A yk+1, αj≥0,∀j∈ {1. . . k} 6cost = 0; n′=0 7for αj,∀j∈ {1. . . k}do 8rj=kyjk∩R;n′ j=⌈αj⌉ 9cost =cost +⌈αj⌉·ci 10 end 11 end 12 if k≤ |R|and cost ≤budget then 13 n=n′ 14 end 15 if k < |R|and cost ≤budget and kyk+1k∩{p0}=∅then 16 assignRestOfBudget(budget −cost, hS,si, R, c, n) 17 end Algorithm 3: The resource optimisation heuristics. 95 Section 7.2 7. Compensation of Throughput Degradation in FT Systems the vector of cost c, which assigns a cost cito each resource ricontained in R. The output is the number of items nineeded to increase each resource ri. Firstly, an upper throughput bound y1of hS,s,riis calculated according to LPP (6.6). After that, the iteration process (steps 3–10) is repeated either until the last assignment of resources has spent the available budget, or until all resources have been dimensioned, or until the last computed resource to be increased matches with the process-idle place. Step 5 calculates, in each iteration, the number of items of a resource which need to be increased to obtain the next restrictive resource. It should be noted that the LPP in step 5 is a generalisation of LPP (7.3). After that, the cost of increasing such a number of instances of the resources is computed. Note that the ceiling integer of the value αjis taken as the result. There are two reasons for this: firstly, we assume that the number of instances of the resources must be a natural number; and secondly, when the resource is not saturated it will still be the restrictive resource. Finally, step 12 checks whether all the resources have been assigned and that the cost of new resources does not exceed the given budget. When these conditions are fulfilled, the last resource assignment is taken as the valid one. Step 15 checks whether there is a resource that has not been assigned, the last resource assignment does not exceed the given budget and the last computed p-semiflow does not contain the process-idle place. When these conditions are fulfilled, the remaining budget may be spent on increasing the system throughput. A procedure is invoked (assignRestOfBudget, step 16) for spending the rest of the assigned budget to increase the resources as much as possible. Note that the assignment of the remaining budget is an NP-problem, similar to the Bounded Knapsack Problem (BKP) [Kellerer et al., 2004]. To solve it, several heuristics can be used. For instance, a “round-trip” algorithm which tries to increase all the resources per round until it cannot longer increase them. Let us illustrate the use of this strategy through the packet-routing algorithm example, depicted in Figure 6.4. Suppose an initial marking of nP = 30, nT = 2 and nS = 2, and an initial budget of $30,000 dollars. The deployment of each new thread costs $5,000 dollars, while a new filtering-thread deployment has a price of $700 dollars. The initial bottleneck is ky1k ∩ R={p2}, that is, the subnet associated to the threads. Therefore, this result gives us the following information: to attend to 30 packets whose think time follows an exponential distribution of a mean of 30 minutes, more threads are needed. The LPP at step 5 gives, in the first iteration, the increase in new threads needed, α1= 2.666, and the new constraining p-semiflow, which corresponds to the use of filtering-threads. So, at least three new threads (⌈α1⌉) are needed to attend to the incoming packets. As the cost of deployment of a new thread is $5,000 dollars and the initial budget is $30,000 dollars, the new deployments can be done and there is still money which remains to be spent, so a new iteration can take place. The LPP at step 5 gives, in the second iteration, the values of α1= 3.6752 and α2= 0.4322. Hence, to attend to the packets, four new threads and one more filtering-thread are needed. As the cost of these are $20,700 dollars in total, the increase in resources can be carried out. Now, the unassigned budget 96 7. Compensation of Throughput Degradation in FT Systems Section 7.3 is $9,300 and we can continue increasing both resources in parallel. Indeed, the relation between both resources is known thanks to the equalities of the ratios. In this case, even though part of the budget remains to be spent, the new constraining p-semiflow contains the process-idle place, that is, the place representing packets. Thus, the resources of the system (threads and filtering-threads) have been optimally calculated to attend to 30 packets whose think time follows an exponential distribution of a mean of 30 minutes. In this way, the algorithm has computed that to attend to the customers, at least four more threads and one filtering-threads are needed. Note that it may happen that the LPP at step 5 returns the p-semiflow containing in its support the process-idle place in the first iteration. This would indicate that the system has enough resources to attend to such a number of customers with such a think time. Therefore, the strategy is also able to compute when a system with an initial configuration is able to support the estimated workload, or otherwise, to compute the number of instances of resources needed to be able to support such a workload. 7.3 Minimising Cost of Compensating Throughput Degradation This section introduces an iterative strategy that computes the number of resources needed to maintain a given upper throughput bound in a degradable system where our proposed FT models are added (see Section 4.2). Such a strategy is presented in Algorithm 4. As input, it needs the description of the PN model with the FT techniques added to it with the initial marking and the vector of service times of transitions, hN,m0, δi; the upper throughput bound Θ before adding the FT techniques; and the set YF T of minimal p-semiflows that are modified after adding the FT techniques. As output, it returns the initial marking m′ 0such that the upper throughput bound Θ′of the FT system is greater than or equal than Θ. Input:hN,m0, δi,Θ,YF T Output:m′ 0 1m′ 0=m0 2for yi∈YF T do 3m′ 0(ri) = maximum(m0(ri),⌈(yi·Pre ·D)·Θ⌉) 4end Algorithm 4: An iterative algorithm to compute initial marking needed to maintain a certain upper throughput bound with a probability of error. Algorithm 4 works as follows. It iterates in the content of the set YF T of minimal psemiflows that have been modified when adding a proposed FT model. For each minimal p-semiflow yi∈YF T , the value of the initial marking for associated resource riis com97 Section 7.3 7. Compensation of Throughput Degradation in FT Systems 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0 20 40 60 80 100 120 Probability of error Initial marking Initial marking nP Initial marking nT Initial marking nS Figure 7.1: Results of initial marking with respect to probability of error. puted as the maximum of the previous initial marking of the resource (i.e., m0(ri)) or the ⌈(yi·Pre ·D)·Θ⌉. The latter equation comes from solving Θ = m0(ri) yi·Pre ·D. The ceiling is needed because m′ 0(ri)∈N. Let us apply the Algorithm 4 in the Petri net example depicted in Figure 4.6 (the packetrouting algorithm). The previous upper throughput bound is Θ = 0.470588, and the set of minimal p-semiflows that are modified after adding isolation FT is YF T ={y′ 1,y′ 2,y′ 3}. For a given initial marking m0(p0) = 10,m0(p2) = 2,m0(p7) = 2, Algorithm 4 returns as solution: m′ 0(p0) = m0(p0) = 10,m′ 0(p2) = 3,m′ 0(p7) = 4. That is, it is needed another thread and two more filtering-threads to compensate a 20% of errors (and a 5% of them deriving in solid faults) using reconfiguration as FT technique. We have plotted in Figure 7.1 the initial marking needed to support the given throughput of Θ = 0.470588 varying the probability of error re, re∈[0 ...1], taking steps of 0.01. The dotted line is the initial number of tokens of p0(packets, nP), the solid line corresponds to the initial number of tokens of p2(threads, nT ) and the dashed line is the initial number of tokens of p7(filtering-threads, nS). The results show that the number of packets and threads remain more or less equal, i.e., there is no need to increment too much units to be able to maintain the given throughput, even with high probability of errors. However, the number of filtering-threads needed increases rapidly with respect to the probability of error. 7.3.1 An ILPP for Minimising the Cost of Compensating In this section, we present an Integer-Linear Programming Problem (ILPP) that minimises the cost of compensating throughput degradation caused by the presence of errors. 98 8. Case Study: a Secure Database System Section 8.1 WS-SecurityToken WS-CoordinatorServiceWS-PolicyService WS-DBapplicationWS-ApplicationWS-Requester Request doOperation() initialise() validate(encRequest) transmit(request) decrypt(encRequest) requestAccess(encRequest) processRequest() validate(request) parseOutputFormat() pack() getToken() sign&encrypt(result) transmit(encResult) WSDone() initProcessing() unpack&validate() generateToken() token initProcessing() unpack&validate() generateToken() getToken() validate(encResult) decrypt(encResult) display(result) DBwrite() retrieveData() checksParams() sign&encrypt(request) DBread() retrieveData() newAccess(request) «gaRelStep» {resUnits=1} «gaAcqStep» {resUnits=1} sd SDBS «gaScenario» {respTime=(value=$rTime; unit=ms; statQ=mean; source=calc)} «gaStep» {hostDemand= (value=$initProc1,unit=ms, statQ=mean, source=est)} «gaStep» {hostDemand= (value=$genToken,unit=ms, statQ=mean, source=est)} Figure 8.2: SDBS Update Customer’s Data scenario. 105 Section 8.1 8. Case Study: a Secure Database System Transition Method Value(s) T0newAccess() 0.2ms T2, T8, T10, T49 $ delayNet 2.5ms T13, T16, T19, T23, $ intranetLag 0.2ms T36, T41, T46 T26, T29, T32, T34 $ secIntraLag 0.5ms T4, T43 initProcessing() 1ms T5, T44 unpack&validate() 0.1ms T6, T45 generateToken() 0.5ms T9, T48 sign&encrypt() 0.8ms T12 initialise() 0.3ms T15, T22, T52 validate() 0.3ms T18, T54 decrypt() 1ms T28, T33 DBread() 0.2ms T30 checkParams() 0.6ms T31 doOperation() 0.2ms T39 parseOutputFormat() 0.3ms T40 pack() 0.1ms T55 display() 1.5ms (a) Activity times Place Meaning Value(s) p0No. users 15,20,21,22,23 . . . 30 p2No. request capacity ≥m0(p0) p5No. security hosts 5 p13 No. policy hosts 10 p24 No. coordinator hosts 10 p29 No. application hosts 5 p32 No. DB hosts 2 (b) Initial number (no.) of resources Table 8.1: Experimental parameters. 106 8. Case Study: a Secure Database System Section 8.1 Figure 8.3: Petri net of the SDBS. Resource places are depicted in dark grey, whilst processidle place in light grey. Distefano et al., 2011], and can be carried out by several tools, such as ArgoPN, ArgoPerformance [Distefano et al., 2011] or ArgoSPE. In this case, ArgoSPE tool1has been chosen to carry out this transformation because the ArgoSPE output net format is compatible with GreatSPN tool [Baarir et al., 2009] input net format (used later for analysis in the experiments). Note that as software engineers usually work with UMLs diagrams, ArgoSPE is useful in this context for obtaining the PN models we need to work with. Each resource annotated in Figure 8.1 is represented by a place in the PN: the resource places (depicted in dark grey) are p7(security service), p18 (policy service), p26 (coordinator service), p28 (application service) and p31 (database service), while the process-idle place (user’s requests, depicted in light grey) is represented by place p0. As in the running example of Figure 4.5, we consider that there is a place p′ 0with the same initial marking that p0, thus it becomes implicit and it is not considered for the analysis (indeed, we omitted it in the Figure 8.3). The number of instances of each resource is summarised in Table 8.1, and they will be represented by tokens in the respective place. The acquire (release) of a resource has been transformed into an immediate transition with an input (output) arc. For example, transition t3represents the acquire of the security host, while t7represents the release of such a resource. Each one of the activities, self-messages in Figure 8.2, has been transformed into an exponential transition in the Petri net with its corresponding duration (given in Table 8.1). Each message exchanged through a net among two resources (e.g., getToken()) gives rise in the PN to an exponential transition (e.g., T2) whose delay is that of the net involved (e.g., $ delayNet). We have assumed that the operations/messages needed for establishing 1https://argospe.tigris.org 107 Section 8.2 8. Case Study: a Secure Database System communication through the secure intranet are more expensive (in computing time terms). For this reason, we have set an upper delay for the secure intranet ( $ intranetLag) than for the insecure intranet ( $ secIntraLag). For simplicity, we have assumed the same delay for each message on the intranet communication independent from its size. process-idle place (p0). Its values are shown in Table 8.1. The throughput of the system will be calculated by exact analysis when it can be computed, or by simulation otherwise. 8.2 Experiments and Discussion In this section we test our approach by performing a set of experiments in the Petri net that accurately represents the SDBS. After applying our approach, the results obtained will be discussed. 8.2.1 Performance Estimation We have carried out the regrowing strategy (Algorithm 2, Section 6.4.1) to estimate the throughput of the SDBS system with a different number of requests. The overall strategy has been implemented in MATLAB, while the throughput computation of the SDBS has been performed with the GreatSPN tool. The GreatSPN tool has been run in an Intel Pentium IV 3.6GHz with 2GiB RAM DDR2 533MHz host machine. Table 8.2 shows the results obtained in the set of experiments with the parameters set as described above. The first column indicates the number of requests, followed by the number of regrowing steps. We have applied the name regrowing step to each iteration of the loop of the Algorithm 2. For each number of requests considered in the experiments, we have simulated the whole system. Such results are indicated in the first row of each experiment. The next column shows the size of the bottleneck (in terms of the number of places and transitions) produced by the algorithm and its percentage with respect to the total size. Then, the result of the upper throughput bound computed by the algorithm is shown. Such a bound is computed by solving the underlying Markov Chain when this is computationally feasible [Ajmone Marsan et al., 1995] or by simulating the net otherwise. Note that in the case of simulation, the upper throughput bound value is the mean of the simulation values, and the real upper throughput bound value is within an interval of ±4% with a confidence level of 95%. The next two columns show, in the first place, the percentage of increasing/decreasing improvement of one bound with respect to the previous upper throughput bound, and secondly, the accuracy of the computed bound with respect to the throughput of the whole system. The negative relative errors are caused by the confidence level and degree of accuracy used in the experiments. Finally, the last column shows the execution time consumed for computing the upper throughput bound of the PN system. We have distinguished whether the computation of the upper throughput bound has been achieved by exact analysis (†symbol) or by simulation (no symbol). 108 8. Case Study: a Secure Database System Section 8.2 Number of Regrowing Size ThroughPartial Bound Execution requests step |P|(%) |T|(%) put improvement error time (s) 15 (full system) 61 (100%) 56 (100%) 0.525685 >+1 day (initial bound) 56 (91.80%) 56 (100%) 0.551637 - 4.7045% 5.87s 1 57 (93.44%) 56 (100%) 0.533037 3.3718% 1.3792% 122.94s 2 58 (95.08%) 56 (100%) 0.522379 1.9995% −0.6330% 751.20s 3 59 (96.72%) 56 (100%) 0.522346 0.0063% −0.6393% 34256.97s 20 (full system) 61 (100%) 56 (100%) 0.652313 >+1 day (initial bound) 56 (91.80%) 56 (100%) 0.735930 - 11.3621% 5.80s 1 57 (93.44%) 56 (100%) 0.675957 8.1493% 3.4979% 302.60s 2 58 (95.08%) 56 (100%) 0.637812 5.6431% −2.2735% 300.17s 3 59 (96.72%) 56 (100%) 0.637860 −0.0075% −2.2658% 3166.09s 21 (full system) 61 (100%) 56 (100%) 0.671806 >+1 day (initial bound) 9 (14.75%) 9 (16.07%) 0.740741 - 9.3063% 0.18s† 1 57 (93.44%) 56 (100%) 0.697133 5.8871% 3.6331% 826.82s 2 58 (95.08%) 56 (100%) 0.653556 6.2509% −2.7924% 280.46s 3 59 (96.72%) 56 (100%) 0.653116 0.0673% −2.8616% 2216.06s 22 (full system) 61 (100%) 56 (100%) 0.687808 >+1 day (initial bound) 9 (14.75%) 9 (16.07%) 0.740741 - 7.1459% 0.18s† 1 57 (93.44%) 56 (100%) 0.713762 3.6422% 3.6362% 2763.5s 2 58 (95.08%) 56 (100%) 0.666148 6.6709% −3.2515% 502.95s 3 59 (96.72%) 56 (100%) 0.667222 −0.1612% −3.0853% 1502.62s 23 ...30 (full system) 61 (100%) 56 (100%) 0.700056 >+1 day (initial bound) 9 (14.75%) 9 (16.07%) 0.740741 - 5.4925% 0.18s† 1 14 (22.95%) 13 (23.21%) 0.740733 0.0011% 5.4915% 0.262s† Table 8.2: Experimental results for number of requests {15,20,21,22,23 . . . 30}. 109 Section 8.2 8. Case Study: a Secure Database System Figure 8.4: Throughput of the SDBS with variable number of users. Note that in all cases the computation of the throughput of the whole system takes longer than one day of simulation time to finish, even though the evaluated system is an academic example. For larger systems, simulations may need a long convergence time, and therefore the usefulness of bounds computation is proved. The degree of precision (ε) of the Algorithm 2 has been set to 10−3. As can be observed, the initial bottleneck with the lowest number of requests (15, 20) corresponds to the underlying state machine (this is the result of removing resource places from the net in Figure 8.3). Again, this result indicates that the system’s resources are well-dimensioned for attending to such a number of requests. In the case of 15 requests, in each iteration step there is no significant improvement (near to 6% in two iterations) and the regrowing strategy finishes in few steps. However, the greatest improvement occurs when the requests reach 20 units. In such a case, the first regrowing achieves an improvement near to 8%, reaching over 13% in the next iteration. It is interesting to note what happens when the requests are increased to 21. For this value, the initial bottleneck is produced by one of the system’s resources (specifically, the number of DB application hosts). This implies that the throughput bound of the system will remain the same for any number of requests over 21 (see Average thr. of first regrowing step for a number of requests greater than 21). In other words, requests will start waiting to be attended to if their number is equal to or higher than 21. Besides, note that when the number of requests is greater than 23, in the second iteration step there is an improvement in the upper throughput bound lower than 10−3%. As stated previously, the most significant improvement occurs when the number of 110 8. Case Study: a Secure Database System Section 8.2 requests is 20. In just one iteration step, the initial throughput bound is improved by a value of nearly 8%. This indicates that the proposed method is more useful (i.e., it achieves a significant improvement in the upper throughput bound in few iterations) if the resources and requests are more well-balanced. Besides, it should be noted that the simulation of the whole PN becomes unfeasible for large systems, as indicated by the execution time. The throughput results have been plotted in Figure 8.4. The throughput is drawn for each number of requests and for each step. Besides, the result of LPP (6.6) has also been drawn (dotted line). The LPP values match the throughput values of the initial bottleneck. As expected, the result of solving the LPP (6.6) (dotted line) is an upper bound of all the rest of the values. As can be seen, the improvement in the upper throughput bound for each regrowing step is almost insignificant in the case of requests lower than 20 or greater than 25. While the number of requests is near to 20, the relative difference between the throughput of the initial upper throughput bound and the first iteration becomes greater, reaching its maximum in the case of 20 requests. After that point, it becomes lower even tending towards a minimal difference near to zero (see, for instance, the case of 30 requests). Finally, the execution time shown in last column in Table 8.2 indicates that the bigger the size of the net, the longer it takes to complete the simulation. Note that small additions to the net (i.e., just one place) normally cause an execution time of one or two orders of magnitude greater than previous executions. However, the improvement of the upper throughput bound is not so significant as to justify such an amount of execution time. The main conclusions that can be extracted from both experiments can be summarised as follows:  there exists a number of requests (inflexion point) at which the initially most restrictive p-semiflow of the system changes. Around such an inflexion point, the accuracy of the initial throughput bound is low. This occurs because when the slowest psemiflow of the system is much slower than the others, it predominates over them and the system throughput is determined by the throughput of such a p-semiflow. The initial throughput bound is therefore usually quite accurate. However, when several p-semiflows have similar speeds, none of them predominates over the others. Hence the initial throughput bound, which considers just one p-semiflow, is less accurate;  the improvement in the upper bound is specially significant in the proximity of the inflexion point. As future work, we aim to continue researching into performance estimation based on performance bounds, seeking to obtain some quality bound characterisation. The use of LP problems and the token/delay ratio between p-semiflows in a PN system could be useful for this goal. As the reader can imagine, it would be of great interest to be able to compute such inflexion points directly. This is the goal in the next set of experiments. 111 Section 8.2 8. Case Study: a Secure Database System Figure 8.5: Different resources configurations and their associated cost. 8.2.2 Resource Optimisation Maximising Throughput For these experiments, the number of requests has been set to nRequests = 100, whilst the initial number of resources remains unchanged: 5 security hosts, 10 policy hosts, 10 coordination hosts, 5 application hosts and 2 DB application hosts (summarised in Table 8.1). Let the budget be $20,000 and the costs per resource be: $3,500 per security host (represented by place p7), $1,000 per policy host (place p18), $2,000 per coordinator host (place p26), $500 per application host (place p28) and $500 per DB application host (place p31). The prices of the hosts reflect either the cost of the physical hardware or the cost of reimplementing the services. Applying the optimisation strategy introduced in Section 7.2.2, the initial restrictive resource is the number of DB application hosts, $nDBapps (initial tokens of place p31). The algorithm in Figure 3 computes the new restrictive resource, the security hosts, and the number of DB application hosts needed to be increased (which is just one host). As the cost is $500 per DB application host and there is a budget of $20,000, the increase is possible. The strategy continues looking for the next restrictive resource. The second iteration gives as a result the new restrictive resource (application host) and the new instances of DB application and security hosts, respectively, 2 and 5 units. The increase of such resources has a cost of $18,500, so it can be afforded. The new restrictive resource after the third iteration is the number of coordinator hosts. This time, it is necessary to increase the security hosts by 6 units, the DB application hosts by 3 units and the application hosts 112 8. Case Study: a Secure Database System Section 8.2 by 1 unit with respect to the initial configuration. This last assignment has a cost greater than the initial budget, so the iteration process finishes and the previous assignment is taken as the valid one (5 security hosts and 2 DB application hosts). Moreover, there is no possibility of spending the rest of the budget (which amounts to $1,500) Therefore, the optimisation strategy ends. Hence, with the initial configuration and the given budget, the number of security hosts needs to be increased by 5 units and the number of DB application hosts by 2 units in order for the system resources to be optimally distributed and the throughput maximised. Figure 8.5 plots the upper throughput bound (dashed line) of each configuration of resources, its associated cost in dollars (dotted line) and the total assigned budget (solid line). Initial cfg. (configuration) is 5 security hosts, 10 policy hosts, 10 coordination hosts, 5 application hosts and 2 DB application hosts. Cfg. 1 refers to the increase by one unit of DB application hosts, whilst Cfg. 2 indicates the last assignment of resources computed: the increase of 5 security hosts and of 2 DB application hosts. Finally, Cfg. 3 refers to the configuration which cannot be afforded with such a budget ($20,000): an increase in the security hosts by 6 units, the DB application hosts by 3 units and the application hosts by 1 unit with respect to the initial configuration. As can be observed in Figure 8.5, the cost of the last resources configuration exceeds the assigned budget, so the solution for the resource distribution is the previous configuration. The evolution of the upper throughput bound is worth remarking. With the initial configuration, the upper throughput bound is Θ = 0.740740. In the first configuration, the upper throughput bound increases by 0.75% (Θ = 0.746271), while in the second configuration it increases by almost 100% (Θ = 1.470598). Finally, with the third configuration the upper throughput bound increases by 9.68% (Θ = 1.612920). 8.2.3 Resource Optimisation Minimising Cost while Adding FT Techniques In this section, we consider the addition of a Fault-Tolerant (FT) technique PN-based model as described in Section 4.2, and we apply to the combined model the resource optimisation strategies presented in Section 7.3. Consider that transition that represents an operation on data after reading the DB, T31, may fail with a probability of 0.15. We decide to add a reinitialisation FT technique F T1, without compensation phase and with a concurrent error detection that takes, on average, δ(T1 detect) = 0.5ms. The recovery time, i.e., the time needed for reconfiguring DB service takes, on average, δ(T1 rec) = 20ms. Lastly, place p36 (the one before faulty transition T31) is labelled as p36|rtn. The upper throughput bound of the system is, before adding the FT technique, Θ = 1.481481, and it is associated to the minimal p-semiflow of p32 – i.e., WS-DBApplication. When adding the FT technique described, the minimal p-semiflows that are modified correspond to the ones that use T31, i.e., yp0,yp2,yp29 and yp32 , and the upper throughput 113 Section 8.3 8. Case Study: a Secure Database System bound decreases near to a 133.98%, that is, Θ′= 0.633147 and it is related as well to WS-DBApplication. Let us apply now Algorithm 4 to compute the initial marking needed to compensate the throughput degradation. The minimal p-semiflows under study here are: y′ p0= yp0∪ {•T31, T• 31, p1 4},y′ p2=yp2∪ {•T31, T• 31, p1 4},y′ p29 =yp29 ∪ {•T31, T • 31, p1 4},y′ p31 = yp31 ∪ {•T31, T• 31, p1 4}(the other p-semiflows y′′ p0,y′′ p2,y′′ p29 ,y′′ p31 are not of interest due to δdetect <=δ31). The computation of value of y1 pi·Pre ·Dis, respectively, 41.9520,41.6557,10.3965,9.3594. Thus, the solution of Algorithm 4 is m′ 0(p0) = 100,m′ 0(p2) = 50,m′ 0(p29) = 11,m′ 0(p31) = 10. That is, the number of WS-Application (p29) and WS-DBApplication (p31) must be incremented to 11 and 10 units, respectively, to maintain the given throughput of Θ = 1.481481 and a probability of error of 0.15. If resources are incremented as it is given by the solution of this algorithm, the new upper throughput bound has a value of Θ′= 1.567476. Let us consider that the addition of new resources has some associated cost, more precisely, the cost of adding new instances of any host service is $350 each (for instance, because new licenses for deploying more virtual servers must be purchased). In the case of recovery method, it can be improved having a cost, on average, of $250 per each millisecond, and the minimum required time for recovering is 5ms (i.e., δmin(Trec) = 5ms). With this configuration, we apply now the proposed ILPP (7.6) for computing the minimal cost that compensate a probability of error of 0.15. The result of applying ILPP (7.6) is that 4 more resources of WS-Application (p29), 5 more resources of WS-DBApplication (p32) and recovery time must be decremented in 2ms. The cost associated to these actions is $3,650. After applying these changes, the upper throughput bound is Θ′′ = 1.500441, which represents an improvement near to 1.28% of the previous upper throughput bound Θ. Note that as the number of resources and the timing must be natural numbers, we will always obtain an upper throughput bound in the FT system where results of ILPP (7.6) are applied (slightly) better than in the original system model. In summary, the solution of Algorithm 4 has an associated cost of $3,850, because 11 more resources must be added, whilst the solution giving by minimising cost through ILPP (7.6) costs $3,650. 8.3 Concluding Remarks The formalism of Petri nets allows one to model the behaviour of a large class of artificial systems in which resources are shared by the different tasks. The performance of these systems, which is usually measured as the number of completed operations per time unit, is often a system requirement. Unfortunately, in most cases of interest it is not possible to compute the exact performance of a system in a reasonable time due to the state explosion problem inherent to large discrete systems. To overcome this issue, performance estimation 114 9. Case Study: an E-Commerce System Section 9.2 Resource No. instances webServer 50 dispatcher 40 userController 30 database 20 webServer (replicas) 5 watchDog 5 Table 9.1: Experimental parameters: system resources and number of instances. Method name/UML-SD Duration (ms) login 0.5 checkLoginCustomer 0.5 checkLoginDB 0.5 checkCustomerItemDB 2 sendUserCredentials 0.5 verifyCustomerCredentials 12.4 acceptedCustomers 0.5 loginOK 0.5 UML-SD DSGeneration 107 UML-SD DSVerification 68 UML-SD Encryption 117 UML-SD Decryption 117 Table 9.2: Experimental parameters: execution times of system actions. 121 Section 9.2 9. Case Study: an E-Commerce System «secaAttackGenerator» {attack=(occurrenceProb= (value=$attRate, source=est); type=Active; class=ResourceConsuming; kind=Flooding; objective=Denial-of-Service)} «gaStep» {hostDemand= (value=$cusRate; unit=ms; statQ=mean; source=est)} «gaStep» {hostDemand= (value=2; unit=ms; statQ=mean; source=mea)} «gaStep» {hostDemand= (value=12.4; unit=ms; statQ=mean; source=mea)} «gaStep» {hostDemand= (value=0.5; unit=ms; statQ=mean; source=mea)} opt ref D-./0/345 ion ref E0 6 ryption ref D / 63785 ref D-9/3:; 64 tion =3/>:?5/3/@BF?5GH/3I ref -S:5 6JKL/3M 4:a:0> @ N O @454N 4?/ F 6OF?/3 Contr G aa/3 @O@:?8 456J/3 S ?O S/ N-/3L /3 BF?5GH/3 PO aG>:0Q 3 ) PRTRURTO aG>:0K V PRTRUO466 / 85/@BF?5GH/3 2.1.2: L /3: W7X?/3B r /@/05:4a ?Q 3Y 43 Z ?/0@ X ?/3 Cr /@/05:4a ?Q 43 ) 2.1.1.1: c J/ 6\BF?5GH/3]5/HD^Q 3 Z 2.1.1: ch / 6\_G>:0D^Q 3 Z 2.1: 6J/ 6\_G>:0BF?5GH/3Q 3 Z 1.1: aG>:0 Q 3Z TO aG>:0`/bF/?5Q 3 ) «gaStep» {prob=0.85} 2.1.1.2: sd pr G 6/??`/bF/?5 Figure 9.2: ECS SMs-FTTs-Enabled Application Model. 122 9. Case Study: an E-Commerce System Section 9.2 a probability of 0.3 and 0.7, respectively. As it is shown in Figure 9.1(a), a new purchase may have two different scenarios, each one with different duration. 9.2.2 Experimental results The experimentation has been conducted while considering the following scenarios: (i) the Performance-Annotated Application Model (see Figure 9.1); (ii) the FTTs-Enabled Application Model (SoF), i.e., without SMs but with SwitchOverFailing FTT only; (iii) the FTTs-Enabled Application Model (P&R), i.e., without SMs but with Ping&Restore FTT only; (iv) the SMs-FTTs-Enabled Application Model (SoF), i.e., with SMs and the SwitchOverFailing FTT only (see Figure 9.2); (v) the SMs-FTTs-Enabled Application Model (SoF + P&R), i.e., with SMs and both FTTs. The transformation from UML software models to GSPN performance models has been carried out by ArgoSPE [G´omez-Mart´ınez and Merseguer, 2006] tool. We have used the PeabraiN simulator (introduced in Chapter 11), which is a PNML-compliant tool and allows to simulate GSPNs in transient mode. We have simulated an execution of the system of 2 hours with the experimental parameters reported in Tables 9.1 and 9.2. Figure 9.3 shows the experimental results. Figure 9.3(a) reports the system throughput (transactions completed per unit of time) while varying attack rates from 0.05 to 0.4. When we consider attacks, the system throughput of the performance-annotated application model quickly drops down, reaching values lower than 10−4. In fact, when the request is an attack but it is not detected, then the server collapses and it needs to be repaired, and such procedure lasts for 30 minutes. On the contrary, when FTTs are enabled, the system is able to mitigate the effects of attacks, maintaining a certain level of server availability. However, the throughput of the FTTs-Enabled Application Model (SoF) is greater than the throughput of the FTTsEnabled Application Model (P&R). Finally, we can observe that when we consider a scenario with SMs and both FTTs then the throughput outperforms any other combination. Ultimately, if the system is subjected to an increasing probability of attacks, then a better throughput is achieved while considering SMs and both FTTs, rather than considering FTTs in an isolated way. Figure 9.3(b) reports the system throughput while varying the incoming customers rate from 5 to 40, and with a fixed attack rate of 1%, in all the considered scenarios. As it is shown, the throughput in the performance-annotated application model and with the P&R FTT only remains quite constant despite the increasing of the incoming customers rate. The throughput in the latter scenario, however, outperforms the former. In the rest of scenarios, the more incoming customers, the more throughput is achieved. The highest throughput is obtained in the scenario where SMs and both FTTs have been added. These results show that such scenario, i.e., SMs-FTTs-Enabled Application Model (SoF + P&R), is able to successfully support the increasing rate of incoming customers. We can conclude that the conjunction of both FTTs techniques is beneficial for the 123 Section 9.2 9. Case Study: an E-Commerce System 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0 0.5 1 1.5 2 2.5 3 3.5x 10 f 3 Attacks (%) Throughput Application model FTTs g Enabled Application model (SoF) FTTs g Enabled Application model (P&R) SMs g FTTs g Enabled Application model (SoF) SMs g FTTs g Enabled Application model (SoF + P&R) (a) Throughput of the system while varying attacks rate. 5 10 15 20 25 30 35 40 2 4 6 8 10 12 14 16x 10−3 Incoming customers rate Throughput Application model FTTs−Enabled Application model (SoF) FTTs−Enabled Application model (P&R) SMs−FTTs−Enabled Application model (SoF) SMs−FTTs−Enabled Application model (SoF + P&R) (b) Throughput of the system while varying incoming customer rate. Figure 9.3: ECS Performance Analysis Results. 124 9. Case Study: an E-Commerce System Section 9.3 application model. As future work we plan to investigate the system throughput while varying the probability of detecting attack conditions, i.e., by increasing the detection rate of the IDS algorithm. We recall that the the goal of this chapter is to validate a methodology that applies FTTs and SMs at the architectural level by enabling the possibility of computing performance impact before deployment. More in general, several security capabilities can be tested to find the most suitable options. From a performance analysis viewpoint, our experimentation follows standard practices: a performance model is built, instrumented with input parameters and finally evaluated through simulation. Further experimentation can be conducted by instrumenting the model with different numerical values for the experimental parameters. As future work, we plan to apply our approach to other real world examples in order to assess the scalability of the framework. 9.3 Concluding Remarks In Chapter 5 we have introduced a model-based methodology for performance prediction of critical systems which combine Fault-Tolerant Techniques (FTTs) and/or Security Mechanisms (SMs). In this chapter, we validated our proposal given in Chapter 5 by applying it to a case study. The experiments put on evidence that our approach enables the estimation of system performance when adding security protection strategies, and sensitive analysis (testing various security alternatives) can be carried out as support while designing critical systems. 125 Chapter 10 Performance Analysis of Data-Intensive Workflows This chapter addresses the main contributions of this dissertation related to performance analysis applied to a more specific domain, namely, scientific workflows. The major findings of this chapter have been published in [Rodr´ıguez et al., 2012b, Rodr´ıguez et al., 2012c] and [Rodr´ıguez et al., 2013]. 10.1 Motivation Using workflow techniques, scientists can specify their computational experiments by means of a control/data flow graph, consisting of a set of tasks and the dependencies between them. Workflow enactors can subsequently interpret these specifications, enabling tasks in the graph to be mapped onto distributed resources. There are, however, several efficiency limitations of the workflow system in performance and resource usage [Park and Humphrey, 2008]. Such limitations may be due to limited parallelism within the application, or due to the workflow enactment engine. In data-intensive workflows, the enactors must be efficient in both mapping tasks to resources and in transferring large data files between tasks. Previous approaches exploit data location and link bandwidth information to minimise data movement or move data via higher capacity links whenever possible. Such an approach of moving the largest files via the highest-capacity links can result in sub-optimal workflow execution [Park and Humphrey, 2008]. This data movement policy generally involves moving the output data of a task to its successor node immediately after completing its execution. However, if a task needs multiple files to be made available before it can begin execution, it will remain idle until all the required data files from other predecessor nodes have been delivered. It is therefore not how fast each file can be moved to the task, but the interval from the delivery of the first file to the last one that is most significant. Even if the first file is delivered quickly, the task must 127 Section 10.1 10. Performance Analysis of Data-Intensive Workflows still remain idle until others are also available. In consequence, the effective use of network bandwidth and the buffer/storage at the receiving task is not made. If one file arrives too early taking up all of the network bandwidth for one task, it may be at a determent to other tasks (which may have to wait for their data to be delivered) – even though the receiving task still has to wait for other files. Similarly, if there is limited buffer capacity at the receiving task and the buffer needs to be shared between tasks, a quick delivery of one file (while waiting for other files to be delivered) for a task excludes other tasks from using the same buffer. In general therefore, the current practise of moving data from one location to another as early as possible is often either: (i) unnecessary when viewed in isolation (both in terms of networking and buffering): any data file that arrives much before the last needed data file or ii) harmful when viewed in-the-large: there is only finite capacity on each link and a limited buffer capacity – multiple concurrent data movement operations can significantly slow each other down, or an inappropriate buffer usage may lead to a buffer overflow. Park & Humphrey analysed this problem in [Park and Humphrey, 2008] and proposed a data-throttling framework that allows a workflow programmer/engine to describe the requirements on the data movement delay. This technique can be utilised to balance the execution time of workflow branches and eliminate unnecessary bandwidth usage, resulting in more efficient buffer and network usage. However, they do not propose any mechanism for analysing and automatically deriving the values needed to throttle data exchange between nodes involved in the transfer. In this chapter, we firstly introduce a metric for quantitatively measuring the impact that applying an intelligent data movement policy can have on buffer/storage in comparison with existing approaches. This metric considers a workflow structure expressed as a Directed Acyclic Graph (DAG), and performance information collected from historical past executions of the considered workflow. It is intended for being used at the design-stage, comparing various DAG structures and evaluating their potential for optimisation (of network bandwidth and buffer usage). Then, we propose an automated analysis method for DAG that may be used to derive data-throttling values. The method utilises Petri nets for the workflow specification and combines the abstract representation with performance information instrumented from past executions, obtaining a performance model of the workflow: an iterative method is used to compute data-throttling values associated with different links within the workflow. Subsequently, a performance analysis is conducted using the throttling values and the result is compared with the performance achieved without throttling. Lastly, we introduce dynamism on the environment where a scientific workflow is executed, i.e., the network bandwidth of the links or/and the power of hosts machines where workflow tasks are executed significantly vary over the time. 128 10. Performance Analysis of Data-Intensive Workflows Section 10.2 (a) (b) Figure 10.1: (a) Workflow tasks and (b) its transformation to PN. 10.2 Model Transformation: From a DAG to a SMG Before going forward more in detail about performance analysis on workflows, let us explain in this section the model transformation that we perform on a Directed Acyclic Graph (DAG) by transforming it to a performance model based on Petri nets (PNs), namely, Stochastic Marked Graphs (SMGs, see Definition 8). In this paper, we make use of SMGs with exponential random distributions associated with transitions in order to model scientific workflows. In particular, we are interested in workflows expressed as DAGs, where vertices represent tasks and edges represent data dependencies between them. Figure 10.1 depicts how we derive a PN model from a DAG. Figure 10.1(a) shows two workflow tasks of a DAG, task1and task2and a data-link dependence from task1to task2, while Figure 10.1(b) illustrates the transformation to a PN. Note that such a PN model fulfils the definition of a SMG model: there are timed transitions and each place has exactly one input and exactly one output arc. Hence, each task of the workflow DAG is transformed to a place and a transition (represented by a white rectangle), joined by an arc. A task transmission is also transformed to a place and a transition (grey rectangle). For instance, p1→Ttask1represents task1 of the workflow. Note that place p1models the input buffer of task1. Finally, the data dependency between task1and task2is modelled by adding a place and a transition, p2 and Ttx1,2, respectively. Transition Ttx1,2represents the time spent in sending output data from task1to the input buffer of task2(place p3). 10.3 A Metric for Quantifying the Effectiveness of Throttled Data Transfers A task in a workflow DAG cannot start its execution until all its inputs are available. The strategy of receiving these input values as fast as possible is often not appropriate. As some inputs may arrive earlier than others, these inputs have to be buffered locally at the task, resulting in unnecessary use of buffer space. If such buffer space is a shared resource and of 129 Section 10.3 10. Performance Analysis of Data-Intensive Workflows limited capacity, it remains blocked by the task, waiting for the remaining data to arrive. Hence, the greater the variation between arrival times of the different input data sets, the greater the inefficiency in buffer use. Intuitively, the objective of an effective data transfer is that each task with multiple inputs has all its data sets arrive simultaneously. Our approach is therefore relevant for a workflow which has: (i) multiple synchronisation points (identified as tasks in the workflow containing more than one input, where all inputs are needed before the task can begin execution); (ii) difference in arrival times between the different inputs to such synchronisation point. The higher the value of (i) and (ii), the greater the possible optimisation we are likely to see with our approach. Both of these aspects depend on the structure of the workflow and the environment within which a workflow is enacted. Our approach could be used to re-write a workflow DAG that has a structural imbalance, i.e. a DAG containing multiple paths whose execution times differ significantly. Such an imbalance [Park and Humphrey, 2008] may also arise due to a scheduler binding tasks to resources, faults or unexpected performance degradation, such as a slow network connection or limited storage for the dataset. In order to compute the metric, we convert the workflow DAG specification into a Petri net (as explained in Section 10.2), we subsequently feed the Petri net model with performance information on computational tasks, and network, as well as data size [Rodr´ıguez et al., 2012b]. Petri net theory is subsequently used to analyse the Petri net model, and to obtain slack (µ) [Rodr´ıguez and J´ulvez, 2010] values (a key concept in our analysis, see Section 6.2). Intuitively, a slack is a positive value associated with each input link to a synchronisation (sync.) point and captures the time taken for an input data to be delivered to such a synchronisation point. The higher the slack, the more likely to have a higher input delay, thereby delaying the execution of the task at the synchronisation point. A more formal description of a synchronisation point and the associated slack, in term of workflows, is as follows. Let Wbe a workflow represented as a cyclic Petri net and composed of a set Tof tasks T={t1,...,tn},|T|=n. Let ψtbe the number of inputs of task t∈T. Let T′⊆Tbe a set of tasks with multiple inputs, i.e., ∀t∈T′, ψt>1. A task t∈T′is then called synchronisation task (or synchronisation point). Let δi,j be the time taken for an input j≤ψtito arrive at synchronisation task ti. As each input jarrives at different times, we can determine the value of max(δi,j ) for a synchronisation task tithat represents the time taken for the slowest arriving input. Considering the entire workflow W, we can find the slowest path from the input to the output of the workflow, which also represents the workflow makespan M– represented as M=Pt∈Texecution time(t) + Pti∈T′max(δi,j), j ≤ψti. The slack µi,j >0 for input j≤ψtiof task ti, can be calculated as: µi,j =(maxψti j=1(δi,j)−δi,j ) M (10.1) 130