Checking consistency of qualitative preferences in CP-theory is PSPACE-complete in general. Building on Wilson’s seminal work on Complete Search (cs) tree based sufficient conditions for preferences, we characterize the necessary and sufficient conditions for the existence of a cs-tree, yielding the weakest sufficient condition for cs-tree–based consistency, and demonstrate that testing consistency under this condition is coNP-complete. Additionally, we present a polynomial-time computable upper approximation of the dominance relation for cs-tree–consistent CP-theory preferences, and prove that it subsumes all previously proposed approximations. Finally, we introduce set-labeled cs-trees, a generalization of cs-trees, which characterizes necessary and sufficient conditions for consistency checking in CP-theory preferences.

We investigate the problem of checking the consistency of qualitative preferences expressed in CP-theory. This problem is PSPACE-Complete even when the preferences are locally consistent or the preference variables have binary domain. We present a new sufficient condition for consistency of preferences and show that the condition can be checked in polynomial time in settings of practical relevance (locally consistent or binary domain preference variables). We further show how the resulting sufficient condition can be used to efficiently identify a subset of outcomes that are non-dominated with respect to a set of qualitative preferences.

Submodular optimization has become increasingly prominent in machine learning, and fairness has drawn much attention. In this paper, we propose to study the fair k-submodular maximization problem and develop a 1/3-approximation greedy algorithm with a running time of O(knB). Our theoretical guarantee matches the best-known k-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a (1/3 ϵ) approximation with ${\mathcal{O}}\left({\frac{{kn}}{\varepsilon }\log \frac{B}{\varepsilon }}\right)$ evaluations of the function−f. Furthermore, for both algorithms, we provide approximation guarantees when the k-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical study and examined the practical implications of fairness. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions.

Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form h = f-c, where f is a monotone, non-negative, weakly submodular set function and c is a modular function. We design a deterministic approximation algorithm that runs with O(n/ε log n/(γ ε) ) oracle calls to function h, and outputs a set S such that h(S) ≥ γ(1-ε)f(OPT)-c(OPT)-c(OPT)/γ(1-ε) log f(OPT)/c(OPT), where γ is the submodularity ratio of f. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of f. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function f, and Bayesian A-Optimal design for weakly submodular f. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.

Many decision-making scenarios, e.g., public policy, healthcare, business, and disaster response, require accommodating the preferences of multiple stakeholders. We offer the first formal treatment of reasoning with multi-stakeholder qualitative preferences in a setting where stakeholders express their preferences in a qualitative preference language, e.g., CP-net, CI-net, TCP-net, CP-Theory. We introduce a query language for expressing queries against such preferences over sets of outcomes that satisfy specified criteria, e.g., ψ1PAψ2 (read loosely as the set of outcomes satisfying ψ1 that are preferred over outcomes satisfying ψ2 by a set of stakeholders A). Motivated by practical application scenarios, we introduce and analyze several alternative semantics for such queries, and examine their interrelationships. We provide a provably correct algorithm for answering multi-stakeholder qualitative preference queries using model checking in alternation-free μ-calculus. We present experimental results that demonstrate the feasibility of our approach.

We investigate the problems of maximizing k-submodular functions over total size constraints and over individual size constraints. k-submodularity is a generalization of submodularity beyond just picking items of a ground set, instead associating one of k types to chosen items. For sensor selection problems, for instance, this enables modeling of which type of sensor to put at a location, not simply whether to put a sensor or not. We propose and analyze threshold-greedy algorithms for both types of constraints. We prove that our proposed algorithms achieve the best known approximation ratios for both constraint types, up to a user-chosen parameter that balances computational complexity and the approximation ratio, while only using a number of function evaluations that depends linearly (up to poly-logarithmic terms) on the number of elements n, the number of types k, and the inverse of the user chosen parameter. Other algorithms that achieve the best-known deterministic approximation ratios require a number of function evaluations that depends linearly on the budget B, while our methods do not. We empirically demonstrate our algorithms’ performance in applications of sensor placement with k types and influence maximization with k topics.

We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: SCSKC and DiffC. Given two submodular functions f and g where f is monotone, the objective of SCSKC problem is to find a set S of size at most k that maximizes f(S) under the constraint that g(S) < theta, for a given value of theta. The problem of DiffC focuses on finding a set S of size at most k such that h(S) = f(S)-g(S) is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve data-dependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of SCSKC, we prove that the greedy algorithm produces a solution whose value is at least (1-1/e)f(OPT) - A, where A is the data-dependent additive error. For the DiffC problem, we design an algorithm that uses the SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least (1-1/e)h(OPT)-B, where B is also a data-dependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.

We investigate the problem of multi-objective submodular optimization with cardinality constraint in the context of δ-approximate oracle and show that it is possible to ensure (1 − 1/e)2− 3δ-approximate guarantee for the multi-objective submodular optimization problem. We show that group influence maximization in online social networks is an instance of this optimization problem with cardinality constraint and δ-oracle. We develop a prototype implementation of our solution strategy for group influence maximization problem for networks of different sizes and experimentally justify the effectiveness and scalability of our strategy.

Influence diffusion has been central to the study of the propagation of information in social networks, where influence is typically modeled as a binary property of entities: influenced or not influenced. We introduce the notion of attitude, which, as described in social psychology, is the degree by which an entity is influenced by the information. We present an information diffusion model that quantifies the degree of influence, i.e., attitude of individuals, in a social network. With this model, we formulate and study the attitude maximization problem. We prove that the function for computing attitude is monotonic and sub-modular, and the attitude maximization problem is NP-Hard. We present a greedy algorithm for maximization with an approximation guarantee of (1 - 1/e). Using the same model, we also introduce the notion of “actionable” attitude with the aim to study the scenarios where attaining individuals with high attitude is objectively more important than maximizing the attitude of the entire network. We show that the function for computing actionable attitude, unlike that for computing attitude, is non-submodular but is approximately submodular. We present an approximation algorithm for maximizing actionable attitude in a network. We experimentally evaluated our algorithms and studied empirical properties of the attitude of nodes in the network such as spatial and value distribution of high attitude nodes.

We formulate and study Constrained Influence Maximization problem where a network has two types of nodes-targets and non-targets. Given k and θ, the objective is to find a k-size seed set which maximizes the influence spread among the target nodes and keeps the number of non-targets influenced below the threshold θ. The problem, in general, is NP-hard. We also prove that obtaining a constant factor approximation algorithm for this problem is quasi-NP hard. Nevertheless, we are able to present a greedy algorithm and prove that it has certain approximation guarantees with a multiplicative factor of (1 - 1/e) and an additive error, where the latter is dependent on the underlying network structure. We evaluate the extent of the additive error on several representative social networks of varying sizes, and show that in most scenarios, the greedy algorithm indeed provides a high quality solution efficiently. We also develop a multi-greedy algorithm that attempts to keep multiple seed sets and improves upon the greedy algorithm. However, naive implementations of this algorithm is not practically viable due to prohibitively high time overhead. To address this issue, we develop a two-phase heuristic framework to improve the run times. We have conducted extensive empirical evaluation, which not only validates our algorithms, evaluates their effectiveness and efficiency, but also provides important insights on the interplay between the seed-set size, number of non-targets, the threshold, and the additive approximation error on influence-spread.

We present a framework for reasoning with preferences in the context of Goal-Oriented Requirements Engineering (GORE). Our choice of preference language, conditional importance networks (CI-nets), is motivated by the occurrence in requirements engineering of qualitative preferences and tradeoffs involving sets of items; such preferences are expressed more naturally in CI-nets than in other representations. Building on our past experience with CI-nets, we are improving the scalability and usability of CI-nets for specifying and analyzing requirements preferences. We discuss our ongoing work and long-term plans, including efforts to develop more efficient methods to identify conflicting preferences among possible requirements, guide negotiation of resolutions to such conflicts, and improve traceability and comprehension of requirements preferences.

Asynchronous communication requires message queues to store the messages that are yet to be consumed. Verification of interactions in asynchronously communicating systems is challenging since the sizes of these queues can grow arbitrarily large during execution. In fact, behavioral models for asynchronously communicating systems typically have infinite state spaces, which makes many analysis and verification problems undecidable. In this paper, we show that, focusing only on the interaction behavior (modeled as the global sequence of messages that are sent, recorded in the order they are sent) results in decidable verification for a class of asynchronously communicating systems. In particular, we present the necessary and sufficient condition under which asynchronously communicating systems with unbounded queues exhibit interaction behavior that is equivalent to their interactions over finitely bounded queues. We show that this condition can be automatically checked, ensuring existence of a finite bound on the queue sizes, and, we show that, the finite bound on the queue sizes can be automatically computed.

As cyber threats increasingly utilize automated and adaptive attacks to bypass or overwhelm static defenses, the role of intrusion detection and response systems (IDRS) as an active defense layer is becoming more critical. To remain effective against current attacks IDRS must be capable of automating detection of, and response to, threats in their specific environment. Different operating characteristics, detection capabilities, and response actions all contribute to make each environment unique, complicating this automation. In this work we consider IDRS automation in three areas: detector tuning, detector correlation, and response selection. We motivate and present a novel, more finely-grained model of threats, detectors, and responses called S-MAIDS: A Semantic Model of Automated Intrusion Detection Systems. Based on the concept of a "signal" (an observable indicator of an attack), we show the utility of combining such a model with an existing measure of IDRS performance to facilitate automated tuning, cross-system correlation, and response selection. We support our claims through several case-studies demonstrating the application of this model, and provide the model as an OWL ontology.

In many applications such as service-oriented computing, users often prefer some compositions over the others based on their preferences over non-functional attributes such as security and cost. After a composition is deployed, apart from changes in the functional requirements, service-oriented architectures often have to deal with changes in the user preferences over the non-functional attributes and/or repository of available components. We formulate the problem of adaptation as iterative substitution of appropriate components in a composition, and provide two algorithms that produce a sequence of increasingly preferred adaptations with time: a fast algorithm that searches for preferred adaptations by improving the valuation of the relatively more important attributes, and another that is computationally more intensive but guaranteed to produce at least one preferred adaptation, if one exists.

Systems-on-chip (SoCs) contain multiple interconnected and interacting components. In this paper, we present a compositional approach for the integration of multiple components with a wide range of protocol mismatches into a single SoC. We show how SoC construction can be done in single-step when all components are integrated at once or it can also be performed incrementally by adding components to an already integrated design. Using a number of AMBA IPs, we show that the proposed framework is able to perform protocol conversion in many cases where existing approaches fail.

Since software systems are becoming increasingly more concurrent and distributed, modeling and analysis of interactions among their components is a crucial problem. In several application domains, message-based communication is used as the interaction mechanism, and the communication contract among the components of the system is specified semantically as a state machine. In the service-oriented computing domain such communication contracts are called "choreography" specifications. A choreography specification identifies allowable ordering of message exchanges in a distributed system. A fundamental question about a choreography specification is determining its realizability, i.e., given a choreography specification, is it possible to build a distributed system that communicates exactly as the choreography specifies? Checking realizability of choreography specifications has been an open problem for several years and it was not known if this was a decidable problem. In this paper we give necessary and sufficient conditions for realizability of choreographies. We implemented the proposed realizability check and our experiments show that it can efficiently determine the realizability of 1) web service choreographies, 2) Singularity OS channel contracts, and 3) UML collaboration (communication) diagrams.

In recent years, cost-sensitive intrusion response has gained significant interest mainly due to its emphasis on the balance between potential damage incurred by the intrusion and cost of the response. However, one of the challenges in applying this approach is defining consistent and adaptable measurements of these cost factors on the basis of requirements and policy of the system being protected against intrusions. In this paper we present a framework for the cost-sensitive selection of intrusion response. Specifically, we introduce a set of measurements that characterize potential costs associated with the intrusion handling process and propose evaluation method of intrusion response with respect to the risk of potential intrusion damage, effectiveness of response action and response cost for a system. We provide an implementation of the proposed solution as a plugin tool for Snort IDS and demonstrate its advantages on DARPA data set and real network traffic.

We have developed a new approximate probabilistic model-checking method for untimed properties in probabilistic systems, expressed in a probabilistic temporal logic (PCTL, CSL). This method, in contrast to the existing ones, does not require the untimed until properties to be bounded a priori, where the bound refers to the number of discrete steps in the system required to verify the until property. The method consists of two phases. In the first phase, a suitable system- and property-dependent bound k 0 is obtained automatically. In the second phase, the probability of satisfying the k 0 -bounded until property is computed as the estimate of the probability of satisfying the original unbounded until property. Both phases require only verification of bounded until properties, which can be effectively performed by simulation-based methods. We prove the correctness of the proposed two-phase method and present its optimized implementation in the widely used PRISM model-checking engine. We compare this implementation with sampling-based model-checking techniques implemented in two tools: PRISM and MRMC. We show that for several models these existing tools fail to compute the result, while the two-phase method successfully computes the result efficiently with respect to time and space.

Spread of infections (diseases, ideas, etc.) in a networkcan be modeled as the evolution of states of nodes ina graph as a function of the states of their neighbors.Given an initial configuration of a network in which asubset of the nodes have been infected, and an infectionpropagation function that specifies how the states ofthe nodes evolve over time, we show how to use modelchecking to identify, verify, and evaluate the effectivenessof intervention policies for containing the propagationof infection over such networks.

For a Web service composition to satisfy a user's needs, it must not only provide the desired functionality, but also have nonfunctional properties (e.g., reliability, availability, cost) that are acceptable to the user. In the recent past, several techniques have been developed and deployed to identify a composite service that conforms to the functional requirements and is also optimal with respect to the user-defined preferences over non-functional properties. However, these composition techniques are limited to using one formalism for specifying the required functionality, in short, the existing techniques cannot identify optimal (w.r.t. non-functional properties) composite services that are required to satisfy functional requirements described in multiple formalisms. We have previously proposed a meta-framework for service composition that involves decomposing the required functionality into a boolean combination of atomic requirements, which are expressed using different formalisms. This meta-framework supports the use of multiple formalisms and their corresponding composition algorithms within a single scenario. In this paper, we integrate support for unconditional preferences over nonfunctional requirements into this composition meta-framework. We show that for a large class of problems, local selection of preferred service(s) can yield the most preferred composite service that satisfies the desired functional requirements.

In goal-oriented requirements engineering, a goal model graphically represents relationships between the required goals (functional requirements), tasks (realizations of goals), and optional goals (non-functional properties) involved in designing a system. It may, however, be impossible to find a design that fulfills all required goals and all optional goals. In such cases, it is useful to find designs that provide the required functionality while satisfying the most preferred set of optional goals under the goal model's constraints. We present an approach that considers expressive qualitative preferences over optional goals, as these can model interacting and/or mutually exclusive subgoals. Our framework employs a model checking-based method for reasoning with qualitative preferences to identify the most preferred alternative(s). We evaluate our approach using existing goal models from the literature.

Choreography analysis has been a crucial problem in service oriented computing. Interactions among services involve message exchanges across organizational boundaries in a distributed computing environment, and in order to build such systems in a reliable manner, it is necessary to develop techniques for analyzing such interactions. Choreography conformance involves verifying that a set of services behave according to a given choreography specification that characterizes their interactions. Unfortunately this is an undecidable problem when services interact with asynchronous communication. In this paper we present techniques that identify if the interaction behavior for a set of services remain the same when asynchronous communication is replaced with synchronous communication. This is called the synchronizability problem and determining the synchronizability of a set of services has been an open problem for several years. We solve this problem in this paper. Our results can be used to identify synchronizable services for which choreography conformance can be checked efficiently. Our results on synchronizability are applicable to any software infrastructure that supports message-based interactions.

Dominance testing, the problem of determining whether an outcome is preferred over another, is of fundamental importance in many applications. Hence, there is a need for algorithms and tools for dominance testing. CP-nets and TCP-nets are some of the widely studied languages for representing and reasoning with preferences. We reduce dominance testing in TCP-nets to reachability analysis in a graph of outcomes. We provide an encoding of TCP-nets in the form of a Kripke structure for CTL. We show how to compute dominance using NuSMV, a model checker for CTL. We present results of experiments that demonstrate the feasibility of our approach to dominance testing.

With the increasing reliance of complex real-world applications on composite web services assembled from independently developed component services, there is a growing need for effective approaches to verifying that a composite service not only offers the required functionality but also satisfies the desired non-functional requirements (NFRs). In high-assurance applications such as traffic control, medical decision support, and coordinated response to civil emergencies, of special concern are NFRs having to do with security, safety and reliability of composite services. Current approaches to verifying NFRs of composite services (as opposed to individual services) remain largely ad-hoc and informal in nature. In this paper we develop techniques for ensuring that a composite service meets the user-specified NFRs expressible in the form of hard constraints e.g., “response time has to be less than 5 minutes.” We introduce an automata-based framework for verifying that a composite service satisfies the desired NFRs based on the known guarantees regarding the non-functional properties of the component services. We further show how to improve the efficiency of verifying that a composite service indeed satisfies a desired set of NFRs by: (i) Exploiting information about the applicability of specific NFRs (e.g., security) only to certain subsets of the component services that make up a composite service to minimize the verification effort and (ii) Identifying inconsistencies between NFRs with overlapping scopes. We illustrate how our approach can be used to verify the security requirements for an Emergency Management System. We also show how the approach can be used to verify whether a composite service satisfies any desired set of NFRs that can be expressed in the form of hard constraints of a quantitative nature.

We study the problem of statistical model checking of probabilistic systems for PCTL unbounded until property PJoinp(Æ1UÆ2) (where Join |X| {<, d, >, e}) using the computation of P d 0(Æ1UÆ2). The approach is first proposed by Sen et al. in CAV'05 but their approach suffers from two drawbacks. Firstly, the computation of Pd0Æ1UÆ2) requires for its validity, a user-specified input parameter ´2 which the user is unlikely to correctly provide. Secondly, the validity of computation of Pd0Æ1UÆ2) is limited only to probabilistic models that do not contain loops. We present a new technique which addresses both problems described above. Essentially our technique transforms the hypothesis test for the unbounded until property in the original model into a new equivalent hypothesis test for bounded until property in our modified model. We empirically show the effectiveness of our technique and compare our results with those using the method proposed by Sen et al.

In this paper we present a structured methodology for evaluating cost of responses based on three factors: the response operational cost associated with the daily maintenance of the response, the response goodness that measures the applicability of the selected response for a detected intrusion and the response impact on the system that refers to the possible response effect on the system functionality. The proposed approach provides a consistent basis for response evaluation across different systems while incorporating security policy and properties of the specific system environment.

The automated design of SoCs from pre-selected IPs that may require different clocks is challenging because of the following issues. Firstly, protocol mismatches between IPs need to be resolved automatically before IPs are integrated. Secondly, the presence of multiple clocks makes the protocol conversion even more difficult. Thirdly, it is desirable that the resulting integration is correct-by-construction, i.e., the resulting SoC satisfies given system-level specifications. All of these issues have been studied extensively, although not in a unifying manner. In this paper we propose a framework based on protocol conversion that addresses all these issues. We have extensively studied many SoC design problems and show that the proposed methodology is capable of handling them better than other known approaches. A significant contribution of the proposed approach is that it nicely generalizes many existing techniques for formal SoC design and integrates them into a single approach.

We study the problem of substitution of components in a composite service, especially in the setting where the substitute is composed in an asynchronous fashion. By asynchronous composition, we mean that the participants in the composition are not required to synchronize on the input/output actions as long as the input to one participant always follows the corresponding output from another. We show that such asynchronous composition can be realized by synchronous composition of the participating components along with an appropriate buffer process. We obtain the condition which, when satisfied by a service Q1', allows Q1' to act as a correct substitute for Q1in a composition of services Q1and Q2. Our work extends prior results on substitutability where the conditions relied on synchronous composition and/or on the structural equivalence between the substitute and the component being replaced.

We address the problem of optimizing mediator-based service composition where the services and the desired composition (goal) functionality are represented as i/o automata with loops. The objective of optimization is to minimize the costs of communications and computations necessary to realize the goal from the existing services. We develop an algorithm to compute the minimum cost of an automaton representing the choreographed behavior of services realizing the goal. This forms the central theme of our technique for developing automatically a strategy of decentralized mediation that will result in the optimized composition of services.

Verifying correctness properties of parameterized systems is a long-standing problem. The challenge lies in the lack of guarantee that the property is satisfied for all instances of the parameterized system. Existing work on addressing this challenge aims to reduce this problem to checking the properties on smaller systems with a bound on the parameter referred to as the cut-off. A property satisfied on the system with the cut-off ensures that it is satisfied for systems with any larger parameter. The major problem with these techniques is that they only work for certain classes of systems with specific communication topology such as ring topology, thus leaving other interesting classes of systems unverified. We contribute an automated technique for finding the cut-off of the parameterized system that works for systems defined with any topology. Given the specification and the topology of the system, our technique is able to automatically generate the cut-off specific to this system. We prove the soundness of our technique and demonstrate its effectiveness and practicality by applying it to several canonical examples where in some cases, our technique obtains smaller cut-off values than those presented in the existing literature.

The proliferation of complex and fast-spreading intrusions not only requires advances in intrusion detection mechanisms but also demands development of sophisticated and automated intrusion response systems. In this paper we present a novel cost-sensitive model for intrusion response that incorporates preemptive deployment of the response actions. Specifically, our technique relies on comparing the cost of deploying a response against the cost of damage caused by an "'un-attended" intrusion and decides to preemptively deploy a response with maximum benefit. Our technique further allows adaptation of responses to the changing environment through evaluation of success and failure of previously triggered responses. We demonstrate the advantages of the approach and evaluate it using a damage reduction metric.

We study the problem of synthesis of a choreographer in Web service composition for a given set of services and a goal. Services and goal are represented using I/O automata which can succinctly and precisely describe the interfaces of the services. Our technique considers existence and synthesis of two types of the choreographers: a simple choreographer capable of only relaying outputs from one service to input of another and a transducing choreographer which is capable of storing and reusing inputs/outputs from the services. The central theme of our technique relies on generating I/O automata representation of all possible choreographed behavior of existing services (captured in form of universal service automaton, a concept introduced in this paper) and verifying that the goal can be simulated by the universal set of choreographed behaviors.

Web service substitution refers to the problem of identifying a service that can replace another service in the context of a composition with a specified functionality. Existing solutions to this problem rely on detecting the functional and behavioral equivalence of a particular service to be replaced and candidate services that could replace it. We introduce the notion of context-specific substitutability, where context refers to the overall functionality of the composition that is required to be maintained after replacement of its constituents. Using the context information, we investigate two variants of the substitution problem, namely environment-independent and environment- dependent, where environment refers to the constituents of a composition and show how the substitutability criteria can be relaxed within this model. We provide a logical formulation of the resulting criteria based on model checking techniques as well as prove the soundness and completeness of the proposed approach.

We present a goal-directed, local and on-the-fly algorithm for verifying the existence and synthesizing a choreographer forWeb service composition. We use i/o-automata to represent services, the desired functionality of the composition, and a choreographer to achieve the desired service by composing the existing ones. Choreographer existence and synthesis are typically performed by identifying all possible compositions realizable from the existing services and verifying whether one such composition conforms to the desired required functionality. Such a technique is subject to state-space explosion. In light of this, we have developed a tabled-logic programming technique which generates and explores compositions in a goal-directed fashion to prove/disprove the existence of choreographer and to infer whether the desired functionality is realizable. We present a prototype implementation and show the practical applicability of our technique using a variety of composition problems with the corresponding computational savings in terms of number of states and transitions explored.

Recent advances in intrusion detection field brought new requirements to intrusion prevention and response. Traditionally, the response to an attack was manually triggered by an administrator. However, increased complexity and speed of the attack-spread during recent years showed acute necessity for complex dynamic response mechanisms. Although intrusion detection systems are being actively developed, research efforts in intrusion response are still isolated. In this work we present taxonomy of intrusion response systems, together with a review of current trends in intrusion response research. We also provide a set of essential fetures as a requirement for an ideal intrusion response system.

We report on our efforts to use the XMC model checker to model and verify the Java metalocking algorithm. XMC [Ramakrishna et al. 1997] is a versatile and efficient model checker for systems specified in XL, a highly expressive value-passing language. Metalocking [Agesen et al. 1999] is a highly-optimized technique for ensuring mutually exclusive access by threads to object monitor queues and, therefore; plays an essential role in allowing Java to offer concurrent access to objects. Metalocking can be viewed as a two-tiered scheme. At the upper level, the metalock level, a thread waits until it can enqueue itself on an object's monitor queue in a mutually exclusive manner. At the lower level, the monitor-lock level, enqueued threads race to obtain exclusive access to the object. Our abstract XL specification of the metalocking algorithm is fully parameterized, both on the number of threads M , and the number of objects N . It also captures a sophisticated optimization of the basic metalocking algorithm known as extra-fast locking and unlocking of uncontended objects. Using XMC, we show that for a variety of values of M and N , the algorithm indeed provides mutual exclusion and freedom from deadlock and lockout at the metalock level. We also show that, while the monitor-lock level of the protocol preserves mutual exclusion and deadlock-freedom, it is not lockout-free because the protocol's designers chose to give equal preference to awaiting threads and newly arrived threads.

Run-time monitoring is a powerful approach for dynamically detecting faults or malicious activity of software systems. However, there are often two obstacles to the implementation of this approach in practice: (1) that developing correct and/or faulty behavioral patterns can be a difficult, labor-intensive process, and (2) that use of such pattern-monitoring must provide rapid turn-around or response time. We present a novel data structure, called extended action graph, and associated algorithms to overcome these drawbacks. At its core, our technique relies on effectively identifying and caching specifications from (correct/faulty) patterns learned via machine-learning algorithm. We describe the design and implementation of our technique and show its practical applicability in the domain of security monitoring of sendmail software

We propose a specification-driven approach to Web service composition. The proposed framework allows users to start with a high-level, possibly incomplete specification of a desired (goal) service that is to be realized using a subset of the available component services. These services are represented by the system using transition systems augmented with guards over variables with infinite domains and are used to determine a strategy for their composition that would realize the goal service. In the event that the goal service cannot be realized using the available services, the system identifies the cause(s) for such failure which can then be used by the developer to reformulate the goal specification. Thus, the system supports Web service composition through iterative refinement of the functional specifications. We present a prototype implementation in tabled-logic programming environment that illustrates the key features of the proposed approach

Model checking is usually applied at the design phase to verify that preliminary high-level design specifications conform to their requirements. Source code analysis, on the other hand, is used to check for correctness of implementation once it is realized from the design specifications. However, the current practice of validating a design and its implementation in isolation makes it necessary to employ rigorous testing analysis to empirically ensure that the implementation satisfies the design specification. This article describes a formal framework that allows design models to contain embedded partial implementations as components; these models are then formally analyzed to ensure that global requirements are satisfied. This framework can be utilized to incrementally develop and ensure correctness of the design and the corresponding implementation. Realization of this framework requires consolidation and expansion of traditional formal verification techniques by integration of model checking, program analysis and constraint solving