Application monitoring through collective record and replay

[0001] This application is a continuation of co-pending U.S. patent application Ser. No. 13/325,062, filed Dec. 14, 2011 which is entitled “Application Monitoring Through Collective Record and Replay,” the application of which is incorporated herein by this reference as though fully set forth herein.

[0002] Many multi-user operating systems associate privileges with user accounts. When a user installs an application, the application runs in the name of the user and inherits the user's ability to access the system resources. However, modern browsers and device operating systems, such as smartphone operating systems, often treat applications as mutually-untrusting, potentially-malicious principals. In most cases, applications are isolated except for explicit inter-process, or inter-application, communication (IPC) channels. In addition, applications can be unprivileged by default, requiring user permission for additional privileges. In other words, permission to use devices and access user-private data through system application programming interfaces (APIs) may be granted to individual applications by the user.

[0003] However, modern permission systems may be undermined by the presence of malicious software within applications. Such malicious software may compromise users' privacy or violate platform providers' security policies. Current approaches focus on preventing malicious applications from reaching end users through manual review of each application that is added to the marketplace. However, this process is costly and time-consuming. Moreover, although approaches exist for monitoring applications in the wild, such as event logging and crash reports or online taint flow analysis, these methods are limited by either the small quantity of data collected or the high performance overhead on the end user.

[0004] The following presents a simplified summary of the innovation in order to provide a basic understanding of some aspects described herein. This summary is not an extensive overview of the claimed subject matter. It is intended to neither identify key nor critical elements of the claimed subject matter nor delineate the scope of the subject innovation. Its sole purpose is to present some concepts of the claimed subject matter in a simplified form as a prelude to the more detailed description that is presented later.

[0005] An embodiment provides a method for application monitoring through collective record and replay. The method includes recording a number of execution traces for an application from a number of user devices at a runtime library, wherein the number of execution traces relates to non-deterministic data. The method also includes replaying the number of execution traces to determine whether a behavior of the application creates a security risk.

[0006] Another embodiment provides a system for application monitoring through collective record and replay. The system includes an application configured to send a number of execution traces to a central server(s) from a number of user devices, wherein the number of execution traces relates to non-deterministic data. The system also includes a runtime library configured to redirect the number of execution traces from the API to the runtime library, record the number of execution traces on a memory device, and replay the number of execution traces to determine whether the application is functioning as expected.

[0007] In addition, another embodiment provides one or more non-transitory, computer-readable storage media for storing computer readable instructions, the computer-readable instructions providing a collective record and replay system when executed by one or more processing devices. The computer-readable instructions comprising code configured to perform probabilistic logging for an application to record a number of execution traces relating to non-deterministic data from a number of user devices. The computer-readable instructions also include code configured to determine whether the application is utilizing the number of non-deterministic data for an unexpected purpose by replaying the number of executions traces.

[0008] This Summary is provided to introduce a selection of concepts in a simplified form; these concepts are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

[0014] The same numbers are used throughout the disclosure and figures to reference like components and features. Numbers in the 100 series refer to features originally found in FIG. 1, numbers in the 200 series refer to features originally found in FIG. 2, numbers in the 300 series refer to features originally found in FIG. 3, and so on.

[0015] As discussed above, many modern applications include malicious software that violates the privacy of users and the security policies of platform providers. Such malicious software may gain access to users' private data through several different mechanisms. In some instances, a developer of an application may intentionally exploit user-private data for unauthorized or illegal purposes. In other instances, an application may unintentionally expose user-private data to potentially-malicious applications or third parties. In various embodiments, user-private data may be considered to be any data that is non-deterministic, or variable. The protection of such non-deterministic data from malicious applications may ensure that users' privacy rights are not violated.

[0016] Embodiments disclosed herein set forth a method and system for application monitoring through collective record and replay. The applications may include, for example, smartphone applications implemented on a mobile phone or Web applications implemented on a Web site, among others. Moreover, the applications may also include any types of computer programs which execute code that is related to any form of non-deterministic data. Such a method and system may prevent applications from performing actions that are not desired by the user, particularly in relation to non-deterministic data.

[0017] To implement the collective record and replay procedure, a number of execution traces for a particular application may be collectively recorded at a centralized location, referred to herein as a runtime library, from a number of different user devices. As used herein, an “execution trace” is a sequence of application programming interface (API) calls and non-deterministic data related to the API calls made by an application. Moreover, the execution traces may be recorded from a number of different user devices based on an assigned probability. The assigned probability may dictate the number of execution traces which are recorded from each user device and, thus, may determine the performance overhead of the collective recording procedure. When a partial execution trace is recorded, the assigned probability may also be used to decide whether to record the non-deterministic data related to a given API call. The assigned probability can be either API independent (i.e., all APIs have the same record/not-record probability) or API dependent (i.e., every API has its own record/not-record probability).

[0018] In various embodiments, the data recorded may include both the parameters passed to the API and the data returned from the API. Furthermore, partial execution traces may be probabilistically recorded in order to reduce the overhead cost. Once the execution traces have been recorded, they may be aggregated, replayed, and analyzed in order to determine whether the particular application is likely to be using the non-deterministic data for malicious purposes. Moreover, if it is determined that the application is likely to be malicious, the application may be blocked from the marketplace or removed from the user devices, or both.

[0019] As a preliminary matter, some of the figures describe concepts in the context of one or more structural components, variously referred to as functionality, modules, features, elements, etc. The various components shown in the figures can be implemented in any manner, for example, by software, hardware (e.g., discreet logic components, etc.), firmware, and so on, or any combination of these implementations. In one embodiment, the various components may reflect the use of corresponding components in an actual implementation. In other embodiments, any single component illustrated in the figures may be implemented by a number of actual components. The depiction of any two or more separate components in the figures may reflect different functions performed by a single actual component. FIG. 1, discussed below, provides details regarding one system that may be used to implement the functions shown in the figures.

[0020] Other figures describe the concepts in flowchart form. In this form, certain operations are described as constituting distinct blocks performed in a certain order. Such implementations are exemplary and non-limiting. Certain blocks described herein can be grouped together and performed in a single operation, certain blocks can be broken apart into plural component blocks, and certain blocks can be performed in an order that differs from that which is illustrated herein, including a parallel manner of performing the blocks. The blocks shown in the flowcharts can be implemented by software, hardware, firmware, manual processing, and the like, or any combination of these implementations. As used herein, hardware may include computer systems, discreet logic components, such as application specific integrated circuits (ASICs), and the like, as well as any combinations thereof.

[0021] As to terminology, the phrase “configured to” encompasses any way that any kind of functionality can be constructed to perform an identified operation. The functionality can be configured to perform an operation using, for instance, software, hardware, firmware and the like, or any combinations thereof.

[0022] The term “logic” encompasses any functionality for performing a task. For instance, each operation illustrated in the flowcharts corresponds to logic for performing that operation. An operation can be performed using, for instance, software, hardware, firmware, etc., or any combinations thereof.

[0023] As utilized herein, terms “component,” “system,” “client” and the like are intended to refer to a computer-related entity, either hardware, software (e.g., in execution), and/or firmware, or a combination thereof. For example, a component can be a process running on a processor, an object, an executable, a program, a function, a library, a subroutine, and/or a computer or a combination of software and hardware.

[0024] By way of illustration, both an application running on a server and the server can be a component. One or more components can reside within a process and a component can be localized on one computer and/or distributed between two or more computers. The term “processor” is generally understood to refer to a hardware component, such as a processing unit of a computer system.

[0025] Furthermore, the claimed subject matter may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof to control a computer to implement the disclosed subject matter. The term “article of manufacture” as used herein is intended to encompass a computer program accessible from any non-transitory computer-readable device, or media.

[0026] Computer-readable storage media can include but are not limited to magnetic storage devices (e.g., hard disk, floppy disk, and magnetic strips, among others), optical disks (e.g., compact disk (CD), and digital versatile disk (DVD), among others), smart cards, and flash memory devices (e.g., card, stick, and key drive, among others). In contrast, computer-readable media generally (i.e., not storage media) may additionally include communication media such as transmission media for wireless signals and the like.

[0027] FIG. 1 is a block diagram of an exemplary system 100 that may monitor potentially-malicious applications through the implementation of a collective record and replay procedure. The system 100 may be included within a computing device, such as, for example, a mobile phone, a tablet, a desktop computer, a laptop computer, an electronic reader, a television, or a media player, or any combinations thereof. Moreover, the system 100 may implemented within a server, wherein the server may include, for example, a Web server or a cloud server. The system 100 may include a processor 102 that is adapted to execute stored instructions, as well as a memory device 104 that stores instructions that are executable by the processor 102. The processor 102 may be a single core processor, a multi-core processor, a computing cluster, or any number of other configurations. The memory device 104 can include random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory systems. The stored instructions executed by the processor 102 may implement a method for monitoring applications in the wild using execution traces from multiple user devices according to a collective record and replay procedure. The processor 102 may be connected through a bus 106 to one or more input and output devices.

[0028] The system 100 may include a storage device 108 adapted to store a collective record and replay module 110 and a runtime library 112. The collective record and replay module 110 can be used to monitor applications by logging execution traces from multiple user devices, while the runtime library 112 can store the execution traces relating to the applications. In some embodiments, the runtime library 112 may include a record runtime library and a replay runtime library. The storage device 108 may include a hard drive, an optical drive, a thumbdrive, an array of drives, or any combinations thereof. Moreover, the storage device 108 may also be adapted to store an API 114 and any number of applications 116. The applications 116 may communicate with each other through the API 114.

[0029] A human-machine interface (HMI) 118 may connect the system 100 to any number of user-interface devices 120, such as a touchscreen, a speaker, or a pointing device, among others. The system 100 may be linked through the bus 106 to a display interface 122 adapted to connect the system 100 to a display device 124. The display device 124 may include a computer monitor or a display screen of a mobile device, among others.

[0030] A network interface controller (NIC) 126 may be included to connect the system 100 through the bus 106 to a network 128. Through the network 128, Web-based applications 130 may be downloaded and stored within the computer's storage device 108, or may be accessed through a Web browser. The Web-based applications 130 may be stored on a remote server or computing device. The system 100 may also be communicably coupled to multiple user devices (not shown) through the network 128. Moreover, the system 100 may download and record logs relating to API calls from the multiple user devices through the network 128. Further, the system 100 may be a server or other computing device configured to provide a centralized location for the recording and replaying of a number of execution traces for an application from a number of user devices. The number of execution traces may be sequences of API calls and non-deterministic data related to the API calls made by an application. In various embodiments, partial execution traces may be recorded instead of full execution traces in order to reduce the overhead. Moreover, data relating to a particular execution trace may be recorded, including both parameters passed to the API and data returned from the API.

[0031] FIG. 2 is a process flow diagram showing a method 200 for application monitoring through collective record and replay. The method begins at block 202 with the collective recording of a number of execution traces for an application from a number of user devices at a runtime library. The recorded execution traces may relate to a sequence of API calls and a number of non-deterministic data associated with the API calls. Non-deterministic data may include any data that is variable or inconstant, such as data that is typed into the user device directly by the user, multiple-choice data, or any type of user-private data. For example, non-deterministic data may include a name, a day of the week, a day of the month, a gender, an age, a phone number, an email address, a contact list, a message inbox, a message outbox, a global positioning system (GPS) location, a birthday, or a credit card number, among others. Moreover, the user devices from which the execution traces are recorded may include any types of computing devices, such as mobile devices, desktop computers, laptop computers, electronic readers, tablets, televisions, or gaming devices, among others. Moreover, any computing system which utilizes any type of application or program may be used in conjunction with the method 200. For example, the user devices may also include systems in cars or homes that are configured to perform any of a variety of different functions in response to execution traces generated through applications or programs.

[0032] In various embodiments, full execution traces may not be recorded but, rather, partial execution traces may be probabilistically recorded. For example, the probability of recording an execution trace may be a fixed value for all API calls or may be an API-independent variable. Moreover, the recorded data may include data relating to a particular API call, such as parameters passed to the API and data returned from the API.

[0033] The recording of the number of execution traces from the number of user devices within the runtime library may be performed at any level of the application stack, i.e., at any interface. The interface may be chosen in order to minimize the recording overhead on the client, wherein the recording overhead may be characterized by the amount of time, space, and energy consumed by the recording process. For example, in some embodiments, the recording of the execution traces, or the interposing on the events executed by a particular application, may be performed at the level of the native platform libraries. However, the method 200 is not limited to the interposing on events at the level of the native libraries but, rather, may be implemented at any interface level.

[0034] Recording the number of execution traces from the number of user devices may include sending some number of execution traces from each of the number of user devices to the runtime library. The runtime library may be configured to record the execution traces within a memory device, wherein the memory device may be located within the runtime library or may be communicably coupled to the runtime library, such as through a wireless or wired connection. For example, the memory device may include the storage device 108 or memory device 104 of the system 100 discussed with respect to FIG. 1. Moreover, the runtime library may be connected to the user devices through a network, such as, for example, a wide area network (WAN) or a local area network (LAN).

[0035] Furthermore, in some embodiments, the runtime library may be replaced with two separate runtime libraries, including a record runtime library and a replay runtime library. The record runtime library, or log transferring module, may run on each user device in conjunction with the application. In various embodiments, the record runtime library may be used to record one or more execution traces of an application on a particular user device. Based on configurations, the record runtime library may either immediately send the recorded execution traces to a central server or wait until the user device is connected to a power supply or a non-cellular network, for example, to send the recorded execution traces. In various embodiments, the replay runtime library may run on the central server. For each potentially-incomplete execution trace, the replay runtime library may attempt to utilize the recorded API data first if it is available in the execution trace. Otherwise, the replay runtime library may leverage the recorded data from the same API from other execution traces in order to reproduce the full execution trace from the partially-recorded execution trace.

[0036] The runtime library may record the number of execution traces from the number of user devices by redirecting a number of application API calls from an API to the runtime library, wherein the API may include a native library or any other type of application programming interface. The API may be the module that is normally responsible for recording and executing API calls from applications. Once the runtime library has received and recorded the redirected API calls, the API calls may be sent back to the user devices to be executed as normal. A network may be configured to communicably couple the runtime library, the application, the API, and the memory device, or any combinations thereof. Furthermore, the application and the API may be physically colocated within a user device, while the memory device and the runtime library may be physically colocated within a centralized server.

[0037] In various embodiments, the runtime library may probabilistically log, or record, the number of execution traces for a given event from the number of user devices, wherein the given event may include a specific function of an application. Moreover, the probabilistic logging of the number of execution traces may include determining a probability that a particular execution trace relating to a particular application will be recorded from an individual user device. Thus, the performance overhead for the method 200 may be shared between multiple user devices in order to decrease the burden on the users. In some embodiments, the lower the probability that a particular execution trace may be recorded from an individual user device, the lower the burden on the user. Moreover, a lower probability of recording a particular event or execution trace from a particular user device may correspond to a lower total number of recorded execution traces from the user devices.

[0038] Further, a variety of additional information relating to the API calls from the number of user devices may be recorded by the runtime library. For example, information about where in the application, or program, a particular API call originated may be stored by the runtime library in order to enable the replaying of the execution traces within the API call at block 204. A number of methods for recording such information may be employed, including, for example, tracking the application's execution history precisely using a path profiling algorithm or computing a hash of the call stack at the time when the function was invoked. Moreover, a timestamp relative to the start of the application may be recorded in order to track additional information pertaining to a particular API call.

[0039] In some embodiments, the recording of asynchronous events may be accomplished by intercepting the API through which the particular application registers the callback function. This is possible because a callback registration may be used to deliver such asynchronous events. The runtime library may then replace the reference to the callback function with a reference to a recording function in the runtime library. This ensures that, when the callback is invoked from the library code, the runtime library will be notified and may record the information relating to the particular callback.

[0040] At block 204, the number of execution traces may be replayed to determine whether a behavior of the application is malicious. The runtime library may obtain the recorded execution traces by reading the execution traces from the memory device. The runtime library may then replay the number of execution traces by recombining each of the number of execution traces recorded from each of the number of user devices in order to generate a replay of an event relating to the application. The replaying of the execution traces may be performed in a manner that maintains the original ordering and latency of API calls within each execution trace. One execution trace may be replayed at a time. When there is an API call in the execution for which there is no recorded data, recorded data of the same API from other execution traces may be combined to generate the data for the replay procedure. This may be repeated for each execution trace in the set of execution traces reported to the central server. Moreover, in some embodiments, replaying the number of execution traces may include executing an API call using the number of execution traces recorded by the runtime library and utilizing a result of the API call to analyze the behavior of the application.

[0041] Once the number of execution traces have been recombined and replayed, the recombined execution traces may be analyzed in order to determine whether the behavior of the application is malicious. The behavior of the application may be considered to be malicious if the application utilizes any non-deterministic data in an unauthorized manner or for an unexpected purpose, wherein the unexpected purpose may include any function that is not approved or authorized by a user or a service provider, or both. For example, a malicious application may share the non-deterministic data with an unapproved third party in an unauthorized manner.

[0042] The method 200 is not intended to indicate that the steps of the method 200 are to be executed in any particular order or that all of the steps are to be included in every case. Further, steps may be added to the method 200 according to the specific application. For example, once the execution traces have been replayed at block 204, the recombined execution traces may be sent to a separate device through a network to be analyzed. For example, the separate device may analyze the recombined execution traces using a specific program that is configured to determine the behavior of the application. The separate device may be utilized by the particular service provider for each type of user device. Moreover, a particular service provider may determine whether to remove a particular application from the user devices, or block the particular application from the marketplace, based on the information obtained from the recombined execution traces.

[0043] FIG. 3 is a block diagram of an exemplary system 300 that may be used to monitor applications through the collective recording of execution traces. The system 300 may include an application 302, wherein the application 302 is a program that operates within a number of user devices. The application 302 may send a number of API calls to a native library 304 from a number of different user devices, as indicated by the arrow 306. In some embodiments, the native library 304 may be the particular API that has been chosen to interpose on application events. Moreover, the native library 304 may be a module that is configured to store, prepare, and execute API calls received from any of a number of applications, including the application 302. Further, each of the API calls may include a number of execution traces relating to a particular application event and non-deterministic data.

[0044] A runtime library 308 may be configured to redirect the API calls from the native library 304 to the runtime library 308, as indicated by the arrow 310. The runtime library 308 may be a module that is configured to implement the collective record and replay method described with respect to FIG. 2. The runtime library 308 may store the number of execution traces within a memory device 312, as indicated by the arrow 314. The memory device 312 may include random access memory (RAM), read only memory (ROM), or flash memory, among others. For example, the memory device 312 may include the storage device 108 or memory device 104 of the system 100 discussed with respect to FIG. 1.

[0045] The runtime library 308 may also communicate directly with the native library 304. In some embodiments, the runtime library 308 may send the API calls to the native library 304, as indicated by the arrow 316, in order to enable normal execution of the API calls. Moreover, the native library 304 may send the result of each API call back to the runtime library 308, as indicated by the arrow 318. The runtime library 308 may then inform the application 302 of the result of each of the API calls from each of the user devices, as indicated by the arrow 320. In addition, the runtime library may record the result of each API call within the memory device 312.

[0046] The native library 304 may be colocated within a particular user device, while the runtime library 308 may be located within a server or other device that is wirelessly connected to the native library 304 through a network connection. Moreover, the runtime library 308 may be connected to multiple distinct native libraries located on multiple user devices, wherein the multiple user devices are configured to execute the functions of the application 302. In this case, the recording of the execution traces may be performed according to several different methods depending on the settings and capabilities of each user device. For example, if a user device has continuous, unlimited access to the Internet, the native library 304 within the user device may transmit the log of an execution immediately after the program execution ends. On the other hand, if a user device has expensive or bandwidth-limited access to the Internet, logs from API calls may be stored and transmitted in a batch when a less expensive connection becomes available.

[0047] FIG. 4 is a block diagram of an exemplary system 400 that may be used to monitor applications through the replay of collectively-recorded execution traces. Like numbered items are as described with respect to FIG. 3. The replay of the recorded execution traces may be initiated by the application 302, which may send API calls from a number of user devices to the native library 304, as indicated by the arrow 402. The API calls may be once again redirected from the native library 304 to the runtime library 308, as indicated by the arrow 404. The runtime library 308 may then read the recorded information, including the execution traces, pertaining to the particular API calls from the memory device 312, as indicated by the arrow 406.

[0048] The runtime library 308 can select one of the recorded inputs it has available for the particular API call at that program point and directly fill in the output data from the log, i.e., from the memory device 312. However, this selection process may have some degree of imprecision, since the recorded inputs stored within the memory device 312 may not be precise. In addition, due to the probabilistic nature of the recording process described with respect to FIG. 3, it is possible that multiple recorded events may be appropriate for a particular API call, or that no recorded events may be available for a particular API call.

[0049] If no recorded events are available for a particular API call, an input may be synthesized using random or crafted data, an appropriate input may be derived using a technology such as symbolic execution, or the API call may be stalled until an appropriate event is recorded by some client. Moreover, in order to replay asynchronous events, the runtime library 308 may call corresponding callbacks from the memory device 312 with recorded input parameters at certain times. The callback time may be dictated by the original ordering and latency of the API calls within the execution trace. Further, once the runtime library 308 has retrieved the recorded input information, including the recombined execution traces, normal execution of the API call event may continue at the application 302 on the number of user devices, as indicated by the arrow 408.

[0050] FIG. 5 is a block diagram showing a tangible, computer-readable medium 500 that stores code adapted to monitor potentially-malicious applications. The tangible, computer-readable medium 500 may be accessed by a processor 502, for example, over a computer bus 504. Furthermore, the tangible, computer-readable medium 500 may include code configured to direct the processor 502 to perform the steps of the current method. The various software components discussed herein may be stored on the tangible, computer-readable medium 800, as indicated in FIG. 5. For example, a collective record module 506 may be configured to record a number of execution traces for an application from a number of user devices, wherein the number of execution traces relate to user-private, non-deterministic data. A collective replay module 508 may also be configured to recombine and replay the application event that is defined by the number of recorded execution traces. The result obtained by the collective replay module 508 may then be used to determine whether the application violates the privacy of users or the security policies of service providers by utilizing the non-deterministic data in an unauthorized manner. Further, the tangible, computer-readable medium 500 may also include any number of additional software components not shown in FIG. 5.

[0051] Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.