دانلود رایگان ترجمه مقاله اکتشاف هدفمند و عمیق برای آزمایش سیستماتیک از برنامه های آندروید – ACM 2013

الگوریتم جست و جوی اول عمق و هدفمند برای تست سیستمی و اصولی برنامه های اندروید

Targeted and Depth-first Exploration for Systematic Testing of Android Apps

چکیده 
جست وجوی سیستمی برنامه های اندرویید یک توان مند ساز برای تحلیل طیف وسیعی از برنامه ها و فعالیت های آزمایشی است. انجام جست و جو در زمان کار کرد گوشی های واقعی، برای جست و جو کشف همه قابلیت های نرم افزار لازم است. با این حال، جست و جوی نرم افزار های دنیای واقعی بر روی گوشی های واقعی به دلیل عدم قطعیت، عدم جریان کنترل استاندارد، توسعه پذیری و محدودیت های سربار سخت است. با اتکا به کار بران نهایی برای انجام جست و جو ها ما یک مطالعه 7 کاربری را بر روی برنامه های محبوب اندرویید انجام داده و پی بردیم که پوشش 7 کاربری برای فیلتر برنامه ها برابر با 30.8 درصد و برای روش های نرم افزار و برنامه نویسی 6.46 درصد است. رویکرد های قبلی برای جست و جوی خودکار برنامه های اندروییدی دارای برنامه هایی در شبیه ساز بوده و یا این که بر برنامه های کوچک تر یمتمرکز هستند که کد منبع آن ها قابل دسترس است. برای حل این مسائل، ما از رویکرد A3E استفاده کردیم که از طریق آن می توان به جست و جوی سیستمی برنامه های اجرا شده برر روی گوشی های اقعی بدون دسترسی به کد منبع پرداخت. اطلاعات کلیدی مربوط به رویکرد ما شامل استفاده از تحلیل جریان داده ها، استاتیک و سبک قدیمی بر روی بایت کد های برنامه به شکلی جدید است که می تواند طیف وسیعی از فعالیت ها را در نظر بگیرد. ما از این نمودار برای توسعه یک راهبرد جست و جویی موسوم به کشف و جست و جوی هدفمند استفاده می کنیم که امکان جست و جوی مستقیم از جمله فعالیت هایی که طی استفاده طبیعی سخت هستند را می دهد. ما از راهبرد موسوم به جست و جوی اول عمق نیز بهره می بریم که از عملیات کاربر برای فعالیت های اکتشافی و نیز اجزای سازنده آن به طور کند تر ولی سیستمی الگو برداری می کند: ما از دو شاخص استفاده می کنیم: پوشش فعالیت و پوشش روش. ازمایشات با استفاده از رویکرد ما بر روی 25 برنامه اندرویید شامل بی بی سی نیوز، گاز بادی، و غیره بود.

Abstract

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

1. Introduction

Users are increasingly relying on smartphones for computational tasks [1, 2], hence concerns such as app correctness, performance, and security become increasingly pressing [6, 8, 30, 31, 38]. Dynamic analysis is an attractive approach for tackling such concerns via profiling and monitoring, and has been used to study a wide range of properties, from energy usage [38, 39] to profiling [40] and security [31]. However, dynamic analysis critically hinges on the availability of test cases that can ensure good coverage, i.e., drive program execution through a significant set of representative program states [36, 37]. To facilitate test case construction and exploration for smartphone apps, several approaches have emerged. The Monkey tool [15] can send random event streams to an app, but this limits exploration effectiveness. Frameworks such as Monkeyrunner [24], Robotium [18] and Troyd [20] support scripting and sending events, but scripting takes manual effort. Prior approaches for automated GUI exploration [9– 12, 17, 34] have one or more limitations that stand in the way of understanding how popular apps run in their natural environment, i.e., on actual phones: running apps in an emulator, targeting small apps whose source code is available, incomplete model extraction, state space explosion. For illustration, consider the task of automatically exploring popular apps, such as Amazon Mobile, Gas Buddy, YouTube, Shazam Encore, or CNN, whose source code is not available. Our approach can carry out this task, as shown in Section 6, since we connect to apps running naturally on the phone. However, existing approaches have multiple difficulties due to the lack of source code or running the app on the emulator where the full range of required sensor inputs (camera, GPS, microphone) or output devices (e.g., flashlight) is either unavailable [32] or would have to be simulated. To tackle these challenges, we present Automatic Android App Explorer (A 3E), an approach and open-source tool1 for systematically exploring real-world, popular apps Android apps running on actual phones. Developers can use our approach to complement their existing test suites with automatically-generated test cases aimed at systematic exploration. Since A 3E does not require access to source code, users other than the developers can execute substantial parts of the app automatically. A 3E supports sensors and does not require kernel- or framework-level instrumentation, so the typical overhead of instrumentation and device emulation can be avoided. Hence we believe that researchers and practitioners can use A 3E as a basis for dynamic analyses [36] (e.g., monitoring, profiling, information flow tracking), testing, debugging, etc. In this paper, our approach is focused on improving coverage at two granularity levels: activity (high-level) and method (low-level). Activities are the main parts of Android apps—an activity roughly corresponds to a different screen or window in traditional GUI-based applications. Increasing activity coverage means, roughly, exploring more screens. For method coverage we focus on covering app methods, as available in the Dalvik bytecode (compiled from Java), that runs on the Dalvik VM on an actual phone; an activity’s implementation usually consists of many methods, so by improving method coverage we allow the functionality associated with each activity to be systematically explored and tested. In Section 2 we provide an overview of the Android platform and apps, we define the graphs that help drive our approach, and provide definitions for our coverage metrics. To understand the level of exploration attained by Android app users in practice, we performed a user study and measured coverage during regular interaction. For the study, we enrolled 7 users that exercised 28 popular Android apps. We found that across all apps and participants, on average, just 30.08% of the app screens and 6.46% of the app methods were explored. The results and reasons for these low levels of coverage are presented in Section 3. In Section 4 we present our approach for automated exploration: given an app, we construct systematic exploration traces that can then be replayed, analyzed and used for a variety of purposes, e.g., to drive dynamic analysis or assemble test suites. Our approach consists of two techniques, Targeted Exploration and Depth-First Exploration. Targeted Exploration is a directed approach that first uses static bytecode analysis to extract a Static Activity Transition Graph and then explore the graph systematically while the app runs on a phone. Depth-First Exploration is a completely dynamic approach based on automated exploration of activities and GUI elements in a depth-first manner. In Section 5 we provide an overview of A 3E’s implementation: hardware platform, tools and measurement procedures. In Section 6 we provide an evaluation of our approach on 25 apps (3 apps could not be explored because they were written mainly in native code rather than bytecode). We show that our approach is effective: on average it attains 64.11% and 59.39% activity coverage via Targeted and Depth-first Exploration, respectively (a 2x increase compared to what the 7 users have attained); it also attains 29.53% and 36.46% method coverage via Targeted and Depth-first Exploration, respectively (a 4.5x increase compared to the 7 users). Our approach is also efficient: average figures are 74 seconds for Static Activity Transition Graph construction, 87 minutes for Targeted Exploration and 104 minutes for Depth-first Exploration. In summary, this work makes the following contributions: • A qualitative and quantitative study of coverage attained in practice by 7 users for 28 popular Android apps. • Two approaches, Targeted Exploration and Depth-first Exploration, for exploring substantial apps running on Android smartphones. • An evaluation of the effectiveness of Targeted and Depthfirst Exploration on 25 popular Android apps.