Given the high cost of formal verification, a large system may include differently analyzed components: a few are fully verified, and the rest are tested. Currently, there is no reasoning system that can soundly compose these heterogeneous analyses and derive the overall formal guarantees of the entire system. The traditional compositional reasoning technique—rely-guarantee reasoning—is effective for verified components, which undergo over-approximated reasoning, but not for those components that undergo under-approximated reasoning, e.g., using testing or other program analysis techniques. The goal of this paper is to develop a formal, logical foundation for composing heterogeneous analysis, deploying both over-approximated (verification) and under-approximated (testing) reasoning. We focus on systems that can be modeled as a collection of communicating processes. Each process owns its internal resources and a set of channels through which it communicates with other processes. The key idea is to quantify the guarantees obtained about the behavior of a process as a test level , which captures the constraints under which this guarantee is analyzed to be true. We design a novel proof system LabelBI based on the logic of bunched implications that enables rely-guarantee reasoning principles for a system of differently analyzed components. We develop trace semantics for this logic, against which we prove our logic is sound. We also prove cut elimination of our sequent calculus. We demonstrate the expressiveness of our logic via a case study.

Verifying complex Cyber-physical Systems (CPSs) is increasingly important given the push to deploy safety-critical autonomous features. Unfortunately, traditional verification methods do not scale to the complexity of these systems and do not provide systematic methods to protect verified properties when not all the components can be verified. To address these challenges, this article proposes a real-time mixed-trust computing framework that combines verification and protection. The framework introduces a new task model, where an application task can have both an untrusted and a trusted part. The untrusted part allows complex computations supported by a full OS with a real-time scheduler running in a VM hosted by a trusted hypervisor. The trusted part is executed by another scheduler within the hypervisor and is thus protected from the untrusted part. If the untrusted part fails to finish by a specific time, the trusted part is activated to preserve safety (e.g., prevent a crash) including its timing guarantees. This framework is the first allowing the use of untrusted components for CPS critical functions while preserving logical and timing guarantees, even in the presence of malicious attackers. We present the framework, its schedulability analysis, and the coordination protocol between the trusted and untrusted parts. Our implementation on a Raspberry Pi 3 is also discussed along with experiments showing the behavior of the system under failures of untrusted components and a drone application to demonstrate its practicality.

This paper presents a task synchronization mechanism, called co-runner locking, to address the timing interference problem in multi-core real-time systems. It prevents certain subsets of tasks from executing simultaneously on different cores in order to avoid large performance penalties from inter-core interference. We provide the general properties of the co-runner locking mechanism and discuss the runtime control policies that determine the execution order of tasks in a co-runner-locking relationship. For schedulability analysis, we derive a response-time test that upper-bounds the delay from co-runner locking and the slowdown imposed by permitted co-runners by combining two new analytic approaches: job-oriented and load-oriented. In evaluation, we demonstrate that the co-runner locking mechanism is an effective alternative to address the "one-out-of-m" problem and brings about a significant improvement in real-time taskset schedulability.

In this paper we present a new scheduling model for resilient real-time mixed trust systems. This model extends the previous Real-Time Mixed-Trust Computing framework RT-MTC to support degradation modes. Management of these modes has been identified in industrial documents as a key requirement for deploying trusted autonomous vehicles for safe autonomy. RT-MTC uses verified components (known as enforcers) to guarantee that the output of a system is safe by replacing it with a verified safe one if this output is deemed unsafe or is not produced on time. In this paper we extend RT-MTC and develop a scheduling model that uses the digraph scheduling model as a baseline but extends it in four critical ways: (1) it creates extensions for the mixed-preemptive scheduling required by RT-MTC, (2) it enables priority bands in order to separate trusted and untrusted components, (3) it uses these bands in order to calculate intermediate deadlines used by the RT-MTC framework for the scheduling of the trusted components, and (4) it defines system mode semantics to obtain two desirable properties of the new schedulability analysis: low pessimism and low time-complexity. This paper evaluates the new schedulability algorithm and shows that it is efficient in that it only needs to analyze one transition at a time. The new model supports the construction of a resilient autonomous system with provable guarantees protected by verified enforcers within the RT-MTC framework and, more importantly, preserves these guarantees even across failure-triggered mode changes.

The Real-Time Mixed-Trust (RTMT) Framework [2] enables the use of untrusted components in safety-critical CPS functions (e.g., driving a car) by monitoring their actions with verified and trusted components (called enforcers ) that correct unsafe actions to guarantee critical safety properties (e.g., brake to prevent a crash). The enforcers are run within a verified hypervisor that protects them from security attacks or bugs and the untrusted components are run in an unverified virtual machine (VM) on top of the hypervisor. The untrusted and trusted components are executed as a single coordinated sporadic real-time task, called a mixed-trust task , where the untrusted part is known as the guest task (GT, because it runs in the guest VM) and the trusted part running in the hypervisor (HV) is known as the hypertask (HT). The GT is run by a preemptive fixed-priority scheduler in the VM and the HT by a non-preemptive fixed-priority scheduler in the HV. The non-preemptive scheduler prevents interleavings and simplifies the logical verification [4] , [5] . From a timing point of view, the HT monitors that the GT produces a valid output before the deadline, and if not, the HT itself produces a safe output before the deadline elapses. A new set of schedulability equations to evaluate their schedulability were presented in [2] along with a full discussion of the framework.

Verifying complex Cyber-Physical Systems (CPS) is increasingly important given the push to deploy safety-critical autonomous features. Unfortunately, traditional verification methods do not scale to the complexity of these systems and do not provide systematic methods to protect verified properties when not all the components can be verified. To address these challenges, this paper proposes a real-time mixed-trust computing framework that combines verification and protection. The framework introduces a new task model, where an application task can have both an untrusted and a trusted part. The untrusted part allows complex computations supported by a full OS with a realtime scheduler running in a VM hosted by a trusted hypervisor. The trusted part is executed by another scheduler within the hypervisor and is thus protected from the untrusted part. If the untrusted part fails to finish by a specific time, the trusted part is activated to preserve safety (e.g., prevent a crash) including its timing guarantees. This framework is the first allowing the use of untrusted components for CPS critical functions while preserving logical and timing guarantees, even in the presence of malicious attackers. We present the framework design and implementation along with the schedulability analysis and the coordination protocol between the trusted and untrusted parts. We also present our Raspberry Pi 3 implementation along with experiments showing the behavior of the system under failures of untrusted components, and a drone application to demonstrate its practicality.

Consider fixed-priority preemptive partitioned scheduling of constrained-deadline sporadic tasks on a multiprocessor. A task generates a sequence of jobs and each job has a deadline that must be met. Assume tasks have Corunner-dependent execution times; i.e., the execution time of a job J depends on the set of jobs that happen to execute (on other processors) at instants when J executes. We present a model that describes Corunner-dependent execution times. For this model, we show that exact schedulability testing is co-NP-hard in the strong sense. Facing this complexity, we present a sufficient schedulability test, which has pseudo-polynomial-time complexity if the number of processors is fixed. We ran experiments with synthetic software benchmarks on a quad-core Intel multicore processor with the Linux/RK operating system and found that for each task, its maximum measured response time was bounded by the upper bound computed by our theory.

While a number of schemes exist for mixed-criticality scheduling in a single processor setting, no solution exists to cover the industry need for end-to-end scheduling across multiple processors in a pipeline. In this paper, we present an end-to-end zero-slack rate-monotonic scheme (ZSRM) based on real-time pipelines, called the ZSRM pipeline scheduler, that addresses this need. Under ZSRM, each task is associated with a parameter called zero-slack instant, and whenever a higher-criticality job has not finished at its zero-slack instant relative to its arrival time, all jobs of lower criticality are suspended to meet the deadline of the higher-criticality job. We develop a new schedulability test and algorithm for computing the zero-slack instants of tasks scheduled across a pipeline.

Cyber-physical system (CPS) have been recognized as a top-priority in research and development. The innovations sought for CPS demand them to deal effectively with dynamicity of their environment, to be scalable, adaptive, tolerant to threats, etc. -- i.e. they have to be smart. Although approaches in software engineering (SE) exist that individually meet these demands, their synergy to address the challenges of smart CPS (sCPS) in a holistic manner remains an open challenge. The workshop focuses on software engineering challenges for sCPS. The goals are to increase the understanding of problems of SE for sCPS, study foundational principles for engineering sCPS, and identify promising SE solutions for sCPS. Based on these goals, the workshop aims to formulate a research agenda for SE of sCPS.

In commercial-off-the-shelf (COTS) multi-core systems, a task running on one core can be delayed by other tasks running simultaneously on other cores due to interference in the shared DRAM main memory. Such memory interference delay can be large and highly variable, thereby posing a significant challenge for the design of predictable real-time systems. In this paper, we present techniques to provide a tight upper bound on the worst-case memory interference in a COTS-based multi-core system. We explicitly model the major resources in the DRAM system, including banks, buses and the memory controller. By considering their timing characteristics, we analyze the worst-case memory interference delay imposed on a task by other tasks running in parallel. To the best of our knowledge, this is the first work bounding the request re-ordering effect of COTS memory controllers. Our work also enables the quantification of the extent by which memory interference can be reduced by partitioning DRAM banks. We evaluate our approach on a commodity multi-core platform running Linux/RK. Experimental results show that our approach provides an upper bound very close to our measured worst-case interference.

An organization is architecturally competent if it has the ability to acquire, use and sustain the skills and knowledge necessary to carry out architecture-related practices that lead to systems that serve the organization's business goals. This paper presents some principles of architecture competence, based on four models that aid in explaining, measuring, and improving the architecture competence of an individual or an organization with respect to these principles, The principles are based on a set of fundamental beliefs about software architecture.

The Architecture Expert (ArchE) is a software architecture design assistant under development at the Software Engineering Institute (SEI). It embodies knowledge of quality attributes and the relation between the achievement of quality attribute requirements and architecture design. In this paper, we describe the use of ArchE in a graduate level software architecture class at Clemson University. The discussion combines aspects of using ArchE as a tool to produce architectures and using ArchE to teach about architecting. The students were positive about the use of ArchE although critical of ArchE's immaturity. The instructor was also positive about the use of ArchE.

Much research in the software architecture field has focused on the purely technical aspects of architecting: architectural styles, documentation, analysis, architecture description languages, reverse engineering, and so forth. In this working session we seek to explore a less exhaustively studied, but equally important, realm: architectural competence. What defines a competent software architect? And equally important, what defines an architecturally competent software development organization? In particular, we seek to better understand the following issues: (a) What do architects actually do on a day-to-day basis? (b) What skills and knowledge must a competent architect have? (c) What does it mean to be a competent architect? (d) What can an organization do to get the best performance from its software architects? (e) How can we measure architectural competence of an individual or an organization and how can we increase this? Our goal for this working session is to propose an initial "theory" of architectural competence, even if very informally rendered, and then provide some practical guidance deriving from that theory to practicing architects (and to those who aspire to be architects), as well as technical managers in software development organizations.

This paper focuses on the human aspects of architecting software-in particular, the duties, skills, and knowledge of software architects. We present the results of a survey of approximately 200 public sources of information aimed at professional software architects that we conducted in the summer of 2006. We summarize what those sources have to say about the duties, skills, and knowledge that competent architects must perform and have.

This paper presents a technique developed at the Software Engineering Institute (SEI) for encapsulating quality attribute knowledge for use in the design and validation of software architectures. A reasoning framework, our encapsulation mechanism, can be used by nonexperts to analyze a specific quality (e.g., performance, modifiability, availability) of a system.

ArchE (Architecture Expert) is an rule based system that contains a model of modifiability. The model plus modifiability scenarios that characterize expected change enable ArchE to collaborate with an architect to produce a design of the architecture that supports the expected change. ArchE has been used with real requirements from a manufacturer. This paper describes the model used in ArchE and how the architect and ArchE interact in order to produce a design.

This paper outlines experiences with using economic criteria to make architecture design decisions. It briefly describes the CBAM (Cost Benefit Analysis Method) framework applied to estimate the value of architectural strategies in a NASA project, the ECS. This paper describes the practical difficulties and experiences in applying the method to a large realworld system. It concludes with some lessons learned from the experience.

In this paper we discuss a set of architecture-based methods for architecture design and analysis that have been developed over the past 10 years at the Software Engineering Institute. We then discuss the need for integrating these architecture-based methods, both with each other and into an organization's system development life cycle, based on experience with NASA's EOSDIS project. We discuss the framework for doing this integration, and present a life cycle view of architecture-based design and analysis methods.

Reservation-based operating systems provide applications with guaranteed and timely access to system resources. One of their chief benefits is temporal isolation, which prevents the timing mis-behavior of one task from interfering with other tasks. Such a benefit is appealing enough that many systems [2, 8] desire to recursively apply this reservation model to each of their components. This recursive application provides flexible load isolation among applications, users and other high-level resource management entities such as aggregated flows for network bandwith. The hierarchical reservation study can be applied to hierarchical schedulers [5, 6], that support heterogenous scheduling algorithms. We propose and analyze a hierarchical reservation model in the context of fixed-priority scheduling, rate-monotonic and deadline-monotonic, as used in systems such as the Resource Kernel [11]. Detailed schedulability analyses under both deferrable-server and sporadic-server replenishment schemes, including exact completion time tests under hierarchical deadline-monotonic schedulers, are presented. We also derive the least upper scheduling bound for hierarchicalrate-monotonic schedulers. Finally, we describe how to apply multi-reserve PCP [4 ], an extension of the Priority Ceiling Protocol for reservation-based systems, to allow tasks to share non-preemptable resources across the hierarchy.

The benefits of a software system are assessable only relative to the business goals the system has been developed to serve. In turn, these benefits result from interactions between the system's functionality and its quality attributes (such as performance, reliability and security). Its quality attributes are, in most cases, dictated by its architectural design decisions. Therefore, we argue that the software architecture is the crucial artifact to study in making design tradeoffs and in performing cost-benefit analyses. A substantial part of such an analysis is in determining the level of uncertainty with which we estimate both costs and benefits. We offer an architecture-centric approach to the economic modeling of software design decision making called CBAM (Cost Benefit Analysis Method), in which costs and benefits are traded off with system quality attributes. We present the CBAM, the early results from applying this method in a large-scale case study, and discuss the application of more sophisticated economic models to software decision making.

This tutorial will discuss, exemplify, and involve the students in the use of Attribute-Based Architectural Styles (ABASs)—architectural styles accompanied by explicit analysis reasoning frameworks—in both the design and analysis of software and system architectures. The tutorial has several objectives: to introduce the students to a catalog of ABASs covering performance, availability, testability, modifiability, and usability; to convince students that ABASs provide a basis for insightful reasoning about a software architecture's ability to meet its quality attribute goals; and to demonstrate the utility of ABASs by showing examples of how ABASs are used to design and analyze real-world system architectures. We will present some large excerpts from our growing ABAS handbook and show that ABASs help us in designing architectures efficiently and predictably and in quickly finding architectural risks and tradeoffs when doing analysis.

Article Experience with performing architecture tradeoff analysis Share on Authors: Rick Kazman Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PAView Profile , Mario Barbacci Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PAView Profile , Mark Klein Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PAView Profile , S. Jeromy Carrière Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PAView Profile , Steven G. Woods Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PA Software Engineering Institute, Carnegie Mellon University, Pittsburgh, PAView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 54–63https://doi.org/10.1145/302405.302452Online:16 May 1999Publication History 103citation1,056DownloadsMetricsTotal Citations103Total Downloads1,056Last 12 Months16Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents the Architecture Tradeoff Analysis Method (ATAM), a structured technique for understanding the tradeoffs inherent in the architectures of software-intensive systems. This method was developed to provide a principled way to evaluate a software architecture's fitness with respect to multiple competing quality attributes: modifiability, security, performance, availability, and so forth. These attributes interact-improving one often comes at the price of worsening one or more of the others-as is shown in the paper, and the method helps us to reason about architectural decisions that affect quality attribute interactions. The ATAM is a spiral model of design: one of postulating candidate architectures followed by analysis and risk mitigation, leading to refined architectures.

This paper presents a timing analysis for a quite general hard real-time periodic task set on a uniprocessor using fixed-priority methods. Periodic tasks are composed of serially executed subtasks, where each subtask is characterized by an execution time, a fixed priority and a deadline. A method for determining the schedulability of each task and subtask is presented along with its theoretical underpinnings. This method can be used to analyze the schedulability of any task set on a uniprocessor whose priority structure can be modeled as serially executed subtasks, which can lead to a very complex priority structure. Important examples include task sets that involve interrupts, certain synchronization protocols, certain precedence constraints, nonpreemptible sections, and some message-passing systems. The method is illustrated by a robotics example.>

The problem of fixed priority scheduling of periodic tasks where each task's execution priority may vary is considered. Periodic tasks are decomposed into serially executed subtasks, where each subtask is characterized by an execution time and a fixed priority and is permitted to have a deadline. A method for determining the schedulability of each task is presented along with its theoretical underpinnings. This method can be used to analyze the schedulability of complex task sets which involve interrupts, certain synchronization protocols, nonpreemptible sections and, in general, any mechanism that contributes to a complex priority structure. The authors introduce a simple but realistic real-time robotics application and illustrate how one uses the schedulability equations presented.>