4.3.1 Transparency

We define transparency as the ability for a system to tell its users why it is doing what it is doing, and the need for this property is uprising in recent years. The primary motivator is the ubiquitous popularity of personal devices such as smartphones and tablets. These personal devices enable users to browse the Web, to send e‐mails, to take pictures, etc. anywhere they go with high‐bandwidth connectivity to the Internet. Due to this convenience, the penetration of personal devices has shown a startling growth; it has been reported that the global shipments of smartphones have already surpassed the shipments of PCs in 2011 [1]. Facebook, the most popular social networking service, reports that 90% of their daily active users access it via mobile [2], and it is the main target of growth in 2012 [3].

However, this popularity of personal devices not only provided convenience but also brought many why questions from users. These why questions are not just traditional questions that researchers have asked before such as “why is this device so slow?” or “why does this device cannot connect to the Internet?” but rather new questions more pertinent to personal devices such as “is this application sending a personal phone number to some Internet server?” “is it tracking locations?” or “why is this device not lasting even a day?” Many survey results recognize these questions, and the news media has numerous suggestions and advice to deal with these questions [4–7].

The underlying issue of answering these why questions is transparency. If a system is transparent, that is, if a system provides detailed information that reveals its inner working, then we can start answering the why questions. For example, if an application or a platform reveals how the application behaves in regard to all the data read from contacts, we should be able to answer “is this application sending a personal phone number to some Internet server?” Traditionally, this issue of transparency has been more relevant to researchers and developers as they need to understand how a system behaves for various purposes such as debugging and performance improvement. Accordingly, a large number of tools have been developed to assist researchers and developers, for example, Kprobes [8] and SystemTap [9] among many others. But now, it is relevant to end users as well, and we need to develop tools and techniques to provide transparency not only for researchers and developers but also for users.

Although such tools and techniques could be developed in any layer of a system, it would be particularly useful if they were provided by the operating system layer, either as a platform tool or as a system‐level service. This is because those tools and techniques could benefit the entire set of applications running on top of an operating system if they were implemented within the operating system. In the case of a popular operating system, it would also seamlessly benefit a large number of users at the same time.

However, transparency—as we define it—is a broad issue that has many aspects, for example, performance, energy efficiency, privacy, etc. Thus, it is difficult to tackle all transparency issues at once. Thus, in our own research we are taking some initial steps to develop tools and techniques that pertains to one aspect of transparency, which we call information flow transparency.

BlueSeal [10, 11] is our first effort toward providing information flow transparency. This transparency reveals answers to questions on how an application uses the data of its user, for example, “is this application sending a personal phone number to some Internet server?” The reason why we call it information flow transparency is because this type of question can be answered by a technique called information flow tracking [12–18], which analyzes how information gets propagated in a system from an information source to an information sink. For example, by tracking how the information from a file that contains personal phone numbers gets propagated within an application, we can check if a phone number gets sent over the network by the application. In this example, the information source is the phone number file, and the information sink is the network. BlueSeal analyzes how various types of information get propagated between many different sources (such as storage, GPS, contacts, camera, etc.) and sinks (such as network, log, storage, inter‐process communication channels, etc.) and reveals them to end users.

Revealing an information flow is a first step toward enforcing a flow or preventing a flow from happening. For example, an operating system might want to analyze an application first to make sure that at runtime there is no other information flow occurring. Also, an operating system might want to prevent an application from executing at all if there is a potentially malicious information flow.

However, revealing an information flow is also useful in and of itself, especially to users. If presented at installation time, for example, a user could decide whether the user wants to install an application or not. This is particularly useful when there are many alternatives for an application. For example, there are many file browser applications for a smartphone, and a user might want to choose a file browser application with the least number of information flows.

In light of this, the uniqueness of our tool, BlueSeal, is twofold. First, BlueSeal statically analyzes an application and displays all potential information flows to end users at installation time. This means that we analyze the binary of an application to detect information flows that exist within the application; this is opposed to dynamic information flow tracking, where the tracking happens at runtime. The reason for our static analysis is to give a user a chance to examine the behavior of an application before installing it so that the user can make a more informed decision on which applications to install. We do this in the form of permissions; we display at installation time what potential information flows exist in an application for various sources and sinks, and a user needs to approve that the user is still willing to install the application. Two most popular mobile operating systems, iOS and Android, both have such a permission mechanism, and we have chosen Android¹ as the implementation platform. Figure 4.1 shows a screenshot of how BlueSeal displays information flows.

The second uniqueness of BlueSeal is that it addresses the challenges of adapting existing static information flow analysis techniques to a specific platform. This is due to the fact that there are many practical issues to consider for a specific platform, which general static information flow analysis techniques do not address. This is why we mention in Section 4.2 that providing a new property in an existing operating system does not simply mean that one uses it as an implementation platform. Often times, there are platform‐specific issues to address, and it leads to interesting research problems.

In the case of BlueSeal, there are two categories of practical issues we needed to consider for Android when adapting existing static analysis techniques. The first category is the issues caused by the programming model of Android. The fundamental reason is that Android’s programming model is highly event driven; an application implements numerous entry points that react to outside events. In other words, an Android application does not have any single entry point where all the logic starts from; an Android application is a collection of handlers that processes events, for example, a button click. This type of programming models is popular for GUI‐based frameworks, and Android is no exception. The problem with this programming model for static information flow analysis is that traditional techniques assume that a program has a single call graph starting from main(). They do not work if a program is a set of handlers with no single entry point.

Not only that, Android introduced many new constructs such as new thread types, message handlers, and IPC mechanisms. The issue with these new constructs is that their execution is implicit, that is, they are executed not by direct method calls within application code but by the underlying Android platform with some predefined rules. This is the second category of issues we needed to deal with in BlueSeal.

To illustrate this point, we use AsyncTask, a popular construct for threading on Android, as an example. AsyncTask is a new threading class introduced in Android. It provides a simple way to write a thread that communicates with the UI thread in an asynchronous fashion. An AsyncTask can implement five methods—onPreExecute(), doInBackground(), onProgressUpdate(), onPostExecute(), and onCancelled(). The interesting aspect about this construct is that there is a predefined order of execution and that there is no explicit method calls that can be found in application code for any of the five methods. Figures 4.2 and 4.3 illustrate this point. Figure 4.2 shows a code snippet written in Java, and Figure 4.3 shows the corresponding order of execution.

As shown in Figure 4.2, a developer can implement a new thread by extending AsyncTask and providing the implementation for the five methods previously mentioned. In Figure 4.2, the developer‐implemented class is Task, and it is started in onCreate() by calling Task.execute(). Now, as the execution flow shows, the call to Task.execute() triggers the execution of Task.onPreExecute(), and there is no explicit call to that method in the application code—the execution is triggered by the underlying Android platform. Similarly, other methods (e.g., doInBackground()) are called at later times but without any explicit call. AsyncTask is just one example; many other constructs in Android have similar characteristics. The problem of these constructs for static information flow analysis then is how to handle indirect call relationships in various pieces of code.

In order to handle the two categories of issues described so far, BlueSeal implements a mechanism to understand many entry points that exist in an Android application as well as implicit calls introduced by new constructs of Android. In a nutshell, BlueSeal builds a call graph, where all implicit calls are converted to explicit calls, and augments traditional static information flow analysis techniques to handle multiple entry points. Using BlueSeal, we have analyzed 1800 applications (600 top‐rated free applications and 1200 malicious applications identified by MalGenomeproject [19]) and found that all but 79 applications take less than 2 minutes to analyze. This shows that if the analysis is done off‐line using a server (e.g., an application store server), it is practical to use BlueSeal to provide information flow transparency at installation time.

Our previously published paper [11] reports the full set of results, and here we summarize some of our findings. First, we have observed that malicious applications are heavily interested in unique phone identifiers such as the device ID. Moreover, when normal applications use unique phone identifiers, they just use them internally without sending it to a server or storing it somewhere. In contrast, malicious applications almost always send the identifiers out of the applications themselves either to a server or to a device storage. Second, we have observed that normal applications access the phones’ location data more frequently than malicious applications, that is, there is less interest among malicious applications about users’ locations. Third, both normal and malicious applications read system content providers often. The most commonly accessed content provider in both normal and malicious applications is the contacts. Thus, reading contacts is probably not a reliable indicator of a malicious activity.

At the time of our publication, the most closely related work to ours was CHEX [20]. It provides a tool for detecting highjack‐enabling flows within an Android application. It uses a brute‐force permutation approach to tackle the analysis of Android’s constructs such as async tasks and handlers, making it susceptible to incorrect disambiguation. Thus, our call graph restructuring technique can refine CHEX’s approach since we identify implicit calls in Android’s constructs whenever possible. More recently, FlowDroid [21] has proposed more sophisticated techniques to analyze Android applications. It performs context‐sensitive analysis that specifically handles Android’s constructs.

4.3.2 Predictable Performance

The second property that deserves more attention is what we call predictable performance, which we define as the ability for an operating system to provide consistent, predictable performance to important applications. This is coming from the traditional real‐time systems domain, where an application consists of multiple tasks with different priorities. An aircraft control system is a well‐known case of a real‐time system; there are many tasks an aircraft control system needs to carry out, for example, radar control, navigation, flight control, etc., and these tasks have different priorities in terms of their relative importance. In addition, these tasks should perform in a predictable fashion. This means that for each task, there has to be a guarantee about exactly when it starts and exactly when it finishes. For example, if the radar of an aircraft senses a foreign object, the sensed data should be delivered to its data processing unit in a predictable way with a reasonable bound on latency. If there is no such guarantee, then the aircraft will not be able to react to sensed objects in a timely manner. This guarantee should be provided even when there are multiple tasks that compete for shared resources such as CPU, memory, and I/O.

This property of predictable performance has become more important recently, as there are many more types of newer devices that operate in real‐time contexts. For example, many new medical IoT devices are appearing, and they perform critical tasks such as patient monitoring. These critical medical tasks typically require predictable performance; otherwise, there will be no guarantee about whether or not the critical tasks can be performed in a timely manner for a patient. Similarly, small UAVs are becoming popular, and they also require predictable performance; otherwise, they will not be able to fly reliably. Thus, the property of predictable performance is becoming more important now.

In our own research, we are investigating how to provide the property of predictable performance in Android. The system we are developing is a variation of Android called RTDroid [22–24]. Our goal for RTDroid is to add real‐time support to Android as a whole system so that one can run real‐time applications and non‐real‐time applications on a single system. Having such a system enables scenarios previously not possible. For example, a hospital inpatient can potentially use a tablet to play games, while the table is also being used as a central hub for controlling all medical devices that the patient needs. Or, a smartphone can potentially become an onboard satellite controller as the United Kingdom envisions [25]. Before RTDroid, there were a few discussions on how to add real‐time support to Android [26–28], but RTDroid is the first system that explores the question of how to add real‐time support to Android as a whole system, to the best of our knowledge.

With RTDroid, we have explored several research questions related to adding real‐time support to Android. The questions are (i) whether or not the current Android provides real‐time guarantees, (ii) if not, what kinds of techniques we need, (iii) what changes we need to make in Android to implement the techniques identified by the previous question, and (iv) how effective the implemented techniques are. It turns out that Android does not provide adequate real‐time guarantees, and while we can reuse existing techniques to add real‐time support to Android, namely, priority awareness, implementing these techniques in Android as a whole system requires careful examination and strategies. This presents a significant challenge due to the complexities of Android, especially when considering the entire system. In the succeeding text, we elaborate these findings further, starting with the answer for the first question.

To answer the first question, we began by analyzing Android for its real‐time capability. To explain our findings, Figure 4.4 shows a simplified view of Android’s internal components. As shown, there are three main layers that support Android applications—the Android kernel, the Android runtime (ART), and the application framework. The Android kernel is basically a Linux kernel with some Android‐specific customizations. The ART contains Android’s Java virtual machine (previously Dalvik, now ART) as well as system libraries (Java and C libraries, similar to the ones that a typical Linux distribution has). Android applications are mainly written in Java, so this runtime layer is directly responsible for running an application. The last layer—the application framework—has system services and provides APIs to access them as well as convenient constructs.

In order to analyze Android’s real‐time capabilities as a whole system, we need to examine each layer and see if every layer is capable of supporting real‐time applications. We start by examining the bottommost layer, which is the Android kernel. As mentioned earlier, the Android kernel is essentially a Linux kernel with some Android‐specific customizations; and it is well known that the Linux kernel does not have real‐time capabilities.² Instead, there is a patch that one can apply to transform a Linux kernel into a real‐time kernel. This patch is called RT‐Preempt.³ There also exist other real‐time kernels such as RTEMS [29]. Thus, we can conclude that the current Android kernel does not have any real‐time capability, although there are potential alternatives.

The layer above the kernel is the ART that contains Android’s Java virtual machine and system libraries. Similar to the Linux kernel case, it is well known that Android’s Java virtual machine does not have any real‐time capability. In fact, designing a real‐time Java virtual machine is a research area of its own, and there has been active research in the past few years [30–32]. In order to design a real‐time Java virtual machine, specific mechanisms need to be implemented, for example, a real‐time garbage collector, but Android’s virtual machine does not implement such mechanisms. Thus, we can also conclude that the current runtime of Android does not have any real‐time capability.

For our research, these bottom two layers—the Android kernel and the runtime—did not require much examination for us to see that they did not have any real‐time capability. It was and still is a known and well‐documented fact that a kernel layer as well as a Java runtime layer need additional support to make real‐time applications work correctly. However, the application framework layer required more thorough understanding and analysis, since it was not known in the literature if that layer provides any real‐time capability. After a closer look at the application framework layer, we concluded that the framework layer also needed much work to add real‐time capabilities. We first explain the application framework layer and discuss our findings.

As mentioned earlier, the application framework layer consists of two categories of components. The first category is system services, and the second category is constructs and APIs. It is depicted in Figure 4.4. System services are the operating system services of Android that applications can leverage. Some examples include a sensor service that manages sensor input delivery; an alarm service that provides timers (e.g., one‐time timers, periodic timers, etc.); a media service that manages on‐device cameras, microphones, and speakers; and a location service that manages GPS and location data delivery. The APIs in the second category allow easy access to these system services. The APIs also provide access to standard programming constructs and facilities such as data structures (e.g., HashMap) and OS facilities (e.g., Socket). In addition, there are extra programming constructs that Android provides to its application developers. We categorize them as “constructs.” Some examples include Looper, Handler, AsyncTask (which we showed earlier in Section 4.3.1), etc. Looper and Handler provide a convenient way for message passing between different components. AsyncTask, as explained earlier, provides a convenient way to create and use a thread.

By examining these constructs, APIs, and system services, we have found out that the application framework layer has limitations for real‐time applications, as it is not designed with real‐time support in mind. This is true for many constructs and system services such as Looper, Handler, the sensor service, the alarm service, etc. This is understandable, since Android was designed for smartphones initially that do not require any real‐time capability.

To illusrate one such design limitation, Figure 4.5 depicts the overall sensor architecture of Android. It shows two sensors, an accelerometer and a gyroscope, and how their data is passed to applications. It crosses the hardware‐kernel boundary as well as the kernel‐user boundary. As shown, there are separate data delivery paths for different sensors up to the kernel, and then the data is processed and passed through over one path with the sensor service and the sensor manager. The sensor service and the sensor manager basically pull all sensor data out of the kernel, queue them up, and deliver them in the FIFO order to different applications.

This single path design is a problem for real‐time applications if they need to prioritize the delivery of different types of sensor data. For example, suppose a scenario where a real‐time application needs accelerometer data for a high‐priority critical task, but it also needs gyroscope data for a low‐priority task. Since a gyroscope can produce data at a much higher rate than an accelerometer, if there is one path that delivers both types of data in the FIFO order as Android does, the gyroscope data will block and delay the delivery of accelerometer data. For real‐time applications, there has to be a mechanism to differentiate important tasks and data from less important tasks and data. The underlying system then needs to guarantee that less important ones do not interfere with more important ones.

Thus, our findings on the real‐time capabilities of Android is that in all layers, appropriate support is necessary to make Android real time, and RTDroid is our solution for that. Figure 4.6 shows a quick look at our overall architecture. At the bottommost layer, we replace the Android kernel with a real‐time kernel; we currently use Linux with RT‐Preempt and RTEMS as our kernel options. We then replace the ART with a real‐time Java runtime; we currently use FijiVM [32] as our option and add real‐time support for the system C library for Android called Bionic. These components provide essential real‐time mechanisms such as priority‐aware scheduling, real‐time interrupt handling, full preemption, real‐time garbage collection, etc. They are mostly off the shelf and require some engineering effort to use on Android.

While these components provide basic real‐time building blocks, they do not solve the problems in the application layer design. Thus, we redesign and implement the application framework layer, so that it supports real‐time applications. The key principle in our design is to make Android’s internal constructs, components, and message delivery mechanisms priority aware, that is, if there are more important tasks to run or messages to deliver, the whole system should be able to prioritize them over other tasks or message. Although this is a well‐known concept, implementing it in Android requires much careful examination of the whole system and its design, which is a significant challenge. So far, we have redesigned a few constructs and system services to demonstrate the feasibility of our approach. We have redesigned Looper, Handler, the alarm service, and the sensor service. As an example, Figure 4.7 shows our redesigned sensor architecture. For brevity, we have simplified the figure and do not show the full design.

As mentioned earlier, Android’s sensor architecture uses a single path to deliver all sensor events in the FIFO order. This poses a problem for real‐time applications, since they cannot prioritize the delivery of important sensor data over less important data. Thus, in our design, we create separate, prioritized paths for different sensors. In Figure 4.7, this is shown with the accelerometer service/manager and the gyroscope service/manager to illustrate how we support the two sensors. Our architecture has the advantage of being able to prioritize the data delivery from one sensor over another. This can be done by assigning different task priorities for different sensor managers (where task priorities are supported by the underlying runtime and the kernel). For example, if we assign a higher priority to the accelerometer manager than the gyroscope manager, the accelerometer manager will have a higher priority for its execution, resulting in the prioritized delivery of accelerometer data over gyroscope data.

Figure 4.8 shows the performance comparison between our sensor architecture and Android’s architecture. It shows the result from one set of experiments we conducted with Google Nexus S smartphone. The workload we ran consists of two parts. The first part is our main workload, and it is a real‐time fall detection application. It runs on a phone and implements a fall detection algorithm that alerts a sudden change of height of the phone. It can be used to detect a fall of a soldier, an elderly, etc. The second part is our background workload intended to create much background noise to disrupt our main workload. What we used for the figure is 100 memory‐intensive background threads, each of which allocates a 2.5 MB integer array. This creates much memory pressure and stresses the whole system. Since the fall detection application requires accelerometer sensor data, it tests our redesign of the sensor architecture.

Figuire 4.8 illustrates the observed latency of the sensor event delivery for the fall detection application. The x‐axis indicates all sensor events, and the y‐axis indicates the delivery latency for each sensor event. As shown, RTDroid provides the upper bound of around 30 ms; however, Android does not provide such tight latency bound, and latency varies greatly across different events. This means that the possibility of missing some of the fall events exists on Android. This result demonstrates that our redesign is effective in providing predictable performance for real‐time applications.

4.3.3 Openness

The last property that deserves more attention is openness, which we define as the ability for an operating system to easily incorporate and deploy innovation from third parties. Traditionally many areas in computer science have benefited from such openness. Perhaps the most recent example is software‐defined networking (SDN) (in which Feamster et al. [33] provide a good summary for), which essentially provides openness in networking—they open routers and switches so that third‐party developers can write software to control them. This openness enabled by SDN has sparked much interest in the networking community, and now there are many innovative solutions being proposed for different problems in networking. There are other popular examples we can find, such as NetFilter⁴ and FUSE.⁵ NetFilter is a Linux facility for network packet filtering, where a third‐party developer can write an extension for packet analysis and transformation. FUSE is also a Linux facility for user‐space file system extensions. It allows third‐party developers to implement a fully functional file system as a user‐space program. These kernel facilities have enabled the development of countless research prototypes.

We believe that such openness is necessary for the operating systems used in fog networking devices such as smartphones and IoT devices. This will enable unobstructed innovation, not only from the vendors of the operating systems but also from third parties. In the current state, even the most open platform—Android—is in fact mostly closed. It is open in the sense that its source code is open. If we want to examine the source, we can simply clone the source repositories and take a look at the source. If we want to contribute to the source, it is also possible; we can review the current list of bugs and submit patches. A patch has a chance to be incorporated in the main distribution. However, it is still closed in the sense that it is not easy to deploy any innovation in the Android operating system, unless one has access to the official Android update channels, which is controlled by Google and other vendors. For example, if a researcher develops an innovative technique for an OS subsystem such as networking or storage, there is no easy way to deploy it and test it with a large number of real users since it requires an operating system update.

Recognizing such a problem, we are taking initial steps in our research. One such effort is a system called BlueMountain [34], which aims to enable open innovation in mobile data management. Though the full development of BlueMountain is in progress, we discuss the system here briefly to give an idea on what kinds of openness might be possible in operating systems for fog networking devices.

The basic idea of BlueMountain is a technique called storage API virtualization. It allows a third‐party developer to write extensions for storage operations and inject it into existing mobile applications using binary instrumentation. An extension provides a new implementation for storage APIs such as open(), read(), and write() so that, when an application calls those APIs for storage, the extension can intercept the calls and modify the behavior of the calls. In addition, an extension is injected to an application using binary instrumentation. This provides the benefit of deployability; by injecting a storage extension to an application, there is no need to update an operating system—an extension can be distributed as part of an application.

Figure 4.9 illustrates this idea with an extension example. It shows that there is a storage API virtualization layer injected into an existing application, and this API virtualization layer can execute code from an extension; and this extension can modify the behavior of storage API calls, for example, seamlessly intercepting and sending all data written with write() API to a cloud storage service for automated backup. There can be many other possibilities for a mobile storage extension; for example, we could automatically enable proximity‐based peer‐to‐peer storage where a user takes a picture with friends and calls write() that transparently sends the picture to all friends’ devices.

There are several challenges to overcome in order to realize storage API virtualization, some of which are described in our workshop paper on BlueMountain [34]. We encourage interested readers to refer to the paper for further information.