ENQUIRE PROJECT DETAILS BY GENERAL PUBLIC

Project Details
Funding Scheme : General Research Fund
Project Number : 611912
Project Title(English) : Fault Detection of Event-Driven Mobile Applications Using Static Analysis 
Project Title(Chinese) : 事件驅動的移動應用程式錯誤之靜態檢測方法 
Principal Investigator(English) : Prof Cheung, Shing-chi 
Principal Investigator(Chinese) :  
Department : Dept of Computer Science & Engineering
Institution : The Hong Kong University of Science and Technology
E-mail Address : scc@cse.ust.hk 
Tel : 2358 7016 
Co - Investigator(s) :
Panel : Engineering
Subject Area : Computing Science & Information Technology
Exercise Year : 2012 / 13
Fund Approved : 905,425
Project Status : Completed
Completion Date : 30-6-2016
Project Objectives :
To tabulate the common faults arising from the event handlers of mobile applications and identify their causes to these faults.
To develop a framework that supports the static analysis of event handler faults.
To implement the proposed framework and evaluate it using simulated and real-life event handler faults of mobile applications.
Abstract as per original application
(English/Chinese):
Recent advances in smart phone technology have led to the proliferation of mobile applications. These applications typically feature event-driven interaction between software, human, and hardware. Since the execution of these applications often involves user interaction and event triggering from hardware sensors, their automated testing is difficult. This severely weakens the use of testing to detect faults in mobile applications. Static analysis provides a promising alternative to testing because it is able to uncover program faults without actual execution. Analyzing event-driven applications statically, however, involves two significant challenges. First, these applications typically involve a large number of event handlers, which rarely have explicit control flows or call relations between one another. Static analysis based on control flow information may conclude that these handlers can be invoked with arbitrary orders. This leads to a lot of handler invocation orders and combinations; many of which are infeasible. As a result, the fault report contains a high rate of false positives. Second, as mobile applications are typically long running and continually adaptive to events, it is impractical to conduct precise analysis of the entire execution for all possible adaptive behaviors. How to abstract them to scale up the analysis, however, remains an open question. In this project, we propose to address these two challenges and develop an effective technique to detect mobile application faults arising from the interactions among event handlers. Our technique will be able to identify common software faults such as null pointer dereferences and resource leaks against an interaction model that describes the feasible execution orders of event handlers. The technique will be evaluated using real Android subjects. Mobile applications like those running on Android and iPhone devices have penetrated into the daily life of people in Hong Kong. Such applications include banking, navigation, scheduling, e-commerce, remote device control, and health care. Many companies invest large amount of human resources in developing dependable mobile applications. This project will greatly facilitate the dependability checking of such applications.
Recent advances in smart phone technology have led to the proliferation of mobile applications. These applications typically feature event-driven interaction between software, human, and hardware. Since the execution of these applications often involves user interaction and event triggering from hardware sensors, their automated testing is difficult. This severely weakens the use of testing to detect faults in mobile applications. Static analysis provides a promising alternative to testing because it is able to uncover program faults without actual execution. Analyzing event-driven applications statically, however, involves two significant challenges. First, these applications typically involve a large number of event handlers, which rarely have explicit control flows or call relations between one another. Static analysis based on control flow information may conclude that these handlers can be invoked with arbitrary orders. This leads to a lot of handler invocation orders and combinations; many of which are infeasible. As a result, the fault report contains a high rate of false positives. Second, as mobile applications are typically long running and continually adaptive to events, it is impractical to conduct precise analysis of the entire execution for all possible adaptive behaviors. How to abstract them to scale up the analysis, however, remains an open question. In this project, we propose to address these two challenges and develop an effective technique to detect mobile application faults arising from the interactions among event handlers. Our technique will be able to identify common software faults such as null pointer dereferences and resource leaks against an interaction model that describes the feasible execution orders of event handlers. The technique will be evaluated using real Android subjects. Mobile applications like those running on Android and iPhone devices have penetrated into the daily life of people in Hong Kong. Such applications include banking, navigation, scheduling, e-commerce, remote device control, and health care. Many companies invest large amount of human resources in developing dependable mobile applications. This project will greatly facilitate the dependability checking of such applications. 最近的智慧手機技術已近造成移動應用程式的大量增長。這些應用程式通常都包含了人機之間的事件驅動的交互。由於這些程式通常都包括和使用者的交互和來自硬體的感測器的交互,對它們自動化測試通常比較困難。這種困難嚴重弱化了測試在移動應用中的使用。由於靜態分析可以不用運行被檢測的軟體而發現錯誤,靜態分析提供了一個很有潛力的選擇。然而分析事件驅動的應用套裝程式含了兩個挑戰。第一,這些應用程式包括大量的事件處理控制碼。事件處理控制碼之間通常沒有清楚的程式控制流。基於程式控制流的靜態分析可以假設任意兩個事件驅動控制碼都可以以任何順序調用。這樣會造成分析大量的不可能的事件順序。結果是大量的假陽性的報告。第二,由於移動應用程式通常是長時間運行並且持續自我調整事件,對所有的事件序列對應的自我調整行為做準確的分析是不實際的。然而,如何對自我調整行為做出抽象以便增大分析的規模還是一個未解的問題。在這個項目裡,我們將要應對這些挑戰並且開發出有效的技術檢測移動應用程式的事件控制碼交互造成的常見錯誤。我們的技術將會生成一個描述可能的交互序列的模型並在這個模型的指導下檢測如空指標和資源洩漏等錯誤。這個技術將會在用真實的Android軟體做評測。 移動應用程式如Android和iPhone上的軟體已近進入香港人的生活。這樣的應用包括金融,導航,計畫,電子商務,遠端控制,和醫療保健。很多公司投入大筆的人力開發可靠的移動應用程式。這個項目將幫助提高這類應用的可靠性。
Realisation of objectives: Executions of mobile applications are mostly driven by user interaction or system events. During its execution, an application keeps handling received user interaction and system events by calling their handlers. Each call to an event handler may change the application’s state by modifying its components’ local or global program data. Bugs arising from erroneous event handling in mobile applications are significant. Since event handling is subject to non-determinism, failures induced by the related bugs are hard to detect and reproduce. To achieve the first objective, we carried an empirical study of 70 real-world bugs collected from eight large-scale and popular Android applications. Each of these applications has more than 10,000 downloads and are actively maintained with a public bug tracking system. These bugs involve performance issues and reside in event handlers. We studied their bug reports and code fixes to identify their types and root causes. We checked whether manifestation of these bugs require special inputs and identified their common bug patterns. To achieve the second objective, we derive an analysis framework. We formalize the concepts of user interaction event sequences, application states and bounded state space exploration. We propose an application execution model to abstract activity lifecycles, and use the model to drive event sequence generation. A framework based on symbolic analysis was developed. A common deficiency of symbolic analysis is that it is not scalable to inter-procedural analysis of real-life applications. Our approach addresses the problem by identifying and removing equivalent symbolic states. It makes the analysis scalable to millions lines of code. We approached the problem using static analysis and then enhanced it with dynamic analysis. We find that it is beneficial to augment static analysis with dynamic analysis or runtime data for three reasons. First precise static analysis needs to be path-sensitive but carrying such analysis on real mobile applications is not scalable. Second, mobile applications typically make many system library calls. Precise modeling of all these library calls require non-trivial manual effort, which is ineffective when mobile system library evolves frequently. Third, popular mobile applications can involve execution of native code written in C or C++. Effects of these code are not easy to precisely trace. In this connection, we enhance our approach to validating the analyzed symbolic states with runtime data collected from large open source projects. Finally, we worked with Microsoft Research Asia and proposed a technique to locate faulty methods based on a collection of crash reports. To achieve the third objective, we implemented our framework in Java and evaluated using 29 popular Android apps and other open source projects. We set up a web site making our data set and tools available at http://sccpu2.cse.ust.hk/perfchecker.
Summary of objectives addressed:
Objectives Addressed Percentage achieved
1.To tabulate the common faults arising from the event handlers of mobile applications and identify their causes to these faults.Yes100%
2.To develop a framework that supports the static analysis of event handler faults.Yes100%
3.To implement the proposed framework and evaluate it using simulated and real-life event handler faults of mobile applications.Yes100%
Research Outcome
Major findings and research outcome: The findings of this project were disseminated by one top-tier journal (TOSEM) and three top-tier conference publications (ICSE, ISSTA and ASE). Two PhD students were trained. Our two publications at ICSE and ISSTA were well received by the software engineering community and received the ACM SIGSOFT Distinguished Paper awards. The data set of our study and static analysis tools are made available to public. We summarize our findings as follows. - Performance bugs reside in the event handler of mobile applications largely lead to the lagging of user interactions, energy leakage and memory bloat. - Small-scale inputs suffice to manifest the bugs. In other words, most of the bugs can be triggered by small volume of input data. - Specific user interactions needed to manifest the bugs. Many of the bugs can only be triggered by specific user interaction sequences. Therefore, test sets driven by a coverage based on statement or branches cannot effectively expose the bugs. Modeling of activity lifecycles is crucial to the bug detection. - Quite a few of the bugs are platform-dependent. They may occur only on specific system library versions or mobile device models. - It takes a significantly longer time for developers to fix a performance bugs than non-performance bugs. This is likely because developers lack effective performance measurement tools for mobile devices. - Three common bug patterns are observed in event handling bugs. First, the event dispatcher thread involves computationally intensive operations. Second, unintended event sequences cause wasted computation. Third, heavy-weight callbacks are frequently triggered. - Removal of equivalent symbolic states can achieve a speedup of several order of magnitudes. As compared with the state-of-the-arts approaches, our technique improves the function coverage and block coverage by 40% and 32%, respectively. - Our analysis framework when applied to 29 popular Android applications detected 18 of them contain a total of 126 unreported bugs. 68 of them were confirmed quickly by the corresponding application developers that they are real bugs. - Experimental results show that the most suspicious function reported by our crash analysis has an overall probability of 51% that it is truly faulty. The overall probability that one of the top 10 most suspicious functions reported by our crash analysis is truly faulty is 66%.
Potential for further development of the research
and the proposed course of action:
Our findings lead to the following future work. - Bug detection can be made possible by generating user interaction sequences with small scale inputs. - We can consider to augment crash analysis with runtime log data. - We can consider to leverage the common bug patterns and generate possible patches for detected bugs. - We can consider to adapt the analysis techniques to iOS applications.
Layman's Summary of
Completion Report:
The smartphone application market is expanding rapidly. However, random sampling of Android applications available at Google Play store indicates that many of them suffer from various kinds of bugs triggered by anomalous event handling. These bugs cannot be effectively detected by existing tools. To address the problem, we gain better understanding of these bugs via an empirical study. The study identifies the common bug types, their root causes and problematic coding patterns that likely induce these bugs. A static analysis framework augmented with runtime data is developed to help developers to detect bugs in their applications. Promising results were found. Our techniques were well received by the software engineering community. Our work received two ACM SIGSOFT Distinguished Paper awards. To promote impacts, we made our dataset and tools available to the public. Our dataset and tools were also used by prominent research groups in other research institutes such as Oregon State University, Ohio State University, the Chinese University of Hong Kong, the National University of Singapore, the University of Southern California, the College of William and Mary, the University of Alberta and Technische Universität Darmstadt.
Research Output
Peer-reviewed journal publication(s)
arising directly from this research project :
(* denotes the corresponding author)
Year of
Publication
Author(s) Title and Journal/Book
2014 Yueqi Li, S.C. Cheung*, Xiangyu Zhang, Yepang Liu  Scaling Up Symbolic Analysis by Removing Z-Equivalent States, ACM Transactions on Software Engineering and Methodology (TOSEM) 23(4), article 34, August 2014. 
Recognized international conference(s)
in which paper(s) related to this research
project was/were delivered :
Month/Year/City Title Conference Name
June/2014/Hyderabad Characterizing and Detecting Performance Bugs for Smartphone Applications  36th International Conference on Software Engineering (ICSE 2014) 
July/2014/San Jose CrashLocator: Locating Crashing Faults based on Crash Stacks  International Symposium on Software Testing and Analysis (ISSTA 2014) 
September/2014/Vasteras Symbolic State Validation through Runtime Data  29th IEEE/ACM International Conference on Automated Software Engineering (ASE 2014) 
Other impact
(e.g. award of patents or prizes,
collaboration with other research institutions,
technology transfer, etc.):
- Collaboration with Microsoft Research Asia. - Collaboration with Purdue University. - A research corpora for Android applications is made available to public at http://sccpu2.cse.ust.hk/perfchecker. - Two ACM SIGSOFT Distinguished Paper awards: ICSE 2014 and ISSTA 2014.

  SCREEN ID: SCRRM00542