Call Graph Soundness in Android Static Analysis

Android; Call Graph Soundness; Dynamic Analysis; Static Analysis; Analysis tools; Android apps; Call graph construction; Call graph soundness; Call graphs; Dynamics analysis; Entry point; Program code; Static analyzers; Computational Theory and Mathematics; Computer Science Applications; Software

Abstract :

[en] Static analysis is sound in theory, but an implementation may unsoundly fail to analyze all of a program's code. Any such omission is a serious threat to the validity of the tool's output. Our work is the first to measure the prevalence of these omissions. Previously, researchers and analysts did not know what is missed by static analysis, what sort of code is missed, or the reasons behind these omissions. To address this gap, we ran 13static analysis tools and a dynamic analysis on 1000 Android apps. Any method in the dynamic analysis but not in a static analysis is an unsoundness. Our findings include the following. (1) Apps built around external frameworks challenge static analyzers. On average, the 13 static analysis tools failed to capture 61% of the dynamically-executed methods. (2) A high level of precision in call graph construction is a synonym for a high level of unsoundness. (3) No existing approach significantly improves static analysis soundness. This includes those specifically tailored for a given mechanism, such as DroidRA to address reflection. It also includes systematic approaches, such as EdgeMiner, capturing all callbacks in the Android framework systematically. (4) Modeling entry point methods challenges call graph construction which jeopardizes soundness.

Disciplines :

Computer science

Author, co-author :

SAMHI, Jordan ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > TruX ; Cispa Helmholtz Center for Information Security, Saarbrucken, Germany

Just, René ; University of Washington, Seattle, United States

BISSYANDE, Tegawendé François d Assise ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > TruX

Ernst, Michael D. ; University of Washington, Seattle, United States

KLEIN, Jacques ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > TruX

External co-authors :

yes

Language :

English

Title :

Call Graph Soundness in Android Static Analysis

Publication date :

11 September 2024

Event name :

Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis

Event place :

Vienna, Aut

Event date :

16-09-2024 => 20-09-2024

Main work title :

ISSTA 2024 - Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis

Editor :

Christakis, Maria

Publisher :

Association for Computing Machinery, Inc

ISBN/EAN :

9798400706127

Peer reviewed :

Peer reviewed

Focus Area :

Security, Reliability and Trust

Additional URL :

https://dl.acm.org/doi/pdf/10.1145/3650212.3680333

FnR Project :

16344458
18154263

Name of the research project :

U-AGR-7109 - C21/IS/16344458/REPROCESS/Klein - KLEIN Jacques
U-AGR-7343 - C23/IS/18154263/Unlock - KLEIN Jacques

Funders :

ACM SIGSOFT
AITO

Funding number :

18154263; 16344458

Funding text :

This research was funded in whole, or in part, by the Luxembourg National Research Fund (FNR), grant references 16344458 (REPROCESS) and 18154263 (UNLOCK).

Data Set :

https://github.com/JordanSamhi/Call-Graph-Soundness-in-Android-Static-Analysis

Available on ORBilu :

since 13 November 2024

Statistics

Number of views

118 (1 by Unilu)

Number of downloads

40 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Karim Ali, Xiaoni Lai, Zhaoyi Luo, Ondrej Lhoták, Julian Dolby, and Frank Tip. 2021. A Study of Call Graph Construction for JVM-Hosted Languages. IEEE Transactions on Software Engineering 47, 12 (2021), 2644-2666. https: //doi.org/10.1109/TSE.2019.2956925
Dana Aljawder. 2016. Identifying unsoundness of call graphs in Android static analysis tools. Master's thesis. Boston University. https://open.bu.edu/handle/ 2144/17085
Kevin Allix, Tegawendé F. Bissyandé, Jacques Klein, and Yves Le Traon. 2016. AndroZoo: Collecting Millions of Android Apps for the Research Community. In Proceedings of the 13th International Conference on Mining Software Repositories (Austin, Texas) (MSR '16). ACM, New York, NY, USA, 468-471. https://doi.org/10.1145/2901739.2903508
ApkID. 2023. https://github.com/rednaga/APKiD. Accessed December 2023.
Steven Arzt and Eric Bodden. 2016. StubDroid: Automatic Inference of Precise Data-Flow Summaries for the Android Framework. In Proceedings of the 38th International Conference on Software Engineering (Austin, Texas) (ICSE '16). Association for Computing Machinery, New York, NY, USA, 725-735. https://doi.org/10.1145/2884781.2884816
Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. 2014. Flow- Droid: Precise Context, Flow, Field, Object-Sensitive and Lifecycle-Aware Taint Analysis for Android Apps. ACM SIGPLAN NOTICES 49, 6 (June 2014), 259-269. https://doi.org/10.1145/2666356.2594299
Paulo Barros, René Just, Suzanne Millstein, Paul Vines, Werner Dietl, Marcelo d'Amorim, and Michael D. Ernst. 2015. Static Analysis of Implicit Control Flow: Resolving Java Reflection and Android Intents. In Proceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering (Lincoln, Nebraska) (ASE '15). IEEE Press, 669-679. https://doi.org/10.1109/ASE.2015.69
Paulo Barros, René Just, Suzanne Millstein, Paul Vines, Werner Dietl, Marcelo d'Amorim, and Michael D. Ernst. 2015. Static analysis of implicit control flow: Resolving Java reflection and Android intents. In Proceedings of the International Conference on Automated Software Engineering (ASE). Lincoln, NE, USA, 669-679.
Sam Blackshear, Alexandra Gendreau, and Bor-Yuh Evan Chang. 2015. Droidel: A General Approach to Android Framework Modeling. In Proceedings of the 4th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis (Portland, OR, USA) (SOAP 2015). Association for Computing Machinery, New York, NY, USA, 19-25. https://doi.org/10.1145/2771284.2771288
Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezini. 2011. Taming Reflection: Aiding Static Analysis in the Presence of Reflection and Custom Class Loaders. In Proceedings of the 33rd International Conference on Software Engineering (Waikiki, Honolulu, HI, USA) (ICSE '11). Association for Computing Machinery, New York, NY, USA, 241-250. https: //doi.org/10.1145/1985793.1985827
Priyanka Bose, Dipanjan Das, Saastha Vasan, Sebastiano Mariani, Ilya Grishchenko, Andrea Continella, Antonio Bianchi, Christopher Kruegel, and Giovanni Vigna. 2023. COLUMBUS: Android App Testing Through Systematic Callback Exploration. In Proceedings of the International Conference on Software Engineering (ICSE). 45th International Conference on Software Engineering, ICSE 2023.
Yinzhi Cao, Yanick Fratantonio, Antonio Bianchi, Manuel Egele, Christopher Kruegel, Giovanni Vigna, and Yan Chen. 2015. EdgeMiner: Automatically Detecting Implicit Control Flow Transitions through the Android Framework. In NDSS.
Sen Chen, Lingling Fan, Chunyang Chen, and Yang Liu. 2022. Automatically Distilling Storyboard with Rich Features for Android Apps. IEEE Transactions on Software Engineering (2022).
Sen Chen, Lingling Fan, Chunyang Chen, Ting Su,Wenhe Li, Yang Liu, and Lihua Xu. 2019. StoryDroid: Automated Generation of Storyboard for Android Apps. In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). 596-607. https://doi.org/10.1109/ICSE.2019.00070
DexProtector. 2023. https://dexprotector.com. Accessed December 2023.
Malinda Dilhara, Haipeng Cai, and John Jenkins. 2018. Automated Detection and Repair of Incompatible Uses of Runtime Permissions in Android Apps. In Proceedings of the 5th International Conference on Mobile Software Engineering and Systems (Gothenburg, Sweden) (MOBILESoft '18). Association for Computing Machinery, New York, NY, USA, 67-71. https://doi.org/10.1145/3197231.3197255
Flutter Downloader. 2023. https://github.com/fluttercommunity/flutter_ downloader. Accessed December 2023.
Michael D. Ernst. [n. d.]. Static and dynamic analysis: Synergy and duality. 24-27.
Yonghui Liu et al. 2023. ReuNify: A Step Towards Whole Program Analysis for React Native Android Apps. In Proceedings of the 38th ACM/IEEE International Conference on Automated Software Engineering (Luxembourg, France) (ASE 2023). Association for Computing Machinery.
Yu Feng, Saswat Anand, Isil Dillig, and Alex Aiken. 2014. Apposcopy: Semantics- Based Detection of Android Malware through Static Analysis. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (Hong Kong, China) (FSE 2014). Association for Computing Machinery, New York, NY, USA, 576-587. https://doi.org/10.1145/2635868.2635869
Xinwei Fu, Dongyoon Lee, and Changhee Jung. 2018. NAdroid: Statically Detecting Ordering Violations in Android Applications. In Proceedings of the 2018 International Symposium on Code Generation and Optimization (Vienna, Austria) (CGO 2018). Association for Computing Machinery, New York, NY, USA, 62-74. https://doi.org/10.1145/3168829
Google. 2023. Android Monkey, https://developer.android.com/studio/test/ monkey. Accessed July 2023.
Google. 2023. Flutter. https://flutter.dev Accessed December 2023.
Michael I Gordon, Deokhwan Kim, Jeff H Perkins, Limei Gilham, Nguyen Nguyen, and Martin C Rinard. 2015. Information flow analysis of android applications in droidsafe. In NDSS, Vol. 15. 110.
Satori Threat Intelligence and Research Team. 2022. Poseidon's Offspring: Charybdis and Scylla, https://www.humansecurity.com/learn/blog/poseidons-offspringcharybdis- and-scylla. Accessed July 2023.
Kadiray Karakaya and Eric Bodden. 2021. SootFX: A Static Code Feature Extraction Tool for Java and Android. In 2021 IEEE 21st International Working Conference on Source Code Analysis and Manipulation (SCAM). 181-186. https://doi.org/10.1109/SCAM52516.2021.00030
William Klieber, Lori Flynn, Amar Bhosale, Limin Jia, and Lujo Bauer. 2014. Android taint flow analysis for app sets. In Proceedings of the 3rd ACM SIGPLAN International Workshop on the State of the Art in Java Program Analysis. 1-6.
Konstantin Kuznetsov, Vitalii Avdiienko, Alessandra Gorla, and Andreas Zeller. 2018. Analyzing the User Interface of Android Apps. In Proceedings of the 5th International Conference on Mobile Software Engineering and Systems (Gothenburg, Sweden) (MOBILESoft '18). Association for Computing Machinery, New York, NY, USA, 84-87. https://doi.org/10.1145/3197231.3197232
Duling Lai and Julia Rubin. 2020. Goal-Driven Exploration for Android Applications. In Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering (San Diego, California) (ASE '19). IEEE Press, 115-127. https://doi.org/10.1109/ASE.2019.00021
Sungho Lee, Julian Dolby, and Sukyoung Ryu. 2016. HybriDroid: Static Analysis Framework for Android Hybrid Applications. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering (Singapore, Singapore) (ASE '16). Association for Computing Machinery, New York, NY, USA, 250-261. https://doi.org/10.1145/2970276.2970368
Youn Kyu Lee, Jae young Bang, Gholamreza Safi, Arman Shahbazian, Yixue Zhao, and Nenad Medvidovic. 2017. A SEALANT for Inter-App Security Holes in Android. In Proceedings of the 39th International Conference on Software Engineering (Buenos Aires, Argentina) (ICSE '17). IEEE Press, 312-323. https://doi.org/10.1109/ICSE.2017.36
Chaoran Li, Xiao Chen, Ruoxi Sun, Minhui Xue, Sheng Wen, Muhammad Ejaz Ahmed, Seyit Camtepe, and Yang Xiang. 2022. Cross-Language Android Permission Specification. In Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (Singapore, Singapore) (ESEC/FSE 2022). Association for Computing Machinery, New York, NY, USA, 772-783. https://doi.org/10.1145/3540250.3549142
Cong Li, Chang Xu, Lili Wei, Jue Wang, Jun Ma, and Jian Lu. 2018. ELEGANT: Towards Effective Location of Fragmentation-Induced Compatibility Issues for Android Apps. In 2018 25th Asia-Pacific Software Engineering Conference (APSEC). 278-287. https://doi.org/10.1109/APSEC.2018.00042
Li Li, Alexandre Bartel, Tegawendé F. Bissyandé, Jacques Klein, Yves Le Traon, Steven Arzt, Siegfried Rasthofer, Eric Bodden, Damien Octeau, and Patrick Mc- Daniel. 2015. IccTA: Detecting Inter-Component Privacy Leaks in Android Apps. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (Florence, Italy) (ICSE '15). IEEE Press, 280-291.
Li Li, Tegawendé F. Bissyandé, Damien Octeau, and Jacques Klein. 2016. DroidRA: Taming Reflection to Support Whole-Program Analysis of Android Apps. In Proceedings of the 25th International Symposium on Software Testing and Analysis (Saarbrücken, Germany) (ISSTA 2016). Association for Computing Machinery, New York, NY, USA, 318-329. https://doi.org/10.1145/2931037.2931044
Tarek Mahmud, Meiru Che, and Guowei Yang. 2022. ACID: An API Compatibility Issue Detector for Android Apps. In Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings (Pittsburgh, Pennsylvania) (ICSE '22). Association for Computing Machinery, New York, NY, USA, 1-5. https://doi.org/10.1145/3510454.3516854
H. B. Mann and D. R. Whitney. 1947. On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other. Annals of Mathematical Statistics 18, 1 (03 1947), 50-60. https://doi.org/10.1214/aoms/1177730491
Damien Octeau, Daniel Luchaup, Matthew Dering, Somesh Jha, and Patrick McDaniel. 2015. Composite Constant Propagation: Application to Android Inter- Component Communication Analysis. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (Florence, Italy) (ICSE '15). IEEE Press, 77-88.
Lucky Onwuzurike, Enrico Mariconti, Panagiotis Andriotis, Emiliano De Cristofaro, Gordon Ross, and Gianluca Stringhini. 2019. MaMaDroid: Detecting Android Malware by Building Markov Chains of Behavioral Models (Extended Version). ACM Trans. Priv. Secur. 22, 2, Article 14 (apr 2019), 34 pages. https: //doi.org/10.1145/3313391
Felix Pauck and Heike Wehrheim. 2021. Jicer: Simplifying Cooperative Android App Analysis Tasks. In 2021 IEEE 21st International Working Conference on Source Code Analysis and Manipulation (SCAM). 187-197. https://doi.org/10. 1109/SCAM52516.2021.00031
Michael Reif, Florian Kübler, Michael Eichberg, Dominik Helm, and Mira Mezini. 2019. Judge: Identifying, Understanding, and Evaluating Sources of Unsoundness in Call Graphs. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (Beijing, China) (ISSTA 2019). Association for Computing Machinery, New York, NY, USA, 251-261. https://doi.org/10.1145/3293882.3330555
Columbus repository. 2023. https://github.com/ucsb-seclab/columbus. Accessed December 2023.
Jordan Samhi. 2023. Analyzing the Unanalyzable: an Application to Android Apps. Ph.D. Dissertation. University of Luxembourg, Luxembourg City, Luxembourg. http://hdl.handle.net/10993/54372
J. Samhi, A. Bartel, T. F. Bissyande, and J. Klein. 2021. RAICC: Revealing Atypical Inter-Component Communication in Android Apps. In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE). IEEE Computer Society, Los Alamitos, CA, USA, 1398-1409. https://doi.org/10.1109/ICSE43902.2021.00126
J. Samhi, T. F. Bissyande, and J. Klein. 2024. AndroLibZoo: A Reliable Dataset of Libraries Based on Software Dependency Analysis. In 2024 IEEE/ACM 21st International Conference on Mining Software Repositories (MSR).
Jordan Samhi, Jun Gao, Nadia Daoudi, Pierre Graux, Henri Hoyez, Xiaoyu Sun, Kevin Allix, Tegawendé F Bissyandé, and Jacques Klein. 2022. JuCify: A Step Towards Android Code Unification for Enhanced Static Analysis. In 2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE). IEEE Computer Society, Los Alamitos, CA, USA, 1232-1244. https://doi.org/10.1145/3510003.3512766
J. Samhi, L. Li, T. F. Bissyande, and J. Klein. 2022. Difuzer: Uncovering Suspicious Hidden Sensitive Operations in Android Apps. In 2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE). IEEE Computer Society, Los Alamitos, CA, USA, 723-735. https://doi.org/10.1145/3510003.3510135
Jordan Samhi and Andreas Zeller. 2024. AndroLog: Android Instrumentation and Code Coverage Analysis. In Companion Proceedings of the 32nd ACM International Conference on the Foundations of Software Engineering (Porto de Galinhas, Brazil) (FSE 2024). Association for Computing Machinery, New York, NY, USA, 597-601. https://doi.org/10.1145/3663529.3663806
Audio Service. 2023. https://github.com/ryanheise/audio_service. Accessed December 2023.
Dakota Soles. 2023. An Empirical Study of Nondeterministic Behavior and Its Causes in Static Analysis Tools. ECOOP and ISSTA 2023 Student Research Competition.
Li Sui, Jens Dietrich, Michael Emery, Shawn Rasheed, and Amjed Tahir. 2018. On the Soundness of Call Graph Construction in the Presence of Dynamic Language Features - A Benchmark and Tool Evaluation. In Programming Languages and Systems, Sukyoung Ryu (Ed.). Springer International Publishing, Cham, 69-88.
Unity. 2023. Unity. https://unity.com Accessed December 2023.
Wenyu Wang, Wing Lam, and Tao Xie. 2021. An Infrastructure Approach to Improving Effectiveness of Android UI Testing Tools. In Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis (Virtual, Denmark) (ISSTA 2021). Association for Computing Machinery, New York, NY, USA, 165-176. https://doi.org/10.1145/3460319.3464828
Wenyu Wang, Dengfeng Li, Wei Yang, Yurui Cao, Zhenwen Zhang, Yuetang Deng, and Tao Xie. 2018. An Empirical Study of Android Test Generation Tools in Industrial Cases. In 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE). 738-748. https://doi.org/10.1145/3238147.3240465
Yan Wang, Hailong Zhang, and Atanas Rountev. 2016. On the Unsoundness of Static Analysis for Android GUIs. In Proceedings of the 5th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis (Santa Barbara, CA, USA) (SOAP 2016). Association for Computing Machinery, New York, NY, USA, 18-23. https://doi.org/10.1145/2931021.2931026
Fengguo Wei, Sankardas Roy, Xinming Ou, and Robby. 2014. Amandroid: A Precise and General Inter-Component Data Flow Analysis Framework for Security Vetting of Android Apps. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (Scottsdale, Arizona, USA) (CCS '14). Association for Computing Machinery, New York, NY, USA, 1329-1341. https://doi.org/10.1145/2660267.2660357
Daoyuan Wu, Debin Gao, Robert H. Deng, and Chang Rocky K. C. 2021. When Program Analysis Meets Bytecode Search: Targeted and Efficient Inter-procedural Analysis of Modern Android Apps in BackDroid. In 2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 543-554. https://doi.org/10.1109/DSN48987.2021.00063
Tianyong Wu, Jierui Liu, Zhenbo Xu, Chaorong Guo, Yanli Zhang, Jun Yan, and Jian Zhang. 2016. Light-Weight, Inter-Procedural and Callback-Aware Resource Leak Detection for Android Apps. IEEE Transactions on Software Engineering 42, 11 (2016), 1054-1076. https://doi.org/10.1109/TSE.2016.2547385
XAMARIN. 2023. https://dotnet.microsoft.com/apps/xamarin. Accessed December 2023.
Jiwei Yan, Shixin Zhang, Yepang Liu, Jun Yan, and Jian Zhang. 2022. ICCBot: Fragment-Aware and Context-Sensitive ICC Resolution for Android Applications. In 2022 IEEE/ACM 44th International Conference on Software Engineering: Companion Proceedings (ICSE-Companion). 105-109. https://doi.org/10.1109/ICSECompanion55297.2022.9793791
Shengqian Yang, Dacong Yan, Haowei Wu, Yan Wang, and Atanas Rountev. 2015. Static Control-Flow Analysis of User-Driven Callbacks in Android Applications. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, Vol. 1. 89-99. https://doi.org/10.1109/ICSE.2015.31
Shengqian Yang, Dacong Yan, Haowei Wu, Yan Wang, and Atanas Rountev. 2015. Static Control-Flow Analysis of User-Driven Callbacks in Android Applications. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, Vol. 1. 89-99. https://doi.org/10.1109/ICSE.2015.31