The Use of Dependencies for Improving the Precision of Program Static Analysis
Abstract
The development of dependency analysis methods in order to improve static code analysis precision is considered in this paper. Reasons for precision loss is abstract interpretation methods when detecting defects in program source code are explained. The need for program object dependency extraction and interpretation is justified by numerous real-world examples. A dependency classification is presented. The necessity for aggregate analysis of values and dependencies is considered. The dependency extraction from assignment statements is described. The dependency interpretation based on logic inference using logic and arithmetic rules is proposed. The methods proposed are implemented in defect detection tool Digitek Aegis and significant increase of precision is shown.
About the Authors
M. I. Glukhikh
Санкт-Петербургский государственный политехнический университет
Russian Federation
Russian Federation
V. M. Itsykson
Санкт-Петербургский государственный политехнический университет
Russian Federation
Russian Federation
V. A. Tsesko
Санкт-Петербургский государственный политехнический университет
Russian Federation
Russian Federation
References
1. Zhivich M., Cunningham R. The Real Cost of Software Errors. IEEE Security & Privacy // IEEE Computer Society. 2009. Vol. 7, № 2.
2. Nielson F., Nielson N., Hankin C. Principles of Program Analysis. Corr. 2nd printing. Springer, 2005. XXI. 452 p.
3. Cousot P. Abstract Interpretation. ACM Computing Surveys (CSUR) // ACM, New York, 1996. Vol. 28, Issue 2. P. 324-328.
4. Jones N., Nielson F. Abstract Interpretation: A Semantic-based Tool for Program Analysis. Handbook of logic in computer science (vol. 4): semantic modeling. Oxford: Oxford University Press, 1995. P. 527-636.
5. Несов В. С., Маликов О. Р. Использование информации о линейных зависимостях для обнаружения уязвимостей в исходном коде программ // Труды ИСП РАН. 2006. №9. С. 51-57.
6. Cousot P., Halbwachs N. Automatic discovery of linear restraints among variables of a program // Proceedings of the 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL '78). ACM, New York, 1978. P. 8496.
7. Code Analysis for C/C++ Overview, Microsoft Corporation. <http://msdn.microsoft.com/en-us/library/d3bbz7tz.aspx>
8. Frama-C Software Analyzers. <http://frama-c.com>
9. Splint home page. <http://www.splint.org>
10. Fortify Software. <http://www.fortify.com>
11. Ицыксон В.М., Моисеев М. Ю., Цесько В. А., Карпенко А. В. Исследование систем автоматизации обнаружения дефектов в исходном коде программного обеспечения // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2008. №5(65). C. 119-127.
12. Schwartzbach M. Lecture Notes on Static Analysis. Aarhus, 2000. 58 p.
13. Aegis - a defect detection system. <http://www.digiteklabs.ru/aegis>
14. Ицыксон В. М., Моисеев М. Ю., Цесько В. А., Захаров А. В., Ахин М.Х. Алгоритм интервального анализа для обнаружения дефектов в исходном коде программ // Информационные и управляющие системы. 2009. №2 (39). C. 3441.
15. Ицыксон В. М., Моисеев М. Ю., Ахин М.Х., Захаров А. В., Цесько В. А. Алгоритмы анализа указателей для обнаружения дефектов в исходном коде // Системное программирование. 2009. C. 5-30.
16. Bush W., Pincus J., Sielaff D. A static analyzer for finding dynamic programming errors // Software: Practice and Experience. Vol. 30, iss. 7 (June 2000). John Wiley & Sons, Inc. NY, USA. P. 775-802.
17. Wang A., Fei H., Gu M., Song X. Verifying Java Programs By Theorem Prover HOL // Proceedings of the 30th Annual International Computer Software and Applications Conference. Vol. 01. IEEE Computer Society Washington DC, USA 2006. P. 139-142.
18. HOL 4 Kananaskis 6. <http://hol.sourceforge.net>
19. WHY - a software verification platform. <http://why.lri.fr>
20. Steensgaard B. Points-to analysis in almost linear time // Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, USA, 1996. P. 32-41.
21. Avots D., Dalton M., Livshits V., Lam M. Improving software security with a C pointer analysis // Proceedings of the 27th international conference on Software engineering. New York, USA, 2005. P. 332-341.
22. VCC. <http://vcc.codeplex.com>
23. Z3. <http://research.microsoft.com/en-us/um/redmond/projects/z3>
24. SMT-LIB. <http://www.smtlib.org>
Review
For citations:
Glukhikh M.I., Itsykson V.M., Tsesko V.A. The Use of Dependencies for Improving the Precision of Program Static Analysis. Modeling and Analysis of Information Systems. 2011;18(4):68-79. (In Russ.)
Views:
541
Email this article 