7900372
Complexity of the Unique Extension Problem in Default Logic
In this paper we analyze the problem of checking whether a default theory has a single extension. This problem is important for at least three reasons. First, if a theory has a single extension, nonmonotonic inference can be reduced to entailment in propositional logic (which is computationally easier) using the set of consequences of the generating defaults. Second, a theory with many extensions is typically weak i.e., it has few consequences; this indicates that the theory is of little use, and that new information has to be added to it, either as new formulae, or as preferences over defaults. Third, some applications require as few extensions as possible (e.g. diagnosis). We study the complexity of checking whether a default theory has a single extension. We consider the combination of several restrictions of default logics: seminormal, normal, disjunction-free, unary, ordered. Complexity varies from the first to the third level of the polynomial hierarchy. The problem of checking whether a theory has a given number of extensions is also discussed.
33218482
Some Algorithms for Extension Computation of Nonmonotonic Rule Systems
In this paper, we will place our emphasis on the problem of existence of extensions and on finding more efficient algorithms for computing extensions of nonmonotonic rule systems. First, in order to dedicate further research into nonmonotonic rule systems a new characterization and some new results are given. This characterization and these results lead to new algorithms for computing extensions. Second, a class of nonmonotonic rule systems, called regular nonmonotonic rule systems, is developed. The existence of extensions and semi-monotonicity of regular nonmonotonic rule systems are proved. Third, we prove that each regular nonmonotonic rule system has at most 1.47^n extensions, where n is the number of elements occurring in the system.
8163164
Regular disjunction-free default theories
In this paper, the class of regular disjunction-free default theories is introduced and investigated. A transformation from regular default theories to normal default theories is established. The initial theory and the transformed theory have the same extensions when restricted to old variables. Hence, regular default theories enjoy some similar properties (e.g., existence of extensions, semi-monotonicity) as normal default theories. Then, a new algorithm for credulous reasoning of regular theories is developed. This algorithm runs in a time not more thanO(1. 45n), wheren is the number of defaults. In case of regular prerequisite-free or semi-2CNF default theories, the credulous reasoning can be solved in polynomial time. However, credulous reasoning for semi-Horn default theories is shown to be NP-complete although it is tractable for Horn default theories. Moreover, skeptical reasoning for regular unary default theories is co-NP-complete.
31571428
Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency
We say a propositional formula F in conjunctive normal form is represented by a formula H and a homomorphism φ, if φ(H) = F. A homomorphism is a mapping consisting of a renaming and an identification of literals. The deficiency of a formula is the difference between the number of clauses and the number of variables. We show that for fixed k ≥ 1 and t ≥ 1 each minimal unsatisfiable formula with deficiency k can be represented by a formula H with deficiency t and a homomorphism and such a representation can be computed in polynomial time.
30011892
Complexity of argument-based default reasoning with specificity
In this paper we investigate the complexity of Dung and Son's approach to default reasoning with specificity. We show that the three decision problems: existence of extensions, brave reasoning and cautious reasoning are generally complete for the second level of the polynomial hierarchy. For some restricted cases, e.g., Horn and 2CNF default theories, all the three problems are intractable although classical brave reasoning in these cases is tractable. Finally, we show that stratification can not reduce the complexity of brave and cautious reasoning although it guarantees the existence of extensions.
13301251
Fixed-parameter tractability of disjunction-free default reasoning
In this paper, the parameter which is the source of the complexity of disjunction-free default reasoning is determined. It is shown that when the value of this parameter is fixed, the disjunction-free default reasoning can be solved in time bounded by a polynomial whose degree does not depend on the parameter. Consequently, disjunction-free default reasoning is fixed parameter tractable.
1661187
Siren: catching evasive malware
With the growing popularity of anomaly detection systems, which is due partly to the rise in zero-day attacks, a new class of threats have evolved where the attacker mimics legitimate activity to blend in and avoid detection. We propose a new system called Siren that injects crafted human input alongside legitimate user activity to thwart these mimicry attacks. The crafted input is specially designed to trigger a known sequence of network requests, which Siren compares to the actual traffic. It then flags unexpected messages as malicious. Using this method, we were able to detect ten spyware programs that we tested, many of which attempt to blend in with user activity. This paper presents the design, implementation, and evaluation of the Siren activity injection system, as well as a discussion of its potential limitations
15922787
Supporting Mobility in MosquitoNet
The goal of the MosquitoNet project is to provide continuous Internet connectivity to mobile hosts. Mobile hosts must be able to take advantage of the best network connectivity available in any location, whether wired or wireless. We have implemented a mobile IP system that supports seamless switching between different networks and communication devices. In contrast to previous approaches to mobile IP, we believe mobile hosts should not assume any explicit mobility support from the networks they visit, aside from basic Internet connectivity. This decision places extra responsibilities on the mobile hosts themselves. In this paper, we describe the design and implications of such a system. Measurements of our implementation show that the inherent overhead to switch networks (below 10ms) is insignificant compared to the time required to bring up a new communication device.
15041582
Towards the Semantics and Verification of BPEL4WS
In this paper, we discuss the semantics of BPEL4WS language which is a de facto standard for specifying and execution workflow specification for web service composition and orchestration. We propose a language @m-BPEL that includes most primitive and structured activities of BPEL4WS, and define its semantics. As the Timed Automata (TA) is powerful in designing real-time models with multiple clocks and has well developed automatic tool support, we define a map from @m-BPEL into composable TA. Therefore, the properties we want to check can be verified in TA network correspondingly. Furthermore, we prove that the mapping from @m-BPEL to TA is a simulation, which means that the TA network simulates correctly the corresponding @m-BPEL specification. The case study with model checker Uppaal shows that our method is effective, and a Java supporting tool based on Uppaal model checker engine has been developed.
18186547
Experiences with a Mobile Testbed
This paper presents results from an eight-day network packet-trace of MosquitoNet. MosquitoNet allows users of laptop computers to switch seamlessly between a metropolitan-area wireless network and a wired network (10 Mbit/s Ethernet) available in offices and on-campus residences. Results include the amount of user mobility between the wired and wireless networks, the amount of mobility within the wireless network, an examination of application end-to-end delays, and an examination of overall packet loss and reordering in the wireless network. We find that the average mobile host switches between the wired and wireless networks 14 times during the trace and moves within the wireless network five times. Round trip latencies in the wireless network are very high, with a minimum of 0.2 seconds. Even higher end-to-end delays, of up to hundreds of seconds, are due to packet loss and reordering. These delays cause users to change their usage patterns when connected to the wireless network. We conclude that latency is a critical problem in the wireless network.
1611793
Type Checking Choreography Description Language
The Web Services Choreography Description Language (WS-CDL) is a W3C specification developed for the description of peer-to-peer collaborations of participants from a global viewpoint. Currently WS-CDL has no rigorous static type checking. We believe that introducing a type system will exclude many design and description errors, and ensure desirable properties of the choreography specifications. In this paper, we took a core language CDL, which covers most of the important features of the WS-CDL, and is more convenient for the study. We developed the abstract syntax and operational semantics of CDL, and defined a collection of rules which can be used to check if choreography is well-typed. Moreover, we also proved some type safety theorems for CDL in the sense that well-typed choreography cannot get stuck. We show how the use of type information can allow us to gain confidence in the correctness of choreography.