Abstract
Modern development environments integrate various static analyses into the build process. Analyses that analyze the whole project whenever the project changes are impractical in this context. We present an approach to automatic incrementalization of analyses that are specified as tabled logic programs and evaluated using incremental tabled evaluation, a technique for efficiently updating memo tables in response to changes in facts and rules. The approach has been implemented and integrated into the Eclipse IDE. Our measurements show that this technique is effective for automatically incrementalizing a broad range of static analyses.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ashcraft, K., Engler, D.: Using programmer-written compiler extensions to catch security holes. In: Proceedings of the Symposium on Security and Privacy. IEEE, Los Alamitos (2002)
Ball, T., Cook, B., Levin, V., Rajamani, S.K.: Slam and static driver verifier: Technology transfer of formal methods inside Microsoft. In: Proceedings of IFM. Springer, Heidelberg (2004)
Besson, F., Jensen, T.P.: Modular class analysis with datalog. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694. Springer, Heidelberg (2003)
Blewitt, A., Bundy, A., Stark, I.: Automatic verification of java design patterns. In: Proceedings of ASE. IEEE, Los Alamitos (2001)
Bol, R., Degerstadt, L.: Tabulated resolution for well-founded semantics. In: Proceedings of ILPS. MIT Press, Cambridge (1993)
Burke, M.: An interval-based approach to exhaustive and incremental interprocedural data-flow analysis. TOPLAS 12(3) (1990)
Burke, M.G., Ryder, B.G.: A critical analysis of incremental iterative data flow analysis algorithms. IEEE Transactions on Software Engineering 16(7) (1990)
Carroll, M.D., Ryder, B.G.: Incremental data flow analysis via dominator and attribute update. In: Proceedings of POPL. ACM, New York (1988)
Chen, W., Warren, D.S.: Tabled evaluation with delaying for general logic programs. Journal of the ACM 43(1) (1996)
Conway, C.L., Namjoshi, K.S., Dams, D.R., Edwards, S.A.: Incremental algorithms for inter-procedural analysis of safety properties. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 449–461. Springer, Heidelberg (2005)
Crew, R.F.: Astlog: A language for examining abstract syntax trees. In: Proceedings of DSL. USENIX (1997)
Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K.: Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems 13(4) (1991)
Dawson, S., Ramakrishnan, C.R., Warren, D.S.: Practical program analysis using general purpose logic programming systems — a case study. In: Proceedings of PLDI. ACM, New York (1996)
Eichberg, M., Mezini, M., Ostermann, K., Schäfer, T.: Xirc: A kernel for cross-artifact information engineering in software development environments. In: Proceedings of WCRE. IEEE, Los Alamitos (2004)
Eichberg, M., Schäfer, T., Mezini, M.: Using annotations to check structural properties of classes. In: Cerioli, M. (ed.) FASE 2005. LNCS, vol. 3442, pp. 237–252. Springer, Heidelberg (2005)
Eichberg, M., Kahl, M., Saha, D., Mezini, M., Ostermann, K.: Automatic incrementalization of static analyses. Technical report (2006), http://www.st.informatik.tu-darmstadt.de/Magellan
Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley, Reading (1995)
Hajiyev, E., Verbaere, M., de Moor, O.: Codequest: Scalable source code queries with datalog. In: Thomas, D. (ed.) ECOOP 2006. LNCS, vol. 4067. Springer, Heidelberg (2006)
Hovemeyer, D., Pugh, W.: Finding bugs is easy. SIGPLAN Not. 39(12) (2004)
Landi, W., Ryder, B.G.: A safe approximate algorithm for interprocedural pointer aliasing. In: Proceedings of PLDI. ACM, New York (1992)
Liu, Y.A., Rothamel, T., Yu, F., Stoller, S.D., Hu, N.: Parametric regular path queries. In: Proceedings of PLDI. ACM, New York (2004)
Marlowe, T.J., Ryder, B.G.: An efficient hybrid algorithm for incremental data flow analysis. In: Proceedings of POPL. ACM, New York (1990)
Martin, M., Livshits, B., Lam, M.S.: Finding application errors and security flaws using PQL: a program query language. In: Proceedings of OOPSLA. ACM, New York (2005)
Pollock, L.L., Soffa, M.L.: An incremental version of iterative data flow analysis. IEEE Transactions on Software Engineering 15(12) (1989)
Ryder, B.G., Paull, M.C.: Incremental data-flow analysis algorithms. ACM Transactions on Programming Languages and Systems 10(1) (1988)
Saha, D., Ramakrishnan, C.R.: Incremental evaluation of tabled logic programs. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 392–406. Springer, Heidelberg (2003)
Saha, D., Ramakrishnan, C.R.: Incremental and demand-driven points-to analysis using logic programming. In: Proceedings of PPDP. ACM, New York (2005)
Saha, D., Ramakrishnan, C.R.: Symbolic support graph: A space-efficient data structure for incremental tabled evaluation. In: Gabbrielli, M., Gupta, G. (eds.) ICLP 2005. LNCS, vol. 3668, pp. 235–249. Springer, Heidelberg (2005)
Saha, D., Ramakrishnan, C.R.: Incremental evaluation of tabled prolog: Beyond pure logic programs. In: Van Hentenryck, P. (ed.) PADL 2006. LNCS, vol. 3819, pp. 215–229. Springer, Heidelberg (2005)
Saha, D., Ramakrishnan, C.R.: A local algorithm for incremental evaluation of logic programs. In: Etalle, S., Truszczyński, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 56–71. Springer, Heidelberg (2006)
Tamaki, H., Sato, T.: OLDT resolution with tabulation. In: Shapiro, E. (ed.) ICLP 1986. LNCS, vol. 225. Springer, Heidelberg (1986)
Vitek, J., Bokowski, B.: Confined types in java. Software Practice and Experience 31(6) (2001)
Vivien, F., Rinard, M.C.: Incrementalized pointer and escape analysis. In: Proceedings of PLDI. ACM, New York (2001)
Whaley, J., Lam, M.S.: Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In: Proceedings of PLDI. ACM, New York (2004)
Wuyts, R.: Declarative reasoning about the structure of object-oriented systems. In: Proceedings of TOOLS-USA. IEEE, Los Alamitos (1998)
Yur, J., Ryder, B.G., Landi, W., Stocks, P.: Incremental analysis of side effects for C software system. In: Proceedings of ICSE. ACM, New York (1997)
Yur, J., Ryder, B.G., Landi, W.A.: An incremental flow- and context-sensitive pointer aliasing analysis. In: Proceedings of ICSE. IEEE, Los Alamitos (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eichberg, M., Kahl, M., Saha, D., Mezini, M., Ostermann, K. (2006). Automatic Incrementalization of Prolog Based Static Analyses. In: Hanus, M. (eds) Practical Aspects of Declarative Languages. PADL 2007. Lecture Notes in Computer Science, vol 4354. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69611-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-69611-7_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69608-7
Online ISBN: 978-3-540-69611-7
eBook Packages: Computer ScienceComputer Science (R0)