Improving Taint Analysis of Android Applications Using Finite State Machines
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:80071", author = "Assad Maalouf and Lunjin Lu and James Lynott", title = "Improving Taint Analysis of Android Applications Using Finite State Machines", 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.", volume = "14", number = "12", pages = "524-7", }
