CN110347448A - A method of the model when operation of construction terminal applies behavior - Google Patents

Abstract

The invention discloses a method for constructing a runtime model of a terminal application behavior. Through a behavior interpreter, a complete, accurate, and detailed self-statement of the application behavior is generated, that is, a runtime model of the terminal application behavior, which overcomes the limitations of the prior art. The dynamic, changeable, and difficult-to-control application runtime environment has insufficient monitoring of terminal application behaviors, and realizes flexible and complete monitoring of terminal application behaviors, providing a basis for the subsequent realization of command-level control of terminal application behaviors. technical support.

Description

A Method for Constructing a Runtime Model of Terminal Application Behavior

technical field

The present invention relates to computer technology, in particular to a method for constructing a runtime model of terminal application behavior.

Background technique

Internet architecture software (also known as terminal application) is an abstraction of the basic form of software systems in the open, dynamic and changeable environment of the Internet. It is not only a natural extension of traditional software structures, but also has a traditional Unique basic features of software form: 1) Autonomy, which means that software entities in Internet-based software systems have relative independence, initiative and adaptability. Autonomy makes it different from the dependence and passivity of software entities in traditional software systems; 2) Collaboration, which means that software entities in Internet-based software systems can communicate with each other in an open network according to various static connections and dynamic cooperation methods. Interconnection, intercommunication, collaboration and alliance in the network environment. Synergy makes it different from the single static connection mode of traditional software systems in a closed and centralized environment; 3) Reactivity refers to the ability of Internet-based software to perceive external operating and usage environments and provide useful information for system evolution. Reactivity enables the Internet-based software system to have the perception ability to adapt to open, dynamic and changeable environments; 4) Evolvability, which means that the Internet-based software structure can dynamically evolve according to application requirements and changes in the network environment, mainly manifested in its physical elements The variability of the number, the adjustability of the structural relationship and the dynamic configurability of the structural form. Evolvability enables Internet-based software systems to have the ability to adapt to open, dynamic and changeable environments; 5) Polymorphism, which means that the effects of Internet-based software systems reflect compatible multi-objectives. It can meet a variety of compatible target forms in a dynamically changing network environment according to some basic synergy principles. Polymorphism makes Internet-structured software systems have a certain degree of flexibility and the ability to meet individual needs in the network environment.

The realization of the above-mentioned Internet-structured software features often requires software modification in the running state to ensure or improve quality, optimize or add new functions. Classical software engineering methods and techniques emphasize modifying software in the development state, and do not support direct modification of software in the running state.

Correspondingly, system software such as programming languages, operating systems, and middleware provide a common main mechanism for operating state monitoring and control applications—computational reflection (reflection for short). Based on computational reflection, various development frameworks and testing frameworks can be implemented to improve the efficiency of developers in code development, testing, and even deployment. In the computer field, B.Smith gave a general definition of reflectivity: reflectivity is the ability of an entity to describe, manipulate and process the entity itself in the same way as it describes, manipulates and processes the main problem domains faced by the entity . This definition is subsequently interpreted as: reflexivity is the ability of a program to manipulate a set of data at runtime. This set of data describes the running status of the program. Manipulation has two meanings: 1) Monitoring (Introspection), the program can observe and reasoning about its own state; 2) control (Intercession), the program can change its own operation or semantics. Both of these aspects need to be able to encode the state of program execution into data, and providing this encoding is called reflection. In other words, reflection actually maps the running state of the program into a set of operable data. The former part constitutes the base-level entity, and the latter part constitutes the meta-level entity, and the causal relationship between the base-level entity and the meta-level entity is maintained. According to different base entities, computational reflection is mainly divided into structural reflection and behavioral reflection. The basic entity of structural reflection is the current program and its abstract data type (which can be regarded as the state of the application), while the basic entity of behavioral reflection is the execution behavior of the current program and the data required for its execution (which can be regarded as the behavior of the application) .

Structural reflection refers to the ability of a programming language to provide reflection on the current program and its abstract data types. It exists naturally because it is similar to the ability of a programming language framework (runtime or framework), and is an inherent ability of most programming language frameworks.

Behavior reflection refers to the ability of a programming language to provide its own execution semantics and the data reflection required for its execution, that is, the programming language framework itself needs to be reflected. Behavior reflection faces two challenges in monitoring and control: first, it needs complete Describe the existing application behavior, that is, monitor the execution of the application. The execution of an application can be regarded as a collection of runtime activities. The finer the granularity of the activities, the richer the monitoring information will be. The more resources the monitoring function will occupy, the more serious the resource competition between it and the business logic will be. At this time, the complexity and scale of application behavior monitoring become the primary challenge for terminal application behavior reflection. Second, the existing programming language and the behavior reflection of system software such as operating system and middleware do not support instruction-level behavior control. The root cause is the complex data and control dependencies contained in the instruction sequence. Control becomes the main difficulty of terminal application behavior reflection.

Contents of the invention

The main purpose of the present invention is to provide a method for constructing a runtime model of terminal application behavior, overcome the first challenge above, and realize complete monitoring of terminal application runtime behavior.

The present invention is achieved through the following technical solutions:

In order to solve the above technical problems, the present invention proposes a method for constructing a runtime model of terminal application behavior, the runtime model includes a runtime stack model and a runtime heap model, and the method includes constructing a runtime model of the terminal application behavior Steps of a runtime stack model and a step of constructing a runtime heap model of the behavior of the terminal application;

The step of constructing the runtime stack model of the terminal application behavior includes:

When the terminal application is running, obtain the code actually executed in the memory of the terminal application, and abstract the code actually executed to generate a control flow graph;

For the control flow graph, input the control flow graph to be monitored into a preset behavior interpreter;

Using the behavior interpreter to interpret and execute the control flow graph that needs to be monitored, and generate stack activities when the terminal application is running;

When the terminal application is running, generate a dependency between the control flows of the stack activities, and obtain a runtime stack model of the terminal application behavior;

The step of constructing the runtime heap model of the terminal application behavior includes:

When the terminal application is running, generate an initial state of the heap;

A heap operation activity is generated to obtain a runtime heap model of the terminal application behavior.

Further, the method includes a class filter and an activity type filter; wherein, the class filter is based on a coarse-grained screening of a regular match between a package and a class name, and is used to remove program activities that developers do not care about; the activity type Filters are based on fine-grained filtering of activity types and are used to remove activity types that developers do not care about.

Further, the activity type of the stack activity includes method start and method end, field read, array read and synchronization instruction;

Using the behavior interpreter to interpret and execute the control flow graph that needs to be monitored, the step of generating the stack activity when the terminal application is running includes:

Using a behavior interpreter capable of monitoring the application behavior of the terminal application to interpret and execute the control flow graph that needs to be monitored, to obtain the running activities of the terminal application;

According to the concerned class, use the class filter to perform coarse-grained screening on the activities of the terminal application during runtime, and generate stack activities caused by the class;

For the activity type of the stack activity, the activity type filter is used to perform fine-grained screening on the stack activity.

Further, the step of constructing the runtime heap model of the terminal application behavior includes:

The running activities of the terminal application include instantiation activities, modification activities and recycling activities.

Further, the activity type of the heap operation activity includes object instantiation, array instantiation, object field writing, array element writing, clearing activity and compression activity;

The steps of generating heap operation activities include:

According to the concerned class, use the class filter to perform coarse-grained screening on the activities of the terminal application during runtime, and generate heap operation activities caused by the class;

For the activity type of the heap operation activity, the activity type filter is used to perform fine-grained screening on the heap operation activity.

Further, the dependencies include synchronization dependencies and communication dependencies.

Furthermore, when generating synchronization dependencies between control flows, for the case where the end of one method depends on the end of another method, use the timestamp to find matching activities in other threads from the back to the front, and if found, it corresponds to A synchronization dependency. For the case where the start of an activity depends on the end of another activity, the current thread is checked first. If the activity is the first activity executed in the current thread, the activity is dependent on the end of another thread. activity, otherwise the activity is just a normal method call and does not depend on another thread's activity.

Further, when generating the dependencies between the control flows of the stack activities, summarize all the classes related to the communication dependencies between the activities, and use the related methods of the classes and the methods related to the thread dependencies as the generated communication dependencies knowledge base.

Further, when the runtime model is generated, the activity sequence in the runtime model is stored in a buffer with a configurable size, and when the number of activities exceeds a preset value, the activities in the buffer are sequenced and persist to local storage.

Further, the runtime heap model is expressed in the form of Backus-Naur Form.

Compared with the prior art, the present invention uses a behavior interpreter to generate a complete, accurate, and detailed application behavior statement, that is, a runtime model of the terminal application application behavior, which overcomes the dynamic, changeable, and difficult-to-control problems of the prior art. The lack of monitoring of terminal application behavior by the application runtime environment enables flexible and complete monitoring of terminal application behavior, and provides technical support for the subsequent realization of command-level control of terminal application behavior.

Description of drawings

FIG. 1 is an existing 3G radio resource control state machine;

Fig. 2 (a) is the network request control flow schematic diagram before merging in the example of a network request merging;

Fig. 2 (b) is a network request control flow diagram after merging in an example of network request merging;

Figure 3 is an example of communication dependencies between threads - a schematic diagram of the producer-consumer model;

FIG. 4 is a flow chart of steps of a method for constructing a runtime model of terminal application behavior in the present invention;

Fig. 5 is an example of Android multi-thread programming;

Figure 6 is an example of dependencies between multi-threaded programming;

Figure 7(a) is the heap object before execution;

Figure 7(b) is the heap object after execution;

Fig. 8 is a schematic diagram of the architecture of the reflectall model generation subsystem of the present invention;

Fig. 9 is the structural representation of the interface operating subsystem of the example Reflectall of the present invention;

Figure 10(a) is the experimental result on the open source application set;

Figure 10(b) is the experimental result on the closed-source application set;

Figure 11 is a comparison of application startup time results when Reflectall and Emma generate code coverage reports.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the embodiments and accompanying drawings.

In order to better understand the technical problems of this application, the present invention adopts the application function evolution scenarios of two typical cases for analysis, so as to clarify the root cause of the inapplicability of the existing behavioral reflection.

Case number one:

With the development of smart phones, terminal mobile applications increasingly rely on software and hardware resources provided by the cloud to provide better services. However, the communication between the cloud and the terminal consumes a lot of power. Networked applications (such as weather, email, news, etc.) present the typical component-based characteristics of Internet architecture software, and use the network to realize the communication between the terminal and the components of the cloud. Especially in the 3G/4G environment, networked applications use the network to obtain corresponding push messages in the background for a long time and at intervals. This kind of long-term and intermittent message push has brought great pressure on the battery life of smartphones with limited battery capacity. 3G and 4G are currently the mainstream mobile cellular networks, and their power consumption characteristics are more complicated. On the one hand, because the mobility of the cellular network is strong, a mobile device may quickly switch to a different cellular network base station as the physical location moves. Therefore, it is not possible for a cellular network base station to assign a channel to a mobile device all the time. On the other hand, due to the limited battery life of mobile devices, connecting to a cellular network base station for a long time will greatly increase its power consumption and affect battery life. Therefore, in the cellular network standard, the state of the radio resource control (Radio Resource Control, RRC) module is further specified.

Taking the 3G network module in the mobile device as an example, it contains three states in total, as shown in FIG. 1 .

(1) IDLE: It is the idle state. In this state, the power consumption of the 3G module is the lowest, and it cannot send or receive any data. In this state, if data is to be sent or received, it will transfer to the CELL_DCH state.

(2) CELL_DCH: In this state, the bandwidth of the 3G module reaches the maximum. At this time, data transmission can be performed at the maximum rate, and its power consumption is also the maximum. If there is still no data transmission for a period of time, it will transfer to the CELL_FACH state. According to the settings of different operators, the time for continuous operation in the CELL_DCH state is usually 5 seconds to 10 seconds.

(3) CELL_FACH: In this state, the power consumption of the 3G module is 50% less than that of CELL_DCH. At the same time, in this state, its network transmission rate is also low. If in this state, the data sent or received is greater than a certain threshold, it will re-transfer to the CELL_DCH state. And if no data is sent or received in the CELL_FACH state for a period of time, it will transfer to the IDLE state. Generally speaking, this period of time is usually 10 seconds to 15 seconds.

Figure 2 shows an example of network request coalescing. Figure 2(a) shows the power consumption of the network request and the wireless communication module before merging, the horizontal axis is time, the upper half is the power consumption of the wireless communication module; the dotted line in the lower half is the thread that initiated the two network requests; The solid line in the lower part is its control flow. First, a background news push thread wakes up the thread responsible for sending network requests ①; after the thread is woken up, it initiates a network request ②. At this time, the power consumption of the wireless communication module also changes from the low power consumption in the IDLE state to It is high power consumption in the CELL_DCH state; when the entire request is completed, the thread responsible for sending the network request will return the result to the news push thread ③, although the wireless communication module does not receive or send data at this time, it will still maintain high power consumption The power consumption of the wireless communication module starting from this point is called "tail time power consumption", which corresponds to the slash part used in Figure 2(a); after the news push thread receives the returned result ④, it checks the result Process and prompt on the notification bar ⑤. After another period of time, another version update thread also executed similar logic ⑥ and sent a network request. As shown in Figure 2(a), since the two network requests are separated by dozens of seconds, the wireless communication module is woken up twice, so there are also two corresponding "tail times", which leads to additional network requests. energy consumption.

For Android applications, a large part of background requests can be delayed for tens of seconds, or even two or three minutes, without affecting the user experience. For example, the above-mentioned news push, version update push, etc. For these network requests, if they are combined in the time dimension, that is, two requests are sent at the same time instead of being sent with an interval of tens of seconds, the network power consumption of the "tail time" can be reduced. Fig. 2(b) shows the control flow and the power consumption of the wireless communication module after the two requests in Fig. 2(a) are merged. First of all, after the thread responsible for sending network requests is awakened by the news push thread, it does not directly send network requests, but enters a waiting state⑦. After a period of time, another network request thread is woken up by the background update push thread, and at the same time, it also enters a waiting state⑧. After the waiting state is over⑨, the two threads send network requests at the same time, and the corresponding wireless communication module is only woken up once. As shown in Figure 2(b), the power consumption of the combined network request is much smaller than that of the network request before the combination.

In order to achieve network request merging, 1) a network request scheduling mechanism is needed, that is, the network requests that were originally sent directly can be delayed; 2) a network request scheduling algorithm is to find out the requests that can be delayed scheduling, and at the same time Use the scheduling mechanism for delayed sending. Structural reflection can be used to automatically refactor the network request execution logic of mobile applications, and build the scheduling mechanism into the application. However, this requires developers of different applications to use the same automatic refactoring framework, and all applications need to be recompiled, deployed, and run. This is obviously unrealistic for a large number of closed-source applications belonging to different application developers.

Case two:

With the popularity of WeChat, WeChat is not just a simple communication application, it has also become an essential tool for work communication; it has given birth to the "WeChat business" that uses WeChat Moments and official accounts for marketing; it has become the largest self- Media publishing platform. The core of WeChat is a communication tool, and its function is mainly to satisfy ordinary users. Even so, it struggles to meet the specific needs of the average user. For example, as WeChat is used for a longer period of time, its cached chat log files are also getting larger and larger. For ordinary users, it is difficult to manage their own chat logs. Furthermore, it is difficult for WeChat to meet the specific needs of special groups such as WeChat merchants and self-media people. In order to realize the open sharing of data and functions in the WeChat application, it is necessary to convert the user-oriented user interface interface into an interoperable programmable interface. Generally speaking, for a user-oriented user interface interface, the starting point of its execution lies in operations such as clicking, dragging, and inputting elements of the user interface. After some logical processing, access to external resources in the form of network requests, database queries, and file reading and writing, to obtain corresponding data or realize corresponding functions. In this processing flow, most of the logic is similar to the execution logic of the interoperability-oriented programmable interface, but the starting point of its execution is different. However, the granularity of existing behavioral reflection monitoring and control is method level. Based on the existing behavioral reflection, it is difficult to convert the user-oriented user interface interface into an interoperable programmable interface by inserting some execution logic into the execution flow of the existing application: the existing functions can correspond to the running A set of program activities at the time, the behavior at the granularity of the method reflects the limited monitoring content, and it is impossible to monitor the execution of the instructions in the method, and then it cannot be controlled. This has led to the fact that existing solutions are often based on existing codes and documents. For a development team, the flow of developers, lack of documents, and even non-standard source code comments will make iterative development of mobile applications change. It is difficult to carry out.

From the analysis of the above two cases, it can be seen that the root cause of the difficulty in realizing the mobile application interoperability interface is that the existing work lacks a complete and detailed description of the application behavior, and at the same time, there is no control over the self-description of the instruction granularity. Methods. Therefore, whether a runtime model that fully describes the application behavior and is operable can be given becomes the difficulty and the key to solve the problem of the present invention.

In view of the above technical problems, an embodiment of the present invention proposes a method for constructing a runtime model of terminal application behavior, and the runtime model includes a runtime stack model and a runtime heap model.

After the application runs in the operating system, it can be regarded as one or more processes, and the operating system loads the executable files required by the mobile application into the memory and starts execution. In general, the memory occupied by a process can be divided into three areas:

Code segment: a memory area that stores the execution code, which has a read-only attribute;

Heap area: It can be divided into a memory area (data segment) for storing global variables and a memory area for dynamic allocation during process running. For example, in the object-oriented programming language Java, creating a new object by a thread is equivalent to A piece of memory is applied for in the heap area;

Stack area: used for temporary storage of local variables, etc. For example, in the object-oriented programming language Java, when a thread calls a method, it will apply for a new frame (frame), which stores data such as parameters required by the method.

After careful research by the inventor, it is found that when the terminal application is running, the execution of the code segment will cause changes in the memory data in the heap area and the stack area. The runtime model of the application needs to be able to reflect the following: 1) The execution of the code: during development, the code of the mobile application can be abstracted as a control flow graph, and corresponding to the runtime, the execution of the code can be abstracted as One or more paths of the control flow graph; 2) Changes in memory data (such as the heap area): During development, developers will design various data structures to represent the application's data model (Data Model), while at runtime , the execution of the code causes the creation, modification, and deletion of instances of these data structures, that is, the allocation and modification operations corresponding to a set of memory. From the perspective of memory area, the most important area affected by program execution is the stack area and heap area of memory. The path in the control flow graph in 1) can be regarded as a description of the stack change, while 2) mainly reflects the change of the heap area data.

Therefore, the application run-time model constructed by the present invention includes a run-time stack model describing stack changes and a run-time heap model describing heap changes. The runtime stack model also includes the acquisition of codes, so that the memory occupied by a process is completely divided into three areas. Through the runtime stack model of the embodiment of the present invention, it is possible to know the code execution status of the mobile application at any time; and through the runtime heap model, it is possible to know the object data state on which the code execution depends at any time.

runtime stack model

The control flow graph is a directed graph G=<B, P>;

Among them, B={b ₁ , b ₂ ,..., b _n } is a basic block;

is the control flow path;

For any p _i =(b _i1 , b _i2 ), p _i ∈ P is executed if and only if b _i2 is possible after b _i1 . At runtime, the control flow graph will be instantiated into one or more control flows, and the basic blocks will be executed according to the path in the control flow graph. The present invention calls the basic blocks executed at a certain moment as activities, and then the runtime stack model within a period of time is composed of a control flow graph, one or more control flows, and a group of activity sequences. When the granularity of the basic block is the instruction granularity, the active sequence is the instruction execution sequence. The formal definition of the runtime stack model of the present invention is given below.

Define the runtime stack model as a set of activities M=<G, T, A, I, E> of one or more control flows occurring over a period of time,

Among them, G=<B, P> is the control flow graph, T={t ₁ , t ₂ ,…,t _n } is a set of time instants, I={i ₁ , i ₂ ,…,i _n }, representing t The heap status of the program from time ₁ to t _n .

Let F={f ₁ , f ₂ ,...,f _n } be a group of control flows, then A=F×I×T×B is a collection of activities that occur within a period of time, Represents a collection of contexts in which two activities occur.

The run-time stack model can be viewed as a collection of multiple paths in the control flow graph, therefore, edges in the run-time stack model must have corresponding edges in the control flow graph. which is: Where a _i (f _i1 , t _i2 , b _i3 ), a _j = (f _j1 , t _j2 , b _j3 ) a _j = (f _j1 , t _j2 , b _j3 ), there is (b _i3 , b _j3 )∈ p. In addition, the edge of the runtime stack model represents the context of two activities. For two activities in the same control flow, there is a sequence relationship in time; for two activities in different control flows, if The presence of an edge indicates that there is also a dependency between the two activities.

In the same control flow, if there are two activities that have the relationship of happening before and after, it is impossible for any other activity to happen between these two activities in the same control flow, that is where a _i = (f _i1 , t _i2 , b _i3 ), a _j = (f _j1 , t _j2 , b _j3 ), if f _i1 ≠ f _j1 , then

In different control flows, if two activities have a occurrence relationship, then for the control flow where the latter activity is located, after the moment when the previous activity occurs, other activities can occur first. Where a _i =(f _i1 , t _i2 , b _i3 ), a _j =(f _j1 , t _j2 , b _j3 ), if f _i1 ≠f _j1 , then t _i2 <t _j2 .

Define program activity a _j synchronization depends on program activity a _i , if the start or end of a _j is determined by the execution of a _i , generally, and a _i is often some thread synchronization operation. It is said that the communication of a _j depends on a _i , if a certain data dependency of a _j is generated by the activity of a _i . Taking the object-oriented programming language Java as an example, the granularity of the basic block is the granularity of the basic block of the source code. Each control flow of the execution stack model corresponds to the execution sequence of a Java thread. There are six states in thread state transition:

Creation: The thread object is just created and is in this state before it starts;

Running: The thread is in the running state, and the thread in this state may wait for some system resources, such as CPU;

Blocking: The thread is waiting for a monitor lock (Monitor Lock). For example, when the thread enters the method or code block modified by the synchronized keyword, the thread will enter the blocked state;

Waiting/timed waiting: The thread is waiting, for example, when the thread calls the wait method of an object to enter the waiting state. When the notify method of the object is used, the thread will re-enter the running state;

Death: When the execution of the run method of a thread ends, it will enter the death state.

From the above state transitions, it can be found that in some cases, a thread in the running state can wake up another thread in the non-running state to enter the running state. The present invention calls this relationship between threads a synchronization dependency. When these inter-thread wakeups occur, corresponding to the runtime stack model, there is a cross-thread (cross-control flow) edge between the activities of the running thread and the activities of the non-running thread entering the running state. From the Java language level, these thread dependencies can be classified into four categories, as shown in Table 1.

Table 1: Classification of synchronization dependencies at the Java language level

In Table 1, the activities of each running thread correspond to the activities of non-running threads. Therefore, the inter-thread dependencies in Table 1 are called synchronization dependencies. Based on the state transitions of the above threads, Java provides a variety of multi-threaded programming libraries to support, for example, java.util.concurrent provides read-write locks, reentrant locks, blocking locks, and thread pools.

Figure 3 shows an example of communication dependencies between threads - producer-consumer pattern. In this example, the Task class represents computing tasks; the static field tasks represents the pending task queue; the postTask method represents generating and submitting tasks; the handleTask method represents processing tasks. As shown in Figure 3, there are two threads: 1) thread 1 represents the producer thread, which will submit tasks to the pending task queue; 2) thread 2 represents the consumer thread, which will check the pending task queue every once in a while, and handle the corresponding tasks. In this example, there is no synchronization dependency between the producer thread and the consumer thread - the consumer thread automatically changes from the timing waiting state to the running state every once in a while, but there is a communication dependency - if the production If the consumer thread does not submit the task, the task.run method of the consumer thread will not be called.

It can be found from the above examples that the generation of activity relations in the runtime stack model must depend on the corresponding data at runtime. In classic data flow analysis, the data flow analysis algorithm calculates the data flow equation according to the structure of the control flow graph, and iterates to a stable point. Therefore, in addition to the above-mentioned runtime stack model, the runtime model of the application also needs a runtime heap model that describes the data state changes in the memory heap area.

runtime heap model

The classic data flow diagram is often used in the requirements analysis phase. The software uses the data flow graph to decompose the software system to be developed layer by layer from abstraction to concrete. The data flow graph is a directed graph, which contains two different types of edges and a variety of different nodes to describe data starting from an initial node, performing layer-by-layer calculations, and finally obtaining the final result. At runtime, a node in the data flow graph essentially corresponds to a set of memory data changes. Therefore, the heap model of the behavior runtime model of the application of the present invention focuses on the change of memory data, rather than the changed operation. The runtime heap model described in the present invention only models the memory heap area when the application is running from the perspective of memory data changes.

The runtime heap model is a set M=<D, A, T, R> of a set of initial values of memory data and heap memory modification activities that occur within a period of time;

Among them, D={d ₁ , d ₂ ,..., d _n }, is the initial value of a group of memory addresses, A={i ₁ , i ₂ ,..., i _n }, is the activity that causes the memory data to change, T ={t ₁ , t ₂ , . . . , t _n }, which is the time stamp.

For different object-oriented programming languages, they will provide different application programming interfaces to realize the dynamic allocation and recovery of memory. For example, the C/C++ language realizes memory allocation and recovery by providing malloc and free functions in the standard library functions; while the Java language can create new objects through the new keyword to achieve memory allocation, and through the automatic garbage collection mechanism, Realize the recovery of memory.

Aiming at the technical problem of the present invention, how to construct the above runtime model of the embodiment of the present invention will be described in detail next.

Referring to FIG. 4 , it shows a flow chart of steps of a method for constructing a runtime model of a terminal application behavior according to the present invention, the method including the steps of constructing a runtime stack model of the terminal application behavior and constructing the terminal application behavior The steps of the runtime heap model.

The step of constructing the runtime stack model of the terminal application behavior may specifically include:

Step S401: when the terminal application is running, obtain the actually executed code in the memory of the terminal application, and abstract the actually executed code to generate a control flow graph;

Step S402: For the control flow graph, input the control flow graph to be monitored into a preset behavior interpreter;

Step S403: using the behavior interpreter to interpret and execute the control flow graph that needs to be monitored, and generate the stack activity when the terminal application is running;

Step S404: When the terminal application is running, generate dependencies between control flows of the stack activities, and obtain a runtime stack model of the terminal application behavior;

In the embodiment of the present invention, building the runtime stack model includes the following three basic elements: 1) Control flow graph: contains all possible activities and all possible activity relationships, and is the source code of the program, or the abstraction of the intermediate code Represents; 2) a group of activities that occur at runtime, that is, a path in the control flow graph, which can be regarded as a group of nodes in the stack model; 3) the relationship between activities that occur at runtime, that is, the edges of the stack model.

The construction of the stack model needs to focus on solving three challenges: First, due to technologies such as compilation optimization and runtime just-in-time compilation, the source code of the application and the bytecode generated by compilation may be different from the code segment in the runtime memory. The control flow graph and runtime activities can be correctly mapped; second, how to generate activities of different granularities to describe the change of the complex application running state; third, because current applications use a lot of multi-threaded compilation to ensure the response speed of the interface, To improve user experience, how to generate dependencies between runtime control flows. In response to the above three challenges, the first step of the embodiment of the present invention is to abstract the currently executed code by obtaining the code actually executed in the memory at runtime, so as to ensure the accurate mapping between the control flow graph and the runtime activities. The second step proposes a behavior interpreter, which takes the control flow graph generated in the previous step as input, and interprets and executes it. The third step is to explain the activities of generating application runtime during execution; and the last step of model generation is to generate dependencies between control flows at runtime.

Below, a further overview of the steps for generating the runtime stack model is given.

1. Control flow graph generation. During the development process of the application, since the installation package release contains the compiled intermediate code of the application, for the purpose of protection, the application will use various obfuscation tools to generate the intermediate code, such as the dex bytecode under Android , for confusion. This makes it difficult to map the directly provided source code with the activities performed by the application at runtime. These obfuscated codes will be loaded and executed through the application runtime environment. For example, the Dex bytecode in an Android application will be executed in the Android Runtime (ART). The present invention obtains the bytecode of the application by modifying the running time of the application. This method can bring two advantages. First, there is no need to provide matching intermediate code or source code, which improves the practicability of the method. Second, the intermediate code generated when the application is running can ensure consistency with the executed activities. Thus, the matching between the control flow graph and the control flow at runtime is ensured.

Specifically, the generation of the control flow graph:

The boundary of the basic block is derived according to the instruction category. An instruction is the beginning of a basic block if and only if: 1) it is the first instruction of a method or 2) there is an instruction that may jump to the current instruction. And an instruction is the end of a basic block if and only if: 1) it is a method return, such as return, throw instruction; or 2) it is a jump instruction, such as if, goto, or the instruction may throw an exception . After defining the start and end of the basic block, the control flow graph generation algorithm of the present invention is divided into the following three steps:

Calculate the target address of all jump instructions (including explicit jumps and exception jumps), and mark the instruction at this address as an instruction that can be used as the start of a basic block.

Initialize the basic block queue to be empty, and traverse each instruction from low to high, if the instruction is the beginning of the basic block, or the current basic block is empty, create a new basic block, use it as the current basic block, and put it in the basic block The end of the block queue; if the instruction is the end of the basic block, put it into the current basic block, and create a new basic block as the current basic block, and put it at the end of the basic block queue.

Traverse the entire basic block queue to establish the predecessor and successor relationship of the basic block: if the last instruction of a basic block is a jumpable instruction, add a directed edge between the basic block and the basic block of the jump target; if If a basic block is not a return or goto instruction, add a directed edge to the next basic block in the queue.

Second, on-demand redistribution of the execution of the control flow graph, and the generation of the activities of the application runtime by the behavioral interpreter. When the application is running, each thread corresponds to a control flow, and each control flow can be regarded as a set of ordered activities. This set of activities can be regarded as a path of the control flow graph generated in the previous step. Therefore, the present invention proposes a behavioral interpreter suitable for monitoring program execution. According to the configuration, the control flow graph that needs to be monitored is assigned to the behavior interpreter for execution. If the execution of each instruction corresponds to an activity, this group of instruction sequences will become extremely large and difficult to handle: 1. Numerical calculation statements are difficult to correspond to semantics; 2. A large number of activities generated by program loops will obliterate the real processing logic. Therefore, the present invention divides activities into numerical calculation, branch control, method invocation, etc., and implements an activity filter that provides activity screening of various granularities in the behavior interpreter, so as to generate a suitable stack model.

In the construction method of the embodiment of the present invention, a class filter and an activity type filter are included; wherein, the class filter is based on a coarse-grained screening of a regular match between a package and a class name, and is used to remove program activities that developers do not care about; The activity type filter is based on fine-grained filtering of activity types, and is used to remove activity types that are not concerned by developers.

Wherein, the activity type of the stack activity includes method start and method end, field read, array read and synchronization instruction; based on the above activity type, the implementation method of step S403 includes:

Using a behavior interpreter capable of monitoring the application behavior of the terminal application to interpret and execute the control flow graph that needs to be monitored, to obtain the running activities of the terminal application;

According to the concerned class, use the class filter to perform coarse-grained screening on the activities of the terminal application during runtime, and generate stack activities caused by the class;

For the activity type of the stack activity, the activity type filter is used to perform fine-grained screening on the stack activity.

The embodiment of the present invention can generate a required stack model by flexibly specifying specific packages, classes and instruction types, thereby improving usability.

In order to improve the accuracy of constructing the model, the invention regards the beginning and the end of executing the method calling instruction as activities and records them. From the method call of Java, its call shows a tree structure: for a certain method call, multiple method calls may occur during the execution process. Therefore, in order to ensure that the generated sequence can be restored to this tree structure, the subscript s in the present invention indicates the activity starting from the method call, and the subscript e indicates the activity ending the method call. For the two program execution situations of the above example, there will be two different sequences:

1) If calculate is called in doInBackground, the sequence is d _s →c _s →c _e →c _s →c _e →d _e ;

2) If there is a recursive call of calculate itself, the sequence is d _s →c _s →c _s →c _e →c _e →d _e .

A call tree construction algorithm may be used to reconstruct the generated sequence of activities into a tree-structured method call. The process of the algorithm is actually the process of simulating the execution flow of the Java virtual machine. At the beginning of the algorithm, the activities of each thread correspond to an actions object. For each thread, two data structures are maintained: 1) a sub-control flow queue that has been executed; 2) a function stack for the execution of the current control flow. Traverse each activity in actions in order, and make the following judgments:

If there is no current control flow, one is instantiated and pushed onto the function stack.

If the current activity is a method start type, instantiate a new sub-control flow, push the newly instantiated sub-control flow onto the function stack, and add it to the activity queue of the current control flow. Finally, set the current control flow to the sub-control flow that was just instantiated.

If the current activity is a method end type, pop the stack. If the function stack is empty after popping the stack, it means that the sub-control flow of the current thread has been executed and can be added to the executed sub-control flow queue; if the function stack is not empty, the current control flow is set to function The child control flow at the top of the stack.

Otherwise push the current activity onto the activity queue of the child control flow.

Similar to method call instructions, other types of instructions can have two activities: instruction start execution and execution end. Because these instructions are atomic, that is, in the same thread, there is no other activity between the beginning and the end of the instruction execution, so for these types of instructions, only the activity that the instruction starts to execute is required.

In a specific implementation, the runtime activity representation implementation can have a storage form: it can be an object in memory, or a persistent binary file or an ASIC II file. In the present invention, the runtime heap model can be expressed in the form of Backus-Naur Form.

The present invention realizes this scalability through an active serialization and deserialization mechanism. When the runtime model is generated, the activity sequence in the runtime model is stored in a buffer with a configurable size. When the number of activities exceeds the preset, the activities in the buffer are serialized and persisted to the local storage .

Third, the generation of dependencies between control flows. Multithreaded programming has become an important part of Android application development. Utilizing multi-thread programming can realize efficient response of user interface and parallel acceleration of multiple computing tasks. Thread synchronization and mutual awakening in multithreaded programming (called thread dependencies) can be abstracted as edges between control flows in the stack model. The thread dependency is a relationship related to time: at a certain moment, the main thread can send computing tasks to the background thread, and the activities performed for the background thread at this time depend on the activities of the main thread; and at the next moment, the background thread completes the computing tasks After that, notify the main thread to update the interface; at this time, the activities performed by the main thread depend on the activities of the background thread. Therefore, the present invention classifies these inter-thread dependencies and processes different types of dependencies to generate them at runtime.

In the embodiment of the present invention, the dependencies include synchronization dependencies and communication dependencies. Threads use the thread state transfer related methods provided in the Java language specification, such as Thread.join, Object.wait, Object.notify, etc. to realize the collaboration between multiple threads. The present invention calls the dependency between these threads as synchronization dependency. . However, if objects are used between threads to realize coordination among multiple threads, the present invention refers to the dependency between these threads as communication dependency. In actual development, application developers will reuse various multi-threaded programming classes provided by the framework layer to improve development efficiency. Although the framework layer provides application programming interfaces with good semantics for classes in the application layer and shields the implementation details, in order to ensure the performance and robustness of the framework, the implementation is often more complicated. Programs implemented using these programming frameworks may be either synchronization dependencies or communication dependencies between runtime threads.

Take the BackgroundTask.execute method call in Figure 5 from the beginning to the end of the onPostExecute method call as an example, there are two active threads globally, and there are synchronization dependencies and communication dependencies between them. The method call of this process is shown in Figure 6: the upper and lower axes in the figure respectively represent the method stack of the foreground thread and the background thread over time; the boxes in the figure represent the methods, and the gray boxes represent the methods of the framework layer , the white box represents the method of the application layer, that is, the method implemented by the application developer; the arrows in the figure represent the dependencies between threads, where the solid arrows represent synchronization dependencies, and the dashed arrows represent communication dependencies. In the method call process shown in Figure 6, the BackgroundTask.execute method will call the ThreadPoolExecutor.execute method during execution (activity ①), and then call the start method of the background thread object (activity ②), which will further cause the background thread to run Method call (activity ③). After the run method of the background thread starts to execute, after layers of calls, the BackgroundTask.doInBackground method (activity ④) will eventually be called. During the execution of this method, in addition to calling the calculate method to perform calculation tasks, AsyncTask.publishProgress will also be called method (activity ⑤), so that the foreground thread calls the onProgressUpdated method (activity ⑥) to update the interface. Afterwards, after the background thread finishes the calculation task, it will notify the foreground process again that the current task has ended in a similar way. Among them, activity ② and activity ③ are synchronization dependencies, and activities ⑤ and activities ⑥ are communication dependencies.

Generation of synchronous dependencies:

In order to realize the generation of synchronous dependencies, methods related to synchronous dependencies in Java will be considered as activities that need to be collected. In this way, the runtime stack model can collect various activities related to synchronization dependencies as shown in Table 1.

For two activities that have synchronization dependencies, the activity that occurs later may be the end of a method or the start of a method. Accordingly, synchronization dependencies can be divided into two types and processed separately:

For the case where the end of one method depends on the end of another method, use the timestamp to find matching activities in other threads from the back to the front. If found, it corresponds to a synchronization dependency. For example, the end of Thread.join depends on the end of Thread.run; the end of Object.wait depends on the end of Object.notify. For methods such as Thread.join or Object.wait to end activities, you can use the timestamp to find other Matchable activities in the thread. If found, it corresponds to a sync dependency.

When generating synchronization dependencies between control flows, when the end of one method depends on the end of another method, use the timestamp to find matching activities in other threads from the back to the front. If found, it corresponds to a synchronization dependency. Relationship; for example, the end of Thread.join depends on the end of Thread.run; the end of Object.wait depends on the end of Object.notify. For methods such as Thread.join or Object.wait to end activities, timestamps can be used from back to front Look for matching activity in other threads. If found, it corresponds to a sync dependency.

For the case where the start of an activity depends on the end of another activity, first check the current thread, if the activity is the first executed activity in the current thread, then the activity depends on another thread to end the activity, otherwise the Activities are just normal method calls and do not depend on another thread's activity. For example, the beginning of Thread.run depends on the end of Thread.start, because in Java, the beginning of an activity (that is, the call of a certain method) can be performed any number of times anywhere, including the Thread.run method. Therefore, to determine whether a Thread.run method call depends on the Thread.start method call, you cannot directly search for a match based on the timestamp from the back, you need to check the current Thread.run first: if the activity is The first activity to execute, it depends on another thread Thread.start to end the activity, otherwise it is just a normal method call and does not depend on the activity of another thread.

Generation of communication dependencies:

The thread is not based on the method provided by Java that can realize thread state transfer and realize the coordination among multiple threads. The present invention refers to the dependency relationship between these threads as communication dependency.

Taking activities ⑤ and ⑥ in Figure 6 as an example, the specific implementation is based on the next method and enqueueMessage method of MessageQueue. During this process, if there are still elements waiting to be processed in the pending queue of the foreground thread, the enqueueMessage method triggered by activity ⑤ will only add the current task to the queue, and will not explicitly wake up the foreground thread. But logically, it can be considered that for a MessageQueue object, the Message object returned by its next method will be passed into the dispatchMessage method by the Handler as a parameter, so it can be considered that the end of the next method of the MessageQueue depends on MessageQueue.enqueueMessage , and the dependency takes the parameter Message as the matching object instead of MessageQueue.

When generating communication dependencies between control flows, all classes related to communication dependencies between activities are summarized, and the related methods of these classes and methods related to thread dependencies are used as a knowledge base for generating communication dependencies. The knowledge base can also support the customization of the application.

Referring to FIG. 4, the step of constructing the runtime heap model of the terminal application behavior may specifically include:

Step S405: When the terminal application is running, generate an initial state of the heap;

Step S406: Generate a heap operation activity to obtain a runtime heap model of the terminal application behavior.

In the embodiment of the present invention, the runtime heap model includes the following basic elements: 1) the initial state of a heap; 2) a group of activities that affect the data in the heap during runtime. The invention first provides a description method of the initial state of the heap area, and generates the initial state of the heap data conforming to the representation at runtime. Secondly, the invention provides a description method for heap operation activities, and constructs the activities in the heap model during runtime. Finally, the BNF representation of the initial state of the heap area and the operation activities of the heap is given.

Below, a further overview of the steps involved in generating the runtime heap model is given.

One is to generate the initial state of the heap area. The initial state of the heap is the state of the heap data at the beginning. In the Java virtual machine specification, only the simplest description is given for the heap area: the heap is the area used to analyze all class instances and arrays at runtime, and this area is managed by an automatic storage management system (ie, garbage collector) . Objects in the heap are never explicitly reclaimed, but are automatically reclaimed by the garbage collector. The initial state of the heap area can be regarded as a snapshot of the heap area data at a certain moment. Therefore, if other threads continue to execute and perform heap area operations (such as creating objects, performing garbage collection, etc.) etc.), it will destroy the atomicity of the initial state. Therefore, the present invention first provides a BNF representation for describing the initial state of the heap area, and adopts the method of "freezing" the heap area data when generating the initial state of the heap area data, which ensures the atomicity of the initial state generation process.

Second, the generation of activities in the heap model. While the application is running, Java's garbage collector can generate activities to reclaim memory. In addition to these activities, other activities can be considered as a subset of the activities in the runtime stack model. On the one hand, if each operation that affects the data in the heap corresponds to an activity, the number of activities in this group will become extremely large and unmanageable. For example, if there are large file I/O operations in an application, if all operations are recorded in the form of activities, the data volume of activities will not be less than the data volume of large files; on the other hand, similar to the control flow model, it may only Pay attention to the execution of some classes and methods, and generate an excessively large heap model, which is difficult to analyze. The description of activities is extended here to support the description of garbage collection activities, which is similar to the runtime stack model and provides multiple granularity of activity selection and filtering options in order to generate a suitable heap model. The generated heap model describes the changes of the concerned objects in detail. Therefore, the state of the heap objects at any time can be queried by using the time stamp-based heap object state query algorithm.

Next, a specific example is used to introduce the modeling process of the runtime heap model:

The data in the Java heap includes only instantiated objects and arrays. For the application, the object creation may occur in the application layer code or the framework layer code. Therefore, we divide the objects in the application into the application layer and the framework layer. Taking the code implemented in Figure 5 as an example, before triggering the click event, The objects in the heap area are shown in Figure 7(a). Each circle in the figure represents an object, and the lines between the circles represent the reference relationship. The objects related to the application business logic in Figure 7(a) include the display interface FloatActivity, the button Button that can trigger the background calculation task, the pending background task BackgroundTask, the TextView used to display the task calculation result, and the click event listening object OnClickListener. In addition to objects related to business logic, there are many framework layer objects. For example, a MessageQueue object in the framework layer. Implementing background processing tasks can notify the foreground to update. The solid arrow in Figure 7 indicates the reference relationship of the object, that is, if an object A has a field pointing to another object B, there is a directed connection from A to B; the dotted arrow indicates that during the entire event processing, there is There is no reference relationship between objects, and at the end, there is no reference relationship.

During the event triggering process, the following objects will be created: during the execution of the BackgroundTask.execute method, the ThreadPoolExecutor.execute method will be called. At this time, since this object executes the execute method for the first time, the object will create a new Thread object①, as The thread executed in the background; after calling the start method of the background thread object, it will further cause the call of the run method of the background thread and officially start calling the doInBackground method. In this method, in addition to calling the calculate method to perform calculation tasks, the AsyncTask.publishProgress method will also be called. Before executing this method, the incoming parameters will be encapsulated into the newly created Integer[] object②; and in the method During execution, a new Message object ③ will be created and placed in a global MessageQueue queue. When the foreground thread receives the Message and executes onProgressPublished, it will create a StringBuilder object ④ to construct the parameters required by setText, and instantiate a new String object ⑤ through the StringBuilder.toString method. And before the execution of the doInBackground method ends, a new StringBuilder object ⑥ will be created, and the return value String object ⑦ will be calculated. The String object will be encapsulated again into a newly created Message object ⑧, and notify the foreground thread to execute the onPostExecute method. Some steps have been simplified in the above process, and there will be more object creation in actual operation. For example, the Thread object does not directly depend on the BackgroundTask, but indirectly depends on the BackgroundTask object through layer-by-layer encapsulation of FutureTask, Callable and other objects. After the process ends, objects ① to ⑧ may all be recycled in a garbage collection.

In the heap model, the present invention regards the instantiation, field assignment and recycling of each object in Fig. 7(b) as an activity. Similar to the representation of the runtime stack model, the following present invention preferably presents a runtime heap model representation in the form of Backus-Naur Form.

Among them, DataAction is similar to ControlAction described in the key technology of runtime stack model construction. ControlAction is used to describe the executed instructions, and DataAction is used to describe the change of memory data. Number represents a numeric type, which can be a value or a memory address; String represents a character string type. From the above representation, it can be found that the complexity of the model mainly depends on: 1) the number of objects in the initial state; 2) the number of data activities in the heap area.

In the specific implementation of Android, its heap area can be divided into three sub-areas: 1) Application Heap (App Heap), the memory area used when the current application instantiates objects and arrays; 2) Image Heap (Image Heap), loaded with The memory area of the current application image; 3) Incubation heap (Zygote Heap), the memory area where the system classes loaded when the system starts are stored. The initial state described in the present invention mainly focuses on the application heap that changes the most during runtime. For the Dalvik virtual machine and the ART virtual machine on the Android platform, they realize that the state of the current application heap can be saved in the state of a file at any time (heap dump operation). This file is a private memory image format, which can be converted to the hprof format compliant with the J2EE platform through the Android developer tool.

However, based on the current application heap dump, it can only reflect the heap state at a certain moment, and it is difficult to reflect the heap state at any time within a period of time. First of all, performing a heap dump operation needs to suspend all threads, which takes a long time, and the generated files range from tens of megabytes to hundreds of megabytes, so it is difficult to reflect by performing a heap dump operation every once in a while. The state of the heap at any moment in a period of time. Secondly, performing a heap dump operation will not dump those objects recovered by the collector, including those temporary objects generated during execution. However, for an execution process, the generated temporary objects are also very important to the execution of the description process. Important, for example, objects ② to ⑧ in Figure 7 are all temporary objects, and these objects cannot be directly persisted by using the heap dump.

In the embodiment of the present invention, the step of constructing the runtime heap model of the terminal application behavior includes: the runtime activities of the terminal application include instantiation activities, modification activities and recycling activities.

Wherein, the instantiation activity (NewAction), that is, the activity of creating a new object or a new array, may correspond to the execution of instructions such as newInstance and newArray in the bytecode at runtime.

The modification activity (ModifiyAction), that is, the activity of modifying the value of the static field of the class, the field of the object, and the element of the array, can correspond to sput, iput, aput and other instructions in the bytecode.

Recycling activity (GCAction), that is, the activity that affects the objects in the heap when garbage collection is performed. For recycling activities, the garbage collection mechanism is an automatic memory management mechanism. When the data in a piece of memory is no longer used, it will be reclaimed and released for the next allocation. The specific implementation of garbage collection algorithm includes reference counting method, reachability analysis algorithm, etc.

The recycling activity does not correspond to the instructions of the dex bytecode at runtime, because its specific implementation is at the virtual machine level. Recycling activities can be further subdivided into removal activities and compaction activities. The so-called clearing activity is to clear objects that are no longer needed; the so-called compaction activity is to organize active objects into a continuous memory space, so as to avoid allocation failure due to fragmentation when allocating large memory.

In addition, in addition to the objects created by the code of the implemented application layer, the code of the framework layer will also create a large number of objects, in some cases, even several times the number of objects created by the application layer. It is necessary to provide a mechanism for managing the complexity of the heap model to ensure the accuracy and ease of use of the generated runtime stack model. Similar to the aforementioned two-level screening mechanism, there is also a two-level screening mechanism for the activity generation of the heap model. Coarse-grained filtering based on regular matching of package and class names and fine-grained filtering based on activity type.

The present invention preferably provides 6 kinds of heap operation activities, and the activity types of the heap operation activities include object instantiation, array instantiation, object field writing, array element writing, clearing activity and compression activity;

The steps of generating heap operation activities include:

According to the concerned class, use the class filter to perform coarse-grained screening on the activities of the terminal application during runtime, and generate heap operation activities caused by the class;

For the activity type of the heap operation activity, the activity type filter is used to perform fine-grained screening on the heap operation activity.

The challenge faced in the control of behavior reflection, that is, the second challenge described in the background of the present invention, supports instruction-level behavior control. Since it is not the focus of the present invention, it will not be described here.

Next, a specific example is used to verify the effectiveness of the embodiment of the present invention in monitoring terminal application behavior.

For Android mobile applications widely used in the mobile Internet, a prototype system implementation of the behavioral reflection framework is given: Reflectall. The full name of Reflectall is Reflection at low level interpreter, which has two meanings. One is the reflection based on the underlying behavior interpreter; the other is that it can monitor and control the application behavior at the instruction level. Reflectall is based on the Android OS open source project. In order to realize the monitoring and control of mobile application behavior, the Reflectall platform can be divided into the behavior runtime model construction subsystem, the model analysis and code generation subsystem and the running subsystem, realizing the monitoring and control in the behavior reflection framework.

Referring to Figure 8, a schematic diagram of the subsystem architecture is generated for the Reflectall model. The behavioral runtime model construction subsystem of Reflectall realizes the construction of the mobile application behavioral runtime model. Its core implementation is at the system layer, which consists of four modules: optimization-de-optimizer, behavior interpreter, model construction and interface layer. These four modules realize the monitoring and control of mobile application behavior.

Among them, optimization-deoptimizer: the Android runtime environment can load native instructions that can be directly executed by the CPU. Therefore, it is necessary to switch native instructions into bytecodes, that is, de-optimize, and interpret and execute them through a behavioral interpreter, so as to monitor the runtime activities of mobile applications. Due to the complexity of mobile applications, it is difficult to monitor all activities in the execution of mobile applications, so a two-level screening mechanism is introduced. The optimization-de-optimizer implements the class screening mechanism in the two-level screening mechanism. Through the optimization-de-optimizer, the class to be monitored can be de-optimized into bytecode as needed, and interpreted and executed; while for unmonitored class, it is still executed in the native executor. The optimization-de-optimizer will be triggered in the following three situations: 1) When receiving the command to start monitoring, it will filter the methods of the currently loaded class according to the configured parameters and perform de-optimization; 2) Receive When the monitoring command ends, the class that has been deoptimized will be re-optimized to re-enter the native executor for execution; 3) When the class linker loads a new class, it will perform a class similar to the case 1) screening and de-optimization process. In order to ensure the correctness of program execution, the de-optimization process needs to be the same as some garbage collection algorithms, temporarily suspend the execution of all threads, and resume the execution of threads after the de-optimization execution is completed. Through this kind of local anti-optimization and maintaining the coexistence of interpreted execution and native execution, the performance overhead of monitoring can be greatly reduced.

Behavior interpreter: Behavior interpreter is an interpreter that interprets and executes bytecodes in dex format, and can monitor the activities that occur in the current program execution during the process of interpreting and executing. Most of the activities in the mobile application behavior runtime model are generated by the behavior interpreter. In addition to the activities generated by the behavior interpreter, the garbage collector can also generate some activities - garbage collection activities. The behavior interpreter also implements the activity screening mechanism in the two-level screening mechanism, which can generate different kinds of activities according to the configured activity collection granularity.

ModelBuilder: The activities generated by the Behavior Interpreter and Garbage Collector are built in ModelBuilder. When there are many activities generated at runtime, it will lead to a large memory usage. Therefore, Model Builder enables both online and offline model building. When there are few activities, when the model builder runs in the online model building mode, when the number of activities reaches the configured threshold, the model builder will persist the currently generated activity sequence and persist it to the storage in the form of a file .

Interface layer: Encapsulates the functions provided by optimizer-deoptimizer, behavior interpreter and model builder. At the same time, it also provides the interfaces required for deserialization activities, such as finding objects based on addresses and converting a given object to an address.

In the prototype realized by the example of the present invention, two types of runtime models of mobile application behavior can be generated: 1) a refined model that includes runtime data dependencies; 2) a simplified model that does not include runtime data dependencies. Based on the implementation of the system layer, at the framework layer, Reflectall includes a set of behavioral reflection interfaces that can monitor the activities of applications with different granularities and generate runtime models of application behaviors with different granularities; a set of remote debugging connection interfaces that can control the monitoring of application activities start and end. In the application layer, the interface of the framework layer is encapsulated, and an Android application is implemented, which can provide a remote debugging interface in the form of a Web service.

Reflectall's analysis and code generation subsystem is a browser-server architecture. The analysis and code generation subsystem implements:

Version management: use git to manage different versions of mobile applications and interoperable interfaces. At the same time, it supports server-side compilation, and uses the client-side interface management application to push the compiled dex bytecode to the client.

Stack model visualization: Provides a tree view and supports keyword-based data dependency contamination analysis.

The interface operation subsystem of Reflectall adds a behavioral reflection class loader on the framework layer of the Android open source project, as shown in FIG. 9 , which is a schematic structural diagram of the interface operation subsystem of the example Reflectall of the present invention. When the application process starts, it will check whether there is a behavior reflection interface bytecode file that can be loaded. If there is a behavior reflection interface bytecode file suitable for the current application, load it into the application process through the behavior reflection class loader, and at the same time, use the Binder communication mechanism to register the interoperability interface provided by the current application with the interface management application. The interface management application provides services such as interface forwarding and status detection. The caller process can interoperate with the specified application through the interface management application.

During specific verification, the present invention verifies the performance generated by the Reflectall model with an open source application set containing 69 open source Android applications and a closed source application set containing 39 closed source applications.

The construction cost of a mobile application behavioral runtime model is positively related to the number of activities in the model—the more complex the application and the more activities, the more expensive it is to generate the behavioral runtime model. Compared with closed-source applications, the implementation complexity of open-source applications is much lower than that of closed-source applications. The median number of classes in the open source application set is 58, and the median number of methods is 246; the number of classes in 75% of the open source application sets is not greater than 167; the number of methods is not greater than 859 . For the applications in the closed-source application collection, the median number of application classes is 14,266, and the median number of methods is 87,717, which are 245 times and 102 times the corresponding values in the open-source application collection. The hardware configuration used in the experiment is as follows: 1) Use the Android smart phone Redmi 2A, its CPU is 1.5GHz, the memory is 1GB, and the running Android operating system version is 5.1.1. 2) The experiment uses an ordinary PC as a remote control The terminal controls the mobile phone for experiments. The CPU of the PC is Intel Core i5 3427U (1.8GHz), the memory is 4GB, and the OSX 10.11 operating system is running.

At present, in addition to the method of implementing the behavior interpreter described in the present invention, the method for monitoring the execution flow of the application also includes two methods of runtime meta-message binding and compilation-time bytecode reconstruction. Table 2 shows the granularity of activity monitoring supported by the three methods. Reflectall is finer in the granularity of activity monitoring than the method based on runtime binding: it supports activity monitoring at the instruction level; it is also more adaptable than the method based on bytecode refactoring: based on bytecode refactoring This method needs to modify the compilation process of the original application, and it is difficult to directly use it on the obfuscated and hardened application.

Table 2: Comparison of methods for monitoring program execution flow

Granularity of Execution Process Monitoring Is bytecode required Reflect all Support method-level and instruction-level monitoring unnecessary Runtime Binding Based Approach Supports method-level monitoring unnecessary Method based on bytecode reconstruction Support method-level and instruction-level monitoring need

In Experiment 1, the present invention compares the performance of Reflectall and the method based on runtime binding in monitoring program execution flow. In Experiment 2, the performance of Reflectall and the method based on bytecode reconstruction is compared in monitoring the activity of instruction granularity.

Experiment 1: Comparing the methods of runtime meta-message binding

The Xposed framework is a framework service that can monitor and modify program running behavior without modifying the APK (rovo89, 2012). Similar to Reflectall, the Xposed framework is also modified at the system level of the Android operating system. The Xposed framework implements the behavior reflection of the meta-message model, that is, Xposed binds the corresponding meta-object to the specified method according to the configuration when the application is running. In subsequent executions, these methods bound to the meta-object will call the before and after methods in the meta-object before and after execution. This article uses the Xposed framework to implement an Xposed module that monitors program execution similar to Reflectall. In this section, the application startup time is used as an indicator. On two Redmi 2A mobile phones with the same hardware configuration, Reflectall and Xposed-based monitoring modules are respectively deployed, and the Android operating system is 5.1.1. Through the following six different experimental scenarios, compare the performance of Reflectall and the method based on the Xposed framework in monitoring the execution performance of all application classes of the application on the open source application set and the closed source application set, as shown in Table 3. In each scenario, each application is started 10 times, and the experimental results are shown in Figure 10.

Table 3: Comparison of methods for monitoring program execution flow

Figure 10(a) shows the experimental results on the open source application set. In the open source application collection, 69 applications can be started normally in the above six scenarios. The solid line in Figure 10(a) is the three scenarios where Reflectall is deployed; the dotted line is the three scenarios where the Xposed framework is deployed. Without monitoring the program execution process, the average startup time of the mobile phone deployed with Reflectall (Scenario 1) was 392 milliseconds, while the platform startup time of the mobile phone deployed with the Xposed framework (Scene 3) was 449 milliseconds. This is because even if the implementation of the Xposed framework does not bind the meta-object, there will be a certain overhead when the application is loaded. And Reflectall's optimization-deoptimizer realizes that all codes are executed in the native executor when it is not monitored. In scenario 2, the average startup time of Reflectall is 486 milliseconds, compared with the case of no monitoring (392 milliseconds), the additional overhead is 23%; while the method based on the Xposed framework, the average startup time in scenario 2 is as high as 2078 milliseconds, compared with Compared to the case of no monitoring (449 ms), the overhead is 368%. While generating more complex behavioral runtime models (Scenario 3 and Scenario 6), the additional overhead of Reflectall is only 27%, while the method based on the Xposed framework is as high as 477%.

Figure 10(b) shows the experimental results on the closed-source application set. In the non-monitoring scenario, compared with simple open source applications, the average startup time of closed source applications is 936 milliseconds (Reflectall) and 1010 milliseconds (Xposed). In scenario 2, due to the complexity of the application, 3 applications of Reflectall are unresponsive, and the average startup time of the remaining 36 applications is 1601 milliseconds, compared with the non-monitoring scenario (936 milliseconds), the additional overhead is 71%. In scenario 4, 22 applications are unresponsive, and the average startup time of the remaining 17 applications is 4593 milliseconds. Compared with the scenario without monitoring (1010 milliseconds), the additional overhead is 354%. While generating more complex behavioral runtime models (Scenario 3 and Scenario 6), Reflectall has an additional overhead of 98%, while the method based on the Xposed framework is as high as 470%.

The performance of the behavior runtime model generated by Reflectall is quite different between the open source application set and the closed source application set. Garbage collection and activity persistence process, which brings more performance overhead. However, the cost of the Xposed-based method in these two application sets is close. The reason is that when Xposed is used for monitoring, 22 applications are unresponsive, accounting for 57% of the entire closed-source application set. One of the reasons why the performance overhead of Reflectall is lower than that of the method based on the Xposed framework is that the programming language used by the method based on the Xposed framework is Java, and the programming language of the behavior interpreter implemented by Reflectall is C++. When the execution process of the application is complex, the method based on the Xposed framework will allocate and reclaim memory more frequently than Reflectall. The above experiments show that the implementation of Reflectall in the present invention can handle more complex applications.

Experiment 2: Comparing methods based on bytecode reconstruction

Many commonly used Java libraries use bytecode reconstruction frameworks. A very important usage scenario for bytecode reconstruction is program analysis. For example, the popular bug location tool FindBugs uses ASM at the bottom to analyze bytecode and locate vulnerabilities. Another common usage scenario is to use bytecode refactoring to generate program code coverage reports, such as Emma (Roubtsov, 2005), JCover (JCover, 2017). The compact models generated by Reflectall can be converted into code coverage reports. This experiment will compare the difference between Reflectall and Emma in generating code coverage reports. Because the method based on bytecode reconstruction is not suitable for closed-source applications that only have application installation packages. Therefore, this part is only for open source application sets. In this implementation, the application startup time is still used as an indicator. On two Redmi 2A mobile phones with the same hardware configuration, Reflectall and the unmodified Android system are respectively deployed, and the Android operating system is 5.1.1. In this experiment, the original application is installed on the mobile phone where Reflectall is deployed; the application that has been instrumented by Emma is installed on the unmodified Android mobile phone, and the code generated on the open source application set generated by Reflectall and Emma is compared in the following three different experimental scenarios Override reported performance. In each scenario, each application is started 10 times, and the experimental results are shown in Figure 11.

The experimental results show that the average startup time of Reflectall and Emma's applications is close, the average startup time is 442 milliseconds and 455 milliseconds, and the overhead is 13% and 16% respectively. But from the generated code coverage information, Reflectall is richer than Emma. Table 4 shows the difference between the monitoring granularity and deployment operation of Reflectall in the code coverage report. Emma's report on block coverage may be inaccurate, and does not support the number of branch executions, while Reflectall's behavior-based interpreter can ensure the accuracy of the coverage report, and also implements branch instructions (such as If-gt, Packed-Switch) Statistics of execution times of each branch. Another difference is that Emma needs to be configured to refactor the bytecode, and needs to be repackaged after refactoring; while Reflectall does not need these configurations and will not change the compilation process of mobile applications. Therefore, Reflectall is easier to use and more practical than bytecode refactoring tools such as Emma.

Table 4: Comparison of monitoring granularity between Reflectall and Emma

Compare categories Emma Reflect all class coverage support support method override support support block coverage partial support support branch coverage partial support support line coverage support support number of branch executions not support support instruction coverage not support support Is bytecode required need unnecessary Do you need to repackage need unnecessary

In summary, the present invention provides a method for constructing a runtime model of terminal application behavior, which can regard the execution of the application as a programming language framework (such as an interpreter, a virtual machine), and read the memory according to the code segment of the application. write operation. What kind of method is executed can correspond to the operation of the programming language framework on the stack; what kind of object data is modified can correspond to the operation of the programming language framework on the heap. It realizes the flexible and complete monitoring of the application behavior of the terminal application, and provides a technical guarantee for the subsequent realization of the command-level control of the application behavior of the terminal application. The calculation reflection engine designed according to this method can be used as a separate operating environment, and can also be integrated into various mainstream development platforms or commercial software, providing developers with the basic ability to monitor application runtime.

The above-mentioned embodiments are only preferred embodiments, and are not intended to limit the protection scope of the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection scope of the present invention .

Claims (10)

1. A method for constructing a runtime model of terminal application behavior, wherein the runtime model includes a runtime stack model and a runtime heap model, and the method includes constructing a runtime stack model of the terminal application behavior and the step of constructing a runtime heap model of the terminal application behavior; The step of constructing the runtime stack model of the terminal application behavior includes: When the terminal application is running, obtain the code actually executed in the memory of the terminal application, and abstract the code actually executed to generate a control flow graph; For the control flow graph, input the control flow graph to be monitored into a preset behavior interpreter; Using the behavior interpreter to interpret and execute the control flow graph that needs to be monitored, and generate stack activities when the terminal application is running; When the terminal application is running, generate a dependency between the control flows of the stack activities, and obtain a runtime stack model of the terminal application behavior; The step of constructing the runtime heap model of the terminal application behavior includes: When the terminal application is running, generate an initial state of the heap; A heap operation activity is generated to obtain a runtime heap model of the terminal application behavior. 2. The method according to claim 1, wherein the method comprises a class filter and an activity type filter; wherein the class filter is based on a coarse-grained screening of regular matching of a package and a class name, and is used to remove Program activities that developers don't care about; the activity type filter is based on fine-grained screening of activity types, and is used to remove activity types that developers don't care about. 3. The method according to claim 2, wherein the activity type of the stack activity includes method start and method end, field read, array read and synchronization instructions; Using the behavior interpreter to interpret and execute the control flow graph that needs to be monitored, the step of generating the stack activity when the terminal application is running includes: Using a behavior interpreter capable of monitoring the application behavior of the terminal application to interpret and execute the control flow graph that needs to be monitored, to obtain the running activities of the terminal application; According to the concerned class, use the class filter to perform coarse-grained screening on the activities of the terminal application during runtime, and generate stack activities caused by the class; For the activity type of the stack activity, the activity type filter is used to perform fine-grained screening on the stack activity. 4. The method according to claim 1, wherein the step of constructing the runtime heap model of the terminal application behavior comprises: The running activities of the terminal application include instantiation activities, modification activities and recycling activities. 5. The method according to claim 2, wherein the activity type of the heap operation activity includes object instantiation, array instantiation, object field writing, array element writing, clearing activity and compression activity; The steps of generating heap operation activities include: According to the concerned class, use the class filter to perform coarse-grained screening on the activities of the terminal application during runtime, and generate heap operation activities caused by the class; For the activity type of the heap operation activity, the activity type filter is used to perform fine-grained screening on the heap operation activity. 6. The method according to claim 1, wherein the dependencies include synchronization dependencies and communication dependencies. 7. The method according to claim 6, characterized in that when generating synchronization dependencies between control flows, when the end of one method depends on the end of another method, the time stamp is used to find other threads from the back to the front Matchable activities in , if found, correspond to a synchronization dependency; for the case where the start of one activity depends on the end of another activity, first check the current thread, if the activity is the first execution in the current thread , the activity depends on another thread to end the activity, otherwise the activity is just a normal method call and does not depend on the activity of another thread. 8. The method according to claim 6, wherein when generating the dependency between the control flows of the stack activities, all the classes related to the inter-activity communication dependencies are summarized, and the related classes of the classes are Methods together with methods related to thread dependencies serve as a knowledge base for generating communication dependencies. 9. The method according to claim 1, wherein when the runtime model is generated, the sequence of activities in the runtime model is stored in a buffer with a configurable size, and when the number of activities exceeds a preset , the activities of the buffer are serialized and persisted to the local storage. 10. The method of claim 1, wherein the runtime heap model is represented in Backus-Naur Form.