We address logic locking, a mechanism for securing digital Integrated Circuits (ICs) from piracy by untrustworthy foundries. We discuss previous work and the state-of-the-art, and observe that, despite more than a decade of research that has gone into the topic (resulting in both powerful attacks and subsequent defenses), there is no consensus on what it means for a particular locking mechanism to be secure. This paper attempts to remedy this situation. Specifically, it formulates a definition of security for a logic locking mechanism based on indistinguishability and relates the definition to security from actual attackers in a precise and unambiguous manner. We then describe a mechanism that satisfies the definition, thereby achieving (provable) security from all prior attacks. The mechanism assumes the existence of both a puncturable pseudorandom function family and an indistinguishability obfuscator, two cryptographic primitives that exist under well-founded assumptions. The mechanism builds upon the Stripped-Functionality Logic Locking (SFLL) framework, a state-of-the-art family of locking mechanisms whose potential for ever achieving security is currently in question. Along the way, partly as motivation, we present additional results, such as a reason founded in average-case complexity for why benchmark circuits locked with a prior scheme are susceptible to the well-known SAT attack against such schemes, and why provably thwarting the SAT attack is insufficient as a meaningful notion of security for logic locking.

Access control deals with the roles and privileges to which a user is authorized, and is an important aspect of the security of a system. As enterprise access control systems need to scale to several users, roles and privileges, it is common for access control models to support delegation: a trusted security administrator is able to give semi-trusted users the ability to change portions of the authorization state. With delegation comes the danger that semi-trusted users, perhaps in collusion, may effect a state that violates enterprise policy, which in turn results in the problem called safety analysis, which is regarded as a fundamental and technically challenging problem in access control. Safety analysis is used by a trusted security administrator to answer “what if” questions before she grants privileges to a semi-trusted user. Safety analysis has been studied for various access control schemes in the literature; we address safety analysis in the context of Administrative Temporal Role-Based Access Control (ATRBAC), an administrative model for TRBAC, which is an extension to the traditional RBAC. ATRBAC has new features, which introduce new technical challenges for safety analysis: (i) a time-dimension: two new components in each administrative rule that specify in which time periods an administrative action may be effected, and a user is authorized to a role, and, (ii) two new kinds of rules for whether a role is enabled for administrative action. We propose a software tool, which we call Cree, for safety analysis of ATRBAC policies. In Cree we reduce ATRBAC-Safety to model checking and use an off-the-shelf model checker, NuSMV. The foundation for Cree is the observation from our prior work that ATRBAC safety is PSPACE. Along with an efficient reduction to model checking, we include in Cree four techniques to further improve performance: Polynomial Time Solving when possible, Forward and Backwards Pruning, Abstraction Refinement, and Bound Estimation. These are inspired by prior work, but our algorithms are different in that they address the new challenges that ATRBAC introduces. We discuss our design of Cree, and the results of a thorough empirical assessment across our approach, and five other prior tools for ATRBAC safety. Our results suggest that there are input classes for which Cree outperforms existing tools, and for the remainder, Cree's performance is no worse. We have made Cree available as open-source for public download.

Recent work suggests that scheduling, with security as a consideration, can be effective in minimizing information leakage, via side-channels, that can exist when virtual machines (VMs) co-reside in clouds. We analyze the overhead that is incurred by such an approach. We first pose and answer a fundamental question: is the problem tractable? We show that the seemingly simpler sub-cases of initial placement and migration across only two equal-capacity servers are both intractable (NP-hard). However, a decision version of the general problem to which the optimization version is related polynomially is in NP. With these results as the basis, we make several other contributions. We revisit recent work that proposes a greedy algorithm for this problem, called Nomad. We establish that if P ≠ NP, then there exist infinitely many classes of input, each with an infinite number of inputs, for which a decrease in information leakage is possible, but Nomad provides none, let alone minimize it. We establish also that a mapping to Integer Linear Programming (ILP) in prior work is deficient in that the mapping can be inefficient (exponential-time), and therefore does not accurately convey the overhead of such an approach that, unlike Nomad, actually decreases information leakage. We present our efficient reductions to ILP and boolean satisfiability in conjunctive normal form (CNF-SAT). We have implemented these approaches and conducted an empirical assessment using the same ILP solver as prior work, and a SAT solver. Our analytical and empirical results more accurately convey the overhead that is incurred by an approach that actually provides security (decrease in information leakage).

Safety analysis is recognized as a fundamental problem in access control. It has been studied for various access control schemes in the literature. Recent work has proposed an administrative model for Temporal Role-Based Access Control (TRBAC) policies called Administrative TRBAC (ATRBAC). We address ATRBAC-safety. We first identify that the problem is PSPACE-Complete. This is a much tighter identification of the computational complexity of the problem than prior work, which shows only that the problem is decidable. With this result as the basis, we propose an approach that leverages an existing open-source software tool called Mohawk to address ATRBAC-safety. Our approach is to efficiently reduce ATRBAC-safety to ARBAC-safety, and then use Mohawk. We have conducted a thorough empirical assessment. In the course of our assessment, we came up with a "reduction toolkit," which allows us to reduce Mohawk+T input instances to instances that existing tools support. Our results suggest that there are some input classes for which Mohawk+T outperforms existing tools, and others for which existing tools outperform Mohawk+T. The source code for Mohawk+T is available for public download.