OPAL: An extensible framework for ontology-based program analysis

摘要

The syntactic information of a program can be represented as resource description framework (RDF) triples calledprogram triples. We propose an extensible static analysis framework, called OPAL-Ontology-based Program AnaLysis. The framework enables formal representation of external knowledge, such as usage knowledge of libraries and domain knowledge. Utilizing this knowledge and the program triples, we compute the semantic information, calledstatic traceof the program. It is generated through path-sensitive intraprocedural traversal of the program. We approximate information in case of loops by unrolling them a fixed number of times. The main contribution of the framework is to store the static trace as RDF triples calledsemantic triples. They are described using the Program Analysis ontology proposed in this article. The program triples and the semantic triples are together calledconsolidated program triples. These triples are stored and used to accelerate the execution of client-analyses specified by the end user. In the framework, a client-analysis is specified by a set of conjunctive expressions that use SPARQL (W3C RDF query language) queries. The framework is effective for the client-analyses that warrant sound and approximate information. The effectiveness is assessed first, using two source-code-analyses that require only the program triples, and then 10 intraprocedural path-sensitive analyses that require the consolidated program triples. Using NPB and SPEC 2006 benchmarks, we achieve an improvement in the conciseness of analysis specifications. Also, the execution time using OPAL is competitive to LLVM'sclangfor individual analysis and outperformsclangover a series of analyses because of the reuse of consolidated program triples.