Automata-Based String Analysis for Detecting Malware in Android Programs

Authors: Assad Maalouf, Lunjin Lu, James Lynott

Abstract:

We design and implement a precise model of string operations using finite state machine transformers and state transformers to approximate the values string variables can take throughout the execution of the program.We use our model to analyze Android program string variables. Our experimental results show that our string analysis is very efficient at detecting the contextual effect of string operations on the string variables. Our model proved to be very useful when it came to verifying statements about the string variables of the program.

Keywords: Abstract interpretation, android, static analysis, string analysis.

References:

[1] “Open web application security project..” Available at https://www. owasp.org.
[2] A. S. Christensen, A. Møller, and M. I. Schwartzbach, “Precise analysis of string expressions,” in International Static Analysis Symposium, pp. 1–18, Springer, 2003.
[3] F. Yu, T. Bultan, M. Cova, and O. H. Ibarra, “Symbolic string verification: An automata-based approach,” in International SPIN Workshop on Model Checking of Software, pp. 306–324, Springer, 2008.
[4] S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel, “Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps,” SIGPLAN Not., vol. 49, pp. 259–269, June 2014.
[5] D. Li, Y. Lyu, M. Wan, and W. G. Halfond, “String analysis for java and android applications,” in Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, pp. 661–672, ACM, 2015.
[6] D. Octeau, P. McDaniel, S. Jha, A. Bartel, E. Bodden, J. Klein, and Y. Le Traon, “Effective inter-component communication mapping in android: An essential step towards holistic security analysis,” in Presented as part of the 22nd {USENIX} Security Symposium ({USENIX} Security 13), pp. 543–558, 2013.
[7] E. Bodden, “Inter-procedural data-flow analysis with ifds/ide and soot,” in Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis, pp. 3–8, ACM, 2012.
[8] A. Einarsson and J. D. Nielsen, “A survivorâ˘A ´ Zs guide to java program analysis with soot,” BRICS, Department of Computer Science, University of Aarhus, Denmark, p. 17, 2008.
[9] C. Fritz, S. Arzt, S. Rasthofer, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel, “Highly precise taint analysis for android applications,” 2013.
[10] R. Amadini, A. Jordan, G. Gange, F. Gauthier, P. Schachte, H. Søndergaard, P. J. Stuckey, and C. Zhang, “Combining string abstract domains for javascript analysis: an evaluation,” in International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 41–57, Springer, 2017.
[11] G. Costantini, P. Ferrara, and A. Cortesi, “A suite of abstract domains for static analysis of string values,” Software: Practice and Experience, vol. 45, no. 2, pp. 245–287, 2015.
[12] M. Madsen and E. Andreasen, “String analysis for dynamic field access,” in International Conference on Compiler Construction, pp. 197–217, Springer, 2014.
[13] S. H. Jensen, A. Møller, and P. Thiemann, “Type analysis for javascript,” in International Static Analysis Symposium, pp. 238–255, Springer, 2009.
[14] V. Kashyap, K. Dewey, E. A. Kuefner, J. Wagner, K. Gibbons, J. Sarracino, B. Wiedermann, and B. Hardekopf, “Jsai: a static analysis platform for javascript,” in Proceedings of the 22nd ACM SIGSOFT international symposium on Foundations of Software Engineering, pp. 121–132, ACM, 2014.
[15] H. Lee, S. Won, J. Jin, J. Cho, and S. Ryu, “Safe: Formal specification and implementation of a scalable analysis framework for ecmascript,” in FOOL 2012: 19th International Workshop on Foundations of Object-Oriented Languages, p. 96, Citeseer, 2012.
[16] F. Yu, T. Bultan, and O. H. Ibarra, “Relational string verification using multi-track automata,” International Journal of Foundations of Computer Science, vol. 22, no. 08, pp. 1909–1924, 2011.
[17] R. Padhye and U. P. Khedker, “Interprocedural data flow analysis in soot using value contexts,” in Proceedings of the 2nd ACM SIGPLAN International Workshop on State Of the Art in Java Program analysis, pp. 31–36, ACM, 2013.
[18] N. Almashfi, L. Lu, K. Picker, and C. Maldonado, “Precise string analysis for javascript programs using automata,” in Proceedings of the 2019 8th International Conference on Software and Computer Applications, pp. 159–166, ACM, 2019.
[19] “Droidbench benchmark suite.,” 2020. Available at https://github.com/ secure-software-engineering/DroidBench.
[20] “Icc-bench benchmark suite.,” 2020. Available at https://github.com/ fgwei/ICC-Bench.
[21] L. Qiu, Y. Wang, and J. Rubin, “Analyzing the analyzers: Flowdroid/iccta, amandroid, and droidsafe,” in Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 176–186, ACM, 2018.
[22] “Taint analysis of strings with automatons.,” 2020. Available at https:// drive.google.com/file/d/1RmxuFvk6TCCFxSuUuUss9cUVKI3zHOwV/ view?usp=sharing.