Automated workarounds from Java program specifications based on SAT solving

The failures that bugs in software lead to can sometimes be bypassed by the so-called workarounds: when a (faulty) routine fails, alternative routines that the system offers can be used in place of the failing one, to circumvent the failure. Existing approaches to workaround-based system recovery consider workarounds that are produced from equivalent method sequences, automatically computed from user-provided abstract models, or directly produced from user-provided equivalent sequences of operations. In this paper, we present two techniques for computing workarounds from Java code equipped with formal specifications, that improve previous approaches in two respects. First, the particular state where the failure originated is actively involved in computing workarounds, thus leading to repairs that are more state specific. Second, our techniques automatically compute workarounds on concrete program state characterizations, avoiding abstract software models and user-provided equivalences. The first technique uses SAT solving to compute a sequence of methods that is equivalent to a failing method on a specific failing state, but which can also be generalized to schemas for workaround reuse. The second technique directly exploits SAT to circumvent a failing method, building a state that mimics the (correct) behaviour of a failing routine, from a specific program state too. We perform an experimental evaluation based on case studies involving implementations of collections and a library for date arithmetic, showing that the techniques can effectively compute workarounds from complex contracts in an important number of cases, in time that makes them feasible to be used for run-time repairs. Our results also show that our state-specific workarounds enable us to produce repairs in many cases where previous workaround-based approaches are inapplicable.     

Automatically maintaining navigation sequences for querying semi-structured web sources

A substantial subset of Web data has an underlying structure. For instance, the pages obtained in response to a query executed through a Web search form are usually generated by a program that accesses structured data in a local database, and embeds them into an HTML template. For software programs to gain full benefit from these “semi-structured” Web sources, wrapper programs must be built to provide a “machine-readable” view over them. Since Web sources are autonomous, they may experience changes that invalidate the current wrapper, thus automatic maintenance is an important issue. Wrappers must perform two tasks: navigating through Web sites and extracting structured data from HTML pages. While several works have addressed the automatic maintenance of data extraction tasks, the problem of maintaining the navigation sequences remains unaddressed to the best of our knowledge. In this paper, we propose a set of novel techniques to fill this gap.     

Automatically maintaining navigation sequences for querying semi-structured web sources

A substantial subset of Web data has an underlying structure. For instance, the pages obtained in response to a query executed through a Web search form are usually generated by a program that accesses structured data in a local database, and embeds them into an HTML template. For software programs to gain full benefit from these “semi-structured” Web sources, wrapper programs must be built to provide a “machine-readable” view over them. Since Web sources are autonomous, they may experience changes that invalidate the current wrapper, thus automatic maintenance is an important issue. Wrappers must perform two tasks: navigating through Web sites and extracting structured data from HTML pages. While several works have addressed the automatic maintenance of data extraction tasks, the problem of maintaining the navigation sequences remains unaddressed to the best of our knowledge. In this paper, we propose a set of novel techniques to fill this gap.     

基于主体的语义Web服务自动组合研究

语义Web服务要解决的一个主要问题就是如何实现服务组合自动化.主体技术因其智能性、自主性等特点在解决语义Web服务组合问题中具有较大优势.通过分析语义Web服务组合研究现状,分析主体、语义Web与Web服务的紧密关系,论证了基于主体的语义Web服务的可行性并描述了基于多主体的Web服务组合平台架构.介绍了基于主体技术的语义Web服务组合技术,将服务组合看成是一个多主体环境下的规划问题,给出语义Web服务作为主体动作子类的形式化定义,并针对服务组合问题增加限定条件,定义服务之间的5种关系,试图从逻辑角度,以描述逻辑为基本工具,突出服务的动态性与交互性.最后利用主体的目标规划以及基于描述逻辑的有效推理,给出了服务的自动组合算法.     

面向Web服务测试的单线执行序列生成方法

测试用例自动生成是实现Web服务自动化测试的关键,基于代数规约的传统测试技术均依赖于创建、初始化和复制被测对象等操作来验证测试结果的正确性,但第三方Web服务并不支持这些操作,无法将测试用例转换成可执行操作序列。一种可行的解决方案是将测试用例转换成只包含一个被测服务实例、不包括实例初始化、只对实例进行状态修改和检查的线性执行序列。改进已有工作,提出包含逆项的测试执行图TEG-I来描述测试用例执行过程中的状态变化,设计TEG-I构造算法和单线执行序列生成算法并实现相应原型工具。实验结果表明,提出的方法能够有效地自动完成测试用例生成,提高Web服务的可测试性。     

Meme Media for Clipping and Combining Web Resources

The publication and reuse of intellectual resources using the Web technologies provide no support for us to clip out any portion of Web pages, to combine them together for their local reuse, nor to publish the newly composed object as a new Web page for its reuse by other people. This paper shows how the meme-media architecture is applied to the Web to provide such support for us. This makes the Web work as a shared repository not only for publishing intellectual resources, but also for their collaborative reediting. We will propose a general framework for clipping arbitrary Web contents as live objects, for defining IO ports on such a clip, and for the recombination and linkage of such clips based on both the original and some user-defined relationships among them. In our previous works, we proposed two separate frameworks for these three purposes; one works for the first two, and the other for the last. Here we will propose a unified framework for these three purposes, as well as its detailed internal mechanisms. Then we show how it can be easily applied to various legacy Web applications to develop innovative services.     

A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes

In this paper, we propose a new algorithm for the alignment of nested arc-annotated sequences, having applications in the comparison of RNA secondary structures without pseudo-knots. We use a general edit distance model between arc-annotated sequences, that considers classical sequences of edit operations and structural edit operations on arcs. In this model, the general edit distance problem under a non-constrained weight scheme, is NP-hard. Recently, a hierarchy of arc-annotated sequence alignment problems that highlights less general, but tractable, problems was introduced. We refine this hierarchy of alignment problems and extend the class of tractable alignment problems. Up to date, the alignment problem we solve is the most general one that is known to be tractable in the considered edit distance model and under arbitrary weight schemes. This algorithm is efficient, as its asymptotic time and space complexities are the same as the complexities of the best previously published algorithm.     

Qualitative and quantitative temporal constraints and relationaldatabases: theory, architecture, and applications

Many different applications in different areas need to deal with both: databases, in order to take into account large amounts of structured data; and quantitative and qualitative temporal constraints about such data. We propose an approach that extends: temporal databases and artificial intelligence temporal reasoning techniques and integrate them in order to face such a need. Regarding temporal reasoning, we consider some results that we proved recently about efficient query answering in the Simple Temporal Problem framework and we extend them in order to deal with partitioned sets of constraints and to support relational database operations. Regarding databases, we extend the relational model in order to consider also qualitative and quantitative temporal constraints both in the data (data expressiveness) and in the queries (query expressiveness). We then propose a modular architecture integrating a relational database with a temporal reasoner. We also consider classes of applications that fit into our approach and consider patient management in a hospital as an example     

Toward an OSGi-based infrastructure for context-aware applications

Applications and services must adapt to changing contexts in dynamic environments. However, building context-aware applications is still complex and time-consuming due to inadequate infrastructure support. We propose a context-aware infrastructure for building and rapidly prototyping such applications in a smart-home environment. This OSGi-based infrastructure manages context-aware services reliably and securely and efficiently supports context acquisition, discovery, and reasoning. A formal, ontology-based context model enables semantic context representation, reasoning, and knowledge sharing. We propose an ontology-based context model that leverages Semantic Web technology and OWL (Web Ontology Language). OWL is an ontology markup language that enables context sharing and context reasoning. Based on our context model, we also propose a service-oriented context-aware middleware (SOCAM) architecture, including a set of independent services that perform context discovery, acquisition, and interpretation.     

Markov constraints: steerable generation of Markov sequences

Markov chains are a well known tool to model temporal properties of many phenomena, from text structure to fluctuations in economics. Because they are easy to generate, Markovian sequences, i.e. temporal sequences having the Markov property, are also used for content generation applications such as text or music generation that imitate a given style. However, Markov sequences are traditionally generated using greedy, left-to-right algorithms. While this approach is computationally cheap, it is fundamentally unsuited for interactive control. This paper addresses the issue of generating steerable Markovian sequences. We target interactive applications such as games, in which users want to control, through simple input devices, the way the system generates a Markovian sequence, such as a text, a musical sequence or a drawing. To this aim, we propose to revisit Markov sequence generation as a branch and bound constraint satisfaction problem (CSP). We propose a CSP formulation of the basic Markovian hypothesis as elementary Markov Constraints (EMC). We propose algorithms that achieve domain-consistency for the propagators of EMCs, in an event-based implementation of CSP. We show how EMCs can be combined to estimate the global Markovian probability of a whole sequence, and accommodate for different species of Markov generation such as fixed order, variable-order, or smoothing. Such a formulation, although more costly than traditional greedy generation algorithms, yields the immense advantage of being naturally steerable, since control specifications can be represented by arbitrary additional constraints, without any modification of the generation algorithm. We illustrate our approach on simple yet combinatorial chord sequence and melody generation problems and give some performance results.     

Crawlability metrics for automated web testing

Web applications are exposed to frequent changes both in requirements and involved technologies. At the same time, there is a continuously growing demand for quality and trust and such a fast evolution and quality constraints claim for mechanisms and techniques for automated testing. Web application automated testing often involves random crawlers to navigate the application under test and automatically explore its structure. However, owing to the specific challenges of the modern Web systems, automatic crawlers may leave large portions of the application unexplored. In this paper, we propose the use of structural metrics to predict whether an automatic crawler with given crawling capabilities will be sufficient or not to achieve high coverage of the application under test. In this work, we define a taxonomy of such capabilities and we determine which combination of them is expected to give the highest reward in terms of coverage increase. Our proposal is supported by an experiment in which 19 web applications have been analyzed.     

Composition of Semantic Web services using Linear Logic theorem proving

This paper introduces a method for automatic composition of Semantic Web services using Linear Logic (LL) theorem proving. The method uses a Semantic Web service language (DAML-S) for external presentation of Web services, while, internally, the services are presented by extralogical axioms and proofs in LL. LL, as a resource conscious logic, enables us to capture the concurrent features of Web services formally (including parameters, states and non-functional attributes). We use a process calculus to present the process model of the composite service. The process calculus is attached to the LL inference rules in the style of type theory. Thus, the process model for a composite service can be generated directly from the complete proof. We introduce a set of subtyping rules that defines a valid dataflow for composite services. The subtyping rules that are used for semantic reasoning are presented with LL inference figures. We propose a system architecture where the DAML-S Translator, LL Theorem Prover and Semantic Reasoner can operate together. This architecture has been implemented in Java.     

Towards a data‐driven IoT software architecture for smart city utilities

The Internet of things (IoT) is emerging as the next big wave of digital presence for billions of devices on the Internet. Smart cities are a practical manifestation of IoT, with the goal of efficient, reliable, and safe delivery of city utilities like water, power, and transport to residents, through their intelligent management. A data‐driven IoT software platform is essential for realizing manageable and sustainable smart utilities and for novel applications to be developed upon them. Here, we propose such service‐oriented software architecture to address 2 key operational activities in a smart utility: the IoT fabric for resource management and the data and application platform for decision‐making. Our design uses Open Web standards and evolving network protocols, cloud and edge resources, and streaming big data platforms. We motivate our design requirements using the smart water management domain; some of these requirements are unique to developing nations. We also validate the architecture within a campus‐scale IoT testbed at the Indian Institute of Science, Bangalore and present our experiences. Our architecture is scalable to a township or city while also generalizable to other smart utility domains. Our experiences serve as a template for other similar efforts, particularly in emerging markets and highlight the gaps and opportunities for a data‐driven IoT software architecture for smart cities.     

InCloud: a cloud-based middleware for vehicular infotainment systems

Smart vehicles form pervasive environment to enhance user experience through multimedia enabled infotainment systems. In order to realize effective infotainment system for vehicles, we need to have context-aware applications that use latest (live) information for enhanced user experience. Such latest information is abundantly available on the Internet due to explosive growth of Web 3.0, which can be accessed through wireless communication infrastructures such as VANETs and LTE. In this paper we propose a cloud-based middleware framework, InCloud, for vehicular infotainment application development. The proposed framework follows service oriented architecture in which data filtering and fusion functionalities are delegated to the cloud. Data filtering and fusion reduce the data flow over wireless link. Furthermore, because most of the processing is done on the cloud, the client becomes lightweight and loosely coupled with Internet resources and underlying platforms in vehicles. We also propose a class-based fusion method for combining information from multiple resources on the Internet. The efficacy of the proposed framework is validated by developing three infotainment applications for vehicles: context-aware music, news, and an enhanced Direction (eDirection) application.

     

Ws-AC: A Fine Grained Access Control System for Web Services

The emerging Web service technology has enabled the development of Internet-based applications that integrate distributed and heterogeneous systems and processes which are owned by different organizations. However, while Web services are rapidly becoming a fundamental paradigm for the development of complex Web applications, several security issues still need to be addressed. Among the various open issues concerning security, an important issue is represented by the development of suitable access control models, able to restrict access to Web services to authorized users. In this paper we present an innovative access control model for Web services. The model is characterized by a number of key features, including identity attributes and service negotiation capabilities. We formally define the protocol for carrying on negotiations, by specifying the types of message to be exchanged and their contents, based on which requestor and provider can reach an agreement about security requirements and services. We also discuss the architecture of the prototype we are currently implementing. As part of the architecture we propose a mechanism for mapping our policies onto the WS-Policy standard which provides a standardized grammar for expressing Web services policies.     

Two-dimensional indexing to provide one-integrated-memory view of distributed memory for a massively-parallel search engine

We propose two-dimensional indexing—a novel in-memory indexing architecture that operates over distributed memory of a massively-parallel search engine. The goal of two-dimensional indexing is to provide a one-integrated-memory view as in a single node system using one large integrated memory. In two-dimensional indexing, we partition the entire index into n× m fragments and distribute them over the memories of multiple nodes in such a way that each fragment is entirely stored in main memory of one node. The proposed architecture is not only scalable as it uses a scaled-out shared-nothing architecture but also is capable of achieving low query response time as it processes queries in main memory. We also propose the concept of the one-memory point, which is the amount of the memory space required to completely store the entire index in main memory providing a one-integrated-memory view. We first prove the effectiveness of two-dimensional indexing with single-keyword queries, and then, extend the notion so as to be able to handle multiple-keyword queries. To handle multiple-keyword queries, we adopt pre-join that materializes a multiple-keyword query a priori as well as a new notion of semi-memory join that obviates extensive communication overhead to perform join across multiple nodes. In experiments using the real-life search query set over a database consisting of 100 million Web documents crawled, we show that two-dimensional indexing can effectively provide a one-integrated-memory view without too much of additional memory compared with the single node system using one large integrated memory. We also show that, with a six-node prototype, in an ideal case, it significantly improves the query processing performance over a disk-based search engine with an equivalent amount of in-memory buffer but without two-dimensional indexing — by up to 535.54 times. This improvement is expected to get larger as the system is scaled-out with a larger number of machines.

     

Web应用漏洞报告理解及漏洞复现

随着Web应用的功能日趋复杂,其安全问题不容乐观, Web应用安全性测试成为软件测试领域的研究重点之一.漏洞报告旨在记录Web应用安全问题,辅助Web应用测试,提升其安全性与质量.然而,如何自动识别漏洞报告中的关键信息,复现漏洞,仍是当前的研究难点.为此,本文提出一种自动化的漏洞报告理解和漏洞复现方法,首先,依据漏洞报告的特点,归纳其语法依存模式,并结合依存句法分析技术,解析漏洞描述,提取漏洞触发的关键信息.其次,不同于常规自然语言描述, Web漏洞的攻击负载通常是非法字符串,大多以代码片段的形式存在,为此,本文针对攻击负载,设计提取规则,完善漏洞报告中攻击负载的提取.在此基础上,考虑漏洞报告与Web应用文本描述不同但语义相近,提出基于语义相似度的漏洞复现脚本自动生成方法,实现Web应用漏洞的自动复现.为验证本文方法的有效性,从漏洞收集平台Exploit-db的300余个Web应用项目中收集了400份漏洞报告,归纳出其语法依存模式;并针对23个开源Web应用涉及的26份真实漏洞报告进行漏洞复现实验,结果表明本文方法可有效提取漏洞报告的关键信息,并据此生成可行测试脚本,复现漏洞,有效减少...