Обзор подходов к улучшению качества результатов статического анализа программ

Автор: Герасимов А.Ю.

Журнал: Труды Института системного программирования РАН @trudy-isp-ran

Статья в выпуске: 3 т.29, 2017 года.

Бесплатный доступ

В настоящий момент индустрия создания программ для всевозможного рода вычислительных устройств находится в состоянии бурного развития. Постоянно увеличивающаяся мощность вычислительных систем предоставляет всё новые возможности для создания высокопроизводительных, в том числе - параллельных, программ и программных комплексов. В связи с этим постоянно возрастает сложность программного обеспечения, управляющего вычислительными системами. Из-за высокой сложности программных систем процесс обеспечения качества разрабатываемого программного обеспечения требует новых подходов к процессу проверки корректности программ как на соответствие требованиям пользователей, так и на наличие критических дефектов и уязвимостей безопасности. Одним из методов контроля качества программного обеспечения является применение инструментальных средств программиста, предназначенных для анализа программ. Отрасль создания инструментальных средств статического и динамического анализа программ активно развивается с начала 2000-х годов. Разрабатывается большое количество академических и промышленных сред и инструментов анализа программ. В связи с фундаментальными ограничениями и инженерными компромиссами в угоду производительности и масштабируемости инструменты статического анализа не всегда могут обеспечить отсутствие ошибок первого рода в результатах своей работы. При этом анализ предупреждений инструмента может отнимать значительное время высококвалифицированного эксперта в области разработки и обеспечения качества программного обеспечения. В связи с этим возникает задача улучшения качества результатов работы статических анализаторов программ. Данная статья посвящена обзору методов анализа программ и подходов к улучшению качества работы статических анализаторов. Особое внимание в статье уделяется методам совмещения подходов статического и динамического анализа программ.

Еще

Статический анализ программ, динамический анализ программ, комбинированный анализ программ

Короткий адрес: https://sciup.org/14916443

IDR: 14916443 | DOI: 10.15514/ISPRAS-2017-29(3)-6

Список литературы Обзор подходов к улучшению качества результатов статического анализа программ

Sketch of The Analytical Engine Invented by Charles Babbage by L. F. Menabea from the Bibliotheque Universalle de Geneve, October, 1942, No. 82. With notes upon the Memoir by the translator Ada Augusta, countess of Lovelace. HTML referenced 05.05.2017: https://www.fourmilab.ch/babbage/sketch.html
Per Runeson, Carian Andersson, Thomas Thelin, Anneliese Andrews, Tomas Berling. What Do We Know about Defect Detection Methods? IEEE Software May/June 2006
IEEE 1044-2009 Standard Classification for Software Anomalies. IEEE. 3 Park Avenue, New Yourk, NY 10016-5997, USA, 7 January 2010, ISBN 978-0-7381-6114-3
Gerald J. Holzmann. The Power of 10: Roles for Developing Safety-Critical Code. Computer/2006, vol. 39, no. 6, pp 95-97
MISRA C: 2004 Guidelines for the use of the C language in critical systems. First published October 2004, by MIRA Limited, Watling Street, Nuneaton, Warkwickshire CV10 0TU UK, ISBN 978-0-9524156-4-0
E. J. Weyuker, T. J. Ostrand. Theories of program testing and the application of revealing subdomains. IEEE Transactions on software engineering, 6(3):236-246. May 1980.
E. W. Dijkstra. On the reliability of the programs. HTML referenced 03.05.2017: https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD303.PDF
Dennis M. Ritchie. The development of the C language. Proceedings of HOPL-II The second ACM SIGPLAN conference on History of programming languages. Cambridge, MA, USA -April 20-23, 1993, pp. 201-208
S. C. Johnson. A Portable Compiler: Theory and Practice. Proceedings of 5th ACM POPL Symposium, January 1978
S. C. Johnson. Lint, a Program Checker. Unix Programmer’s manual, Seventh Edition, Vol. 2B, M.D. McIlroy and B.W. Kernigan, eds. AT&T Bell Laboratories: Murray Hill, NJ, 1979.
Benjamine Chelf, Andy Chou. The next generation of Static Analysis. Coverity, March 18, 2008. HTML referenced 24.04.2017: http://www.coverity.com/library/pdf/Coverity_White_Paper-SAT-Next_Generation_Static_Analysis.pdf
Pär Emanuelsson, Ulf Nilsson, A Comparative Study of Industrial Static Analysis Tools. Technical report. Department of Computer and Information Science, Linköping University. Linköping, Sweden, 2008.
Dawson Engler, Benjamin Chelf, Andy Chou, Seth Hallem. Checking system rules using system-specific, programmer-written compiler extensions. OSDI’00 Proceedings of the 4th conference on Symposium on Operating System Design and Implementation, Volume 4, Article No. 1. San Diego, California -October 22-25, 2000
Brittany Johnson, Yoonki Song, Emerson Murphy-Hill, Robert Bowdidge. Why don’t software developers use static analysis tools to find bugs?. ICSE’13 Proceedings of the 2013 International conference on Software Engineering. San Francisco, CA, USE, May 18-26, 2013
John Franco, John Martin. A history of Satisfiability. Handbook of Satisfiability. IOS Press, 2009 DOI: 10.3233/978-1-58603-929-5-3
Coverity Scan: 2012 Open Source Report. PDF referenced 24.04.2017: http://wpcme.coverity.com/wp-content/uploads/2012-Coverity-Scan-Report.pdf
Coverity Scan. Project Spotlight: Python. PDF referenced 24.04.2017: http://wpcme.coverity.com/wp-content/uploads/2013-Coverity-Scan-Spotlight-Python.pdf
Tukaram Muske, Alexander Serebrenik. Survey of Approaches for Handling Static Analysis Alarms. Proceedings of IEEE 16th International Working Conference on Source Code Analysis and Manipulation (SCAM). Raleigh, NC, USA. October 2-3, 2016
Woosuk Lee, Wonchan Lee, Kwengkeun Yi. Sound non-statistical clustering of static analysis alarms. VMCAI’12 Proceedings of the 13th international conference on verification, model checking and abstract verification interpretation. Philadelphia, PA, USA. January 22-24, 2012.
Zachary P. Fry, Westley Weimer. Clustering static analysis defect reports to Reduce maintenance costs. WCRE’13 Proceeding of 30th working conference on reverse engineering. Koblenz, Germany. October 14-17, 2013.
Ted Kremenek, Dawson Engler. Z-ranking: using statistical analysis to counter the impact of static analysis approximations. SAS’03 Proceedings of the 10th International conference on static analysis. San Diego, CA, USA. June 11, 2003.
Sunghun Kim, Michael D. Ernst. Prioritizing Warning Categories by Analyzing Software History. MSR’07 Proceedings of the Fourth International Workshop on Mining Software Repositories. Minneapolis, MN, USA. May 20-26, 2007.
Sunghun Kim, Michael D. Ernst. Which warnings should I fix first? ESEC-FSE’07 Proceedings of the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering. Dubrovnik, Croatia. September 03-07, 2007
Haihao Shen, Jianhong Fang, Jianjun Zhao. EFindBugs: Effective Error Ranking for FindBugs. ICST’11 Proceedings of the 2011 Fourth IEEE International conference on Software Testing, Verification and Validation. Berlin, Germany. March 21-25, 2011
Sunghun Kim, Michael D. Ernst. Prioritizing Software Inspection Results using Static Profiling. SCAM’06 Source code analysis and manipulation. Philadelphia, PA, USA. December 11, 2006.
Deguang Kong, Quan Zheng, Chao Chen, Jianmei Shuai, Ming Zhu. ISA: A source code static vulnerability detection system based on data fusion. InfoScale’07 Proceedings of the 2nd international conference on Scalable information systems. Suzhou, China. June 06-08, 2007
Na Meng, Qianxiang Wang, Qian Wu, Hong Mei. An approach to merge results of multiple static analysis tools. QSIC’08 Proceedings of the 2008 the eighth international conference on quality software. Oxford, UK. August 12-13, 2008
Quinn Hanam, Lin Tan, Reid Holmes, Patrick Lam. Finding patters in static analysis alerts. Improving actionable alert ranking. MSR 2014 Proceedings of the 11th working conference on mining software repositories. Hyderabad, India. May 31 -June 01, 2014
Ulas Yüskel, Hasan Sözer. Automated classification of static code analysis alerts: a case study. ICSM’13 Proceedings of the 2013 IEEE international conference on software maintenance. Eindhoven, Netherlands. September 24-26, 2013
Jaime Spacco, David Hovermeyer, William Pugh. Tracking defect warnings across versions. MSR’06 Proceedings of the 2006 international workshop on mining software repositories. Shanghai, China. May 22-23, 2006
Brahti Chimdyalwar, Shrawan Kumar. Effective false positive filtering for evolving software. ISEC’11 Proceedings of the 4th India software engineering conference. Thiruvananthapuram, Kerala, India. February 24-27, 2011
J. R. Rithruff, J. Penix, J. D. Morgenthaler, S. Elbaum, G. Rothermel. Predicting accurate and actionable static analysis warnings: and experimental approach. ICSE’08 Proceedings of the 30th international conference on software engineering. Leipzig, Germany. May 10-18, 2008
H. Post, C. Sinz, A. Kaiser, T. Gorges. Reducing false positives by combining abstract interpretation and bounded model checking. ASE’08 Proceedings of the 2008 23rd IEEE/ACM international conference on automated software engineering. L’Aquila, Italy. September 15-19, 2008
Tukaram Muske, Advaita Datar, Mayur Khanzode, Kumar Madhukar. Efficient elimination of false positives using bounded model checking. ISSRE’15 Proceedings of the 2015 IEEE 26th international symposium on software reliability engineering. Gaithersburg, MD, USA. November 2-5, 2015
M. Junker, R. Huuck, A. Fehnker, A. Knapp. SMT-based false positive elimination in static program analysis". ICFEM’12 Proceedings of the 14th international conference on formal engineering methods: formal mehods and software engineering. Kyoto, Japan. November 12-16, 2012
G. Brat, W. Visser. Combining static analysis and model checking for software analysis tools. ACE’01 Proceedings of the 16th IEEE international conference on automated software engineering. San Diego, CA, USA. November 26-29, 2001
A. Fenker, R. Huuck. Model checking driven static analysis for the real world: designing and tuning large scale bug detection. Journal Innovations in systems and software engineering. Volume 9, Issue 1, March 2013
D. Hovemeyer, W. Pugh. Finding bugs easily. ACM SIGPLAN notices. Volume 39, issue 12, December 2004
D. Evans, D. Larochelle. Improving security using extensible lightweight static analysis. IEEE Software. Volume 19, Issue 1, 2002
C. Csallner, Y. Smaragdakis. Check’N’Crash: combining static checking and testing. ICSE’05 Proceedings of the 27th international conference on software engineering. St. Luis, MO, USA. May 15-21, 2005
C. Flanagan, K Rustan, M. Leino, M. Lillibridge, G. Nelson, J. B. Saxe, R. Stata. Extended static checking for Java. PLDI’02 Proceedings of the ACM SIGPLAN 2002 conference on programming language design and implementation. Berlin, Germany. June 17-19, 2002
C. Csallner, Y. Smaragdakis. JCrasher: an automatic robustness testing tester for Java. Software -Practice & Experience. Volume 34, Issue 11. September 2004.
C. Csallner, Y. Smaragdakis. DSD-Crasher: a hybrid analysis tool for bug finding. ISSTA’06 Proceedings of the 2006 international symposium on software testing and analysis. Portland, Maide, USA July 17-20, 2006
O. Chebaro, N Kosmatov, A. Giorgetti, J. Julliand. Programs slicing enhances a verification technique combining static and dynamic analysis. SAC’12 Proceedings of the 27th annual ACM symposium of applied computing. Trento, Italy. March 26-30, 2012
K. Li, C Reichenbach, C. Csallner, Y. Smaragdakis. Residual investigation: predictive and precise bug detection. ISSTA’2012 Proceedings of the 2012 international symposium on software testing and analysis. Minneanapolis, MN, USA. July 15-20, 2012
F. Elberzhager, J. Münch, V.T. Ngoc Nha. A systematic study on the combination of static and dynamic quality assurance techniques. Infromation and siftware technology. Vol. 54, Issue1. January, 2012
A. Hanna, H. Z. Ling, X Yang, M. Debbabi. A synergy between static and dynamic analysis for the detection of software security vulnerabilities. OTM’09 Proceedings of the confederated international congress, CoopIS, DOA, IS and ADBASE 2009 on on the move to meaningful internet systems: part II. Vilamoura, Protugal. November 01-06, 2009
R. Hadjidj, X. Yang, S. Tlili, M. Debabi. Model-checking for software vulnerabilities detection with multi-language support. PST’08 Proceedings of the 2008 sixth annual conference on privacy, security and trust. Fredericton, NB, Canada. October 01-03, 2008.
D. Novillo. Tree SSA: a new optimization infrastructure for GCC. Proceedings of the GCC developers summit. Ottawa, ON, Canada. May 25-27, 2003
S. Schwoon. Model-checking pushdown systems. PhD thesis. Technischen Universität München. 2002
C. Artho, A. Biere. Combined static and dynamic analysis. Technical Report 466, ETH Zürich, Zürich, Switzerland, 2005.
O. Chebaro, N. Kostomarov, A. Giorgetti, J. Julliand. Combining static analysis and test generation for C program debugging. TAP’10 Proceedings of the 4th international conference on tests and proofs. Málaga, Spain. July 01-02, 2010
N. Williams, B. Marre, P. Mouy, M. Roger. PathCrawler: automatic generation of tests by combining static and dynamic analysis. EDCC’05 Proceedings of the 5th European conference on dependable computing. Budapest, Hungary. April 20-22, 2005
P. Cuoq, F. Kirchner, N. Kosmatov, V. Prevosto, J. Signoles, B. Yakobowski. Frama-C: a software analysis perspective. SEFM’12 Proceedings of the 10th international conference on software engineering and formal methods. Thesaloniki, Grece. October 01-05, 2012
P. Cuoq, F. Kirchner, N. Kosmatov, V. Prevosto, J. Signoles, B. Yakobowski. Frama-C: a software analysis perspective. Formal aspects of computing. Volume 27, issue 3. May, 2015
A. V. Nori, S. K. Rajamani, S. Tetali, A. V. Thakur. The Yogi ptoject: software property checking via static analysis and testing. TACAS’09 Proceedings of the 15th international conference on tools and algorithms for the construction and analysis of systems: held as part of the ETAPS’09 joint European conferences on theory and practice of software. York, UK. March 22-29, 2009.
T. Ball, S. K. Rajamani. Slic: a specification language for interface checking (of C). Technical report MSR-TR2001-21, Microsoft Research. Redmond, WA, USA. January, 10. 2002
S. Rawat, D. Ceara, L. Mounier, M.-L. Potet. Combining static and dynamic analysis of vulnerability detection. Cornell University Library arXiv:1305.3883. May 16, 2013
T. Ball. The concept of dynamic analysis. ESEC/FSE-7 Proceedings of the 7th European software engineering conference held jointly with 7th ACM SIGSOFT international symposium on foundations of software engineering. Toulouse, France. September 06-10, 1999
J. Schütte, R. Fedler, D. Titze. ConDroid: targeted dynamic analysis of Android applications. AINA’15 Proceedings of IEEE 29th international conference on advanced information networking and applications. Gwangui, South Korea. March 24-27, 2015
X. Ge, K. Taneja, T. Xie, N. Tillmann. DyTa: dynamic symbolic execution guided with static verification results. ICSE’11 Proceedings of the 33th international conference on software engineering. Waikiki, Honolulu, HI, USA. May 21-28, 2011
N. Tillmann, J. de Hallex. Pex -white box test generation for.NET. TAP’08 Proceedings of the 2nd international conference on tests and proofs. Prato, Italy. April 09-11, 2008
M. Y. Wong, D. Lie. IntelliDroid: a targeted input generator for the dynamic analysis of android malware. NDSS’16 The network and distributed system security symposium 2016. San Diego, CA, USA. February 21-24, 2016
H. Gunadi. Formal certification of non-interferent Android bytecode (DEX bytecode). ICECCS’15 Proceedings of the 2015 20th international conference on engineering and complex computer systems. Gold Coast, Australia. December 9-12, 2015
L. De Moura, N. Bjørner. Z3: an efficient SMT solver. TACAS’08/ETAPS’08 Proceedings of the theory and practice of software, 14th international conference on tools and algorithms for the constructions and analysis of systems. Budapest, Hungary. March 29 -April 06, 2009
Chen N., Kim S. STAR: stack trace based automatic crash reproduction via symbolic execution. IEEE transactions on software engineering. 2015, volume 41, issue 2.
T. Avgerinos, S. Kil Cha, A. Rebert, E. J. Schwartz, M. Woo, D. Brumley. Automatic exploit generation. Communications of the ACM, volume 57, issue 2, February 2014.
M. Li, Y. Chen, L. Wang, G. Xu. Dynamically validating static memory leak warnings. ISSTA’13 Proceedings of the 2013 international symposium on software testing and analysis. Lugano, Switzerland. July 15-20, 2013.
HP Fortify. https://saas.hpe.com/en-us/software/sca, accessed 05.05.2017
CREST -automatic test generation tool for C. https://github.com/jburnim/crest, accessed 05.05.2017
D. Babić, L. Martignoni, S. McCamant, S. Song. Statically-directed dynamic automated test generation. ISSTA’11 Proceedings of the 2011 international symposium on software testing and analysis. Toronto, Ontario, Canada. July 17-21, 2011
N. Nethercote, J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. PLDI’07 Proceedings of the 28th ACM SIGPLAN Conference on programming languages design and implementation. San Diego, CA, USA. June 10-13, 2007
F. Bellard. QEMU, a fast and portable dynamic translator. ATEC’05 Proceedings of the annual conference on USENIX annual technical conference. Anaheim, CA, USA. April 10-15, 2005
J. Seward, N. Nethercote. Using Valgrind to detect undefined value errors with bit-precision. ATEC’05 Proceedings of the annual conference on USENIX annual technical conference. Anaheim, CA, USA. April 10-15, 2005
V. Chipounov, V. Kuznetsov, G. Candea. S2E: a platform for in-vivo multi-path analysis of software systems. ASPLOS XVI Proceedings of the sixteenth international conference on architectural support for programming languages and operating systems. Newport Beach, CA, USA. March 05-11, 2011

Еще

Статья научная