Search

This paper presents verification-guided development (VGD), a software engineering process we used to build Cedar, a new policy language for expressive, fast, safe, and analyzable authorization. Developing a system with VGD involves writing an executable model of the system and mechanically proving properties about the model; writing production code for the system and using differential random testing (DRT) to check that the production code matches the model; and using property-based testing (PBT) to check properties of unmodeled parts of the production code. Using VGD for Cedar, we can build fast, idiomatic production code, prove our model correct, and find and fix subtle implementation bugs that evade code reviews and unit testing. While carrying out proofs, we found and fixed 4 bugs in Cedar's policy validator, and DRT and PBT helped us find and fix 21 additional bugs in various parts of Cedar.

Cedar is a new authorization policy language designed to be ergonomic, fast, safe, and analyzable. Rather than embed authorization logic in an application's code, developers can write that logic as Cedar policies and delegate access decisions to Cedar's evaluation engine. Cedar's simple and intuitive syntax supports common authorization use-cases with readable policies, naturally leveraging concepts from role-based, attribute-based, and relation-based access control models. Cedar's policy structure enables access requests to be decided quickly. Cedar's policy validator leverages optional typing to help policy writers avoid mistakes, but not get in their way. Cedar's design has been finely balanced to allow for a sound and complete logical encoding, which enables precise policy analysis, e.g., to ensure that when refactoring a set of policies, the authorized permissions do not change. We have modeled Cedar in the Lean programming language, and used Lean's proof assistant to prove important properties of Cedar's design. We have implemented Cedar in Rust, and released it open-source. Comparing Cedar to two open-source languages, OpenFGA and Rego, we find (subjectively) that Cedar has equally or more readable policies, but (objectively) performs far better.

As robots become more prevalent, the complexity of robot-robot, robot-human, and robot-environment interactions increases. In these interactions, a robot needs to consider not only the effects of its own actions, but also the effects of other agents' actions and the possible interactions between agents. Previous works have considered reactive synthesis, where the human/environment is modeled as a deterministic, adversarial agent; as well as probabilistic synthesis, where the human/environment is modeled via a Markov chain. While they provide strong theoretical frameworks, there are still many aspects of human-robot interaction that cannot be fully expressed and many assumptions that must be made in each model. In this work, we propose stochastic games as a general model for human-robot interaction, which subsumes the expressivity of all previous representations. In addition, it allows us to make fewer modeling assumptions and leads to more natural and powerful models of interaction. We introduce the semantics of this abstraction and show how existing tools can be utilized to synthesize strategies to achieve complex tasks with guarantees. Further, we discuss the current computational limitations and improve the scalability by two orders of magnitude by a new way of constructing models for PRISM-games., Comment: Accepted: ICRA 2024

The innovations in reactive synthesis from {\em Linear Temporal Logics over finite traces} (LTLf) will be amplified by the ability to verify the correctness of the strategies generated by LTLf synthesis tools. This motivates our work on {\em LTLf model checking}. LTLf model checking, however, is not straightforward. The strategies generated by LTLf synthesis may be represented using {\em terminating} transducers or {\em non-terminating} transducers where executions are of finite-but-unbounded length or infinite length, respectively. For synthesis, there is no evidence that one type of transducer is better than the other since they both demonstrate the same complexity and similar algorithms. In this work, we show that for model checking, the two types of transducers are fundamentally different. Our central result is that LTLf model checking of non-terminating transducers is \emph{exponentially harder} than that of terminating transducers. We show that the problems are EXPSPACE-complete and PSPACE-complete, respectively. Hence, considering the feasibility of verification, LTLf synthesis tools should synthesize terminating transducers. This is, to the best of our knowledge, the \emph{first} evidence to use one transducer over the other in LTLf synthesis., Comment: Accepted by ATVA 23

Enceladus is a primary target for astrobiology due to the $\rm H_2O$ plume ejecta measured by the Cassini spacecraft and the inferred subsurface ocean sustained by tidal heating. Sourcing the plumes via a direct connection from the ocean to the surface requires a fracture through the entire ice shell ($\sim$10 km). Here we explore an alternative mechanism in which shear heating within shallower tiger stripe fractures produces partial melting in the ice shell and interstitial convection allows fluid to be ejected as geysers. We use an idealized two-dimensional multiphase reactive transport model to simulate the thermomechanics of a mushy region generated by an upper bound estimate for the localized shear heating rate in a salty ice shell. From our simulations, we predict the temperature, porosity, salt content, melting rate, and liquid volume of an intrashell mushy zone surrounding a fracture. We find that the rate of internal melting can match the observed $\rm H_2O$ eruption rate and that there is sufficient brine volume within the mushy zone to sustain the geysers for $\sim350$ kyr without additional melting. The composition of the liquid brine is, however, distinct from that of the ocean, due to partial melting. This shear heating mechanism for geyser formation applies to Enceladus and other icy moons and has implications for our understanding of the geophysical processes and astrobiological potential of icy satellites., Comment: Main text (11 pages, 3 figures), supplement (16 pages, 7 figures, 1 table). Added new figures and discussion to the supplement

Reactive synthesis from high-level specifications that combine hard constraints expressed in Linear Temporal Logic LTL with soft constraints expressed by discounted-sum (DS) rewards has applications in planning and reinforcement learning. An existing approach combines techniques from LTL synthesis with optimization for the DS rewards but has failed to yield a sound algorithm. An alternative approach combining LTL synthesis with satisficing DS rewards (rewards that achieve a threshold) is sound and complete for integer discount factors, but, in practice, a fractional discount factor is desired. This work extends the existing satisficing approach, presenting the first sound algorithm for synthesis from LTL and DS rewards with fractional discount factors. The utility of our algorithm is demonstrated on robotic planning domains.

The physics of planetary climate features a variety of complex systems that are challenging to model as they feature turbulent flows. A key example is the heat flux from the upper ocean to the underside of sea ice which provides a key contribution to the evolution of the Arctic sea ice cover. Here, we develop a model of the turbulent ice-ocean heat flux using coupled ordinary stochastic differential equations to model fluctuations in the vertical velocity and temperature in the Arctic mixed layer. All the parameters in the model are determined from observational data. A detailed comparison between the model results and measurements made during the Surface Heat Budget of the Arctic Ocean (SHEBA) project reveals that the model is able to capture the probability density functions (PDFs) of velocity, temperature and heat flux fluctuations. Furthermore, we show that the temperature in the upper layer of the Arctic ocean can be treated as a passive scalar during the whole year of SHEBA measurements. The stochastic model developed here provides a computationally inexpensive way to compute an observationally consistent PDF of this heat flux, and has implications for its parametrization in regional and global climate models., Comment: 8 pages, 6 figures

Motivated by the mushy zones of sea ice, volcanoes, and icy moons of the outer solar system, we perform a theoretical and numerical study of boundary-layer convection along a vertical heated wall in a bounded ideal mushy region. The mush is comprised of a porous and reactive binary alloy with a mixture of saline liquid in a solid matrix, and is studied in the near-eutectic approximation. Here we demonstrate the existence of four regions and study their behavior asymptotically. Starting from the bottom of the wall, the four regions are (i) an isotropic corner region; (ii) a buoyancy dominated vertical boundary layer; (iii) an isotropic connection region; and (iv) a horizontal boundary layer at the top boundary with strong gradients of pressure and buoyancy. Scalings from numerical simulations are consistent with the theoretical predictions. Close to the heated wall, the convection in the mushy layer is similar to a rising buoyant plume abruptly stopped at the top, leading to increased pressure and temperature in the upper region, whose impact is discussed as an efficient melting mechanism.

Many systems are naturally modeled as Markov Decision Processes (MDPs), combining probabilities and strategic actions. Given a model of a system as an MDP and some logical specification of system behavior, the goal of synthesis is to find a policy that maximizes the probability of achieving this behavior. A popular choice for defining behaviors is Linear Temporal Logic (LTL). Policy synthesis on MDPs for properties specified in LTL has been well studied. LTL, however, is defined over infinite traces, while many properties of interest are inherently finite. Linear Temporal Logic over finite traces (LTLf) has been used to express such properties, but no tools exist to solve policy synthesis for MDP behaviors given finite-trace properties. We present two algorithms for solving this synthesis problem: the first via reduction of LTLf to LTL and the second using native tools for LTLf. We compare the scalability of these two approaches for synthesis and show that the native approach offers better scalability compared to existing automaton generation tools for LTL., Comment: In Proceedings GandALF 2020, arXiv:2009.09360

We use well resolved numerical simulations with the Lattice Boltzmann Method to study Rayleigh-B\'enard convection in cells with a fractal boundary in two dimensions for $Pr = 1$ and $Ra \in \left[10^7, 10^{10}\right]$. The fractal boundaries are functions characterized by power spectral densities $S(k)$ that decay with wavenumber, $k$, as $S(k) \sim k^{p}$ ($p < 0$). The degree of roughness is quantified by the exponent $p$ with $p < -3$ for smooth (differentiable) surfaces and $-3 \le p < -1$ for rough surfaces with Hausdorff dimension $D_f=\frac{1}{2}(p+5)$. By computing the exponent $\beta$ in power law fits $Nu \sim Ra^{\beta}$, where $Nu$ and $Ra$ are the Nusselt and the Rayleigh numbers for $Ra \in \left[10^8, 10^{10}\right]$, we observe that heat transport scaling increases with roughness over the top two decades of $Ra \in \left[10^8, 10^{10}\right]$. For $p$ $= -3.0$, $-2.0$ and $-1.5$ we find $\beta = 0.288 \pm 0.005, 0.329 \pm 0.006$ and $0.352 \pm 0.011$, respectively. We also observe that the Reynolds number, $Re$, scales as $Re \sim Ra^{\xi}$, where $\xi \approx 0.57$ over $Ra \in \left[10^7, 10^{10}\right]$, for all $p$ used in the study. For a given value of $p$, the averaged $Nu$ and $Re$ are insensitive to the specific realization of the roughness., Comment: 15 pages, 13 figures

The Human Cell Atlas (HCA) will be made up of comprehensive reference maps of all human cells - the fundamental units of life - as a basis for understanding fundamental human biological processes and diagnosing, monitoring, and treating disease. It will help scientists understand how genetic variants impact disease risk, define drug toxicities, discover better therapies, and advance regenerative medicine. A resource of such ambition and scale should be built in stages, increasing in size, breadth, and resolution as technologies develop and understanding deepens. We will therefore pursue Phase 1 as a suite of flagship projects in key tissues, systems, and organs. We will bring together experts in biology, medicine, genomics, technology development and computation (including data analysis, software engineering, and visualization). We will also need standardized experimental and computational methods that will allow us to compare diverse cell and tissue types - and samples across human communities - in consistent ways, ensuring that the resulting resource is truly global. This document, the first version of the HCA White Paper, was written by experts in the field with feedback and suggestions from the HCA community, gathered during recent international meetings. The White Paper, released at the close of this yearlong planning process, will be a living document that evolves as the HCA community provides additional feedback, as technological and computational advances are made, and as lessons are learned during the construction of the atlas.

Most of the recent power line communication (PLC) systems and standards, both narrow-band and broadband, are based on orthogonal frequency-division multiplexing (OFDM). This multiplexing scheme however suffers from the high peak-to-average power ratio (PAPR) which can considerably impact the energy efficiency, size and cost of PLC modems as well as cause electromagnetic compatibility (EMC) issues. This paper investigates the performance of vector OFDM (VOFDM), which has inherently better PAPR properties, over non-Gaussian broadband PLC channels equipped with two nonlinear preprocessors at the receiver. In addition, the low PAPR property of the VOFDM system is exploited to further enhance the efficiency of the nonlinear preprocessors. The achievable gains are studied in terms of the complementary cumulative distribution function of the PAPR, probability of noise detection error and the signal-to-noise ratio at the output of the nonlinear preprocessors. For comparison's sake, the performance of conventional OFDM systems is also presented throughout the paper. Results reveal that the proposed system is able to provide up to 2 dB saving in the transmit power relative to the conventional OFDM under same system conditions, which eventually also translates into a system that is more resilient to EMC limits, reduced cost and size of PLC modems. It is also shown that the achievable gains become more significant as the vector block (VB) size of the VOFDM system is increased.

The physics of ice crystal growth from the liquid phase, especially in the presence of salt, has received much less attention than the growth of snow crystals from the vapour phase. The growth of so-called frazil ice by solidification of a supercooled aqueous salt solution is consistent with crystal growth in the basal plane being limited by the diffusive removal of the latent heat of solidification from the solid--liquid interface, while being limited by attachment kinetics in the perpendicular direction. This leads to the formation of approximately disk-shaped crystals with a low aspect ratio of thickness compared to radius, because radial growth is much faster than axial growth. We calculate numerically how fast disk-shaped crystals grow in both pure and binary melts, accounting for the comparatively slow axial growth, the effect of dissolved solute in the fluid phase and the difference in thermal properties between solid and fluid phases. We identify the main physical mechanisms that control crystal growth and show that the diffusive removal of both the latent heat released and also the salt rejected at the growing interface are significant. Our calculations demonstrate that certain previous parameterizations, based on scaling arguments, substantially underestimate crystal growth rates by a factor of order 10-100 for low aspect ratio disks, and provide a parameterization for use in models of ice crystal growth in environmental settings., Comment: 11 pages, 9 figures. Updated version with some additional discussion and references, mostly in the introduction. We tested a further two models of axial growth in section III, and added a new figure in that section