A common feature in Android apps is saving, or exporting, user’s work (e.g., a drawing) as well as data (e.g., a spreadsheet) onto local storage, as a file. Due to the volatile nature of the OS and the mobile environment in general, the system can terminate apps without notice, which prevents the execution of file write operations; consequently, user data that was supposed to be saved/exported is instead lost. Testing apps for such potential losses raises several challenges: how to identify data originating from user input or resulting from user action (then check whether it is saved), and how to reproduce a potential error by terminating the app at the exact moment when unsaved changes are pending. We address these challenges via an approach that finds potential “lost writes”, i.e., user data supposed to be written to a file, but the file write does not take place due to system-initiated termination. Our approach consists of two phases: a static analysis that finds potential losses and a dynamic loss verification phase where we compare lossy and lossless system-level file write traces to confirm errors. We ran our analysis on 2,182 apps from Google Play and 38 apps from F-Droid. Our approach found 163 apps where termination caused losses, including losing user’s app-specific data, notes, photos, user’s work and settings. In contrast, two state-of-the-art tools aimed at finding volatility errors in Android apps failed to discover the issues we found.

Sixty-five percent of mobile apps require user accounts for offering full-fledged functionality. Account information includes private data, e.g., address, phone number, credit card. Our concern is “leftover” account data kept on the server after account deletion, which can be a significant privacy violation. Specifically, we analyzed 1,435 popular apps from Google Play (and 771 associated websites), of which 678 have their own sign-up process, to answer questions such as: Can accounts be deleted at all? Following account deletion, will user data remain on the app’s servers? If so, for how long? Do apps keep their promise to remove data? Answering these questions, and more generally, understanding and tackling the leftover account problem, is challenging. A fundamental obstacle is that leftover data is manipulated and retained in a private space, on the app’s backend servers; we devised a novel, reverse-engineering approach to infer leftover data from app–server communication. Another obstacle is the distributed nature of this data: program analysis as well as information retrieval are required on both the app and its website. We have developed an end-to-end solution (static analysis, dynamic analysis, natural language processing) to the leftover account problem. First, our toolchain checks whether an app, or its website, support account deletion; next, it checks whether the app/website have a data retention policy, and whether the account is left on servers after deletion, or after the specified retention period; finally, it automatically cleans up leftover accounts. We found that 64.45% of apps do not offer any means for users to delete accounts; 2.5% of apps still keep account data on app servers even after accounts are deleted by users. Only 5% of apps specify a retention period; some of these apps violate their own policy by still retaining data months after the period has ended. Experiments show that our approach is effective, with an F-measure $\gt 88$%, and efficient, with a typical analysis time of 279 seconds per app/website.

Current taint analyses track flow from sources to sinks, and report the results simply as source → sink pairs, or flows. This is imprecise and ineffective in many real-world scenarios; examples include taint sources that are mutually exclusive, or flows that combine sources (e.g., IMEI and MAC Address are concatenated, hashed, leaked vs. IMEI and MAC Address hashed separately and leaked separately). These shortcomings are particularly acute in the context of Android, where sensitive identifiers can be combined, processed, and then leaked, in complicated ways. To address these issues, we introduce a novel, algebraic-datatype taint analysis that generates rich yet concise taint signatures involving AND, XOR, hashing – akin to algebraic, product and sum, types. We implemented our approach as a static analysis for Android that derives app leak signatures – an algebraic representation of how, and where, hardware/software identifiers are manipulated before being exfiltrated to the network. We perform six empirical studies of algebraic-datatype taint tracking on 1,000 top apps from Google Play and their embedded libraries, including: discerning between “raw” and hashed flows which eliminates a source of imprecision in current analyses; finding apps and libraries that go against Google Play’s guidelines by (ab)using hardware identifiers; showing that third-party code, rather than app code, is the predominant source of leaks; exposing potential de-anonymization practices; and quantifying how apps have become more privacy-friendly over the past two years.

A deterministic clustering algorithm is designed to always produce the same clustering solution on a given input. Therefore, users of clustering implementations (toolkits) naturally assume that implementations of a deterministic clustering algorithm A have deterministic behavior, that is: (1) two different implementations I1and I2of A are interchangeable, producing the same clustering on a given input D, and (2) an implementation produces the same clustering solution when run repeatedly on D. We challenge these assumptions. Specifically, we analyze clustering behavior on 528 datasets, three deterministic algorithms (Affinity Propagation, DBSCAN, Hierarchical Agglomerative Clustering) and the deterministic portion of a fourth (K-means), as implemented in various toolkits; in total, we examined 13 algorithm-toolkit combinations. We found that different implementations of deterministic clustering algorithms make different choices, e.g., default parameter settings, noise insertion, input dataset characteristics. As a result, clustering solutions for a fixed algorithm-dataset combination can differ across runs (nondeterminism) and across toolkits (inconsistency). We expose several root causes of such behavior. We show that remedying these root causes improves determinism, increases consistency, and can even improve efficiency. Our approach and findings can benefit developers, testers, and users of clustering algorithms.

Mobile operating systems, especially Android, expose apps to a volatile runtime environment. The app state that reflects past user interaction and system environment updates (e.g., battery status changes) can be destroyed implicitly, in response to runtime configuration changes (e.g., screen rotations) or memory pressure. Developers are therefore responsible for identifying app state affected by volatility and preserving it across app lifecycles. When handled inappropriately, the app may lose state or end up in an inconsistent state after a runtime configuration change or when users return to the app. To free developers from this tedious and error-prone task, we propose a systematic solution, LiveDroid, which precisely identifies the necessary part of the app state that needs to be preserved across app lifecycles, and automatically saves and restores it. LiveDroid consists of: (i) a static analyzer that reasons about app source code and resource files to pinpoint the program variables and GUI properties that represent the necessary app state, and (ii) a runtime system that manages the state saving and recovering. We implemented LiveDroid as a plugin in Android Studio and a patching tool for APKs. Our evaluation shows that LiveDroid can be successfully applied to 966 Android apps. A focused study with 36 Android apps shows that LiveDroid identifies app state much more precisely than an existing solution that includes all mutable program variables but ignores GUI properties. As a result, on average, LiveDroid is able to reduce the costs of state saving and restoring by 16.6X (1.7X - 141.1X) and 9.5X (1.1X - 43.8X), respectively. Furthermore, compared with the manual state handling performed by developers, our analysis reveals a set of 46 issues due to incomplete state saving/restoring, all of which can be successfully eliminated by LiveDroid.

Dynamic program slicing is useful for a variety of tasks, from testing to debugging to security. Prior slicing approaches have targeted traditional desktop/server platforms, rather than mobile platforms such as Android. Slicing mobile, event-based systems is challenging due to their asynchronous callback construction and the IPC (interprocess communication)- heavy, sensor-driven, timing-sensitive nature of the platform. To address these problems, we introduce AndroidSlicer1, the first slicing approach for Android. AndroidSlicer combines a novel asynchronous slicing approach for modeling data and control dependences in the presence of callbacks with lightweight and precise instrumentation; this allows slicing for apps running on actual phones, and without requiring the app's source code. Our slicer is capable of handling a wide array of inputs that Android supports without adding any noticeable overhead. Experiments on 60 apps from Google Play show that AndroidSlicer is effective (reducing the number of instructions to be examined to 0.3% of executed instructions) and efficient (app instrumentation and post-processing combined takes 31 seconds); all while imposing a runtime overhead of just 4%. We present three applications of AndroidSlicer that are particularly relevant in the mobile domain: (1) finding and tracking input parts responsible for an error/crash, (2) fault localization, i.e., finding the instructions responsible for an error/crash, and (3) reducing the regression test suite. Experiments with these applications on an additional set of 18 popular apps indicate that AndroidSlicer is effective for Android testing and debugging.

Clustering is a key Machine Learning technique, used in many high-stakes domains from medicine to self-driving cars. Many clustering algorithms have been proposed, and these algorithms have been implemented in many toolkits. Clustering users assume that clustering implementations are correct, reliable, and for a given algorithm, interchangeable. We challenge these assumptions. We introduce SmokeOut, an approach and tool that pits clustering implementations against each other (and against themselves) while controlling for algorithm and dataset, to find datasets where clustering outcomes differ when they shouldn't, and measure this difference. We ran SmokeOut on 7 clustering algorithms (3 deterministic and 4 nondeterministic) implemented in 7 widely-used toolkits, and run in a variety of scenarios on the Penn Machine Learning Benchmark (162 datasets). SmokeOut has revealed that clustering implementations are fragile: on a given input dataset and using a given clustering algorithm, clustering outcomes and accuracy vary widely between (1) successive runs of the same toolkit; (2) different input parameters for that tool; (3) different toolkits.

Device Administrator (DA) capabilities for mobile devices, e.g., remote locking/wiping, or enforcing password strength, were originally introduced to help organizations manage phone fleets or enable parental control. However, DA capabilities have been subverted and abused: malicious apps have used DA to create ransomware or lock users out, while benign apps have used DA to prevent or hinder uninstallation; in certain cases the only remedy is to factory-reset the phone. We call these apps "Deathless Device Administrator" (DDA), i.e., apps that cannot be uninstalled. We provide the first systematic study of Android DA capabilities, DDA apps, DDA-attack resistance across Android versions, and DDA-induced families in malicious apps. To enable scalable studies of questionable DA behavior, we developed DAAX, a static analyzer which exposes potential DA abuse effectively and efficiently. In a corpus of 39,459 apps (20,467 malicious and 18,992 benign) DAAX has found 4,135 DA apps and 691 potential DDA apps. The static analysis results on the 4,135 apps were cross-checked via dynamic analysis on at least 3 phones, confirming 578 true DDAs, including apps currently on Google Play. The study has shown that DAAX is effective (84.8% F-measure) and efficient (analysis typically takes 205 seconds per app).

App links, also known as mobile deep links, are URIs that point to specific pages in an app. App links are essential to many mobile experiences: Google and Bing use them to link search results directly to relevant pages in an app and apps use them for cross-app navigation. However, app links are hard to discover and, since they must be explicitly built into apps by developers, only exist for a small fraction of apps. To address these two problems, we propose Elix, an automated app link extractor. We define link extraction as a static information flow problem where a link, with its scheme and parameters, is synthesized by analyzing the data flow between subsequent pages in an app. As static analysis is prone to false positives, Elix adopts a novel, path-selective taint analysis that leverages symbolic execution to reason about path constraints and abandon infeasible paths. Elix can automatically and correctly discover links that are exposed by an app, and many others that are not explicitly exposed, thus increasing coverage of both link-enabled apps and link-enabled pages in an app. Elix also simplifies the scheme of extracted links by reducing complex types to a minimal set of primitive types. We have implemented Elix on Android and applied it to 1007 popular Android apps. Elix can extract 80-90% of an app's links, and above 80% of the extracted links are stable.

Event-based races are the main source of concurrency errors in Android apps. Prior approaches for scalable detection of event-based races have been dynamic. Due to their dynamic nature, these approaches suffer from coverage and false negative issues. We introduce a precise and scalable static approach and tool, named SIERRA, for detecting Android event-based races. SIERRA is centered around a new concept of "concurrency action" (that reifies threads, events/messages, system and user actions) and statically-derived order (happens-before relation) between actions. Establishing action order is complicated in Android, and event-based systems in general, because of externally-orchestrated control flow, use of callbacks, asynchronous tasks, and ad-hoc synchronization. We introduce several novel approaches that enable us to infer order relations statically: auto-generated code models which impose order among lifecycle and GUI events; a novel context abstraction for event-driven programs named action-sensitivity and finally, on-demand path sensitivity via backward symbolic execution to further rule out false positives. We have evaluated SIERRA on 194 Android apps. Of these, we chose 20 apps for manual analysis and comparison with a state-of-the-art dynamic race detector. Experimental results show that SIERRA is effective and efficient, typically taking 960 seconds to analyze an app and revealing 43 potential races. Compared with the dynamic race detector, SIERRA discovered an average 29.5 true races with 3.5 false positives, where the dynamic detector only discovered 4 races (hence missing 25.5 races per app) -- this demonstrates the advantage of a precise static approach. We believe that our approach opens the way for precise analysis and static event race detection in other event-driven systems beyond Android.

Applications (apps) that conceal their activities are fundamentally deceptive; app marketplaces and end-users should treat such apps as suspicious. However, due to its nature and intent, activity concealing is not disclosed up-front, which puts users at risk. In this paper, we focus on characterization and detection of such techniques, e.g., hiding the app or removing traces, which we call "self hiding behavior" (SHB). SHB has not been studied per se - rather it has been reported on only as a byproduct of malware investigations. We address this gap via a study and suite of static analyses targeted at SH in Android apps. Specifically, we present (1) a detailed characterization of SHB, (2) a suite of static analyses to detect such behavior, and (3) a set of detectors that employ SHB to distinguish between benign and malicious apps. We show that SHB ranges from hiding the app's presence or activity to covering an app's traces, e.g., by blocking phone calls/text messages or removing calls and messages from logs. Using our static analysis tools on a large dataset of 9,452 Android apps (benign as well as malicious) we expose the frequency of 12 such SH behaviors. Our approach is effective: it has revealed that malicious apps employ 1.5 SHBs per app on average. Surprisingly, SH behavior is also employed by legitimate ("benign") apps, which can affect users negatively in multiple ways. When using our approach for separating malicious from benign apps, our approach has high precision and recall (combined F-measure = 87.19%). Our approach is also efficient, with analysis typically taking just 37 seconds per app. We believe that our findings and analysis tool are beneficial to both app marketplaces and end-users.

User surveys have shown that a typical user has over a 100 apps on his/her smartphone [1], but stops using many of them. We conduct a user study to identify such unused apps, which we call zombies, and show via experiments that zombie apps consume significant resources on a user's smartphone and access his/her private information. We then design and build ZapDroid, which enables users to detect and silo zombie apps in an effective way to prevent their undesired activities. If and when the user wishes to resume using such an app, ZapDroid restores the app quickly and effectively. Our evaluations show that: (i) ZapDroid saves twice the energy from unwanted zombie app behaviors as compared to apps from the Play Store that kill background unwanted processes, and (ii) it effectively prevents zombie apps from using undesired permissions. In addition, ZapDroid is energy-efficient, consuming <;4 percent of the battery per day.

The choice of data structures is crucial for achieving high performance. For applications that are long-running and/or operate on large data sets, the best choice for main data structures can change multiple times over the course of a single execution. For example, in a graph-processing application where the graph evolves over time, the best data structure for representing the graph may change as the program executes. Similarly, in a database or a key-value store application, with changes in relative frequencies of different types of queries over time, the most efficient data structure changes as well. We introduce an approach that allows applications to adapt to current conditions (input characteristics, operations on data, state) by switching their data structures on-the-fly with little overhead and without the developer worrying about safety or specifying adaptation points (this is handled by our compiler infrastructure). We use our approach on different classes of problems that are compute- and memory-intensive: graph algorithms, database indexing, and two real-world applications, the Memcached object cache and the Space Tyrant online game server. Our results show that off-the-shelf applications can be transformed into adaptive applications with modest programmer effort; that the adaptive versions outperform the original, fixed-representation versions; and that adaptation can be performed on-the-fly safely and with very little runtime overhead.

Specification-based data structure verification is a powerful debugging technique. In this work we combine specification-based data structure verification with automatic detection of faulty program statements that corrupt data structures. The user specifies the consistency constraints for dynamic data structures as relationships among the nodes of a memory graph. Our system detects constraint violations to identify corrupted data structures during program execution and then automatically locates faulty code responsible for data structure corruption. Our approach offers two main advantages: (1) a highly precise automatic fault location method, and (2) a simple specification language. We employ incremental constraint checking for time efficient constraint matching and fault location. On average, while Tarantula statistical debugging technique narrows the fault to 10 statements, our technique narrows it to ≈ 4 statements..

Large-scale parallel graph analytics involves executing iterative algorithms (e.g., PageRank, Shortest Paths, etc.) that are both data- and compute-intensive. In this work we construct faster versions of iterative graph algorithms from their original counterparts using input graph reduction. A large input graph is transformed into a small graph using a sequence of input reduction transformations. Savings in execution time are achieved using our two phased processing model that effectively runs the original iterative algorithm in two phases: first, using the reduced input graph to gain savings in execution time; and second, using the original input graph along with the results from the first phase for computing precise results. We propose several input reduction transformations and identify the structural and non-structural properties that they guarantee, which in turn are used to ensure the correctness of results while using our two phased processing model. We further present a unified input reduction algorithm that efficiently applies a non-interfering sequence of simple local input reduction transformations. Our experiments show that our transformation techniques enable significant reductions in execution time (1.25x-2.14x) while achieving precise final results for most of the algorithms. For cases where precise results cannot be achieved, the relative error remains very small (at most 0.065).

Linearizability of concurrent data structure implementations is notoriously hard to prove. Consequently, current verification techniques can only prove linearizability for certain classes of data structures. We introduce a generic, sound, and practical technique to statically check the linearizability of concurrent data structure implementations. Our technique involves specifying the concurrent operations as a list of sub-operations and passing this specification on to an automated checker that verifies linearizability using relationships between individual suboperations. We have proven the soundness of our technique. Our approach is expressive: we have successfully verified the linearizability of 12 popular concurrent data structure implementations including algorithms that are considered to be challenging to prove linearizable such as elimination back-off stack, lazy linked list, and time-stamped stack. Our checker is effective, as it can verify the specifications in less than a second.

Concurrency has been a perpetual problem in Android apps, mainly due to event-based races. Several event-based race detectors have been proposed, but they produce false positives, cannot reproduce races, and cannot distinguish be- tween benign and harmful races. To address these issues, we introduce a race verification and reproduction approach named ERVA. Given a race report produced by a race detector, ERVA uses event dependency graphs, event flipping, and replay to verify the race and determine whether it is a false positive, or a true positive; for true positives, ERVA uses state comparison to distinguish benign races from harmful races. ERVA automatically produces an event schedule that can be used to deterministically reproduce the race, so developers can fix it. Experiments on 16 apps indicate that only 3% of the races reported by race detectors are harmful, and that ERVA can verify an app in 20 minutes on average.

Smartphone apps create and handle a large variety of ``instance'' data that has to persist across runs, such as the current navigation route, workout results, antivirus settings, or game state. Due to the nature of the smartphone platform, an app can be paused, sent into background, or killed at any time. If the instance data is not saved and restored between runs, in addition to data loss, partially-saved or corrupted data can crash the app upon resume or restart. While smartphone platforms offer API support for data-saving and data-retrieving operations, the use of this API is ad-hoc: left to the programmer, rather than enforced by the compiler. We have observed that several categories of bugs---including data loss, failure to resume/restart or resuming/restarting in the wrong state---are due to incorrect handling of instance data and are easily triggered by just pressing the `Home' or `Back' buttons. To help address this problem, we have constructed a tool chain for Android (the KREfinder static analysis and the KREreproducer input generator) that helps find and reproduce such incorrect handling. We have evaluated our approach by running the static analysis on 324 apps, of which 49 were further analyzed manually. Results indicate that our approach is (i) effective, as it has discovered 49 bugs, including in popular Android apps, and (ii) efficient, completing on average in 61 seconds per app. More generally, our approach helps determine whether an app saves too much or too little state.

Concurrency bugs are difficult to find and fix. To help with finding and fixing concurrency bugs, prior research has mostly focused on static or dynamic analyses for finding specific classes of bugs. We present an approach whose focus is understanding the differences between concurrency and non-concurrency bugs, the differences among various concurrency bug classes, and predicting bug quantity, type, and location, from patches, bug reports and bug-fix metrics. First, we show that bug characteristics and bug-fixing processes vary significantly among different kinds of concurrency bugs and compared to non-concurrency bugs. Next, we build a quantitative predictor model to estimate concurrency bugs appearance in future releases. Then, we build a qualitative predictor that can predict the type of concurrency bug for a newly-filed bug report. Finally, we build a bug location predictor to indicate the likely source code location for newly-reported bugs. We validate the effectiveness of our approach on three popular projects, Mozilla, KDE, and Apache.

As smartphones continue to increase in popularity, understanding how software processes associated with the smartphone platform differ from the traditional desktop platform is critical for improving user experience and facilitating software development and maintenance. In this paper we focus specifically on differences in bugs and bug-fixing processes between desktop and smartphone software. Our study covers 444,129 bug reports in 88 open source projects on desktop, Android, and iOS. The study has two main thrusts: a quantitative analysis to discover similarities and differences between desktop and smartphone bug reports/processes; and a qualitative analysis where we extract topics from bug reports to understand bugs' nature, categories, and differences between platforms. Our findings include: during 2011--2013, iOS bugs were fixed three times faster compared to Android and desktop; top smartphone bug fixers are more involved in reporting bugs than top desktop bug fixers; and most frequent high-severity bugs are due to build issues on desktop, concurrency on Android, and application logic on iOS. Our study, findings, and recommendations are potentially useful to smartphone researchers and practitioners.

Smartphone privacy and security work has focused mostly on malicious apps. We take a different angle by questioning whether good apps suffer from a lack of judgment and interact with "bad" websites. We use the term bad websites to refer to entities that engage in dangerous or annoying activities that range from distributing malware, to phishing and overly aggressive ad spamming. The focus of our work is this relatively neglected aspect of security: "Whom does an app talk to?" In this paper, we design and implement AURA, a framework for identifying the hosts that an app talks to and evaluating the risks this communication entails. AURA makes use of both static and dynamic analysis. We studied 13,500 popular free Android apps that connect to 254,022 URLs and 1,260 malicious Android apps that connect to 19,510 URLs. Our main contribution is showing that good apps pose security risks as they contact at least one website that: (a) distributes malware (8.8% of apps), (b) are in a blacklist (15% of apps) based on the classification by VirusTotal and Web of Trust. Our work can raise awareness that even good apps need to be carefully evaluated, especially as people become more concerned about smartphone security and privacy.

User surveys have shown that a typical user has over a hundred apps on her smartphone [1], but stops using many of them. We conduct a user study to identify such unused apps, which we call zombies, and show via experiments that zombie apps consume significant resources on a user's smartphone and access her private information. We then design and build ZapDroid, which enables users to detect and silo zombie apps in an effective way to prevent their undesired activities. If and when the user wishes to resume using such an app, ZapDroid restores the app quickly and effectively. Our evaluations show that: (i) ZapDroid saves twice the energy from unwanted zombie app behaviors as compared to apps from the Play Store that kill background unwanted processes, and (ii) it effectively prevents zombie apps from using undesired permissions. In addition, ZapDroid is energ-efficient, consuming < 4% of the battery per day.

The Bring-Your-Own-Handheld-device (BYOH) phenomenon continues to make inroads as more people bring their own handheld devices to work or school. While convenient to device owners, this trend presents novel management challenges to network administrators. Prior efforts only focused on studying either the comparative characterization of aggregate network traffic between BYOHs and non-BYOHs or network performance issues, such as TCP and download times or mobility issues. We identify one critical question that network administrators need to answer: how do these BYOHs behave individually? In response, we design and deploy Brofiler, a behavior-aware profiling framework that improves visibility into the management of BYOHs. The contributions of our work are two-fold. First, we present Brofiler, a time-aware device-centric approach for grouping devices into intuitive behavioral groups. Second, we conduct an extensive study of BYOHs using our approach with real data collected over a year, and highlight several novel insights on the behavior of BYOHs. These observations underscore the importance of that BYOHs need to be managed explicitly as they behave in unique and unexpected ways.

Bugs of different severities have so far been put into the same category, but their characteristics differ significantly. Moreover, the nature of issues with the same severity, e.g., high, differs markedly between desktops and smartphones. To understand these differences, we perform an empirical study on 72 Android and desktop projects. We first define three bug severity classes: high, medium, and low. Next, we study how severity changes and quantify differences between classes in terms of bug-fixing attributes. Then, we focus on topic differences: using LDA, we extract topics associated with each severity class, and study how these topics differ across classes, platforms, and over time. Our findings include: severity and priority affect bug fixing time; medium-severity contributors are more experienced than high-severity contributors; and there have been more concurrency and cloud-related high-severity bugs on desktop since 2009, while on Android concurrency bugs are prevalent.

Recording and replaying the execution of smartphone apps is useful in a variety of contexts, from reproducing bugs to profiling and testing. Achieving effective record-and-replay is a balancing act between accuracy and overhead. On smartphones, the act is particularly complicated, because smartphone apps receive a high-bandwidth stream of input (e.g., network, GPS, camera, microphone, touchscreen) and concurrency events, but the stream has to be recorded and replayed with minimal overhead, to avoid interfering with app execution. Prior record-and-replay approaches have focused on replaying machine instructions or system calls, which is not a good fit on smartphones. We propose a novel, stream-oriented record-and-replay approach which achieves high-accuracy and low-overhead by aiming at a sweet spot: recording and replaying sensor and network input, event schedules, and inter-app communication via intents. To demonstrate the versatility of our approach, we have constructed a tool named VALERA that supports record-and-replay on the Android platform. VALERA works with apps running directly on the phone, and does not require access to the app source code. Through an evaluation on 50 popular Android apps, we show that: VALERA's replay fidelity far exceeds current record-and-replay approaches for Android; VALERA's precise timing control and low overhead (about 1% for either record or replay) allows it to replay high-throughput, timing-sensitive apps such as video/audio capture and recognition; and VALERA's support for event schedule replay enables the construction of useful analyses, such as reproducing event-driven race bugs.

Memory graphs are very useful in understanding the behavior of programs that use dynamically allocated data structures. We present a new memory graph representation, MG++, and a memory graph construction algorithm, that greatly enhance the utility of memory graphs. First, in addition to capturing the shapes of dynamically-constructed data structures, MG++ also captures how they evolve as the program executes and records the source code statements that play a role in their evolution to assist in debugging. Second, MG++ captures the history of actions performed by the memory allocator. This is useful in debugging programs that internally manage storage or in cases where understanding program behavior requires examining memory allocator actions. Our binary instrumentation-based algorithm for MG++ construction does not rely on the knowledge of memory allocator functions or on symbol table information. Our algorithm works for custom memory allocators as well as for in-program memory management. Experiments studying the time and space efficiency for real-world programs show that MG++ representation is space-efficient and the time overhead for MG++ construction algorithm is practical. We show that MG++ is effective for fault location and for analyzing binaries to detect heap buffer overflow attacks.

Determining contributors' expertise, role, and individual importance are fundamental for assessing their impact on a software project. Currently-used expertise metrics are agnostic to contributor roles and can lead to incorrect characterizations. To address these issues, we operationalize contributor expertise and role. First, we revisit current expertise metrics and show that their use bundles many different aspects, creating ambiguity. Second, we introduce clearly-defined contributor roles, which capture multiple project facets. Third, we propose a graph model, based on contributor collaborations, that captures the hierarchical structure of the contributor community in a concise yet informative way. We demonstrate the model's usefulness in two ways: (a) for identifying the structure and evolution of contributor interactions, (b) for predicting contributor roles. We substantiate our study using two large open-source projects, Fire fox and Eclipse. Our systematic approach clarifies and isolates contributor role and expertise, and sheds light onto the dynamics of contributors within software projects.

Frequent app bugs and low tolerance for loss of functionality create an impetus for self-healing smartphone software. We take a step towards this via on-the-fly error detection and automated patching. Specifically, we add failure detection and recovery to Android by detecting crashes and ``sealing off'' the crashing part of the app to avoid future crashes. In the detection stage, our system dynamically analyzes app execution to detect certain exceptional situations. In the recovery stage, we use bytecode rewriting to alter app behavior as to avoid such situations in the future. When using our implementation, apps can resume operation (albeit with limited functionality) instead of repeatedly crashing. Our approach does not require access to app source code or any system (e.g., kernel-level) modification. Experiments on several real-world, popular Android apps and bugs show that our approach manages to recover the apps from crashes effectively, timely, and without introducing overhead.

Touchscreen-based devices such as smartphones and tablets are gaining popularity, but their rich input capabilities pose new development and testing complications. To alleviate this problem, we present an approach and tool named Reran that permits record-and-replay for the Android smartphone platform. Existing GUI-level record-and-replay approaches are inadequate due to the expressiveness of the smartphone domain, in which applications support sophisticated GUI gestures, depend on inputs from a variety of sensors on the device, and have precise timing requirements among the various input events. We address these challenges by directly capturing the low-level event stream on the phone, which includes both GUI events and sensor events, and replaying it with microsecond accuracy. Moreover, Reran does not require access to app source code, perform any app rewriting, or perform any modifications to the virtual machine or Android platform. We demonstrate RERAN's applicability in a variety of scenarios, including (a) replaying 86 out of the Top-100 Android apps on Google Play; (b) reproducing bugs in popular apps, e.g., Firefox, Facebook, Quickoffice; and (c) fast-forwarding executions. We believe that our versatile approach can help both Android developers and researchers.

In this paper we develop a dynamic analysis, named relevant input analysis, that characterizes the role and strength of inputs in the computation of different values during a program execution. The role indicates whether a computed value is derived from an input value or its computation is simply influenced by an input value. The strength indicates if role (derived or influenced) relied upon the precise value of the input or it is among one of many values that can play a similar role. While it is clear that the results of our analysis can be very useful for the programmer in understanding relationships between inputs and program behavior, we also demonstrate the usefulness of the analysis by developing an efficient delta debugging algorithm. Other applications of relevant input analysis include assisting in generating test inputs and detection of security holes.

We present a new approach for constructing debuggers based on declarative specification of bug conditions and root causes, and automatic generation of debugger code. We illustrate our approach on several classes of bugs, memory or otherwise. For each bug class, bug conditions and their root cause are specified declaratively, in First-order logic, using 1 to 4 predicates. We employ a low-level operational semantics and abstract traces to permit concise bug specification and prove soundness. To facilitate locating bugs, we introduce a new concept of value propagation chains that reduce programmer burden by narrowing the fault to a handful of executed instructions (1 to 16 in our experiments). We employ automatic translation to generate the debugger implementation, which runs on top of the Pin infrastructure. Experiments with using our system on 7 versions of 4 real-world programs show that our approach is expressive, effective at finding bugs and their causes, and efficient. We believe that, using our approach, other kinds of declaratively-specified, provably-correct, auto-generated debuggers can be constructed with little effort.

Systematic exploration of Android apps is an enabler for a variety of app analysis and testing tasks. Performing the exploration while apps run on actual phones is essential for exploring the full range of app capabilities. However, exploring real-world apps on real phones is challenging due to non-determinism, non-standard control flow, scalability and overhead constraints. Relying on end-users to conduct the exploration might not be very effective: we performed a 7-use study on popular Android apps, and found that the combined 7-use coverage was 30.08% of the app screens and 6.46% of the app methods. Prior approaches for automated exploration of Android apps have run apps in an emulator or focused on small apps whose source code was available. To address these problems, we present A3E, an approach and tool that allows substantial Android apps to be explored systematically while running on actual phones, yet without requiring access to the app's source code. The key insight of our approach is to use a static, taint-style, dataflow analysis on the app bytecode in a novel way, to construct a high-level control flow graph that captures legal transitions among activities (app screens). We then use this graph to develop an exploration strategy named Targeted Exploration that permits fast, direct exploration of activities, including activities that would be difficult to reach during normal use. We also developed a strategy named Depth-first Exploration that mimics user actions for exploring activities and their constituents in a slower, but more systematic way. To measure the effectiveness of our techniques, we use two metrics: activity coverage (number of screens explored) and method coverage. Experiments with using our approach on 25 popular Android apps including BBC News, Gas Buddy, Amazon Mobile, YouTube, Shazam Encore, and CNN, show that our exploration techniques achieve 59.39--64.11% activity coverage and 29.53--36.46% method coverage.

Despite significant advances in automated debugging, programmers still rely on traditional interactive debuggers (e.g., GDB) to find and fix bugs. While popular, these debuggers have major deficiencies: they do not guide the programmer in narrowing the source of error, and they only support a limited and low-level set of state-altering commands, hence semantic state alteration requires recompilation and reexecution. To address these shortcomings, we present an interactive debugger that combines capabilities that reduce debugging effort and increase debugging speed. The capabilities that yield these benefits include: state alteration commands for dynamically switching the directions of conditional branches and suppressing the execution of statements; state inspection commands including navigating and pruning dynamic slices; and state rollback and checkpointing commands to allow reexecution of the program from an earlier checkpoint. Our prototype is built on top of GDB using the Pin infrastructure; we also provide a GUI based on KDbg. Our experience shows that our debugger handles many kinds of real bugs effectively and efficiently.

In this paper, we study the intertwined propagation of two competing "memes" (or data, rumors, etc.) in a composite network. Within the constraints of this scenario, we ask two key questions: (a) which meme will prevail? and (b) can one influence the outcome of the propagations? Our model is underpinned by two key concepts, a structural graph model (composite network) and a viral propagation model (SI1I2S). Using this framework, we formulate a non-linear dynamic system and perform an eigenvalue analysis to identify the tipping point of the epidemic behavior. Based on insights gained from this analysis, we demonstrate an effective and accurate prediction method to determine viral dominance, which we call the EigenPredictor. Next, using a combination of synthetic and real composite networks, we evaluate the effectiveness of various viral suppression techniques by either a) concurrently suppressing both memes or b) unilaterally suppressing a single meme while leaving the other relatively unaffected.

SUMMARY Software evolution is a fact of life. Over the past 30 years, researchers have proposed hypotheses on how software changes and provided evidence that both supports and refutes these hypotheses. To paint a clearer image of the software evolution process, we performed an empirical study on long spans in the lifetime of nine open‐source projects. Our analysis covers 705 official releases and a combined 108 years of evolution. We first tried to confirm Lehman's eight laws of software evolution on these projects using statistical hypothesis testing. Our findings indicate that only the laws of continuing change and continuing growth are confirmed for all programs, whereas the other six laws are violated by some programs, or can be both confirmed and invalidated, depending on the laws' operational definitions. Second, we analyze the growth rate for projects' development and maintenance branches, and the distribution of software changes. We find similarities in the evolution patterns of the programs we studied, which brings us closer to constructing rigorous models for software evolution. Copyright © 2011 John Wiley & Sons, Ltd.

Android uses a system of permissions to control how apps access sensitive devices and data stores. Unfortunately, we have little understanding of the evolution of Android permissions since their inception (2008). Is the permission model allowing the Android platform and apps to become more secure? In this paper, we present arguably the first long-term study that is centered around both permission evolution and usage, of the entire Android ecosystem (platform, third-party apps, and pre-installed apps). First, we study the Android platform to see how the set of permissions has evolved; we find that this set tends to grow, and the growth is not aimed towards providing finer-grained permissions but rather towards offering access to new hardware features; a particular concern is that the set of Dangerous permissions is increasing. Second, we study Android third-party and pre-installed apps to examine whether they follow the principle of least privilege. We find that this is not the case, as an increasing percentage of the popular apps we study are overprivileged. In addition, the apps tend to use more permissions over time. Third, we highlight some concerns with pre-installed apps, e.g., apps that vendors distribute with the phone; these apps have access to, and use, a larger set of higher-privileged permissions which pose security and privacy risks. At the risk of oversimplification, we state that the Android ecosystem is not becoming more secure from the user's point of view. Our study derives four recommendations for improving the Android security and suggests the need to revisit the practices and policies of the ecosystem.

We exploit recent advances in analysis of graph topology to better understand software evolution, and to construct predictors that facilitate software development and maintenance. Managing an evolving, collaborative software system is a complex and expensive process, which still cannot ensure software reliability. Emerging techniques in graph mining have revolutionized the modeling of many complex systems and processes. We show how we can use a graph-based characterization of a software system to capture its evolution and facilitate development, by helping us estimate bug severity, prioritize refactoring efforts, and predict defect-prone releases. Our work consists of three main thrusts. First, we construct graphs that capture software structure at two different levels: (a) the product, i.e., source code and module level, and (b) the process, i.e., developer collaboration level. We identify a set of graph metrics that capture interesting properties of these graphs. Second, we study the evolution of eleven open source programs, including Firefox, Eclipse, MySQL, over the lifespan of the programs, typically a decade or more. Third, we show how our graph metrics can be used to construct predictors for bug severity, high-maintenance software parts, and failure-prone releases. Our work strongly suggests that using graph topology analysis concepts can open many actionable avenues in software engineering research and practice.

The Android platform lacks tools for assessing and monitoring apps in a systematic way. This lack of tools is particularly problematic when combined with the open nature of Google Play, the main app distribution channel. As our key contribution, we design and implement ProfileDroid, a comprehensive, multi-layer system for monitoring and profiling apps. Our approach is arguably the first to profile apps at four layers: (a) static, or app specification, (b) user interaction, (c) operating system, and (d) network. We evaluate 27 free and paid Android apps and make several observations: (a) we identify discrepancies between the app specification and app execution, (b) free versions of apps could end up costing more than their paid counterparts, due to an order of magnitude increase in traffic, (c) most network traffic is not encrypted, (d) apps communicate with many more sources than users might expect---as many as 13, and (e) we find that 22 out of 27 apps communicate with Google during execution. ProfileDroid is the first step towards a systematic approach for (a) generating cost-effective but comprehensive app profiles, and (b) identifying inconsistencies and surprising behaviors.

Software-based thread-level parallelization has been widely studied for exploiting data parallelism in purely computational loops to improve program performance on multiprocessors. However, none of the previous efforts deal with efficient parallelization of hybrid loops, i.e., loops that contain a mix of computation and I/O operations. In this paper, we propose a set of techniques for efficiently parallelizing hybrid loops. Our techniques apply DOALL parallelism to hybrid loops by breaking the cross-iteration dependences caused by I/O operations. We also support speculative execution of I/O operations to enable speculative parallelization of hybrid loops. Helper threading is used to reduce the I/O bus contention caused by the improved parallelism. We provide an easy-to-use programming model for exploiting parallelism in loops with I/O operations. Parallelizing hybrid loops using our model requires few modifications to the code. We have developed a prototype implementation of our programming model. We have evaluated our implementation on a 24-core machine using eight applications, including a widely-used genomic sequence assembler and a multi-player game server, and others from PARSEC and SPEC CPU2000 benchmark suites. The hybrid loops in these applications take 23%-99% of the total execution time on our 24-core machine. The parallelized applications achieve speedups of 3.0x-12.8x with hybrid loop parallelization over the sequential versions of the same applications. Compared to the versions of applications where only computation loops are parallelized, hybrid loop parallelization improves the application performance by 68% on average.

Billions of dollars are spent every year for building and maintaining software. To reduce these costs we must identify the key factors that lead to better software and more productive development. One such key factor, and the focus of our paper, is the choice of programming language. Existing studies that analyze the impact of choice of programming language suffer from several deficiencies with respect to methodology and the applications they consider. For example, they consider applications built by different teams in different languages, hence fail to control for developer competence, or they consider small-sized, infrequently-used, short-lived projects. We propose a novel methodology which controls for development process and developer competence, and quantifies how the choice of programming language impacts software quality and developer productivity. We conduct a study and statistical analysis on a set of long-lived, widely-used, open source projects - Firefox, Blender, VLC, and MySQL. The key novelties of our study are: (1) we only consider projects which have considerable portions of development in two languages, C and C++, and (2) a majority of developers in these projects contribute to both C and C++ code bases. We found that using C++ instead of C results in improved software quality and reduced maintenance effort, and that code bases are shifting from C to C++. Our methodology lays a solid foundation for future studies on comparative advantages of particular programming languages.

Predicting bug-fix time is useful in several areas of software evolution, such as predicting software quality or coordinating development effort during bug triaging. Prior work has proposed bug-fix time prediction models that use various bug report attributes (e.g., number of developers who participated in fixing the bug, bug severity, number of patches, bug-opener's reputation) for estimating the time it will take to fix a newly-reported bug. In this paper we take a step towards constructing more accurate and more general bug-fix time prediction models by showing how existing models fail to validate on large projects widely-used in bug studies. In particular, we used multivariate and univariate regression testing to test the prediction significance of existing models on 512,474 bug reports from five open source projects: Eclipse, Chrome and three products from the Mozilla project (Firefox, Seamonkey and Thunderbird). The results of our regression testing indicate that the predictive power of existing models is between 30% and 49% and that there is a need for more independent variables (attributes) when constructing a prediction model. Additionally, we found that, unlike in prior recent studies on commercial software, in the projects we examined there is no correlation between bug-fix likelihood, bug-opener's reputation and the time it takes to fix a bug. These findings indicate three open research problems: (1) assessing whether prioritizing bugs using bug-opener's reputation is beneficial, (2) identifying attributes which are effective in predicting bug-fix time, and (3) constructing bug-fix time prediction models which can be validated on multiple projects.

Software bugs are inevitable and bug fixing is a difficult, expensive, and lengthy process. One of the primary reasons why bug fixing takes so long is the difficulty of accurately assigning a bug to the most competent developer for that bug kind or bug class. Assigning a bug to a potential developer, also known as bug triaging, is a labor-intensive, time-consuming and fault-prone process if done manually. Moreover, bugs frequently get reassigned to multiple developers before they are resolved, a process known as bug tossing. Researchers have proposed automated techniques to facilitate bug triaging and reduce bug tossing using machine learning-based prediction and tossing graphs. While these techniques achieve good prediction accuracy for triaging and reduce tossing paths, they are vulnerable to several issues: outdated training sets, inactive developers, and imprecise, single-attribute tossing graphs. In this paper we improve triaging accuracy and reduce tossing path lengths by employing several techniques such as refined classification using additional attributes and intra-fold updates during training, a precise ranking function for recommending potential tossees in tossing graphs, and multi-feature tossing graphs. We validate our approach on two large software projects, Mozilla and Eclipse, covering 856,259 bug reports and 21 cumulative years of development. We demonstrate that our techniques can achieve up to 83.62% prediction accuracy in bug triaging. Moreover, we reduce tossing path lengths to 1.5-2 tosses for most bugs, which represents a reduction of up to 86.31% compared to original tossing paths. Our improvements have the potential to significantly reduce the bug fixing effort, especially in the context of sizable projects with large numbers of testers and developers.

Software evolution is a fact of life. Over the past thirty years, researchers have proposed hypotheses on how software changes, and provided evidence that both supports and refutes these hypotheses. To paint a clearer image of the software evolution process, we performed an empirical study on long spans in the lifetime of seven open source projects. Our analysis covers 653 official releases, and a combined 69 years of evolution. We first tried to verify Lehman's laws of software evolution. Our findings indicate that several of these laws are confirmed, while the rest can be either confirmed or infirmed depending on the laws' operational definitions. Second, we analyze the growth rate for projects' development and maintenance branches, and the distribution of software changes. We find similarities in the evolution patterns of the programs we studied, which brings us closer to constructing rigorous models for software evolution.

Many dynamic updating systems have been developed that enable a program to be patched while it runs, to fix bugs or add new features. This paper explores techniques for supporting dynamic updates to multi-threaded programs, focusing on the problem of applying an update in a timely fashion while still producing correct behavior. Past work has shown that this tension of safety versus timeliness can be balanced for single-threaded programs. For multi-threaded programs, the task is more difficult because myriad thread interactions complicate understanding the possible program states to which a patch could be applied. Our approach allows the programmer to specify a few program points (e.g., one per thread) at which a patch may be applied, which simplifies reasoning about safety. To improve timeliness, a combination of static analysis and run-time support automatically expands these few points to many more that produce behavior equivalent to the originals. Experiments with thirteen realistic updates to three multi-threaded servers show that we can safely perform a dynamic update within milliseconds when more straightforward alternatives would delay some updates indefinitely.

This paper presents a generalization of standard effect systems that we call contextual effects. A traditional effect system computes the effect of an expression e. Our system additionally computes the effects of the computational context in which e occurs. More specifically, we computethe effect of the computation that has already occurred(the prior effect) and the effect of the computation yet to take place (the future effect).

This article presents Proteus, a core calculus that models dynamic software updating, a service for fixing bugs and adding features to a running program. Proteus permits a program's type structure to change dynamically but guarantees the updated program remains type-correct by ensuring a property we call con-freeness. We show how con-freeness can be enforced dynamically, and how it can be approximated via a novel static analysis. This analysis can be used to assess the implications of a program's structure on future updates in order to make update success more predictable. We have implemented Proteus for C, and briefly discuss our implementation which we have tested on several well-known programs.

Software updates typically require stopping and restarting an application, but many systems cannot afford to halt service, or would prefer not to. Dynamic software updating (DSU) addresses this difficulty by permitting programs to be updated while they run. DSU is appealing compared to other approaches for on-line upgrades because it is quite general and requires no redundant hardware. The challenge is in making DSU practical: it should be flexible, and yet safe, efficient, and easy to use.In this paper, we present Ginseng, a DSU implementation for C that aims to meet this challenge. We compile programs specially so that they can be dynamically patched, and generate most of a dynamic patch automatically. Ginseng performs a series of analyses that when combined with some simple runtime support ensure that an update will not violate type-safety while guaranteeing that data is kept up-to-date. We have used Ginseng to construct and dynamically apply patches to three substantial open-source server programs---Very Secure FTP daemon, OpenSSH sshd daemon, and GNU Zebra. In total, we dynamically patched each program with three years' worth of releases. Though the programs changed substantially, the majority of updates were easy to generate. Performance experiments show that all patches could be applied in less than 5 ms, and that the overhead on application throughput due to updating support ranged from 0 to at most 32%.

Dynamic software updates can be used to fix bugs or add features to a running program without downtime. Essential for some applications and convenient for others, low-level dynamic updating has been used for many years. Perhaps surprisingly, there is little high-level understanding or language support to help programmers write dynamic updates effectively.To bridge this gap, we present Proteus, a core calculus for dynamic software updating in C-like languages that is flexible, safe, and predictable. Proteus supports dynamic updates to functions (even active ones), to named types and to data, allowing on-line evolution to match source-code evolution as we have observed it in practice. We ensure updates are type-safe by checking for a property we call "con-freeness" for updated types t at the point of update. This means that non-updated code will not use t concretely beyond that point (concrete usages are via explicit coercions) and thus t's representation can safely change. We show how con-freeness can be enforced dynamically for a particular program state. We additionally define a novel and efficient static updateability analysis to establish con-freeness statically, and can thus automatically infer program points at which all future (well-formed) updates will be type-safe. We have implemented our analysis for C and tested it on several well-known programs.