Document Open Access Logo

Towards Ontology-Based Program Analysis

Authors Yue Zhao, Guoyang Chen, Chunhua Liao, Xipeng Shen

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2016.26.pdf
  • Filesize: 1.96 MB
  • 25 pages

Document Identifiers

Author Details

Yue Zhao
Guoyang Chen
Chunhua Liao
Xipeng Shen

Cite As Get BibTex

Yue Zhao, Guoyang Chen, Chunhua Liao, and Xipeng Shen. Towards Ontology-Based Program Analysis. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 26:1-26:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ECOOP.2016.26

Abstract

Program analysis is fundamental for program optimizations, debugging,
and many other tasks. But developing program analyses has been a
challenging and error-prone process for general users. Declarative
program analysis has shown the promise to dramatically improve the
productivity in the development of program analyses. Current
declarative program analysis is however subject to some major
limitations in supporting cooperations among analysis tools, guiding
program optimizations, and often requires much effort for repeated
program preprocessing.

In this work, we advocate the integration of ontology into declarative
program analysis. As a way to standardize the definitions of concepts
in a domain and the representation of the knowledge in the domain,
ontology offers a promising way to address the limitations of current
declarative program analysis. We develop a prototype framework named
PATO for conducting program analysis upon ontology-based program
representation. Experiments on six program analyses confirm the
potential of ontology for complementing existing declarative program
analysis. It supports multiple analyses without separate program
preprocessing, promotes cooperative Liveness analysis between two
compilers, and effectively guides a data placement optimization for
Graphic Processing Units (GPU).

Subject Classification

Keywords
  • ontology
  • compiler
  • program analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. The JTransformer project. URL: http://sewiki.iai.uni-bonn.de/research/jtransformer/.
  2. Large single compilation-unit C programs. URL: http://people.csail.mit.edu/smcc/projects/single-file-programs/.
  3. OpenAnalysis at Rice University. URL: http://www.hipersoft.rice.edu/openanalysis/.
  4. ROSE compiler infrastructure. URL: http://www.rosecompiler.org/.
  5. Lars Ole Andersen. Program analysis and specialization for the C programming language. PhD thesis, University of Cophenhagen, 1994. Google Scholar
  6. Michael Ashburner, Catherine A Ball, Judith A Blake, David Botstein, Heather Butler, J Michael Cherry, Allan P Davis, Kara Dolinski, Selina S Dwight, Janan T Eppig, et al. Gene Ontology: Tool for the unification of biology. Nature genetics, 25(1):25-29, 2000. Google Scholar
  7. Roberto Bagnara and Manuel Carro. Foreign language interfaces for Prolog: A terse survey. ALP newsletter, 15, 2002. Google Scholar
  8. D. H. Bailey, E. Barszcz, J. T. Barton, D. S. Browning, R. L. Carter, R. A. Fatoohi, P. O. Frederickson, T. A. Lasinski, H. D. Simon, V. Venkatakrishnan, and S. K. Weeratunga. The NAS parallel benchmarks. Technical report, The International Journal of Supercomputer Applications, 1991. Google Scholar
  9. Nick Bassiliades, Grigoris Antoniou, and Ioannis Vlahavas. A defeasible logic reasoner for the semantic web. International Journal on Semantic Web and Information Systems (IJSWIS), 2(1):1-41, 2006. Google Scholar
  10. William C Benton and Charles N Fischer. Interactive, scalable, declarative program analysis: from prototype to implementation. In Proceedings of the 9th ACM SIGPLAN international conference on Principles and practice of declarative programming, pages 13-24. ACM, 2007. Google Scholar
  11. Grady Booch, James Rumbaugh, and Ivar Jacobson. Unified Modeling Language User Guide, The (2nd Edition) Addison-Wesley Object Technology Series. Addison-Wesley Professional, 2005. Google Scholar
  12. Ivan Bratko. Prolog (3rd Ed.): Programming for Artificial Intelligence. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2001. Google Scholar
  13. Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '09, pages 243-262, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1640089.1640108.
  14. Guoyang Chen, Bo Wu, Dong Li, and Xipeng Shen. PORPLE: An extensible optimizer for portable data placement on GPU. In Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-47, pages 88-100, Washington, DC, USA, 2014. IEEE Computer Society. URL: http://dx.doi.org/10.1109/MICRO.2014.20.
  15. Michael Compton, Payam Barnaghi, Luis Bermudez, Raúl García-Castro, Oscar Corcho, Simon Cox, John Graybeal, Manfred Hauswirth, Cory Henson, Arthur Herzog, Vincent Huang, Krzysztof Janowicz, W. David Kelsey, Danh Le Phuoc, Laurent Lefort, Myriam Leggieri, Holger Neuhaus, Andriy Nikolov, Kevin Page, Alexandre Passant, Amit Sheth, and Kerry Taylor. The SSN ontology of the W3C semantic sensor network incubator group. Web Semantics: Science, Services and Agents on the World Wide Web, 17:25-32, 2012. URL: http://www.w3.org/2005/Incubator/ssn/ssnx/ssn, URL: http://dx.doi.org/10.1016/j.websem.2012.05.003.
  16. Leonardo Luiz Padovani Da Mata, Fernando Magno QuintãO Pereira, and Renato Ferreira. Automatic parallelization of canonical loops. Sci. Comput. Program., 78(8):1193-1206, August 2013. URL: http://dx.doi.org/10.1016/j.scico.2012.09.006.
  17. Steven Dawson, C. R. Ramakrishnan, and David S. Warren. Practical program analysis using general purpose logic programming systems—a case study. SIGPLAN Not., 31(5):117-126, May 1996. URL: http://dx.doi.org/10.1145/249069.231399.
  18. Premkumar T Devanbu. GENOA: A customizable language-and front-end independent code analyzer. In Proceedings of the 14th international conference on Software engineering, pages 307-317. ACM, 1992. Google Scholar
  19. Ken Ducatel, Marc Bogdanowicz, Fabiana Scapolo, Jos Leijten, and Jean-Claude Burgelman. Scenarios for ambient intelligence in 2010. Office for official publications of the European Communities, 2001. Google Scholar
  20. Jürgen Ebert, Volker Riediger, and Andreas Winter. Graph technology in reverse engineering-the TGraph approach. In Proc. 10th Workshop Software Reengineering. GI Lecture Notes in Informatics. Citeseer, 2008. Google Scholar
  21. Amnon H Eden and Raymond Turner. Problems in the ontology of computer programs. Applied Ontology, 2(1):13-36, 2007. Google Scholar
  22. Rudolf Ferenc, Árpd Beszédes, Mikko Tarkiainen, and Tibor Gyimóthy. Columbus-reverse engineering tool and schema for C++. In Software Maintenance, 2002. Proceedings. International Conference on, pages 172-181. IEEE, 2002. Google Scholar
  23. Charles N. Fischer, Ronald K. Cytron, and Richard J. LeBlanc. Crafting A Compiler. Addison-Wesley Publishing Company, USA, 1st edition, 2009. Google Scholar
  24. Gopinath Ganapathi, Ravi Lourdusamy, and Veeraraghavan Rajaram. Towards ontology development for teaching programming language. In World Congress on Engineering, 2011. Google Scholar
  25. John H Gennari, Mark A Musen, Ray W Fergerson, William E Grosso, Monica Crubézy, Henrik Eriksson, Natalya F Noy, and Samson W Tu. The evolution of protégé: an environment for knowledge-based systems development. International Journal of Human-computer studies, 58(1):89-123, 2003. Google Scholar
  26. Elnar Hajiyev, Mathieu Verbaere, and Oege De Moor. Codequest: Scalable source code queries with datalog. In ECOOP 2006-Object-Oriented Programming, pages 2-27. Springer, 2006. Google Scholar
  27. Nevin Heintze and Olivier Tardieu. Ultra-fast aliasing analysis using CLA. In Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation - PLDI '01, pages 254-263, New York, New York, USA, 2001. ACM Press. URL: http://dx.doi.org/10.1145/378795.378855.
  28. Pascal Hitzler, Markus Krötzsch, Bijan Parsia, Peter F Patel-Schneider, and Sebastian Rudolph. OWL 2 web ontology language primer. W3C recommendation, 27(1):123, 2009. Google Scholar
  29. Richard C Holt. An introduction to TA: The tuple-attribute language. University of Toronto, Toronto, Draft Mar, 24, 1997. Google Scholar
  30. Richard C Holt, Andreas Winter, and Andy Schürr. GXL: toward a standard exchange format. In Reverse Engineering, 2000. Proceedings. Seventh Working Conference on, pages 162-171. IEEE, 2000. Google Scholar
  31. Matthew Horridge and Sean Bechhofer. The OWL API: A Java API for OWL ontologies. Semantic Web, 2(1):11-21, 2011. Google Scholar
  32. Susan Horwitz, Thomas Reps, and Mooly Sagiv. Demand interprocedural dataflow analysis. SIGSOFT Softw. Eng. Notes, 20(4):104-115, October 1995. URL: http://dx.doi.org/10.1145/222132.222146.
  33. Mark James and David Atkinson. STAR* TOOL- an environment and language for expert system implementation. Jet Propulsion Laboratory Report NTR C, 17536, 1988. Google Scholar
  34. Byunghyun Jang, Dana Schaa, Perhaad Mistry, and David Kaeli. Exploiting memory access patterns to improve memory performance in data-parallel architectures. IEEE Trans. Parallel Distrib. Syst., 22(1):105-118, January 2011. URL: http://dx.doi.org/10.1109/TPDS.2010.107.
  35. Mahmut Kandemir, J Ramanujam, and Alok Choudhary. Improving cache locality by a combination of loop and data transformations. Computers, IEEE Transactions on, 48(2):159-167, 1999. Google Scholar
  36. Markus Krötzsch, Frantisek Simancik, and Ian Horrocks. A description logic primer. arXiv preprint arXiv:1201.4089, 2012. Google Scholar
  37. Pascal Lando, Anne Lapujade, Gilles Kassel, and Frédéric Fürst. Towards a general ontology of computer programs. In ICSOFT (PL/DPS/KE/MUSE), pages 163-170, 2007. Google Scholar
  38. Chris Lattner. LLVM and Clang: Next generation compiler technology. In The BSD Conference, pages 1-2, 2008. Google Scholar
  39. Chris Lattner and Vikram Adve. LLVM: A compilation framework for lifelong program analysis &transformation. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-directed and Runtime Optimization, CGO '04, pages 75-, Washington, DC, USA, 2004. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=977395.977673.
  40. Timothy C Lethbridge, Sander Tichelaar, and Erhard Plödereder. The dagstuhl middle metamodel: A schema for reverse engineering. Electronic Notes in Theoretical Computer Science, 94:7-18, 2004. Google Scholar
  41. Chunhua Liao, DanielJ. Quinlan, JeremiahJ. Willcock, and Thomas Panas. Semantic-aware automatic parallelization of modern applications using high-level abstractions. International Journal of Parallel Programming, 38(5-6):361-378, 2010. URL: http://dx.doi.org/10.1007/s10766-010-0139-0.
  42. James Malone, Andy Brown, Allyson L Lister, Jon Ison, Duncan Hull, Helen Parkinson, and Robert Stevens. The software ontology (SWO): A resource for reproducibility in biomedical data analysis, curation and digital preservation. Journal of Biomedical Semantics, 5(1):25, 2014. Google Scholar
  43. Cynthia Matuszek, John Cabral, Michael J Witbrock, and John DeOliveira. An introduction to the syntax and content of Cyc. In AAAI Spring Symposium: Formalizing and Compiling Background Knowledge and Its Applications to Knowledge Representation and Question Answering, pages 44-49. Citeseer, 2006. Google Scholar
  44. Deborah L McGuinness and Frank Van Harmelen. OWL web ontology language overview. W3C recommendation, 10(10):2004, 2004. Google Scholar
  45. Flemming Nielson, Hanne R Nielson, and Chris Hankin. Principles of program analysis. Springer, 2004. Google Scholar
  46. Ian Niles and Adam Pease. Towards a standard upper ontology. In Proceedings of the international conference on Formal Ontology in Information Systems-Volume 2001, pages 2-9. ACM, 2001. Google Scholar
  47. Natalya F Noy and Deborah L McGuinness. Ontology development 101: A guide to creating your first ontology, 2001. Google Scholar
  48. OpenMP Architecture Review Board. OpenMP application program interface version 4.0, July 2013. URL: http://www.openmp.org/mp-documents/spec30.pdf.
  49. Adam Pease, Ian Niles, and John Li. The suggested upper merged ontology: A large ontology for the semantic web and its applications. In Working notes of the AAAI-2002 workshop on ontologies and the semantic web, volume 28, 2002. Google Scholar
  50. Davy Preuveneers, Jan Van den Bergh, Dennis Wagelaar, Andy Georges, Peter Rigole, Tim Clerckx, Yolande Berbers, Karin Coninx, Viviane Jonckers, and Koen De Bosschere. Towards an extensible context ontology for ambient intelligence. In Ambient intelligence, pages 148-159. Springer, 2004. Google Scholar
  51. Natalia Díaz Rodríguez, Manuel P Cuéllar, Johan Lilius, and Miguel Delgado Calvo-Flores. A survey on ontologies for human behavior recognition. ACM Computing Surveys (CSUR), 46(4):43, 2014. Google Scholar
  52. Sergey Sosnovsky and Tatiana Gavrilova. Development of educational ontology for C-programming. 2006. Google Scholar
  53. Steffen Staab and Rudi Studer. Handbook on ontologies. Springer Science &Business Media, 2013. Google Scholar
  54. Moritz Tenorth and Michael Beetz. KnowRob - knowledge processing for autonomous personal robots. In Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, pages 4261-4266. IEEE, 2009. Google Scholar
  55. Dmitry Tsarkov and Ian Horrocks. FaCT++ description logic reasoner: system description. In Automated reasoning, pages 292-297. Springer, 2006. Google Scholar
  56. Jeffrey D. Ullman. Principles of Database and Knowledge-base Systems, Vol. I. Computer Science Press, Inc., New York, NY, USA, 1988. Google Scholar
  57. Mathieu Verbaere, Ran Ettinger, and Oege de Moor. JunGL: A scripting language for refactoring. In Proceedings of the 28th international conference on Software engineering, pages 172-181. ACM, 2006. Google Scholar
  58. Mathieu Verbaere, Elnar Hajiyev, and Oege De Moor. Improve software quality with SemmleCode: an Eclipse plugin for semantic code search. In Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companion, pages 880-881. ACM, 2007. Google Scholar
  59. John Whaley, Dzintars Avots, Michael Carbin, and Monica S. Lam. Using datalog with binary decision diagrams for program analysis. In Proceedings of the Third Asian Conference on Programming Languages and Systems, APLAS'05, pages 97-118, Berlin, Heidelberg, 2005. Springer-Verlag. URL: http://dx.doi.org/10.1007/11575467_8.
  60. John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI '04, pages 131-144, New York, NY, USA, 2004. ACM. URL: http://dx.doi.org/10.1145/996841.996859.
  61. Jan Wielemaker. SWI-Prolog Semantic Web Library 3.0. URL: http://www.swi-prolog.org/pldoc/package/semweb.html.
  62. Jan Wielemaker, Tom Schrijvers, Markus Triska, and Torbjörn Lager. SWI-Prolog. Theory and Practice of Logic Programming, 12(1-2):67-96, 2012. Google Scholar
  63. Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. Finding and understanding bugs in C compilers. In ACM SIGPLAN Notices, volume 46, pages 283-294. ACM, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact