ABSTRACT
Runtime monitoring allows programmers to validate, for instance, the proper use of application interfaces. Given a property specification, a runtime monitor tracks appropriate runtime events to detect violations and possibly execute recovery code. Although powerful, runtime monitoring inspects only one program run at a time and so may require many program runs to find errors. Therefore, in this paper, we present ahead-of-time techniques that can (1) prove the absence of property violations on all program runs, or (2) flag locations where violations are likely to occur. Our work focuses on tracematches, an expressive runtime monitoring notation for reasoning about groups of correlated objects. We describe a novel flow-sensitive static analysis for analyzing monitor states. Our abstraction captures both positive information (a set of objects could be in a particular monitor state) and negative information (the set is known not to be in a state). The analysis resolves heap references by combining the results of three points-to and alias analyses. We also propose a machine learning phase to filter out likely false positives. We applied a set of 13 tracematches to the DaCapo benchmark suite and SciMark2. Our static analysis rules out all potential points of failure in 50% of the cases, and 75% of false positives on average. Our machine learning algorithm correctly classifies the remaining potential points of failure in all but three of 461 cases. The approach revealed defects and suspicious code in three benchmark programs.
- A. Aiken, J. S. Foster, J. Kodumal, and T. Terauchi. Checking and inferring local non-aliasing. In PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, pages 129--140, New York, NY, USA, 2003. ACM Press. Google ScholarDigital Library
- C. Allan, P. Avgustinov, A. S. Christensen, L. Hendren, S. Kuzins, O. Lhoták, O. de Moor, D. Sereni, G. Sittampalam, and J. Tibble. Adding Trace Matching with Free Variables to AspectJ. In OOPSLA, pages 345--364. ACM Press, 2005. Google ScholarDigital Library
- P. Avgustinov, A. S. Christensen, L. Hendren, S. Kuzins, J. Lhoták, O. Lhoták, O. de Moor, D. Sereni, G. Sittampalam, and J. Tibble. abc: An extensible AspectJ compiler. In AOSD, pages 87--98. ACM Press, 2005. Google ScholarDigital Library
- K. Bierhoff and J. Aldrich. Modular typestate checking of aliased objects. In OOPSLA, pages 301--320, 2007. Google ScholarDigital Library
- S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovic, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In OOPSLA, pages 169--190. ACM Press, 2006. Google ScholarDigital Library
- E. Bodden, F. Chen, and G. Roşu. Dependent advice: A general approach to optimizing history-based aspects (Extended version). Technical Report abc-2008-2, http://www.aspectbench.org/, March 2008.Google Scholar
- E. Bodden, L. J. Hendren, and O. Lhoták. A staged static program analysis to improve the performance of runtime monitoring. In ECOOP, volume 4609 of LNCS, pages 525--549. Springer, 2007. Google ScholarDigital Library
- E. Bodden, P. Lam, and L. Hendren. Object representatives: a uniform abstraction for pointer information. In 1st International Academic Research Conference of the British Computer Society (BCS 2008), Sept. 2008. To appear. Google ScholarDigital Library
- R. DeLine and M. Fähndrich. Typestates for objects. In ECOOP, volume 3086 of LNCS, pages 465--490, 2004.Google Scholar
- M. B. Dwyer and R. Purandare. Residual dynamic typestate analysis: Exploiting static analysis results to reformulate and reduce the cost of dynamic analysis. In ASE, pages 124--133. ACM Press, 2007. Google ScholarDigital Library
- S. Fink, E. Yahav, N. Dor, G. Ramalingam, and E. Geay. Effective typestate verification in the presence of aliasing. In ISSTA, pages 133--144. ACM Press, 2006. Google ScholarDigital Library
- B. Hackett and R. Rugina. Region-based shape analysis with tracked locations. In J. Palsberg and M. Abadi, editors, POPL, pages 310--323. ACM Press, 2005. Google ScholarDigital Library
- R. Kohavi. A study of cross-validation and bootstrap for accuracy estimation and model selection. In IJCAI, San Mateo, CA, pages 1137--1143, 1995. Google ScholarDigital Library
- M. Martin, B. Livshits, and M. S. Lam. Finding application errors using PQL: a program query language. In OOPSLA, pages 365--383. ACM Press, 2005. Google ScholarDigital Library
- H. Masuhara, G. Kiczales, and C. Dutchyn. A compilation and optimization model for aspect-oriented programs. In CC, volume 2622 of LNCS, pages 46--60, 2003. Google ScholarDigital Library
- N. A. Naeem and O. Lhoták. Extending typestate analysis to multiple interacting objects. In OOPSLA. ACM Press, Oct. 2008. To appear. Google ScholarDigital Library
- R. Pozo and B. Miller. Scimark 2.0, June 2000. http://math.nist.gov/scimark.Google Scholar
- M. Sridharan and R. Bodík. Refinement-based context-sensitive points-to analysis for Java. In PLDI, pages 387--400. ACM Press, 2006. Google ScholarDigital Library
- R. E. Strom and S. Yemini. Typestate: A programming language concept for enhancing software reliability. IEEE Trans. on Software Engineering, 12(1):157--171, 1986. Google ScholarDigital Library
- A. Wasylkowski, A. Zeller, and C. Lindig. Detecting object usage anomalies. In ESEC-FSE, pages 35--44, New York, NY, USA, 2007. ACM Press. Google ScholarDigital Library
- I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques (Second Edition). Morgan Kaufmann, June 2005. Google ScholarDigital Library
Recommendations
TAJ: effective taint analysis of web applications
PLDI '09Taint analysis, a form of information-flow analysis, establishes whether values from untrusted methods and parameters may flow into security-sensitive operations. Taint analysis can detect many common vulnerabilities in Web applications, and so has ...
Types, distribution, and test and correction times for programming errors
International Conference on Reliable SoftwareIn order to develop some basic information on software errors, an experiment in collecting data on types and frequencies of such errors was conducted at Bell Laboratories.
The paper reports the results of this experiment, whose objectives were to: (1) ...
FlowDroid: precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps
PLDI '14Today's smartphones are a ubiquitous source of private and confidential data. At the same time, smartphone users are plagued by carelessly programmed apps that leak important data by accident, and by malicious apps that exploit their given privileges to ...
Comments