Improving Taint Analysis of Android Applications Using Finite State Machines

Authors: Assad Maalouf, Lunjin Lu, James Lynott

Abstract:

We present a taint analysis that can automatically detect when string operations result in a string that is free of taints, where all the tainted patterns have been removed. This is an improvement on the conservative behavior of previous taint analyzers, where a string operation on a tainted string always leads to a tainted string unless the operation is manually marked as a sanitizer. The taint analysis is built on top of a string analysis that uses finite state automata to approximate the sets of values that string variables can take during the execution of a program. The proposed approach has been implemented as an extension of FlowDroid and experimental results show that the resulting taint analyzer is much more precise than the original FlowDroid.

Keywords: Android, static analysis, string analysis, taint analysis.

References:

[1] S. Calzavara, I. Grishchenko, and M. Maffei, “Horndroid: Practical and sound static analysis of android applications by smt solving,” in 2016 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 47–62, IEEE, 2016.
[2] F. Wei, S. Roy, X. Ou, et al., “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, pp. 1329–1341, ACM, 2014.
[3] “Taint analysis of strings with automatons.,” 2020. Available at https:// drive.google.com/file/d/1RmxuFvk6TCCFxSuUuUss9cUVKI3zHOwV/ view?usp=sharing.
[4] 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.
[5] 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.
[6] L. Li, A. Bartel, T. F. Bissyandé, J. Klein, Y. Le Traon, S. Arzt, S. Rasthofer, E. Bodden, D. Octeau, and P. McDaniel, “Iccta: Detecting inter-component privacy leaks in android apps,” in Proceedings of the 37th International Conference on Software Engineering-Volume 1, pp. 280–291, IEEE Press, 2015.
[7] W. Klieber, L. Flynn, A. Bhosale, L. Jia, and L. Bauer, “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, pp. 1–6, ACM, 2014.
[8] A. Rountev and D. Yan, “Static reference analysis for gui objects in android software,” in Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’14, (New York, NY, USA), pp. 143:143–143:153, ACM, 2014.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] “Droidbench benchmark suite.,” 2020. Available at https://github.com/ secure-software-engineering/DroidBench.
[19] “Icc-bench benchmark suite.,” 2020. Available at https://github.com/ fgwei/ICC-Bench.
[20] 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.
[21] “An insecure example application.,” 2020. Available at https://github. com/hdiv/insecure-bank.