Automata-Based String Analysis for Detecting Malware in Android Programs
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:80053", author = "Assad Maalouf and Lunjin Lu and James Lynott", title = "Automata-Based String Analysis for Detecting Malware in Android Programs", 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.", volume = "14", number = "12", pages = "500-8", }
