Throughout the years, the attention on technical debt experienced a steady growth, and can now boast to be a consolidated concept within the software engineering field. Despite the growing academic and industrial interest in the topic, a category of technical debt appears to date to be unexplored. In this paper, we introduce the concept of turnover technical debt, i.e., technical debt that arises when developers leave projects with software artifacts other developers will struggle to work with. Our contribution presents an initial formulation of the phenomenon, which intuitively revolves around two co-occurring properties in software artifacts, namely (i) centralized ownership and (ii) low understandability and suboptimal documentation. Based on these two properties, we present an approach outlining a conceptual basis to quantitatively observe turnover technical debt via a mix of repository mining and static analysis. We complement our contribution with a mixed-method case study conducted with the twofold goal of assessing the viability of the proposed measurement approach and collecting initial insights from practitioners on the phenomenon. The gathered results point to the relevance of turnover technical debt in practice, and to promising avenues to more precisely measure the phenomenon.

Apache Kafka is a key component in event-driven and microservice architectures relying on distributed publishsubscribe messaging for scalable and fault-tolerant streaming of real-time data. To reduce distribution overhead, messages are buffered and dispatched to the broker when either a maximum batch size N is reached or a timeout T expires, enabling control on the trade-off between high throughput and low latency. However, this trade-off has been explored only through empirical studies, referred to specific system deployments and not suited for runtime adaptation to variable workload conditions. We provide an analytical characterization of the arrival process induced by Kafka batching policy under Poisson arrivals. The analysis develops on the observation that the time for buffering a full batch and the size of a batch dispatched at expiration of the timeout follow truncated Erlang and Poisson distributions, respectively. Leveraging this insight, we derive closed forms for quantities that characterize the arrival process, and we propose a method for efficient simulation of the process embedded at dispatching times. To support practical implementation, we evaluate solutions for drawing samples from an Erlang distribution provided by NumPy, PyTorch, and R, and we also propose a novel approach based on rejection sampling with proposal function in the family of Kumaraswamy distributions with automated optimization of parameters with respect to the number of phases. Numerical experimentation shows that: (i) aggregated simulation enabled by the analytical formulation is insensitive to the value of the batch size, and it definitely outperforms fine-grained simulation of individual message arrivals; (ii) the best efficiency is obtained with the NumPy implementation of Erlang, with promising results of the novel approach based on Kumaraswamy, which achieves results comparable to PyTorch and better than $\mathbf{R}$.

Hands-off detection (HOD) is used in autonomous driving vehicle (ADV). However, how to choose an appropriate HOD timespan (HODT) either practically or legislatively remains unsolved. In this paper, an asymmetric Nash bargaining-based HODT determination is introduced. Utility functions of autonomous driving system (ADS) and driver are developed. HODT is determined based on the asymmetric Nash bargaining solution. Experimental result shows existing adopted HODTs can be obtained using the proposed method. Appropriate HODT can be obtained considering safety requirement and driver's need. Under high safety requirement, HODT is short regardless of driver's need. When safety requirement is not strict, HODT can be prolonged to satisfy driver's need. By constructing situation awareness (SA) evolution process considering HODT, ceiling HODT can be obtained, which can be used in legislation as the longest HODT that can be chosen. Experiment also shows superiority of dynamical HODT over the constant HODT. The proposed method offers a possible theoretical solution to HODT determination, showing potential in practice and legislation.

Context: Microservices are gaining significant traction in academic research and industry due to their advantages, and technical debt has long been a heavily researched metric in software quality context. However, to date, no study has attempted to understand how code technical debt evolves in such architectures. Aim: This research aims to understand how technical debt evolves over time in microservice architectures by investigating its trends, patterns, and potential relations with microservices number. Method: We analyze the technical debt evolution of 13 open-source projects. We collect data from systems through automated source code analysis , statistically analyze results to identify technical debt trends and correlations with microservices number, and conduct a subsequent manual commit inspection. Results: Technical debt increases over time, with periods of stability. The growth is related to microservices number, but its rate is not. The analysis revealed trend differences during initial development phases and later stages. Different activities can introduce technical debt, while its removal relies mainly on refactoring. Conclusions: Microservices independence is fundamental to maintain the technical debt under control, keeping it compartmentalized. The findings underscore the importance of technical debt management strategies to support the long-term success of microservices.

The ever-increasing complexity of modern software architectures has exacerbated the need for advanced software tools able to track software execution traces to improve software reliability. In this paper, we present OREO, a tool for offline and run-time monitoring and fault localization. The tool implements a novel method enabling to trace software executions to discover the run-time status, dependencies, and interactions among software components. OREO is based on a timeline extractor, i.e., an abstraction of component lifecycles and their interactions. The timeline extractor enables the tool to perform a runtime health state examination of the software under analysis. The profiler is then used to analyze the error propagation originated during the running states among software components. In so doing, the possible fault-error-failure chains are identified. To showcase the capabilities of OREO and its flexibility, we report the execution of the tool on three software projects of different nature, sizes, and architectures. The analysis results in the localization of fault-error-failure chains and safe components of the three software projects. A discussion of the versatility, scalability, and applicability of the proposed tool to a rich variety of application contexts is provided.

The inclusion of generally distributed random variables in stochastic models is often tackled by choosing a parametric family of distributions and applying fitting algorithms to find appropriate parameters. A recent paper proposed the approximation of probability density functions (PDFs) by Bernstein exponentials, which are obtained from Bernstein polynomials by a change of variable and result in a particular case of acyclic phase-type distributions. In this paper, we show that this approximation can also be applied to cumulative distribution functions (CDFs), which enjoys advantageous properties and achieves similar accuracy; by focusing on CDFs, we propose an approach to obtain stochastically ordered approximations. The use of a scaling parameter in the approximation is also presented, evaluating its effect on approximation accuracy.

We present a Model Driven Engineering (MDE) approach to dependability evaluation of component-based coherent dyadic systems, implemented by the FaultFlow library, combining simple high-level modeling with powerful quantitative evaluation methods. In the functional perspective, distinctive features are: modeling of fault propagations within individual components and between different components, possibly not connected through physical or communication interfaces; support for non-Markovian distributions, both for the times to the occurrence of faults and for the duration of fault-to-failure propagations; derivation of the distribution of the time to the occurrence of a given failure; derivation of fault importance measures, for models where each fault does not propagate into multiple failures and, viceversa, each failure does not act as fault to multiple components, achieving evaluation efficiency even for significantly complex systems with hundreds of different faults. In the implementation perspective, distinctive features are: definition of a custom-made extensible metamodel to specify the system structure and failure logic; automated derivation of metamodel instances from Systems Modeling Language (SysML) Block Definition Diagrams (BDDs) and Stochastic Static Fault Trees (SSFTs); automated derivation of the mentioned dependability measures; open source availability. We illustrate the typical modeling and evaluation workflow with relevant uses cases, comparing functionalities with those of other dependability evaluation tools.

In performance engineering of composed services, coordinated provisioning can reduce the amount of resources required to meet end-to-end response time objectives. To this aim, various intertwined aspects of the application architecture need to be taken into account, notably including precedence constraints in the composition of elementary services, along with their durations and sensitivity to the scaling of provisioned resources. We address coordinated provisioning of resources for elementary services with stochastic durations with general distributions (i.e., including non-exponential distributions). We compose services in a workflow where precedence constraints define a Directed Acyclic Graph (DAG) and the distribution of the end-to-end (E2E) response time is subject to a Service Level Objective (SLO). We leverage a surrogate model of service performance, assuming a low workload of workflow requests (i.e., a single-request scenario) and service durations inversely proportional to provisioned resources. Given the total amount of resources, our approach derives the service provisioning that optimizes the workflow E2E response time distribution, by exploiting a compositional approach and by using stochastically ordered approximations to manage dependencies in non-well-nested precedence DAGs. Then, the approach scales provisioned resources up or down to determine the minimum amount of resources needed to satisfy the SLO, while leaving the remaining resources for horizontal scaling in order to manage multiple workflow requests at high workloads. Experiments consider low-workload and high-workload scenarios, different relations between elementary service durations and provisioned resources, and workflow topologies taken from benchmarks or randomly generated with controlled statistics, using elementary service durations from a dataset of the literature. Results show that the technique is feasible also for workflows with a thousand of services and that it outperforms other provisioning methods in fitting the SLO using the same resource amount and in minimizing the resource amount needed to fit the SLO.

Background: Over the past decade, microservices have surged in popularity within software engineering. From a research viewpoint, mining studies are frequently employed to assess the evolution of diverse microservice properties. Despite the growing need, a validated static method to swiftly identify microservices seems to be currently missing in the literature.

Context: With the ever-evolving software landscape, methods to train software programmers are continuously advancing and evolving. In this investigation, we study the case of 42, a programming school with over 50 campuses worldwide. 42’s pedagogical method blends elements of problem-based learning, peer pedagogy, community building, and gamification. Objectives: The goal of the research is twofold: On one hand, to gain a deep understanding of the pedagogical method itself, and on the other hand, to study how its different components affect learning. Method: We adopt an ethnographic qualitative inquiry, with two academic researchers conducting participant observation over a period of six months by using activity theory as theoretical underpinning. Results: Problems of incremental difficulty, albeit challenging, foster virtuous cycles of reinforcing feedback and community building. Gamification and peer learning elements, which are deeply rooted in the carefully crafted educational receipt, further support the pedagogical method. Conclusions: The characteristic nature of 42 positions it as an outlier compared to the recurrent academic setting of frontal lectures followed by a final exam, making it a valuable case study to understand how various pedagogical components may function, interact, and affect student learning.

Effective exploitation of Machine Learning solutions in the Digital Twin (DT) paradigm may largely benefit from Federated Analytics (FA) approaches, to mitigate data scarcity, by merging distributed data, and heterogeneity while limiting communication overhead and exchange of sensitive raw data. In the DT paradigm, federated schemes find a native collocation in the conceptual association between Digital Twin Prototype (DTP) of a class and Digital Twin Instance (DTI) of individual products. We propose the application of the democratized learning (Dem-AI) scheme to provide a scalable solution for multi-level hierarchical integration of data owned by a multiplicity of distributed DTs, and we showcase its application in a failure prediction scenario. The proposed model integration scheme preserves the inherent cohesive relationships between generalization and specialization (or personalization) capabilities of the DTP model and the DTI model, respectively. Based on the model acquired, DTs monitor the system behavior and forecast failure occurrences. Experimental analysis has been conducted to thoroughly investigate the performance of the Dem-AI failure prediction framework designed, considering different levels of model specialization and public dataset.

In component-based software systems, micro-rejuvenation of individual components can be performed to limit the number of more time-consuming system macro-rejuvenations, requiring appropriate selection of rejuvenation times to actually reduce the system unavailability. We present a novel coordinated approach to micro-rejuvenation of software components, aimed at minimizing the system cumulative unavailability over time.Specifically, each component is periodically rejuvenated, and, if it fails, rejuvenation is scheduled after repair. To limit concurrent component rejuvenations, an efficient calculus is defined to derive the optimal rejuvenation offset of each component, based on the condition of system unavailability expressed as a static fault tree with AND and OR gates. An efficient compositional approach is also provided to derive the system unavailability, by leveraging numerical analysis of a stochastic model with underlying Markov regenerative process. The solution accuracy is exploited to analyze how components loose synchronization over time due to random rejuvenation and repair times, enabling the definition of a macro-rejuvenation policy. Experiments performed on several randomly and manually generated models show feasibility and effectiveness of the approach, enabling further extensions.

When testing three-tiered architectures, strategies often rely on superficial information, e.g., black-box input. However, the correct behavior of software-intensive systems based on such architectural pattern also depends on the logic hidden behind the interface. Verifying the response process is thus often complex and requires ad-hoc strategies. We propose an approach to identify faults hidden behind the presentation layer. The model-based approach uses an architectural abstraction called managed component Data Flow Graph (mcDFG). The mcDFG is aware of the interactions between all layers of the architecture and guides the generation of tests based on different mcDFG coverage criteria to identify faults in the business logic. To evaluate the approach viability, we consider a three-tiered web application and 32 faults. The fault detection capability is assessed by comparing a set of test suites created by following our method and a set of test suites developed by utilizing traditional testing strategies. The collected data show that the proposed model-based approach is a viable option to identify faults hidden in the logic layer, as it can outperform standard strategies based solely on the presentation layer while keeping the number of test cases and number of interactions per test case low.

Quantitative evaluation of stochastic models supports early verification of design choices and assessment of non-functional requirements. Model Driven Engineering (MDE) leverages automated derivation of formal stochastic models from semi-formal artifacts of the Unified Modeling Language (UML) to facilitate deployment of quantitative evaluation methods without disrupting industrial practices. As a major limitation, when generally distributed (GEN) temporal parameters are considered to enhance the model expressivity, the structure and complexity of the underlying stochastic process cannot be easily controlled, possibly impairing the model analyzability. We present a hierarchical modeling formalism based on UML statecharts with GEN durations, designed to guarantee ease of modeling and efficient evaluation of steady-state or transient behaviour until absorption. To this end, fairly lax restrictions are applied to the model syntax to enable separate analysis of the Semi-Markov Process (SMP) underlying each model component. Scalability of solution is assessed by analyzing a suite of synthetic models referred to the context of timed Failure Logic Analysis (FLA) of component-based systems, specifically designed to point out each factor of computational complexity. Notably, the analysis derives both the probability that the system is in each step before failure and the Cumulative Distribution Function (CDF) of the duration of the overall failure process. A challenging case study that significantly and jointly stresses the main factors of computational complexity is finally addressed, performing steady-state analysis of a non-Markovian variant of a server virtualized system from the literature on software rejuvenation.

Workflows are patterns of orchestrated activities designed to deliver some specific output, with application in various relevant contexts including software services, business processes, supply chain management. In most of these scenarios, durational properties of individual activities can be identified from logged data and cast in stochastic models, enabling quantitative evaluation of time behavior for diagnostic and predictive analytics. However, effective fitting of observed durations commonly requires that distributions break the limits of memoryless behavior and unbounded support of Exponential distributions, casting the problem in the class of non-Markovian models. This results in a major hurdle for numerical solution, largely exacerbated by the concurrency structure of workflows, which natively subtend concurrent activities with overlapping execution intervals and a limited number of regeneration points, i.e., time points at which the Markov property is satisfied and analysis can be decomposed according to a renewal argument. We propose a compositional method for quantitative evaluation of end-to-end response time of complex workflows. The workflow is modeled through Stochastic Time Petri Nets (STPNs), associating activity durations with Exponential distributions truncated over bilateral firmly bounded supports that fit mean and coefficient of variation of real logged histograms. Based on the model structure, the workflow is decomposed into a hierarchy of subworkflows, each amenable to efficient numerical solution through Markov regenerative transient analysis. In this step, the grain of decomposition is driven by non-deterministic analysis of the space of feasible behaviors in the underlying Time Petri Net (TPN) model, which permits efficient characterization of the factors that affect behavior complexity between regeneration points. Duration distributions of the subworkflows obtained through separate analyses are then repeatedly recomposed in numerical form to compute the response time distribution of the overall workflow.

In systems with imperfect fault coverage (IFC), all components are subject to uncovered failures, possibly threatening the whole system. Therefore, to improve the system reliability, it is important to timely detect, identify, and shut down the components that are no more relevant for the system operation. This article addresses quantitative evaluation of the relevance of components, assuming that they have independent and identically distributed lifetimes to characterize the impact of the system design only on the system reliability and energy consumption. To this end, the dynamic relevance measure is defined to characterize the irrelevant components in different stages of the system lifetime depending on the number of occurred component failures, supporting the evaluation of the probability that the system fails due to uncovered failures of irrelevant components. Moreover, the system reliability over time is also efficiently derived, both in the case that irrelevance is not considered and in the case that irrelevant components can be immediately isolated, notably supporting any general (i.e., non-Markovian) distribution for the failure time of components. Feasibility and effectiveness of the approach are assessed on two real-scale case studies addressing reliability evaluation of a flight control system and a multihop wireless sensor network.

We present the next generation of ORIS, a toolbox for quantitative evaluation of concurrent models with non-Markovian timers. The tool shifts its focus from timed models to stochastic ones, it includes a new graphical user interface, new analysis methods and a Java Application Programming Interface (API). Models can be specified as Stochastic Time Petri Nets (STPNs) through the graphical editor, validated using an interactive token game, and analyzed through several techniques to compute instantaneous or cumulative rewards. STPNs can also be exported as Java code to conduct extensive parametric studies through the Java library, now distributed as open-source. A well-engineered software architecture allows the user to implement new features for STPNs, new modeling formalisms, and new analysis methods. The most distinctive features of ORIS include transient and steady-state analysis of STPNs modeling Markov Regenerative Processes (MRPs), and transient analysis of STPNs modeling generalized semi-Markov processes. ORIS also supports state-space analysis of Time Petri Nets (TPNs), simulation of STPNs, and standard analysis techniques for continuous-time Markov chains or MRPs with at most one non-exponential timer in each state. We illustrate the general workflow for the application of ORIS to the modeling and evaluation of non-functional requirements of software-intensive systems.

A Water Distribution System (WDS) is a critical infrastructure for society and economy, subject to frequent maintenance either for contingencies or planned operations. Maintenance procedures affect the hybrid dynamics of a WDS at stochastic time points, representing the completion of repair activities that change the WDS topology and operation mode. Hence, the problem of performability evaluation of the WDS behavior during a maintenance intervention falls in the class of stochastic hybrid systems (SHSs), for which existing numerical or simulative approaches cannot afford the complexity of realistic WDSs. We propose a viable approach that computes the expected demand not served during a maintenance procedure by integrating fluid-dynamic analysis of the WDS with quantitative evaluation of the procedure timing, notably assuming non-Markovian repair times over a bounded support. Different solution techniques are presented to evaluate the joint distribution of the times when the procedure affects the WDS, performing either simulation of the procedure model or state-space analysis based on an extension of the method of stochastic state classes. Feasibility and effectiveness of the proposed methods are assessed on a real WDS in terms of result accuracy and computational complexity, showing that the overall approach could be efficiently applied in higher level tasks including activity scheduling, resource planning, and budget allocation.

Runtime predictive analysis of quantitative models can support software reliability in various application scenarios. The spread of logging technologies promotes approaches where such models are learned from observed events. We consider a system visiting transient states of a hidden process until reaching a final state and producing observations with stochastic arrival times and types conditioned by visited states, and we abstract it as a marked Markov modulated Poisson Process (MMMPP) with left-to right structure. We present an Expectation-Maximization (EM) algorithm that learns the MMMPP parameters from observation sequences acquired in repeated execution of the transient behavior, and we use the model at runtime to infer the current state of the process from actual observed events and to dynamically evaluate the remaining time to the final state. The approach is illustrated using synthetic datasets generated from a stochastic attack tree of the literature enriched with an observation model associating each state with an expected statistics of observation types and arrival times. Accuracy of prediction is evaluated under different variability of hidden states sojourn durations and of the observations arrival process, and compared against previous literature that mainly exploits either the timing or the types of observed events.

We propose an approach for assessing the impact of multi-phased repair procedures on gas distribution networks, capturing load profiles that can depend on time for different classes of users, suspension of activities during non-working hours, and random execution times depending on topological, physical, and geographical characteristics of the network. The problem is characterized through a semi-formal specification based on artifacts of the Systems Modeling Language (SysML), which is then translated into a formal model based on stochastic time Petri nets. The solution method interleaves fluid-dynamic analysis of the gas behavior and stochastic analysis of the time spent in the repair process, decoupling complexities and making stochastic analysis almost insensitive to the network size and topology. Hence, our approach turns out to be applicable to real scale cases, notably computing the optimal time of day to start the repair procedure. Moreover, by encompassing general (non-Markovian) distributions, the approach enables effective fitting of durations.

We present a model-based approach to Activity Recognition (AR) in Ambient Assisted Living (AAL). The approach leverages an a priori stochastic model termed Continuous-Time Hidden Semi-Markov Model (CT-HSMM), capturing the continuous-time durations of activities and inter-event times. The model is enhanced according to the observed statistics, associating the events with an occurrence probability, and the sojourn time and the inter-event time in each activity with a continuous-time probability density function, allowing effective fitting of observed durations through non-Markovian distributions. The model is updated at run time according to a sequence of time-stamped observations, exploiting the method of stochastic state classes to perform transient analysis and derive a measure of likelihood that an activity is currently performed. The approach supports both online AR, predicting the activity performed at time t using only the events observed until that time, and offline AR, applying a forward- backward procedure that exploits all the events observed before and after time t. The approach is experimented on a real dataset of the literature, providing performance measures that can be compared with those of offline Hidden Markov Models (HMMs) and offline Hidden Semi-Markov Models (HSMMs).

Agile production systems face major issues in satisfying fickle market needs in highly demand-driven industry sectors, such as electronics and mechatronics. In this context, the time needed to complete the production of an item tends to be highly variable, and online estimation of the remaining completion time may suffer the lack of adequate sensor data, especially in existing manufacturing systems. To solve this issue, we propose a new analytical technique for the evaluation of an upper and a lower stochastic bound on the remaining completion time of a product, considering an assembly line made of sequential workstations with transfer blocking and buffer capacity. The approach notably encompasses service times with non-Markovian distribution, and avoids the limitation of existing works requiring the system to be at steady state at the inspection time. The technique is experimented on a case study and validated through simulation, providing an empirical analysis of its complexity.

Fischer's protocol is a well-known timed mechanism through which a set of processes can synchronize access to a critical section without relying on atomic test-and-set operations, as might occur in a distributed environment or on a low-level computing platform. The protocol is based on a deterministic waiting time that can be defined so as to guarantee that possible interference due to concurrent accesses with random bounded delays be resolved with certainty. While protocol correctness descends from firm lower and upper bounds on waiting times and random delays, performance attained in synchronization also depends on continuous distributions of delays. Performance evaluation of a correct implementation thus requires the solution of a non-Markovian model whose underlying stochastic process falls in the class of Markov regenerative processes (MRPs) with multiple concurrent delays with non-exponential duration. Numerical solution of this class of models is to a large extent still an open problem. We provide a twofold contribution. We first introduce a novel method for the steady-state analysis of MRPs where regenerations are reached in a bounded number of discrete events, which enlarges the class amenable to numerical solution by allowing multiple concurrent timers with non-exponential distributions. The proposed technique is then applied to Fischer's protocol by characterizing the latency overhead due to synchronization, which comprises the first case where performance of the protocol is quantitatively assessed by jointly accounting for firm bounds and continuous distributions of delays.

The recent rise of the NoSQL movement motivates investigation on the performance impact that new persistence approaches can bring in the model-driven re-engineering of a consolidated object-oriented software architecture. We report comparative experimental performance results attained by combining a pattern-based domain logic with a persistence layer based on different paradigms and we describe how data model is persisted in various implementation based on MySQL, Neo4j, and MongoDB.

We consider the problem of verifying quantitative reachability properties in stochastic models of concurrent activities with generally distributed durations. Models are specified as stochastic time Petri nets and checked against Boolean combinations of interval until operators imposing bounds on the probability that the marking process will satisfy a goal condition at some time in the interval [α, β] after an execution that never violates a safety property. The proposed solution is based on the analysis of regeneration points in model executions: a regeneration is encountered after a discrete event if the future evolution depends only on the current marking and not on its previous history, thus satisfying the Markov property. We analyze systems in which multiple generally distributed timers can be started or stopped independently, but regeneration points are always encountered with probability 1 after a bounded number of discrete events. Leveraging the properties of regeneration points in probability spaces of execution paths, we show that the problem can be reduced to a set of Volterra integral equations, and we provide algorithms to compute their parameters through the enumeration of finite sequences of stochastic state classes encoding the joint probability density function (PDF) of generally distributed timers after each discrete event. The computation of symbolic PDFs is limited to discrete events before the first regeneration, and the repetitive structure of the stochastic process is exploited also before the lower bound α, providing crucial benefits for large time bounds. A case study is presented through the probabilistic formulation of Fischer's mutual exclusion protocol, a well-known real-time verification benchmark.

Quantitative evaluation of models with stochastic timings can decisively support schedulability analysis and performance engineering of real-time concurrent systems. These tasks require modeling formalisms and solution techniques that can encompass stochastic temporal parameters firmly constrained within a bounded support, thus breaking the limits of Markovian approaches. The problem is further exacerbated by the need to represent suspension of timers, which results from common patterns of real-time programming. This poses relevant challenges both in the theoretical development of non-Markovian solution techniques and in their practical integration within a viable tailoring of industrial processes.

Automated monitoring and the recognition of activities of daily living (ADLs) is a key challenge in ambient-assisted living (AAL) for the assistance of the elderly. Within this context, a formal approach may provide a means to fill the gap between the low-level observations acquired by sensing devices and the high-level concepts that are required for the recognition of human activities. We describe a system named ARA (Automated Recognizer of ADLs) that exploits propositional temporal logic and model checking to support automated real-time recognition of ADLs within a smart environment. The logic is shown to be expressive enough for the specification of realistic patterns of ADLs in terms of basic actions detected by a sensorized environment. The online model checking engine is shown to be capable of processing a stream of detected actions in real time. The effectiveness and viability of the approach are evaluated within the context of a smart kitchen, where different types of ADLs are repeatedly performed.

We present an approach for integration of formal methods within an industrial SW process, illustrating results obtained in a real scenario subject to Military Standard 498 (MIL-STD-498). On the one hand, the formal nucleus of preemptive Time Petri Nets (pTPNs) is used to support design and verification activities of the development process; on the other hand, the Unified Modeling Language (UML) profile for Modeling and Analysis of Real-Time and Embedded (MARTE) systems is adopted to manage the documentation process prescribed by MIL-STD-498. The two cores are integrated by providing guidance for translation of UML-MARTE specifications into equivalent pTPN models, with specific reference to concurrency control and synchronization mechanisms. This permits to attain a smooth transition from the standard artifacts of MIL-STD-498 to pTPN models and analyses, facilitating deployment of the formal core of pTPNs with a limited impact on the industrial practice. The experience proves practical feasibility and effectiveness of the approach, comprising a step towards industrial applicability of formal methods and practices.

Hierarchical Scheduling (HS) techniques achieve resource partitioning among a set of real-time applications, providing reduction of complexity, confinement of failure modes, and temporal isolation among system applications. This facilitates compositional analysis for architectural verification and plays a crucial role in all industrial areas where high-performance microprocessors allow growing integration of multiple applications on a single platform. We propose a compositional approach to formal specification and schedulability analysis of real-time applications running under a Time Division Multiplexing (TDM) global scheduler and preemptive Fixed Priority (FP) local schedulers, according to the ARINC-653 standard. As a characterizing trait, each application is made of periodic, sporadic, and jittering tasks with offsets, jitters, and nondeterministic execution times, encompassing intra-application synchronizations through semaphores and mailboxes and interapplication communications among periodic tasks through message passing. The approach leverages the assumption of a TDM partitioning to enable compositional design and analysis based on the model of preemptive Time Petri Nets (pTPNs), which is expressly extended with a concept of Required Interface (RI) that specifies the embedding environment of an application through sequencing and timing constraints. This enables exact verification of intra-application constraints and approximate but safe verification of interapplication constraints. Experimentation illustrates results and validates their applicability on two challenging workloads in the field of safety-critical avionic systems.

In the process of testing of concurrent timed systems, input generation identifies values of temporal parameters that let the Implementation Under Test (IUT) execute selected cases. However, when some parameters are not under control of the driver, test execution may diverge from the selected input and produce an inconclusive behavior. We formulate the problem on the basis of an abstraction of the IUT which we call partially stochastic Time Petri Net (psTPN), where controllable parameters are modeled as nondeterministic values and noncontrollable parameters as random variables with general (GEN) distribution. With reference to this abstraction, we derive the analytical form of the probability that the IUT runs along a selected behavior as a function of choices taken on controllable parameters. In the applicative perspective of real-time testing, this identifies a theoretical upper limit on the probability of a conclusive result, thus providing a means to plan the number of test repetitions that are necessary to guarantee a given probability of test-case coverage. It also provides a constructive technique for an optimal or suboptimal approach to input generation and a way to characterize the probability of conclusive testing under other suboptimal strategies.

Preemptive Time Petri Nets (pTPNs) support modeling and analysis of concurrent timed SW components running under fixed priority preemptive scheduling. The model is supported by a well-established theory based on symbolic state space analysis through Difference Bounds Matrix (DBM) zones, with specific contributions on compositional modularization, trace analysis, and efficient overapproximation and cleanup in the management of suspension deriving from preemptive behavior. In this paper, we devise and implement a framework that brings the theory to application. To this end, we cast the theory into an organic tailoring of design, coding, and testing activities within a V-Model SW life cycle in respect of the principles of regulatory standards applied to the construction of safety-critical SW components. To implement the toolchain subtended by the overall approach into a Model Driven Development (MDD) framework, we complement the theory of state space analysis with methods and techniques supporting semiformal specification and automated compilation into pTPN models and real-time code, measurement-based Execution Time estimation, test case selection and execution, coverage evaluation.

Critical systems require supervising infrastructures to keep their unreliability under control. We propose safety-critical systems to be modeled through a fault-tolerant architecture based on Stochastic Fault Trees (SFTs) and we refer to a scenario where the monitoring infrastructure is a Wireless Sensor Network (WSN). SFTs associate the failure time of leaf events with a non-Markovian (GEN) cumulative distribution function (CDF) and support the evaluation of system unreliability over time. In the reference scenario, the SFT model dynamically updates system unreliability according to samples delivered by the WSN, it maintains a dynamic measure of the safe time-horizon within which the system is expected to operate under a given threshold of unreliability, and it also provides the WSN with a measure of the contribution of each basic event to system unreliability.

Quantitative evaluation of models with generally-distributed transitions requires analysis of non-Markovian processes that may be not isomorphic to their underlying untimed models and may include any number of concurrent non-exponential timers. The analysis of stochastic Time Petri Nets copes with the problem by covering the state space with stochastic-classes, which extend Difference Bounds Matrices (DBM) with a state probability density function. We show that the state-density function accepts a continuous piecewise representation over a partition in DBM-shaped sub-domains. We then develop a closed-form symbolic calculus of state-density functions assuming that model transitions have expolynomial distributions. The calculus shows that within each sub-domain the state-density function is a multivariate expolynomial function and makes explicit how this form evolves through subsequent transitions. This enables an efficient implementation of the analysis process and provides the formal basis that supports introduction of an approximate analysis based on Bernstein Polynomials. The approximation attacks practical and theoretical limits in the applicability of stochastic state-classes, and devises a new approach to the analysis of non Markovian models, relying on approximations in the state space rather than in the structure of the model.

In the verification of reactive systems with nondeterministic densely valued temporal parameters, the state-space can be covered through equivalence classes, each composed of a discrete logical location and a dense variety of clock valuations encoded as a difference bounds matrix (DBM). The reachability relation among such classes enables qualitative verification of properties pertaining events ordering and stimulus/response deadlines, but it does not provide any measure of probability for feasible behaviors. We extend DBM equivalence classes with a density-function which provides a measure for the probability of individual states. To this end, we extend time Petri nets by associating a probability density-function to the static firing interval of each nondeterministic transition. We then explain how this stochastic information induces a probability distribution for the states contained within a DBM class and how this probability evolves in the enumeration of the reachability relation among classes. This enables the construction of a stochastic transition system which supports correctness verification based on the theory of TPNs, provides a measure of probability for each feasible run, enables steady-state analysis based on Markov renewal theory. In so doing, we provide a means to identify feasible behaviors and to associate them with a measure of probability in models with multiple concurrent generally distributed nondeterministic timers.

We describe a methodology for the construction of real-time tasking sets, which smoothly integrates a formal approach in both development and verification processes of the software life cycle. In the design stage, a timeline schema is used to specify concurrent processes with their dependencies and their expected temporal parameters. The schema is automatically translated into an equivalent preemptive time Petri net, which supports verification of the process architecture with respect to timeliness and sequencing requirements through state space analysis. The specification model drives the implementation stage enabling a disciplined coding of the process architecture on top of conventional primitives of a real-time operating system. At the same time, the preemptive Time Petri Net specification and the results of its state space analysis support functional testing enabling the construction of a time-sensitive Oracle and providing a metrics for coverage analysis. Computational experience in the Linux RTAI environment is reported to demonstrate the capability of the method to be effectively integrated in a practical approach.

We address the problem of test case selection and path sensitization in the process of testing real-time preemptive systems, following a formal methodology based on the theory of preemptive Time Petri Nets (pTPN) implemented in the Oris tool. We discuss practical factors that limit feasible behaviors in the implementation of a nondeterministic specification and we motivate the assumption of test cases defined as paths selected in the symbolic state space of a pTPN specification. Feasibility and effectiveness of the proposed sensitization technique are demonstrated through experimentation on a real-time operating system.

Time Petri nets describe the state of a timed system through a marking and a set of clocks. If clocks take values in a dense domain, state space analysis must rely on equivalence classes. These support verification of logical sequencing and quantitative timing of events, but they are hard to be enriched with a stochastic characterization of nondeterminism necessary for performance and dependability evaluation. Casting clocks into a discrete domain overcomes the limitation, but raises a number of problems deriving from the intertwined effects of concurrency and timing. We present a discrete-time variant of time Petri nets, called stochastic preemptive time Petri nets, which provides a unified solution for the above problems through the adoption of a maximal step semantics in which the logical location evolves through the concurrent firing of transition sets. We propose an analysis technique, which integrates the enumeration of a succession relation among sets of timed states with the calculus of their probability distribution. This enables a joint approach to the evaluation of performance and dependability indexes as well as to the verification of sequencing and timeliness correctness. Expressive and analysis capabilities of the model are demonstrated with reference to a real-time digital control system.

A modeling notation is introduced which extends time Petri nets with an additional mechanism of resource assignment making the progress of timed transitions be dependent on the availability of a set of preemptable resources. The resulting notation, which we call preemptive time Petri nets, permits natural description of complex real-time systems running under preemptive scheduling, with periodic, sporadic, and one-shot processes, with nondeterministic execution times, with semaphore synchronizations and precedence relations deriving from internal task sequentialization and from interprocess communication, running on multiple processors. A state space analysis technique is presented which supports the validation of preemptive time Petri net models, combining tight schedulability analysis with exhaustive verification of the correctness of logical sequencing. The analysis technique partitions the state space in equivalence classes in which timing constraints are represented in the form of difference bounds matrixes. This permits it to maintain a polynomial complexity in the representation and derivation of state classes, but it does not tightly encompass the constraints deriving from preemptive behavior, thus producing an enlarged representation of the state space. False behaviors deriving from the approximation can be cleaned-up through an algorithm which provides a necessary and sufficient condition for the feasibility of a behavior along with a tight estimation of its timing profile.

Preemptive Time Petri nets are obtained by extending Time Petri nets with an additional mechanism of resource assignment which makes the progress of timed transitions be dependent on the availability of a set of preemptable resources, and with the capability to make transition times and priorities be dependent on the marking. The combination of these capabilities supports description and verification of flexible real time systems running under preemptive scheduling, with periodic, sporadic and one shot processes, with non-deterministic execution times, with semaphore synchronizations and precedence relations deriving from internal task sequentialization and from interprocess communication. The expressive capabilities of the model and the type of results that can be derived through symbolic enumeration of its dense-timed state space are illustrated with reference to a flexible system mixing dynamic acceptance and performance polymorphism.

A modeling and validation approach extending the formalism of timed Petri nets (TPN) for the analysis of real time systems with flexible scheduling capabilities is introduced. The new formalism is called AdaptiveTPNs. State space analysis of the model supports exhaustive prediction of the time needed to complete critical functions, and permits automatic identification of loading conditions which determine the reduction of the quality of produced results.

In the access to image databases, queries based on the appearing visual features of searched data reduce the gap between the user and the engineering representation. To support this access modality, image content can be modeled in terms of different types of features such as shape, texture, color, and spatial arrangement. An original framework is presented which supports quantitative nonsymbolic representation and comparison of the mutual positioning of extended nonrectangular spatial entities. Properties of the model are expounded to develop an efficient computation technique and to motivate and assess a metric of similarity for quantitative comparison of spatial relationships. Representation and comparison of binary relationships between entities is then embedded into a graph-theoretical framework supporting representation and comparison of the spatial arrangements of a picture. Two prototype applications are described.

In retrieval from image databases, evaluation of similarity, based both on the appearance of spatial entities and on their mutual relationships, depends on content representation based on attributed relational graphs. This kind of modeling entails complex matching and indexing, which presently prevents its usage within comprehensive applications. In this paper, we provide a graph-theoretical formulation for the problem of retrieval based on the joint similarity of individual entities and of their mutual relationships and we expound its implications on indexing and matching. In particular, we propose the usage of metric indexing to organize large archives of graph models, and we propose an original look-ahead method which represents an efficient solution for the (sub)graph error correcting isomorphism problem needed to compute object distances. Analytic comparison and experimental results show that the proposed lookahead improves the state-of-the-art in state-space search methods and that the combined use of the proposed matching and indexing scheme permits for the management of the complexity of a typical application of retrieval by spatial arrangement.

An enumerative technique is presented which supports reachability and timeliness analysis of time-dependent models. The technique assumes a dense model of time and uses equivalence classes to enable discrete and compact enumeration of the state space. Properties of timed reachability among states are recovered through the analysis of timing constraints embedded within equivalence classes. In particular, algorithms are given to evaluate a tight profile for the set of feasible timings of any untimed run. Runtime refinement of static profiles supports a mixed static/dynamic strategy in the development of a failure avoidance mechanism for dynamic acceptance and a guarantee of hard real-time processes.

Image retrieval by spatial arrangement underlies a matching problem for the interpretation of entities specified in the user query on the entities appearing in the image of the database, and for the joint comparison of their features and spatial relationships. In this paper, we provide a graph-theoretical formulation of the problem and discuss its implication on indexing and matching. We first identify an indexing scheme which may fit the characteristics of the problem, and then expound and evaluate an efficient graph matching technique which makes this indexing approach viable.

A visual formalism for the presentation of a real time logic is introduced, motivated, and evaluated.The visual formalism has been designed following a user-centered usability engineering process, targeted to the students of higher education courses in software engineering. On the one hand, heuristic design was applied to maximize consistency, i.e. to minimize the complexity of the visual metaphor mapping textual sentences to the visual representation. On the other hand, individual metaphoric assumptions were defined by prototyping and exposing alternative graphical representations to a representative sample of the target community of expected users.The resulting notation has been implemented within an interactive syntax-directed editor which integrates the visual presentation with the conventional textual notation. The editor has been used to carry out a competitive user-based evaluation of the usability of textual and visual representations, by carrying out a readability test on a larger sample of representative end-users.

Retrieval by content from image databases faces the distance between low-level syntactic features that can be automatically detected by conventional image processing tools and high level semantics which captures user's filtering intentions. A system is presented which bridges this gap by resorting to a theory formulated by Johannes Itten in 1960, and widely accepted in the community of fine arts, to support objective interpretation of color arrangements over paintings. The system relies upon a schema distinguishing archiving, querying, and retrieval stages. In the archiving stage, images are associated with a description capturing the spatial arrangement of regions with homogeneous chromatic attributes, as detected by the use of an automatic image processing tool. Imprecise descriptions are supported through the adoption of a hierarchical index providing a multi-resolution representation of image contents. In the querying stage, a visual iconic language allows the expression of sentences about chromatic contents in accordance with a high-level semantic model of colors combinations. By permitting flexible expression of abstract, non-literal, properties, the model supports intentional vagueness and incompleteness in the specification of searching queries. In the retrieval stage, a similarity score is introduced, which accounts for the degree with which a query assertion applies to a given image. The measure of similarity drives the traversal of the hierarchical index up to find the minimum level of description precision, permitting a definite decision about the satisfaction of the query on each stored image. © 1998 John Wiley & Sons, Inc.

High level operational languages support the specification and validation of complex reactive systems through the automatic generation of rapid prototypes since the early stages of the development lifecycle. However, when it comes to the implementation stage, these prototypes must be translated into target code to accomplish performance requirements without losing validation results. A transformation method supporting the incremental and automatic transition from rapid prototypes to target code is presented, which relies on a Petri net based specification language. Experimental results are presented to evaluate the performance improvement achieved by this automatic transformation.>

The emergence of advanced multimedia applications is emphasizing the relevance of retrieval by contents within databases of images and image sequences. Matching the inherent visuality of the information stored in such databases, visual specification by example provides an effective and natural way to express content-oriented queries. To support this querying approach, the system must be able to interpret example scenes reproducing the contents of images and sequences to be retrieved, and to match them against the actual contents of the database. In the accomplishment of this task, to avoid a direct access to raw image data, the system must be provided with an appropriate description language supporting the representation of the contents of pictorial data. An original language for the symbolic representation of the contents of image sequences is presented. This language, referred to as spatio-temporal logic, comprises a framework for the qualitative representation of the contents of image sequences, which allows for treatment and operation of content structures at a higher level than pixels or image features. Organization and operation principles of a prototype system exploiting spatio-temporal logic to support querying by example through visual iconic interaction are expounded.>

An extended Petri net model which considers modular partitioning along with timing restrictions and environment models is presented. Module constructs permit the specification of a complex system as a set of message passing modules with the timing semantics of time Petri nets. The state space of each individual module can be separately enumerated and assessed under the assumption of a partial specification of the intended module operation environment. State spaces of individual modules can be recursively integrated, to permit the assessment of module clusters and of the overall model, and to check the satisfaction of the assumptions made in the separate analysis of elementary component modules. In the intermediate stages between subsequent integration steps, the state spaces of module and module clusters can be projected onto reduced representations concealing local events that are not essential to the purposes of the analysis. The joint use of incremental enumeration and intermediate concealment of local events allows for a flexible management of state explosion, and permits a scalable approach to the validation of complex systems.

The development of virtual agents running within graphic environments which emulate real-life contexts may largely benefit from the use of visual specification by-example. To support this specification, the development system must be able to interpret the examples and cast their underlying rules into an internal representation language. This language must find a suitable trade-off among a number of contrasting requirements regarding expressiveness, automatic executability, and suitability to the automatic representation of rules deriving from the analysis of examples. A language is presented which attains this trade-off by combining together an operational and a declarative fragment to separately represent the autonomous execution of each individual agent and its interaction with the environment, respectively. While the declarative part permits to capture interaction rules emerging from specification examples, the operational part supports the automatic execution in the operation of the virtual environment. A system is presented which embeds this language within a visual shell to support a behavioral training in which the animation rules of virtual agents are defined through visual examples.

The performance evaluation of transport protocols is a relevant step for designing efficient distributed applications. This analysis can be performed either with an unloaded medium or in the presence of background load. In this latter case, the effects of the interaction with other users are made evident, but remarkable difficulties exist to obtain a reproducible network load and to achieve accuracy in measurements. In this paper, performance measurements in the presence of background load are presented for TCP and UDP in the Internet family. And SPP and IDP in the Xerox Network System family. Experiments were carried out over an Ethernet LAN with MS-DOS AT-class stations.>

A framework for the development of distributed object-oriented systems in heterogeneous environments is presented. This model attempts to incorporate concepts of distributed computing technology together with software engineering methods. A tool has been developed to enforce the model by means of a high-level specification language and an automatic code generator. However, it is emphasized that the model may be exploited as a methodologic foundation even outside an automatic generation approach.>

The design and implementation of a tool for the construction of distributed systems are described. This tool is based on a specification model which extends ordinary Petri nets to include functional and structural concepts. Functional extensions give the model specification completeness, whereas structuring extensions support the organization of the system under development into a set of message passing modules. The augmented model is named communicating Petri net (CmPN). After an introduction to communicating Petri nets, an outline of the software lifecycle activities enforced by the tool under development is given. Two different methods for automatic code generation are expounded and compared in terms of both computational run-time overhead and code dimension (in the case of an example comprised of four CmPNs).>

Results of an analysis of the communication performance as perceived by the application layer in the presence of background load are presented. The analysis was carried out on two distinct protocol suites, TCP/IP and XNS, on a single Ethernet LAN with personal computer workstations. Service times for a reliable transfer and an unreliable transmission as perceived by the application layer were measured. An appropriate model of the reliable transfer process was used to derive service time analytical estimates. Owing to the close relation between measured and estimated values, the model was used to identify the major sources of delay and to evaluate the effects of possible improvements. The most important causes affecting the transport layer performance as background load increases are identified, and different strategies are examined in order to reduce their impact. The improvement margin offered by the implementation of a lightweight transport protocol specifically tailored to the requirements of a bulk data transfer over an Ethernet is addressed.>