Android动态切片外文翻译资料

英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

Android动态切片

摘要动态程序切片对于从测试到调试到安全性的各种任务都很有用。以前的切片方法针对的是传统的桌面/服务器平台，而不是像Android这样的移动平台。由于其异步回调结构和IPC（进程间通信）重、传感器驱动、对时间敏感的平台特性，对基于事件的移动系统进行切片具有挑战性。为了解决这些问题，我们引入AndroidSlicer1，这是Android的第一种切片方法。AndroidSlicer结合了一种新的异步切片方法，用于在回调存在时建模数据和控制依赖项，并使用轻量级和精确的工具；这允许对在实际手机上运行的应用程序进行切片，而不需要应用程序的源代码。我们的切片器能够处理Android支持的大量输入，而不会增加任何明显的开销。对来自Google Play的60个应用程序的实验表明，AndroidSlicer是有效的（将要检查的指令数量减少到已执行指令的0.3%）和有效的（应用程序检测和后处理的总和需要31秒）；同时，它只会带来4%的运行开销。我们提出了AndroidSlicer在移动领域的三个应用：（1）查找和跟踪导致错误/崩溃的输入部分；（2）故障定位，即查找导致错误/崩溃的指令；（3）减少回归测试套件。在另外18个流行应用上对这些应用程序进行的实验表明，AndroidSlicer对于Android测试和调试是有效的。索引术语移动应用程序，Android，动态分析

一、 导言

虽然移动平台非常成功——仅安卓就运行在20多亿台设备上[1]——但它们容易出现影响用户、开发人员和制造商的开发、测试和可靠性问题[2]、[3]。我们提出了一种通过动态切片（dynamic slicing）来解决这些问题的方法，动态切片是一种在执行过程中隔离相关代码和数据依赖关系的技术。从安全性（如污染分析）到调试（如故障定位）和测试，切片在许多情况下都被证明是有用的，但之前的切片方法并没有针对移动平台[4]–[6]。与“传统”桌面/服务器平台相比，智能手机平台有着独特的挑战和限制。这使得传统的切片方法不适用，并允许我们设计新的解决方案。首先，重建控制流是困难的，Android应用程序使用回调来异步处理事件。为了解决这个问题，我们将异步依赖的概念引入捕获控制，并将回调之间的数据依赖作为超级图中的超级节点。其次，Android应用程序对时间敏感：即使传感器输入稍有延迟，也会改变输入语义，干扰应用程序的执行。我们使用ondemand静态动态分析后，允许低开销，但精确切片。第三，Android的输入范围很广：多点触控手势、传感器、麦克风、摄像头等。在不损失精度的情况下正确捕捉这些输入是一项挑战，并会在其他工具（如Pin[7]）中带来大量开销。我们通过结合轻量级跟踪（AF wrappers）和分层抽象（supergraph）来解决这个难题。第四，Android大量使用IPC进行应用程序间和应用程序内的通信，这需要跟踪应用程序、系统调用和外部应用程序之间的依赖关系。第三节介绍了我们的模型和依赖规则。第四节描述了我们处理Android特定挑战的方法，例如传感器输入、低开销和IPC。我们的实现AndroidSlicer在第五节中有描述；AndroidSlicer在实际手机上运行的Android应用程序上工作，不需要应用程序源代码。接下来，我们将展示AndroidSlicer如何作为构建三个应用程序的基础，这三个应用程序有助于查找、修复和测试错误。首先，导致故障的输入分析，即找到与错误或崩溃相关的输入部分，并跟踪其传播到错误/崩溃站点（第VI-a节）。第二，故障定位，即查找导致错误或崩溃的代码部分（一组指令）（第VI-B节）。第三，我们展示了切片如何帮助减少回归测试的测试数量（第VI-C节）。我们的分析是健壮的和可扩展的：我们应用它们来隔离在广泛流行的应用程序中的真正的错误的原因，如SoundCloud、Etsy、K9邮件和NPR新闻。在第七节中，我们对来自Google Play的60个流行应用程序的AndroidSlicer进行了评估。其中，我们手动分析了10个应用程序，以检查AndroidSlicer的正确性。实验表明AndroidSlicer是有效的：它通常只需19.1秒就能安装一个应用程序，而在后处理过程中切片计算通常只需11.9秒。对于庞大的Twitter应用程序（字节码大小为50.6mb），切片计算最多花费293.5秒。此外，AndroidSlicer的运行时开销很低，通常为4%。最后，AndroidSlicer是有效的：它设法将大型执行（平均14491条指令）减少到对开发人员来说更易于管理的小片段（平均44条指令）。总之，这项工作作出了四项贡献：

1） 一种新的异步切片模型。

2） 一种精确的方法来分割Android应用程序，解决这个平台和环境的特定挑战和限制。

3） AndroidSlicer，一个在实际手机上运行的Android应用程序切片工具。

4） 一种减少运行时开销和处理Android支持的大量输入的新方法。

5） 三个切片应用程序，有助于Android应用程序的开发、调试和测试。

二。背景

我们首先简要介绍了程序依赖图和程序切片；接下来，我们讨论了Android平台及其基于事件的模型。程序依赖图（PDG）。PDG捕获程序的数据和控制依赖项。每个PDG边表示节点之间的数据或控件依赖关系，这些节点可以表示指令或基本块。定向数据相关边nj☆d ni表示在ni中执行的任何计算都取决于节点nj处的计算值。控制相关边njlt;c ni表示执行ni的决定是由nj做出的，即nj包含一个谓词，其结果控制ni的执行。静态PDG由所有可能的数据和控制依赖关系组成。动态PDG是一个子图，它只包含在特定运行期间执行的那些节点和边。程序切片。动态程序切片是Korel和Laski[4]提出的一种动态分析方法。指令实例s上相对于切片准则t，s，value的向后动态切片

（其中t是时间戳）包含对值有直接或间接影响的已执行指令；更准确地说，它是PDG中从切片标准开始的动态数据和控制依赖的传递闭包。切片条件表示与应用程序相关的分析需求，例如，对于调试，该条件表示导致崩溃的指令执行。安卓平台。Android软件栈包括：apps；一个名为Android Framework（AF）的中间件组件，它协调控制流，并调解应用程序之间和内部的通信，以及应用程序和较低层之间的通信；库和服务；运行时环境；2和操作系统，一个嵌入式Linux版本。Android基于事件的模型。Android应用程序没有main（）方法，而是由组件（例如，带有GUI的应用程序由名为Activities3的屏幕组成）和一个或多个入口点组成。与传统程序不同，应用程序使用事件驱动的模型来指示控制流。事件可以是用户操作（例如触摸）、生命周期事件（例如应用程序暂停时的onPause（））、传感器数据的到达（例如GPS）以及应用程序间或内部消息。所有这些特性，从外部的控制流到时间敏感的传感器输入，使得传统的切片方法不适用于Android。其中回调变量c包含回调的地址，t是创建节点的时间戳，a是活动上下文（活动的运行时状态），而Sit（常规节点）表示时间t时指令Si的实例。数据和控制依赖项分别表示为lt;.d和lt;.c。超边连接超节点，规则边连接规则节点。注意，超级节点可能包含子图（由正则节点Sit☆c Sjt或Sit☆dsjt组成）；因此是层次PDG概念。我们现在解释依赖性规则，如图1所示。表示特定时间戳t处的指令s中的寄存器vs。由于指令是PDG中的常规节点，我们将互换使用这两个术语，即st指的是时间t处的指令的确切实例和PDG节点。我们保持输出是寄存器v1，v2，hellip;，vn的序列，以及寄存器使用的回调c1，c2，hellip;，cm。跟踪输入传播。在PDG中，对于每个异步回调，我们可以通过跟踪任何寄存器vi的值的数据依赖性来创建输入传播路径。我们确定通过寄存器传播的值是否受任何应用程序输入I的影响。这对于识别由于损坏的文件或大型传感器输入（例如视频流）引起的故障特别有用。例子。我们举例说明了我们对一个实际错误的分析，这个错误是由于一个格式错误的SQL查询，在Olam中，一个翻译应用程序。7这个应用程序从一个文本框中提取一个输入字并翻译它。在图5（顶部）中，我们展示了代码的相关部分：指令的不同动态实例的数量（左侧）、实际指令（中间）和沿PDG边缘（右侧）通过寄存器v1、v2、hellip;、vn的值传播。在getSimilarItems方法中，应用程序尝试查询SQLite数据库，这会生成异常，从而导致崩溃。来自Android事件日志的异常跟踪表明查询格式不正确。PDG（左下角）指出了抛出异常的回调：与MainSearch活动中的search按钮关联的onClick事件。我们通过向后跟踪数据相关边来分析事件输入，并看到寄存器的值指向文本框editText中的输入文本。我们使用错误的寄存器引用作为切片准则来计算切片。执行片段如图5所示：我们看到，illformatted字符串存储在寄存器v1中。我们的方法通过切片反向传播v1的值，以确定它是否受到输入的任何部分的影响。反向传播从错误位置开始，即指令实例29754。该值传播到寄存器v5，该寄存器引用在指向GUI控件元素EditTextBox的v4实例上调用的getText返回值。我们的分析在返回带有相应回调信息的寄存器v5时结束。图的第二部分显示了关联的超级节点，这些节点显示执行的切片属于MainSearch:onClick回调。因此，通过分析更小的指令集，更重要的是，在存在不确定的回调命令的情况下，可以从根本上确定导致故障的输入。B、 故障定位此分析有助于检测和识别应用程序中的故障位置。对于顺序程序，故障定位的挑战性较小，因为它不需要处理异步事件强加的非确定性。Android应用程序不仅是事件驱动的，而且可以通过传感器、文件和各种形式的用户交互在执行的任何时候接受输入。因此，Android上的故障定位对开发人员来说尤其具有挑战性。问题陈述。分析的输入将是应用程序跟踪，以及寄存器verr，它在指令的特定事件中保存错误值。这次的输出将是指令s1、s2、hellip;、sn的序列，这些指令定义并传播verr中引用的值。跟踪故障传播。我们的切片方法有助于故障定位如下。给定执行期间的错误，我们通过将Android事件日志映射到执行跟踪来确定寄存器verr中的错误值引用。然后，我们通过反向传播执行片来计算verr的执行片。当我们向后遍历PDG时，如果异步回调及其输入参数与verr的最终值有直接的数据或控件依赖关系，我们将考虑它们。这样，我们既可以处理事件的不确定性，又可以支持来自内部和外部源的随机输入。例子。我们在漫画书浏览应用程序ACV中演示了一个真正的bug。8图6显示了错误执行生成的顺序和异步依赖项。当用户打开文件资源管理器选择漫画书时，该错误会导致崩溃。如果用户长时间点击

三、 模型

在本节中，我们将介绍我们方法的基础模型。切片精度取决于准确识别控制和数据依赖项-这些依赖项形成PDG。我们以回调为中心的设计在不牺牲精度的情况下实现了低开销的事件捕获（所有输入数据都是从框架中本地捕获的）。我们不将单个指令实例视为节点，而是将回调定义为包含其他节点（指令）或超级节点的节点。与常规节点一样，回调或超级节点可以直接调用其他事件/回调（控件依赖），或者通过将参数传递给框架，然后传递给另一个回调（数据依赖）。我们的模型捕获回调/超级节点和指令/单个节点的这两种依赖关系。我们使用“分层”PDG，构造如下。高级超级节点N表示回调及其动态上下文；超级边表示超级节点之间的异步控制或数据依赖关系。在超级节点中，我们使用低级指令节点Sit和捕获顺序依赖关系的边。超节点N，我们模型的核心，被定义为：N：=c，t，a，{[Sit☆c Sjt | Sit☆dsjt]*

A、 异步依赖

异步数据依赖。直观地说，异步数据依赖通过消息传递（IPC、对象等）捕获通信。我们将回调c1中定义的寄存器集表示为Def（c1）；将时间t时存储在寄存器vx中的引用表示为ref（vx，t）。然后，如果在时间t时，c1在寄存器v1中定义进程间或进程内消息传递对象（意图），并且c2在寄存器v2中接收相同的引用作为参数，则回调实例c2依赖于回调实例c1（即N1lt;.d N2）。这还引入了从使用v2的c2中的第一指令S2t到定义v1的c1中的指令S1t的数据依赖性。根据回调，数据依赖可以是应用程序间或应用程序内；我们跟踪两者。异步控制依赖性。有效的异步切片依赖于精确捕捉异步事件之间的依赖关系，当N确定（启动）N2通过

活动上下文转换。作为一个基于事件的模型，Android的运行时系统在调用异步回调时在不同的UI状态（“活动上下文”）之间切换。假设当前活动上下文是a2，当前回调是c2，其超级节点是N2，上一个活动上下文是a1，其“退出”（即触发上下文转换的回调）是c1，其超级节点是N1，我们使用速记发起者（N2）=N1来指示N1已触发到a2的转换。我们定义了两个规则来捕捉谁启动了N2。第一条规则捕获了一个简单的转换-两个事件之间没有传递意图，即，，（N1lt;-d N2）。4当N2依赖于N1时，第二条规则适用；在这种情况下，发起方是N1依赖于的超级节点N0。然后我们递归地在N0上应用相同的规则。换言之，这两个规则通过查找哪个事件N导致了事件N2来帮助捕获事件因果关系；这被记录为superedge N☆cn2。

B、 顺序依赖

顺序数据依赖性是通过顺序跟踪通过指令的值的传播来捕获的，也就是说，控制流不会离开当前回调或其被调用方。注意，Android是一个基于寄存器的机器，因此寄存器用于保存值、传入和传出值、执行计算等。我们通过这些寄存器跟踪内存引用。我们将指令s中定义的寄存器集表示为dins，将指令s中使用的寄存器集表示为uin。然后，如果在时间t的特定执行中在S1t中定义了在S2t中使用的寄存器v2中的至少一个，则指令S2t依赖于指令S1t。换句话说，该寄存器出现在定义dins集合（S1t）和使用uin集合（S2t）中；在S2t中被称为V2t的条件是“活的”。顺序控制依赖性。对于按顺序执行的

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[234414]，资料为PDF文档或Word文档，PDF文档可免费转换为Word