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

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

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

1. 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. https://www.fourmilab.ch/babbage/sketch.html, , дата обращения 05.05.2017

2. Per Runeson, Carian Andersson, Thomas Thelin, Anneliese Andrews, Tomas Berling. What Do We Know about Defect Detection Methods? IEEE Software May/June 2006

3. 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

4. Gerald J. Holzmann. The Power of 10: Roles for Developing Safety-Critical Code. Computer/ 2006, vol. 39, no. 6, pp 95-97

5. 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

6. 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.

7. E. W. Dijkstra. On the reliability of the programs. https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD303.PDF, дата обращения 05.05.2017

8. 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

9. S. C. Johnson. A Portable Compiler: Theory and Practice. Proceedings of 5th ACM POPL Symposium, January 1978

10. 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.

11. Benjamine Chelf, Andy Chou. The next generation of Static Analysis. Coverity, March 18, 2008. http://www.coverity.com/library/pdf/Coverity_White_Paper-SAT-Next_Generation_Static_Analysis.pdf, , дата обращения 05.05.2017

12. 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.

13. 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

14. 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

15. John Franco, John Martin. A history of Satisfiability. Handbook of Satisfiability. IOS Press, 2009 doi:10.3233/978-1-58603-929-5-3

16. Coverity Scan: 2012 Open Source Report. http://wpcme.coverity.com/wp-content/uploads/2012-Coverity-Scan-Report.pdf, дата обращения 05.05.2017

17. Coverity Scan. Project Spotlight: Python. http://wpcme.coverity.com/wp-content/uploads/2013-Coverity-Scan-Spotlight-Python.pdf, дата обращения 05.05.2017

18. 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

19. 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.

20. 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.

21. 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.

22. 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.

23. 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

24. 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

25. 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.

26. 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

27. 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

28. 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

29. 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

30. 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

31. 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

32. 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

33. 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

34. 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

35. 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

36. 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

37. 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

38. D. Hovemeyer, W. Pugh. Finding bugs easily. ACM SIGPLAN notices. Volume 39, issue 12, December 2004

39. D. Evans, D. Larochelle. Improving security using extensible lightweight static analysis. IEEE Software. Volume 19, Issue 1, 2002

40. 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

41. 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

42. C. Csallner, Y. Smaragdakis. JCrasher: an automatic robustness testing tester for Java. Software – Practice & Experience. Volume 34, Issue 11. September 2004.

43. 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

44. 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

45. 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

46. 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

47. 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

48. 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.

49. D. Novillo. Tree SSA: a new optimization infrastructure for GCC. Proceedings of the GCC developers summit. Ottawa, ON, Canada. May 25-27, 2003

50. S. Schwoon. Model-checking pushdown systems. PhD thesis. Technischen Universität München. 2002

51. C. Artho, A. Biere. Combined static and dynamic analysis. Technical Report 466, ETH Zürich, Zürich, Switzerland, 2005.

52. 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

53. 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

54. 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

55. 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

56. 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.

57. 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

58. 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

59. 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

60. 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

61. 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

62. 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

63. 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

64. 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

65. 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

66. Chen N., Kim S. STAR: stack trace based automatic crash reproduction via symbolic execution. IEEE transactions on software engineering. 2015, volume 41, issue 2.

67. 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.

68. 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.

69. HP Fortify. https://saas.hpe.com/en-us/software/sca, дата обращения 05.05.2017:

70. CREST – automatic test generation tool for C. https://github.com/jburnim/crest, дата обращения 05.05.2017

71. 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

72. 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

73. 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

74. 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

75. 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