Computer Engineering Commons^™

Contracts Made Manifest, Michael Greenberg, Benjamin C. Pierce, Stephanie Weirich

Stephanie Weirich

Since Findler and Felleisen (Findler, R. B. & Felleisen, M. 2002) introduced higher-order contracts, many variants have been proposed. Broadly, these fall into two groups: some follow Findler and Felleisen (2002) in using latent contracts, purely dynamic checks that are transparent to the type system; others use manifest contracts, where refinement types record the most recent check that has been applied to each value. These two approaches are commonly assumed to be equivalent—different ways of implementing the same idea, one retaining a simple type system, and the other providing more static information. Our goal is to formalize and clarify this …

Combining Proofs And Programs In A Dependently Typed Language, Stephanie Weirich, Vilhelm Sjoberg, Chris Casinghino

Stephanie Weirich

Most dependently-typed programming languages either require that all expressions terminate (e.g. Coq, Agda, and Epigram), or allow infinite loops but are inconsistent when viewed as logics (e.g. Haskell, ATS, mega). Here, we combine these two approaches into a single dependently-typed core language. The language is composed of two fragments that share a common syntax and overlapping semantics: a logic that guarantees total correctness, and a call-by-value programming language that guarantees type safety but not termination. The two fragments may interact: logical expressions may be used as programs; the logic may soundly reason about potentially nonterminating programs; programs can require logical …

Programming Up To Congruence (Extended Version), Vilhelm Sjoberg, Stephanie Weirich

Stephanie Weirich

This paper presents the design of ZOMBIE, a dependently-typed programming language that uses an adaptation of a congruence closure algorithm for proof and type inference. This algorithm allows the type checker to automatically use equality assumptions from the context when reasoning about equality. Most dependently typed languages automatically use equalities that follow from -reduction during type checking; however, such reasoning is incompatible with congruence closure. In contrast, ZOMBIE does not use automatic -reduction because types may contain potentially diverging terms. Therefore ZOMBIE provides a unique opportunity to explore an alternative definition of equivalence in dependently typed language design. Our work …

Closed Type Families With Overlapping Equations (Extended Version), Richard A. Eisenberg, Dimitrios Vytiniotis, Simon Peyton Jones, Stephanie Weirich

Stephanie Weirich

Open, type-level functions are a recent innovation in Haskell that move Haskell towards the expressiveness of dependent types, while retaining the look and feel of a practical programming language. This paper shows how to increase expressiveness still further, by adding closed type functions whose equations may overlap, and may have non-linear patterns over an open type universe. Although practically useful and simple to implement, these features go beyond conventional dependent type theory in some respects, and have a subtle metatheory.

Data Management In Cloud Environments: Nosql And Newsql Data Stores, Katarina Grolinger, Wilson A. Higashino, Abhinav Tiwari, Miriam Am Capretz

Wilson A Higashino

: Advances in Web technology and the proliferation of mobile devices and sensors connected to the Internet have resulted in immense processing and storage requirements. Cloud computing has emerged as a paradigm that promises to meet these requirements. This work focuses on the storage aspect of cloud computing, specifically on data management in cloud environments. Traditional relational databases were designed in a different hardware and software era and are facing challenges in meeting the performance and scale requirements of Big Data. NoSQL and NewSQL data stores present themselves as alternatives that can handle huge volume of data. Because of the …

Co-Design Of Control And Platform With Dropped Signals, Damoon Soudbakhsh, Linh T.X. Phan, Oleg Sokolsky, Insup Lee, Anuradha Annaswamy

Oleg Sokolsky

This paper examines a co-design of control and platform in the presence of dropped signals. In a cyber-physical system, due to increasing complexities such as the simultaneous control of several applications, limited resources, and complex platform architectures, some of the signals transmitted may often be dropped. In this paper, we address the challenges that arise both from the control design and the platform design point of view. A dynamic model is proposed that accommodates these drops, and a suitable switching control design is proposed. A Multiple Lyapunov function based approach is used to guarantee the stability of the system with …

Model-Based Development Of The Generic Pca Infusion Pump User Interface Prototype In Pvs, Paolo Masci, Anaheed Ayoub, Paul Curzon, Insup Lee, Oleg Sokolsky, Harold Thimbleby

Oleg Sokolsky

A realistic user interface is rigorously developed for the US Food and Drug Administration (FDA) Generic Patient Controlled Analgesia (GPCA) pump prototype. The GPCA pump prototype is intended as a realistic workbench for trialling development methods and techniques for improving the safety of such devices. A model-based approach based on the use of formal methods is illustrated and implemented within the Prototype Verification System (PVS) verification system. The user interface behaviour is formally specified as an executable PVS model. The specification is verified with the PVS theorem prover against relevant safety requirements provided by the FDA for the GPCA pump. …

Cache-Aware Compositional Analysis Of Real-Time Multicore Virtualization Platforms, Meng Xu, Linh T.X. Phan, Insup Lee, Oleg Sokolsky, Sisu Xi, Chenyang Lu, Christopher Gill

Oleg Sokolsky

Multicore processors are becoming ubiquitous, and it is becoming increasingly common to run multiple real-time systems on a shared multicore platform. While this trend helps to reduce cost and to increase performance, it also makes it more challenging to achieve timing guarantees and functional isolation. One approach to achieving functional isolation is to use virtualization. However, virtualization also introduces many challenges to the multicore timing analysis; for instance, the overhead due to cache misses becomes harder to predict, since it depends not only on the direct interference between tasks but also on the indirect interference between virtual processors and the …

Towards Synthesis Of Platform-Aware Attack-Resilient Control Systems: Extended Abstract, Miroslav Pajic, Nicola Bezzo, James Weimer, Rajeev Alur, Rahul Mangharam, Nathan Michael, George J. Pappas, Oleg Sokolsky, Paulo Tabuada, Stephanie Weirich, Insup Lee

Oleg Sokolsky

No abstract provided.

Platform-Dependent Code Generation For Embedded Real-Time Software, Baekgyu Kim, Linh T.X. Phan, Oleg Sokolsky, Insup Lee

Oleg Sokolsky

Code generation for embedded systems is challenging, since the generated code (e.g., C code) is expected to run on a heterogeneous set of target platforms with different characteristics, such as hardware/software architectures and programming interfaces. We propose a code generation framework that provides the flexibility to generate different source code that is executable on each target platform. In our framework, the platform-dependent characteristics of a target platform are explicitly specified by an Architectural Analysis Description Language (AADL) model and a code snippet repository. The AADL model captures hardware/software architectural aspects of the platform, such as periodic/aperiodic threads and their interactions …

Linking Abstract Analysis To Concrete Design: A Hierarchical Approach To Verify Medical Cps Safety, Anitha Murugesan, Oleg Sokolsky, Sanjai Rayadurgam, Michael Whalen, Mats Heimdahl, Insup Lee

Oleg Sokolsky

Complex cyber-physical systems are typically hierarchically organized into multiple layers of abstraction in order to manage design complexity and provide verification tractability. Formal reasoning about such systems, therefore, necessarily involves the use of multiple modeling formalisms, verification paradigms, and concomitant tools, chosen as appropriate for the level of abstraction at which the analysis is performed. System properties verified using an abstract component specification in one paradigm must then be shown to logically follow from properties verified, possibly using a different paradigm, on a more concrete component description, if one is to claim that a particular component when deployed in the …

Assuring The Safety Of On-Demand Medical Cyber-Physical Systems, Andrew L. King, Lu Feng, Oleg Sokolsky, Insup Lee

Oleg Sokolsky

We present an approach to establish safety of on-demand medical cyber-physical systems which are assembled to treat a patient in a specific clinical scenario. We treat such a system as a virtual medial device (VMD) and propose a model-based framework that includes a modeling language with formal semantics and a medical application platform (MAP) that provides the necessary deployment support for the VMD models.

Robustness Of Attack-Resilient State Estimators, Miroslav Pajic, James Weimer, Nicola Bezzo, Paulo Tabuada, Oleg Sokolsky, Insup Lee, George Pappas

Oleg Sokolsky

The interaction between information technology and physical world makes Cyber-Physical Systems (CPS) vulnerable to malicious attacks beyond the standard cyber attacks. This has motivated the need for attack-resilient state estimation. Yet, the existing state-estimators are based on the non-realistic assumption that the exact system model is known. Consequently, in this work we present a method for state estimation in presence of attacks, for systems with noise and modeling errors. When the the estimated states are used by a state-based feedback controller, we show that the attacker cannot destabilize the system by exploiting the difeerence between the model used for the …

Functional Alarms For Systems Of Interoperable Medical Devices, Krishna Venkatasubramanian, Eugene Vasserman, Oleg Sokolsky, Insup Lee

Oleg Sokolsky

Alarms are essential for medical systems in order to ensure patient safety during deteriorating clinical situations and inevitable device malfunction. As medical devices are connected together to become interoperable, alarms become crucial part in making them high-assurance, in nature. Traditional alarm systems for interoperable medical devices have been patient-centric. In this paper, we introduce the need for an alarm system that focuses on the correct functionality of the interoperability architecture itself, along with several considerations and design challenges in enabling them.

Runtime Assurance Based On Formal Specifications, Insup Lee, Sampath Kannan, Moonjoo Kim, Oleg Sokolsky, Mahesh Viswanathan

Oleg Sokolsky

We describe the Monitoring and Checking (MaC) framework which assures the correctness of the current execution at run-time. Monitoring is performed based on a formal specification of system requirements. MaC bridges the gap between formal specification and verification, which ensures the correctness of a design rather than an implementation, and testing, which partially validates an implementation. An important aspect of the framework is a clear separation between implementation-dependent description of monitored objects and high-level requirements specification. Another salient feature is automatic instrumentation of executable code. The paper presents an overview of the framework and two languages to specify monitoring scripts …

Resilient Parameter-Invariant Control With Application To Vehicle Cruise Control, James Weimer, Nicola Bezzo, Miroslav Pajic, George J. Pappas, Oleg Sokolsky, Insup Lee

Oleg Sokolsky

This work addresses the general problem of resilient control of unknown stochastic linear time-invariant (LTI) systems in the presence of sensor attacks. Motivated by a vehicle cruise control application, this work considers a first order system with multiple measurements, of which a bounded subset may be corrupted. A frequency-domain-designed resilient parameter-invariant controller is introduced that simultaneously minimizes the effect of corrupted sensors, while maintaining a desired closed-loop performance, invariant to unknown model parameters. Simulated results illustrate that the resilient parameter-invariant controller is capable of stabilizing unknown state disturbances and can perform state trajectory tracking.

Safety-Critical Medical Device Development Using The Upp2sf Model, Miroslav Pajic, Zhihao Jiang, Insup Lee, Oleg Sokolsky, Rahul Mangharam

Oleg Sokolsky

Software-based control of life-critical embedded systems has become increasingly complex, and to a large extent has come to determine the safety of the human being. For example, implantable cardiac pacemakers have over 80,000 lines of code which are responsible for maintaining the heart within safe operating limits. As firmware-related recalls accounted for over 41% of the 600,000 devices recalled in the last decade, there is a need for rigorous model-driven design tools to generate verified code from verified software models. To this effect we have developed the UPP2SF model-translation tool, which facilitates automatic conversion of verified models (in UPPAAL) to …

A Safety Argument Strategy For Pca Closed-Loop Systems: A Preliminary Proposal, Lu Feng, Andrew L. King, Sanjian Chen, Anaheed Ayoub, Junkil Park, Nicola Bezzo, Oleg Sokolsky, Insup Lee

Oleg Sokolsky

The emerging network-enabled medical devices impose new challenges for the safety assurance of medical cyber-physical systems (MCPS). In this paper, we present a case study of building a high-level safety argument for a patient-controlled analgesia (PCA) closed-loop system, with the purpose of exploring potential methodologies for assuring the safety of MCPS.

Understanding The Influence Of Blog On The Development Of Social Capital, Reza Vaezi, Gholamreza Torkzadeh, Jerry Cha-Jan Chang

Reza Vaezi

The rapid use and application of blogs in diverse areas such as education, marketing, journalism, and human resource management in recent years underlines the need for a better understanding of the impact of this new technology on social capital. Social capital reflects the norm of reciprocity and the level of trust among individuals who connect, interact, and benefit from one another. Blog is expected to influence the extent and the scope of this interaction by providing new means of networking among people. This paper examines the relationship between blog use and social capital and reports on the results of an …

The Use Of The Blackboard Architecture For A Decision Making System For The Control Of Craft With Various Actuator And Movement Capabilities, Jeremy Straub, Hassan Reza

Jeremy Straub

This paper provides an overview of an approach to the control of multiple craft with heterogeneous movement and actuation characteristics that is based on the Blackboard software architecture. An overview of the Blackboard architecture is provided. Then, the operational and mission requirements that dictate the need for autonomous control are characterized and the utility of the Blackboard architecture is for meeting these requirements is discussed. The performance of a best-path solver and naïve solver are compared. The results demonstrate that the best-path solver outperforms the naïve solver in the amount of time taken to generate a solution; however, the number …

Openorbiter Operating Software, Dayln Limesand, Christoffer Korvald, Jeremy Straub, Ronald Marsh

Jeremy Straub

The operating software team of the OpenOrbiter project has been tasked with developing software for general spacecraft maintenance, performing mission tasks and the monitoring of system critical aspects of the spacecraft. To do so, the team is developing an autonomous system that will be able to continuously check sensors for data, and schedule tasks that pertain to the current mission and general maintenance of the onboard systems. Development in support of these objectives is ongoing with work focusing on the completion of the development of a stable system. This poster will present an overview of current work on the project …

Using Meta-Ethnography To Synthesize Research: A Worked Example Of The Relations Between Personality On Software Team Processes, Fabio Q. B. Silva Dr., Shirley S. J. O. Cruz, Tatiana B. Gouveia, Luiz Fernando Capretz

Luiz Fernando Capretz

Context: The increase in the number of qualitative and mixed-methods research published in software engineering has created an opportunity for further knowledge generation through the synthesis of studies with similar aims. This is particularly true in the research on human aspects because the phenomena of interest are often better understood using qualitative research. However, the use of qualitative synthesis methods is not widespread and worked examples of their consistent application in software engineering are needed. Objective: To explore the use of meta-ethnography in the synthesis of empirical studies in software engineering through an example using studies about the relations between …

Disaster Data Management In Cloud Environments, Katarina Grolinger

Katarina Grolinger

Facilitating decision-making in a vital discipline such as disaster management requires information gathering, sharing, and integration on a global scale and across governments, industries, communities, and academia. A large quantity of immensely heterogeneous disaster-related data is available; however, current data management solutions offer few or no integration capabilities and limited potential for collaboration. Moreover, recent advances in cloud computing, Big Data, and NoSQL have opened the door for new solutions in disaster data management. In this thesis, a Knowledge as a Service (KaaS) framework is proposed for disaster cloud data management (Disaster-CDM) with the objectives of 1) facilitating information gathering …

Data Management In Cloud Environments: Nosql And Newsql Data Stores, Katarina Grolinger, Wilson A. Higashino, Abhinav Tiwari, Miriam Am Capretz

Katarina Grolinger

: Advances in Web technology and the proliferation of mobile devices and sensors connected to the Internet have resulted in immense processing and storage requirements. Cloud computing has emerged as a paradigm that promises to meet these requirements. This work focuses on the storage aspect of cloud computing, specifically on data management in cloud environments. Traditional relational databases were designed in a different hardware and software era and are facing challenges in meeting the performance and scale requirements of Big Data. NoSQL and NewSQL data stores present themselves as alternatives that can handle huge volume of data. Because of the …

Probabilistic Verification Of Coordinated Multi-Robot Missions, Sagar J. Chaki, Joseph A. Giampapa

Joseph Andrew Giampapa

Robots are increasingly used to perform a wide variety of tasks, especially those involving dangerous or inaccessible locations. As the complexity of such tasks grow, robots are being deployed in teams, with complex coordination schemes aimed at maximizing the chance of mission success. Such teams operate under inherently uncertain conditions -- the robots themselves fail, and have to continuously adapt to changing environmental conditions. A key challenge facing robotic mission designers is therefore to construct a mission -- i.e., specify number and type of robots, number and size of teams, coordination and planning mechanisms etc. -- so as to maximize …

Rapport: Semantic-Sensitive Namespace Management In Large-Scale File Systems, Yu Hua, Hong Jiang, Yifeng Zhu, Dan Feng

Yifeng Zhu

Explosive growth in volume and complexity of data exacerbates the key challenge to effectively and efficiently manage data in a way that fundamentally improves the ease and efficacy of their use. Existing large-scale file systems rely on hierarchically structured namespace that leads to severe performance bottlenecks and renders it impossible to support real-time queries on multi-dimensional attributes. This paper proposes a novel semantic-sensitive scheme, called Rapport, to provide dynamic and adaptive namespace management and support complex queries. The basic idea is to build files’ namespace by utilizing their semantic correlation and exploiting dynamic evolution of attributes to support namespace management. …

Optimizing Parallel Belief Propagation In Junction Trees Using Regression, Lu Zheng, Ole J. Mengshoel

Ole J Mengshoel

Making Sense Of Software Development And Personality Types, Luiz Fernando Capretz, Faheem Ahmed Dr.

Luiz Fernando Capretz

No abstract provided.

How To Build An Rss Feed Using Asp, Umakant Mishra

Umakant Mishra

RSS is a XML based format. The Current popular version of RSS is RSS version 2.0. The purpose of adding an RSS feed to your site is to show if anything new is added to the site. For example, if a new article or blog or news item is added to your site that should automatically appear in the RSS feed so that the visitors/ RSS readers will automatically get updated about this new addition. The RSS feed is also called RSS channel.

There are two main elements of the RSS XML file, one is the header or channel element …

Exploring Multiple Dimensions Of Parallelism In Junction Tree Message Passing, Lu Zheng, Ole J. Mengshoel

Ole J Mengshoel