Many of today’s message-passing systems not only require messages to be exchanged in a certain order but also to happen at a certain time or within a certain time window . Such correctness conditions are particularly prominent in Internet of Things (IoT) and real-time systems applications, which interface with hardware devices that come with inherent timing constraints. Verifying compliance of such systems with the intended timed protocol is challenged by their heterogeneity —ruling out any verification method that relies on the system to be implemented in one common language, let alone in a high-level and typed programming language. To address this challenge, this paper contributes a logical relation to verify that its inhabitants (the applications and hardware devices to be proved correct) comply with the given timed protocol. To cater to the systems’ heterogeneity, the logical relation is entirely semantic , lifting the requirement that its inhabitants are syntactically well-typed. A semantic approach enables two modes of use of the logical relation for program verification: (i) once-and-for-all verification of an arbitrary well-typed application, given a type system, and (ii) per-instance verification of a specific application / hardware device ( a.k.a ., foreign code). To facilitate mode (i) , the paper develops a refinement type system for expressing timed message-passing protocols and proves that any well-typed program inhabits the logical relation (fundamental theorem). A type checker for the refinement type system has been implemented in Rust, using an SMT solver to check satisfiability of timing constraints. Then, the paper demonstrates both modes of use based on a small case study of a smart home system for monitoring air quality, consisting of a controller application and various environment sensors.

Visual SLAM systems are concurrent, performance-critical systems that respond to real-time environmental conditions and are frequently deployed on resource-constrained hardware. Previous work has identified three interconnected systems challenges to building consistent, accurate, and robust SLAM systems— timeliness , concurrency , and context awareness . In this article, we analyze three popular, state-of-the-art frameworks with varying system designs and optimization techniques, and we quantify the extent to which they are affected by the aforementioned system challenges. We find that all SLAM systems must balance the interconnected nature of timeliness and accuracy, and different system designs and optimization techniques uniquely address this tension. Global-map-based SLAM systems typically achieve the best performance but suffer in resource-constrained scenarios with increased concurrency . Across all SLAM systems, incorporating context awareness into decision-making would mitigate the impact of timeliness and concurrency on accuracy in resource-constrained scenarios.

We develop a session types framework for implementing and validating rate-based message passing systems in Internet of Things (IoT) domains. To model the indefinite repetition present in many embedded and IoT systems, we introduce a timed process calculus with a periodic recursion primitive. This allows us to model rate-based computations and communications inherent to these application domains. We introduce a definition of rate-based session types in a binary session types setting and a new compatibility relationship, which we call rate compatibility . Programs which type-check enjoy the standard session types guarantees as well as rate error freedom—meaning processes which exchanges messages do so at the same rate . Rate compatibility is defined through a new notion of type expansion, a relation that allows communication between processes of differing periods by synthesizing and checking a common superperiod type. We prove type preservation and rate error freedom for our system and show a decidable method for type checking based on computing superperiods for a collection of processes. We implement a prototype of our type system including rate compatibility via an embedding into the native type system of Rust. We apply this framework to a range of examples from our target domain such as Android software sensors, wearable devices, and sound processing. Our framework is used to implement a heart rate sensor application that runs on a commercially available smartwatch.

ARM Cortex-M is one of the most popular microcontroller architectures designed for embedded and Internet of Things (IoT) applications. To facilitate efficient execution, it has some unique hardware optimization. In particular, Cortex-M TrustZone has a fast state switch mechanism that allows direct control-flow transfer from the secure state program to the non-secure state userspace program. In this paper, we demonstrate how this fast state switch mechanism can be exploited for arbitrary code execution with escalated privilege in the non-secure state by introducing a new exploitation technique, namely return-to-non-secure (ret2ns). We experimentally confirmed the feasibility of four variants of ret2ns attacks on two Cortex-M hardware systems. To defend against ret2ns attacks, we design two address sanitizing mechanisms that have negligible performance overhead.

Identifying what front-end library runs on a web page is challenging. Although many mature detectors exist on the market, they suffer from false positives and the inability to detect libraries bundled by packers such as Webpack. Most importantly, the detection features they use are collected from developers' knowledge leading to an inefficient manual workflow and a large number of libraries that the existing detectors cannot detect. This paper introduces PTDETECTOR, which provides the first automated method for generating features and detecting libraries on web pages. We propose a novel data structure, the pTree, which we use as a detection feature. The pTree is well-suited for automation and addresses the limitations of existing detectors. We implement PTDETECTOR as a browser extension and test it on 200 top-traffic websites. Our experiments show that PTDETECTOR can identify packer-bundled libraries, and its detection results outperform existing tools.

We develop a session types based framework for implementing and validating rate-based message passing systems in Internet of Things (IoT) domains. To model the indefinite repetition present in many embedded and IoT systems, we introduce a timed process calculus with a periodic recursion primitive. This allows us to model rate-based computations and communications inherent to these application domains. We introduce a definition of rate based session types in a binary session types setting and a new compatibility relationship, which we call rate compatibility. Programs which type check enjoy the standard session types guarantees as well as rate error freedom --- meaning processes which exchanges messages do so at the same rate. Rate compatibility is defined through a new notion of type expansion, a relation that allows communication between processes of differing periods by synthesizing and checking a common superperiod type. We prove type preservation and rate error freedom for our system, and show a decidable method for type checking based on computing superperiods for a collection of processes. We implement a prototype of our type system including rate compatibility via an embedding into the native type system of Rust. We apply this framework to a range of examples from our target domain such as Android software sensors, wearable devices, and sound processing.

Visual SLAM is a long-standing research area with many significant advances over the years. New systems typically build on previous contributions, but this requires significant development overhead, a highly detailed understanding of previous system implementations, and is rife with programming pitfalls. To enable fast experimentation and reduce the need for researchers to re-invent the wheel, we propose an extensible Visual SLAM framework with three features: modularity, seamless edge offloading, and safe concurrency.

Abstract In this paper, we introduce a tiered-priority scheme for a synchronous message-passing language with support for selective communication and first-class communication protocols. Crucially, our scheme allows higher priority threads to communicate with lower priority threads, providing the ability to express programs that would be rejected by classic priority mechanisms that disallow any (potentially) blocking interactions between threads of differing priorities. We formalize our scheme in a novel semantic framework featuring a collection of actions to represent possible communications. Utilizing our formalism, we prove several important and desirable properties of our priority scheme. We also provide a prototype implementation of our tiered-priority scheme capable of expressing Concurrent ML and built in the MLton SML compiler and runtime. We evaluate the viability of our implementation through three case studies: a prioritized buyer-seller protocol and predictable shutdown mechanisms in the Swerve web server and eXene windowing toolkit. Our experiments show that priority can be easily added to existing CML programs without degrading performance. Our system exhibits negligible overheads on more modest workloads.

Unmanned Aerial Vehicles (UAVs) are an emerging computation platform known for their safety-critical need. In this paper, we conduct an empirical study on a widely used open-source UAV software framework, Paparazzi, with the goal of understanding the safety-critical concerns of UAV software from a bottom-updeveloper-in-the-fieldperspective. We set our focus on the use of Bounding Functions (BFs), the runtime checks injected by Paparazzi developers on the range of variables. Through an in-depth analysis on BFs in the Paparazzi autopilot software, we found a large number of them (109 instances) are used to bound safety-critical variables essential to the cyber-physical nature of the UAV, such as its thrust, its speed, and its sensor values. The novel contributions of this study are two fold. First, we take a static approach to classify all BF instances, presenting a noveldatatype-based5-category taxonomy with fine-grained insight on the role of BFs in ensuring the safety of UAV systems. Second, we dynamically evaluate the impact of the BF uses through adifferentialapproach, establishing the UAV behavioral difference with and without BFs. The two-pronged static and dynamic approach together illuminates a rarely studied design space of safety-critical UAV software systems.

UAVs are deployed in various applications including disaster search-and-rescue, precision agriculture, law enforcement and first response. As UAV software systems grow more complex, the drawbacks of developing them in low-level languages become more pronounced. For example, the lack of memory safety in C implies poor isolation between the UAV autopilot and other concurrent tasks. As a result, the most crucial aspect of UAV reliability-timely control of the flight-could be adversely impacted by other tasks such as perception or planning. We introduce JCopter, an autopilot framework for UAVs developed in a managed language, i.e., a high-level language with built-in safe memory and timing management. Through detailed simulation as well as flight testing, we demonstrate how JCopter retains the timeliness of C-based autopilots while also providing the reliability of managed languages.

Abstract In this paper, we describe our experience incorporating gradual types in a statically typed functional language with Hindley-Milner style type inference. Where most gradually typed systems aim to improve static checking in a dynamically typed language, we approach it from the opposite perspective and promote dynamic checking in a statically typed language. Our approach provides a glimpse into how languages like SML and OCaml might handle gradual typing. We discuss our implementation and challenges faced—specifically how gradual typing rules apply to our representation of composite and recursive types. We review the various implementations that add dynamic typing to a statically typed language in order to highlight the different ways of mixing static and dynamic typing and examine possible inspirations while maintaining the gradual nature of our type system. This paper also discusses our motivation for adding gradual types to our language, and the practical benefits of doing so in our industrial setting.

A compiler's optimizer operates over abstract syntax trees (ASTs), continuously applying rewrite rules to replace subtrees of the AST with more efficient ones. Especially on large source repositories, even simply finding opportunities for a rewrite can be expensive, as optimizer traverses the AST naively. In this paper, we leverage the need to repeatedly find rewrites, and explore options for making the search faster through indexing and incremental view maintenance (IVM). Concretely, we consider bolt-on approaches that make use of embedded IVM systems like DBToaster, as well as two new approaches: Label-indexing and TreeToaster, an AST-specialized form of IVM. We integrate these approaches into an existing just-in-time data structure compiler and show experimentally that TreeToaster can significantly improve performance with minimal memory overheads.

Abstract There is a growing interest in leveraging functional programming languages in real-time and embedded contexts. Functional languages are appealing as many are strictly typed, amenable to formal methods, have limited mutation, and have simple but powerful concurrency control mechanisms. Although there have been many recent proposals for specialized domain-specific languages for embedded and real-time systems, there has been relatively little progress on adapting more general purpose functional languages for programming embedded and real-time systems. In this paper, we present our current work on leveraging Standard ML (SML) in the embedded and real-time domains. Specifically, we detail our experiences in modifying MLton, a whole-program optimizing compiler for SML, for use in such contexts. We focus primarily on the language runtime, reworking the threading subsystem, object model, and garbage collector. We provide preliminary results over a radar-based aircraft collision detector ported to SML.

This paper presents a formulation of multiparty session types (MPSTs) for practical fault-tolerant distributed programming. We tackle the challenges faced by session types in the context of distributed systems involving asynchronous and concurrent partial failures – such as supporting dynamic replacement of failed parties and retrying failed protocol segments in an ongoing multiparty session – in the presence of unreliable failure detection. Key to our approach is that we develop a novel model of event-driven concurrency for multiparty sessions. Inspired by real-world practices, it enables us to unify the session-typed handling of regular I/O events with failure handling and the combination of features needed to express practical fault-tolerant protocols. Moreover, the characteristics of our model allow us to prove a global progress property for well-typed processes engaged in multiple concurrent sessions, which does not hold in traditional MPST systems. To demonstrate its practicality, we implement our framework as a toolchain and runtime for Scala, and use it to specify and implement a session-typed version of the cluster management system of the industrial-strength Apache Spark data analytics framework. Our session-typed cluster manager composes with other vanilla Spark components to give a functioning Spark runtime; e.g., it can execute existing third-party Spark applications without code modification. A performance evaluation using the TPC-H benchmark shows our prototype implementation incurs an average overhead below 10%.

This paper proposes Mimic, an automated UI compatibility testing system for Android apps. Mimic is designed specifically for comparing the UI behavior of an app across different devices, different Android versions, and different app versions. This design choice stems from a common problem that Android developers and researchers face-how to test whether or not an app behaves consistently across different environments or internal changes. Mimic allows Android app developers to easily perform backward and forward compatibility testing for their apps. It also enables a clear comparison between a stable version of app and a newer version of app. In doing so, Mimic allows multiple testing strategies to be used, such as randomized or sequential testing. Finally, Mimic programming model allows such tests to be scripted with much less developer effort than other comparable systems. Additionally, Mimic allows parallel testing with multiple testing devices and thereby speeds up testing time. To demonstrate these capabilities, we perform extensive tests for each of the scenarios described above. Our results show that Mimic is effective in detecting forward and backward compatibility issues, and verify runtime behavior of apps. Our evaluation also shows that Mimic significantly reduces the development burden for developers.

Trusted Applications (TAs) written for Trusted Execution Environments (TEEs) using ARM TrustZone are currently written in C; there is limited support for higher-level languages. This leads to common manual memory management problems like buffer overflow and use-after-free. Higher-level languages, which have managed runtimes, allow for automated memory management, the benefits of which are widely accepted. To allow for automated memory management of TAs, we need to have a runtime that handles allocation and garbage collection (GC). However, having the entire allocator and GC in the secure world would increase the Trusted Computing Base (TCB) of the secure world. We propose TrustGC, a mechanism to partition garbage collection and allocation between the secure world and the normal world. TrustGC allows for automated memory management of TAs by leveraging the help of a GC partly running in the normal world.

Summary Functional programming languages play an important role in the development of correct software systems. As embedded devices become pervasive and perform critical tasks in our lives, their reliability becomes paramount. This presents a natural opportunity to explore the application of functional programming languages to systems that demand highly predictable behavior. In this paper, we explore existing functional programming language compilers and their applicability to real‐time embedded systems. We do this by defining important characteristics needed by a real‐time programming language and survey how well existing languages meet these characteristics. We conduct empirical analysis of language runtimes in order to assess the impact of dynamic memory management on predictability and performance. Lastly, we review different programming models for expressing real‐time considerations in applications.

Rapid advancements in computing, communication, sensing, and actuation have seen the growth of Internet of Things (IoT) devices in our daily life. One of the fundamental constraints of a typical IoT device is energy as IoT devices rely on a battery. Therefore, it is crucial for their operating system (OS) to be able to accurately account for system-wide energy usage. Specifically, the OS should be able to attribute such accounted energy to the running applications accurately. Traditional OSs have limited capability when it comes to tracking components such as sensors, actuators and network interfaces, as they are often used in an asynchronous fashion. This would make it difficult to conduct energy accounting accurately. This paper proposes a new mechanism to accurately account for the asynchronous energy usage of resources in mobile systems and IoT devices. Our insight is that by accurately relating the application requests with kernel requests to device and corresponding device responses, we can accurately attribute time of use to the requesting process. However, resources such as WiFi reception violate this assumption. In such cases, we can measure usage by the number of bytes in each individual transaction. Using such a hybrid approach, we can account for energy usage with 94% accuracy and perform much better than using each of these models individually.

Gesto is a system that enables task automation for Android apps using gestures and voice commands. Using Gesto, a user can record a UI action sequence for an app, choose a gesture or a voice command to activate the UI action sequence, and later trigger the UI action sequence by the corresponding gesture/voice command. Gesto enables this for existing Android apps without requiring their source code or any help from their developers. In order to make such capability possible, Gesto combines bytecode instrumentation and UI action record-and-replay. To show the applicability of Gesto, we develop four use cases using real apps downloaded from Google Play-Bing, Yelp, AVG Cleaner, and Spotify. For each of these apps, we map a gesture or a voice command to a sequence of UI actions. According to our measurement, Gesto incurs modest overhead for these apps in terms of memory usage, energy usage, and code size increase. We evaluate our instrumentation capability and overhead using 1,000 popular apps downloaded from Google Play. Our result shows that Gesto is able to instrument 94.9% of the apps without any significant overhead. In addition, since our prototype currently supports 6 main UI elements of Android, we evaluate our coverage and measure what percentage of UI element uses we can cover. Our result shows that our 6 UI elements can cover 96.4% of all statically-declared UI element uses in the 1,000 Google Play apps.

Time predictability is difficult to achieve in the complex, layered execution environments that are common in modern embedded devices such as smartphones. We explore adopting the Android programming model for a range of embedded applications that extends beyond mobile devices, under the constraint that changes to widely used libraries should be minimized. The challenges we explore include the interplay between real-time activities and the rest of the system, how to express the timeliness requirements of components, and how well those requirements can be met on stock embedded platforms. We detail the design and implementation of our modifications to the Android framework along with a real-time VM and OS, and we provide experimental data validating feasibility over five applications.

This paper proposes a new technique to detect mobile malware based on information flow analysis. Our approach examines the structure of information flows to identify patterns of behavior present in them and which flows are related, those that share partial computation paths. We call such flows Complex-Flows, as their structure, patterns, and relations accurately capture the complex behavior exhibited by both recent malware and benign applications. N-gram analysis is used to identify unique and common behavioral patterns present in Complex-Flows. The N-gram analysis is performed on sequences of API calls that occur along Complex-Flows' control flow paths. We show the precision of our technique by applying it to four different data sets totaling 8,598 apps. These data sets consist of both recent and older generation benign and malicious apps to demonstrate the effectiveness of our approach across different generations of apps.

A key requirement for many distributed systems is to be resilient toward partial failures, allowing a system to progress despite the failure of some components. This makes programming of such systems daunting, particularly in regards to avoiding inconsistencies due to failures and asynchrony. This work introduces a formal model for crash failure handling in asynchronous distributed systems featuring a lightweight coordinator, modeled in the image of widely used systems such as ZooKeeper and Chubby. We develop a typing discipline based on multiparty session types for this model that supports the specification and static verification of multiparty protocols with explicit failure handling. We show that our type system ensures subject reduction and progress in the presence of failures. In other words, in a well-typed system even if some participants crash during execution, the system is guaranteed to progress in a consistent manner with the remaining participants.

This work in progress introduces cross-course collaborative, project-based learning, or C3PBL. C3PBL builds on established collaborative project-based learning ideas that have been shown to improve retention at various institutions, by introducing collaboration that spans multiple courses in the same term. We discuss how such a collaboration between students in different courses can change the undergraduate educational experience to improve retention, community, and self-confidence. For our work we are focusing on a curriculum based approach, leveraging collaborative project-based learning experiences to affect the mindset and culture of our department. We present lessons learned from an initial pilot of C3PBL deployed over two semesters. The pilot looks at the pairing of introductory level courses with an upper level software engineering class. The collaboration is centered on the idea of experienced students in the upper level software engineering course working with novice students from the introductory courses. The logistics explored has lead to more meaningful interaction and assessment in the second semester offering of C3PBL.

We present the algorithm visualization capabilities of the METAL project. Using METAL's graph data which represents highway systems, a selection of interactive algorithm visualizations are performed. Progress of the algorithm is shown by changing the colors of the graph's vertices and/or edges overlaid on Google Maps and in color-coded tabular form, including contents of important data structures. Advantages include the real-world data set and the variety of data sizes available, enhancing student engagement. While many visualizations and visualization tools exist for graph and related algorithms, most focus on small, synthetic graphs. We describe our algorithm visualization capabilities, which include implementations of sequential search, graph traversals, Dijkstra's algorithm, and convex hulls. These can be executed on graphs ranging in size from a few vertices and edges to hundreds. We also present results of a survey of students who have used METAL's algorithm visualizations.

This paper proposes a new technique to detect mobile malware based on information flow analysis. Our approach examines the structure of information flows to identify patterns of behavior present in them and which flows are related, those that share partial computation paths. We call such flows Complex-Flows, as their structure, patterns, and relations accurately capture the complex behavior exhibited by both recent malware and benign applications. N-gram analysis is used to identify unique and common behavioral patterns present in Complex-Flows. The N-gram analysis is performed on sequences of API calls that occur along Complex-Flows' control flow paths. We show the precision of our technique by applying it to different data sets totaling 7,798 apps. These data sets consist of both recent and older generation benign and malicious apps to demonstrate the effectiveness of our approach across different generations of apps.

This paper proposes a new technique that enables open innovation in mobile platforms. Our technique allows third-party developers to modify, instrument, or extend platform API calls and deploy their modifications seamlessly. The uniqueness of our technique is that it enables modifications completely at the app layer without requiring any platform-level changes. This allows practical openness---third parties can easily distribute their modifications for a platform without the need to update the entire platform. To demonstrate the benefits of our technique, we have developed a prototype on Android called Reptor and used it to instrument real-world apps with novel functionality. Our evaluation in realistic scenarios shows that Reptor has little overhead in performance and energy, and only modest overhead in memory usage that ranges from 0.6% to 10% for the observed worst cases.

We demonstrate AutoClicker, a fully automated UI testing system for large-scale Android apps using multiple devices. It provides a way to quickly and easily verify that a large number of Android apps behave correctly at runtime in a repeatable manner.

We demonstrate Reptor, a bytecode instrumentation tool enabling API virtualization on Android. It provides a general way to alter functionality of platform APIs on Android. With Reptor, third-party developers can modify the behavior of platform APIs according to their needs. All modifications are completely at the app layer without modifying the underlying platform. This allows practical openness---third-party developers can easily distribute their modifications for a platform without the need to update the entire platform.

We demonstrate Gesto, a dynamic gesture mapping tool. It provides users to map any gesture to a certain UI event that the users need. Also, the mapping can be easily changed by users.

This paper proposes a new technique for detecting mobile malware based on information flow analysis. Our approach focuses on the structure of information flows we gather in our analysis, and the patterns of behavior present in information flows. Our analysis not only gathers simple flows that have a single source and a single sink, but also Multi-Flows that either start from a single source and flow to multiple sinks, or start from multiple sources and flow to a single sink. This analysis captures more complex behavior that both recent malware and recent benign applications exhibit. We leverage N-gram analysis to understand both unique and common behavioral patterns present in Multi-Flows. Our tool leverages N-gram analysis over sequences of API calls that occur along control flow paths in Multi-Flows to precisely analyze Multi-Flows with respect to app behavior.

Since the introduction of the smartphone, mobile computing has become pervasive in our society. Meanwhile, Mobile devices have evolved far beyond the stereotypical personal devices and been employed in various traditional real-time embedded domains. Of the currently available mobile systems, Android has seen the most widespread deployment outside of the consumer electronics market. Its open source nature has prompted its ubiquitous adoption in sensing, medical, robotics, and autopilot applications. However, it is not surprising that Android does not provide any real-time guarantee since it is designed as a mobile system and optimised for mobility, user experience, and energy efficiency. Although there has been much interest in adopting Android in real-time contexts, surprisingly little work has been done to examine the suitability of Android for real-time systems. Existing work only provides solutions to traditional problems, including real-time garbage collection at the virtual machine layer, real-time OS scheduling and resource management. While it is critical to address these issues, it is by no means sufficient. After all, Android is a vast system that is more than a Java virtual machine and a kernel.

Time predictability is difficult to achieve in the complex, layered execution environments that are common in modern embedded devices. We consider the possibility of adopting the Android programming model for a range of embedded applications that extends beyond mobile devices, under the constraint that changes to widely used libraries should be minimized. The challenges we explore include: the interplay between real-time activities and the rest of the system, how to express the timeliness requirements of components, and how well those requirements can be met on stock embedded platforms. We report on the design and implementation of an Android virtual machine with soft-real-time support, and provides experimental data validating feasibility over three case studies.

One essential functionality of a modern operating system is to accurately account for the resource usage of the underlying hardware. This is especially important for computing systems that operate on battery power, since energy management requires accurately attributing resource uses to processes. However, components such as sensors, actuators and specialized network interfaces are often used in an asynchronous fashion, and makes it difficult to conduct accurate resource accounting. For example, a process that makes a request to a sensor may not be running on the processor for the full duration of the resource usage; and current mechanisms of resource accounting fail to provide accurate accounting for such asynchronous uses. This paper proposes a new mechanism to accurately account for the asynchronous usage of resources in mobile systems. Our insight is that by accurately relating the user requests with kernel requests to device and corresponding device responses, we can accurately attribute resource use to the requesting process. Our prototype implemented in Linux demonstrates that we can account for the usage of asynchronous resources such as GPS and WiFi accurately.

This paper presents our work on the inception of RTDroid, a variant of Android that provides predictability to Android applications. Although there has been much interest in adopting Android in real-time contexts, surprisingly little work has been done to examine the suitability of the Android franework layer for real-time systems. Existing work only provides solutions to traditional problems, including adding support for real-time garbage collection at the virtual machine layer as well as kernel-level real-time scheduling and resource management. While it is critical to address these issues, it is by no means sufficient. After all, Android is a vast system that is more than a Java virtual machine and a kernel. Thus, this paper goes beyond existing work and examines the internals of Android, the Android programming model, libraries, and core systems services. We discuss the implications and challenges of adapting Android constructs and core system services for real-time and present a solution for each. Our system is unique in that it redesigns Androids internal components, replaces Androids Dalvik VM with a real-time VM, and leverages off-the-shelf real-time OSes. We demonstrate the feasibility and predictability of our solution on three different platforms. The evaluation results show that our design can successfully provide predictability to Android applications even under heavy loads.

The desire to understand mobile applications has resulted in researchers adapting classical static analysis techniques to the mobile domain. Examination of data and control flows in Android apps is now a common practice to classify them. Important to these analyses is a fine-grained examination and understanding of strings, since in Android they are heavily used in intents, URLs, reflection, and content providers. Rigorous analysis of string creation, usage, and value characteristics offers additional information to increase precision of app classification. This paper shows that inter-procedural static analysis that specifically targets string construction and usage can be used to reveal valuable insights for classifying Android apps. To this end, we first present case studies to illustrate typical uses of strings in Android apps. We then present the results of our analysis on real-world malicious and benign apps. Our analysis examines how strings are created and used for URL objects, Java reflection, and Android intents, and infers the actual string values used as much as possible. Our results demonstrate that string disambiguation based on creation, usage, and value indeed provides additional information that may be used to improve precision of classifying application behaviors.

This paper proposes Flow Permissions, an extension to the Android permission mechanism. Unlike the existing permission mechanism, our permission mechanism contains semantic information based on information flows. Flow Permissions allow users to examine and grant per-app information flows within an application e.g., a permission for reading the phone number and sending it over the network) as well as cross-app information flows across multiple applications e.g., a permission for reading the phone number and sending it to another application already installed on the user's phone). Our goal with Flow Permissions is to provide visibility into the holistic behavior of the applications installed on a user's phone. In order to support Flow Permissions on Android, we have developed a static analysis engine that detects flows within an Android application. We have also modified Android's existing permission mechanism and installation procedure to support Flow Permissions. We evaluate our prototype with 2,992 popular applications and 1,047 malicious applications and show that our design is practical and effective in deriving Flow Permissions. We validate our cross-app flow generation and installation procedure on a Galaxy Nexus smartphone.

Today's mobile applications operate in a diverse set of environments, where it is difficult for a developer to know beforehand what conditions his or her application will be put under. For example, once deployed on an online application store, an application can be downloaded on different types of hardware, ranging from budget smartphones to high-end tablets. In addition, network conditions can vary widely from Wi-Fi to 3G to 4G. Mobile applications also need to co-exist with other applications that compete for resources at different times.

This paper presents RTDroid, a variant of Android that provides predictability to Android applications. Although there has been much interest in adopting Android in real-time contexts, surprisingly little work has been done to examine the suitability of Android for real-time systems. Existing work only provides solutions to traditional problems, including real-time garbage collection at the virtual machine layer and kernel-level real-time scheduling and resource management. While it is critical to address these issues, it is by no means sufficient. After all, Android is a vast system that is more than a Java virtual machine and a kernel.

SUMMARY Hard real‐time systems have stringent timing and resource requirements. As such, debugging and tracing such systems often requires low‐level hardware support, and online debugging is usually precluded entirely. In other areas, however, visual debugging has greatly improved program understanding and late cycle development times for nonreal‐time applications. In this paper, we introduce a visual test and debug framework for hard real‐time Java applications built around theJIVEplatform and realized in the Fiji virtual machine. Our framework, calledJI.FI [" dZIfi], provides high‐level debugging support over low‐level execution traces.JI.FIprovides both powerful visualizations and real‐time centric temporal query support. To ensure preservation of the real‐time characteristics of the application being tested and debugged,JI.FIleverages a real‐time event log infrastructure that logs only relevant application and virtual machine level events, such as synchronization and modifications to priorities or thread state. Our performance results indicate that our logging infrastructure is suitable for hard real‐time systems, as the performance impact is bothuniformandquantifiable. Copyright © 2013 John Wiley & Sons, Ltd.

Abstract MultiMLton is an extension of the MLton compiler and runtime system that targets scalable, multicore architectures. It provides specific support for ACML, a derivative of Concurrent ML that allows for the construction of composable asynchronous events. To effectively manage asynchrony, we require the runtime to efficiently handle potentially large numbers of lightweight, short-lived threads, many of which are created specifically to deal with the implicit concurrency introduced by asynchronous events. Scalability demands also dictate that the runtime minimize global coordination. MultiMLton therefore implements a split-heap memory manager that allows mutators and collectors running on different cores to operate mostly independently. More significantly, MultiMLton exploits the premise that there is a surfeit of available concurrency in ACML programs to realize a new collector design that completely eliminates the need for read barriers, a source of significant overhead in other managed runtimes. These two symbiotic features - a thread design specifically tailored to support asynchronous communication, and a memory manager that exploits lightweight concurrency to greatly reduce barrier overheads - are MultiMLton 's key novelties. In this article, we describe the rationale, design, and implementation of these features, and provide experimental results over a range of parallel benchmarks and different multicore architectures including an 864 core Azul Vega 3, and a 48 core non-coherent Intel SCC (Single-Cloud Computer), that justify our design decisions.

This paper proposes Flow Permissions, an extension to the Android permission mechanism. Unlike the existing permission mechanism our permission mechanism contains semantic information based on information flows. Flow Permissions allow users to examine and grant explicit information flows within an application (e.g., a permission for reading the phone number and sending it over the network) as well as implicit information flows across multiple applications (e.g., a permission for reading the phone number and sending it to another application already installed on the user's phone). Our goal with Flow Permissions is to provide visibility into the holistic behavior of the applications installed on a user's phone. Our evaluation compares our approach to dynamic flow tracking techniques; our results with 600 popular applications and 1,200 malicious applications show that our approach is practical and effective in deriving Flow Permissions statically.

Managed languages typically use read barriers to interpret forwarding pointers introduced to keep track of copied objects. For example, in a multicore environment with thread-local heaps and a global, shared heap, an object initially allocated on a local heap may be copied to a shared heap if it becomes the source of a store operation whose target location resides on the shared heap. As part of the copy operation, a forwarding pointer may be established in the original object to point to the copied object. This level of indirection avoids the need to update all of the references to the object that has been copied.

Although asynchronous communication is an important feature of many concurrent systems, building composable abstractions that leverage asynchrony is challenging. This is because an asynchronous operation necessarily involves two distinct threads of control -- the thread that initiates the operation, and the thread that discharges it. Existing attempts to marry composability with asynchrony either entail sacrificing performance (by limiting the degree of asynchrony permitted), or modularity (by forcing natural abstraction boundaries to be broken).

While managed languages such as C# and Java have become quite popular in enterprise computing, they are still considered unsuitable for hard real-time systems. In particular, the presence of garbage collection has been a sore point for their acceptance for low-level system programming tasks. Real-time extensions to these languages have the dubious distinction of, at the same time, eschewing the benefits of high-level programming and failing to offer competitive performance. The goal of our research is to explore the limitations of high-level managed languages for real-time systems programming. To this end we target a real-world embedded platform, the LEON3 architecture running the RTEMS real-time operating system, and demonstrate the feasibility of writing garbage collected code in critical parts of embedded systems. We show that Java with a concurrent, real-time garbage collector, can have throughput close to that of C programs and comes within 10% in the worst observed case on realistic benchmark. We provide a detailed breakdown of the costs of Java features and their execution times and compare to real-time and throughput-optimized commercial Java virtual machines.

Managed languages such as Java and C# are being considered for use in hard real-time systems. A hurdle to their widespread adoption is the lack of garbage collection algorithms that offer predictable space-and-time performance in the face of fragmentation. We introduce SCHISM/CMR, a new concurrent and real-time garbage collector that is fragmentation tolerant and guarantees time-and-space worst-case bounds while providing good throughput. SCHISM/CMR combines mark-region collection of fragmented objects and arrays (arraylets) with separate replication-copying collection of immutable arraylet spines, so as to cope with external fragmentation when running in small heaps. We present an implementation of SCHISM/CMR in the Fiji VM, a high-performance Java virtual machine for mission-critical systems, along with a thorough experimental evaluation on a wide variety of architectures, including server-class and embedded systems. The results show that SCHISM/CMR tolerates fragmentation better than previous schemes, with a much more acceptable throughput penalty.

Abstract Transient faults that arise in large-scale software systems can often be repaired by reexecuting the code in which they occur. Ascribing a meaningful semantics for safe reexecution in multithreaded code is not obvious, however. For a thread to reexecute correctly a region of code, it must ensure that all other threads that have witnessed its unwanted effects within that region are also reverted to a meaningful earlier state. If not done properly, data inconsistencies and other undesirable behavior might result. However, automatically determining what constitutes a consistent global checkpoint is not straightforward because thread interactions are a dynamic property of the program. In this paper, we present a safe and efficient checkpointing mechanism for Concurrent ML (CML) that can be used to recover from transient faults. We introduce a new linguistic abstraction, called stabilizers , that permits the specification of per-thread monitors and the restoration of globally consistent checkpoints. Safe global states are computed through lightweight monitoring of communication events among threads (e.g., message-passing operations or updates to shared variables). We present a formal characterization of its design, and provide a detailed description of its implementation within MLton, a whole-program optimizing compiler for Standard ML. Our experimental results on microbenchmarks as well as several realistic, multithreaded, server-style CML applications, including a web server and a windowing toolkit, show that the overheads to use stabilizers are small, and lead us to conclude that they are a viable mechanism for defining safe checkpoints in concurrent functional programs.

Memoization is a well-known optimization technique used to eliminate redundant calls for pure functions. If a call to a function f with argument v yields result r, a subsequent call to f with v can be immediately reduced to r without the need to re-evaluate f's body. Understanding memoization in the presence of concurrency and communication is significantly more challenging. For example, if f communicates with other threads, it is not sufficient to simply record its input/output behavior; we must also track inter-thread dependencies induced by these communication actions. Subsequent calls to f can be elided only if we can identify an interleaving of actions from these call-sites that lead to states in which these dependencies are satisfied. Similar issues arise if f spawns additional threads. In this paper, we consider the memoization problem for a higher-order concurrent language whose threads may communicate through synchronous message-based communication. To avoid the need to perform unbounded state space search that may be necessary to determine if all communication dependencies manifest in an earlier call can be satisfied in a later one, we introduce a weaker notion of memoization called partial memoization that gives implementations the freedom to avoid performing some part, if not all, of a previously memoized call. To validate the effectiveness of our ideas, we consider the benefits of memoization for reducing the overhead of recomputation for streaming, server-based, and transactional applications executed on a multi-core machine. We show that on a variety of workloads, memoization can lead to substantial performance improvements without incurring high memory costs.

Transient faults that arise in large-scale software systems can often be repaired by re-executing the code in which they occur. Ascribing a meaningful semantics for safe re-execution in multi-threaded code is not obvious, however. For a thread to correctly rexecute a region of code, it must ensure that all other threads which have witnessed its unwanted effects within that region are also reverted to a meaningful earlier state. If not done properly, data inconsistencies and other undesirable behavior may result. however, automatically determining what constitutes a consistent global checkpoint is not straightforward since thread interactions are a dynamic property of the program.In this paper, we present a safe and efficient checkpointing mechanism for Concurrent ML (CML) that can be used to recover from transient faults. We introduce a new linguistic abstraction called stabilizers that permits the specification of per-thread monitors and the restoration of globally consistent checkpoints. Safe global states are computed through lightweight monitoring of communication events among threads (e.g. message-passing operations or updates to shared variables).Our experimental results on several realistic, multithreaded, server-style CML applications, including a web server and a windowing toolkit, show that the overheads to use stabilizers are small, and lead us to conclude that they are a viable mechanism for defining safe checkpoints in concurrent functional programs.