一种构造终端应用行为的运行时模型的方法

摘要

本发明公开了一种构造终端应用行为的运行时模型的方法，通过行为解释器，生成一个完整、准确、详实的应用行为自述，即终端应用应用行为的运行时模型，克服了现有技术在动态、多变、难控的应用运行时环境对终端应用应用行为的监测上的不足，实现了对终端应用应用行为的灵活、完整的监测，为后续实现对终端应用应用行为的指令级控制提供了技术保障。

权利要求

1.一种构造终端应用行为的运行时模型的方法，其特征在于，所述运行时模型包括运行时栈模型和运行时堆模型，所述方法包括构造所述终端应用行为的运行时栈模型的步骤和构造所述终端应用行为的运行时堆模型的步骤；

所述构造所述终端应用行为的运行时栈模型的步骤包括：

在所述终端应用运行时，获取所述终端应用的内存中真正执行的代码，并对所述真正执行的代码进行抽象，生成控制流图；

针对所述控制流图，将需要监测的控制流图输入至预设的行为解释器；

利用所述行为解释器对所述需要监测的控制流图进行解释执行，生成所述终端应用运行时的栈活动；

在所述终端应用运行时，生成所述栈活动的控制流间的依赖关系，得到所述终端应用行为的运行时栈模型；

所述构造所述终端应用行为的运行时堆模型的步骤包括：

在所述终端应用运行时，生成堆区的初始状态；

生成堆操作活动，得到所述终端应用行为的运行时堆模型；

其中，所述依赖关系包括同步依赖和通信依赖；

在生成所述同步依赖关系时，对于一个方法的结束依赖另一个方法的结束的情况，利用时间戳由后往前寻找其他线程中可匹配的活动，如果找到，则对应于一个同步依赖关系；

对于一个活动的开始依赖另一个活动的结束的情况，先对当前线程进行检查，如果该活动为当前线程中的第一个执行的活动，则该活动是依赖另一个线程结束活动的，否则该活动仅是正常的方法调用，并不依赖另一个线程的活动。

2.如权利要求1所述的方法，其特征在于，所述方法包括类筛选器和活动类型筛选器；

其中，所述类筛选器基于包和类名正则匹配的粗粒度筛选，用于去除开发人员不关心的程序活动；所述活动类型筛选器基于活动类型的细粒度筛选，用于去除与开发者不关心的活动类型。

3.如权利要求2所述的方法，其特征在于，所述栈活动的活动类型包括方法开始与方法结束，字段读，数组读和同步指令；

利用所述行为解释器对所述需要监测的控制流图进行解释执行，生成所述终端应用运行时的栈活动的步骤包括：利用对所述终端应用的应用行为具有监测功能的行为解释器对所述需要监测的控制流图进行解释执行，获得所述终端应用运行时的活动；

根据所关注的类，利用所述类筛选器对所述终端应用运行时的活动进行粗粒度筛选，生成由所述类引起的栈活动；

针对所述栈活动的活动类型，利用所述活动类型筛选器对所述栈活动进行细粒度筛选。

4.如权利要求1所述的方法，其特征在于，所述构造所述终端应用行为的运行时堆模型的步骤包括：所述终端应用运行时的活动包括实例化活动、修改活动和回收活动。

5.如权利要求2所述的方法，其特征在于，所述堆操作活动的活动类型包括对象实例化，数组实例化，对象字段写，数组元素写，清除活动和压缩活动；

所述生成堆操作活动的步骤包括：

根据所关注的类，利用所述类筛选器对所述终端应用运行时的活动进行粗粒度筛选，生成由所述类引起的堆操作活动；

针对所述堆操作活动的活动类型，利用所述活动类型筛选器对所述堆操作活动进行细粒度筛选。

6.如权利要求1所述的方法，其特征在于，在生成所述栈活动的控制流间的依赖关系时，对所有与活动间通信依赖相关的类进行总结，并将所述类的相关方法与线程依赖相关的方法一起作为生成通信依赖的知识库。

7.如权利要求1所述的方法，其特征在于，在所述运行时模型生成时，将所述运行时模型中的活动序列存放于可配置大小的缓冲区中，当活动数量超过预设时，则将所述缓冲区的活动进行序列化，并持久化到本地存储中。

8.如权利要求1所述的方法，其特征在于，所述运行时堆模型以巴科斯范式的形式表示。

说明书

一种构造终端应用行为的运行时模型的方法

技术领域

[0001] 本发明涉及计算机技术，尤其涉及一种构造终端应用行为的运行时模型的方法。

背景技术

[0002] 网构软件(也称终端应用)是在互联网开放、动态和多变环境下软件系统基本形态的一种抽象，它既是传统软件结构的自然延伸，又具有区别于集中封装环境下发展起来的传统软件形态的独有基本特征：1) 自主性，指网构软件系统中的软件实体具有相对独立性、主动性和自适应性。自主性使其区别于传统软件系统中软件实体的依赖性和被动性；2)协同性，指网构软件系统中软件实体与软件实体之间可按多种静态连接和动态合作方式在开放的网络环境下加以互连、互通、协作和联盟。协同性使其区别于传统软件系统在封闭集中环境下单一静态的连接模式；3)反应性，指网构软件具有感知外部运行和使用环境并对系统演化提供有用信息的能力。反应性使网构软件系统具备了适应开放、动态和多变环境的感知能力；4) 演化性，指网构软件结构可根据应用需求和网络环境变化而发生动态演化，主要表现在其实体元素数目的可变性，结构关系的可调节性和结构形态的动态可配置性。演化性使网构软件系统具备了适应比开放、动态和多变环境的应变能力；5)多态性，指网构软件系统的效果体现出相容的多目标性。它可根据某些基本协同原则，在动态变化的网络环境下，满足多种相容的目标形态。多态性使网构软件系统在网络环境下具备了一定的柔性和满足个性化需求的能力。

[0003] 上述网构软件特征的实现，往往需要在运行态修改软件以保障或改善质量、优化或新增功能。经典软件工程方法与技术强调在开发态修改软件，不支持运行态直接修改软件。

[0004] 与之对应，编程语言、操作系统、中间件等系统软件，提供了一种常见的运行态监测与控制应用的主要机制——计算反射(computational reflection，简称反射)。基于计算反射可以实现各种开发框架、测试框架，以提高开发人员在代码开发、测试甚至运行部署中的效率。在计算机领域，B.Smith给出了通用的反射性的定义：反射性是实体具有按照描述、操作和处理实体所面临的主要问题域的相同方式来描述、操作和处理实体自身的一种能力。该定义后续被解释为：反射性是程序具有在运行时刻操纵一组数据的能力，这组数据描述了该程序的运行状态，操纵有两方面含意：1)监测(Introspection)，程序可以观测并推理自身的状态；2)控制(Intercession)，程序可以改变自身的运行或语义。而这两方面都需要能将程序执行的状态编码为数据，而提供这种编码便称为反射也就是说，反射其实是将程序的运行状态映射为一组可操作的数据。前一部分组成基层实体，后一部分组成元层实体，而基层实体与元层实体之间保持了因果关联。根据基层实体的不同，计算反射主要分为结构反射和行为反射。结构反射的基层实体为当前程序及其抽象数据类型(可视为应用的状态)，而行为反射的基层实体则是当前程序的执行行为及其执行所需的数据(可视为应用的行为)。

[0005] 结构反射是指编程语言提供对当前程序及其抽象数据类型反射的能力，由于与编程语言框架(runtime 或framework)的能力类似而自然存在，是大多数编程语言框架固有的能力。

[0006] 行为反射是指编程语言提供对自身的执行语义及其执行所需的数据反射的能力，也就是编程语言框架自身需要被反射，行为反射在监测和控制上面临两个挑战：其一，需要完整描述既有的应用行为，也就是对应用的执行进行监测。应用的执行可视为一组运行时活动的集合，活动的粒度越细，监测的信息也越丰富，监测功能占用的资源就越大，其与业务逻辑之间的资源竞争也就越严重。此时，应用行为监测的复杂性和规模性就成为终端应用行为反射的首要挑战。其二，现有编程语言以及操作系统和中间件等系统软件的行为反射，均不支持指令级的行为控制，根本原因在于指令序列蕴含的复杂的数据和控制依赖，因此，应用行为的指令级控制就成为终端应用行为反射的主要难点。

发明内容

[0007] 本发明主要目的在于，提供一种构造终端应用行为的运行时模型的方法，克服上述第一个挑战，实现对终端应用运行时行为的完整监测。

[0008] 本发明是通过如下技术方案实现的：

[0009] 为解决上述技术问题，本发明提出了一种构造终端应用行为的运行时模型的方法，所述运行时模型包括运行时栈模型和运行时堆模型，所述方法包括构造所述终端应用行为的运行时栈模型的步骤和构造所述终端应用行为的运行时堆模型的步骤；

[0010] 所述构造所述终端应用行为的运行时栈模型的步骤包括：

[0011] 在所述终端应用运行时，获取所述终端应用的内存中真正执行的代码，并对所述真正执行的代码进行抽象，生成控制流图；

[0012] 针对所述控制流图，将需要监测的控制流图输入至预设的行为解释器；

[0013] 利用所述行为解释器对所述需要监测的控制流图进行解释执行，生成所述终端应用运行时的栈活动；

[0014] 在所述终端应用运行时，生成所述栈活动的控制流间的依赖关系，得到所述终端应用行为的运行时栈模型；

[0015] 所述构造所述终端应用行为的运行时堆模型的步骤包括：

[0016] 在所述终端应用运行时，生成堆区的初始状态；

[0017] 生成堆操作活动，得到所述终端应用行为的运行时堆模型。

[0018] 进一步的，所述方法包括类筛选器和活动类型筛选器；其中，所述类筛选器基于包和类名正则匹配的粗粒度筛选，用于去除开发人员不关心的程序活动；所述活动类型筛选器基于活动类型的细粒度筛选，用于去除与开发者不关心的活动类型。

[0019] 进一步的，所述栈活动的活动类型包括方法开始与方法结束，字段读，数组读和同步指令；

[0020] 利用所述行为解释器对所述需要监测的控制流图进行解释执行，生成所述终端应用运行时的栈活动的步骤包括：

[0021] 利用对所述终端应用的应用行为具有监测功能的行为解释器对所述需要监测的控制流图进行解释执行，获得所述终端应用运行时的活动；

[0022] 根据所关注的类，利用所述类筛选器对所述终端应用运行时的活动进行粗粒度筛选，生成由所述类引起的栈活动；

[0023] 针对所述栈活动的活动类型，利用所述活动类型筛选器对所述栈活动进行细粒度筛选。

[0024] 进一步的，所述构造所述终端应用行为的运行时堆模型的步骤包括：

[0025] 所述终端应用运行时的活动包括实例化活动、修改活动和回收活动。

[0026] 进一步的，所述堆操作活动的活动类型包括对象实例化，数组实例化，对象字段写，数组元素写，清除活动和压缩活动；

[0027] 所述生成堆操作活动的步骤包括：

[0028] 根据所关注的类，利用所述类筛选器对所述终端应用运行时的活动进行粗粒度筛选，生成由所述类引起的堆操作活动；

[0029] 针对所述堆操作活动的活动类型，利用所述活动类型筛选器对所述堆操作活动进行细粒度筛选。

[0030] 进一步的，所述依赖关系包括同步依赖和通信依赖。

[0031] 进一步的，在生成控制流间的同步依赖关系时，对于一个方法的结束依赖另一个方法的结束的情况，利用时间戳由后往前寻找其他线程中可匹配的活动，如果找到，则对应于一个同步依赖关系，对于一个活动的开始依赖另一个活动的结束的情况，先对当前线程进行检查，如果该活动为当前线程中的第一个执行的活动，则该活动是依赖另一个线程结束活动的，否则该活动仅是正常的方法调用，并不依赖另一个线程的活动。

[0032] 进一步的，在生成所述栈活动的控制流间的依赖关系时，对所有与活动间通信依赖相关的类进行总结，并将所述类的相关方法与线程依赖相关的方法一起作为生成通信依赖的知识库。

[0033] 进一步的，在所述运行时模型生成时，将所述运行时模型中的活动序列存放于可配置大小的缓冲区中，当活动数量超过预设时，则将所述缓冲区的活动进行序列化，并持久化到本地存储中。

[0034] 进一步的，所述运行时堆模型以巴科斯范式的形式表示。

[0035] 与现有技术相比，本发明通过行为解释器，生成一个完整、准确、详实的应用行为自述，即终端应用应用行为的运行时模型，克服了现有技术在动态、多变、难控的应用运行时环境对终端应用应用行为的监测上的不足，实现了对终端应用应用行为的灵活、完整的监测，为后续实现对终端应用应用行为的指令级控制提供了技术保障。

附图说明

[0036] 图1是现有3G无线资源控制状态机；

[0037] 图2(a)是一个网络请求合并的实例中合并前的网络请求控制流示意图；

[0038] 图2(b)是一个网络请求合并的实例中合并后的网络请求控制流示意图；

[0039] 图3是一个线程之间通信依赖的例子——生产者-消费者模式示意图；

[0040] 图4是本发明一种构造终端应用行为的运行时模型的方法的步骤流程图；

[0041] 图5是安卓多线程编程示例；

[0042] 图6是一个多线程编程间依赖示例；

[0043] 图7(a)是执行前堆区对象；

[0044] 图7(b)是执行后堆区对象；

[0045] 图8是本发明示例Reflectall模型生成子系统架构示意图；

[0046] 图9是本发明示例Reflectall的接口运行子系统的结构示意图；

[0047] 图10(a)是开源应用集上的实验结果；

[0048] 图10(b)是闭源应用集上的实验结果；

[0049] 图11是Reflectall与Emma生成代码覆盖率报告时的应用启动时间结果对比图。

具体实施方式

[0050] 为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施例和附图，对本发明作进一步详细说明。

[0051] 为了更好理解本申请的技术问题，本发明采用选取两个典型案例的应用功能演化场景进行分析，以此来明确现有的行为反射不适用的根本原因。

[0052] 案例一：

[0053] 随着智能手机的发展，终端的移动应用越来越依赖云端提供的软件、硬件资源，以提供更好的服务。然而，云端与终端之间的通讯需要消耗大量的电能。联网应用(如天气、邮件、新闻等)呈现了网构软件典型的构件化特点，利用网络实现了终端与云端各构件的通讯。特别在3G/4G环境下，联网应用在后台长时间、间隔式地利用网络获取相应的推送消息。这种长时间、间隔式的消息推送给电池容量有限的智能手机的续航带来了巨大压力。3G和
4G是当前主流使用的移动蜂窝网络，其耗电特点更为复杂。一方面，因为蜂窝网络移动性较强，对于一个移动设备，随着物理位置的移动，可能快速切换到不同蜂窝网络基站。因此，对于蜂窝网络基站，不可能将一个信道一直分配给一台移动设备。另一方面，由于移动设备续航有限，而长时间连接至蜂窝网络基站，会大大提高其功耗，影响续航。因此，蜂窝网络标准中，进一步对无线资源控制(Radio Resource Control，RRC)模块的状态进行了规定。

[0054] 以移动设备中的3G网络模块为例，一共包含三个状态，如图1所示。

[0055] (1)IDLE：即空闲状态，在此状态下，3G模块的耗电最低，同时也不能发送、接收任何数据。在这个状态下，如果要发送或接收数据，则会转移至CELL_DCH状态。

[0056] (2)CELL_DCH：在这个状态下，3G模块的带宽达到最大，此时能以最大的速率进行数据传输，同时它的功耗也是最大的。如果持续一段时间，仍然没有数据传输的话，它会转移至CELL_FACH状态。根据不同的运营商的设置，持续运行于CELL_DCH状态的时间通常是5秒至10秒。

[0057] (3)CELL_FACH:在这个状态下，3G模块的耗电比CELL_DCH要节省50％，同时，在这个状态下，其网络传输速率也较低。如果在这个状态，发送或接收的数据大于某个阀值，则会重新转移至 CELL_DCH状态。而如果在CELL_FACH状态持续一段时间没有发送或接收数据，则会转移至IDLE状态。一般来说这段时间通常是10秒至15秒。

[0058] 图2(a) 、图 2(b) 展示了一个网络请求合并的实例。图2(a)为合并前的网络请求与无线通讯模块耗电，其横轴为时间，上半部分为无线通讯模块的功耗；下半部分的虚线为发起这两个网络请求的线程；下半部分的实线为其控制流。首先，一个后台的新闻推送线程唤醒了负责发送网络请求的线程①；该线程被唤醒后，发起了网络请求②，此时，无线通讯模块的功耗也由IDLE状态下的低功耗，变为CELL_DCH状态下的高功耗；当整个请求完成后，负责发送网络请求的线程将结果返回给新闻推送线程③，此时虽然无线通讯模块没有接收或发送数据，但它仍会保持在高功耗状态，由此开始的无线通讯模块耗电被称之为“尾时间耗电”，对应为图2(a)中用的斜线部分；新闻推送线程在收到返回结果后④，对结果进行处理，并在通知栏上进行提示⑤。又过了一段时间后，另一个版本更新线程也执行了类似的逻辑⑥，发送了网络请求。如图2(a) 所示，由于这两个网络请求间隔了几十秒，导致无线通讯模块被唤醒了两次，因此也有了对应的两次“尾时间”，由此导致了额外的网络能耗。

[0059] 对于安卓应用，有很大一部分后台请求可以被延迟几十秒、甚至两、三分钟，而不会影响用户的体验。例如上述的新闻推送、版本更新推送等。对于这些网络请求，如果在时间维度上进行合并，即两个请求同时发送，而不是间隔了几十秒发送，就可以减少“尾时间”的网络耗电。图2(b)为图2(a)中两个请求进行了合并后的控制流及其无线通讯模块耗电情况。首先，负责发送网络请求的线程被新闻推送线程唤醒后，并不直接发送网络请求，而是进入一个等待状态⑦。一段时间后，另一个网络请求线程被后台更新推送线程唤醒，同时，它也进入一个等待状态⑧。在等待状态结束后⑨，这两个线程同时发送网络请求，对应的无线通讯模块也只被唤醒一次。如图2(b)所示，合并后的网络请求的耗电要远小于合并前的网络请求耗电。

[0060] 为了实现网络请求合并，需要1)一种网络请求调度机制，即，使原本直接发送的网络请求可被延迟发送；2)一种网络请求调度算法，即找出可被延迟调度的请求，同时利用调度机制进行延迟发送。利用结构反射可以实现自动化重构移动应用的网络请求执行逻辑，并把调度机制内置进应用。然而这就要求不同应用的开发者均使用同一个自动重构框架，并且需要对所有应用进行重新的编译、部署和运行。这对于大量的、分属于不同应用开发者的闭源应用显然不现实。

[0061] 案例二：

[0062] 随着微信的普及，微信已经不仅仅是一个简单的通讯应用，它还成为了工作交流的必备工具；催生了利用微信朋友圈、公众号进行营销的“微商”；成为了最大的自媒体的发布平台。微信其核心作为一个通讯工具，其功能还是以满足普通用户为主。即便如此，它也很难满足普通用户的特定需求。例如，随着微信使用的时间越来越长，其缓存的聊天记录文件也越来越大，对于普通用户而言，很难对自己的聊天日志进行管理。更进一步地，微信难以满足微商、自媒体人等特殊群体的特定的需求。要实现微信应用内数据与功能的开放共享，就需要将面向用户的用户界面接口转换为面向互操作的可编程接口。一般而言，对于面向用户的用户界面接口，其执行的起点在于用户界面元素的点击、拖动和输入等操作。经过部分的逻辑处理，以网络请求、数据库查询、文件读写的方式，访问外部资源，获取相应的数据或实现相应的功能。在该处理流程中，有大部分的逻辑是与面向互操作的可编程接口的执行逻辑是相似的，只是其执行的起点不同。然而，现有的行为反射监测和控制的粒度为方法级别。基于现有的行为反射，在既有应用的执行流程中插入某些执行逻辑的方式，难以实现将面向用户的用户界面接口转换为面向互操作的可编程接口：既有的功能可对应于运行时的一组程序活动，以方法为粒度的行为反射其监测的内容有限，无法监测方法内的指令的执行，继而也无法控制。这就导致了现有的解决方案往往是基于既有的代码和文档，对于一个开发团队而言，开发人员的流动、文档的缺失、甚至是不规范的源码注释都会使得移动应用的迭代开发变得难以进行。

[0063] 由上述两个案例分析可以看出，难以实现移动应用互操作接口根本原因在于现有的工作由于缺乏对应用行为的一个完整、详实的描述，同时也没有对这种指令粒度的自描述的控制的方法。因而，能否给出一个完整描述应用行为、并且可操作的运行时模型也就成了解决本发明问题的难点和关键。

[0064] 针对上述技术问题，本发明实施例提出了一种构造终端应用行为的运行时模型的方法，所述运行时模型包括运行时栈模型和运行时堆模型。

[0065] 应用在操作系统中运行起来之后，可视为一个或多个进程，操作系统将移动应用所需的可执行文件加载到内存中，并开始执行。一般而言，一个进程所占的内存可分为三个区域：

[0066] 代码段：存放执行代码的一块内存区域，具有只读属性；

[0067] 堆区：可分为用于存放全局变量的一块内存区域(数据段)，和用于进程运行中动态分配的内存区域，例如，面向对象编程语言Java中，线程创建一个新的对象相当于在堆区中申请了一片内存；

[0068] 栈区：用于临时存局部变量等。例如，面向对象编程语言Java中，线程调用一个方法时，会新申请一个帧(frame)，帧中保存了方法所需的参数等数据。

[0069] 经过发明人仔细研究发现，终端应用在运行时，代码段的执行会引起堆区和栈区内存数据的变化。应用的运行时模型需要能反映应用在一段时间内的：1)代码的执行情况：在开发时，移动应用的代码可抽象为控制流图，那么对应于运行时，代码的执行情况可抽象为控制流图的一条或多条路径；2)内存数据(如堆区)的变化：在开发时，开发人员会设计好各种数据结构以表示应用的数据模型(Data Model)，而在运行时，代码的执行引起对这些数据结构的实例的创建、修改、删除，也就是对应于一组内存的分配和修改操作。从内存区域角度上看，程序执行所影响的最主要的区域是内存的栈区和堆区。1)中的控制流图中的路径可视为对栈变化的一个描述，而2)中主要体现的是堆区数据的变化。

[0070] 因此，本发明所构造的应用运行时模型包括一个描述栈变化的运行时栈模型和一个描述堆变化的运行时堆模型。其中运行时栈模型还包括对代码的获取，以此将一个进程所占的内存完整的分为三个区域。通过本发明实施例的运行时栈模型，可以了解在任意时刻移动应用的代码执行情况；而通过运行时堆模型，可以了解在任意时刻代码执行所依赖的对象数据状态。

[0071] 运行时栈模型

[0072] 控制流图为一个有向图G＝；

[0073] 其中，B＝{b1，b2，…，bn}为基本块；

[0074] 为控制流路径；

[0075] 对于任意pi＝(bi1，bi2)，pi∈P，当且仅当bi2可能bi1之后执行。而在运行时，控制流图会实例化为一个或多个控制流，并按照控制流图中的路径执行基本块。本发明称在某一时刻执行的基本块为活动，则一段时间内的运行时栈模型是由控制流图，一个或多个控制流，和一组活动序列组成。当基本块的粒度为指令粒度时，活动序列就是指令执行序列。下面给出本发明所述的运行时栈模型的形式化定义。

[0076] 定义运行时栈模型为一个或多个控制流在一段时间内发生的活动的集合M＝，

[0077] 其中，G＝为控制流图，T＝{t1，t2，…，tn}为一组时刻，I＝{i1，i2，…，in}，表示t1至tn时刻的程序的堆区状态。

[0078] 令F＝{f1，f2，…，fn}，为一组控制流，则A＝F×I×T×B为一段时间内发生的活动的集合， 表示两个活动发生的前后关系的集合。

[0079] 运行时栈模型可视为控制流图的多条路径的集合，因此，在运行时栈模型中的边必须在控制流图中有相应的边。即： 其中ai(fi1，ti2，bi3)， aj＝(fj1，tj2，bj3)aj＝(fj1，tj2，bj3)，有(bi3，bj3)∈P。除此之外，运行时栈模型的边表示两个活动发生的前后关系，对于在同一控制流中的两个活动，具有时间上的前后顺序关系；对于在不同控制流中的两个活动如果存在边，则表明这两个活动间还具有依赖关系。

[0080] 在同一个控制流中，若有两个活动具有前后发生关系，则对于任意的其他活动，都不可能在同一控制流的这两个活动之间发生，即 其中ai＝(fi1，ti2，bi3)， aj＝(fj1，tj2，bj3)，如果fi1≠fj1，则

[0081] 在不同控制流中，若两个活动具有前后发生关系，则对于后一个活动所在的控制流，在发生前一活动的时刻之后，可以先发生其他活动。 其中ai＝(fi1，ti2，bi3)，aj＝(fj1，tj2，bj3)，如果fi1≠fj1，则ti2＜tj2。

[0082] 定义程序活动aj同步依赖于程序活动ai，如果aj的开始或结束由ai的执行决定，一般地，而ai往往是一些线程同步操作。称aj通信依赖于ai，如果aj的某项数据依赖是由ai活动产生。以面向对象编程语言Java为例，基本块的粒度为源代码的基本块的粒度。运行栈模型的每一个控制流对应于一个Java线程的执行序列。线程的状态转移共有六种状态：

[0083] 创建：线程对象刚创建，还未开始时处于该状态；

[0084] 运行：线程处于正在运行的状态，在该状态的线程可能等待一些系统资源，如CPU；

[0085] 阻塞:线程正在等待某个监控锁(Monitor Lock)，例如线程在进入synchronized关键字修改的方法或是代码块时，线程会进入阻塞状态；

[0086] 等待/定时等待:线程正在等待，例如，当线程调用某个对象的wait方法进入等待状态。当该对象的 notify方法被该用时，线程会重新进入运行状态；

[0087] 死亡：当一个线程的run方法执行结束后，会进入死亡状态。

[0088] 由以上的状态转换可以发现，在某些情况下，某一个处于运行状态的线程可以唤醒另一个处于非运行状态的线程进入运行状态。本发明称线程之间的这种关系为同步依赖关系。在这些线程间唤醒发生时，对应于运行时栈模型中，处于运行状态的线程发生的活动会与非运行状态线程进入运行状态时发生的活动存在一条跨线程(跨控制流)的边。从Java的语言层面，可将这些线程依赖归纳为四类，如表1所示。

[0089] 表1：Java语言层面的同步依赖关系分类

[0090]

[0091] 在表1中，每个运行线程的活动都会与非运行线程的活动对应。因此，称表1中的线程间依赖关系为同步依赖关系。基于以上线程的状态转换，Java提供了多种多线程编程库，以支持，例如java.util.concurrent 中提供了读写锁、可重入锁、阻塞锁和线程池等。

[0092] 图3展示了一个线程之间通信依赖的例子——生产者-消费者模式。在该例子中，Task类表示计算任务；静态字段tasks表示待处理任务队列；postTask方法表示生成并提交任务；handleTask方法表示处理任务。如图3所示，存在两个线程：1)线程1表示生产者线程，会提交任务至待处理任务队列；2)线程2表示消费者线程，每隔一段时间便会查看待处理任务队列，并处理相应的任务。在这个例子中，生产者线程与消费者线程之间并无同步依赖关系——消费者线程每隔一段时间便自动由定时等待状态转为运行状态，但是却存在通信的依赖关系——如果生产者线程不提交任务，消费者线程的task.run方法便不会被调用。

[0093] 由上述例子可以发现，运行时栈模型中的活动关系的生成必须依赖运行时的相应数据。在经典的数据流分析中，数据流分析算法会根据控制流图的结构计算数据流方程，并迭代至稳定点。因此，应用的运行时模型除了上述的运行时栈模型外，还需一个描述内存堆区数据状态变化的运行时堆模型。

[0094] 运行时堆模型

[0095] 经典的数据流图常用于需求分析阶段。软件利用数据流图由抽象到具体、逐层分解待开发的软件系统。数据流图为一个有向图，包含了两种不同类型的边和多种不同的节点用以描述数据从一个初始节点出发，进行层层计算，最后得到最终结果。在运行时，数据流图的某个节点本质上对应了一组内存数据的变化。因此，本发明的应用的行为运行时模型的堆模型重点关注内存数据的变化，而不是变化的操作。本发明所述的运行时的堆模型仅从内存数据变化角度对应用运行时的内存的堆区进行建模。

[0096] 运行时堆模型是由一组内存数据的初始值和在一段时间内发生堆的内存修改活动的集合 M＝；

[0097] 其中，D＝{d1，d2，…，dn}，为一组内存地址的初始值，A＝{i1，i2，…，in}，为引起内存数据变化的活动，T＝{t1，t2，…，tn}，为时间戳。

[0098] 对于不同的面向对象编程语言，它们会提供不同的应用编程接口以实现内存的动态分配和回收。例如C/C++ 语言，通过在标准库函数中提供malloc和free函数实现内存的分配和回收；而Java语言，通过new关键字可创建新的对象，实现内存的分配，通过自动的垃圾回收机制，实现对内存的回收。

[0099] 针对本发明的技术问题，接下来对如何构造本发明实施例的上述运行时模型进行详细阐述。

[0100] 参照图4，示出了本发明一种构造终端应用行为的运行时模型的方法的步骤流程图，所述方法包括构造所述终端应用行为的运行时栈模型的步骤和构造所述终端应用行为的运行时堆模型的步骤。

[0101] 所述构造所述终端应用行为的运行时栈模型的步骤具体可以包括：

[0102] 步骤S401：在所述终端应用运行时，获取所述终端应用的内存中真正执行的代码，并对所述真正执行的代码进行抽象，生成控制流图；

[0103] 步骤S402：针对所述控制流图，将需要监测的控制流图输入至预设的行为解释器；

[0104] 步骤S403：利用所述行为解释器对所述需要监测的控制流图进行解释执行，生成所述终端应用运行时的栈活动；

[0105] 步骤S404：在所述终端应用运行时，生成所述栈活动的控制流间的依赖关系，得到所述终端应用行为的运行时栈模型；

[0106] 在本发明实施例中，构建运行时栈模型包含以下三个基本要素：1)控制流图：包含了所有可能的活动和所有可能的活动关系，是程序的源代码，或是中间代码的抽象表示；2)运行时发生的一组活动，即控制流图中的一条路径，可视为栈模型中的一组节点；3)运行时发生的活动之间的关系，即栈模型的边。

[0107] 栈模型的构造需要着力解决三方面的挑战：第一，由于编译优化、运行时即时编译等技术，应用的源代码和编译生成的字节码可能与运行时内存中的代码段不同，如何保障控制流图与运行时的活动能正确映射；第二，如何生成不同粒度的活动以描述复杂的应用运行状态的改变；第三，由于现在的应用大量使用多线程编译以保证界面的响应速度，提升用户体验，如何生成运行时控制流之间的依赖关系。针对以上三个挑战，本发明实施例的第一步是通过在运行时获取内存中真正执行的代码，对当前执行的代码进行抽象，可以保证控制流图与运行时活动的准确映射。第二步提出一种行为解释器，该行为解释器以上步生成的控制流图作为输入，对其进行解释执行。第三步，解释执行过程中生成应用运行时的活动；而模型生成的最后一步，是在运行时生成控制流之间的依赖关系。

[0108] 下面，对运行时栈模型的生成步骤作进一步概述。

[0109] 一、控制流图生成。在应用的开发过程中，由于安装包发布会包含应用编译过的中间代码，因此，出于保护的目的，应用通过会使用各种混淆工具对生成的中间代码，例如安卓下的dex字节码，进行混淆。这会导致直接提供的源代码难以与应用运行时执行的活动进行映射。这些混淆过的代码会通过应用运行时环境进行加载执行。例如，在安卓应用的Dex字节码会在Android Runtime(ART)中执行。本发明采用修改应用运行时的方式获取应用的字节码。这种方式可以带来两个好处，一是无需提供与匹配的中间代码或源代码，提高了方法的实用性；二是在应用运行时生成的中间代码可保证与执行的活动的一致性，从而保障了控制流图与运行时的控制流的匹配。

[0110] 具体的，控制流图的生成：

[0111] 根据指令类别得出基本块的边界，一条指令是基本块的开始当且仅当：1)它是一个方法的第一条指令或2)有某一条指令可能跳转至当前指令。而一条指令是基本块的结束，当且仅当：1)它是方法的返回，如return，throw指令；或者2)它是一条跳转指令，如if，goto，或者该指令可能抛出异常。在界定好基本块的起始和结束后，本发明的控制流图生成算法分为以下三个步骤：

[0112] 计算所有跳转指令(包括显式跳转和异常跳转)的目标地址，将该地址的指令标记为可作为基本块开始的指令。

[0113] 初始化基本块队列为空，并由低至高遍历每一条指令，若该指令是基本块的开始，或是当前基本块为空，则新建一个基本块，将其作为当前基本块，并放到基本块队列末尾；若该指令是基本块的结束，则将其放到当前基本块内，并新建一个基本块作为当前基本块，并放到基本块队列末尾。

[0114] 遍历整个基本块队列，建立基本块的前趋和后继关系：一个基本块的最后一条指令如果是可跳转的指令，则在该基本块和跳转的目标基本块添加一条有向边；如果一个基本块不是return或goto指令，则与队列中的下一个基本块添加一条有向边。

[0115] 二、按需重分配控制流图的执行，以及由行为解释器生成应用运行时的活动。在应用运行时，每一个线程会对应一条控制流，每一条控制流可视为一组有序的活动。这组活动可视为上步生成的控制流图的一条路径。因此，本发明提出一个适用于监测程序执行的行为解释器。根据配置，将需要监测的控制流图分配至行为解释器中执行。如果将每一条指令的执行都对应于一个活动，会导致这组指令序列变得规模极大而难以处理：1、数值计算语句难以与语义对应；2、程序循环产生的大量活动会湮没真正的处理逻辑。因此，本发明将活动分为数值计算、分支控制、方法调用等，并在行为解释器中实现了提供多种粒度的活动筛选的活动筛选器，以便生成合适的栈模型。

[0116] 在本发明实施例的构造方法中，包括类筛选器和活动类型筛选器；其中，所述类筛选器基于包和类名正则匹配的粗粒度筛选，用于去除开发人员不关心的程序活动；所述活动类型筛选器基于活动类型的细粒度筛选，用于去除与开发者不关心的活动类型。

[0117] 其中，所述栈活动的活动类型包括方法开始与方法结束，字段读，数组读和同步指令；基于上述活动类型，步骤S403的实现方法包括：

[0118] 利用对所述终端应用的应用行为具有监测功能的行为解释器对所述需要监测的控制流图进行解释执行，获得所述终端应用运行时的活动；

[0119] 根据所关注的类，利用所述类筛选器对所述终端应用运行时的活动进行粗粒度筛选，生成由所述类引起的栈活动；

[0120] 针对所述栈活动的活动类型，利用所述活动类型筛选器对所述栈活动进行细粒度筛选。

[0121] 本发明实施例通过灵活地指定特定的包、类及指令类型，可以生成所需的栈模型，提高了易用性。

[0122] 为提高构造模型的准确性，本发明把执行方法调用指令的开始和结束都视作活动并进行记录。从Java 的方法调用上看，其调用显现的是一种树状的结构：对于某一个方法调用，在执行过程中可能又发生多个方法的调用。因此，为了保证生成的序列能还原成这种树状的结构，本发明以下标s表示方法调用开始的活动，下标e表示方法调用结束的活动。对于上述示例的两种程序执行情况会对应为两个不同的序列：

[0123] 1)如果calculate都是在doInBackground中被调用，则序列为ds→cs→ce→cs→ce→de；

[0124] 2)如果有一个calculate是自身的递归调用，则序列为ds→cs→cs→ce→ce→de。

[0125] 将生成的活动序列重新构造成树状结构的方法调用可采用调用树构建算法。算法的过程其实是模拟 Java虚拟机执行流程的过程。算法开始时，每一个线程的活动对应一个actions对象。对于每一个线程，维护两个数据结构：1)为已执行过的子控制流队列；2)为当前控制流的执行的函数栈。按序遍历actions 中的各个活动，并进行以下判断：

[0126] 如果没有当前控制流，则实例化一个，并压入函数栈。

[0127] 如果当前活动为方法开始类型，则实例化一个新的子控制流，将新实例化的子控制流压入函数栈，并添加进当前控制流的活动队列。最后将当前控制流设置为刚实例化的子控制流。

[0128] 如果当前活动为方法结束类型，则进行弹栈操作。如果弹栈结束后，函数栈为空，则说明当前线程的子控制流已经执行完毕，可以添加进已执行的子控制流队列中；如果函数栈不为空，则当前的控制流设置为函数栈顶的那个子控制流。

[0129] 否则将当前活动压入子控制流的活动队列中。

[0130] 类似于方法调用指令，其他类型的指令都可以有指令开始执行和执行结束两种活动。因为这些指令具有原子性，即在同一线程中，指令执行的开始与结束之间具有不会发生其他活动，所以，对于这些类型的指令仅需有指令开始执行的活动即可。

[0131] 在具体实现中，运行时的活动表示实现可以有存储形式：可以是内存中的对象，也可以是持久化的二进制文件或ASIC II文件。本发明中，运行时堆模型可以巴科斯范式的形式表示。

[0132] 本发明通过一个活动的序列化与反序列化的机制来实现这种伸缩性。在运行时模型生成时，将运行时模型中的活动序列存放于可配置大小的缓冲区中，当活动数量超过预设时，则将缓冲区的活动进行序列化，并持久化到本地存储中。

[0133] 三、控制流之间依赖关系的生成。多线程编程已成为安卓应用开发中重要的一部分。利用多线程编程可实现用户界面的高效响应，和多项计算任务的并行加速。多线程编程中的线程同步和相互唤醒(称之为线程依赖关系)，可抽象为对于栈模型中控制流之间的边。线程的依赖关系是与时间相关的一个关系：在某时刻，主线程可以向后台线程发送计算任务，此时为后台线程执行的活动依赖主线程的活动；而在下一时刻，后台线程完成计算任务后，通知主线程进行界面更新；此时，为主线程执行的活动依赖后台线程的活动。因此，本发明对这些线程间依赖关系进行分类，并对不同类型的依赖进行处理，以在运行时生成这些依赖关系。

[0134] 在本发明实施例中，所述依赖关系包括同步依赖和通信依赖。线程间利用Java语言规范中提供的线程状态转移相关的方法，如Thread.join，Object.wait，Object.notify等实现多个线程之间的协同，本发明称这些线程间的依赖关系为同步依赖。而线程间利用对象，实现多线程间的协同的，本发明称这些线程间的依赖关系为通信依赖。在实际开发中，应用开发者会复用框架层提供的各种多线程编程类，以提升开发效率。框架层虽然提供良好语义的应用编程接口给应用层的类，屏蔽了实现细节，但是为了保障框架的性能和鲁棒性，往往实现较为复杂。利用这些编程框架实现的程序，在运行时线程之间既可能是同步依赖，也可能是通信依赖。

[0135] 以图5中的BackgroundTask.execute方法调用的开始至onPostExecute方法调用的结束为例，全局共有两个活跃的线程，它们之间相互发生了同步依赖和通信依赖。该过程的方法调用如图6所示：图中的上下两条轴分别表示前台线程和后台线程随时间变化的方法栈的情况；图中的框表示方法，其中灰色的框表示框架层的方法，白色的框表示应用层的方法，即应用开发人员实现的方法；图中的箭头表示线程间的依赖关系，其中实线箭头表示同步依赖，而虚线箭头表示通信依赖。在图6所展示的方法调用过程中， Backgro undTask .execute 方法在执行过程中 (活动①)会 调用
ThreadPoolExecutor.execute方法，进而调用后台线程对象的start方法(活动②)，进一步会引起后台线程的run方法的调用(活动③)。在后台线程的run方法开始执行后，经过层层调用，最终会调用BackgroundTask.doInBackground方法(活动④)，在该方法的执行过程，除了会调用calculate方法进行计算任务外，还会调用AsyncTask.publishProgress方法(活动⑤)，以使前台线程调用onProgressUpdated方法(活动⑥)对界面进行更新。随后，后台线程结束计算任务后，会再次用类似的方式通知前台进程当前任务已结束。其中，活动②与活动③之间为同步依赖，而活动⑤与活动⑥之间为通信依赖。

[0136] 同步依赖的生成：

[0137] 为了实现同步依赖的生成，Java中与同步依赖相关的方法都会被认为是需要收集的活动。这样运行时栈模型就能收集到如表1的各种与同步依赖相关的活动。

[0138] 对于存在同步依赖的两个活动，后发生的活动可能是一个方法的结束或是一个方法的开始，据此，可将同步依赖分为两种，并进行分别处理：

[0139] 对于一个方法的结束依赖另一个方法的结束的情况，利用时间戳由后往前寻找其他线程中可匹配的活动，如果找到，则对应于一个同步依赖关系。例如Thread.join的结束依赖Thread.run的结束；Object.wait的结束依赖Object.notify的结束，对于如Thread.join或Object.wait的方法结束活动，就可利用时间戳由后往前寻找其他线程中可匹配的活动。如果找到了，则对应于一个同步依赖关系。

[0140] 在生成控制流间的同步依赖关系时，对于一个方法的结束依赖另一个方法的结束的情况，利用时间戳由后往前寻找其他线程中可匹配的活动，如果找到，则对应于一个同步依赖关系；例如Thread.join的结束依赖Thread.run的结束；Object.wait的结束依赖Object.notify的结束，对于如Thread.join或Object.wait 的方法结束活动，就可利用时间戳由后往前寻找其他线程中可匹配的活动。如果找到了，则对应于一个同步依赖关系。

[0141] 对于一个活动的开始依赖另一个活动的结束的情况，先对当前线程进行检查，如果该活动为当前线程中的第一个执行的活动，则该活动是依赖另一个线程结束活动的，否则该活动仅是正常的方法调用，并不依赖另一个线程的活动。例如Thread.run的开始依赖Thread.start的结束，由于在Java中，一个活动的开始(即某个方法的调用)可以在任意地方进行任意次数，包括Thread.run方法。因此，要判断一个 Thread.run方法的调用是否依赖Thread.start方法的调用不能直接根据时间戳由后往面查找匹配，需要先对当前的Thread.run进行检查：如果该活动为当前线程中的第一个执行的活动，则它是依赖另一个线程 Thread.start结束活动的，否则它仅是正常的方法调用，并不依赖另一个线程的活动。

[0142] 通信依赖的生成：

[0143] 线程间不基于Java提供的能实现线程状态转移的方法，实现多线程间的协同的，本发明称这些线程间的依赖关系为通信依赖。

[0144] 以图6中活动⑤与⑥为例，其具体实现是基于MessageQueue的next方法与enqueueMessage方法。在这过程中，如果前台线程的待处理队列中还有元素排队等待处理的话，则活动⑤引起的enqueueMessage 方法，仅会将当前任务添加到该队列中，并不会显式地唤醒前台线程。但从逻辑上，可认为对于某一 MessageQueue对象而言，其next方法所返回的Message对象，会被Handler以参数的形式传入 dispatchMessage方法中，因此可认为MessageQueue的next方法的结束依赖 MessageQueue.enqueueMessage，并且该依赖是以参数Message为匹配对象的而不是MessageQueue。

[0145] 在生成控制流间的通信依赖关系时，对所有与活动间通信依赖相关的类进行总结，并将这些类的相关方法与线程依赖相关的方法一起作为生成通信依赖的知识库。该知识库亦可支持应用的进行自定义。

[0146] 参照图4，所述构造所述终端应用行为的运行时堆模型的步骤具体可以包括：

[0147] 步骤S405：在所述终端应用运行时，生成堆区的初始状态；

[0148] 步骤S406：生成堆操作活动，得到所述终端应用行为的运行时堆模型。

[0149] 在本发明实施例中，运行时堆模型包含以下基本要素：1)一个堆区的初始状态；2)运行时发生的一组影响堆区数据的活动。本发明首先给出堆区初始状态的描述方法，并在运行时生成符合该表示的堆数据初始状态。其次，本发明给出了堆操作活动的描述方法，并在运行时构造运行时堆模型中的活动。最后，给出了堆区初始状态与堆操作活动的BNF表示。

[0150] 下面，对运行时堆模型的生成步骤作进一步概述。

[0151] 一、是对堆区初始状态的生成。堆区的初始状态为开始时刻的堆区数据的状态。在Java虚拟机规范中，仅对堆区给出了最简单的描述：堆是运行时用于分析所有类实例和数组的区域，该区域由一个自动存储管理系统(即垃圾回收器)进行管理。堆中的对象从来都不会显式地回收，而是会由垃圾回收器自动回收。堆区的初始状态可视为某一时刻堆区数据的快照，因此，如果在生成内存堆区数据状态时，如果有别的线程继续执行，并进行堆区操作(例如创建对象、执行垃圾回收等)，就会破坏初始状态的原子性。因此，本发明首先给出了一种描述堆区初始状态的BNF表示，并在生成堆区数据初始状态时采用“冻结”堆区数据的方式，保证了初始状态生成过程的原子性。

[0152] 二、堆模型中的活动的生成。在应用运行时，Java的垃圾回收器可以产生回收内存的活动。除了这些活动外，其他活动可视为运行时栈模型中的活动的一个子集。一方面，如果将每一个会影响堆区的数据的操作都对应于一个活动，会导致这组活动数量变得极大而难以处理。例如某应用中存在大文件的I/O操作，如果全部操作都以活动的形式记录下来，则活动的数据量将不小于大文件的数据量；另一方面，类似于控制流模型，可能仅关注部分类、方法的执行，生成过大的堆模型反而难以分析。这里扩展了活动的描述使其支持描述垃圾回收活动，类似于运行时栈模型，提供多种粒度的活动选择筛选选项，以便生成合适的堆模型。生成的堆模型详实地描述了所关心的对象的变化情况，因此，利用基于时间戳的堆对象状态查询算法可以查询堆对象在任意时刻的状态。

[0153] 接下来，采用一个具体的例子对运行时堆模型建模过程进行介绍：

[0154] Java堆区的数据仅包括实例化的对象和数组。对于应用而言，对象的创建可能发生在应用层代码或框架层代码，因此，我们将应用中的对象分为应用层和框架层，以图5实现的代码为例，在触发点击事件前，堆区的对象如图7(a)所示。图中每一个圆表示一个对象，而圆与圆之间的连线表示引用关系。图7(a) 中与应用业务逻辑相关对象有展示界面FloatActivity、可触发后台计算任务的按钮Button、待处理的后台任务BackgroundTask、用于展示任务计算结果的TextView和点击事件监听对象OnClickListener。除了与业务逻辑相关的对象，还有许多框架层的对象。例如，框架层一个MessageQueue对象。实现后台处理任务可以通知前台进行更新。图7(a) 、图 7(b) 中的实线箭头表示对象的引用关系，即对象A如果有某个字段指向另一个对象B，则由A至B有一条有向连接；虚线箭头表示在整个事件的处理过程中，存在过对象的引用关系，而在结束时，已没有引用关系了。

[0155] 在事件触发过程中，会创建如下对象：在BackgroundTask.execute方法在执行过程中，会调用 ThreadPoolExecutor.execute方法，此时，由于是该对象首次执行execute方法，该对象会新建一个Thread 对象①，为后台执行的线程；在调用后台线程对象的start方法之后，进一步会引起后台线程的run方法的调用并正式开始调用doInBackground方法。在该方法中 ，除了会 调用cal culat e方法进行 计算任务 外，还会 调用AsyncTask.publishProgress方法，在执行该方法前，传入的参数会被封装到新创建的Integer[]对象中②；而在方法执行过程中，则是会新创建一个Message对象③，并放至全局的一个MessageQueue队列中。当前台线程接收到该Message，并执行
onProgressPublished时，会创建一个StringBuilder对象④，以构造setText所需的参数，并通过StringBuilder.toString方法实例化出一个新的String对象⑤。而当 
doInBackground方法执行结束前，又会创建一个新的StringBuilder对象⑥，并且计算出返回值String对象⑦。该String对象会被再次封装到一个新创建的Message对象⑧中，并通知前台线程执行 onPostExecute方法。上述过程已对部分步骤进行简化，在实际运行中会存在更多的对象创建。例如，Thread 对象并不是直接依赖BackgroundTask而是会经过FutureTask，Callable等对象的层层封装，间接依赖 BackgroundTask对象。在该过程结束后，对象①至⑧都可能会在某次垃圾回收中被回收。

[0156] 在堆模型中，本发明将图7(b)中的每个对象的实例化、字段赋值以及回收都视为一个活动。类似运行时栈模型的表示，下面本发明优选以巴科斯范式的形式给出一种运行时堆模型的表示。

[0157] 其中，DataAction与运行时栈模型构造关键技术中所描述的ControlAction类似，ControlAction用于描述执行的指令情况，而DataAction用于描述内存数据的变化情况。Number表示数字类型，可以是数值，也可以是内存地址；String表示字符串类型。从上述表示中，可以发现，模型的复杂度主要取决于：1)初始状态中对象的数量；2)堆区数据活动的数量。

[0158] 在安卓的具体实现中，其堆区可分为三个子区域：1)应用堆(App Heap)，当前应用实例化对象和数组时使用的内存区域；2)镜像堆(Image Heap)，装载了当前应用镜像的内存区域；3)孵化堆(Zygote Heap)，系统启动时加载的系统类存放的内存区域。本发明所述的初始状态主要关注运行时变化最大的应用堆。对于安卓平台上的Dalvik虚拟机和ART虚拟机而言，它们实现了可以在任一时刻，将当前应用堆的状态以文件的状态保存下来(堆转储操作)。该文件是一种私有的内存镜像格式，通过安卓开发者工具可将其转换为符合J2EE平台规定的hprof格式。

[0159] 然而直接基于现在的应用堆转储仅能反映某一时刻的堆状态，难以实现反映一段时间内的任意时刻的堆状态。首先，执行一次堆转储操作需要挂起所有线程，耗时高，生成的文件从几十兆字节至几百兆字节不等，难以通过每隔一段时间执行一次堆转储操作实现反映一段时间内的任意时刻的堆状态。其次，执行堆转储操作并不会转储那些被回收器回收的对象，包括那些在执行过程中产生的临时对象，然而对于一个执行过程而言，产生的临时对象对描述过程的执行也十分重要，例如，图7(b) 中的对象②至⑧都是临时对象，这些对象不能直接利用堆转储进行持久化。

[0160] 在本发明实施例中，所述构造所述终端应用行为的运行时堆模型的步骤包括：所述终端应用运行时的活动包括实例化活动、修改活动和回收活动。

[0161] 其中，实例化活动(NewAction)，即创建新的对象、新的数组的活动，可对应于字节码中的newInstance、 newArray等指令在运行时的执行。

[0162] 修改活动(ModifiyAction)，即修改类的静态字段、对象的字段、数组的元素的值的活动，可对应于字节码中的sput，iput，aput等指令。

[0163] 回收活动(GCAction)，即执行垃圾回收时，对堆中的对象产生影响的活动。针对回收活动，垃圾回收机制是一种自动的内存管理机制。当一片内存中的数据不再会被用到时，会予以回收释放，以便于进行下次的分配。具体的垃圾回收算法实现有引用计数法、可达性分析算法等。

[0164] 回收活动在运行时是对应不到dex字节码的指令的，因为它的具体实现是在虚拟机层面。回收活动可进一步细分为清除活动和压缩活动。所谓清除活动就是清除不再需要的对象；而所谓的压缩活动则是对活跃的对象整理到连续的内存空间上，以避免分配大内存时由于碎片化导致分配失败的情况。

[0165] 除此之外，除了实现的应用层的代码会创建对象以外，框架层的代码也会创建大量对象，在某些情况下，甚至会是几倍于应用层创建的对象。需要提供一种堆模型复杂性管理的机制，以保证生成的运行时栈模型的准确性和易用性。与前述两级筛选机制类似，对于堆模型的活动生成，也有一个两级的筛选机制。基于包和类名正则匹配的粗粒度筛选和基于活动类型的细粒度筛选。

[0166] 本发明优选提供了6种堆操作活动，所述堆操作活动的活动类型包括对象实例化，数组实例化，对象字段写，数组元素写，清除活动和压缩活动；

[0167] 所述生成堆操作活动的步骤包括：

[0168] 根据所关注的类，利用所述类筛选器对所述终端应用运行时的活动进行粗粒度筛选，生成由所述类引起的堆操作活动；

[0169] 针对所述堆操作活动的活动类型，利用所述活动类型筛选器对所述堆操作活动进行细粒度筛选。

[0170] 针对行为反射在控制上面临的挑战，即本发明背景技术所阐述的第二个挑战，支持指令级的行为控制，由于不是本发明的重点，在此不多赘述。

[0171] 下面，采用一具体实例验证本发明实施例对终端应用行为监测的有效性。

[0172] 针对移动互联网中广泛使用的安卓移动应用，给出行为反射框架的原型系统实现：Reflectall。Reflectall 的全称为Reflection at low level interpreter，具有两重含意，一是基于底层的行为解释器实现的反射；二是它可以监测和控制指令级别的应用行为。Reflectall基于安卓操作系统开源项目。为了实现移动应用行为的监测与控制，Reflectall平台可分为行为运行时模型构造子系统、模型分析与代码生成子系统和运行子系统，实现了行为反射框架中的监测和控制。

[0173] 参照图8，为Reflectall模型生成子系统架构示意图。Reflectall的行为运行时模型构造子系统实现了移动应用行为运行时模型的构造，其核心实现在系统层，由优化-反优化器、行为解释器、模型构建和接口层四个模块组成。这个四个模块实现了移动应用行为的监测与控制。

[0174] 其中，优化-反优化器：安卓运行时环境可加载CPU可直接执行的原生指令。因此，需要将以原生指令切换为字节码，即反优化，并通过行为解释器进行解释执行，从而实现对移动应用运行时活动的监测。移动应用由于其复杂性，难以监测移动应用执行中的所有活动，因此引入了一个两级筛选机制。优化-反优化器实现了两级筛选机制中的类筛选机制，通过优化-反优化器，可以按需地将待监测的类反优化为字节码，并进行解释执行；而对于未被监测的类，则仍然在原生执行器中执行。优化-反优化器会在如下三种情况下触发：1)收到开始监测的命令时，会根据所配置的参数，对当前已经加载的类的方法进行筛选，并进行反优化；2)收到结束监测命令时，会对当前已反优化后的类进行再优化，令其重新进入原生执行器中执行；3)类链接器加载新的类时，会对类进行类似于情况1)中的筛选和反优化过程。为了保证程序执行的正确性，反优化的过程需要和部分垃圾回收算法一样，暂时挂起所有线程的执行，待反优化执行结束后，再恢复线程的执行。通过这种局部反优化，并保持解释执行与原生执行共存的状态，可以大大减少监测的性能开销。

[0175] 行为解释器：行为解释器是解释执行dex格式字节码的解释器，能在解释执行的过程中，监测当前的程序执行中发生的活动。移动应用行为运行时模型中的活动大多是由行为解释器生成。除了行为解释器所生成的活动，垃圾回收器也可以生成部分活动——垃圾回收活动。行为解释器还实现了两级筛选机制中的活动筛选机制，可根据配置的活动收集粒度产生不同种类的活动。

[0176] 模型构建器：行为解释器与垃圾回收器所产生的活动会在模型构建器中构建。当运行时产生的活动较多时，会导致内存占用较大。因此，模型构建器实现了在线和离线的模型构建。当活动较少时，模型构建器运行于在线的模型构建模式时，当活动数量达到配置的阀值，模型构建器会将当前已产生的活动序列持久化，并以文件的形式持久化至存储。

[0177] 接口层：对优化-反优化器、行为解释器和模型构建器所提供的功能进行封装。同时也提供反序列化活动所需的接口，例如根据地址查找对象和给定对象转换为地址等。

[0178] 本发明实例所实现的原型中，可以生成两种移动应用行为运行时模型：1)包含了运行时数据依赖的精细化模型；2)不包含运行时数据依赖的精简模型。基于系统层的实现，在框架层，Reflectall包括一组行为反射接口，可监测不同粒度的应用的活动，生成不同粒度的应用行为运行时模型；一组远程调试连接接口，可控制应用活动监测的开始与结束。在应用层，对框架层的接口进行封装，实现了一个安卓应用，可以以Web服务的形式对外提供远程调试接口。

[0179] Reflectall的分析与代码生成子系统为浏览器-服务端架构。分析与代码生成子系统实现了：

[0180] 版本管理：利用git管理不同版本的移动应用与互操作接口。同时支持服务器端编译，并利用客户端的接口管理应用将编译好的dex字节码推送至客户端。

[0181] 栈模型可视化：提供了一个树状的视图，并支持基于关键字的数据依赖沾染分析。

[0182] Reflectall的接口运行子系统在安卓开源项目的框架层上添加了一个行为反射类加载器，如图9所示，为本发明示例Reflectall的接口运行子系统的结构示意图。当应用进程启动时，会检查是否有可加载的行为反射接口字节码文件。如果存在适合当前应用的行为反射接口字节码文件，则通过行为反射类加载器将其加载进应用进程，同时，利用Binder通信机制向接口管理应用注册当前应用提供的互操作接口。接口管理应用提供了接口转发、状态检测等服务。调用者进程通过接口管理应用可实现与指定应用互操作。

[0183] 具体验证时，本发明以一个包含69个开源安卓应用的开源应用集和一个包含39个闭源应用的闭源应用集对Reflectall模型生成的性能进行验证。

[0184] 移动应用行为运行时模型的构造开销与模型的活动数量正相关——应用越复杂、活动越多，生成行为运行时模型的开销也就越大。相比闭源应用，开源应用在实现的复杂程度远低于闭源应用。开源应用集的类的数量的中位数为58个，方法的数量的中位数为246个；75％的开源应用集中的应用的类的数量不大于167个；方法的数量不大于859个。而闭源应用集中的应用，应用的类的数量的中位数为14266，方法的数量的中位数是87717个，是开源应用集中对应的数值的245倍和102倍。实验所使用的硬件配置如下：1)使用Android智能手机红米2A，它的CPU是1.5GHz，内存为1GB，运行安卓操作系统版本为5.1.1。 2)实验使用一台普通PC作为远程控制端控制手机进行实验，该PC的CPU为Intel酷睿i5 3427U (1.8GHz)，内存为4GB，运行OSX 10.11操作系统。

[0185] 目前，监测应用执行流程的方法除了本发明所述的实现行为解释器的方式外，还包括运行时元消息绑定和编译时字节码重构两种方式。表2给出了三种方式所支持的活动监测的粒度。Reflectall在活动监测的粒度上比基于运行时绑定的方法要更细：支持到指令级别的活动监测；同时也比基于字节码重构的方法适应范围更广：基于字节码重构的方式需要修改原应用的编译流程，难以直接在经过混淆、加固的应用上使用。

[0186] 表2：监测程序执行流程的方法比较

[0187]  执行流程监测的粒度 是否需要字节码
Reflectall 支持方法级别、指令级别的监测 不需要
基于运行时绑定的方法 支持方法级别的监测 不需要
基于字节码重构的方法 支持方法级别、指令级别的监测 需要

[0188] 本发明在实验一对比Reflectall与基于运行时绑定的方法在监测程序执行流程方面的性能。在实验二对比Reflectall与基于字节码重构的方法在监测指令粒度的活动的性能。

[0189] 实验一：对比运行时元消息绑定的方法

[0190] Xposed框架是一款可以在不修改APK的情况下监测和修改程序运行行为的框架服务(rovo89,2012)。类似于Reflectall，Xposed框架也是在安卓操作系统的系统层上进行修改。Xposed框架实现了元消息模型的行为反射，即Xposed在应用运行时根据配置对指定的方法绑定相应的元对象。在后续的执行中，这些绑定了元对象的方法在执行前、执行后会调用元对象中的before、after方法。本文利用Xposed框架，实现了与Reflectall类似监测程序执行的Xposed模块。本节以应用启动时间作为指标，在两台硬件配置相同的红米2A手机上，分别部署了Reflectall和基于Xposed的监测模块，安卓操作系统均为5.1.1。通过以下6个不同的实验场景，比较Reflectall与基于Xposed框架的方法在开源应用集和闭源应用集上监测应用的所有应用类执行的性能，如表3所示。在每个场景下，每个应用启动10次，实验的结果如图10(a) 、图 10(b) 所示。

[0191] 表3：监测程序执行流程的方法比较

[0192]

[0193] 图10(a)为开源应用集上的实验结果。在开源应用集中，69个应用在上述6个场景下均能正常启动。图10(a)中的实线部分为部署了Reflectall的三个场景；虚线部分为部署了Xposed框架的三个场景。在不监测程序执行流程的情况下，部署Reflectall的手机(场景1)平均启动时间为392毫秒，而部署了Xposed 框架的手机(场景3)的平台启动时间为449毫秒。这是由于Xposed框架的实现即便不绑定元对象，也在应用加载时会有一定的开销。而Reflectall的优化-反优化器实现了在不监测时，所有代码均在原生执行器中执行。在场景
2下，Reflectall的平均启动时间为486毫秒，相比不监测情况(392毫秒)，额外开销为23％；
而基于Xposed框架的方法，在场景2下的平均启动时间高达2078毫秒，相比不监测情况(449 毫秒)，其额外开销为368％。而在生成更复杂的行为运行时模型时(场景3和场景6)，Reflectall的额外开销仅为27％，而基于Xposed框架的方法高达477％。

[0194] 图10(b)为闭源应用集上的实验结果。在不监测的场景下，相比于实现简单的开源应用，闭源应用的平均启动时间为936毫秒(Reflectall)和1010毫秒(Xposed)。而在场景2下，由于应用的复杂性，Reflectall 有3个应用无响应，剩余的36个应用的平均启动时间为1601毫秒，相比不监测的场景(936毫秒)额外开销为71％。而场景4下有22个应用无响应，剩余的17个应用的平均启动时间为4593毫秒，相比不监测的场景(1010毫秒)，其额外开销为
354％。而在生成更复杂的行为运行时模型时(场景3和场景6)， Reflectall的额外开销为
98％，而基于Xposed框架的方法高达470％。

[0195] Reflectall生成行为运行时模型的性能在开源应用集上和闭源应用集的差异较大，这是由于闭源应用集中的应用实现更为复杂，因此生成的模型规模也更大，可能引起多次的垃圾回收和活动持久化过程，由此带来了更多的性能开销。而基于Xposed的方法在这两个应用集中开销接近，原因在于利用Xposed进行监测时，有22个应用无响应，占整个闭源应用集的57％。Reflectall的性能开销比基于Xposed框架的方法低的一大原因是基于Xposed框架的方法的所使用的编程语言是Java，而Reflectall所实现的行为解释器编程语言为C++。当应用的执行流程较复杂时，基于Xposed框架的方法对内存的分配和回收会比 Reflectall更加频繁。通过上述实验表明，本发明Reflectall的这种实现方式可以处理更复杂的应用。

[0196] 实验二：对比基于字节码重构的方法

[0197] 很多常用的Java库都用到了字节码重构框架。字节码重构的一个很重要的使用场景就是程序分析。例如，流行的bug定位工具FindBugs在底层就使用了ASM来分析字节码并定位漏洞。另外一个常见的使用场景就是利用字节码重构生成程序的代码覆盖率报告，例如Emma(Roubtsov,2005)、JCover(JCover, 2017)。Reflectall所生成的精简模型可转换为代码覆盖率报告。本实验将对比Reflectall与Emma在生成代码覆盖报告上的区别。由于基于字节码重构的方法不适合应用于仅有应用安装包的闭源应用。因此，这部分的仅针对开源应用集进行。本实现仍以应用启动时间作为指标，在两台硬件配置相同的红米2A手机上，分别部署了Reflectall和未修改的安卓系统，安卓操作系统均为5.1.1。本实验在部署了Reflectall的手机上安装原版应用；在未经修改的安卓手机上安装经过Emma插桩过的应用，在以下3个不同的实验场景，比较Reflectall与Emma生成开源应用集上生成代码覆盖报告的性能。在每个场景下，每个应用启动10次，实验的结果如图11所示。

[0198] 实验结果表明，Reflectall与Emma的应用平均启动时间接近，平均启动时间为442毫秒和455毫秒，额外开销分别为13％和16％。但是从生成的代码覆盖信息上，Reflectall要比Emma更丰富。表4给出了 Reflectall在代码覆盖报告的监测粒度和部署运行的区别。Emma对块覆盖的报告可能存在不准确，并且不支持分支执行次数，而Reflectall基于行为解释器可以保证覆盖报告的准确性，同时也实现了对分支指令(如If-gt、Packed-Switch)的各个分支的执行次数的统计。另一区别是Emma需要进行一定配置，以对字节码进行重构，并且重构之后需要重打包；而Reflectall不需要这些配置，也不会改变移动应用的编译流程。因此，Reflectall比Emma这类基于字节码重构的工具更具易用性和实用性。

[0199] 表4：Reflectall与Emma的监测粒度对比

[0200]对比类别 Emma Reflectall
类覆盖 支持 支持
方法覆盖 支持 支持
块覆盖 部分支持 支持
分支覆盖 部分支持 支持
行覆盖 支持 支持
分支执行次数 不支持 支持
指令覆盖 不支持 支持
是否需要字节码 需要 不需要
是否需要重打包 需要 不需要

[0201] 综上，本发明提供的一种构造终端应用行为的运行时模型的方法，能将应用的执行可视为编程语言框架(例如解释器、虚拟机)，根据应用的代码段，对内存进行读写操作。什么样的方法被执行，可对应为编程语言框架在栈上的操作；什么样的对象数据被修改，则可对应为编程语言框架对堆上的操作。实现了对终端应用应用行为的灵活、完整的监测，为后续实现对终端应用应用行为的指令级控制提供了技术保障。依据该方法所设计的计算反射引擎，可作为一个单独的运行环境使用，也可被集成到各种主流的开发平台或商业软件中，给开发者提供对应用运行时监测的基本能力。

[0202] 上述实施例仅为优选实施例，并不用以限制本发明的保护范围，在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。