臺灣博碩士論文加值系統

智慧型手機、平板電腦等行動裝置已日益成為個人的必備工具，軟
體市集的商業模式也蓬勃發展，並成為智慧型裝置的應用軟體主要來
源。然而這些智慧型裝置往往包含著大量個人化的資訊，同時也能進
行發送簡訊等付費行為，因此執行於其上的應用軟體的品質與可靠性
也逐漸成為備受關注的議題。但是一般使用者並沒有能力判斷市集上
的軟體品質，而官方市集以及第三方市集也都無法保證架上的軟體是
否不含缺陷問題。在此論文中，我們描述如何建立一個Android APP
測試環境，採用符號執行(Symbolic execution) 技術，可以自動化對市
集中的應用程式進行品質檢測，透過探測程式的可能執行路徑，以發
掘出未被執行之潛在品質缺陷或隱含可能有威脅疑慮之執行路徑。我
們實作改良原有之軟體品質測試與脅迫平台：CRAX，進行Andorid
APP 之測試，稱為CRAXdroid，已成功實驗於實際應用之Android 程
式，證明此方法可行性高。

Mobile devices such as smart phone and tablet PC are becoming common
personal devices. The business model of software market is also thriving
and turning into a major source of software on those devices. However,
such intelligent devices often contain lots of private information, and also
can be used to conduct operations involving payment, like sending SMS. As
a result, the quality of software on mobile devices becomes a critical issue.
But ordinary users do not have the ability to check whether software on the
shelf contains defective behavior or potential vulnerabilities, and neither the
official APP market nor third party markets can ensure their software have no
privacy risk. In this thesis, we proposed to build a platform for android APP
testing, based on symbolic execution technique. By exploring all possible
paths, we can find potential software vulnerabilities. We revised our software
quality assurance and exploit generation platform, called CRAX, to apply
in the Android APPs. It is called the CRAXdroid subsystem. We perform
several experiments on Android market applications to prove the feasibility
of our method.

摘要i
Abstract ii
誌謝iii
Contents iv
List of Codes vi
List of Figures vii
List of Tables viii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Background 4
2.1 Android . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Android Market . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Android APP and Dalvik VM . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3 Android Security and Privacy . . . . . . . . . . . . . . . . . . . . . . 6
2.1.3.1 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.3.2 Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Software Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 White-box Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1.1 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Black-box Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.3 Fuzz Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.4 Symbolic Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Vulnerability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1 Static Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.2 Dynamic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Related Work 11
3.1 EMMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 TaintDroid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 AppInspector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Leakalizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5 Comparison of related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Methods 14
4.1 Symbolic Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 UI Fuzzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Path Explorer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.4 Exception Handler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5 Implementation 17
5.1 Symbolic Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.1.1 The architecture of S2E . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.1.2 ARM Android on S2E . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.1.3 x86 Android on S2E . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1.4 The architecture of CRAXdroid . . . . . . . . . . . . . . . . . . . . . 20
5.2 Symbolic Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2.1 Platform Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2.2 System Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3 Symbolic Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3.1 JNI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3.2 File I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.4 Exception Repository . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4.1 Crash Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6 Experimental Results 24
6.1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2 Evaluation for White-box testing . . . . . . . . . . . . . . . . . . . . . . . . 24
6.3 Evaluation for Black-box testing . . . . . . . . . . . . . . . . . . . . . . . . 27
7 Conclusions and Further Work 30
7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Reference 33
Appendix 37
A Simple codes and raw output results 37

[1] Google terms of service. http://www.google.com/intl/en/policies/terms/.
[2] Android developer distribution agreement. http://www.android.com/us/developerdistribution-agreement.html.
[3] P. Gilbert, B.G. Chun, L.P. Cox, and J. Jung. Vision: automated security validation of mobile apps at app markets In Acm, editor, Proceedings of the second international workshop on Mobile cloud computing and services, pages 21–26, 2011.
[4] Y. Zhou, Z. Wang, W. Zhou, and X. Jiang. Hey, you, get off of my market: Detecting malicious apps in official and alternative android markets. In Proceedings of the 19th Annual Network and Distributed System Security Symposium, 2012.
[5] A.-D. Schmidt, H.-G. Schmidt, L. Batyuk, J.H. Clausen, S.A. Camtepe, S. Albayrak, and C. Yildizli. Smartphone malware evolution revisited: Android next target? In Proceedings of the 4th IEEE International Conference on Malicious and Unwanted Software (Malware 2009), pages 1–7. Ieee, 2009.
[6] Aubrey-Derrick Schmidt and Sahin Albayrak. Malicious software for smartphones. technical report tub-dai 02/08-01. Technical report, 2008.
[7] S. Bugiel, L. Davi, A. Dmitrienko, T. Fischer, A.R. Sadeghi, and B. Shastry. Towards taming privilege-escalation attacks on android. In Proc. of the 19th Network and Distributed System Security Symposium (NDSS 2012), San Diego, CA, 2012.
[8] L. Davi, A. Dmitrienko, A.R. Sadeghi, and M. Winandy. Privilege escalation attacks on android. Information Security, pages 346–360, 2011.
[9] W. Enck, P. Gilbert, B.G. Chun, L.P. Cox, J. Jung, P. McDaniel, and A.N. Sheth. Taintdroid: An information-flow tracking system for realtime privacy monitoring on smartphones. In USENIX Association, editor, Proceedings of the 9th USENIX conference on Operating systems design and implementation, pages 1–6, 2010.
[10] C. Gibler, J. Crussell, J. Erickson, and H. Chen. Androidleaks: Automatically detecting potential privacy leaks in android applications on a large scale. Trust and Trustworthy Computing, pages 291–307, 2012.
[11] A. Takanen, J. DeMott, and C. Miller. Fuzzing for software security testing and quality assurance. Artech House, 2008.
[12] Android testing framework. http://developer.android.com/tools/testing/testingandroid.html.
[13] Android instrumentation framework – junit. http://developer.android.com/tools/testing/testingandroid.
[14] Ui/application exerciser monkey. http://developer.android.com/tools/help/monkey.html.
[15] Solution center for android – arm. http://www.arm.com/community/softwareenablement/google/solution-center-android/.
[16] D. Bornstein. Dalvik vm internals. In Google I/O Developer Conference, volume 23, pages 17–30, 2008.
[17] Inc. Juniper Networks. Malicious mobile threats report 2010/2011. Technical report.
[18] http://developer.android.com/guide/topics/security/permissions.html.
[19] http://developer.android.com/reference/android/Manifest.permission.html.
[20] z4root. http://forum.xda-developers.com/showthread.php?t=833953.
[21] Superuser. http://forum.xda-developers.com/showthread.php?t=682828, https://play.google.com/store/apps/details?id=com.noshufou.android.su.
[22] Android wargame. http://140.113.87.234/.
[23] W. Uzgalis and E. Zalta. The stanford encyclopedia of philosophy. The Stanford Encyclopedia of Philosophy, 2008.
[24] Andreas Kirchner. Data leak detection in smartphone application. 2011.
[25] White-box testing – wikipedia. http://en.wikipedia.org/wiki/White-boxtesting.
[26] P. Godefroid. Random testing for security: blackbox vs. whitebox fuzzing. In Proceedings of the 2nd international workshop on Random testing: co-located with the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2007), Rt a07, page 1, New York, NY, USA, 2007. Acm.
[27] J.C. King. Symbolic execution and program testing. Communications of the ACM, 19(7):385–394, 1976.
[28] Po-Yen Huang. Automated exploit generation for control-flow hijacking attacks. 2011.
[29] Wai-Meng Leong. Automaticweb testing and attack generation. 2012.
[30] Findbugs. http://findbugs.sourceforge.net/.
[31] Pmd. http://pmd.sourceforge.net/pmd-5.0.0/.
[32] Eclipse – static analysis. http://wiki.eclipse.org/CDT/designs/StaticAnalysis.
[33] Emma: a free java code coverage tool. http://emma.sourceforge.net/.
[34] V. Chipounov, V. Kuznetsov, and G. Candea. S2e: a platform for in-vivo multi-path analysis of software systems. SIGPLAN Not., 46(3):265–278, 2011.
[35] Android-x86 project. http://www.android-x86.org/.
[36] F. Bellard. Qemu, a fast and portable dynamic translator. In Proceedings of the annual conference on USENIX Annual Technical Conference, Atec a05, page 41, Berkeley, CA, USA, 2005. USENIX Association.
[37] C. Cadar, D. Dunbar, and D. Engler. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In USENIX Association, editor, Proceedings of the 8th USENIX conference on Operating systems design and
implementation, pages 209–224, 2008.
[38] Cortex-a9 processor. http://www.arm.com/products/processors/cortex-a/cortexa9.php.
[39] Goldfish. http://elinux.org/AndroidonOMAP#Goldfish.
[40] Vishal Kanaujia. Virtual machines for abstraction: The dalvik vm. http://www.linuxforu.com/2011/06/virtual-machines-for-abstraction-dalvik-vm/.
[41] G. Candea, S. Bucur, and C. Zamfir. Automated software testing as a service. In Proceedings of the 1st ACM symposium on Cloud computing, SoCC a10, pages 155–160, New York, NY, USA, 2010. Acm.