The User Authorization Query (UAQ) Problem is a key issue related to efficient handling of users’ access requests in Role Based Access Control (RBAC) systems. However, there may not exist any solution to a given UAQ problem due to the limitation caused by the current system state, because missing any requested permission may thwart a task, while an extra permission may bring an intolerable risk to the system. Hence, update of the role–permission assignment is needed to support the feasibility of an UAQ problem. In this paper, we study fundamental problems related to role–permission reassignment, including the RVP problem the goal of which is to determine whether a given role–permission assignment satisfies all reassignment objectives and does not violate any prerequisite constraint or permission-capacity constraint, the RFP problem which verifies whether there exists a valid role–permission assignment, and the RGP problem which studies how to generate a valid role–permission assignment. We present the computational complexity analysis of RVP, RFP and RGP, showing that RVP is solvable in linear time, while both RFP and RGP are NP-hard. We also propose an approach for RGP, which incorporates a preprocessing to decrease the size of the problem, and reduce it to an SAT problem. Finally, experimental results show the validity and effectiveness of our proposed approach.

To save energy and alleviate interference, connected dominating set (CDS) was proposed to serve as a virtual backbone of wireless sensor networks (WSNs). Because sensor nodes may fail due to accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone with high redundancy in both coverage and connectivity. This can be modeled as a k-connected m-fold dominating set (abbreviated as (k, m)-CDS) problem. A node set C ⊆ V (G) is a (k, m)-CDS of graph G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. Constant approximation algorithm is known for (3, m)-CDS in unit disk graph, which models homogeneous WSNs. In this paper, we present the first performance guaranteed approximation algorithm for (3, m)-CDS in a heterogeneous WSN. In fact, our performance ratio is valid for any topology. The performance ratio is at most γ, where γ = α + 8 + 2 ln(2α - 6) for α ≥ 4 and γ = 3α +2 ln 2 for α <; 4, and α is the performance ratio for the minimum (2, m)-CDS problem. Using currently best known value of α, the performance ratio is ln δ +o(ln δ), where δ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. Applying our algorithm on a unit disk graph, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the (3, m)-CDS problem on a unit disk graph.

In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight (k, m)-CDS problem in unit disk graphs under the assumption that k and m are two fixed constants with m ≥ k. Prior to this paper, constant approximation algorithms are known for k = 1 with weight and 2 ≤ k ≤ 3 without weight. Our result is the first constant approximation algorithm for the (k, m)-CDS problem with general k, m and with weight. The performance ratio is (α+5ρ) fork ≥ 3 and (α+2.5ρ) for k = 2, where α is the performance ratio for the minimum weight m-fold dominating set problem and ρ is the performance ratio for the subset k-connected subgraph problem (both problems are known to have constant performance ratios).

Modern computing systems typically use a large number of independent, non-identical computing nodes to perform a set of coordinated computations in parallel. The computing system and its constituent computing nodes often exhibit more than two performance levels or states corresponding to different computing powers. This paper models and evaluates performability of largescale multi-state computing systems, which is the probability that a computing system performs at a particular performance level. The heterogeneity in the constituent components of different nodes (due to factors such as different model generations, model suppliers, and operating environments) makes performability analysis difficult and challenging. In this paper a specification method for system performance level (SPL) is first introduced. A multi-valued decision diagram (MDD) based approach is then proposed for performability analysis of multi-state computing systems consisting of nodes with different state occupation probabilities, which encompasses novel and efficient MDD model generation procedures. Example and benchmark studies are performed to show that the proposed approach can offer efficient performability analysis of large-scale computing systems.

In a network system, a propagated failure (PF) is a failure originating from a network component that can cause extensive damages to other network components or even the failure of the entire system. Existing works on PFs have mostly assumed the deterministic effect from a component PF, i.e., a fixed subset of system components is affected whenever the PF occurs. However, in many real-world systems, the components may have different levels of protection, and the effect of damage from a component PF can be dependent upon the status of other components within the same system or the occurrence order of component failures. This paper proposes a new analytical method based on multi-valued decision diagrams (MDDs) for the reliability analysis of network systems with dependent propagation effects. Particularly, new MDD modeling procedures are proposed for considering different types of dependent PF effects introduced by different protection levels. After the system MDD is generated using a new MDD combination algorithm to efficiently handle the dependent PF effects, methods for computing the network reliability and component importance measures are presented. The detailed analysis of an example network system subjected to dependent PFs is presented to illustrate the basics and application of the proposed method. It is shown that the proposed MDD-based method generates smaller model size and thus presents lower computational complexity in the model generation and evaluation than the existing Markov method and separable method.