Scaling up knowledge graph creation to large and heterogeneous data sources

RDF knowledge graphs (KG) are powerful data structures to represent factual statements created from heterogeneous data sources. KG creation is laborious and demands data management techniques to be executed efficiently. This paper tackles the problem of the automatic generation of KG creation processes declaratively specified; it proposes techniques for planning and transforming heterogeneous data into RDF triples following mapping assertions specified in the RDF Mapping Language (RML). Given a set of mapping assertions, the planner provides an optimized execution plan by partitioning and scheduling the execution of the assertions. First, the planner assesses an optimized number of partitions considering the number of data sources, type of mapping assertions, and the associations between different assertions. After providing a list of partitions and assertions that belong to each partition, the planner determines their execution order. A greedy algorithm is implemented to generate the partitions’ bushy tree execution plan. Bushy tree plans are translated into operating system commands that guide the execution of the partitions of the mapping assertions in the order indicated by the bushy tree. The proposed optimization approach is evaluated over state-of-the-art RML-compliant engines, and existing benchmarks of data sources and RML triples maps. Our experimental results suggest that the performance of the studied engines can be considerably improved, particularly in a complex setting with numerous triples maps and large data sources. As a result, engines that time out in complex cases are enabled to produce at least a portion of the KG applying the planner.     

Using static symbolic execution to detect buffer overflows

Buffer overrun remains one of the main sources of errors and vulnerabilities in the C/C++ source code. To detect such kind of defects, static analysis is widely used. In this paper, we propose a path-sensitive static analysis based on symbolic execution with state merging. For buffers with compile-time-known sizes, we present an interprocedural path- and context-sensitive overrun detection algorithm that finds program points satisfying a proposed error definition. The described approach was implemented in the Svace static analyzer without significant loss of performance. On Android 5.0.2, these detectors generated 351 warnings, 64% of which were true positives. In addition, we describe a prototype of an intraprocedural heap buffer overflow detector and present an example of a defect found by this detector.     

Dynamic and fast processing of queries on large-scale RDF data

As RDF data continue to gain popularity, we witness the fast growing trend of RDF datasets in both the number of RDF repositories and the size of RDF datasets. Many known RDF datasets contain billions of RDF triples (subject, predicate and object). One of the grant challenges for managing these huge RDF data is how to execute RDF queries efficiently. In this paper, we address the query processing problems against the billion triple challenges. We first identify some causes for the problems of existing query optimization schemes, such as large intermediate results, initial query cost estimation errors. Then, we present our block-oriented dynamic query plan generation approach powered with pipelining execution. Our approach consists of two phases. In the first phase, a near-optimal execution plan for queries is chosen by identifying the processing blocks of queries. We group the join patterns sharing a join variable into building blocks of the query plan since executing them first provides opportunities to reduce the size of intermediate results generated. In the second phase, we further optimize the initial pipelining for a given query plan. We employ optimization techniques, such as sideways information passing and semi-join, to further reduce the size of intermediate results, improve the query processing cost estimation and speed up the performance of query execution. Experimental results on several RDF datasets of over a billion triples demonstrate that our approach outperforms existing RDF query engines that rely on dynamic programming based static query processing strategies.     

一种基于程序功能标签切片的制导符号执行分析方法

提出了一种基于程序功能标签切片的制导符号执行分析方法OPT-SSE.该方法从程序功能文档提取功能标签,利用程序控制流分析,建立各功能标签和程序基本块的映射关系,并根据功能标签在程序执行中的顺序关系生成功能标签执行流.针对给定的代码目标点,提取与之相关的功能执行流切片,根据预定义好的功能标签流制导规则进行符号执行分析,在路径分析过程中,及时裁剪无关的功能分支路径以提升制导效率.通过对不同的功能标签流进行分离制导符号执行分析,可避免一直执行某复杂循环体的情形,从而提高对目标程序的整体分支覆盖率和指令覆盖率.实验结果表明,通过对binutils、gzip、coreutils等10个不同软件中的20个应用工具上的分析,OPT-SSE与KLEE提供的主流搜索策略相比,代码目标制导速度平均提升到4.238倍,代码目标制导成功率平均提升了31%,程序指令覆盖率平均提升了8.95%,程序分支覆盖率平均提升了8.28%.     

On the Turing Completeness of the Semantic Web

The evidenced fact that “Linking is as powerful as computing” in a dynamic web context has lead to evaluating Turing completeness for hypertext systems based on their linking model. The same evaluation can be applied to the Semantic Web domain too. RDF is the default data model of the Semantic Web links, so the evaluation comes back to whether or not RDF can support the required computational power at the linking level. RDF represents semantic relationships with explicitly naming the participating triples, however the enumeration is only one method amongst many for representing relations, and not always the most efficient or viable. In this paper we firstly consider that Turing completeness of binary-linked hypertext is realized if and only if the links are dynamic (functional). Ashman’s Binary Relation Model (BRM) showed that binary relations can most usefully be represented with Mili’s pE (predicate-expression) representation, and Moreau and Hall concluded that hypertext systems which use the pE representation as the basis for their linking (relation) activities are Turing-complete. Secondly we consider that RDF –as it is- is a static version of a general ternary relations model, called TRM. We then conclude that the current computing power of the Semantic Web depends on the dynamicity supported by its underlying TRM. The value of this is firstly that RDF’s triples can be considered within a framework and compared to alternatives, such as the TRM version of pE, designated pfE (predicate-function-expression). Secondly, that a system whose relations are represented with pfE is likewise going to be Turing-complete. Thus moving from RDF to a pfE representation of relations would give far greater power and flexibility within the Semantic Web applications.     

一种对语义网上本体进行检索和排序新方法

提出了一种对语义网上的本体进行检索和排序的新方法ARRO(an Approach for Retrieval and Ranking for the On-tology),其核心思想是通过对本体进行解析产生逻辑三元组.再在三元组的基础上进行逻辑推理,形成概念的逻辑视图,然后通过排序公式对相关本体进行检索和排序.这种通过逻辑视图和三元组对本体进行检索和排序的方法可以有效的进行逻辑推理,并提高检索效率,从而解决在传统的基于关键字的信息检索中只能从句法上对关键字进行分析,无法将推理和检索相互结合,互相促进的问题.本文对ARRO进行了测试,结果验证了其实用性和有效性.     

SharpChecker: Static analysis tool for C# programs

This paper considers various aspects of static analysis of C# programs in order to detect the maximum number of software bugs in an acceptable time. A complete cycle of software static analysis is described with the main focus being placed on the specifics of the C# language. Some methods are discussed that take into account popular features of C# at all levels of analysis: call graph and control flow graph construction, dataflow analysis, as well as context- and path-sensitive interprocedural analysis. A symbolic execution method is proposed, which is based on the works devoted to the Bounded Model Checking (BMC) and the Saturn Software Analysis Project. A memory model is described that enables an accurate intraprocedural analysis and allows one to create compact representations of error conditions associated with functions, which are essential for interprocedural analysis. A special attention is paid to the optimizations that occur during path-sensitive analysis of error conditions. The conditions need to be optimized in terms of size, because path-sensitive interprocedural analysis requires saving a large number of conditions for each analyzed function. The conditions are resolved using advanced SMT solvers (such as the Microsoft Z3 Prover). This paper also considers various approaches to modeling the behavior of library functions: based on a summary containing a set of properties required for analysis, or based on simplified implementations in C#. All the discussed solutions are implemented in the SharpChecker static analysis tool and are tested on a number of open-source projects from 1.5 thousand to 1.35 million lines of code.     

RDF数据分布式并行语义编码算法

现有的RDF数据分布式并行压缩编码算法均未考虑结合本体文件,导致编码后的RDF数据没有表示任何语义信息,不利于分布式查询或推理。针对这些问题,提出SCOM(Semantic Coding with Ontology on MapReduce)算法在分布式MapReduce下完成RDF数据的语义并行编码。该算法首先结合RDF数据本体,构建类关系和属性关系模型;在三元组项分类与过滤之后,对三元组项进行编码并生成字典表,最终完成RDF数据带有语义信息且具有规律性的编码。此外,SCOM算法能够很容易地将编码后的RDF数据文件恢复为原始文件。实验表明,SCOM算法能够高效地实现大规模数据的分布式并行编码。     

Information retrieval and knowledge discovery utilizing a biomedical patent semantic Web

Before undertaking new biomedical research, identifying concepts that have already been patented is essential. A traditional keyword-based search on patent databases may not be sufficient to retrieve all the relevant information, especially for the biomedical domain. This paper presents BioPatentMiner, a system that facilitates information retrieval and knowledge discovery from biomedical patents. The system first identifies biological terms and relations from the patents and then integrates the information from the patents with knowledge from biomedical ontologies to create a semantic Web. Besides keyword search and queries linking the properties specified by one or more RDF triples, the system can discover semantic associations between the Web resources. The system also determines the importance of the resources to rank the results of a search and prevent information overload while determining the semantic associations.     

Behavioral profiles—a way to model and validate program behavior

Software architecture contains, in addition to its structural part, interaction patterns that can be regarded as part of the architectural solution of the system. The interaction patterns define architecturally significant behavior of the software system. In this paper we propose a visual modeling language, behavioral profiles, for specifying architecturally significant behavioral rules for an application. The language is built on the Unified Modeling Language (UML), which is a visual language widely used in software development. We show how behavioral profiles can be used to support software designers in creating behavioral models that conform to some predefined rules and for ensuring that an application behaves correctly with respect to the rules given in the profiles. A tool called Bebop was built to support software engineers in behavioral profile‐based design and analysis of program behavior. To evaluate the approach and the tools in different application domains, they are utilized in three cases. The size of the applications used in the cases varies from small to quite large software systems, and from academic to industrial ones. The examples demonstrate how the approach presented can be used in practice for different steps in a software engineering process. The examples cover specializing an application framework and monitoring the program execution in run‐time. In addition, they show how behavioral profiles can be used to support guided program comprehension and to validate program execution by analyzing execution traces. Copyright © 2010 John Wiley & Sons, Ltd.     

基于抽象解释的代码迷惑有效性比较框架

代码迷惑是一种以增加理解难度为目的的程序变换技术,用来保护软件免遭逆向剖析.代码迷惑是否有效是代码迷惑研究中首要解决的问题.目前对有效性证明的研究大都是基于非语义的方式.文章将语义与有效性证明联系起来,建立了基于语义的代码迷惑有效性比较框架,该框架能够为迷惑算法在静态分析这样的限定环境下提供有效性证明,而且也能严格比较迷惑算法之间的有效性,最后使用实例描述比较框架如何应用到证明代码迷惑的有效性.     

利用海量知识库实现实体标注的一种方法

互联网上聚集了大量的文本、图像等非结构化信息,RDF作为W3C提出的互联网上的资源描述框架,非常适合于描述网络上的非结构化信息,因此形成了大量的RDF知识库,如Freebase、Yago、DBPedia等。RDF知识库中包含丰富的语义信息,可以对来自网页的名字实体进行标注,实现语义扩充。将网页上的名字实体映射到知识库中对应实体上称作实体标注。实体标注包括两个主要部分:实体间的映射和标注去歧义。利用海量RDF知识库的特性,提出了一种有效的实体标注方法。该方法采用简单的图加权及计算解决实体标注的去歧义问题。该方法已在云平台上实现,并通过实验验证了其准确度和可扩展性。     

SESLDS: An Extension Scheme for Linked Data Sources Based on Semantically Enhanced Annotation and Reasoning

In the era of Big Data, users prefer to get knowledge rather than pages from Web. Linked Data, a rather new form of knowledge representation and publishing described by RDF, can provide a more precise and comprehensible semantic structure to satisfy the aforementioned requirement. Besides, as the standard query language for RDF data, SPARQL has become the foundation protocol of Linked Data querying. The core idea of RDF Schema (RDFS) is to extend upon RDF vocabulary and allow attachment of semantics to user defined classes and properties. However, RDFS cannot fully utilize the potential of RDF since it cannot express the implicit semantics between linked entities in Linked Data sources. To fill this gap, in this paper, we design a new semantic annotating and reasoning approach that can extend more implicit semantics from different properties. We firstly establish a well‐defined semantically enhanced annotation strategy for Linked Data sources. In particular, we present some new semantic properties for predicates in RDF triples and design a Semantic Matrix for Predicates (SM_P). We then propose a novel general Semantically Extended Scheme for Linked Data Sources (SES_LDS) to realize the semantic extension over the target Linked Data source through semantically enhanced reasoning. Lastly, based on the experimental analyses, we verify that our proposal has advantages over the initial Linked Data source and can return more valid results.     

An approach to genuine dynamic linking

This paper describes a new approach to dynamic link/unlink editing. The basis of this approach is a library of link editing functions that can add compiled object code to or remove such code from a process any time during its execution. Loading modules, searching libraries, resolving external references, and allocating storage for global and static data structures are all performed at run time. This approach provides the efficiency of native machine code execution along with the flexibility to modify a program during its execution, thereby making many new applications possible. This paper also describes three sample applications of these dynamic link editing functions: program customization, incremental program development, and support for debugging and testing. A prototype of this approach is implemented under UNIX as a library package called dld for the C programming language and is available for VAX, Sun 3 and SPARCstation machines.     

基于插桩和布尔逻辑的运行时程序验证框架

针对软件测试和静态程序验证中存在的连续性程序执行验证和推理问题,提出一个基于程序插桩和布尔逻辑的运行时程序验证框架——RPA。定义一种用于描述运行时程序性质和规范的动态逻辑语言RPAL,实现自动化插桩以收集运行时程序状态信息,设计一个支持高效验证的句子调度算法。实验结果表明,结合合适的谓词扩展,RPA可以有效地验证和分析软件逻辑,发现潜在的软件错误。