Access control policies are programs used to secure cloud resources. These polices should only grant the necessary permissions that a given application needs. However, it is challenging to write and maintain policies as applications and their required permissions change over time. In this paper, we focus on the Amazon Web Services (AWS) IAM policy language and present an approach that, given a policy, synthesizes a modified policy that is more restrictive and better abides to the principle of least privilege. Our approach looks at the actual access history (e.g., access logs) used by an application and computes the least permissive local modification of the user-given policy that still provides the same permissions that were observed in the access history. We treat the problem of computing the least permissive policy as a generalization problem in a lattice of possible policies (i.e., the set of local modifications). We show that our synthesis algorithm comes with correctness guarantees and is amendable to an efficient implementation that is easy to parallelize. We implement our algorithm in a tool IAM-PolicyRefiner and evaluate it on policies attached to AWS roles with access logs. For each role, IAM-PolicyRefiner can compute easy-to-inspect refined policies in less than 1 minute, and the refined policies do not overfit to the requests in the log—i.e., the policies also allow requests in a left-out test set of requests.

Abstract String solvers are automated-reasoning tools that can solve combinatorial problems over formal languages. They typically operate on restricted first-order logic formulas that include operations such as string concatenation, substring relationship, and regular expression matching. String solving thus amounts to deciding the satisfiability of such formulas. While there exists a variety of different string solvers, many string problems cannot be solved efficiently by any of them. We present a new approach to string solving that encodes input problems into propositional logic and leverages incremental SAT solving. We evaluate our approach on a broad set of benchmarks. On the logical fragment that our tool supports, it is competitive with state-of-the-art solvers. Our experiments also demonstrate that an eager SAT-based approach complements existing approaches to string solving in this specific fragment.

The utility of unmanned aerial vehicle (UAV)-based data collection for massive sensor networks has received great attention. However, limited onboard battery capacity poses a constraint on its operation. In this paper, we model data collection of backscatter nodes using UAVs that are supported by wireless energy transfer from LASER based charging stations (LCS) for sustainable operations. Under the assumption that UAV to backscatter node channel experiences Nakagami-$m$fading, we derive the expression for signal-to-noise ratio (SNR). We define expressions for overall backscatter energy outage probability and overall backscatter SNR outage probability as the metrics of sustainable operations. Our numerical simulations reveal that, at optimal transmit power up to around 55% of UAV operations are reliable and completely sustainable via LCS.

We present a fully automatic algorithm for verifying safety properties of parameterized software systems. This algorithm is based on both IC3 and Lazy Annotation. We implemented it in Cubicle, a model checker for verifying safety properties of array-based systems. Cache-coherence protocols and mutual exclusion algorithms are known examples of such systems. Our algorithm iteratively builds an abstract reachability graph refining the set of reachable states from counter-examples. Refining is made through counter-example approximation. We show the effectiveness and limitations of this algorithm and tradeoffs that results from it.

Building accurate classifiers is difficult when using data that is skewed or imbalanced which is typical of real world data sets. Two popular approaches that have been applied for improving classification accuracy and statistical comparisons of imbalanced data sets are: synthetic minority over-sampling technique (SMOTE) and propensity score matching (PSM). A novel sampling approach is introduced referred to as over-sampling using propensity scores (OUPS) that blends the two and is simple and easy to perform resulting in improvement in accuracy and sensitivity over both SMOTE and PSM. The performance of our proposed approach is assessed using a simulation experiment and several performance metrics are shown where this approach fares and falls in comparison to the others.

We believe that recent advances in formal verification are on the verge of making formal verification a viable option for any protocol designer, assuming the designer understands the protocol well enough to explain why it works. We demonstrate this with an SMT-based proof checker developed at Intel called the Deductive Verification Framework (DVF). We show how DVF can be used to prove correct a classical, fault-tolerant, distributed protocol for consensus, and describe how a protocol expert starting from scratch, with little-to-no prior familiarity with SMT or DVF, was able to model the protocol and prove it correct in six days and nine pages.

Increasing variability in the manufacturing process and growing complexity of the integrated circuits has given rise to many design and verification challenges. Statistical analysis of circuits and current source based gate delay models have started to replace the conventional static timing analysis which uses lookup tables for gate delays. In this paper we develop a statistical current source based gate model. We use accurate analytical models for representing the parameters of the gate model as functions of process parameters. Using the proposed statistical gate model, the gate output signal is generated and modeled as process dependent variational waveform. We present a compact model for representation of the variational signal waveform. The proposed waveform model can accurately generate the signal waveform at any process corner for accurate timing analysis. We generated the prosed model for gates of a 90 nm industry library and validated with SPICE simulations. Our model for logic gates and variational waveforms showed very good correlation with SPICE. The maximum error across all validation experiments was close to 3%.

The inductance and coupling effects in interconnects and non-linear receiver loads has resulted in complex input signals and output loads for gates in the modern deep sub- micron CMOS technologies. As a result, the conventional method of timing characterization, which is based on lookup tables with input slew and output load capacitance as indices, is no longer adequate. The focus has now shifted to current source based standard cell models which are based on the fundamental property of transconductance of MOSFETs. In this paper1we propose a systematic methodology for obtaining a current based delay model for gates, which can accommodate both single (SIS) and multi-input (MIS) switching signals of arbitrary shape and complex non-linear output loads. We use an analytical model for the gate output current expressed as a function of the node voltages. This results in an average error less than 0.5% with maximum standard deviation of 2.5% in error when compared with SPICE for a large number of standard cells. When compared with SPICE, using the proposed models gives stage delay and output slew with an average error of less than 3% and 2% respectively for arbitrary inputs and output load combinations.

In this paper, we present a unified approach for the statistical timing and leakage analysis of circuits in the presence of intradie variations. The intradie variations in device parameters are modeled as a spatial stochastic process with a given covariance function. The covariance function is used to construct a Karhunen-Loeve expansion of the spatial process. This leads to representing the various parameters of all components on the chip in terms of a common set of abstract random variables. The leakage and propagation delay of each gate are represented as quadratic polynomials (QPs), which are elements of a vector space whose bases are multivariate quadratic orthogonal polynomials of the device parameters. In the case of signal arrival times, we describe an efficient method to propagate the QPs through the circuit to obtain a QP representation of the signal arrival times at the primary outputs. The analysis is extended to include sequential components so that flip-flop parameters and clock arrival times can be treated as random variables. This allows efficient estimation of the timing yield of the circuit. We show how a similar representation of QP can be used to model leakage of gates and develop an efficient method to compute a QP representation of the total chip leakage. The proposed techniques and quadratic models were exercised on ISCAS89 benchmark circuits and compared with Monte Carlo (MC) simulations. The results show that the techniques are very accurate and several orders of magnitude faster than MC simulation.

Binary Decision Diagrams (BDDs) often fail to exploit sharing between Boolean functions that differ only in their support variables. In a memory circuit, for example, the functions for the different bits of a word differ only in the data bit while the address decoding part of the function is identical. We present a symbolic representation approach using ordered function templates to exploit such regularity.Templates specify functionality without being bound to a specific set of variables. Functions are obtained by instantiating templates with a list of variables. We ensure canonicity of the representation by requiring that templates are normalized and argument lists are ordered. We also present algorithms for performing Boolean operations using this representation. Experiments with a prototype implementation built on top of CUDD indicate that function templates can dramatically reduce memory requirements for symbolic simulation of regular circuits.

Generalized Symbolic Trajectory Evaluation (GSTE) [17, 18, 19] is a very significant extension of STE that has the power to verify all ω-regular properties but at the same time preserves the benefits of the original STE [16]. It also extends the symbolic quaternary model used by STE to support seamless model refinement for efficiency and accuracy trade-off in GSTE model checking. In this paper, we present a case study on FIFO verification to illustrate the strength of GSTE and demonstrate its methodology in specifying and verifying large scale designs.

This paper describes the model checking effort for an arbiter core for the IBM CoreConnect Architecture. We present our verification methodology and describe how it was influenced by the architecture. We also present and analyze the bugs found and discuss the difficulties associated with verifying complex on-chip buses, highlighting the need for better tools and methodologies for their specification and verification.

We describe a visualization tool to aid aircraft designers during the conceptual design stage. The conceptual design for an aircraft is defined by a vector of 10-30 parameters. The goal is to find a vector that minimizes an objective function while meeting a series of constraints. VizCraft integrates the simulation code that evaluates the design with visualizations for analyzing the design individually or in contrast to other designs. VizCraft allows the designer to easily switch between the view of a design in the form of a parameter set, and a visualization of the corresponding aircraft. The user can easily see which, if any, constraints are violated. VizCraft also allows the user to view a database of designs using parallel coordinates.